The Intensional-Extensional Problem in Probabilistic Databases

on YouTube ↗38m

" summary

Asks whether every safe UCQ whose PTIME proof uses inclusion–exclusion admits a polynomial-size knowledge compilation into deterministic decomposable circuits and answers it positively for the H family of UCQs: provenance is compiled by mapping queries to the Boolean lattice of satisfying-subqueries, reducing to adjacent-pair OBDDs (via Fink–Olteanu), and composing circuits by iterative color/uncolor operations so that disjoint ORs are deterministic. Introduces a set-theoretic combinatorial conjecture called non-cancelling intersections that would generalize the method; work is partial but successful for the H class.

AI-written summary · about

" chapters (8)

1. 0:00Introduction
2. 3:55Probabilistic query evaluation
3. 9:03Deterministic decomposable circuits
4. 14:27Intensional-Extensional problem
5. 17:46Safe queries in class H
6. 25:58Conjecture on set families
7. 33:16Summary
8. 33:59Q&A

" related talks

• 43mA Dichotomy for Queries with Negation in Probabilistic DatabasesDan Olteanu · Uncertainty in Computation 2016
• 01h 05mAlgebraic Structures in Logic and Query Evaluation 2Val Tannen · Logic and Algorithms in Database Theory and AI Boot Camp
• 01h 01mBrief Tutorial on Probabilistic DatabasesDan Suciu · Uncertainty in Computation 2016
• 19mAccessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: IINofar Carmeli · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 21mGenerating Collection Transformations from ProofsMichael Benedikt, Pierre Pradic · POPL 2021
• 35mApproximating Certain and Possible Answers Beyond SetsBoris Glavic · Logic and Algebra for Query Evaluation 2023
• 29mUnderstanding Queries by Conditional InstancesSudeepa Roy · Logic and Algebra for Query Evaluation 2023
• 47mApproximate Lifted Inference with Probabilistic DatabasesWolfgang Gatterbauer · Uncertainty in Computation 2016