Stable model semantics for guarded existential rules and description logics: decidability and complexity

Georg Gottlob, André Hernich, Clemens Kupke, Thomas Lukasiewicz

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
10 Downloads (Pure)


This work investigates the decidability and complexity of database query answering under guarded existential rules with nonmonotonic negation according to the classical stable model semantics. In this setting, existential quantification is interpreted via Skolem functions, and the unique name assumption is adopted. As a first result, we show the decidability of answering first-order queries based on such rules by a translation into the satisfiability problem for guarded second-order formulas having the tree-model property. To obtain precise complexity results for unions of conjunctive queries, we transform the original problem in polynomial time into an intermediate problem that is easier to analyze: query answering for guarded disjunctive existential rules with stratified negation. We obtain precise bounds for the general setting and for various restricted settings. We also consider extensions of the original formalism with negative constraints, keys, and the possibility of negated atoms in queries. Finally, we show how the above results can be used to provide decidability and complexity results for a natural adaptation of the stable model semantics to description logics such as ELHI and the DL-Lite family.
Original languageEnglish
Article number35
Pages (from-to)1-87
Number of pages87
JournalJournal of the ACM
Issue number5
Publication statusPublished - 22 Oct 2021


  • stable model
  • semantics
  • guarded existential rules
  • description logics
  • decidability
  • complexity


Dive into the research topics of 'Stable model semantics for guarded existential rules and description logics: decidability and complexity'. Together they form a unique fingerprint.

Cite this