Equality-friendly well-founded semantics and applications to description logics

Kupke, Clemens and Gottlob, Georg and Lukasiewicz, Thomas and Hernich, Andre; (2012) Equality-friendly well-founded semantics and applications to description logics. In: Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. Association for the Advancement of Artificial Intelligence (AAAI), CAN, pp. 757-764. ISBN 978-1-57735-568-7

[thumbnail of aaai12.pdf]
Preview
 PDF. Filename: aaai12.pdf
Final Published Version
Download (372kB)| Preview

Abstract

We tackle the problem of defining a well-founded semantics (WFS) for Datalog rules with existentially quantified variables in their heads and nega- tions 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-stratified nonmonotonic nega- tion in rule bodies, and we define a WFS for this generalization via guarded fixed 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 profiles 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 defi- 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.

CORE (COnnecting REpositories)