The Intensional-Extensional Problem in Probabilistic Databases
Offered By: Simons Institute via YouTube
Course Description
Overview
Explore the intricacies of probabilistic query evaluation in databases through this 38-minute lecture by Mikael Monet from INRIA. Delve into the dichotomy theorem established by Dalvi and Suciu, which classifies union of conjunctive queries (UCQs) as either solvable in polynomial time or #P-hard. Examine the three fundamental rules used in safe query algorithms: independence, negation, and inclusion-exclusion. Compare this approach with knowledge compilation methods, which utilize similar rules but with a focus on disjoint union instead of inclusion-exclusion. Investigate the ongoing challenge of the intensional-extensional problem, which seeks to determine if knowledge compilation can capture the tractability of safe UCQs. Learn about recent progress in handling specific classes of UCQs and discover the intriguing "non-cancelling intersections" conjecture. Gain insights into the intersection of database theory, probability, and computational complexity in this advanced exploration of probabilistic databases.
Syllabus
The Intensional-Extensional Problem in Probabilistic Databases
Taught by
Simons Institute
Related Courses
Algebra & AlgorithmsMoscow Institute of Physics and Technology via Coursera Lower Bounds in Complexity Theory, Communication Complexity, and Sunflowers - Toniann Pitassi
Institute for Advanced Study via YouTube Proof and Circuit Complexity - Robert Robere
Institute for Advanced Study via YouTube Undergrad Complexity at CMU - SAT
Ryan O'Donnell via YouTube Improved Non-Interactive Zero Knowledge with Applications to Post-Quantum Signatures
Association for Computing Machinery (ACM) via YouTube