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

Clemens Kupke, Georg Gottlob, Thomas Lukasiewicz, Andre Hernich

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

41 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence
Pages757-764
Number of pages8
Publication statusPublished - 2012
EventAAAI-2012: Twenty-Sixth Conference on Artificial Inetelligence - Toronto, Canada
Duration: 24 Jul 2012 → …

Conference

ConferenceAAAI-2012: Twenty-Sixth Conference on Artificial Inetelligence
CountryCanada
CityToronto
Period24/07/12 → …

Fingerprint

Semantics
Ontology

Keywords

  • datalog
  • artificial intelligence

Cite this

Kupke, C., Gottlob, G., Lukasiewicz, T., & Hernich, A. (2012). Equality-friendly well-founded semantics and applications to description logics. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence (pp. 757-764)
Kupke, Clemens ; Gottlob, Georg ; Lukasiewicz, Thomas ; Hernich, Andre. / Equality-friendly well-founded semantics and applications to description logics. Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. 2012. pp. 757-764
@inproceedings{31d2c1fb89644acbacbb5dbafa9eb661,
title = "Equality-friendly well-founded semantics and applications to description logics",
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.",
keywords = "datalog, artificial intelligence",
author = "Clemens Kupke and Georg Gottlob and Thomas Lukasiewicz and Andre Hernich",
year = "2012",
language = "English",
isbn = "978-1-57735-568-7",
pages = "757--764",
booktitle = "Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence",

}

Kupke, C, Gottlob, G, Lukasiewicz, T & Hernich, A 2012, Equality-friendly well-founded semantics and applications to description logics. in Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. pp. 757-764, AAAI-2012: Twenty-Sixth Conference on Artificial Inetelligence, Toronto, Canada, 24/07/12.

Equality-friendly well-founded semantics and applications to description logics. / Kupke, Clemens; Gottlob, Georg; Lukasiewicz, Thomas; Hernich, Andre.

Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. 2012. p. 757-764.

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

TY - GEN

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

AU - Kupke, Clemens

AU - Gottlob, Georg

AU - Lukasiewicz, Thomas

AU - Hernich, Andre

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - datalog

KW - artificial intelligence

UR - http://www.aaai.org/Press/Proceedings/aaai12.php

UR - http://www2.informatik.hu-berlin.de/~hernich/pub/aaai12.pdf

M3 - Conference contribution book

SN - 978-1-57735-568-7

SP - 757

EP - 764

BT - Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence

ER -

Kupke C, Gottlob G, Lukasiewicz T, Hernich A. Equality-friendly well-founded semantics and applications to description logics. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. 2012. p. 757-764