Mixing set and bag semantics

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

Abstract

The conservativity theorem for nested relational calculus implies that query expressions can freely use nesting and unnesting, yet as long as the query result type is a flat relation, these capabilities do not lead to an increase in expressiveness over flat relational queries. Moreover, Wong showed how such queries can be translated to SQL via a constructive rewriting algorithm. While this result holds for queries over either set or multiset semantics, to the best of our knowledge, the questions of conservativity and normalization have not been studied for queries that mix set and bag collections, or provide duplicate-elimination operations such as SQL's SELECT DISTINCT. In this paper we formalize the problem, and present partial progress: specifically, we introduce a calculus with both set and multiset collection types, along with natural mappings from sets to bags and vice versa, present a set of valid rewrite rules for normalizing such queries, and give an inductive characterization of a set of queries whose normal forms can be translated to SQL. We also consider examples that do not appear straightforward to translate to SQL, illustrating that the relative expressiveness of flat and nested queries with mixed set and multiset semantics remains an open question.
Original languageEnglish
Title of host publicationProceedings of The 17th International Symposium on Database Programming Languages
Place of PublicationNew york
PublisherACM
Pages70-73
Number of pages5
ISBN (Print)978-1-4503-6718-9
DOIs
Publication statusPublished - 23 Jun 2019
Event17th International Symposium on Database Programming Languages - Phoenix, United States
Duration: 23 Jun 201923 Jun 2019
https://pldi19.sigplan.org/track/dbpl-2019-papers#About

Symposium

Symposium17th International Symposium on Database Programming Languages
Abbreviated titleDBPL 2019
CountryUnited States
CityPhoenix
Period23/06/1923/06/19
Internet address

Keywords

  • language-integrated query
  • query normalization

Fingerprint Dive into the research topics of 'Mixing set and bag semantics'. Together they form a unique fingerprint.

Cite this