Functional Treewidth: Bounding Complexity in the Presence of Functional Dependencies

DOI10.1007/11814948_14MaRDI QIDQ5756566zbMATH OpenOpenAlexFDO

Authors Yuliya Zabiyaka, Adnan Darwiche

Publication date 4 September 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11814948_14

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Parameterized compilation lower bounds for restricted CNF-formulas
• Weak functional dependencies: full propositional expressiveness for the database practitioner
• Size and treewidth bounds for conjunctive queries
• CV-width: a new complexity parameter for CNFs
• Connecting width and structure in knowledge compilation

Cited in

(4)

• On the complexity of inferring functional dependencies
• Visualizing SAT instances and runs of the DPLL algorithm
• On the Complexity of Insertion Propagation with Functional Dependency Constraints
• scientific article; zbMATH DE number 5200724 (Why is no real title available?)

This page was built for publication: Functional Treewidth: Bounding Complexity in the Presence of Functional Dependencies

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