# Finite-Cliquewidth Sets of Existential Rules: Toward a General Criterion for Decidable yet Highly Expressive Querying

arXiv: https://arxiv.org/abs/2209.02464 · HTML: https://mlsanity.com/paper/2209.02464/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 49 references that are in the map.
- First posted on arXiv 6 Sep 2022.

## Builds on (most cited first, 4 of 4)

- [Query Rewriting and Optimization for Ontological Databases](https://mlsanity.com/paper/1405.2848/) (2014)
- [Combining Existential Rules and Transitivity: Next Steps](https://mlsanity.com/paper/1504.07443/) (2015)
- [Finite Model Theory of the Triguarded Fragment and Related Logics](https://mlsanity.com/paper/2101.08377/) (2021)
- [A Journey to the Frontiers of Query Rewritability](https://mlsanity.com/paper/2012.11269/) (2020)

## Built on by (most cited first, 4 of 4)

- [Decidability of Querying First-Order Theories via Countermodels of Finite Width](https://mlsanity.com/paper/2304.06348/) (2023)
- [Connecting Proof Theory and Knowledge Representation: Sequent Calculi and the Chase with Existential Rules](https://mlsanity.com/paper/2306.02521/) (2023)
- [Derivation-Graph-Based Characterizations of Decidable Existential Rule Sets](https://mlsanity.com/paper/2307.08481/) (2023)
- [The Sticky Path to Expressive Querying: Decidability of Navigational Queries under Existential Rules](https://mlsanity.com/paper/2407.14384/) (2024)

## Abstract (arXiv)

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 at most 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 at most 2, then FCS subsumes FUS.