Finite-Cliquewidth Sets of Existential Rules – Toward a General Criterion for Decidable yet Highly Expressive Querying

Thomas FellerThomas Feller, Tim LyonTim Lyon, Piotr Ostropolski-NalewajaPiotr Ostropolski-Nalewaja, Sebastian RudolphSebastian Rudolph

ISBN: 978-3-95977-270-9
ISSN: 1868-8969
Download
Slides
DOI Link

Thomas Feller, Tim Lyon, Piotr Ostropolski-Nalewaja, Sebastian Rudolph
Finite-Cliquewidth Sets of Existential Rules – Toward a General Criterion for Decidable yet Highly Expressive Querying
In Geerts, Floris and Vandevoort, Brecht, eds., Proceedings of the 26th International Conference on Database Theory (ICDT 2023), volume 255 of Leibniz International Proceedings in Informatics (LIPIcs), 18:1-18:18, March 2023. Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Details
Bibtex

KurzfassungAbstract
In our pursuit of generic criteria for decidable ontology-based querying, we introduce finite-cliquewidth sets (fcs) of existential rules, a model-theoretically defined class of rule sets, inspired by the clique- width measure from graph theory. By a generic argument, we show that fcs ensures decidability of entailment for a sizable class of queries (dubbed DaMSOQs) subsuming conjunctive queries (CQs). The fcs class properly generalizes the class of finite-expansion sets (fes), and for signatures of arity ≤2, the class of bounded-treewidth sets (bts). For higher arities, bts is only indirectly subsumed by fcs by means of reification. Despite the generality of fcs, we provide a rule set with decidable CQ entailment (by virtue of first-order-rewritability) that falls outside fcs, thus demonstrating the incomparability of fcs and the class of finite-unification sets (fus). In spite of this, we show that if we restrict ourselves to single-headed rule sets over signatures of arity ≤2, then fcs subsumes fus.
Projekt:Project: DeciGUT
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@inproceedings{FLOR2023,
  author    = {Thomas Feller and Tim Lyon and Piotr Ostropolski-Nalewaja and
               Sebastian Rudolph},
  title     = {Finite-Cliquewidth Sets of Existential Rules {\textendash} Toward
               a General Criterion for Decidable yet Highly Expressive Querying},
  editor    = {Geerts and Floris and Vandevoort and Brecht},
  booktitle = {Proceedings of the 26th International Conference on Database
               Theory (ICDT 2023)},
  series    = {Leibniz International Proceedings in Informatics (LIPIcs)},
  volume    = {255},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year      = {2023},
  month     = {March},
  pages     = {18:1-18:18},
  doi       = {10.4230/LIPIcs.ICDT.2023.18}
}