Databases Reference
In-Depth Information
INDEPENDENT PROJECTIONS
To close this chapter, I'd like to return to the example I opened it with. Just to remind you, that example involved
the nonloss decomposition of our usual suppliers relvar S into its projections SNC (on {SNO,SNAME,CITY}) and
ST (on {SNO,STATUS}). That decomposition lost the FD {CITY} → {STATUS}, with the consequence that
updates to either of the projections sometimes required updates to the other, in order to enforce the constraint that
each city has just one status. By contrast, the “sensible” decomposition into projections SNC (on
{SNO,SNAME,CITY}) and CT (on {CITY,STATUS}) suffers from no such problem—updates can be made to
either projection without regard to the other.
14
For the sake of the present discussion, let me refer to decompositions like the one into SNC and ST as
bad
and decompositions like the one into SNC and CT as
good
. As we've seen, then, the projections in a good
decomposition can be updated independently of each other; for that reason, they're sometimes referred to explicitly
as
independent projections
. By contrast, the projections in a bad decomposition aren't independent in that same
sense. So we can say that in order to preserve FDs, we want a decomposition in which the projections are
independent. And there's a theorem, due to Jorma Rissanen, that can help in this regard. Before I state that
theorem, however, let me give a precise definition of what it means for two projections to be independent:
Definition:
Projections
R1
and
R2
of relvar
R
are
independent
if and only if every FD that holds in
R
also
holds in the join of
R1
and
R2
.
Here now is the theorem:
Rissanen's Theorem:
Let relvar
R
, with heading
H
, have projections
R1
and
R2
, with headings
H1
and
H2
,
respectively; further, let
H1
and
H2
both be proper subsets of
H
, let their union be equal to
H
, and let their
intersection not be empty.
15
Then projections
R1
and
R2
are
independent
if and only if (a) their common
attributes constitute a superkey for at least one of them and (b) every FD that holds in
R
is implied by those
that hold in at least one of them.
Consider the “good” decomposition of S into its projections SNC and CT. Those two projections are
independent, because (a) the set of common attributes is just {CITY} and {CITY} is a (super)key for CT, and
(b) every FD that holds in S either holds in one of the two projections or is implied by those that do (see the next
chapter). By contrast, consider the “bad” decomposition into the projections SNC and ST. Here the projections
aren't independent, because the FD {CITY} → {STATUS} can't be inferred from those holding in those
projections—although it's at least true that the set of common attributes, {SNO}, is a key for both.
As a historical note, it was Rissanen's work on independent projections (which was done, or at least
published, in 1977) that laid the foundation for the theory of what we now call FD preservation.
14
Except that there might be a foreign key constraint, or even an equality dependency, between {CITY} in CT and {CITY} in SNC.
15
The condition that the intersection of
H1
and
H2
not be empty is as in Rissanen's original statement of the theorem but appears to be
unnecessary.
