Finite Axiomatizability by Disjunctive Existential Rules (Extended Abstract)

摘要

Rule-based languages lie at the core of several areas of central importance to databases and artificial intelligence such as deductive databases and knowledge representation and reasoning. 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 precisely, given a collection C of relational structures, we show that C is axiomatizable via a finite set R of disjunctive existential rules (i.e., C is precisely the set of models of R) iff C enjoys certain model-theoretic properties. This is achieved by using the well-known property of criticality, a refined version of closure under direct products, and a novel property called diagrammatic compatibility that relies on the method of diagrams.