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.