Finite Axiomatizability by Disjunctive Existential Rules

Rule-based languages lie at the core of several areas of cen- tral importance to databases and artificial intelligence such as deductive databases and knowledge representation and rea- soning. Disjunctive existential rules (a.k.a. disjunctive tuple- generating dependencies in the database literature) form such a prominent rule-based language. The goal of this work is to pinpoint the expressive power of disjunctive existential rules in terms of insightful model-theoretic properties. More pre- cisely, given a collection C of relational structures, we show that C is axiomatizable via a finite set Σ of disjunctive exis- tential rules (i.e., C is precisely the set of models of Σ) iff C enjoys certain model-theoretic properties. This is achieved by using the well-known property of criticality, a refined ver- sion of closure under direct products, and a novel property called diagrammatic compatibility that relies on the method of diagrams. We further establish analogous characterizations for the well-behaved classes of linear and guarded disjunctive existential rules by adopting refined versions of diagrammatic compatibility that consider the syntactic restrictions imposed by linearity and guardedness; this illustrates the robustness of diagrammatic compatibility. We finally exploit diagrammatic compatibility to rewrite a set of guarded disjunctive existen- tial rules into an equivalent set that falls in the weaker class of linear disjunctive existential rules, if one exists.