The fine classification of conjunctive queries and parameterized logarithmic space

DOI10.1145/2751316MaRDI QIDQ2828230zbMATH OpenOpenAlexFDO

Authors Hubie Chen, Moritz Müller

Publication date 24 October 2016

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.5424, https://eprints.bbk.ac.uk/id/eprint/21943/1/1306.5424.pdf

zbMATH Keywords

conjunctive queriesgraph decompositionshomomorphism problemsparameterized logarithmic space

Mathematics Subject Classification ID

Database theory (68P15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

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.

Recommendations

• When is the evaluation of conjunctive queries tractable?
• One hierarchy spawns another, graph deconstructions and the complexity classification of conjunctive queries
• scientific article; zbMATH DE number 1222098
• Combined tractability of query evaluation via tree automata and cycluits
• The complexity of acyclic conjunctive queries

Cited in

(11)

• An O(n n)-space decision procedure for the relevance logic B^+
• The parameterized space complexity of embedding along a path
• One hierarchy spawns another, graph deconstructions and the complexity classification of conjunctive queries
• One hierarchy spawns another: graph deconstructions and the complexity classification of conjunctive queries
• The parameterized space complexity of model-checking bounded variable first-order logic
• On the descriptive complexity of color coding
• scientific article; zbMATH DE number 7297821 (Why is no real title available?)
• Decomposing Quantified Conjunctive (or Disjunctive) Formulas
• Parameterised complexity of model checking and satisfiability in propositional dependence logic
• Parameterised counting in logspace
• Parameterised counting in logspace

This page was built for publication: The fine classification of conjunctive queries and parameterized logarithmic space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2828230)