Inproceedings3346

PublikationenPublications

• Nach AutorBy Author
  • Thomas FellerThomas Feller
  • Tim LyonTim Lyon
  • Piotr Ostropolski-NalewajaPiotr Ostropolski-Nalewaja
  • Sebastian RudolphSebastian Rudolph
• Nach ForschungsgruppeBy Research Group
  • Computational LogicComputational Logic

Toggle side column

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}
}