Query lifting. Language-integrated query for heterogeneous nested collections

DOI10.1007/978-3-030-72019-3_21MaRDI QIDQ2233480zbMATH OpenOpenAlexFDO

Authors Wilmer Ricciotti, James Cheney

Publication date 18 October 2021

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2101.04102

zbMATH Keywords

multisetsnested relationslanguage-integrated query

Mathematics Subject Classification ID

Theory of programming languages (68N15) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Database theory (68P15)

Abstract: Language-integrated query based on comprehension syntax is a powerful technique for safe database programming, and provides a basis for advanced techniques such as query shredding or query flattening that allow efficient programming with complex nested collections. However, the foundations of these techniques are lacking: although SQL, the most widely-used database query language, supports heterogeneous queries that mix set and multiset semantics, these important capabilities are not supported by known correctness results or implementations that assume homogeneous collections. In this paper we study language-integrated query for a heterogeneous query language $NR{C}_{l}ambda(Set,Bag)$ that combines set and multiset constructs. We show how to normalize and translate queries to SQL, and develop a novel approach to querying heterogeneous nested collections, based on the insight that ``local query subexpressions that calculate nested subcollections can be ``lifted to the top level analogously to lambda-lifting for local function definitions.

Recommendations

• A practical theory of language-integrated query
• scientific article; zbMATH DE number 1086723
• Normal forms and conservative extension properties for query languages over collection types
• Comprehending Ringads
• Principles of programming with complex objects and collection types

Cites work

• A practical theory of language-integrated query
• An algebra for distributed Big Data analytics
• Finally tagless, partially evaluated: Tagless staged interpreters for simpler typed languages
• Language-integrated query with nested data structures and grouping
• Normal forms and conservative extension properties for query languages over collection types
• Optimizing object queries using an effective calculus
• Principles of programming with complex objects and collection types
• Query languages for bags and aggregate functions
• Query lifting. Language-integrated query for heterogeneous nested collections
• Simulation of the nested relational algebra by the flat relational algebra, with an application to the complexity of evaluating powerset algebra expressions
• The relational model with relation-valued attributes

Cited in

(4)

• A formalization of SQL with nulls
• Query lifting. Language-integrated query for heterogeneous nested collections
• Iterating on multiple collections in synchrony
• Strongly-Normalizing Higher-Order Relational Queries

This page was built for publication: Query lifting. Language-integrated query for heterogeneous nested collections

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2233480)