Polynomial Horn Rewritings for Description Logics Ontologies
Mark Stefan Kaminski, Bernardo Cuenca Grau · Description Logics · 2015
We study the problem of rewriting an ontology O1 in a DL L1 into an ontology O2 in a Horn DL L2 such that O1 and O2 are equisatisfiable when extended with any dataset. After showing undecidability whenever L1 extends ALCF , we focus on devising efficiently checkable conditions that ensure existence of a Horn rewriting. By lifting existing Datalog rewriting techniques for Disjunctive Datalog programs to firstorder programs with function symbols, we identify a class of ontologies that admit Horn rewritings of polynomial size. Our experiments indicate that many real-world ontologies admit such polynomial Horn rewritings.