Dynamic conjunctive queries

摘要

The article investigates classes of queries maintainable by conjunctive queries and their extensions and restrictions in the dynamic complexity framework of Patnaik and Immerman. Starting from the basic language of quantifier-free conjunctions of positive atoms, it studies the impact of additional operators and features — such as union, atomic negation and quantification — on the dynamic expressiveness, for the standard semantics as well as for Δ-semantics. The article identifies a linear hierarchy of five main fragments for the standard semantics, characterized by the addition of (1) arbitrary quantification and atomic negation, (2) existential quantification and atomic negation, (3) existential quantification, (4) atomic negation (but no quantification), and by (5) no addition to the basic language at all. While fragments (3), (4) and (5) can be separated, it remains open whether fragments (1), (2) and (3) are actually different. The fragments arising from Δ-semantics are also subsumed by the standard fragments (1), (2) and (4). Other fragments of DynFO also fit into this linear hierarchy.