DataBaseManagement System

​

​

​

​

​

​

Dr.S.Sivakumar,Principal

C.P.A College, Bodinayakanur

1

Normalization

• Normalization theory is based on the observation that relations with certain properties are more effective in inserting, updating and deleting data than other sets of relations containing the same data
• Normalization is a multi-step process beginning with an “unnormalized”relation
• Hospital example from Atre, S. Data Base: Structured Techniques for Design, Performance, and Management.

Normal Forms

• First Normal Form (1NF)
• Second Normal Form (2NF)
• Third Normal Form (3NF)
• Boyce-Codd Normal Form (BCNF)
• Fourth Normal Form (4NF)
• Fifth Normal Form (5NF)

Normalization

Functional Dependencies

• Functional dependencies (FDs) are used to specify formal measures of the "goodness" of relational designs
• FDs and keys are used to define normal forms for relations
• FDs are constraints that are derived from the meaning and interrelationships of the data attributes

​

Functional Dependency

• A set of attributes X functionally determines a set of attributes Y if the value of X determines a unique value for Y
• X 🡪Y holds if whenever two tuples have the same value for X, they must have the same value for Y

If t1[X]=t2[X], then t1[Y]=t2[Y] in any relation instance r(R)

• X 🡪 Y in R specifies a constraint on all relation instances r(R)
• FDs are derived from the real-world constraints on the attributes

Examples of FD constraints

• Social Security Number determines employee name

SSN 🡪 ENAME

• Project Number determines project name and location

PNUMBER 🡪 {PNAME, PLOCATION}

• Employee SSN and project number determines the hours per week that the employee works on the project

{SSN, PNUMBER} 🡪 HOURS

​

Functional Dependencies and Keys

• An FD is a property of the attributes in the schema R 
• The constraint must hold on every relation instance r(R)
•  If K is a key of R, then K functionally determines all attributes in R (since we never have two distinct tuples with t1[K]=t2[K])

​

Inference Rules for FDs

• Given a set of FDs F, we can infer additional FDs that hold whenever the FDs in F hold
• Armstrong's inference rules

A1. (Reflexive) If Y subset-of X, then X 🡪 Y

A2. (Augmentation) If X 🡪 Y, then XZ 🡪 YZ

(Notation: XZ stands for X U Z)

A3. (Transitive) If X 🡪 Y and Y 🡪 Z, then X 🡪 Z

• A1, A2, A3 form a sound and complete set of inference rules

Additional Useful Inference Rules

• Decomposition
• If X 🡪 YZ, then X 🡪 Y and X 🡪 Z
• Union
• If X 🡪 Y and X 🡪 Z, then X 🡪 YZ
• Psuedotransitivity
• If X 🡪 Y and WY 🡪 Z, then WX 🡪 Z
• Closure of a set F of FDs is the set F+ of all FDs that can be inferred from F

Introduction to Normalization

• Normalization: Process of decomposing unsatisfactory "bad" relations by breaking up their attributes into smaller relations
• Normal form: Condition using keys and FDs of a relation to certify whether a relation schema is in a particular normal form
• 2NF, 3NF, BCNF based on keys and FDs of a relation schema
• 4NF based on keys, multi-valued dependencies

Unnormalized Relations

• First step in normalization is to convert the data into a two-dimensional table
• In unnormalized relations data can repeat within a column

Unnormalized Relation

First Normal Form

• To move to First Normal Form a relation must contain only atomic values at each row and column.
• No repeating groups
• A column or set of columns is called a Candidate Key when its values can uniquely identify the row in the relation.

​

IS 257 – Fall 2008

First Normal Form

1NF Storage Anomalies

• Insertion: A new patient has not yet undergone surgery -- hence no surgeon # -- Since surgeon # is part of the key, we cannot insert.
• Insertion: If a surgeon is newly hired and has not operated yet -- there will be no way to include that person in the database.
• Update: If a patient comes in for a new procedure, and has moved, we need to change multiple address entries.
• Deletion (type 1): Deleting a patient record may also delete all info about a surgeon.
• Deletion (type 2): When there are functional dependencies (like side effects and drug) changing one item eliminates other information.

Second Normal Form

• A relation is said to be in Second Normal Form when every non-key attribute is fully functionally dependent on the primary key.
• That is, every non-key attribute needs the full primary key for unique identification

Why is this not in 2NF?

Second Normal Form

Second Normal Form

1NF Storage Anomalies Removed

• Insertion: Can now enter new patients without surgery.
• Insertion: Can now enter Surgeons who have not operated.
• Deletion (type 1): If Charles Brown dies, the corresponding tuples from Patient and Surgery tables can be deleted without losing information on David Rosen.
• Update: If John White comes in for third time, and has moved, we only need to change the Patient table

2NF Storage Anomalies

• Insertion: Cannot enter the fact that a particular drug has a particular side effect unless it is given to a patient.
• Deletion: If John White receives some other drug because of the penicillin rash, and a new drug and side effect are entered, we lose the information that penicillin can cause a rash
• Update: If drug side effects change (a new formula) we have to update multiple occurrences of side effects.

Third Normal Form

• A relation is said to be in Third Normal Form if there is no transitive functional dependency between non-key attributes
• When one non-key attribute can be determined with one or more non-key attributes there is said to be a transitive functional dependency.
• The side effect column in the Surgery table is determined by the drug administered
• Side effect is transitively functionally dependent on drug so Surgery is not 3NF

Why is this not in 3NF?

Third Normal Form

Third Normal Form

2NF Storage Anomalies Removed

• Insertion: We can now enter the fact that a particular drug has a particular side effect in the Drug relation.
• Deletion: If John White receives some other drug as a result of the rash from penicillin, the information on penicillin and rash is maintained.
• Update: The side effects for each drug appear only once.

Boyce-Codd Normal Form

• Most 3NF relations are also BCNF relations.
• A 3NF relation is NOT in BCNF if:
• Candidate keys in the relation are composite keys (they are not single attributes)
• There is more than one candidate key in the relation, and
• The keys are not disjoint, that is, some attributes in the keys are common

Fourth Normal Form

• Any relation is in Fourth Normal Form if it is BCNF and any multivalued dependencies are trivial
• Eliminate non-trivial multivalued dependencies by projecting into simpler tables

Fifth Normal Form

• A relation is in 5NF if every join dependency in the relation is implied by the keys of the relation
• Implies that relations that have been decomposed in previous normal forms can be recombined via natural joins to recreate the original relation.

Effectiveness and Efficiency Issues for DBMS

• Focus on the relational model
• Any column in a relational database can be searched for values.
• To improve efficiency indexes using storage structures such as BTrees and Hashing are used
• But many useful functions are not indexable and require complete scans of the the database