Thumbnail
Access Restriction
Subscribed

Author Gottlob, Georg ♦ Lee, Stephanie Tien ♦ Valiant, Gregory ♦ Valiant, Paul
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2012
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Database theory ♦ Conjunctive queries ♦ Size bounds ♦ Treewidth
Abstract This article provides new worst-case bounds for the size and treewith of the result $\textit{Q}(\textit{D})$ of a conjunctive query $\textit{Q}$ applied to a database $\textit{D}.$ We derive bounds for the result size $|\textit{Q}(\textit{D})|$ in terms of structural properties of $\textit{Q},$ both in the absence and in the presence of keys and functional dependencies. These bounds are based on a novel “coloring” of the query variables that associates a coloring number $C}(\textit{Q})$ to each query $\textit{Q}.$ Intuitively, each color used represents some possible entropy of that variable. Using this coloring number, we derive tight bounds for the size of $\textit{Q}(\textit{D})$ in case (i) no functional dependencies or keys are specified, and (ii) simple functional dependencies (keys) are given. These results generalize recent size-bounds for join queries obtained by Atserias et al. [2008]. In the case of arbitrary (compound) functional dependencies, we use tools from information theory to provide lower and upper bounds, establishing a close connection between size bounds and a basic question in information theory. Our new coloring scheme also allows us to precisely characterize (both in the absence of keys and with simple keys) the treewidth-preserving queries---the queries for which the treewidth of the output relation is bounded by a function of the treewidth of the input database. Finally, we give some results on the computational complexity of determining the size bounds, and of deciding whether the treewidth is preserved.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2012-06-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 59
Issue Number 3
Page Count 35
Starting Page 1
Ending Page 35


Open content in new tab

   Open content in new tab
Source: ACM Digital Library