Comprehending queries over finite maps

on YouTube ↗35m

" summary

Extends the nested relational calculus with first-class finite maps, grouping, lookups and group-wise aggregation and proves strong normalization, producing normal forms that translate directly to SQL (group by + select) rather than inefficient correlated key-value queries. Shows the extended calculus composes with shredding to SQL so nested-typed queries can be executed by a DBMS, supports mixing sets and bags, and documents a Links implementation on GitHub; shredding is proved but not yet shipped, and the approach yields noticeably better SQL performance.

AI-written summary · about

" chapters (8)

1. 0:00Language-integrated SQL queries
2. 6:16Language-integrated query matters
3. 8:23Nested relational calculus
4. 12:05Calculus with grouping and aggregation
5. 21:07Normal forms and SQL translation
6. 26:55Advantages over prior approaches
7. 28:43Implementation and future work
8. 29:26Q&A

" related talks

• 48mCompositional, Expressive, Performant Database Queries: Choose 3Dave Nicponski · LambdaConf 2019
• 50mModern SQL: Evolution of a dinosaurMarkus Winand · Riga Dev Days 2019
• 47mModern SQL: Evolution of a DinosaurMarkus Winand · International PHP Conference Spring 2019
• 45mMore Than a Query Language: SQL in the 21st CenturyMarkus Winand · Dutch PHP Conference 2019
• 58mThe Mother of All Query Languages: SQL in the 21st CenturyMarkus Winand · Dev Day Dresden 2019
• 01h 00mModern SQL: Evolution of a DinosaurMarkus Winand · JAX 2019
• 18mTranslating canonical SQL to imperative code in CoqLouis Mandel, Chantal Keller, Jerome Simeon, Véronique Benzaken, Évelyne Contejean, Houssem Hachmaoui, Avraham Shinnar · OOPSLA 2023
• 27mFunctional Programming on Top of SQL EnginesTobias Burghardt, Denis Hirn, Torsten Grust · PADL 2022