Sound and efficient language-integrated query: Maintaining the ORDER

Oleg Kiselyov, Tatsuya Katsushima

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

6 Citations (Scopus)


As SQL moved from the English-like language for ad hoc queries by business users to its present status as the universal relational database access, the lack of abstractions and compositionality in the original design is felt more and more acute. Recently added subqueries and common table expressions compensate, albeit generally inefficiently. The inadequacies of SQL motivated language-integrated query systems such as (T-)LINQ, which offer an applicative, programming-like query language compiled to efficient SQL. However, the seemingly straightforward ranking operations ORDER BY and LIMIT are not supported efficiently, consistently or at all in subqueries. The SQL standard defines their behavior only when applied to the whole query. Language-integrated query systems do not support them either: naively extending ranking to subexpressions breaks the distributivity laws of UNION ALL underlying optimizations and compilation. We present the first compositional semantics of ORDER BY and LIMIT, which reproduces in the limit the standard-prescribed SQL behavior but also applies to arbitrarily composed query expressions and preserves the distributivity laws. We introduce the relational calculus SQUR that includes ordering and subranging and whose normal forms correspond to efficient, portable, subquery-free SQL. Treating these operations as effects, we describe a type-and-effect system for SQUR and prove its soundness. Our denotational semantics leads to the provably correctness-preserving normalization-by-evaluation. An implementation of SQUR thus becomes a sound and efficient language-integrated query system maintaining the ORDER.

Original languageEnglish
Title of host publicationProgramming Languages and Systems - 15th Asian Symposium, APLAS 2017, Proceedings
EditorsBor-Yuh Evan Chang
PublisherSpringer Verlag
Number of pages20
ISBN (Print)9783319712369
Publication statusPublished - 2017
Event15th Asian Symposium on Programming Languages and Systems, APLAS 2017 - Suzhou, China
Duration: 2017 Nov 272017 Nov 29

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10695 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference15th Asian Symposium on Programming Languages and Systems, APLAS 2017


Dive into the research topics of 'Sound and efficient language-integrated query: Maintaining the ORDER'. Together they form a unique fingerprint.

Cite this