The Intensional-Extensional Problem in Probabilistic Databases

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.