Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space

The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space We perform a fundamental investigation of the complexity of conjunctive query evaluation from the perspective of parameterized complexity. We classify sets of Boolean 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. We also 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. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space

Download PDF
27 pages

Loading next page...
 
/lp/association-for-computing-machinery/the-fine-classification-of-conjunctive-queries-and-parameterized-CW0saFmOK1
Publisher
Association for Computing Machinery
Copyright
Copyright © 2015 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/2751316
Publisher site
See Article on Publisher Site

Abstract

We perform a fundamental investigation of the complexity of conjunctive query evaluation from the perspective of parameterized complexity. We classify sets of Boolean 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. We also 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.

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: May 11, 2015

Keywords: Conjunctive queries

References

  • Foundations of Databases
    Abiteboul, S.; Hull, R.; Vianu, V.
  • On the monadic second-order transduction hierarchy
    Blumensath, A.; Courcelle, B.
  • A partial k-arboretum of graphs with bounded treewidth
    Bodlaender, H.
  • Optimal implementation of conjunctive queries in relational data bases
    Chandra, Ashok K.; Merlin, Philip M.
  • Constraint satisfaction with succinctly specified relations
    Chen, Hubie; Grohe, Martin
  • Bounded nondeterminism and alternation in parameterized complexity theory
    Chen, Y.; Flum, J.; Grohe, M.
  • Bounded variable logic, parameterized logarithmic space and Savitch’s theorem
    Chen, Y.; Müller, M.
  • Division in logspace-uniform NC1
    Chiu, A.; Davida, G.; Litow, B.
  • Complexity Classification of Boolean Constraint Satisfaction Problems
    Creignou, N.; Khanna, S.; Sudan, M.
  • Complexity of Constraints - An Overview of Current Research Themes
    Creignou, Nadia; Kolaitis, Phokion G.; (Eds, Heribert Vollmer
  • The complexity of counting homomorphisms seen from the other side
    Dalmau, V.; Jonsson, P.
  • Parameterized Complexity
    Downey, R. G.; Fellows, M. R.
  • On the space complexity of parameterized problems
    Elberfeld, M.; Stockhusen, C.; Tantau, T.
  • The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory
    Feder, T.; Vardi, M. Y.
  • Query evaluation via tree-decompositions
    Flum, J.; Frick, M.; Grohe, M.
  • Describing parameterized complexity classes
    Flum, J.; Grohe, M.
  • The parameterized complexity of counting problems
    Flum, J.; Grohe, M.
  • Parameterized Complexity Theory
    Flum, J.; Grohe, M.
  • The complexity of acyclic conjunctive queries
    Gottlob, Georg; Leone, Nicola; Scarcello, Francesco
  • Hypertree decompositions and tractable queries
    Gottlob, Georg; Leone, Nicola; Scarcello, Francesco
  • The complexity of homomorphism and constraint satisfaction problems seen from the other side
    Grohe, Martin
  • When is the evaluation of conjunctive queries tractable? In STOC 2001
    Grohe, Martin; Schwentick, Thomas; Segoufin, Luc
  • Conjunctive-query containment and constraint satisfaction
    Kolaitis, P.; Vardi, M. Y.
  • Relativization of questions about log space computability
    Ladner, R. E.; Lynch, N. A.
  • Can you beat treewidth? Theory of Computing 6, 1 (2010), 85--112
    Marx, Dániel
  • Tractable hypergraph properties for constraint satisfaction and conjunctive queries
    Marx, Dániel
  • Tree depth, subgraph coloring, and homomorphism bounds
    Nešetřil, J.; de Mendez, P. O.
  • On the complexity of database queries
    Papadimitriou, C.; Yannakakis, M.
  • Database theory: Query languages
    Schweikardt, Nicole; Schwentick, Thomas; Segoufin, Luc