2026-07-22T14:20:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17760 2024-03-06T11:00:25Z ddc:004 open_access

Finite-Cliquewidth Sets of Existential Rules: Toward a General Criterion for Decidable yet Highly Expressive Querying Feller, Thomas Lyon, Tim S. Ostropolski-Nalewaja, Piotr Rudolph, Sebastian existential rules TGDs cliquewidth treewidth bounded-treewidth sets finite-unification sets first-order rewritability monadic second-order logic datalog 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 cliquewidth 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Feller and Tim S. Lyon and Piotr Ostropolski-Nalewaja and Sebastian Rudolph 2023 Is Part Of LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2023.18 urn:nbn:de:0030-drops-177602 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.18 eng https://creativecommons.org/licenses/by/4.0/legalcode