Home | | **Database Management Systems** | | **FUNDAMENTALS OF Database Systems** | | **Database Management Systems** | Properties of Relational Decompositions

1. Relation Decomposition and Insufficiency of Normal Forms
2. Dependency Preservation Property of a Decomposition
3. Nonadditive (Lossless) Join Property of a Decomposition
4. Testing Binary Decompositions for the Nonadditive Join Property
5. Successive Nonadditive Join Decompositions

**Properties of Relational Decompositions**

We now turn our attention to the process of decomposition that we used
through-out Chapter 15 to decompose relations in order to get rid of unwanted
dependencies and achieve higher normal forms. In Section 16.2.1 we give
examples to show that looking at an *individual*
relation to test whether it is in a higher normal form does not, on its own,
guarantee a good design; rather, a *set of
relations* that together form the relational database schema must possess
certain additional properties to ensure a good design. In Sections 16.2.2 and
16.2.3 we discuss two of these proper-ties: the dependency preservation
property and the nonadditive (or lossless) join property. Section 16.2.4
discusses binary decompositions and Section 16.2.5 dis-cusses successive
nonadditive join decompositions.

**1. Relation Decomposition and
Insufficiency of Normal Forms**

The
relational database design algorithms that we present in Section 16.3 start
from a single **universal relation schema**
*R* = {*A*_{1}, *A*_{2},
..., *A _{n}*} that includes

We must
make sure that each attribute in *R*
will appear in at least one relation schema *R _{i}*
in the decomposition so that no attributes are

This is
called the **attribute preservation**
condition of a decomposition.

Another
goal is to have each individual relation *R _{i}*
in the decomposition

**2. Dependency Preservation Property of a Decomposition**

It would
be useful if each functional dependency *X*→*Y*
specified in *F* either appeared
directly in one of the relation schemas *R _{i}*
in the decomposition

It is not
necessary that the exact dependencies specified in *F* appear themselves in individual relations of the decomposition *D*. It is sufficient that the union of
the dependencies that hold on the individual relations in *D* be equivalent to *F*. We
now define these concepts more formally.

**Definition. **Given a set of dependencies** ***F*** **on**
***R*, the** projection **of** ***F***
**on** ***R _{i}*,

projections
of *F* on each *Ri* in *D* is equivalent to *F*;
that is, ((π* _{R}* (

(π* _{Rm}*(

If a
decomposition is not dependency-preserving, some dependency is **lost** in the decomposition. To check
that a lost dependency holds, we must take the JOIN of two or more relations in
the decomposition to get a relation that includes all left-and right-hand-side
attributes of the lost dependency, and then check that the dependency holds on
the result of the JOIN—an option that is not practical.

An
example of a decomposition that does not preserve dependencies is shown in Figure
15.13(a), in which the functional dependency FD2 is lost when LOTS1A is decomposed into {LOTS1AX, LOTS1AY}. The decompositions in Figure 15.12, how-ever, are
dependency-preserving. Similarly, for the example in Figure 15.14, no mat-ter
what decomposition is chosen for the relation TEACH(Student, Course, Instructor) from
the three provided in the text, one or both of the dependencies originally
present are bound to be lost. We state a claim below related to this property
without providing any proof.

**Claim 1. **It is always possible to find a
dependency-preserving decomposition** ***D *with respect to* F *such that each relation* R _{i}
*in

In
Section 16.3.1, we describe Algorithm 16.4, which creates a
dependency-preserving decomposition *D*
= {*R*_{1}, *R*_{2}, ..., *R _{m}*} of a universal relation

**3. Nonadditive (Lossless) Join Property of a Decomposition**

Another
property that a decomposition *D*
should possess is the nonadditive join property, which ensures that no spurious
tuples are generated when a NATURAL JOIN operation is applied to the
relations resulting from the decomposition. We already
illustrated this problem in Section 15.1.4 with the example in Figures 15.5 and
15.6. Because this is a property of a decomposition of relation *schemas,* the condition of no spurious
tuples should hold on *every legal
relation state—*that is, every relation state that satisfies the functional
dependencies in *F*. Hence, the
lossless join property is always defined with respect to a specific set *F* of dependencies.

**Definition. **Formally, a decomposition** ***D*** **= {*R*_{1},** ***R*_{2},
...,** ***R _{m}*} of

The word
loss in *lossless* refers to *loss of information*, not to loss of
tuples. If a decom-position does not have the lossless join property, we may
get additional spurious tuples after the PROJECT (π) and NATURAL JOIN (*) operations are applied;
these additional tuples represent erroneous or invalid information. We prefer
the term *nonadditive join *because it
describes the situation more accurately. Although the* *term *lossless join* has
been popular in the literature, *we will
henceforth use the term* *nonadditive
join*, which is self-explanatory and unambiguous. The nonadditive join* *property ensures that no spurious
tuples result after the application of PROJECT and JOIN operations. We may, however,
sometimes use the term **lossy design**
to refer to a design that represents a loss of information (see example at the
end of Algorithm 16.4).

The
decomposition of EMP_PROJ(Ssn, Pnumber, Hours, Ename, Pname, Plocation) in
Figure 15.3 into EMP_LOCS(Ename, Plocation) and EMP_PROJ1(Ssn, Pnumber, Hours,

Pname, Plocation) in Figure 15.5 obviously does not have the
nonadditive join property, as illustrated by Figure 15.6. We will use a
general procedure for testing whether any decomposition *D* of a relation into *n*
relations is nonadditive with respect to a set of given functional dependencies
*F* in the relation; it is presented as
Algorithm 16.3 below. It is possible to apply a simpler test to check if the
decomposition is nonaddi-tive for binary decompositions; that test is described
in Section 16.2.4.

Algorithm 16.3. Testing for Nonadditive Join
Property

**Input: **A universal relation** ***R*,
a decomposition** ***D*** **= {*R*_{1},** ***R*_{2}, ...,** ***R _{m}*}
of

*Note*: Explanatory comments are given
at the end of some of the steps. They fol-low the format: (* *comment* *).

**
**Create an initial matrix *S* with one row *i* for each
relation *R _{i}* in

**
**Set *S*(*i*, *j*):=
*b _{ij}* for all matrix
entries. (* each

**
**For each row *i*
representing relation schema *R _{i}*
{for each column

**
**{if (relation *R _{i}*
includes attribute

**
**Repeat the following loop until a *complete loop execution* results in no

changes
to *S*

{for each
functional dependency *X* → *Y* in *F*

{for all
rows in *S that have the same symbols*
in the columns corresponding to attributes in *X*

{make the
symbols in each column that correspond to an attribute in *Y* be the same in all these rows as follows: If any of the rows has
an *a* sym-bol for the column, set the
other rows to that *same a* symbol in
the col-umn. If no *a* symbol exists
for the attribute in any of the rows, choose one of the *b* symbols that appears in one of the rows for the attribute and set
the other rows to that same *b* symbol
in the column ;} ; } ;};

**
**If a row is made up entirely of *a* symbols, then the decomposition has
the nonadditive join property; otherwise, it does not.

Given a
relation *R* that is decomposed into a
number of relations *R*_{1}, *R*_{2}, ..., *R _{m}*, Algorithm 16.3 begins the matrix

If, on
the other hand, no row ends up being all *a*
symbols, *D* does not satisfy the
lossless join property. In this case, the relation state *r* represented by *S* at the
end of the algorithm will be an example of a relation state *r* of *R*
that satisfies the depend-encies in *F*
but does not satisfy the nonadditive join condition. Thus, this relation serves
as a **counterexample** that proves that
*D* does not have the nonadditive join
property with respect to *F*. Note that
the *a* and *b* symbols have no special meaning at the end of the algorithm.

Figure
16.1(a) shows how we apply Algorithm 16.3 to the decomposition of the EMP_PROJ relation schema from Figure
15.3(b) into the two relation schemas
EMP_PROJ1 and EMP_LOCS in Figure
15.5(a). The loop in step 4 of the algorithm
cannot
change any *b* symbols to *a* symbols; hence, the resulting matrix *S* does not have a row with all *a* symbols, and so the decomposition does
not have the non-additive join property.

Figure
16.1(b) shows another decomposition of EMP_PROJ (into EMP, PROJECT, and WORKS_ON) that
does have the nonadditive join property, and Figure 16.1(c) shows how we apply
the algorithm to that decomposition. Once a row consists only of *a* symbols, we conclude that the decomposition
has the nonadditive join property, and we can stop applying the functional
dependencies (step 4 in the algorithm) to the matrix *S*.

**Figure
16.1**

Nonadditive join test for *n*-ary decompositions. (a) Case 1: Decomposition of EMP_PROJ into
EMP_PROJ1 and EMP_LOCS fails test. (b) A decomposition of EMP_PROJ that has the
lossless join property. (c) Case 2: Decomposition of EMP_PROJ into EMP,
PROJECT, and WORKS_ON satisfies test.

**4. Testing Binary Decompositions for the Nonadditive Join Property**

Algorithm
16.3 allows us to test whether a particular decomposition *D* into *n* relations obeys
the nonadditive join property with respect to a set of functional dependencies *F*. There is a special case of a
decomposition called a **binary
decomposition**—decomposition of a relation** ***R*** **into two relations. We give an easier test to** **apply than Algorithm 16.3, but while it is very handy to use, it
is *limited* to binary decompositions
only.

Property NJB (Nonadditive Join Test for Binary
Decompositions). A decomposition
*D* = {*R*_{1}, *R*_{2}}
of *R* has the lossless (nonadditive)
join property with respect to a set of functional dependencies *F* on *R
if and only if* either

The FD ((*R*_{1}
∩ *R*_{2}) → (*R*_{1} – *R*_{2})) is in *F*^{+},
or

The FD ((*R*_{1}
∩ *R*_{2}) → (*R*_{2} – *R*_{1})) is in *F*^{+}

You
should verify that this property holds with respect to our informal successive
normalization examples in Sections 15.3 and 15.4. In Section 15.5 we decomposed
LOTS1A into two BCNF relations LOTS1AX and LOTS1AY, and decomposed the TEACH relation in Figure 15.14 into the two relations {__Instructor__, Course} and {__Instructor__, __Student__}. These are valid decompositions
because they are nonadditive per the above test.

**5. Successive Nonadditive Join Decompositions**

We saw
the successive decomposition of relations during the process of second and
third normalization in Sections 15.3 and 15.4. To verify that these
decompositions are nonadditive, we need to ensure another property, as set forth
in Claim 2.

**Claim 2 (Preservation of Nonadditivity in
Successive Decompositions). **If a** **decomposition *D* = {*R*_{1}, *R*_{2}, ..., *R _{m}*}
of

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2021 BrainKart.com; All Rights Reserved. (BS) Developed by Therithal info, Chennai.