Torsten Grust
Jan Rittinger
Abstract
We report on a query compilation technique that enables the construction of alternative efficient query providers for Microsoft's Language Integrated Query (LINQ) framework. LINQ programs are mapped into an intermediate algebraic form, suitable for execution on any SQL:1999-capable relational database system.
This compilation technique leads to query providers that (1) faithfully preserve list order and nesting, both being core features of the LINQ data model, (2) support the complete family of LINQ's Standard Query Operators, (3) bring database support to LINQ to XML where the original provider performs in-memory query evaluation, and, most importantly, (4) emit SQL statement sequences whose size is only determined by the input query's result type (and thus independent of the database size).
A sample query scenario uses this LINQ provider to marry database-resident TPC-H and XMark data---resulting in a unique query experience that exhibits quite promising performance characteristics, especially for large data instances.
- A. Adya, J. Blakeley, S. Melnik, and S. Muralidhar. Anatomy of the ADO.NET Entity Framework. In Proc. SIGMOD, 2007. Google Scholar
Digital Library
- R. Agrawal, A. Ailamaki, P. Bernstein, E. Brewer, M. Carey, S. Chauduri, A. Doan, D. Florescu, M. Franklin, H. Garcia-Molina, J. Gehrke, L. Gruenwald, L. Haas, A. Halevy, and J. Hellerstein. The Claremont Report on Database Research. CACM, 52(6), 2009. Google ScholarDigital Library
- G. M. Bierman, E. Meijer, and M. Torgersen. Lost In Translation: Formalizing Proposed Extensions to C#. In Proc. OOPSLA, 2007. Google ScholarDigital Library
- M. Chakravarty, R. Leshchinskiy, S. Peyton-Jones, G. Keller, and S. Marlow. Data-Parallel Haskell: A Status Report. In Proc. DAMP, 2007. Google ScholarDigital Library
- E. Cooper, S. Lindley, P. Wadler, and J. Yallop. Links: Web Programming Without Tiers. In Proc. FMCO, 2006. Google ScholarDigital Library
- P. Fischer and S. Thomas. Operators for Non-First-Normal-Form Relations. In Proc. COMPSAC, 1983.Google Scholar
- T. Grust, M. Mayr, and J. Rittinger. Let SQL Drive the XQuery Workhorse. In Proc. EDBT, 2010. Google ScholarDigital Library
- T. Grust, M. Mayr, J. Rittinger, S. Sakr, and J. Teubner. A SQL:1999 Code Generator for the Pathfinder XQuery Compiler. In Proc. SIGMOD, 2007. Google ScholarDigital Library
- T. Grust, M. Mayr, J. Rittinger, and T. Schreiber. Ferry: Database-Supported Program Execution. In Proc. SIGMOD, 2009. Google ScholarDigital Library
- T. Grust, S. Sakr, and J. Teubner. XQuery on SQL Hosts. In Proc. VLDB, 2004. Google ScholarDigital Library
- S. P. Jones and P. Wadler. Comprehensive Comprehensions: Comprehensions with "Order by" and "Group by". In Proc. Haskell Workshop, 2007. Google ScholarDigital Library
- D. Lieuwen and D. DeWitt. A Transformation-based Approach to Optimizing Loops in Database Programming Languages. In Proc. SIGMOD, 1992. Google ScholarDigital Library
- E. Meijer. Confessions of a Used Programming Language Salesman: Getting the Masses Hooked on Haskell. ACM SIGPLAN Notices, 42(10), 2007. Google ScholarDigital Library
- E. Meijer, B. Beckman, and G. Bierman. LINQ: Reconciling Objects, Relations, and XML in the .NET Framework. In Proc. SIGMOD, 2006. Google ScholarDigital Library
- A. Ohori. Type-Directed Specialization of Polymorphism. Information and Computation, 155(1--2), 1999. Google ScholarDigital Library
- P. O'Neil, E. O'Neil, S. Pal, I. Cseri, G. Schaller, and N. Westbury. ORDPATHs: Insert-Friendly XML Node Labels. In Proc. SIGMOD, 2004. Google ScholarDigital Library
- J. Reynolds. Definitional Interpreters for Higher-Order Programming Languages. Higher-Order and Symbolic Computation, 11(4), 1998. Google ScholarDigital Library
- H. J. Schek and M. H. Scholl. The Relational Model with Relation-Valued Attributes. Information Systems, 11(2), 1986. Google ScholarDigital Library
- A. Schmidt, F. Waas, M. Kersten, M. J. Carey, I. Manolescu, and R. Busse. XMark: A Benchmark for XML Data Management. In Proc. VLDB, 2002. Google ScholarDigital Library
- T. Schreiber, S. Bonetti, T. Grust, M. Mayr, and J. Rittinger. Thirteen New Players in the Team: A Ferry-based LINQ to SQL Provider. In Proc. VLDB, 2010. Google ScholarDigital Library
- M. Stonebraker, J. Becla, D. Dewitt, K. Lim, D. Maier, O. Ratzesberger, and S. Zdonik. Requirements for Science Data Bases and SciDB. In Proc. CIDR, 2009.Google Scholar
- J. F. Terwilliger, P. A. Bernstein, and S. Melnik. Full-Fidelity Flexible Object-Oriented XML Access. In Proc. VLDB, 2009. Google ScholarDigital Library
- TPC Benchmark H. TP Council. http://www.tpc.org/tpch/.Google Scholar
- J. van den Bussche. Simulation of the Nested Relational Algebra by the Flat Relational Algebra, with an Application to the Complexity of Evaluating Powerset Algebra Expressions. Theoretical Computer Science, 254(1--2), 2001. Google ScholarDigital Library
- P. Wadler. Comprehending Monads. In Proc. LFP, 1990. Google ScholarDigital Library
Index Terms
- Avalanche-safe LINQ compilation
Comments