Finite-Cliquewidth Sets of Existential Rules textendash Toward a General Criterion for Decidable yet Highly Expressive Querying
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Konferenzband › Beigetragen › Begutachtung
Beitragende
Abstract
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.
Details
Originalsprache | Englisch |
---|---|
Titel | Proceedings of the 26th International Conference on Database Theory (ICDT 2023) |
Redakteure/-innen | Floris Geerts, Brecht Vandevoort |
Herausgeber (Verlag) | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Seiten | 18:1-18:18 |
ISBN (elektronisch) | 9783959772709 |
Publikationsstatus | Veröffentlicht - 1 März 2023 |
Peer-Review-Status | Ja |
Publikationsreihe
Reihe | Leibniz international proceedings in informatics : LIPIcs |
---|---|
Band | 255 |
ISSN | 1868-8969 |
Externe IDs
Scopus | 85150686731 |
---|---|
ORCID | /0000-0003-3214-0828/work/173054743 |
Schlagworte
ASJC Scopus Sachgebiete
Schlagwörter
- TGDs, bounded-treewidth sets, cliquewidth, datalog, existential rules, finite-unification sets, first-order rewritability, monadic second-order logic, treewidth