Accessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: I

on YouTube ↗01h 09m

" summary

Defines when answer enumeration achieves linear preprocessing and constant delay for conjunctive queries: acyclic, no-self-join queries admit a two-pass semi‑join algorithm and are tractable, while cyclic queries are hard under triangle / hyperclique hardness assumptions. Shows self‑joins break the dichotomy with concrete patterns that become easier or harder (examples, reductions, and a gadget tagging construction), gives RAM‑model and memory assumptions, and highlights small, explicit open patterns where complexity remains unresolved.

AI-written summary · about

" chapters (13)

1. 0:00Introduction
2. 3:10Workshop Overview
3. 11:23Welcome
4. 12:49Outline
5. 13:15Join Queries
6. 15:33Filter Queries
7. 18:17Data Complexity
8. 19:12Optimal Algorithms
9. 22:19Cyclicity
10. 28:20Generalization
11. 32:50Raw Model
12. 38:53Selfjoin
13. 55:00Unary Atom

" related talks

• 29mDirect Access for Conjunctive Queries with AggregationNofar Carmeli · Logic and Algebra for Query Evaluation 2023
• 21mRecent Advances in Incremental View MaintenanceHaozhe Zhang · Sparse 2024
• 53mDirect Access for Conjunctive Queries with NegationFlorent Capelli, Oliver Irwin · Probabilistic Circuits and Logic 2023
• 01h 05mIncremental View Maintenance 2Dan Olteanu · Logic and Algorithms in Database Theory and AI Boot Camp
• 35mApproximating Certain and Possible Answers Beyond SetsBoris Glavic · Logic and Algebra for Query Evaluation 2023
• 01h 05mQuery Optimization and Evaluation 2: Worst-Case Optimal Join AlgorithmsHung Ngo · Logic and Algorithms in Database Theory and AI Boot Camp
• 28mA Dichotomy Structure Theorem for the Resilience ProblemCibele Freire · Symmetry, Logic, Computation 2016
• 01h 06mSampling in Query Evaluation 2Marcelo Arenas · Logic and Algorithms in Database Theory and AI Boot Camp