Query Optimization and Evaluation 1: Output Size Bounds and Information Theory
summary
Covers how to turn degree statistics into provable output-size upper bounds using information theory and linear programming, then links those bounds to practical join runtimes. Shows the entropic bound → relax to the polymatroid bound (a linear program) → further to a modular/fractional edge‑cover form, recovers concrete cases like triangles ≤ N^{1.5} and key‑constraint drops to N. Flags open issues: computability of the entropic region, whether polymatroid LP is PTIME for general constraints, and extensions beyond simple degree summaries.
AI-written summary · about
chapters (18)
- 0:00Graph query complexity
- 2:13Shortest path queries
- 4:08Query optimization techniques
- 5:59Database evaluation problem
- 7:57Query types and profiles
- 11:22Meta-algorithms overview
- 12:20Cardinality bounds
- 14:47Worst-case optimality
- 17:27Conjunctive query models
- 20:09Degree constraints
- 26:08Hierarchy of set functions
- 29:15Triangle query example
- 33:37Entropic bounds
- 37:16Polymatroid bounds
- 40:23Modular bounds and duals
- 45:43General degree constraints
- 48:46Tightness of bounds
- 52:23Open research questions
related talks
01h 02mCounting Subgraphs in Sublinear Time
44mIntermediate Relational Algorithm Design
43mResizable Sketches
26mIncremental View Maintenance: Beyond Worst-Case Analysis II
41mOptimizing Relational Programs I
01h 09mAccessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: I
18mMaximum Consensus Floating Point Solutions for Infeasible Low-Dimensional Linear(…)
41mIntroduction to Constraint Programming