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.2018.16
URN: urn:nbn:de:0030-drops-86100
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8610/
Go to the corresponding LIPIcs Volume Portal

Kara, Ahmet ; Olteanu, Dan

Covers of Query Results

pdf-format:
LIPIcs-ICDT-2018-16.pdf (0.6 MB)

Abstract

We introduce succinct lossless representations of query results called covers. They are subsets of the query results that correspond to minimal edge covers in the hypergraphs of these results.

We first study covers whose structures are given by fractional hypertree decompositions of join queries.
For any decomposition of a query, we give asymptotically tight size bounds for the covers of the query result over that decomposition and show that such covers can be computed in worst-case optimal time up to a logarithmic factor in the database size. For acyclic join queries, we can compute covers compositionally using query plans with a new operator called cover-join. The tuples in the query result can be enumerated from any of its covers with linearithmic pre-computation time and constant delay.

We then generalize covers from joins to functional aggregate queries that express a host of computational problems such as aggregate-join queries, in-database optimization, matrix chain multiplication, and inference in probabilistic graphical models.

BibTeX - Entry

@InProceedings{kara_et_al:LIPIcs:2018:8610,
  author =	{Ahmet Kara and Dan Olteanu},
  title =	{{Covers of Query Results}},
  booktitle =	{21st International Conference on Database Theory (ICDT 2018)},
  pages =	{16:1--16:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-063-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{98},
  editor =	{Benny Kimelfeld and Yael Amsterdamer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8610},
  URN =		{urn:nbn:de:0030-drops-86100},
  doi =		{10.4230/LIPIcs.ICDT.2018.16},
  annote =	{Keywords: factorized database, fractional hypertree decomposition, functional aggregate query, minimal edge cover, query plan}
}

Keywords: factorized database, fractional hypertree decomposition, functional aggregate query, minimal edge cover, query plan
Collection: 21st International Conference on Database Theory (ICDT 2018)
Issue Date: 2018
Date of publication: 05.03.2018

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