Direct Access for Conjunctive Queries with Aggregation
summary
Characterizes when a lexicographically sorted answer array for conjunctive queries with grouping meets quasi-linear preprocessing and logarithmic access: common aggregates (sum, count, min, max) map to commutative semirings so the known acyclic free‑connex/no‑disruptive‑trail dichotomy still decides tractability when the aggregate is not part of the order. Shows count‑distinct infeasible under standard hardness assumptions (3SUM style), proves tractability for idempotent semirings when annotations are local to one relation, and lists open cases (aggregates affecting order, self‑joins, approximations).
AI-written summary · about
chapters (13)
- 0:00Direct access with aggregation
- 1:49Motivating query computation
- 3:41Join complexity motivation
- 5:11Ranked direct access benefits
- 7:23Query complexity goals
- 8:06Conjunctive queries
- 11:21Aggregation with semirings
- 13:31Aggregation without order impact
- 16:19Count distinct hardness
- 17:49Aggregation and lexicographic order
- 21:27Functional dependencies in tractability
- 23:39Results and future work
- 26:12Q&A
related talks
01h 09mAccessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: I
53mDirect Access for Conjunctive Queries with Negation
19mAccessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: II
44mIntermediate Relational Algorithm Design
01h 05mIncremental View Maintenance 2
28mA Dichotomy Structure Theorem for the Resilience Problem
39mUsing Monoids for Large Scale Business Stats
38mAdd ALL the things: abstract algebra meets analytics