Computing Datalog Rewritings for Disjunctive Datalog Programs and Description Logic Ontologies

被引：0

作者：

Kaminski, Mark ^{[1
]}

Nenov, Yavor ^{[1
]}

Grau, Bernardo Cuenca ^{[1
]}

机构：

[1] Univ Oxford, Dept Comp Sci, Oxford OX1 2JD, England

来源：

WEB REASONING AND RULE SYSTEMS, RR 2014 | 2014年 / 8741卷

基金：

英国工程与自然科学研究理事会;

关键词：

FAMILY;

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We study the closely related problems of rewriting disjunctive datalog programs and non-Horn DL ontologies into plain datalog programs that entail the same facts for every dataset. We first propose the class of markable disjunctive datalog programs, which is efficiently recognisable and admits polynomial rewritings into datalog. Markability naturally extends to SHI ontologies, and markable ontologies admit (possibly exponential) datalog rewritings. We then turn our attention to resolution-based rewriting techniques. We devise an enhanced rewriting procedure for disjunctive datalog, and propose a second class of SHI ontologies that admits exponential datalog rewritings via resolution. Finally, we focus on conjunctive query answering over disjunctive datalog programs. We identify classes of queries and programs that admit datalog rewritings and study the complexity of query answering in this setting. We evaluate the feasibility of our techniques over a large corpus of ontologies, with encouraging results.

引用

页码：76 / 91

页数：16