Datalog Rewriting Techniques for Non−Horn Ontologies
Mark Stefan Kaminski, Yavor Nenov, Bernardo Cuenca Grau · Oxford University Research Archive (ORA) (University of Oxford) · 2014
Abstract. We study the closely related problems of rewriting disjunc-tive 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. Markabil-ity 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 resolution rewriting procedure for disjunctive datalog, and propose a second class of SHI ontologies that admits exponential datalog rewritings via reso-lution. Finally, we evaluate the feasibility of our techniques over a large corpus of ontologies, with encouraging results. 1