  Acyclic schemes posses known benefits for database design, speeding up
queries, and reducing space requirements. An acyclic join dependency (AJD) is
lossless with respect to a universal relation if joining the projections
associated with the schema results in the original universal relation. An
intuitive and standard measure of loss entailed by an AJD is the number of
redundant tuples generated by the acyclic join. Recent work has shown that the
loss of an AJD can also be characterized by an information-theoretic measure.
Motivated by the problem of automatically fitting an acyclic schema to a
universal relation, we investigate the connection between these two
characterizations of loss. We first show that the loss of an AJD is captured
using the notion of KL-Divergence. We then show that the KL-divergence can be
used to bound the number of redundant tuples. We prove a deterministic lower
bound on the percentage of redundant tuples. For an upper bound, we propose a
random database model, and establish a high probability bound on the percentage
of redundant tuples, which coincides with the lower bound for large databases.
