Well-Founded Semantics for Extended Datalog and Ontological Reasoning

Clemens Kupke, Georg Gottlob, Thomas Lukasiewicz, Andre Hernich

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

19 Citations (Scopus)

Abstract

The Datalog± family of expressive extensions of Datalog has recently been introduced as a new paradigm for query answering over ontologies, which captures and extends several common description logics. It extends plain Datalog by features such as existentially quantified rule heads and, at the same time, restricts the rule syntax so as to achieve decidability and tractability. In this paper, we continue the research on Datalog±. More precisely, we generalize the well-founded semantics (WFS), as the standard semantics for nonmonotonic normal programs in the database context, to Datalog± programs with negation under the unique name assumption (UNA). We prove that for guarded Datalog± with negation under the standard WFS, answering normal Boolean conjunctive queries is decidable, and we provide precise complexity results for this problem, namely, in particular, completeness for PTIME (resp., 2-EXPTIME) in the data (resp., combined) complexity.
LanguageEnglish
Title of host publicationProceedings of the 32nd Symposium on Principles of Database Systems
Place of PublicationNew York
Pages225-236
Number of pages12
DOIs
Publication statusPublished - Jun 2013

Fingerprint

Semantics
Computability and decidability
Ontology

Keywords

  • ontological reasoning
  • Datalog
  • semantics

Cite this

Kupke, C., Gottlob, G., Lukasiewicz, T., & Hernich, A. (2013). Well-Founded Semantics for Extended Datalog and Ontological Reasoning. In Proceedings of the 32nd Symposium on Principles of Database Systems (pp. 225-236). New York. https://doi.org/10.1145/2463664.2465229
Kupke, Clemens ; Gottlob, Georg ; Lukasiewicz, Thomas ; Hernich, Andre. / Well-Founded Semantics for Extended Datalog and Ontological Reasoning. Proceedings of the 32nd Symposium on Principles of Database Systems. New York, 2013. pp. 225-236
@inproceedings{b11109fbc4524ec99531da73ad49c374,
title = "Well-Founded Semantics for Extended Datalog and Ontological Reasoning",
abstract = "The Datalog± family of expressive extensions of Datalog has recently been introduced as a new paradigm for query answering over ontologies, which captures and extends several common description logics. It extends plain Datalog by features such as existentially quantified rule heads and, at the same time, restricts the rule syntax so as to achieve decidability and tractability. In this paper, we continue the research on Datalog±. More precisely, we generalize the well-founded semantics (WFS), as the standard semantics for nonmonotonic normal programs in the database context, to Datalog± programs with negation under the unique name assumption (UNA). We prove that for guarded Datalog± with negation under the standard WFS, answering normal Boolean conjunctive queries is decidable, and we provide precise complexity results for this problem, namely, in particular, completeness for PTIME (resp., 2-EXPTIME) in the data (resp., combined) complexity.",
keywords = "ontological reasoning , Datalog, semantics",
author = "Clemens Kupke and Georg Gottlob and Thomas Lukasiewicz and Andre Hernich",
year = "2013",
month = "6",
doi = "10.1145/2463664.2465229",
language = "English",
isbn = "978-1-4503-2066-5",
pages = "225--236",
booktitle = "Proceedings of the 32nd Symposium on Principles of Database Systems",

}

Kupke, C, Gottlob, G, Lukasiewicz, T & Hernich, A 2013, Well-Founded Semantics for Extended Datalog and Ontological Reasoning. in Proceedings of the 32nd Symposium on Principles of Database Systems. New York, pp. 225-236. https://doi.org/10.1145/2463664.2465229

Well-Founded Semantics for Extended Datalog and Ontological Reasoning. / Kupke, Clemens; Gottlob, Georg; Lukasiewicz, Thomas; Hernich, Andre.

Proceedings of the 32nd Symposium on Principles of Database Systems. New York, 2013. p. 225-236.

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

TY - GEN

T1 - Well-Founded Semantics for Extended Datalog and Ontological Reasoning

AU - Kupke, Clemens

AU - Gottlob, Georg

AU - Lukasiewicz, Thomas

AU - Hernich, Andre

PY - 2013/6

Y1 - 2013/6

N2 - The Datalog± family of expressive extensions of Datalog has recently been introduced as a new paradigm for query answering over ontologies, which captures and extends several common description logics. It extends plain Datalog by features such as existentially quantified rule heads and, at the same time, restricts the rule syntax so as to achieve decidability and tractability. In this paper, we continue the research on Datalog±. More precisely, we generalize the well-founded semantics (WFS), as the standard semantics for nonmonotonic normal programs in the database context, to Datalog± programs with negation under the unique name assumption (UNA). We prove that for guarded Datalog± with negation under the standard WFS, answering normal Boolean conjunctive queries is decidable, and we provide precise complexity results for this problem, namely, in particular, completeness for PTIME (resp., 2-EXPTIME) in the data (resp., combined) complexity.

AB - The Datalog± family of expressive extensions of Datalog has recently been introduced as a new paradigm for query answering over ontologies, which captures and extends several common description logics. It extends plain Datalog by features such as existentially quantified rule heads and, at the same time, restricts the rule syntax so as to achieve decidability and tractability. In this paper, we continue the research on Datalog±. More precisely, we generalize the well-founded semantics (WFS), as the standard semantics for nonmonotonic normal programs in the database context, to Datalog± programs with negation under the unique name assumption (UNA). We prove that for guarded Datalog± with negation under the standard WFS, answering normal Boolean conjunctive queries is decidable, and we provide precise complexity results for this problem, namely, in particular, completeness for PTIME (resp., 2-EXPTIME) in the data (resp., combined) complexity.

KW - ontological reasoning

KW - Datalog

KW - semantics

UR - http://ceur-ws.org/Vol-1014/paper_78.pdf

U2 - 10.1145/2463664.2465229

DO - 10.1145/2463664.2465229

M3 - Conference contribution book

SN - 978-1-4503-2066-5

SP - 225

EP - 236

BT - Proceedings of the 32nd Symposium on Principles of Database Systems

CY - New York

ER -

Kupke C, Gottlob G, Lukasiewicz T, Hernich A. Well-Founded Semantics for Extended Datalog and Ontological Reasoning. In Proceedings of the 32nd Symposium on Principles of Database Systems. New York. 2013. p. 225-236 https://doi.org/10.1145/2463664.2465229