Equality−Friendly Well−Founded Semantics and Applications to Description Logics
Georg Gottlob‚ André Hernich‚ Clemens Kupke and Thomas Lukasiewicz
We tackle the problem of deﬁning a well-founded semantics (WFS) for Datalog rules with existentially quantiﬁed variables in their heads and negations in their bodies. In particular, we provide a WFS for the recent Datalog family of ontology languages, which covers several important description logics (DLs). To do so, we generalize Datalog by non-stratiﬁed nonmonotonic negation in rule bodies, and we deﬁne a WFS for this generalization via guarded ﬁxed point logic. We refer to this approach as equality-friendly WFS, since it has the advantage that it does not make the unique name assumption (UNA); this brings it close to OWL and its proﬁles as well as typical DLs, which also do not make the UNA. We prove that for guarded Datalog with negation under the equality-friendly WFS, conjunctive query answering is decidable, and we provide precise complexity results for this problem. From these results, we obtain precise deﬁnitions of the standard WFS extensions of EL and of members of the DL-Lite family, as well as corresponding complexity results for query answering.