Relational Database Design (Normalization

Relational Database Design

• Features of Good Relational Design
• Atomic Domains and First Normal Form
• Decomposition Using Functional Dependencies
• Functional Dependency Theory
• Algorithms for Functional Dependencies
• Decomposition Using Multivalued Dependencies
• More Normal Form
• Database-Design Process
• Modeling Temporal Data

Why is Database Normalization Important?�

Normalization helps a database designer optimally distribute attributes into tables. The technique eliminates the following:

• Attributes with multiple values.
• Doubled or repeated attributes.
• Non-descriptive attributes.
• Attributes with redundant information.
• Attributes created from other features.

Although total database normalization is not necessary, it provides a well-functioning information environment.

The method systematically ensures:

• A database structure suitable for generalized queries.
• Minimized data redundancy, increasing memory efficiency on a database server.
• Maximized data integrity through the reduced insert, update, and delete anomalies.

Database normalization transforms overall database consistency, providing an efficient environment.

The Banking Schema

• branch = (branch_name, branch_city, assets)
• customer = (customer_id, customer_name, customer_street, customer_city)
• loan = (loan_number, amount)
• account = (account_number, balance)
• employee = (employee_id. employee_name, telephone_number, start_date)
• dependent_name = (employee_id, dname)
• account_branch = (account_number, branch_name)
• loan_branch = (loan_number, branch_name)
• borrower = (customer_id, loan_number)
• depositor = (customer_id, account_number)
• cust_banker = (customer_id, employee_id, type)
• works_for = (worker_employee_id, manager_employee_id)
• payment = (loan_number, payment_number, payment_date, pay_amount)
• savings_account = (account_number, interest_rate)
• checking_account = (account_number, overdraft_amount)

​

Combine Schemas?

• Suppose we combine borrower and loan to get
• bor_loan = (customer_id, loan_number, amount )
• Result is possible repetition of information (L-100 in example below)

​

A Combined Schema Without Repetition

• Consider combining loan_branch and loan

loan_amt_br = (loan_number, amount, branch_name)

• No repetition (as suggested by example below)

What About Smaller Schemas?

• Suppose we had started with bor_loan. How would we know to split up (decompose) it into borrower and loan?
• Write a rule “if there were a schema (loan_number, amount), then loan_number would be a candidate key”
• Denote as a functional dependency:
• loan_number → amount
• In bor_loan, because loan_number is not a candidate key, the amount of a loan may have to be repeated. This indicates the need to decompose bor_loan.
• Not all decompositions are good. Suppose we decompose employee into
• employee1 = (employee_id, employee_name)
• employee2 = (employee_name, telephone_number, start_date)
• If we cannot reconstruct the original employee relation -- a lossy decomposition.

​

​

A Lossy Decomposition

• Database normalization is the process of organizing data into tables in such a way that the results of using the database are always unambiguous and as intended.
• This involves restructuring the tables to successively meeting higher forms of Normalization.
• A properly normalized database should have the following characteristics
• Scalar values in each fields
• Absence of redundancy.
• Minimal use of null values.
• Minimal loss of information.

Definition Normalization

• Levels of normalization based on the amount of redundancy in the database.
• Various levels of normalization are:
• 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)
• Domain Key Normal Form (DKNF)

Levels of Normalization

Redundancy

Number of Tables

Most databases should be 3NF or BCNF in order to avoid the database anomalies.

Complexity

Levels of Normalization

Each higher level is a subset of the lower level

DKNF

First Normal Form

• Domain is atomic if its elements are considered to be indivisible units
• Examples of non-atomic domains:
• Set of names, composite attributes
• Identification numbers like CS101 that can be broken up into parts
• A relational schema R is in first normal form if the domains of all attributes of R are atomic
• Non-atomic values complicate storage and encourage redundant (repeated) storage of data
• Example: Set of accounts stored with each customer, and set of owners stored with each account.

First Normal Form (Cont’d)

• Atomicity is actually a property of how the elements of the domain are used.
• Example: Strings would normally be considered indivisible
• Suppose that students are given roll numbers which are strings of the form CS0012 or EE1127
• If the first two characters are extracted to find the department, the domain of roll numbers is not atomic.
• Doing so is a bad idea: leads to encoding of information in application program rather than in the database.

A table is considered to be in 1NF if all the fields contain

only scalar values (as opposed to list of values).

Example (Not 1NF)

First Normal Form (1NF) Example

Author and AuPhone columns are not scalar

1. Place all items that appear in the repeating group in a new table
2. Designate a primary key for each new table produced.
3. Duplicate in the new table the primary key of the table from which the repeating group was extracted or vice versa.

Example (1NF)

1NF - Decomposition-Example

Goal — Devise a Theory for the Following

• Decide whether a particular relation R is in “good” form.
• Ifa relation R is not in “good” form, decompose it into a set of relations {R₁, R₂, ..., R_n} such that
• each relation is in good form
• the decomposition is a lossless-join decomposition
• Normalization theory is based on:
• Informal Design Guidelines for Relational Databases
• Semantics of the Relation Attributes
• Redundant Information in Tuples and Update Anomalies
• Null Values in Tuples
• Spurious Tuples
• functional dependencies
• multivalued dependencies

1.1 Semantics of the Relation Attributes

GUIDELINE 1: Informally, each tuple in a relation should represent one entity or relationship instance. (Applies to individual relations and their attributes).

• Attributes of different entities (EMPLOYEEs, DEPARTMENTs, PROJECTs) should not be mixed in the same relation
• Only foreign keys should be used to refer to other entities
•  Entity and relationship attributes should be kept apart as much as possible.

Bottom Line: Design a schema that can be explained easily relation by relation. The semantics of attributes should be easy to interpret.

17

1.2 Redundant Information in Tuples and Update Anomalies

• Mixing attributes of multiple entities may cause problems
• Information is stored redundantly wasting storage
• Problems with update anomalies
• Insertion anomalies
• Deletion anomalies
• Modification anomalies

20

EXAMPLE OF AN UPDATE ANOMALY (1)

Consider the relation:

EMP_PROJ ( Emp#, Proj#, Ename, Pname, No_hours)

• Update Anomaly: Changing the name of project number P1 from “Billing” to “Customer-Accounting” may cause this update to be made for all 100 employees working on project P1.

21

Figure: Two relation schemas suffering from update anomalies

Figure: Example States for EMP_DEPT and EMP_PROJ

Guideline to Redundant Information in Tuples and Update Anomalies

• GUIDELINE 2: Design a schema that does not suffer from the insertion, deletion and update anomalies. If there are any present, then note them so that applications can be made to take them into account

1.3 Null Values in Tuples

GUIDELINE 3: Relations should be designed such that their tuples will have as few NULL values as possible

•  Attributes that are NULL frequently could be placed in separate relations (with the primary key)
•  Reasons for nulls:
• attribute not applicable or invalid
• attribute value unknown (may exist)
• value known to exist, but unavailable

1.4 Spurious Tuples

• Bad designs for a relational database may result in erroneous results for certain JOIN operations
• The "lossless join" property is used to guarantee meaningful results for join operations

GUIDELINE 4: The relations should be designed to satisfy the lossless join condition. No spurious tuples should be generated by doing a natural-join of any relations.

​

 There are two important properties of decompositions:

1. non-additive or losslessness of the corresponding join
2. preservation of the functional dependencies.

​

Note that property (a) is extremely important and cannot be sacrificed. Property (b) is less stringent and may be sacrificed.

Functional Dependencies

• Constraints that describes relationships between attributes on the set of legal relations.
• Require that the value for a certain set of attributes determines uniquely the value for another set of attributes.
• A functional dependency is a generalization of the notion of a key.

• Let R be a relation schema α ⊆ R and β ⊆ R
• The functional dependency α → β�holds on R if and only if for any legal relations r(R), whenever any two tuples t₁ and t₂ of r agree on the attributes α, they also agree on the attributes β. That is,

t₁[α] = t₂ [α] ⇒ t₁[β ] = t₂ [β ]

• Example: Consider r(A,B ) with the following instance of r.

​

​

​

• On this instance, A → B does NOT hold, but B → A does hold.

1. 4

1 5

3 7

1. If one set of attributes in a table determines another set of attributes in the table, then the second set of attributes is said to be functionally dependent on the first set of attributes.

​

Example 1

Functional Dependencies

Table Scheme: {ISBN, Title, Price}

Functional Dependencies: {ISBN} 🡪 {Title}

{ISBN} 🡪 {Price}

Example 2

Functional Dependencies

Table Scheme:{PubID,PubName,PubPhone}

Functional Dependencies:

{PubId} 🡪 {PubPhone}

{PubId} 🡪 {PubName}

{PubName, PubPhone} 🡪 {PubID}

Example 3

Table Scheme:

{AuID, AuName, AuPhone}

Functional Dependencies:

{AuId} 🡪 {AuPhone}

{AuId} 🡪 {AuName}

{AuName, AuPhone} 🡪 {AuID}

Database to track reviews of papers submitted to an academic conference. Prospective authors submit papers for review and possible acceptance in the published conference proceedings. Details of the entities

• Author information includes a unique author number, a name, a mailing address, and a unique (optional) email address.
• Paper information includes the primary author, the paper number, the title, the abstract, and review status (pending, accepted,rejected)
• Reviewer information includes the reviewer number, the name, the mailing address, and a unique (optional) email address
• A completed review includes the reviewer number, the date, the paper number, comments to the authors, comments to the program chairperson, and ratings (overall, originality, correctness, style, clarity)

FD – Example

Functional Dependencies

• AuthNo 🡪 AuthName, AuthEmail, AuthAddress
• AuthEmail 🡪 AuthNo
• PaperNo 🡪 Primary-AuthNo, Title, Abstract, Status
• RevNo 🡪 RevName, RevEmail, RevAddress
• RevEmail 🡪 RevNo
• RevNo, PaperNo 🡪 AuthComm, Prog-Comm, Date, Rating1, Rating2, Rating3, Rating4, Rating5

FD – Example

Inference Rules For FDs

Inference Rules For FDs

For a table to be in 2NF,

• The database is in first normal form
• All nonkey attributes in the table must be functionally dependent on the entire primary key

(No non prime attribute is dependent on the proper subset of any candidate key of the table)

Note: Remember that we are dealing with non-key attributes

​

Example 1 (Not 2NF)

Scheme 🡪 {Title, PubId, AuId, Price, AuAddress}

• Key 🡪 {Title, PubId, AuId}
• {Title, PubId, AuID} 🡪 {Price}
• {AuID} 🡪 {AuAddress}
• AuAddress does not belong to a key
• AuAddress functionally depends on AuId which is a subset of a key

Second Normal Form (2NF)

1. If a data item is fully functionally dependent on only a part of the primary key, move that data item and that part of the primary key to a new table.
2. If other data items are functionally dependent on the same part of the key, place them in the new table also
3. Make the partial primary key copied from the original table the primary key for the new table. Place all items that appear in the repeating group in a new table

Example 1 (Convert to 2NF)

Old Scheme 🡪 {Title, PubId, AuId, Price, AuAddress}

New Scheme 🡪 {Title, PubId, AuId, Price}

New Scheme 🡪 {AuId, AuAddress}

2NF - Decomposition

Example 2 (Not 2NF)

Scheme 🡪 {City, Street, HouseNumber, HouseColor, CityPopulation}

• key 🡪 {City, Street, HouseNumber}
• {City, Street, HouseNumber} 🡪 {HouseColor}
• {City} 🡪 {CityPopulation}
• CityPopulation does not belong to any key.
• CityPopulation is functionally dependent on the City which is a proper subset of the key

​

Example 3 (Not 2NF)

Scheme 🡪 {studio, movie, budget, studio_city}

• Key 🡪 {studio, movie}
• {studio, movie} 🡪 {budget}
• {studio} 🡪 {studio_city}
• studio_city is not a part of a key
• studio_city functionally depends on studio which is a proper subset of the key

​

Second Normal Form (2NF)

Example 2 (Convert to 2NF)

Old Scheme 🡪 {Studio, Movie, Budget, StudioCity}

New Scheme 🡪 {Movie, Studio, Budget}

New Scheme 🡪 {Studio, City}

​

Example 3 (Convert to 2NF)

Old Scheme 🡪 {City, Street, HouseNumber, HouseColor, CityPopulation}

New Scheme 🡪 {City, Street, HouseNumber, HouseColor}

New Scheme 🡪 {City, CityPopulation}

​

2NF - Decomposition

This form dictates that all non-key attributes of a table must be functionally dependent on a candidate key i.e. there can be no interdependencies among non-key attributes.

​

For a table to be in 3NF, there are two requirements

• The table should be second normal form
• No attribute is transitively dependent on the primary key

​

Example (Not in 3NF)

Scheme 🡪 {Title, PubID, PageCount, Price }

• Key 🡪 {Title, PubId}
• {Title, PubId} 🡪 {PageCount}
• {PageCount} 🡪 {Price}
• Both Price and PageCount depend on a key hence 2NF
• Transitively {Title, PubID} 🡪 {Price} hence not in 3NF

Third Normal Form (3NF)

1. Move all items involved in transitive dependencies to a new entity.
2. Identify a primary key for the new entity.
3. Place the primary key for the new entity as a foreign key on the original entity.

Example 1 (Convert to 3NF)

Old Scheme 🡪 {Title, PubID, PageCount, Price }

New Scheme 🡪 {PubID, PageCount, Price}

New Scheme 🡪 {Title, PubID, PageCount}

3NF - Decomposition

Example 2 (Not in 3NF)

Scheme 🡪 {Studio, StudioCity, CityTemp}

• Primary Key 🡪 {Studio}
• {Studio} 🡪 {StudioCity}
• {StudioCity} 🡪 {CityTemp}
• {Studio} 🡪 {CityTemp}
• Both StudioCity and CityTemp depend on the entire key hence 2NF
• CityTemp transitively depends on Studio hence violates 3NF

​

Example 3 (Not in 3NF)

Scheme 🡪 {BuildingID, Contractor, Fee}

• Primary Key 🡪 {BuildingID}
• {BuildingID} 🡪 {Contractor}
• {Contractor} 🡪 {Fee}
• {BuildingID} 🡪 {Fee}
• Fee transitively depends on the BuildingID
• Both Contractor and Fee depend on the entire key hence 2NF

Third Normal Form (3NF)

Example 2 (Convert to 3NF)

Old Scheme 🡪 {Studio, StudioCity, CityTemp}

New Scheme 🡪 {Studio, StudioCity}

New Scheme 🡪 {StudioCity, CityTemp}

Example 3 (Convert to 3NF)

Old Scheme 🡪 {BuildingID, Contractor, Fee}

New Scheme 🡪 {BuildingID, Contractor}

New Scheme 🡪 {Contractor, Fee}

​

3NF - Decomposition

Third Normal Form Definition

• A relation schema R is in third normal form (3NF) if for all:

α → β in F^+�at least one of the following holds:

• α → β is trivial (i.e., β ∈ α)
• α is a superkey for R
• Each attribute A in β – α is contained in a candidate key for R.

(NOTE: each attribute may be in a different candidate key)

• If a relation is in BCNF it is in 3NF (since in BCNF one of the first two conditions above must hold).
• Third condition is a minimal relaxation of BCNF to ensure dependency preservation.

​

• BCNF does not allow dependencies between attributes that belong to candidate keys.
• BCNF is a refinement of the third normal form in which it drops the restriction of a non-key attribute from the 3rd normal form.
• Third normal form and BCNF are not same if the following conditions are true:
• The table has two or more candidate keys
• At least two of the candidate keys are composed of more than one attribute
• The keys are not disjoint i.e. The composite candidate keys share some attributes

​

Boyce-Codd Normal Form (BCNF)

Example 1 - Address (Not in BCNF)

Scheme 🡪 {City, Street, ZipCode }

• Key1 🡪 {City, Street }
• Key2 🡪 {ZipCode, Street}
• No non-key attribute hence 3NF
• {City, Street} 🡪 {ZipCode}
• {ZipCode} 🡪 {City}
• Dependency between attributes belonging to a key

Boyce-Codd Normal Form (BCNF)

1. Place the two candidate primary keys in separate entities
2. Place each of the remaining data items in one of the resulting entities according to its dependency on the primary key.

Example 1 (Convert to BCNF)

Old Scheme 🡪 {City, Street, ZipCode }

New Scheme1 🡪 {ZipCode, Street}

New Scheme2 🡪 {City, Street}

• Loss of relation {ZipCode} 🡪 {City}

Alternate New Scheme1 🡪 {ZipCode, Street }

Alternate New Scheme2 🡪 {ZipCode, City}

1. If decomposition does not cause any loss of information it is called a lossless decomposition.
2. If a decomposition does not cause any dependencies to be lost it is called a dependency-preserving decomposition.
3. Any table scheme can be decomposed in a lossless way into a collection of smaller schemas that are in BCNF form. However the dependency preservation is not guaranteed.
4. Any table can be decomposed in a lossless way into 3^rd normal form that also preserves the dependencies.
• 3NF may be better than BCNF in some cases

​

​

Decomposition – Loss of Information

Use your own judgment when decomposing schemas

Example 2 - Movie (Not in BCNF)

Scheme 🡪 {MovieTitle, MovieID, PersonName, Role, Payment }

• Key1 🡪 {MovieTitle, PersonName}
• Key2 🡪 {MovieID, PersonName}
• Both role and payment functionally depend on both candidate keys thus 3NF
• {MovieID} 🡪 {MovieTitle}
• Dependency between MovieID & MovieTitle Violates BCNF

​

Example 3 - Consulting (Not in BCNF)

Scheme 🡪 {Client, Problem, Consultant}

• Key1 🡪 {Client, Problem}
• Key2 🡪 {Client, Consultant}
• No non-key attribute hence 3NF
• {Client, Problem} 🡪 {Consultant}
• {Client, Consultant} 🡪 {Problem}
• Dependency between attributess belonging to keys violates BCNF

Boyce Codd Normal Form (BCNF)

Example 2 (Convert to BCNF)

Old Scheme 🡪 {MovieTitle, MovieID, PersonName, Role, Payment }

New Scheme 🡪 {MovieID, PersonName, Role, Payment}

New Scheme 🡪 {MovieTitle, PersonName}

• Loss of relation {MovieID} 🡪 {MovieTitle}

New Scheme 🡪 {MovieID, PersonName, Role, Payment}

New Scheme 🡪 {MovieID, MovieTitle}

• We got the {MovieID} 🡪 {MovieTitle} relationship back

Example 3 (Convert to BCNF)

Old Scheme 🡪 {Client, Problem, Consultant}

New Scheme 🡪 {Client, Consultant}

New Scheme 🡪 {Client, Problem}

​

BCNF - Decomposition

Comparison of BCNF and 3NF

• It is always possible to decompose a relation into a set of relations that are in 3NF such that:
• the decomposition is lossless
• the dependencies are preserved
• It is always possible to decompose a relation into a set of relations that are in BCNF such that:
• the decomposition is lossless
• it may not be possible to preserve dependencies.

​

Example of BCNF Decomposition

• R = (A, B, C )�F = {A → B� B → C}�Key = {A}
• R is not in BCNF (B → C but B is not superkey)
• Decomposition
• R₁ = (B, C)
• R₂ = (A,B)

​

Example of BCNF Decomposition

• Original relation R and functional dependency F

R = (branch_name, branch_city, assets,

customer_name, loan_number, amount )

F = {branch_name → assets branch_city

loan_number → amount branch_name }

Key = {loan_number, customer_name}

• Decomposition
• R₁ = (branch_name, branch_city, assets )
• R₂ = (branch_name, customer_name, loan_number, amount )
• R₃ = (branch_name, loan_number, amount )
• R₄ = (customer_name, loan_number )
• Final decomposition � R₁, R₃, R₄

• Fourth normal form eliminates independent many-to-one relationships between columns.
• To be in Fourth Normal Form,
• a relation must first be in Boyce-Codd Normal Form. 
• a given relation may not contain more than one multi-valued attribute.

​

​

Fourth Normal Form (4NF)

​

• Definition:
• A relation schema R is in 4NF with respect to a set D of functional and multivalued dependencies if for all multivalued dependencies in D⁺ of the form α →→ β, where α ⊆ R and β ⊆ R, at least one of the following hold:
• α →→ β is trivial (i.e., β ⊆ α or α ∪ β = R)
• α is a superkey for schema R

MVD (Cont.)

• Tabular representation of α →→ β

• Let R be a relation schema and let α ⊆ R and β ⊆ R. The multivalued dependency

α →→ β

holds on R if in any legal relation r(R), for all pairs for tuples t₁ and t₂ in r such that t₁[α] = t₂ [α], there exist tuples t₃ and t₄ in r such that:

t₁[α] = t₂ [α] = t₃ [α] = t₄ [α] � t₃[β] = t₁ [β] � t₃[R – β] = t₂[R – β] � t₄ [β] = t₂[β] � t₄[R – β] = t₁[R – β] �

Example (Not in 4NF)

Scheme 🡪 {MovieName, ScreeningCity, Genre)

Primary Key: {MovieName, ScreeningCity, Genre)

• All columns are a part of the only candidate key, hence BCNF
• Many Movies can have the same Genre
• Many Cities can have the same movie
• Violates 4NF

​

​

Fourth Normal Form (4NF)

​

Example 2 (Not in 4NF)

Scheme 🡪 {Manager, Child, Employee}

• Primary Key 🡪 {Manager, Child, Employee}
• Each manager can have more than one child
• Each manager can supervise more than one employee
• 4NF Violated

​

Example 3 (Not in 4NF)

Scheme 🡪 {Employee, Skill, ForeignLanguage}

• Primary Key 🡪 {Employee, Skill, Language }
• Each employee can speak multiple languages
• Each employee can have multiple skills
• Thus violates 4NF

​

Fourth Normal Form (4NF)

1. Move the two multi-valued relations to separate tables
2. Identify a primary key for each of the new entity.

​

Example 1 (Convert to 3NF)

Old Scheme 🡪 {MovieName, ScreeningCity, Genre}

New Scheme 🡪 {MovieName, ScreeningCity}

New Scheme 🡪 {MovieName, Genre}

4NF - Decomposition

Example 2 (Convert to 4NF)

Old Scheme 🡪 {Manager, Child, Employee}

New Scheme 🡪 {Manager, Child}

New Scheme 🡪 {Manager, Employee}

​

Example 3 (Convert to 4NF)

Old Scheme 🡪 {Employee, Skill, ForeignLanguage}

New Scheme 🡪 {Employee, Skill}

New Scheme 🡪 {Employee, ForeignLanguage}

​

4NF - Decomposition

• Fifth normal form is satisfied when all tables are broken into as many tables as possible in order to avoid redundancy.
• Once it is in fifth normal form it cannot be broken into smaller relations without changing the facts or the meaning. 
• Fifth normal form is also called as project-join normal form (PJNF)

​

​

Fifth Normal Form (5NF)

​

• The relation is in DKNF when there can be no insertion or deletion anomalies in the database.

​

Domain Key Normal Form (DKNF)

​

Conversion to First Normal Form (continued)

Conversion to Second Normal Form (continued)

Conversion to Third Normal Form (continued)

The Boyce-Codd Normal Form (BCNF) (continued)

Example Multivalued FD and Normalization to 4^Th Normal Form

• R =(A, B, C, G, H, I)

F ={ A →→ B

B →→ HI

CG →→ H }

• R is not in 4NF since A →→ B and A is not a superkey for R
• Decomposition

a) R₁ = (A, B) (R₁ is in 4NF)

b) R₂ = (A, C, G, H, I) (R₂ is not in 4NF)

c) R₃ = (C, G, H) (R₃ is in 4NF)

d) R₄ = (A, C, G, I) (R₄ is not in 4NF)

• Since A →→ B and B →→ HI, A →→ HI, A →→ I

e) R₅ = (A, I) (R₅ is in 4NF)

f)R₆ = (A, C, G) (R₆ is in 4NF)

• https://phoenixnap.com/kb/database-normalization
• https://www.geeksforgeeks.org/difference-between-lossless-and-lossy-join-decomposition/