Structural tractability of counting of solutions to conjunctive queries

DOI10.1007/S00224-014-9543-YzbMATH Open1352.68080arXiv1303.2059OpenAlexW2088101961MaRDI QIDQ269342FDOQ269342

Authors: Arnaud Durand, Stefan Mengel 

Publication date: 18 April 2016

Published in: Theory of Computing Systems (Search for Journal in Brave)

Abstract: In this paper we explore the problem of counting solutions to conjunctive queries. We consider a parameter called the emph{quantified star size} of a formula $varphi$ which measures how the free variables are spread in $varphi$. We show that for conjunctive queries that admit nice decomposition properties (such as being of bounded treewidth or generalized hypertree width) bounded quantified star size exactly characterizes the classes of queries for which counting the number of solutions is tractable. This also allows us to fully characterize the conjunctive queries for which counting the solutions is tractable in the case of bounded arity. To illustrate the applicability of our results, we also show that computing the quantified star size of a formula is possible in time $n^{O(k)}$ for queries of generalized hypertree width $k$. Furthermore, quantified star size is even fixed parameter tractable parameterized by some other width measures, while it is $W1$-hard for generalized hypertree width and thus unlikely to be fixed parameter tractable. We finally show how to compute an approximation of quantified star size in polynomial time where the approximation ratio depends on the width of the input.

Full work available at URL: https://arxiv.org/abs/1303.2059

Recommendations

• Tractable counting of the answers to conjunctive queries
• A trichotomy in the complexity of counting answers to conjunctive queries
• The complexity of weighted counting for acyclic conjunctive queries
• Tractable hypergraph properties for constraint satisfaction and conjunctive queries
• When is the evaluation of conjunctive queries tractable?

zbMATH Keywords

conjunctive queriescounting complexityhypergraph decomposition techniques

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Database theory (68P15)

Cites Work

• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Title not available (Why is that?)
• A partial k-arboretum of graphs with bounded treewidth
• Parametrized complexity theory.
• Title not available (Why is that?)
• Elements of finite model theory.
• Decomposing constraint satisfaction problems using database techniques
• A comparison of structural CSP decomposition methods
• Conjunctive-query containment and constraint satisfaction
• Structural tractability of enumerating CSP solutions
• Hypertree width and related hypergraph invariants
• Approximating fractional hypertree width
• Decomposing Quantified Conjunctive (or Disjunctive) Formulas
• Generalized hypertree decompositions: NP-hardness and tractable variants
• Query evaluation via tree-decompositions
• Beyond Hypertree Width: Decomposition Methods Without Decompositions
• Constraint solving via fractional edge covers
• On Acyclic Conjunctive Queries and Constant Delay Enumeration
• Graph minors. II. Algorithmic aspects of tree-width
• Tractable counting of the answers to conjunctive queries
• The complexity of weighted counting for acyclic conjunctive queries
• Enumerating homomorphisms
• Title not available (Why is that?)
• Title not available (Why is that?)
• When is the evaluation of conjunctive queries tractable?
• A linear time algorithm for finding tree-decompositions of small treewidth
• Hypertree decompositions and tractable queries
• The complexity of counting homomorphisms seen from the other side
• A unified theory of structural tractability for constraint satisfaction problems

Cited In (19)

• Tractable counting of the answers to conjunctive queries
• The complexity of weighted counting for acyclic conjunctive queries
• Parameterised complexity of model checking and satisfiability in propositional dependence logic
• Counting Small Induced Subgraphs with Hereditary Properties
• Exploiting Database Management Systems and Treewidth for Counting
• Parameterised counting in logspace
• Counting Small Induced Subgraphs Satisfying Monotone Properties
• Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
• Characterizing tractability of simple well-designed pattern trees with projection
• Answer Counting under Guarded TGDs
• Tractable hypergraph properties for constraint satisfaction and conjunctive queries
• Size and treewidth bounds for conjunctive queries
• Title not available (Why is that?)
• Enumeration complexity of conjunctive queries with functional dependencies
• The complexity of pattern counting in directed graphs, parameterised by the outdegree
• Parameterized Counting and Cayley Graph Expanders
• Theory and Applications of Satisfiability Testing
• Counting Answers to Existential Questions
• Decomposing Quantified Conjunctive (or Disjunctive) Formulas

This page was built for publication: Structural tractability of counting of solutions to conjunctive queries

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