Decidability of Querying First-Order Theories via Countermodels of Finite Width
This work addresses the challenge of establishing decidability in logical querying for researchers in computational logic and database theory, though it appears incremental as it builds on existing width measures and stratification concepts.
The authors tackled the problem of determining decidability for logical entailment problems by introducing a framework based on countermodels with finite width measures, such as treewidth and cliquewidth, and demonstrated its application to existential rules, covering both known and new decidable classes.
We propose a generic framework for establishing the decidability of a wide range of logical entailment problems (briefly called querying), based on the existence of countermodels that are structurally simple, gauged by certain types of width measures (with treewidth and cliquewidth as popular examples). As an important special case of our framework, we identify logics exhibiting width-finite finitely universal model sets, warranting decidable entailment for a wide range of homomorphism-closed queries, subsuming a diverse set of practically relevant query languages. As a particularly powerful width measure, we propose to employ Blumensath's partitionwidth, which subsumes various other commonly considered width measures and exhibits highly favorable computational and structural properties. Focusing on the formalism of existential rules as a popular showcase, we explain how finite partitionwidth sets of rules subsume other known abstract decidable classes but - leveraging existing notions of stratification - also cover a wide range of new rulesets. We expose natural limitations for fitting the class of finite unification sets into our picture and suggest several options for remedy.