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

Carmeli, Nofar ; Kröll, Markus

Enumeration Complexity of Conjunctive Queries with Functional Dependencies

pdf-format:
LIPIcs-ICDT-2018-11.pdf (0.5 MB)

Abstract

We study the complexity of enumerating the answers of Conjunctive Queries (CQs) in the presence of Functional Dependencies (FDs). Our focus is on the ability to list output tuples with a constant delay in between, following a linear-time preprocessing. A known dichotomy classifies the acyclic self-join-free CQs into those that admit such enumeration, and those that do not. However, this classification no longer holds in the common case where the database exhibits dependencies among attributes. That is, some queries that are classified as hard are in fact tractable if dependencies are accounted for. We establish a generalization of the dichotomy to accommodate FDs; hence, our classification determines which combination of a CQ and a set of FDs admits constant-delay enumeration with a linear-time preprocessing.

In addition, we generalize a hardness result for cyclic CQs to accommodate a common type of FDs. Further conclusions of our development include a dichotomy for enumeration with linear delay, and a dichotomy for CQs with disequalities. Finally, we show that all our results apply to the known class of "cardinality dependencies" that generalize FDs (e.g., by stating an upper bound on the number of genres per movies, or friends per person).

BibTeX - Entry

@InProceedings{carmeli_et_al:LIPIcs:2018:8598,
  author =	{Nofar Carmeli and Markus Kr{\"o}ll},
  title =	{{Enumeration Complexity of Conjunctive Queries with Functional Dependencies}},
  booktitle =	{21st International Conference on Database Theory (ICDT 2018)},
  pages =	{11:1--11:17},
  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/8598},
  URN =		{urn:nbn:de:0030-drops-85988},
  doi =		{10.4230/LIPIcs.ICDT.2018.11},
  annote =	{Keywords: Enumeration, Complexity, CQs}
}

Keywords: Enumeration, Complexity, CQs
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