Tight Bounds of Circuits for Sum-Product Queries
Open Access
- 10 May 2024
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (2) , 1-20
Abstract
In this paper, we ask the following question: given a Boolean Conjunctive Query (CQ), what is the smallest circuit that computes the provenance polynomial of the query over a given semiring? We answer this question by giving upper and lower bounds. Notably, it is shown that any circuit F that computes a CQ over the tropical semiring must have size log |F| ≥ (1-ε) · da-entw for any ε >0, where da-entw is the degree-aware entropic width of the query. We show a circuit construction that matches this bound when the semiring is idempotent. The techniques we use combine several central notions in database theory: provenance polynomials, tree decompositions, and disjunctive Datalog programs. We extend our results to lower and upper bounds for formulas (i.e., circuits where each gate has outdegree one), and to bounds for non-Boolean CQs.Keywords
This publication has 23 references indexed in Scilit:
- FAQ2016
- Size Bounds for Factorised Representations of Query ResultsACM Transactions on Database Systems, 2015
- Lower Bounds for Tropical Circuits and Dynamic ProgramsTheory of Computing Systems, 2014
- Using OBDDs for Efficient Query Evaluation on Probabilistic Databases2008
- Provenance semirings2007
- On a relation between information inequalities and group theoryIEEE Transactions on Information Theory, 2002
- A framework for comparing models of computationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1998
- Graph minors. III. Planar tree-widthJournal of Combinatorial Theory, Series B, 1984
- The complexity of partial derivativesTheoretical Computer Science, 1983
- A lower bound on the number of additions in monotone computationsTheoretical Computer Science, 1976