Titre :  The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity

Exposant : Hubie Chen, Universidad del País Vasco and IKERBASQUE, Basque Foundation for Science

Résumé :  
Conjunctive queries are the most basic and heavily studied database
queries. The complexity of evaluating a conjunctive query on a
relational database has been, since the landmark work of Chandra and
Merlin (1977), a research subject of persistent and enduring interest.
This evaluation problem is equivalent to a number of well-known
problems, including conjunctive query containment, the homomorphism
problem on relational structures, and the constraint satisfaction
problem. Correspondingly, studies of this problem have come from a wide
variety of perspectives and motivations.


In this work, we perform a fundamental investigation of the complexity
of conjunctive query evaluation from the perspective of parameterized
complexity.  We classify sets of conjunctive queries according to the
complexity of this problem.  Previous work showed that a set of
conjunctive queries is fixed-parameter tractable precisely when the set
is equivalent to a set of queries having bounded treewidth. We present a
fine classification of query sets up to parameterized logarithmic space
reduction.  We show that, in the bounded treewidth regime, there are
three complexity degrees and that the properties that determine the
degree of a query set are bounded pathwidth and bounded tree depth.


After presenting this classification theorem, we engage in a study of
the two higher degrees via logarithmic space machine characterizations
and complete problems.  Our work yields a significantly richer
perspective on the complexity of conjunctive queries and, at the same
time, suggests new avenues of research in parameterized complexity.


We will end by discussing recent work that obtains a broad, unifying
perspective on and generalization of the discussed classifications. This
work makes use of a novel variant of the well-known notion of tree
decomposition which we call graph deconstruction.  Interestingly, while
the notion of tree decomposition is typically useful for giving positive algorithmic
results, here we use the notion of graph deconstruction, in a crucial way, to obtain complexity hardness results.



This talk is based on PODS '13 and LICS '14 articles which are joint with Moritz Müller.