The complexity of weighted counting for acyclic conjunctive queries

DOI10.1016/j.jcss.2013.08.001zbMath1311.68052arXiv1110.4201OpenAlexW2036350338MaRDI QIDQ395018

Stefan Mengel, Arnaud Durand

Publication date: 28 January 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

conjunctive queriescounting complexity

Mathematics Subject Classification ID

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

Related Items (4)

Structural tractability of counting of solutions to conjunctive queries ⋮ The arithmetic complexity of tensor contraction ⋮ Answer Counting under Guarded TGDs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Tractable counting of the answers to conjunctive queries
• The complexity of weighted and unweighted \(\#\)CSP
• On the expressive power of CNF formulas of bounded tree- and clique-width
• Arithmetization: A new method in structural complexity theory
• Hypertree decompositions and tractable queries
• Elements of finite model theory.
• The complexity of counting homomorphisms seen from the other side
• Exact algorithms and applications for tree-like Weighted Set Cover
• A unified theory of structural tractability for constraint satisfaction problems
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Characterizing Valiant's algebraic complexity classes
• Parametrized complexity theory.
• Subtractive reductions and complete problems for counting complexity classes
• On the complexity of #CSP
• Tractable hypergraph properties for constraint satisfaction and conjunctive queries
• Decomposing Quantified Conjunctive (or Disjunctive) Formulas
• Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
• Degrees of acyclicity for hypergraphs and relational database schemes
• The complexity of acyclic conjunctive queries
• Query evaluation via tree-decompositions
• The Complexity of the Counting Constraint Satisfaction Problem
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• On Acyclic Conjunctive Queries and Constant Delay Enumeration
• The Complexity of Weighted Boolean #CSP
• Universality considerations in VLSI circuits
• The Parameterized Complexity of Counting Problems
• When is the evaluation of conjunctive queries tractable?
• Complexity of counting CSP with complex weights
• Theory and Applications of Satisfiability Testing

This page was built for publication: The complexity of weighted counting for acyclic conjunctive queries