Approximating Certain and Possible Answers Beyond Sets

on YouTube ↗35m

" summary

Generalizes certain and possible answers from set semantics to semiring-annotated relations, proving that lattice-ordered semirings let query evaluation produce PTIME under-approximations of certain answers and over-approximations of possible answers; extends the model with attribute-level intervals into UA-DBs that remain closed under full relational algebra including aggregation and sort-based ops; provides two implementations (including GProM) and demonstrates feasible execution on TPCH 1GB with measurable but reducible overhead.

AI-written summary · about

" chapters (22)

1. 0:00Introduction
2. 1:11Incomplete databases
3. 2:35Desired properties
4. 4:01Semirings for databases
5. 6:33K-relations semantics
6. 7:15Defining certain and possible annotations
7. 8:59Certain vs possible answers
8. 12:10Mapping uncertainty models
9. 12:52UA-DBs overview
10. 15:00Bound-preserving semantics
11. 17:07Handling difference operator
12. 18:10Datalog for UA-DBs
13. 19:14Existing works trade-offs
14. 20:22Aggregations challenges
15. 22:30Interval domains
16. 25:01Attribute uncertainty bounds
17. 26:06Semiring relations algebra
18. 27:31Aggregations with intervals
19. 28:59Group by sorting uncertain
20. 29:42Conclusion future work
21. 31:06Practical demo
22. 32:11Q&A

" related talks

• 01h 06mAlgebraic Structures in Logic and Query Evaluation 1Val Tannen · Logic and Algorithms in Database Theory and AI Boot Camp
• 01h 05mAlgebraic Structures in Logic and Query Evaluation 2Val Tannen · Logic and Algorithms in Database Theory and AI Boot Camp
• 01h 02mAlgebraic Structures in Logic and Query Evaluation 3Dan Suciu · Logic and Algorithms in Database Theory and AI Boot Camp
• 01h 08mAlgebraic Structures in Logic and Query Evaluation 4Dan Suciu · Logic and Algorithms in Database Theory and AI Boot Camp
• 43mA Dichotomy for Queries with Negation in Probabilistic DatabasesDan Olteanu · Uncertainty in Computation 2016
• 01h 01mBrief Tutorial on Probabilistic DatabasesDan Suciu · Uncertainty in Computation 2016
• 01h 09mAccessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: INofar Carmeli · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 38mThe Intensional-Extensional Problem in Probabilistic DatabasesMikael Monet · Probabilistic Circuits and Logic 2023