This paper resolves the main open question left by Gottlob, Lee, and Valiant
(PODS 2009)[GLV09], establishing tight worst-case bounds for the size of the
result Q(D) of a conjunctive query Q to a database D given an arbitrary set of
functional dependencies. We show that the lower bound presented in [GLV09] in
which the variables of the query are "colored" so as to yield a coloring number
C(Q) for each query Q is, in fact, also an upper bound. To show this, we
formalize the original intuition that each color used represents some possible
entropy of that variable, and express the maximum possible size increase as a
linear program that seeks to maximize how much more entropy is in the result of
the query than the input. Although this linear program has exponentially many
variables, we also show that we can decide in polynomial time whether the
result can be any larger than the input database.