Résumé | (or three complexity dichotomy theorems for existential first-order)
It is known that the data complexity of a Conjunctive Query (CQ) is determined only by the way its variables are shared between atoms, reflected by its hypergraph. In particular, Yannakakis [Yan81, BFMY83] proved that a CQ is decidable in linear time when it is alpha- acyclic, i.e. its hypergraph is alpha-acyclic; Bagan et al. [BDG07] even state: "Any CQ is decidable in linear time iff it is alpha-acyclic (under certain hypotheses)". They also prove a similar result for the enumeration problem.
Since the complexity of a Negative Conjunctive Query (NCQ), a conjunctive query where all atoms are negated, also only depends on its hypergraph, there must be a similar dichotomy in this case. We show that: "Any NCQ is decidable in linear time iff it is beta-acyclic (under certain hypotheses)" and also give a similar result for the enumeration problem.
If we consider Signed Conjunctive Query (SCQ), a conjunctive query where *some* atoms are negated, we need to introduce a notion of acyclicity of bicolored hypergraphs, that generalizes both alpha and beta acyclicities. With this notion, we finally generalize both previous dichotomy theorems in a single one, that deals with both the decision and the enumeration problems. This dichotomy theorem implies that beta-acyclic existential first-order queries are decidable in linear time, and that this hypergraph criterion is optimal. |