A Dichotomy Structure Theorem for the Resilience Problem

on YouTube ↗28m

" summary

Classifies resilience for self‑join‑free conjunctive queries: if the hypergraph of the closed query Q contains a triad then computing the minimum contingency set is NP‑hard (reductions from 3‑set, triangle→tripod families); if no triad exists the problem is polynomial by reducing to network‑flow on a linear form. Handles functional dependencies by computing Q via induced rewrites and proves closure preserves complexity. Constructions and reductions are explicit and effective.

AI-written summary · about

" chapters (8)

1. 0:00Start
2. 1:21Resilience problem
3. 4:07Dual hypergraph
4. 14:25Triads hardness
5. 15:00Linear queries
6. 16:29Domination
7. 17:52Adding functional dependencies
8. 22:33Future Directions

" related talks

• 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
• 01h 09mAccessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: INofar Carmeli · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 29mDirect Access for Conjunctive Queries with AggregationNofar Carmeli · Logic and Algebra for Query Evaluation 2023
• 28mA Unified Approach for Reverse Data Management ProblemsNeha Makhija · Logic and Algebra for Query Evaluation 2023
• 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
• 01h 05mIncremental View Maintenance 2Dan Olteanu · Logic and Algorithms in Database Theory and AI Boot Camp