Finite-Cliquewidth Sets of Existential Rules: Toward a General Criterion for Decidable yet Highly Expressive Querying
This work addresses the challenge of developing decidable yet expressive querying methods for ontologies, which is incremental as it builds upon and generalizes existing classes like finite-expansion sets.
The paper tackles the problem of finding generic criteria for decidable ontology-based querying by introducing finite-cliquewidth sets (FCS) of existential rules, showing that FCS ensures decidability of entailment for a class of queries including conjunctive queries, and demonstrating that FCS generalizes finite-expansion sets and bounded-treewidth sets for low arities.
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.