Connecting width and structure in knowledge compilation
From MaRDI portal
Abstract: Several query evaluation tasks can be done via knowledge compilation: the query result is compiled as a lineage circuit from which the answer can be determined. For such tasks, it is important to leverage some width parameters of the circuit, such as bounded treewidth or pathwidth, to convert the circuit to structured classes, e.g., deterministic structured NNFs (d-SDNNFs) or OBDDs. In this work, we show how to connect the width of circuits to the size of their structured representation, through upper and lower bounds. For the upper bound, we show how bounded-treewidth circuits can be converted to a d-SDNNF, in time linear in the circuit size. Our bound, unlike existing results, is constructive and only singly exponential in the treewidth. We show a related lower bound on monotone DNF or CNF formulas, assuming a constant bound on the arity (size of clauses) and degree (number of occurrences of each variable). Specifically, any d-SDNNF (resp., SDNNF) for such a DNF (resp., CNF) must be of exponential size in its treewidth; and the same holds for pathwidth when compiling to OBDDs. Our lower bounds, in contrast with most previous work, apply to any formula of this class, not just a well-chosen family. Hence, for our language of DNF and CNF, pathwidth and treewidth respectively characterize the efficiency of compiling to OBDDs and (d-)SDNNFs, that is, compilation is singly exponential in the width parameter. We conclude by applying our lower bound results to the task of query evaluation.
Recommendations
Cites work
- scientific article; zbMATH DE number 4121482 (Why is no real title available?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A differential approach to inference in Bayesian networks
- Graph minors. X: Obstructions to tree-decomposition
- Inference and learning in probabilistic logic programs using weighted Boolean formulas
- On compiling structured CNFs to OBDDs
- On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision
- On tree width, bramble size, and expansion
- Probabilistic databases
- Query evaluation via tree-decompositions
Cited in
(7)- Parameterized compilation lower bounds for restricted CNF-formulas
- Top-down algorithms for constructing structured DNNF: theoretical and practical implications
- An Experimental Study of the Treewidth of Real-World Graph Data
- Connecting knowledge compilation classes and width parameters
- Functional Treewidth: Bounding Complexity in the Presence of Functional Dependencies
- Knowledge compilation meets database theory: compiling queries to decision diagrams
- Cliquewidth and knowledge compilation
This page was built for publication: Connecting width and structure in knowledge compilation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3305349)
