Normalization Theory

9 purchases

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

CUSTOMER-PURCHASE

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:

Relation is in the first normal form (1NF) if all it’s attributes are based on atomic (simple) domains and consequently the values in table cells are simple (atomic).
Relation is called normalized if it in first normal form .

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.

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.

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

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 .

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.

This thesis gives formal basis for identifying entities in AD.

Let’s given relation with schema R(A, B, C). Functional dependence R.A → R.B is full if B does not depends functionally from any С ⊂ А that does not contained in B.

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)

CUSTOMER-PURCHASE

Update anomalies. When changing customer city it is necessary to remember that information about customers may be duplicated.
Inset anomalies. When it is necessary to enter information about new customer (Ann) we may do it only when it will do purchase.
Delete anomalies. On deleting information about purchase of Ann we have to delete information about this customer.

Теорема (Хита). 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.

Student card No

Tax ID

Student name

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

А

С

В

В

А

С

DEPARTMENT-FACULTY

DEPARTMENT entities

FACULTY entities

Availability transitive dependencies in a relation means the relation contains information from more that one entity.
As a result such relations imply anomalies of insertion, deletion, updating.

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.

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.

Student

Subject

Teacher

STUDY

Student

Teacher

Teacher

Subject

TEACHING-WHOM

TEACHING-WHAT

NOTE. One of the functional dependence is lost!!!

Assertion. S3NF and BCNF are equivalent

Thesis: If in an application domain there is no direct relationship between attributes A and B, and it is necessary to fix such relationship in one relation, the only correct decision is to determine, that all values of attribute A are related to all values of attribute B, and vise versa.

TEACHING

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

If А →→ В, then А →→ С

2) Augmentation axiom

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

3) Transitivity axiom

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

If А → В, then А →→ В

2) Coalescence axiom

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

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 А →→ В ∩ С, А →→ В – С, А →→ С – В

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].

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

Lets R is a relation with attributes (set of attributes) A1, A2,,.., An. Relation R have join dependency with respect of A1, A2,,.., An, that is denoted as *(A1, A2,…, An), if relation R is equal to natural joins of all of its projections over A1, A2,…, An:
R = πA1(R)*πA2(R)*... * πAn(R) ⇔ R = R[A1] * R[A2]*…*R[An])

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.

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.

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

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.

If relation TBS has additional rule (as a business rule of the application domain):

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)

If relation TBS has additional rule (as a business rule of the application domain):

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)

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.

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)

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.

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

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.