License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2019.8
URN: urn:nbn:de:0030-drops-103106
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10310/
Go to the corresponding LIPIcs Volume Portal

Console, Marco ; Guagliardo, Paolo ; Libkin, Leonid

Fragments of Bag Relational Algebra: Expressiveness and Certain Answers

pdf-format:
LIPIcs-ICDT-2019-8.pdf (0.5 MB)

Abstract

While all relational database systems are based on the bag data model, much of theoretical research still views relations as sets. Recent attempts to provide theoretical foundations for modern data management problems under the bag semantics concentrated on applications that need to deal with incomplete relations, i.e., relations populated by constants and nulls. Our goal is to provide a complete characterization of the complexity of query answering over such relations in fragments of bag relational algebra.
The main challenges that we face are twofold. First, bag relational algebra has more operations than its set analog (e.g., additive union, max-union, min-intersection, duplicate elimination) and the relationship between various fragments is not fully known. Thus we first fill this gap. Second, we look at query answering over incomplete data, which again is more complex than in the set case: rather than certainty and possibility of answers, we now have numerical information about occurrences of tuples. We then fully classify the complexity of finding this information in all the fragments of bag relational algebra.

BibTeX - Entry

@InProceedings{console_et_al:LIPIcs:2019:10310,
  author =	{Marco Console and Paolo Guagliardo and Leonid Libkin},
  title =	{{Fragments of Bag Relational Algebra: Expressiveness and Certain Answers}},
  booktitle =	{22nd International Conference on Database Theory (ICDT 2019)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-101-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{127},
  editor =	{Pablo Barcelo and Marco Calautti},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10310},
  doi =		{10.4230/LIPIcs.ICDT.2019.8},
  annote =	{Keywords: bag semantics, relational algebra, expressivity, certain answers, complexity}
}

Keywords: bag semantics, relational algebra, expressivity, certain answers, complexity
Collection: 22nd International Conference on Database Theory (ICDT 2019)
Issue Date: 2019
Date of publication: 19.03.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI