Knowledge compilation meets database theory: compiling queries to decision diagrams

DOI10.1007/S00224-012-9392-5MaRDI QIDQ359877zbMATHOpenAlexFDO

Authors Abhay Jha, Dan Suciu

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

knowledge compilationbinary decision diagramsOBDDd-DNNFFBDDprobabilistic databases

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1946853
• Automated Reasoning with Analytic Tableaux and Related Methods
• Connecting width and structure in knowledge compilation
• The dichotomy of probabilistic inference for unions of conjunctive queries
• Exact model counting of query expressions. Limitations of propositional methods

Cites work

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

Cited in

(12)

• Open-world probabilistic databases: semantics, algorithms, complexity
• Connecting knowledge compilation classes and width parameters
• On limitations of structured (deterministic) DNNFs
• A framework for method-specific knowledge compilation from databases
• On the complexity of probabilistic abstract argumentation frameworks
• Compiling CP subproblems to MDDs and d-DNNFs
• An Experimental Study of the Treewidth of Real-World Graph Data
• Automated Reasoning with Analytic Tableaux and Related Methods
• Causes for query answers from databases: datalog abduction, view-updates, and integrity constraints
• Knowledge compilation. Preface.
• Exact model counting of query expressions. Limitations of propositional methods
• A new synthetical knowledge representation model and its application in data flow diagram

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

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