<div class="csl-bib-body">
<div class="csl-entry">Carmeli, N., & Kröll, M. (2018). Enumeration Complexity of Conjunctive Queries with Functional Dependencies. In B. Kimelfeld & Y. Amsterdamer (Eds.), <i>21st International Conference on Database Theory, {ICDT} 2018</i> (pp. 1–17). LIPIcs. https://doi.org/10.4230/LIPIcs.ICDT.2018.11</div>
</div>
-
dc.identifier.isbn
978-3-89318-078-3
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/57575
-
dc.description.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).
en
dc.description.sponsorship
Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.description.sponsorship
Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.language.iso
en
-
dc.publisher
LIPIcs
-
dc.relation.ispartofseries
Leibniz International Proceedings in Informatics (LIPIcs)
-
dc.title
Enumeration Complexity of Conjunctive Queries with Functional Dependencies
en
dc.type
Konferenzbeitrag
de
dc.type
Inproceedings
en
dc.relation.publication
21st International Conference on Database Theory, {ICDT} 2018
-
dc.relation.isbn
978-3-95977-063-7
-
dc.relation.issn
1868-8969
-
dc.description.startpage
1
-
dc.description.endpage
17
-
dc.relation.grantno
P25207-N23
-
dc.relation.grantno
P25518-N23
-
dc.type.category
Full-Paper Contribution
-
dc.publisher.place
11
-
tuw.booktitle
21st International Conference on Database Theory, {ICDT} 2018
-
tuw.relation.publisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
-
tuw.relation.publisherplace
Dagstuhl
-
tuw.project.title
Heterogenous Information Integration
-
tuw.project.title
Fixed-Parameter Tractability in Artificial Intelligence and Reasoning (FAIR)
-
tuw.publication.orgunit
E192-02 - Forschungsbereich Databases and Artificial Intelligence
-
tuw.publisher.doi
10.4230/LIPIcs.ICDT.2018.11
-
dc.description.numberOfPages
17
-
tuw.event.name
Edbt / Icdt 2018
-
tuw.event.startdate
26-03-2018
-
tuw.event.enddate
29-03-2018
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Wien
-
tuw.event.country
AT
-
tuw.event.presenter
Carmeli, Nofar
-
wb.sciencebranch
Informatik
-
wb.sciencebranch.oefos
1020
-
wb.facultyfocus
Logic and Computation (LC)
de
wb.facultyfocus
Logic and Computation (LC)
en
wb.facultyfocus.faculty
E180
-
wb.presentation.type
science to science/art to art
-
item.languageiso639-1
en
-
item.openairetype
conference paper
-
item.grantfulltext
none
-
item.fulltext
no Fulltext
-
item.cerifentitytype
Publications
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
crisitem.author.dept
E192-02 - Forschungsbereich Databases and Artificial Intelligence
-
crisitem.author.parentorg
E192 - Institut für Logic and Computation
-
crisitem.project.funder
FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
crisitem.project.funder
FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)