Normalization: Bottom-Up Design

• This lecture focuses on Normalization
• Normalization involves two approaches in relational database design

Top-Down Design

• This process involves identifying different entity types.
• It also includes defining each entity's attributes.

Bottom-Up Design

• This process defines attributes first.
• It then groups them to form entities.
• This lecture focuses on bottom-up design.
• Normalization is minimizing redundancy from a relation.
• Redundancy causes insertion, deletion, and update anomalies.
• Data redundancy increases database size unnecessarily.
• It is caused by the same data repeated in many places.
• Decomposing relations with anomalies yields smaller, well-structured relations.

Normalization of User View Relations (Bottom-Up Design)

• The first step is representing all user views (forms, reports, etc.) as a collection of relations.
• The next step is normalizing these relations, user view by user view.
• Each view should be broken down into fundamental tables based on normalization principles, aiming for 3NF.
• Finally, combine relations with the same primary key(s).
• This is done because they may represent the same entity.
• Functional Dependency describes attribute interactions.
• Functional dependency is when a simplest kind of dependency.
• Given this LecturereID → LecturerName, all statements are deemed equivalent: - For each LecturerID there should be at most one LecturerNan - LecturerName is determined by LecturerID - LecturerName is uniquely determined by LecturerID - LecturerName depends on LecturerID

Full vs Partial Dependency

• X implies Y ( X → Y ) is a full dependency if no attribute can be removed from X.
• X implies Y ( X → Y ) is a partial dependency if an attribute can be removed from X.
• Both X and Y are subsets of attributes.

Examples of Full vs Partial Dependency

• LecturerID, SubjectCode → LecturerName is partial.
• LecturerName depends partially on LecturerID and SubjectCode.
• LabDate, SubjectCode → Tutor is full
• Tutor is fully dependent on both LabDate and SubjectCode.

Transitive Dependency

• Consider FD X -> Z derived from FDs X -> Y and Y -> Z.
• This is considered a problem with X as the primary key.
• This is only a problem if Y is not a candidate key.

Some Definitions

• Attribute X implying attribute Y (X -> Y) holds if two tuples or rows having the same value across attribute X results in that same value across attribute Y
• "Social security number determines employee name", i.e. SSN -> ENAME
• Means that a table containing social security numbers, the user only needs to use SSN to retrieve the Ename - no other values or fields needed
• Project Number determines both Project Name and Location i.e. Pnumber -> {Pname Plocation}
• This means a table containing the hours an employee works on a project, the user must use the project number to access name and location of the project

Functional dependency

• Employee Social Security Number and Project Number determine the hours per week worked i.e. { SSN, Pnumber} -> Hours
• A table containing employee details would require these two to determine the hours, no other fields or values would work If "given {SSN, Pnumber} -> Ename" then for employee name, this can be determined by either SSN or Pnumber alone which means on of the values is redundant and we can remove this to form the "functional join"

Anomalies

Examples that occur in poorly structured tables If a new subject has no allocated lecturer yet then the details on this subject cannot be added to the table due to an insertion anomaly If an existing Subject has changed title then there is a need to change changes to multiple instances only. A failure to update can cause an update anomaly If a lecturer resigns and has their data deleted then there is a possibility that some subjects will be permanently removed due to a deletion anomaly

Normal Forms

• Design errors in relations can be categorized, including potential anomaly types.
• These categories can be successively eliminated through decomposition into normal forms.
• The major normal forms are:
• First Normal Form (1NF)
• Second Normal Form (2NF)
• Third Normal Form (3NF)
• Boyce-Codd Normal Form (BCNF).
• Higher/advanced forms include Fourth (4NF) and Fifth (5NF).
• Problems with 4NF and 5NF rarely occur.
• Database designers usually focus on satisfying 3NF and BCNF. Satisfying 3NF and BCNF is done since designers don't need the highest possible NF.
• The forms become increasingly stricter and error-free.
• Advanced normal forms are based on complex dependencies

First Normal Form

• A relation is in 1NF if: - There are no repeating groups. - A unique key has been identified for each relation. - All attributes are functionally dependent on all or part of the key.

Second Normal Form

• A relation is in 2NF if: - The relation is in 1NF. - All non-key attributes are fully functionally dependent on the entire key. - All partial dependencies have been removed.

Third Normal Form

• A relation is in 3NF if:
  • The relation is in 2NF.
    • All transitive dependencies have been removed.
    • Transitive dependency: non-key attribute dependent on another non-key attribute.

Boyce-Codd Normal Form

• A relation is in BCNF if: - The relation is in 3NF. - Any remaining functional dependency-related anomalies are removed.

Fourth Normal Form

• A relation is in 4NF if: - The relation is in BCNF. - Any multi-valued dependencies are removed.

Fifth Normal Form

• A relation is in 5NF if: - The relation is in 4NF. - Any remaining join dependency-related anomalies are removed. The standard definition of a relation requires attribute values to be atomic - It should not be a set or compound structure. Relations should have only single value attributes

An Un-Normalized Definition

• Any relation which contains non-atomic attribute values (repeating groups) is considered to be in un-normalized form
• A non BCNF table: There is a rule enforced stating that a given customer can only be served by one salesperson per branch A new model no longer enforces said rule i.e. it's now possible for a customer to now be supported by several salepeople at any particular branch Generic Format: 3NF but not BCNF : r1 { a,b,c such that c will determine B converted BNCF: r11 {a,c} and r12 {c,b}