Exploiting Database Management Systems and Treewidth for Counting

DOI10.1017/S147106842100003XMaRDI QIDQ6063876zbMATH OpenFDO

Authors Johannes K. Fichte, Markus Hecher, Patrick Thier, Stefan Woltran

Publication date 12 December 2023

Published in Theory and Practice of Logic Programming (Search for Journal in Brave)

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

zbMATH Keywords

bounded treewidthcountingdatabase systemsdynamic programmingparameterized algorithmicsrelational algebraSQL

Mathematics Subject Classification ID

Database theory (68P15) Combinatorics in computer science (68R05)

Abstract: Bounded treewidth is one of the most cited combinatorial invariants, which was applied in the literature for solving several counting problems efficiently. A canonical counting problem is #SAT, which asks to count the satisfying assignments of a Boolean formula. Recent work shows that benchmarking instances for #SAT often have reasonably small treewidth. This paper deals with counting problems for instances of small treewidth. We introduce a general framework to solve counting questions based on state-of-the-art database management systems (DBMS). Our framework takes explicitly advantage of small treewidth by solving instances using dynamic programming (DP) on tree decompositions (TD). Therefore, we implement the concept of DP into a DBMS (PostgreSQL), since DP algorithms are already often given in terms of table manipulations in theory. This allows for elegant specifications of DP algorithms and the use of SQL to manipulate records and tables, which gives us a natural approach to bring DP algorithms into practice. To the best of our knowledge, we present the first approach to employ a DBMS for algorithms on TDs. A key advantage of our approach is that DBMS naturally allow to deal with huge tables with a limited amount of main memory (RAM), parallelization, as well as suspending computation.

Recommendations

• Fast Counting with Bounded Treewidth
• Counting and Enumeration Problems with Bounded Treewidth
• When is approximate counting for conjunctive queries tractable?
• An Experimental Study of the Treewidth of Real-World Graph Data
• Solving #SAT and MAXSAT by Dynamic Programming

Cites work

• A relational model of data for large shared data banks
• Algorithms for propositional model counting
• Answer set programming modulo acyclicity
• Bounded treewidth as a key to tractability of knowledge representation and reasoning
• Bucket elimination: A unifying framework for reasoning
• Combining restarts, nogoods and decompositions for solving CSPs
• D-FLAT^2: subset minimization in dynamic programming on tree decompositions made easy
• Default logic and bounded treewidth
• Evaluation of an MSO-Solver
• Expansion-based QBF solving on tree decompositions
• Exploiting treewidth for projected model counting and its limits
• Graph theory
• scientific article; zbMATH DE number 4060712 (Why is no real title available?)
• scientific article; zbMATH DE number 1470716 (Why is no real title available?)
• scientific article; zbMATH DE number 194561 (Why is no real title available?)
• scientific article; zbMATH DE number 7286685 (Why is no real title available?)
• scientific article; zbMATH DE number 3420754 (Why is no real title available?)
• Implementing efficient All solutions SAT solvers
• Laissez-faire caching for parallel \#SAT solving
• Lower Bounds for QBFs of Bounded Treewidth
• On the hardness of approximate reasoning
• Parameterized algorithms
• PP is as Hard as the Polynomial-Time Hierarchy
• Practical access to dynamic programming on tree decompositions
• Probabilistic planning via heuristic forward search and weighted model counting
• Some (in)translatability results for normal logic programs and propositional theories
• Structural tractability of counting of solutions to conjunctive queries
• Taming high treewidth with abstraction, nested dynamic programming, and database technology
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The PACE 2017 parameterized algorithms and computational experiments challenge: the second iteration
• The PACE 2019 Parameterized Algorithms and Computational Experiments Challenge: The Fourth Iteration (Invited Paper)
• Treewidth. Computations and approximations
• Weighted model counting on the GPU by exploiting small treewidth

Cited in

(5)

• scientific article; zbMATH DE number 6820309 (Why is no real title available?)
• An Experimental Study of the Treewidth of Real-World Graph Data
• Fast Counting with Bounded Treewidth
• Reasoning in assumption-based argumentation using tree-decompositions
• IASCAR: incremental answer set counting by anytime refinement

This page was built for publication: Exploiting Database Management Systems and Treewidth for Counting

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