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.
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.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence |
| Pages | 757-764 |
| Number of pages | 8 |
| Publication status | Published - 2012 |
| Event | AAAI-2012: Twenty-Sixth Conference on Artificial Inetelligence - Toronto, Canada Duration: 24 Jul 2012 → … |
Conference
| Conference | AAAI-2012: Twenty-Sixth Conference on Artificial Inetelligence |
|---|---|
| Country/Territory | Canada |
| City | Toronto |
| Period | 24/07/12 → … |
Keywords
- datalog
- artificial intelligence