A Dichotomy for Queries with Negation in Probabilistic Databases
summary
Proves a dichotomy for nonrepeating relational-algebra queries with set difference over tuple‑independent probabilistic databases: either evaluation is polynomial-time or it is #P‑hard. Tractable cases are exactly those satisfying the hierarchical property and admit efficient OBDD compilation of the grounding (polynomial in data, exponential in query due to quantifier interleaving); hardness comes from reductions from model counting for positive bipartite 2‑DNF, even for some queries with only one probabilistic relation — so some simple-looking queries are provably intractable.
AI-written summary · about
chapters (14)
- 0:00Intro
- 1:21Tuple-Independent Probabilistic Databases
- 3:29Relational Algebra
- 6:46The Query Evaluation Problem
- 13:17Examples
- 17:18Hardness Proof Idea
- 18:56A Simple Case
- 21:44A Surprising Case
- 24:58A More Involved Case
- 29:07Non-hierarchical Queries Match Minimal Hard Patterns
- 29:53Evaluation of Hierarchical IRA Queries
- 32:22The Inner Workings
- 34:37Query Evaluation Example (2/3)
- 36:26Dichotomies Beyond 1RA
related talks
38mThe Intensional-Extensional Problem in Probabilistic Databases
53mDirect Access for Conjunctive Queries with Negation
35mApproximating Certain and Possible Answers Beyond Sets
28mA Dichotomy Structure Theorem for the Resilience Problem
33mCombined Approximations for Probabilistic Query Evaluation: An Intensional Approach
01h 08mAlgebraic Structures in Logic and Query Evaluation 4
28mA Unified Approach for Reverse Data Management Problems
49mCompiling FO Sentences to Circuits: Upper Bounds and Lower Bounds on the Size of the Circuit