Query shredding: Efficient relational evaluation of queries over nested multisets

James Cheney, Sam Lindley, Philip Wadler

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Citations (Scopus)

Abstract

Nested relational query languages have been explored extensively, and underlie industrial language-integrated query systems such as Microsoft's LINQ. However, relational databases do not natively support nested collections in query results. This can lead to major performance problems: if programmers write queries that yield nested results, then such systems typically either fail or generate a large number of queries. We present a new approach to query shredding, which converts a query returning nested data to a fixed number of SQL queries. Our approach, in contrast to prior work, handles multiset semantics, and generates an idiomatic SQL:1999 query directly from a normal form for nested queries. We provide a detailed description of our translation and present experiments showing that it offers comparable or better performance than a recent alternative approach on a range of examples.

Original languageEnglish
Title of host publicationSIGMOD '14: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data
PublisherAssociation for Computing Machinery
Pages1027-1038
Number of pages12
ISBN (Print)9781450323765
DOIs
Publication statusPublished - Jun 2014
Event2014 ACM SIGMOD International Conference on Management of Data - Snowbird, United States
Duration: 22 Jun 201427 Jun 2014

Conference

Conference2014 ACM SIGMOD International Conference on Management of Data
Abbreviated titleSIGMOD 2014
CountryUnited States
CitySnowbird
Period22/06/1427/06/14

Keywords

  • Language-integrated query
  • Querying nested collections

ASJC Scopus subject areas

  • Software
  • Information Systems

Fingerprint Dive into the research topics of 'Query shredding: Efficient relational evaluation of queries over nested multisets'. Together they form a unique fingerprint.

  • Profiles

    Cite this

    Cheney, J., Lindley, S., & Wadler, P. (2014). Query shredding: Efficient relational evaluation of queries over nested multisets. In SIGMOD '14: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data (pp. 1027-1038). Association for Computing Machinery. https://doi.org/10.1145/2588555.2612186