Knowledge compilation meets database theory: compiling queries to decision diagrams

DOI10.1007/s00224-012-9392-5zbMath1270.68297OpenAlexW2023076960MaRDI QIDQ359877

Dan Suciu, Abhay Jha

Publication date: 23 August 2013

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-012-9392-5

zbMATH Keywords

binary decision diagramsknowledge compilationOBDDd-DNNFFBDDprobabilistic databases

Mathematics Subject Classification ID

Database theory (68P15) Knowledge representation (68T30) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (7)

Causes for query answers from databases: datalog abduction, view-updates, and integrity constraints ⋮ On the Complexity of Probabilistic Abstract Argumentation Frameworks ⋮ Open-world probabilistic databases: semantics, algorithms, complexity ⋮ An Experimental Study of the Treewidth of Real-World Graph Data ⋮ On limitations of structured (deterministic) DNNFs ⋮ Connecting knowledge compilation classes and width parameters ⋮ Compiling CP subproblems to MDDs and d-DNNFs

Cites Work

• Unnamed Item
• Unnamed Item
• A simple function that requires exponential size read-once branching programs
• Graph driven BDDs -- a new data structure for Boolean functions
• Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams
• BDDs -- design, analysis, complexity, and applications.
• Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees
• A very simple function that requires exponential size read-once branching programs.
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
• Graph-Based Algorithms for Boolean Function Manipulation
• Equivalences Among Relational Expressions with the Union and Difference Operators
• Efficient Boolean manipulation with OBDD's can be extended to FBDD's
• On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision
• Branching Programs and Binary Decision Diagrams

This page was built for publication: Knowledge compilation meets database theory: compiling queries to decision diagrams