Databases Reference

In-Depth Information

At the conclusion of this procedure, the elements of
S
are the headings of a set of BCNF relvars into which
R

can be nonloss decomposed, though not necessarily without losing FDs. Also, let me point out for the record that

the procedure makes no mention of either 2NF or 3NF.

IDENTITY DECOMPOSITIONS

It's a bit of a digression from the main theme of this chapter, but I'd like to elaborate briefly on the concept of an

identity projection. Here's a definition (I define it for relvars, but of course an analogous concept applies to

relations as well):

Definition:
The
identity projection
of a given relvar is the projection of that relvar on all of its attributes.

Now, it should be obvious that any relvar can be nonloss decomposed, albeit trivially, into its identity

projection. However, some people don't like to think of such a decomposition as being a decomposition, as such, at

all (as I said in connection with the SJT example, “there isn't much decomposition, as such, going on here”). If you

happen to be one of those people, then, you might prefer the following way of looking at the matter. Let relvar
R

have heading
H
. Then it's certainly true that the FD {} → {} holds in
R
, where {} is the empty set of attributes (this

FD is trivial, of course, and holds in
every
relvar). By Heath's Theorem, therefore—take
X
,
Y
, and
Z
to be {}, {},

and
H
, respectively—
R
can be nonloss decomposed into its projections
R1
and
R2
, where:

1.

The heading
XY
of
R1
is the union of {} and {}, which reduces to just {}; i.e.,
R1
is the projection of
R
on no

attributes at all, and its value is either TABLE_DUM, if
R
is empty, or TABLE_DEE otherwise.
11

2.

The heading
XZ
of
R2
is the union of {} and
H
, which reduces to just
H
; i.e.,
R2
is the projection of
R
on all

of its attributes, or in other words the identity projection of
R
.

I hope it's clear that this decomposition is nonloss—
R
is certainly equal to the join of
R1
and
R2
. (On the other

hand, it's also true that the combination of
R1
and
R2
fails to meet the usual requirement that both projections

should be needed in the reconstruction process.)

While I'm on the subject of what might be called
identity decompositions
, let me remark that any relvar can

also always be decomposed (again trivially, but this time “horizontally” instead of “vertically”) into the

corresponding identity
restriction
.
12
Here's a definition (again I define it for relvars, but of course an analogous

concept applies to relations as well):

Definition:
The
identity restriction
of a given relvar
R
is any restriction of
R
in which the restriction

condition is identically true—in other words, any restriction of
R
that's logically equivalent to one of the

following form:

R
WHERE TRUE

11
TABLE_DUM and TABLE_DEE are pet names for, respectively, the unique relation with no attributes and no tuples and the unique relation

with no attributes and one tuple. (We've met these relations before, in the answer to Exercise 2.8 in Appendix D.) For further discussion, see

SQL and Relational Theory
.

12
For precise definitions of
restriction
and the associated notion of a
restriction condition
, see the answer to Exercise 13.13 in Appendix D.