Sampling in Query Evaluation 1
summary
Shows that counting join answers is #P-complete and uniform random generation in general collapses complexity (polynomial-time uniform generation implies NP = RP), so focus shifts to acyclic queries where exact counting and join tree / Yannakakis counting give O(input)-time counts and provably uniform sampling. Adding projection ruins tractability (reduction from counting perfect matchings). Practical methods use local statistics and rejection sampling using MB(S) or AGM-style upper bounds W(t) that satisfy three monotonicity properties; experiments report low rejection in practice.
AI-written summary · about
chapters (6)
- 0:00Sampling in query evaluation
- 1:54Motivation for database sampling
- 6:49Counting and uniform generation
- 23:49Projection challenges in acyclic queries
- 33:19Uniform generation with joins
- 58:52Q&A
related talks
33mLinear and sublinear algorithms for graphlet sampling
44mIntermediate Relational Algorithm Design
01h 02mCounting Subgraphs in Sublinear Time
01h 09mAccessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: I
47mMassively Parallel Evaluation of Relational Queries I
33mCombined Approximations for Probabilistic Query Evaluation: An Intensional Approach
35mApproximating Certain and Possible Answers Beyond Sets
19mAccessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: II