Logical Interfaces to Data, Beyond Views

on YouTube ↗35m

" summary

Proposes replacing exported views with two interface specs: a set of utility queries users must be able to answer and an equivalence on instances that users cannot distinguish. Uses Segoufin–Vianu determinacy, CQs, relational algebra, nested relational calculus and first‑order/infinitary logic to prove that minimally informative distributed views exist for arbitrary utility queries, that some CQ utilities yield relational‑algebra realizations while others provably are not CQs, and that simple indistinguishability relations (and replication) can achieve privacy‑utility tradeoffs views cannot.

AI-written summary · about

" chapters (7)

1. 0:00Introduction to data interfaces
2. 1:57Defining data interfaces
3. 6:50Minimally informative views
4. 13:56Privacy and utility trade-offs
5. 20:15Indistinguishability relations
6. 27:38Concluding thoughts
7. 29:36Q&A session

" related talks

• 20mVeriEQL: Bounded Equivalence Verification for Complex SQL Queries with Integrity(…)Xinyu Wang, Yang He, Pinhan Zhao, Yuepeng Wang · OOPSLA 2024
• 35mComprehending queries over finite mapsWilmer Ricciotti · PPDP 2023
• 01h 05mAlgebraic Structures in Logic and Query Evaluation 2Val Tannen · Logic and Algorithms in Database Theory and AI Boot Camp
• 01h 05mIncremental View Maintenance 2Dan Olteanu · Logic and Algorithms in Database Theory and AI Boot Camp
• 38mThe Intensional-Extensional Problem in Probabilistic DatabasesMikael Monet · Probabilistic Circuits and Logic 2023
• 48mCompositional, Expressive, Performant Database Queries: Choose 3Dave Nicponski · LambdaConf 2019
• 01h 05mHomomorphism Counts: Expressive Power and Query AlgorithmsPhokion Kolaitis · Satisfiability: Theory, Practice, and Beyond 2023
• 18mTranslating canonical SQL to imperative code in CoqLouis Mandel, Chantal Keller, Jerome Simeon, Véronique Benzaken, Évelyne Contejean, Houssem Hachmaoui, Avraham Shinnar · OOPSLA 2023