James Cheney
Philip Wadler
ABSTRACT
Language-integrated query is receiving renewed attention, in part because of its support through Microsoft's LINQ framework. We present a practical theory of language-integrated query based on quotation and normalisation of quoted terms. Our technique supports join queries, abstraction over values and predicates, composition of queries, dynamic generation of queries, and queries with nested intermediate data. Higher-order features prove useful even for constructing first-order queries. We prove a theorem characterising when a host query is guaranteed to generate a single SQL query. We present experimental results confirming our technique works, even in situations where Microsoft's LINQ framework either fails to produce an SQL query or, in one case, produces an avalanche of SQL queries.
Supplemental Material
Available for Download
zip
icfp033.zip (42.3 KB)
This is the code supplement to the ICFP 2013 paper: A practical theory of language-integrated query James Cheney, Sam Lindley and Philip Wadler ICFP 2013 For further information, please see the README file in the associated ZIP file.
- M. P. Atkinson and O. P. Buneman. Types and persistence in database programming languages. ACM Comput. Surv., 19 (2): 105--170, 1987. Google Scholar
Digital Library
- E. Axelsson and J. Svenningsson. Combining deep and shallow embedding for EDSL. In TFP, 2012.Google Scholar
- E. Axelsson, K. Claessen, M. Sheeran, J. Svenningsson, D. Engdal, and A. Persson. The design and implementation of Feldspar--an embedded language for digital signal processing. In J. Hage and M. T. Morazán, editors, IFL, volume 6647 of LNCS, pages 121--136. Springer, 2010. Google ScholarDigital Library
- B. Beckman. Why LINQ matters: cloud composability guaranteed. Commun. ACM, 55 (4): 38--44, Apr. 2012. Google ScholarDigital Library
- G. M. Bierman, E. Meijer, and M. Torgersen. Lost in translation: formalizing proposed extensions to C\#. In OOPSLA, pages 479--498. ACM, 2007. Google ScholarDigital Library
- M. Budiu, J. Galenson, and G. D. Plotkin. The compiler forest. In ESOP, number 7792 in LNCS, pages 21--40. Springer-Verlag, 2013. Google ScholarDigital Library
- P. Buneman, L. Libkin, D. Suciu, V. Tannen, and L. Wong. Comprehension syntax. SIGMOD Record, 23: 87--96, 1994. Google ScholarDigital Library
- J. Cheney and R. Hinze. First-class phantom types. Computer and Information Science Technical Report TR2003--1901, Cornell University, 2003.Google Scholar
- J. Cheney, S. Lindley, and P. Wadler. A practical theory of language-integrated query (code supplement), 2012. http://homepages.inf.ed.ac.uk/jcheney/linq. Google ScholarDigital Library
- A. J. Chlipala. Ur: statically-typed metaprogramming with type-level record computation. In PLDI, pages 122--133. ACM, 2010. Google ScholarDigital Library
- W. Choi, B. Aktemur, K. Yi, and M. Tatsuta. Static analysis of multi-staged programs via unstaging translation. In POPL, pages 81--92. ACM, 2011. Google ScholarDigital Library
- E. Cooper. The script-writer's dream: How to write great SQL in your own language, and be sure it will succeed. In DBPL, number 5708 in LNCS, pages 36--51. Springer-Verlag, 2009. Google ScholarDigital Library
- E. Cooper, S. Lindley, P. Wadler, and J. Yallop. Links: web programming without tiers. In FMCO, volume 4709 of LNCS, pages 266--296, 2007. Google ScholarDigital Library
- G. Copeland and D. Maier. Making Smalltalk a database system. SIGMOD Rec., 14 (2): 316--325, 1984. Google ScholarDigital Library
- R. Davies and F. Pfenning. A modal analysis of staged computation. J. ACM, 48 (3): 555--604, 2001. Google ScholarDigital Library
- O. Eini. The pain of implementing LINQ providers. Commun. ACM, 54 (8): 55--61, 2011. Google ScholarDigital Library
- G. Giorgidze, T. Grust, T. Schreiber, and J. Weijers. Haskell boards the Ferry - database-supported program execution for Haskell. In IFL, number 6647 in LNCS, pages 1--18. Springer-Verlag, 2010. Google ScholarDigital Library
- T. Goldschmidt, R. Reussner, and J. Winzen. A case study evaluation of maintainability and performance of persistency techniques. In ICSE, pages 401--410. ACM, 2008. Google ScholarDigital Library
- T. Grust, M. van Keulen, and J. Teubner. Accelerating XPath evaluation in any RDBMS. ACM Trans. Database Syst., 29: 91--131, 2004. Google ScholarDigital Library
- T. Grust, M. Mayr, J. Rittinger, and T. Schreiber. Ferry: Database-supported program execution. In SIGMOD, pages 1063--1066. ACM, 2009. Google ScholarDigital Library
- T. Grust, J. Rittinger, and T. Schreiber. Avalanche-safe LINQ compilation. PVLDB, 3 (1): 162--172, 2010. Google ScholarDigital Library
- F. Henglein and K. F. Larsen. Generic multiset programming with discrimination-based joins and symbolic cartesian products. Higher-Order and Symbolic Computation, 23 (3): 337--370, 2010. Google ScholarDigital Library
- S. Lindley and J. Cheney. Row-based effect types for database integration. In TLDI, pages 91--102. ACM, 2012. Google ScholarDigital Library
- G. Mainland. Explicitly heterogeneous metaprogramming with MetaHaskell. In P. Thiemann and R. B. Findler, editors, ICFP, pages 311--322. ACM, 2012. ISBN 978-1-4503-1054-3. Google ScholarDigital Library
- G. Mainland and G. Morrisett. Nikola: embedding compiled GPU functions in haskell. In J. Gibbons, editor, Haskell Symposium, pages 67--78. ACM, 2010. ISBN 978-1-4503-0252-4. Google ScholarDigital Library
- E. Meijer. The world according to LINQ. Commun. ACM, 54 (10): 45--51, Oct. 2011. Google ScholarDigital Library
- E. Meijer, B. Beckman, and G. M. Bierman. LINQ: reconciling object, relations and XML in the .NET framework. In SIGMOD, page 706. ACM, 2006. Google ScholarDigital Library
- Microsoft. Query expressions (F\# 3.0 documentation), 2013. http://msdn.microsoft.com/en-us/library/vstudio/hh225374.aspx, accessed March 18, 2013.Google Scholar
- A. Ohori and K. Ueno. Making Standard ML a practical database programming language. In ICFP, pages 307--319. ACM, 2011. Google ScholarDigital Library
- }petricek-dynamic-flinqT. Petricek. Building LINQ queries at runtime in (F\#), 2007. http://tomasp.net/blog/dynamic-flinq.aspx.Google Scholar
- }petricek-dynamic-linqT. Petricek. Building LINQ queries at runtime in (C\#), 2007. http://tomasp.net/blog/dynamic-linq-queries.aspx.Google Scholar
- T. Petricek and D. Syme. Syntax Matters: Writing abstract computations in F\#. Pre-proceedings of TFP, 2012. http://www.cl.cam.ac.uk/asciitildetp322/drafts/notations.pdf.Google Scholar
- D. Prawitz. Natural Deduction: A Proof-Theoretical Study. Almqvist and Wiksell, Stockholm, 1965.Google Scholar
- M. Rhiger. Staged computation with staged lexical scope. In ESOP, number 7211 in LNCS, pages 559--578. Springer-Verlag, 2012. Google ScholarDigital Library
- T. Rompf and M. Odersky. Lightweight modular staging: a pragmatic approach to runtime code generation and compiled dsls. Commun. ACM, 55 (6): 121--130, 2012. Google ScholarDigital Library
- D. Syme. Leveraging .NET meta-programming components from F\#: integrated queries and interoperable heterogeneous execution. In ML Workshop, pages 43--54. ACM, 2006. Google ScholarDigital Library
- D. Syme, A. Granicz, and A. Cisternino. Expert F\# 3.0. Apress, 2012. ISBN 978-1-4302-4650-3. Google ScholarDigital Library
- W. Taha and T. Sheard. MetaML and multi-stage programming with explicit annotations. Theor. Comput. Sci., 248 (1-2): 211--242, 2000. Google ScholarDigital Library
- P. Trinder. Comprehensions, a query notation for DBPLs. In Proceedings of 3rd International Workshop on Database Programming Languages, pages 49--62. Morgan Kaufmann, 1991. Google ScholarDigital Library
- P. Trinder and P. Wadler. Improving list comprehension database queries. In TENCON '89., 1989.Google ScholarCross Ref
- A. Ulrich. A Ferry-based query backend for the Links programming language. Master's thesis, University of Tübingen, 2011.Google Scholar
- J. Van den Bussche, S. Vansummeren, and G. Vossen. Towards practical meta-querying. Inf. Syst., 30 (4): 317--332, 2005. Google ScholarDigital Library
- L. Wong. Normal forms and conservative extension properties for query languages over collection types. J. Comput. Syst. Sci., 52 (3): 495--505, 1996. Google ScholarDigital Library
Index Terms
- A practical theory of language-integrated query
Recommendations
A practical theory of language-integrated query
ICFP '13Language-integrated query is receiving renewed attention, in part because of its support through Microsoft's LINQ framework. We present a practical theory of language-integrated query based on quotation and normalisation of quoted terms. Our technique ...
Finally, safely-extensible and efficient language-integrated query
PEPM '16: Proceedings of the 2016 ACM SIGPLAN Workshop on Partial Evaluation and Program ManipulationLanguage-integrated query is an embedding of database queries into a host language to code queries at a higher level than the all-to-common concatenation of strings of SQL fragments. The eventually produced SQL is ensured to be well-formed and well-...
Language-integrated query with ordering, grouping and outer joins (poster paper)
PEPM 2017: Proceedings of the 2017 ACM SIGPLAN Workshop on Partial Evaluation and Program ManipulationLanguage-integrated query systems like T-LINQ or QUEΛ make relational operations on (generally external) data feel like the ordinary iteration over native arrays. As ordinary programs, queries are type-checked, can be abstracted over and composed. To ...
Comments