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

on YouTube ↗19m

" summary

Acyclic conjunctive queries that are free-connex admit linear preprocessing and constant-delay enumeration, while acyclic but not free-connex queries are hard under Boolean matrix multiplication reductions because projections force duplicate-elimination across many explanations. Unions can flip hardness: a body-homomorphism from one CQ to another lets one CQ precompute the hard join, Cheater’s Lemma bounds tolerated duplicate output, and classifying unions of two CQs requires reductions to vertex-unbalanced triangle detection; beyond two queries remains open.

AI-written summary · about

" chapters (10)

1. 0:00Introduction
2. 1:07Conjunctive queries with existential vars
3. 3:33Free-connex acyclic queries
4. 4:40Hardness of acyclic non-free-connex
5. 6:54Unions of conjunctive queries
6. 7:59Complexity of mixed-easy unions
7. 9:02Hard queries and matrix multiplication
8. 12:40Unions of hard queries becoming easy
9. 15:31Open problems
10. 17:15Conclusion

" related talks

• 29mDirect Access for Conjunctive Queries with AggregationNofar Carmeli · Logic and Algebra for Query Evaluation 2023
• 53mDirect Access for Conjunctive Queries with NegationFlorent Capelli, Oliver Irwin · Probabilistic Circuits and Logic 2023
• 38mThe Intensional-Extensional Problem in Probabilistic DatabasesMikael Monet · Probabilistic Circuits and Logic 2023
• 01h 05mIncremental View Maintenance 2Dan Olteanu · Logic and Algorithms in Database Theory and AI Boot Camp
• 21mRecent Advances in Incremental View MaintenanceHaozhe Zhang · Sparse 2024
• 28mA Dichotomy Structure Theorem for the Resilience ProblemCibele Freire · Symmetry, Logic, Computation 2016
• 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