of R, where 
= (A, B, C) and 
= (A, D).
In the decomposition, the functional dependency AB 
D
cannot be tested for relations 
and 
without
computing 
.
A decomposition may result in the inability to test whether a functional dependency holds without computing a join.
Example: Consider relation scheme R = (A, B, C, D), a decomposition
of R, where = (A, B, C) and = (A, D).
In the decomposition, the functional dependency AB D
cannot be tested for relations and without
computing .
As computing joins is expensive, we want to avoid computing a join
each time a tuple is inserted into or (or a tuple in either
relation is updated). This is possible if each functional dependency
refers to attributes of only one relation.
Given a decomposition 
of relation scheme R
and a set of functional dependencies F on R, the restriction of
F to 
is the set 
of all functional dependencies
in F such that 
and
.
In the previous example, the functional dependency AB D
is not in any .
Define F' = 
. (Note that 
in general.) The decomposition is
dependency preserving if 
.
In the previous example, F = {AB D} and F' = {}.
The decomposition is not dependency preserving because
AB D 
, but AB D 
.
Naive algorithm for checking dependency preservation:
Inputs: A decomposition D = and a set of
functional dependencies F
Output: true or false
in D and unioning the results.
)
The running time of this algorithm is exponential in the size of F,
because computing takes time exponential in the size of F.
A more efficient algorithm (although one that rejects some decompositions that are actually dependency preserving) is as follows (given the same inputs and computing the same outputs):
, a canonical cover of F.
)
If this algorithm reports that the decomposition is dependency preserving, then it in fact is dependency preserving because:
= (i.e. 
and 
),
then 
by definition of canonical cover. Hence, if
(a subset of ) does not equal , then 
does
not equal .
Unfortunately, this algorithm does reject some decompositions that are dependency preserving because of the choice of canonical cover (remember that canonical covers are not unique).
Example: Given R = (A, B, C, D, E, G) and
F = {CE A, C A,
C B, AB C, A B, B A},
we have seen that both
= {C B, A B, B AC}
and 
= {C B, A C, B A}
are canonical covers of F. Given decomposition = (B, C),
= (A, C) and 
= (A, B, D, E, G):
, because B AC 
= 
However, this algorithm is worth trying because it is much more efficient than the naive algorithm, and spurious rejections are relatively rare for good decompositions.
Note: to test that dependencies hold, the system must test the canonical cover used, NOT the original set of functional dependencies F - because testing F would often require computing joins.