BraultBaron, Johann
A Negative Conjunctive Query is Easy if and only if it is BetaAcyclic
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 alphaacyclic, i.e. its hypergraph is alphaacyclic; Bagan et al. [Bagan/Durand/Grandjean CSL'07] even state:
* Any CQ is decidable in linear time iff it is alphaacyclic. (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 betaacyclic 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 trianglefree in time O(nēlog n) where n is the number of vertices.)
* Any NCQ is decidable in quasilinear time iff it is betaacyclic.
(By quasilinear time, we mean a query on a structure S can be decided in time O(SlogS))
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 betaacyclic existential firstorder query is decidable in quasilinear time.
BibTeX  Entry
@InProceedings{braultbaron:LIPIcs:2012:3669,
author = {Johann BraultBaron},
title = {{A Negative Conjunctive Query is Easy if and only if it is BetaAcyclic}},
booktitle = {Computer Science Logic (CSL'12)  26th International Workshop/21st Annual Conference of the EACSL},
pages = {137151},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897422},
ISSN = {18688969},
year = {2012},
volume = {16},
editor = {Patrick C{\'e}gielski and Arnaud Durand},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3669},
URN = {urn:nbn:de:0030drops36697},
doi = {http://dx.doi.org/10.4230/LIPIcs.CSL.2012.137},
annote = {Keywords: conjunctive query, hypergraph, betaacyclicity, data complexity, DavisPutnam procedure}
}
Keywords: 

conjunctive query, hypergraph, betaacyclicity, data complexity, DavisPutnam procedure 
Seminar: 

Computer Science Logic (CSL'12)  26th International Workshop/21st Annual Conference of the EACSL

Issue date: 

2012 
Date of publication: 

27.08.2012 