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

Download

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
Proceedings of the 26th International Conference on Database Theory (ICDT 2023), to appear

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: Toward a General
               Criterion for Decidable yet Highly Expressive Querying},
  booktitle = {Proceedings of the 26th International Conference on Database
               Theory (ICDT 2023)},
  year      = {2023}
}