Finite-Cliquewidth Sets of Existential Rules

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
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},
  booktitle = {Proceedings of the 26th International Conference on Database
               Theory (ICDT 2023)},
  year      = {2023}
}