Structural tractability of counting of solutions to conjunctive queries

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

Authors Arnaud Durand, Stefan Mengel

Publication date 18 April 2016

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

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

zbMATH Keywords

conjunctive queriescounting complexityhypergraph decomposition techniques

Mathematics Subject Classification ID

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

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.

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?

Cites work

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

Cited in

(21)

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

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)