nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Sound and Efficient Language-Integrated Query

Maintaining the ORDER

verfasst von : Oleg Kiselyov, Tatsuya Katsushima

Erschienen in: Programming Languages and Systems

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Implementing Algebraic Effects in C

Nächstes Kapitel A Computational Interpretation of Context-Free Expressions

To obtain an informative report one may, in principle, run QE first and for each resulting record, query department for the descriptive department name. Such ‘composition’ essentially executes as many department queries as there are well-paid employees and leads to the ‘query avalanche’ well explained in [4]. In this paper we consider only those compositions that result in a single query.

Such subqueries in the FROM SQL clause are sometimes called ‘derived tables’ or ‘inlined views’.

For example, MySQL 5.7 never re-writes and hence optimizes subqueries in the FROM clause: http://dev.mysql.com/doc/refman/5.7/en/subquery-restrictions.html.

https://docs.oracle.com/cd/B28359_01/server.111/b28286/statements_10002.htm#sthref6708.

https://msdn.microsoft.com/en-us/library/ms188385.aspx.

https://mariadb.com/kb/en/mariadb/why-is-order-by-in-a-from-subquery-ignored/.

http://dba.stackexchange.com/questions/82930/database-implementations-of-order -by-in-a-subquery.

http://stackoverflow.com/questions/18031421/the-order-by-clause-is-invalid-in- views-inline-functions-derived-tables-subqu, https://www.sqlservercentral.com/ Forums/Topic1079476-391-1.aspx.

The name, just like Que \(\varLambda \) of [13], is a pun for old-timers.

A simpler example of embedding a bare, first-order calculus into a rich, functional (meta)language is described in http://okmij.org/ftp/tagless-final/nondet-effect.html.

Atkinson, M.P., Buneman, O.P.: Types and persistence in database programming languages. ACM Comput. Surv. 19(2), 105–170 (1987)CrossRef

Buneman, P., Naqvi, S., Tannen, V., Wong, L.: Principles of programming with complex objects and collection types. Theor. Comput. Sci. 149(1), 3–48 (1995)MathSciNetCrossRefMATH

Buneman, P., Ohori, A.: Polymorphism and type inference in database programming. ACM Trans. Database Syst. 21(1), 30–76 (1996)CrossRef

Cheney, J., Lindley, S., Wadler, P.: A practical theory of language-integrated query. In: ICFP 2013, pp. 403–416. ACM, New York (2013)

Chu, S., Weitz, K., Cheung, A., Suciu, D.: HoTTSQL: proving query rewrites with univalent SQL semantics. CoRR abs/1607.04822 (2016). http://arxiv.org/abs/1607.04822

Cooper, E.: The script-writer’s dream: how to write great SQL in your own language, and be sure it will succeed. In: Gardner, P., Geerts, F. (eds.) DBPL 2009. LNCS, vol. 5708, pp. 36–51. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03793-1_3 CrossRef

Dybjer, P., Filinski, A.: Normalization and partial evaluation. In: Barthe, G., Dybjer, P., Pinto, L., Saraiva, J. (eds.) Applied Semantics. LNCS, vol. 2395, pp. 137–192. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45699-6_4 CrossRef

Ellis, T.: Opaleye. https://github.com/tomjaguarpaw/haskell-opaleye. Accessed Dec 2014

Hibino, K., Murayama, S., Yasutake, S., Kuroda, S., Yamamoto, K.: Haskell relational record. http://khibino.github.io/haskell-relational-record/. Accessed May 2017

10.

Libkin, L., Wong, L.: Conservativity of nested relational calculi with internal generic functions. Inf. Process. Lett. 49(6), 273–280 (1994)MathSciNetCrossRefMATH

11.

Najd, S., Lindley, S., Svenningsson, J., Wadler, P.: Everything old is new again: quoted domain-specific languages. In: PEPM, pp. 25–36. ACM (2016)

12.

Ohori, A., Ueno, K.: Making Standard ML a practical database programming language. In: ICFP 2011, pp. 307–319. ACM, New York (2011)

13.

Suzuki, K., Kiselyov, O., Kameyama, Y.: Finally, safely-extensible and efficient language-integrated query. In: Proceedings of the PEPM, pp. 37–48. ACM (2016)

14.

Breazu-Tannen, V., Buneman, P., Wong, L.: Naturally embedded query languages. In: Biskup, J., Hull, R. (eds.) ICDT 1992. LNCS, vol. 646, pp. 140–154. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-56039-4_38

Titel: Sound and Efficient Language-Integrated Query
verfasst von: Oleg Kiselyov
Tatsuya Katsushima
Verlag: Springer International Publishing
Buch: Programming Languages and Systems
Print ISBN: 978-3-319-71236-9

Electronic ISBN: 978-3-319-71237-6

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-71237-6_18

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner