Relational Design

Algorithms
Why Design Algorithms?

• An individual relation in a higher normal form does not, on its

own, guarantee a good design.
• A set of relations that together form the relational database schema
must possess certain additional properties to ensure a good
design. We discuss two of them:

1. The dependency preservation property

2. The lossless or nonadditive join property.

Why Design Algorithms?

Example :

Although EMP_LOCS is in BCNF, it still gives rise to spurious tuples when joined
with EMP_PROJ1
Why Design Algorithms?

Example :

Joining EMP_LOCS with PROJECT of which is in BCNF-also gives

rise to spurious tuples
 PROPERTIES OF
RELATIONAL
DECOMPOSITIONS
Assumptions

1. A single universal relation schema R = {A1, A2, ... An} that

includes all the attributes of the database.

2. Every attribute name is unique.

3. The set F of functional dependencies that should hold on the

attributes of R is specified by the database designers and is made

available to the design algorithms.

Attribute preservation condition of a decomposition

• The algorithms decompose the universal relation schema R into a set

of relation schemas D = {R1, R2 ... , Rm} that will become the

relational database schema; D is called a decomposition of R.

• Each attribute in R will appear in at least one relation schema Ri in the

decomposition so that no attributes are "lost";
1. Dependency Preservation
Property of a Decomposition
What is dependency preservation condition?

• When we decompose R into a set of relation schemas

D = {R1,R2…Rn} , we want each functional

dependency XA in F to be in one of the relation

schemas Ri.

This is the dependency preservation condition.

Why we want to preserve the dependencies ?

• Each dependency in F represents a constraint on the database.

• If one of the dependencies is not present in D then

1. We have to join two or more of the relations in the

decomposition
2. And then check that the functional dependency holds in
the result of the JOIN operation.
Note the following:

1. It is not necessary that the exact dependencies specified in F appear

themselves in individual relations of the decomposition D.

2. It is sufficient that the union of the dependencies

that hold on the individual relations in D be

equivalent to F.
Formal Definition
Let of F be a set of dependencies of on R.

Let Ri (F) denote the projection of F on Ri , where Ri is a subset of R

( Projection of F on Ri is the set of dependencies X Y in F+ such that the

attributes in X U Y are all contained in Ri )
Then,

A decomposition D = {R1, R2, ... , Rm} of R is dependency-

preserving with respect to F if the union of the projections of F on each
Ri in D is equivalent to F;
Example 1

The following decomposition does not preserve dependencies.(FD2 is lost)

Example 2
• The following decompositions preserve all the dependencies.
Example 3
• The following decompositions preserve all the dependencies.
Example 4

All three decompositions "lose" the functional dependency FD1.

Consider,

FD1: {STUDENT, COURSE}  INSTRUCTOR

FD2: INSTRUCTOR COURSE

3 possible decompositions of the above relation is,

1. {INSTRUCTOR , COURSE} and {INSTRUCTOR, STUDENT}

2. {STUDENT, INSTRUCTOR} and {STUDENT , COURSE}.
3. {COURSE , INSTRUCTOR} and {COURSE , STUDENT}.
2. Lossless (Nonadditive) Join Property of a
Decomposition
• The lossless join or nonadditive join property, ensures that no spurious
tuples are generated when a NATURAL JOIN operation is applied to the
relations in the decomposition.

Example :The following decomposition generates spurious tuples when we apply natural
join (*)
2. Lossless (Nonadditive) Join Property of a
Decomposition
Formal Definition
Formally, a decomposition D = {R1, R2, . . . , Rm) of R has the lossless
(nonadditive) join property with respect to the set of dependencies F on R if, for
every relation state r of R that satisfies F, the following holds, where * is the
NATURAL JOIN of all the relations in D:

The lossless join property is always defined with respect to a specific set F of
dependencies.
Testing for Lossless Join Property of a Decomposition
Algorithm : Testing for Lossless (nonadditive) Join Property
Input: A universal relation R, a decomposition D = {R1, R2, . . . Rm} of R, and a
set F of functional dependencies.

1. Create an initial matrix S with one row i for each relation Ri in D, and one column j
for each attribute Aj in R.
2. Set S(i, j):= bi,j for all matrix entries.
(* each bi,j is a distinct symbol associated with indices (i,j) *)

3. For each row i representing relation schema Ri

{for each column j representing attribute Aj
{if (relation Ri, includes attribute Aj ) then set S(i, j):= aj ;};};
(* each aj is a distinct symbol associated with index (j) *)
Testing for Lossless Join Property of a Decomposition

4. Repeat the following loop until a complete loop execution results in no

changes to S
{for each functional dependency X  Yin 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" symbol for column, set the other
rows to that same "a" symbol in the column. 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 ;};};};

5. If a row is made up entirely of "a" symbols, then the decomposition has the lossless join
property; otherwise, it does not.
Testing for Lossless Join Property of a Decomposition

Example 1 :
Testing for Lossless Join Property of a Decomposition
Example 2 :
Testing for Lossless Join Property of a Decomposition
Example 2:
Testing for Lossless Join Property of a Decomposition
Example 2:
Testing for Lossless Join Property of a Decomposition
Exercise

Consider the Relation Schema R = (A, B, C, D, E, G) and the FD set

F = {AB → C, AC → B, AD → E, B → D, BC → A, E → G}.

Determine whether the following decomposition of R has the

lossless join property with respect to F.

R1 = {A, B, C} R2 = {A, C, D, E} R3 = {A, D, G}

Testing Binary Decompositions for the lossless Join
Property:

For Binary decomposition, the following test is sufficient to

ensure that the decomposition has lossless join property.
PROPERTY LJ1 (LOSSLESS JOIN TEST FOR BINARY DECOMPOSITIONS)

A decomposition D = {R1,R2} 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 R2)  (R1 – R2)) is in F+, OR

• The FD ((R1 R2)  (R2 – R1)) is in F+,

Testing Binary Decompositions for the lossless Join
Property:
Exercise
Consider the Relation Schema R = (A, B, C, D, E, G) and the FD set
F = {AB → C, AC → B, AD → E, B → D, BC → A, E → G}.
Determine whether the following binary decomposition of R
has the lossless join property with respect to F.
1. R1 = {A, B, C} and R2 = {A, C, D, E,G}
2. R1 = {A, B,C, D, E} and R2 = {A, D, G}
3. R1 = { B, C,G} and R2 = {A,B,C, D,E}
Successive Lossless (Nonadditive) Join
Decompositions
Three algorithms for creating a relational
decomposition.

1. Relational Synthesis into 3NF with Dependency Preservation

2. Relational Decomposition into BCNF with Nonadditive Join

Property

3. Relational Synthesis into 3NF with Dependency Preservation

and Nonadditive (Lossless) Join Property

1. Relational Synthesis into 3NF with Dependency
Preservation

• The algorithm creates a dependency-preserving decomposition

D = {R1, R2, ... , Rm} of a universal relation R based on a set of
functional dependencies F, such that each Ri, in D is in 3NF.

• It guarantees only the dependency-preserving property; it does not

guarantee the lossless join property.
Algorithm: Relational Synthesis into 3NF with Dependency Preservation
Input: A universal relation R and a set of functional dependencies F on
the attributes of R.

1. Find a minimal cover G for F ;

2. For each left-hand-side X of a functional dependency that appears in
G, create a relation schema in D with attributes {X U {A1} U {A2}... U
{Ak}}, where XA1, XA2, . . . XAk are the only dependencies in G
with X as the left-hand-side . (X is the key of this relation);
3. Place any remaining attributes in a single relation schema to ensure
the attribute preservation property.
Relational Synthesis into 3NF with Dependency Preservation

Exercise -1

Consider the universal relation R = (A, B, C, D, E, F, G, H, I, J) and

the set of functional dependencies
F = {ABC, ADE, BF, FGH, DIJ}.
Decompose the above relation into 3NF using Relational
Synthesis with Dependency- Preservation algorithm
Relational Synthesis into 3NF with Dependency Preservation

Exercise - 2

Consider the universal relation R = {A, B, C, D, E, F, G, H, I, J} and

the set of functional dependencies
G = {AB C, BD EF, ADGH, A l, HJ }.
Decompose the above relation into 3NF using Relational
Synthesis with Dependency- Preservation algorithm
Relational Synthesis into 3NF with Dependency Preservation

Note the following:

1. It is obvious that all the dependencies in G are preserved by the

algorithm because each dependency appears in one of the relations
Ri in the decomposition D.
2. Since G is equivalent to F, all the dependencies in F are either
preserved directly in the decomposition or are derivable using the
inference rules.
3. The Algorithm is called the relational synthesis algorithm,
because each relation schema Ri in the decomposition is
synthesized (constructed) from the set of functional dependencies in
G with the same left-hand-side X.
 2. Relational Decomposition into BCNF with
Nonadditive Join Property

• The algorithm decomposes a universal relation schema R = {A1,A2 …

An} into a decomposition D={R1,R2, ... ,Rm} such that each Ri is in
BCNF and the decomposition D has the lossless join property with
respect to F.

• The Algorithm utilizes Property LJ1 and Claim 2 (preservation of non

additive in successive decompositions) to create a nonadditive join
decomposition D
Algorithm: Relational Decomposition into BCNF with Nonadditive Join Property

Input: A universal relation R and a set of functional dependencies F on the

attributes of R.

1. Set D = {R};

2. While there is a relation schema Q in D that is not in BCNF

do {
choose a relation schema Q in D that is not in BCNF;
find a functional dependency X  Y in Q that violates BCNF
replace Q in D by two relation schemas (Q - Y) and (X U Y);
};
Relational Decomposition into BCNF with Nonadditive Join
Property

Exercise -1
Consider the universal relation R = {A, B, C, D, E, F, G, H, I, J} and
the set of functional dependencies
F = {ABC, ADE, BF, FGH, DIJ}.
Decompose the above relation into BCNF using Relational
Decomposition into BCNF with Nonadditive Join Property
algorithm
Relational Decomposition into BCNF with Nonadditive Join
Property
Exercise -2

Consider the universal relation R = {A, B, C, D, E, F, G, H, I, J} and

the set of functional dependencies
G = {AB C, BD EF, ADGH, A l, HJ }.
Decompose the above relation into BCNF using Relational
Decomposition into BCNF with Nonadditive Join Property
algorithm
3. Relational Synthesis into 3NF with Dependency Preservation and
Nonadditive (Lossless) Join Property

•The Algorithm yields a decomposition D of R that does the following:

1. Preserves dependencies

2. Has the nonadditive join property

3. Is such that each resulting relation schema in the decomposition is in 3NF

If we want a decomposition to have both nonadditive join property and to

preserve dependencies, we have to be satisfied with relation schemas in 3NF
rather than BCNF
Algorithm : Relational Synthesis into 3NF with Dependency Preservation
and Nonadditive (Lossless) Join Property
Input: A universal relation R and a set of functional dependencies F on the

attributes of R.
1. Find a minimal cover G for F
2. For each left-hand-side X of a functional dependency that appears in
G create a relation schema in D with attributes
{X U {A1} U {A2} ... U {Ak}, where XA1 , X A2, ... , X Ak are the
only dependencies in G with X as left· hand-side (X is the key of this
relation).
3. If none of the relation schemas in D contains a key of R, then create
one more relation schema in D that contains attributes that form a
key of R.
Finding a key of R
Step 3 of Algorithm 11.4 involves identifying a key K of R. The following
Algorithm can be used to identify a key K of R based on the set of given
functional dependencies F.

Algorithm : Finding a Key K for R Given a set F of Functional

Dependencies
Input: A universal relation R and a set of functional dependencies F on the
attributes of R.
1. Set K:= R.
2. For each attribute A in K
{compute (K - A)+ with respect to F;
If (K - A)+ contains all the attributes in R, then set K := K - {A}};
Finding a key of R
Exercise - 1

Consider the relation schema R(A,B,C,D,E) and the

functional dependency set F.
F = { AB, BCE, EDA}
Using the algorithm find a key for R
Finding a key of R
Exercise - 2

Consider the relation schema R(A,B,C,D,E,F) and the

functional dependency set F.
F = { AD, BEF, ABC}
Using the algorithm find a key for R
Finding a key of R
Exercise - 3

Use the algorithm to find a key of relation

R(A, B, C, D, E) given the following set F of
functional dependencies
F = {AB  C, CD  E, DE  B}
Relational Synthesis into 3NF with Dependency Preservation and
Nonadditive (Lossless) Join Property

Exercise - 1
Consider the universal relation R = (A, B, C, D, E, F, G) and the set of
functional dependencies
F = {ABC, BCF, BDCE, CDEF, E  FG}.
Decompose R into 3NF relations using Relational Synthesis

algorithm that preserves dependency and lossless join properties

Relational Synthesis into 3NF with Dependency Preservation and
Nonadditive (Lossless) Join Property

Exercise - 2

Consider the universal relation R = (A, B, C, D, E, F, G, H, I,J) and the

set F of functional dependencies
F = {ABC, A DE, BF, F  GH, DIJ}.
Decompose R into 3NF relations using Relational Synthesis

algorithm that preserves dependency and lossless join properties

Relational Synthesis into 3NF with Dependency Preservation and
Nonadditive (Lossless) Join Property

Exercise -3

Consider the universal relation R = (A, B, C, D, E, F, G, H, I, J) and

the set of functional dependencies
G = {AB C, BD EF, ADGH, A l, HJ }.
Decompose R into 3NF relations using Relational Synthesis

algorithm that preserves dependency and lossless join properties

Problems with Null Values
and Dangling Tuples
Null Values - Loss of Information
• Loss of Information occurs when some tuples have null values for
attributes that will be used to join individual relations in the
decomposition.

To illustrate this, consider two relations EMPLOYEE and DEPARTMENT

Null Values - Loss of Information

EMPLOYEE * DEPARTMENT

The last two tuples are lost in JOIN operation

Null Values - Loss of Information
Therefore ,

• Whenever a relational database schema is designed in which

two or more relations are interrelated via foreign keys,
particular care must be devoted to watching for potential null
values in foreign keys.

• If nulls occur in other attributes, such as SALARY, their effect on

built-in functions such as SUM and AVERAGE must be carefully
evaluated.
Dangling tuples
A related problem is that of dangling tuples, which may occur if we carry a
decomposition of the EMPLOYEE relation too far.

Suppose that we decompose the EMPLOYEE relation of Figure 11.2a further into
EMPLOYEE_1 and EMPLOYEE_2
Dangling tuples

In this decomposition , If apply

EMPLOYEE_1 * EMPLOYEE_2 , we get
the original relation.
Dangling tuples
Now suppose that we use the alternative representation for
EMPLOYEE_2, where we do not include a tuple if the employee has
not been assigned a department .

Now in the result of EMPLOYEE_1 * EMPLOYEE_2,

the last two tuples are not found. These are called

dangling tuples because they are represented

in only one of the two relations that represent
employees
MULTIVALUED DEPENDENCIES
AND
FOURTH NORMAL FORM
MULTIVALUED DEPENDENCIES

• In many cases relations have constraints that cannot be specified

as functional dependencies.

• If there are two or more multivalued independent attributes to

repeat every value of one of the attributes with every value of
the other attribute.

• Because we need to keep the relation state consistent and to

maintain the independence
MULTIVALUED DEPENDENCIES

Example : ENAME PNAME DEPENDENT_NAME

Smith X John
Smith Y Michael
Smith X Michael
Smith Y John

• Here to keep the relation state consistent, we must have a

separate tuple to represent every combination of an
employee's dependent and an employee's project.
• This constraint is specified as a multivalued dependency
Formal Definition
A multivalued dependency (MVD) X —>> Y specified on relation
schema R, where X and Y are both subsets of R, specifies the following
constraint on any relation state r of R: If two tuples t1 and t2 exist in r
such that t1[X] = t2[X], then two tuples t3 and t4 should also exist in r
with the following properties:

• t3[X] = t4[X] = t1[X] = t2[X].

• t3[Y] = t1[Y] and t4[Y] = t2[Y].

• t3[Z] = t2[Z] and t4[Z] = t1[Z].

Formal Definition
Note the Following :

1. Whenever X —>> Y holds, we say that X multidetermines Y

2. X —>> Y implies X —>> Z, and therefore it is sometimes written as X

—>> YI Z.

3. An MVD X —>> Y in R is called a trivial MVD if

• Y is a subset of X, OR

• (b) X υ Y = R.

4. An MVD that satisfies neither (a) nor (b) is called a nontrivial MVD
Formal Definition
Example for trivial MVD

EMP_PROJECTS Relation

ENAME PNAME

Smith X ENAME —>> PNAME.

Smith Y

A trivial MVD will hold in any relation state r of R

Fourth Normal (4NF)
Definition:

A relation schema R is in 4NF with respect to a set of

dependencies F (that includes functional dependencies and
multivalued dependencies) if, for every nontrivial multivalued
dependency X —>> Y in F+, X is a superkey for R.

Note: F+ is the (complete) set of all dependencies (functional or

multivalued) that will hold in every relation state r of R that
satisfies F. It is also called the closure of F.
Fourth Normal (4NF) - Example
Lossless (Nonadditive) Join Decomposition into 4NF
Relations

PROPERTY LJ1’

The relation schemas R1 and R2 form a lossless (non-additive)

join decomposition of R with respect to a set F of functional and
multivalued dependencies if and only if

(R1 ∩ R2) —>> (R1 - R2)

or by symmetry, if and only if

(R1 ∩ R2) —>> (R2 - R1)).

Algorithm : Relational decomposition into 4NF relations with
non-additive join property

Input: A universal relation R and a set of functional and multivalued

dependencies F.

1. Set D := { R };
2. While there is a relation schema Q in D that is not in 4NF do
{ choose a relation schema Q in D that is not in 4NF;
find a nontrivial MVD X —>> Y in Q that violates 4NF;
replace Q in D by two relation schemas (Q - Y) and (X υ Y);
};