A Negative Conjunctive Query is Easy if and only if it is Beta-Acyclic

Abstract

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 [Yannakakis VLDB'81,Beeri/Fagin/Maier/Yannakakis JACM'83] proved that a CQ is decidable in linear time when it is alpha-acyclic, i.e. its hypergraph is alpha-acyclic; Bagan et al. [Bagan/Durand/Grandjean CSL'07] even state:

* Any CQ is decidable in linear  time iff it is alpha-acyclic. (under certain hypotheses)
(By linear time, we mean a query on a structure S can be decided in time O(|S|))
A natural question is: since the complexity of a *Negative* Conjunctive Query (NCQ), a conjunctive query where *all* atoms are negated, also only depends on its hypergraph, can we find a similar dichotomy in this case?

To answer this question, we revisit a result of Ordyniak et al. --- that states that satisfiability of a beta-acyclic CNF formula is decidable in polynomial time --- by proving that some part of their procedure can be done in linear time. This implies, under an algorithmic hypothesis that is likely true: (precisely: one cannot decide whether a graph is triangle-free in time O(n²log n) where n is the number of vertices.)

* Any NCQ is decidable in quasi-linear time iff it is beta-acyclic.
(By quasi-linear time, we mean a query on a structure S can be decided in time O(|S|log|S|))
We extend the easiness result to 'Signed' Conjunctive Query (SCQ) where 'some' atoms are negated. This has great interest since using some negated atoms is natural in the frameworks of databases and CSP. Furthermore, it implies straightforwardly the following:

* Any beta-acyclic existential first-order query is decidable in quasi-linear time.