Normalization Theory

Science Faculty
Department of Software Engineering

theory of RM

Bad DB projects

Functional dependencies
Multivalued dependencies
Join dependencies

Normal forms
Design of

theory
The theory of relational model normalization establish :
how initial

limit of 9 purchases. What if a customer has more

9 purchases

be added because some other data is absent .
Update anomaly:

Why! It is possible when one relation contains information about two ore more entities of the application domain

CUSTOMER-PURCHASE

process of equivalent transformation of one relational schema into other

Compound (not atomic) values - 1NF
Not full (partial) functional dependence - 2NF
Transitive functional dependence - 3NF
Multivalued dependence - 4NF
Join dependence - 5NF

There are the following unwanted properties of relations and normal forms that remove corresponding properties:

(1NF)


Relation is in the first normal form (1NF) if

A and B is given. In relation R attribute B

Formally FD is defined in such a way :

The presence of FD is property of the relational schema, but not of instance of relational schema, and reflects semantics of the AD.

The set of FD can be viewed as a set of integrity constraints on the relation scheme; it should be preserved under decomposition.

is candidate key of the relation R if :
each attribute

Assertion: Any relation has candidate key.

Set of attributes K in relation R is called superkey of the relation R if each attribute of the relation R functionally depends on K.

are Armstrong axioms
Armstrong’s axioms are a
sound and complete set of

have set of functional dependencies F and the dependence А

For example, if we have the relation R(A, B, C) and F contains the dependence А → С, then the following dependences are logically implied from F:

(А, С) → В - continuation property is applied;
(А, С) → (В, С) - augmentation property is applied .

FD
Let’s relation R have set of functional dependencies F. The

Set of functional dependencies F is complete if F = F+.

Two sets of dependencies F and G are (logically) equivalent if F+ = G+.

Lets given sets of functional dependencies F and G such that G ⊂ F. G is a cover of F if G+ =F+. If G is minimal then G is called basis of dependencies of F or minimal cover.
NOTE: Minimal cover isn't necessarily unique.

domain contains functional dependence А → В there exists class

This thesis gives formal basis for identifying entities in AD.

form (2NF)
Let’s given relation with schema R(A, B, C). Functional

CUSTOMER-PURCHASE

Attribute Q-TY depends fully from (PN, CN, DATE)
Attributes NAME and CITY depends fully from CN
Attributes NAME and CITY depends not fully (partially) from (PN, CN, DATE)

not full FD exist
CUSTOMER-PURCHASE
Update anomalies. When changing customer city it

in the second normal form (2NF) if it is in

Теорема (Хита). The relation R with attributes А, В, С , where R.A → R.B, is equal to natural join of the projections R[A, B] and R[A, C].

Algorithm of reduction to 2NF. Given relation R with set of attributes M. If in R there is not full functional dependence R.A → R.B of non primary attribute B from a candidate key A, the relation R is decomposed into the following two relations: R [A, B] and R [M - B]. If the resulting relations are still not in the second normal form, the mentioned algorithm is applied to these relations again.

Such splitting is called binary decomposition.

Summary
Source relation contains information from 2 entities, every resulting relations

(3NF)
1) Condition В → А is necessary in order to

Student card No

Tax ID

Student name

2) Conditions С ⊄ В, В ⊄ А are necessary to exclude the following trivial transitive dependencies:

А

С

В

В

А

С

transitive FD exist
DEPARTMENT-FACULTY


DEPARTMENT entities
FACULTY entities
Availability transitive dependencies in a relation

in the third normal form (3NF) if it is in

Algorithm of the relation reduction to 3NF. Let’s given the relation R with attributes A, B, C and there are functional dependencies R.A → R.B and R.В → R.С. The relation R decomposed into following two relations: R[A, B] and R[B, С]. If the resulting relations are still not in the third normal form, the mentioned algorithm is applied to these relations again.

Summary
Results the same as in reduction to the 2NF:
Source relation

absence of transitive dependence of nonprimary attributes but not all

Relation is in strong 3NF, if it is in 3NF and does not contain transitive dependencies of ALL attributes from candidate keys .

This relation is in the 3NF, but still contains information about two entities. So it hold anomalies.

to the S3NF is the same as for 3NF


Student

Subject
Teacher
STUDY






Student

Teacher

Teacher

Subject
TEACHING-WHOM
TEACHING-WHAT
NOTE. One of

Boyce-Codd normal, if every its determinants is a superkey.
Assertion. S3NF and

(4NF)
Thesis: If in an application domain there is no

TEACHING

R with attributes (set of attributes) А, В, С. There

Example: In the relation TEACHING the are the following MVD:

Let’s there is relation R(A,B). The MVDs А →→ ∅ and А →→ В are called trivial because they exist in any relations.

Subject →→ Teacher Subject →→ Bood

of attributes) А, В, С.
Multivalued dependences have the following axioms

If А →→ В, then А →→ С

2) Augmentation axiom

If А →→ В and V ⊆ W, then (А, W) →→ (В, V)

3) Transitivity axiom

If А →→ В and В →→ С, then А →→ С – В

The following two axioms relates functional and multivalued dependencies .
If

2) Coalescence axiom

If А →→ В and Z ⊆ B, and for some W, that is not intersect with B we have W → Z, then A → Z

→→ В and А →→ С, then А →→ (В,

If А →→ В and (W, В) →→ Z ,
then (W, А) →→ Z – (W, В)

2) Pseudo-transitivity

3) Mixed pseudo-tranisitivity

If А →→ В and (А,В) →→ С, then А →→ (С - В)

4) Intersection and difference

If А →→ В and А →→ С, then А →→ В ∩ С, А →→ В – С, А →→ С – В

is in fourth normal form (4NF), if from existence of

Assertion. Lets relation R consists of attributes (set of attributes) А, В, С. Dependence А →→ В exist in R if and only if R = R[A, B] * R[A, C].

reduction to the 4NF. Lets given relation R with attributes

Multivalued dependency is embeded if it is absent in the relation but exists in the projection of the relation by some attributes.

Form (5NF)
Lets R is a relation with attributes (set of

JD is trivial if one of Ai is equal to the list of all attributes of the relation R.

A join dependency is implied by the candidate keys of R if each of Ai (1 ≤ i ≤ n) are superkeys of R.

the form *(A, B) in relation with schema R(A,B), where

In the example to the left relation contains JD *((A,B), (B, C), (A,C)). It may be verified by calculating: πA1(R) * πA2(R) *... * πAn(R) .
But it does not contain any nontrivial MVD.

It may be convinced by testing that no one of the following multi-valued dependency exist:
A →→B, A →→C, B →→A, B →→C, C →→A,C →→B.

is in the fifth normal form (5NF) if and only

This normal form is also called project-join normal form (PJNF).

Assertion. Because of any multivalued dependency is also join dependency, any relation in PJNF (5NF) is also in 4NF .

Classic example to motivate 5NF involves a join n-way decomposition that cannot be derived by a sequence of 2-way decompositions

the is a relation TBS(TCH, BOK, SBJ), where we record

what teaches what books are used;

what books in what subjects are used;

what subjects by what teachers are taught.

The fact that the relation contains the following information:

Reznichenko uses in his lectures the book «SQL language»,

The book «SQL language» is used in the subject DB&KB» and

Reznihcenko has lectures by subject DB&KB.

Does not mean that «Reznichenko uses the book ”SQL Language” in his lectures by subject DB&KB»

Relation TBS is in 5NF because it do not have JDs.

and reduction it to the 5NF
If relation TBS has additional

then relation TBS has JD *((TCH, BOK), (BOK, SBJ), (TCH, SBJ)) and this relation is not in 5NF because it has the only candidate key that coincide with all attributes of the relation, that is (TCH, BOK, SUBJ).

In this case relation TBS reduces to 5NF in such a way:

«From the facts:
- teacher t uses in his lectures book b,
- book b is used in subject s and
- teacher t has lectures by subject s
follows that teacher t uses book b in lectures by subject s»,

TBS(TCH, BOK, SBJ) ⇒TB(TCH,BOK), BS(BOK, SBJ), TS(TCH, SBJ)

and reduction it to the 4NF
If relation TBS has additional

Then relation TBS has JD *((TCH, BOK), (TCH, SBJ)) or it is the same as the relation has the following MVDs TCH →→ BOK, TCH →→ SBJ, and this relation neither in 5NF nor in 4NF.
In this case TBS reduces to the 4NF (and more over to the 5NF) in such a way:

«From the facts:
- teacher t uses in his lectures book b,
- teacher t has lectures by subject s
follows that teacher t uses book b in lectures by subject s»,

TBS(TCH, BOK, SBJ) ⇒TB(TCH,BOK), TS(TCH, SBJ)

the relational schema design task
Decomposition of the relational schema
Equivalence

task
In this definition it is necessary to clarify the following

Thesis of universal relation. All application domain may be represented as one universal relation that contains all attributes of the domain.

Formal definition of the design task. Lets given relational schema S0, that contains schema of the only (universal) relation R:
S0 = {R = }, where U – set of attributes, а G – set of dependencies, It is necessary to find equivalent relational schema SD, represented as the set of relations R1,…, Rn:
SD = {Ri = , i = 1, 2, ..., n},
that should be better in any sense that schema S0.

that decomposition has the property of looseless join, if R

Decomposition is the only operation that is used while splitting relational schemas

Decomposition relation R(M) with set of attributes M into the set of relations R1, R2,…, Rn with attributes M1, MA2,…, Mn is a procedure that satisfy the following conditions:
М1 ∪ М2 ∪ … ∪ Мn = М. That is any attribute of R belongs at least one of relation Ri and all attributes of Ri should be defined in R .
All relations Ri, i = 1, 2,..., n, are projections of the relation R over attributes that are contained in the Ri, that is Ri(Mi) = πMi(R)

dependencies. Two sets of the relations are equivalent by dependencies,

Formally, lets given two schemas S0 and SD, that was defined previously. They are equivalent by dependencies if:

Where U, Ui are attributes of the schemas S0 and SD: and G, Gi are dependencies of S0 and SD.

data. Two sets of relations equivalent by data if natural

If source and resulting schemas are S0 and SD, equivalence by data means that splitting of the relation is done by using loosless decomposition.
How does loosless decomposition may be achived?

Assretion. If R1(U1) R2(U2) are decomposition of R(U) that preserve functional and/or multivalued dependencies, then this decomposition provides lossless join if and only if: U1 ∩ U2 → (or →→) U1 – U2
OR
U1 ∩ U2 → (or →→) U2 – U1

join not always guarantee dependency preservation.
At the same time

Equivalence of the normal forms.
Decomposition of the universal relation up to the 3NF preserve equivalence by data and dependencies.
Converting universal relation to the BCNF preserve equivalence by data but not preserve equivalence by dependencies.

us consider how can we estimate the schema quality: that