Size and Treewidth Bounds for Conjunctive Queries
Georg Gottlob, Stephanie Tien Lee, Gregory Valiant, Paul Valiant · Journal of the ACM · 2012
This article provides new worst-case bounds for the size and treewith of the result Q ( D ) of a conjunctive query Q applied to a database D . We derive bounds for the result size | Q ( D )| in terms of structural properties of 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 ( Q ) to each query Q . Intuitively, each color used represents some possible entropy of that variable. Using this coloring number, we derive tight bounds for the size of Q ( 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.