Databases Reference

In-Depth Information

as indicated in Fig. 3.2 (which shows, of course, values for those relvars corresponding to the sample value shown

for relvar S in Fig. 3.1).

SNC CT

┌─────┬───────┬────────┐ ┌────────┬────────┐

│ SNO │ SNAME │ CITY │ │ CITY │ STATUS │

├═════┼───────┼────────┤ ├════════┼────────┤

│ S1 │ Smith │ London │ │ Athens │ 30 │

│ S2 │ Jones │ Paris │ │ London │ 20 │

│ S3 │ Blake │ Paris │ │ Paris │ 30 │

│ S4 │ Clark │ London │ └────────┴────────┘

│ S5 │ Adams │ Athens │

└─────┴───────┴────────┘

Fig. 3.2: Relvars SNC and CT—sample values

Points arising from this example:

First, the decomposition certainly eliminates the redundancy—the fact that a given city has a given status

now appears exactly once.

Second, the decomposition process is basically a process of
taking projections
—the relations shown in

Fig. 3.2 are each projections of the relation shown in Fig. 3.1.
2
In fact, we can write a couple of equations:

SNC = S { SNO , SNAME , CITY }

CT = S { CITY , STATUS }

(Recall from Chapter 2 that the
Tutorial D
syntax for projection takes the form
r
{
A1
,...,
An
}, where
r
is some

relational expression and
A1
, ...,
An
are attribute names.)
3

Third, the decomposition process is
nonloss
(also called
lossless
)—no information is lost in the process,

because the relation shown in Fig. 3.1 can be reconstructed by taking the
join
of the relations shown in

Fig. 3.2:

S = JOIN { SNC , CT }

(
Tutorial D
syntax again.) Thus, we can say the relation in Fig. 3.1 and the pair of relations in Fig. 3.2 are

information equivalent
—or, to state the matter more precisely, for any query that can be performed against

the relation of Fig. 3.1, there's a corresponding query that can be performed against the relations of Fig. 3.2

2
Other kinds of decomposition are possible, but I'll assume until further notice that “decomposition,” unqualified, means decomposition via

projection specifically.

3
Tutorial D
also supports syntax of the form
R
{ALL BUT
B1
,...,
Bm
}, which denotes the projection of
r
on all of its attributes except
B1
, ...,
Bm
.

For example, the projection corresponding to SNC in the example could alternatively be expressed thus: S {ALL BUT STATUS}.