Understanding Queries by Conditional Instances

on YouTube ↗29m

" summary

Defines conditional instances—small representative instances with global conditions—that capture distinct ways a domain-relational-calculus query can be satisfied; proves existence is undecidable in general and NP-hard subproblems are handled with a chase-inspired heuristic plus SMT solvers and Boolean how‑provenance for minimization. Produces a web UI and test-suite tooling used by 1,600 students over five years; a pilot user study finds concrete ground examples are easier to read but sets of conditional instances reveal multiple errors. Aggregates/HAVING remain unsupported.

AI-written summary · about

" chapters (18)

1. 0:00Database education tools
2. 1:03Database course demand
3. 2:10Debugging student SQL
4. 3:21Autograder limitations
5. 4:26Boolean how-provenance
6. 6:38Motivation for conditional instances
7. 8:31Conditional instances defined
8. 10:01Query tree analysis Q2-Q1
9. 11:05Requirements for solutions
10. 12:35Enumerating homomorphisms
11. 13:43Problem undecidability
12. 14:45Chase procedure
13. 16:30Drinker query example
14. 19:07Handling quantifiers and disjunctions
15. 21:13Query debugging user study
16. 23:00Summary of contributions
17. 24:26Open challenges
18. 25:29Q&A on aggregates and LLMs

" related talks

• 01h 10mQuery Optimization and Evaluation 4: Instance OptimalityMahmoud Abo Khamis · Logic and Algorithms in Database Theory and AI Boot Camp
• 38mThe Intensional-Extensional Problem in Probabilistic DatabasesMikael Monet · Probabilistic Circuits and Logic 2023
• 53mDirect Access for Conjunctive Queries with NegationFlorent Capelli, Oliver Irwin · Probabilistic Circuits and Logic 2023
• 43mA Dichotomy for Queries with Negation in Probabilistic DatabasesDan Olteanu · Uncertainty in Computation 2016
• 19mAccessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: IINofar Carmeli · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 33mCombined Approximations for Probabilistic Query Evaluation: An Intensional ApproachTimothy Van Bremen · Probabilistic Circuits and Logic 2023
• 01h 09mAccessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: INofar Carmeli · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 01h 01mBrief Tutorial on Probabilistic DatabasesDan Suciu · Uncertainty in Computation 2016