Exploiting Database Management Systems and Treewidth for Counting

• URL: http://arxiv.org/abs/2001.04191v2
• Date: Wed, 3 Feb 2021 16:54:41 GMT
• Title: Exploiting Database Management Systems and Treewidth for Counting
• Authors: Johannes K. Fichte, Markus Hecher, Patrick Thier, Stefan Woltran
• Abstract summary: A canonical counting problem is #SAT, which asks to count the assignments of a Boolean formula. Recent work shows that benchmarking instances for #SAT often have reasonably small treewidth. We introduce a general framework to solve counting questions based on state-of-the-art database management systems.
• Score: 22.315022989618594
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• ST-Raptor: LLM-Powered Semi-Structured Table Question Answering [17.807768747239205]
  Semi-structured tables, widely used in real-world applications, often involve flexible and complex layouts.<n>These tables rely on human analysts to interpret table layouts and answer relevant natural language questions.<n>We propose ST-Raptor, a tree-based framework for semi-structured table question answering using large language models.
  arXiv  Detail & Related papers  (2025-08-25T16:48:51Z)
• Agentic-R1: Distilled Dual-Strategy Reasoning [58.73951532294446]
  Current long chain-of-thought (long-CoT) models excel at mathematical reasoning but rely on slow and error-prone natural language traces.<n>We introduce a fine-tuning framework, DualDistill, that distills complementary reasoning strategies from multiple teachers into a unified student model.<n>Our method improves accuracy across a range of tasks, including both computation-intensive and standard benchmarks.
  arXiv  Detail & Related papers  (2025-07-08T06:35:16Z)
• SchemaGraphSQL: Efficient Schema Linking with Pathfinding Graph Algorithms for Text-to-SQL on Large-Scale Databases [1.6544167074080365]
  We present a zero-shot, training-free schema linking approach that first constructs a schema graph based on foreign key relations.<n>We apply classical path-finding algorithms and post-processing to identify the optimal sequence of tables and columns that should be joined.<n>Our method achieves state-of-the-art results on the BIRD benchmark, outperforming previous specialized, fine-tuned, and complex multi-step LLM-based approaches.
  arXiv  Detail & Related papers  (2025-05-23T20:42:36Z)
• PICASO: Permutation-Invariant Context Composition with State Space Models [98.91198288025117]
  State Space Models (SSMs) offer a promising solution by allowing a database of contexts to be mapped onto fixed-dimensional states. We propose a simple mathematical relation derived from SSM dynamics to compose multiple states into one that efficiently approximates the effect of concatenating raw context tokens. We evaluate our resulting method on WikiText and MSMARCO in both zero-shot and fine-tuned settings, and show that we can match the strongest performing baseline while enjoying on average 5.4x speedup.
  arXiv  Detail & Related papers  (2025-02-24T19:48:00Z)
• FastGAS: Fast Graph-based Annotation Selection for In-Context Learning [53.17606395275021]
  In-context learning (ICL) empowers large language models (LLMs) to tackle new tasks by using a series of training instances as prompts. Existing methods have proposed to select a subset of unlabeled examples for annotation. We propose a graph-based selection method, FastGAS, designed to efficiently identify high-quality instances.
  arXiv  Detail & Related papers  (2024-06-06T04:05:54Z)
• Hierarchical Context Merging: Better Long Context Understanding for Pre-trained LLMs [61.40047491337793]
  We present Hierarchical cOntext MERging (HOMER), a new training-free scheme designed to overcome the limitations of large language models. HomeR uses a divide-and-conquer algorithm, dividing long inputs into manageable chunks. A token reduction technique precedes each merging, ensuring memory usage efficiency.
  arXiv  Detail & Related papers  (2024-04-16T06:34:08Z)
• Maximum Independent Set: Self-Training through Dynamic Programming [56.670639478539485]
  This work presents a graph neural network (GNN) framework for solving the maximum independent set (MIS) problem, inspired by dynamic programming (DP) We propose a DP-like recursive algorithm based on GNNs that firstly constructs two smaller sub-graphs, predicts the one with the larger MIS, and then uses it in the next recursion call. Annotating comparisons of different graphs concerning their MIS size leads to a self-training process that results in more accurate self-annotation of the comparisons and vice versa.
  arXiv  Detail & Related papers  (2023-10-28T10:58:25Z)
• DP-starJ: A Differential Private Scheme towards Analytical Star-Join Queries [10.022473569166532]
  Star-join query is the fundamental task in data warehouse and has wide applications in On-line Analytical Processing (OLAP) scenarios. We propose DP-starJ, a novel Differentially Private framework for star-Join queries.
  arXiv  Detail & Related papers  (2023-10-07T07:05:52Z)
• Solving Projected Model Counting by Utilizing Treewidth and its Limits [23.81311815698799]
  We introduce a novel algorithm to solve projected model counting (PMC) Inspired by the observation that the so-called "treewidth" is one of the most prominent structural parameters, our algorithm utilizes small treewidth of the primal graph of the input instance.
  arXiv  Detail & Related papers  (2023-05-30T17:02:07Z)
• Uni-Parser: Unified Semantic Parser for Question Answering on Knowledge Base and Database [86.03294330305097]
  We propose a unified semantic element for question answering (QA) on both knowledge bases (KB) and databases (DB) We introduce the primitive (relation and entity in KB, table name, column name and cell value in DB) as an essential element in our framework. We leverage the generator to predict final logical forms by altering and composing topranked primitives with different operations.
  arXiv  Detail & Related papers  (2022-11-09T19:33:27Z)
• Advanced Tools and Methods for Treewidth-Based Problem Solving -- Extended Abstract [9.480212602202517]
  This work focuses on logic-based problems and treewidth-based methods and tools for solving them. We present a new type of problem reduction, which is referred to by decomposition-guided (DG) We implement an algorithm for solving extensions of Sat efficiently, by directly using treewidth.
  arXiv  Detail & Related papers  (2022-08-24T07:43:58Z)
• Knowledge Base Question Answering by Case-based Reasoning over Subgraphs [81.22050011503933]
  We show that our model answers queries requiring complex reasoning patterns more effectively than existing KG completion algorithms. The proposed model outperforms or performs competitively with state-of-the-art models on several KBQA benchmarks.
  arXiv  Detail & Related papers  (2022-02-22T01:34:35Z)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  We improve the scalability of Branch and Bound (BaB) algorithms for formally proving input-output properties of neural networks. We present a novel activation-based branching strategy and a BaB framework, named Branch and Dual Network Bound (BaDNB) BaDNB outperforms previous complete verification systems by a large margin, cutting average verification times by factors up to 50 on adversarial properties.
  arXiv  Detail & Related papers  (2021-04-14T09:22:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.