BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IC Colloquium : Sound and Efficient Language-Integrated Query: Mai
 ntaining the ORDER
DTSTART:20170911T161500
DTEND:20170911T173000
DTSTAMP:20260407T051123Z
UID:7af9b1e435d4cb7e3e85ecbec90b9c50db91be008619bc06d3df6074
CATEGORIES:Conferences - Seminars
DESCRIPTION:By : Oleg Kiselyov - Tohoku University\nVideo of his talk\n\nA
 bstract :\nAs SQL moved from the English-like language for ad hoc queries 
 by business users to its present status as the universal relational databa
 se access\, the lack of abstractions and compositionality in the original 
 design is felt more and more acute. Recently added subqueries and common t
 able expressions compensate\, albeit generally inefficiently. The inadequa
 cies of SQL motivated language-integrated query systems such as (T-)LINQ\,
  which offer an applicative\, programming-like query language compiled to 
 efficient SQL.\n\nHowever\, the seemingly straightforward ranking operatio
 ns ORDER BY and LIMIT are not supported efficiently\, consistently or at a
 ll in SQL subqueries. The SQL standard defines their behavior only when ap
 plied to the whole query. Language-integrated query systems do not support
  them either: naively extending ranking to subexpressions breaks the distr
 ibutivity laws of UNION ALL that underlie optimizations and compilation.\n
 \nWe present the first compositional semantics of ORDER BY and LIMIT\, whi
 ch reproduces in the limit the standard-prescribed SQL behavior but also a
 pplies to arbitrary composed query expressions and preserves the distribut
 ivity laws. We introduce the relational calculus SQUR that includes orderi
 ng and subranging and whose normal forms correspond to efficient\, subquer
 y-free SQL.  Treating these operations as effects\, we describe a type-an
 d-effect system for SQUR and prove its soundness. Our denotational semanti
 cs leads to the provably correctness-preserving normalization-by-evaluatio
 n. An implementation\nof SQUR thus becomes a sound and efficient language-
 integrated query system maintaining the ORDER.\n\nBio :\nOleg Kiselyov is 
 an Assistant Professor in Tohoku University\, Japan.  He is interested in
  semantics of programming and natural languages.  He worked on continuati
 ons\, extensible-effects\, staging\, HList\, lightweight dependent types\,
  tagless-final DSL embeddings\, macros\, non-determinism and logic program
 ming\, and probabilistic programming. He is the developer of BER MetaOCaml
 .\n\nMore information\n 
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR