Brief Tutorial on Probabilistic Databases

on YouTube ↗01h 01m

" summary

Defines a tuple-independent model where each tuple is a random event and query probability equals the probability of the lineage (grounded FO sentence) and reduces evaluation to propositional model counting. Gives a concrete dichotomy: for non-repeating conjunctive queries hierarchical = PTIME and otherwise #P-hard, and extends to unate universal/existential fragments where syntactic rules (independent projection, inclusion–exclusion) are complete. Shows DPLL-style solvers map to decision DNNF and can be provably exponential even when the rules yield polynomial-time evaluation.

AI-written summary · about

" chapters (26)

1. 0:00Intro
2. 0:26About This Talk
3. 1:50Background: Relational databases
4. 5:20Probabilistic Database
5. 8:32Outline
6. 9:45Probability of a Formula
7. 11:06Algorithms for Model Counting (Gomes, Sabharwal, Selman'2009) Based on full search DPLL
8. 13:40Relational Representation (1/2)
9. 16:17Weighted FO Model Counting
10. 19:27Discussion: Correlations
11. 22:33Background: Query Plans
12. 23:55An Example
13. 26:15Extensional Plans
14. 29:50Unsafe Queries
15. 33:24Hierarchical Queries
16. 34:41The Small Dichotomy Theorem
17. 39:14FOun = Unate FO
18. 44:27Example: Liftable Query
19. 48:42Unliftable Queries (HK)
20. 50:04Summary so Far
21. 51:01Lifted vs. Grounded Inference
22. 52:09Decision-DNNE
23. 53:43Notations
24. 54:41Easy/Hard Queries
25. 55:36Cancellations
26. 57:47Möbius Über Alles

" related talks

• 38mThe Intensional-Extensional Problem in Probabilistic DatabasesMikael Monet · Probabilistic Circuits and Logic 2023
• 01h 03mAn Overview of Probabilistic ProgrammingVikash K. Mansinghka · Strange Loop 2015
• 33mCombined Approximations for Probabilistic Query Evaluation: An Intensional ApproachTimothy Van Bremen · Probabilistic Circuits and Logic 2023
• 35mApproximating Certain and Possible Answers Beyond SetsBoris Glavic · Logic and Algebra for Query Evaluation 2023
• 24mHigher order programming with probabilistic effects: A model of stochastic memo...Younesse Kaddar, Sam Staton · HOPE 2022
• 01h 00mLogic and Probabilistic Circuits 3YooJung Choi · Logic and Algorithms in Database Theory and AI Boot Camp
• 01h 05mLogic and Probabilistic Circuits 1Guy Van den Broeck · Logic and Algorithms in Database Theory and AI Boot Camp
• 15mScaling Exact Inference for Discrete Probabilistic ProgramsTodd Millstein, Guy Van den Broeck, Steven Holtzen · OOPSLA 2020