• Week 08 Tuesday
• Relational Design Theory (recap)
• Normalisation
• Normal Forms
• Relation Decomposition
• Schema (Re)Design
• Boyce-Codd Normal Form
• BCNF Decomposition
• Exercise: BCNF Decomposition (1)
• Exercise: BCNF Decomposition (2)
• Third Normal Form
• Exercise: 3NF Decomposition (1)
• Exercise: 3NF Decomposition (2)
• Database Design Methodology

❖ Week 08 Tuesday

In today's lecture ...

• Dylan's Q & A for Assignment 2
• Relational Design Theory: FDs, Normal Forms, Normalisation

Things to do ...

• Quiz 5 due by 23:59 Friday 7 April
• Assignment 2 due by 23:58 Friday 14 April  (Week 9)

❖ Relational Design Theory (recap)

Schemas with redundancy are prone to update anomalies

ER → SQL mapping tends to give non-redundant schemas

• but does not guarantee no redundancy

Functional dependency gives insights into

• relationships between attributes in a relation
• whether attributes belong in the same relation

The methods we describe in this section

• can remove redundancy in schemas ⇒ eliminate update anomalies

❖ Normalisation

Normalisation: branch of relational theory providing design insights.

Makes use of schema normal forms

• to characterise the level of redundancy in a relational schema

And normalisation algorithms which

• provide mechanisms for transforming schemas to remove redundancy

Normalisation draws heavily on the theory of functional dependencies.

❖ Normal Forms

Normalisation theory defines six normal forms (NFs).

• First,Second,Third Normal Forms (1NF,2NF,3NF) (Codd 1972)
• Boyce-Codd Normal Form (BCNF) (1974)
• Fourth Normal Form (4NF) (Zaniolo 1976, Fagin 1977)
• Fifth Normal Form (5NF) (Fagin 1979)

NF hierarachy:   5NF ⇒ 4NF ⇒ BCNF ⇒ 3NF ⇒ 2NF ⇒ 1NF

1NF allows most redundancy;   5NF allows least redundancy.

We say that "a schema is in xNF", if all of its tables are xNF

For most practical purposes, BCNF (or 3NF) are acceptable NFs.

❖ Normal Forms (cont)

Normal forms:

1NF		all attributes have atomic values we assume this as part of relational model, so every relation schema is in 1NF
2NF		all non-key attributes fully depend on key (i.e. no partial dependencies) avoids much redundancy
3NF BCNF		no attributes dependent on non-key attrs (i.e. no transitive dependencies) avoids most remaining redundancy

❖ Normal Forms (cont)

Boyce-Codd Normal Form (BCNF):

• eliminates all redundancy due to functional dependencies
• but may not preserve original functional dependencies

  (which isn't necessarily a problem, unless FDs capture important semantics)

Third Normal Form (3NF):

• eliminates most (but not all) redundancy due to fds
• guaranteed to preserve all functional dependencies

❖ Normal Forms (cont)

Normalisation aims to puts a schema into xNF

• by ensuring that all relations in the schema are in xNF

How normalisation works ...

• decide which normal form xNF  is "acceptable"
  • i.e. how much redundancy are we willing to tolerate?
• check whether each relation in schema is in xNF
• if a relation is not in xNF
  • partition into sub-relations where each is "closer to" xNF
• repeat until all relations in schema are in xNF

❖ Relation Decomposition

The standard transformation technique to remove redundancy:

• decompose relation R  into relations S  and T

We accomplish decomposition by

• selecting (overlapping) subsets of attributes
• forming new relations based on attribute subsets

Properties:   R = S ∪ T,   S ∩ T ≠ ∅   and   r(R) = s(S) ⋈ t(T)

May require several decompositions to achieve acceptable NF.

Normalisation algorithms tell us how to choose S and T.

❖ Schema (Re)Design

Consider the following relation for BankLoans:

This schema has all of the update anomalies mentioned earlier.

❖ Schema (Re)Design (cont)

To improve the design, decompose the BankLoans relation.

The following decomposition is not helpful:

    Branch(branchName, branchCity, assets)
    CustLoan(custName, loanNo, amount)

because we lose information (which branch is a loan held at?)

Another possible decomposition:

    BranchCust(branchName, branchCity, assets, custName)
    CustLoan(custName, loanNo, amount)

❖ Schema (Re)Design (cont)

The BranchCust relation instance:

❖ Schema (Re)Design (cont)

The CustLoan relation instance:

❖ Schema (Re)Design (cont)

Now consider the result of (BranchCust Join CustLoan)

branchName	branchCity	assets	custName	loanNo	amount
Downtown	Brooklyn	9000000	Jones	L-17	1000
Downtown	Brooklyn	9000000	Jones	L-93	500
Redwood	Palo Alto	2100000	Smith	L-23	2000
Perryridge	Horseneck	1700000	Hayes	L-15	1500
Perryridge	Horseneck	1700000	Hayes	L-16	1300
Downtown	Brooklyn	9000000	Jackson	L-15	1500
Minus	Horseneck	400000	Jones	L-93	500
Minus	Horseneck	400000	Jones	L-17	1000
Round Hill	Horseneck	8000000	Turner	L-11	900
North Town	Rye	3700000	Hayes	L-16	1300
North Town	Rye	3700000	Hayes	L-15	1500

❖ Schema (Re)Design (cont)

This is clearly not a successful decomposition.

The fact that we ended up with extra tuples is symptomatic of losing some critical "connection" information during the decomposition.

Such a decomposition is called a lossy decomposition.

In a good decomposition, we should be able to reconstruct the original relation exactly:

Such a decomposition is called lossless join decomposition.

❖ Boyce-Codd Normal Form

A relation schema R is in BCNF w.r.t a set F of functional dependencies iff:

for all fds X → Y  in F⁺

• either X → Y is trivial (i.e. Y ⊂ X)
• or X  is a superkey   (i.e. non-strict superset of attributes in key)

A DB schema is in BCNF if all of its relation schemas are in BCNF.

Observations:

• any two-attribute relation is in BCNF
• any relation with key K, other attributes Y, and K → Y  is in BCNF

❖ Boyce-Codd Normal Form (cont)

If we transform a schema into BCNF, we are guaranteed:

• no update anomalies due to fd-based redundancy
• lossless join decomposition

However, we are not guaranteed:

• the new schema preserves all fds from the original schema

If we need to preserve dependencies, use 3NF.

A dependency X → Y  is preserved if all of its attributes exist in one table.

Decomposition may e.g. place X  and Y  in separate tables

❖ BCNF Decomposition

The following algorithm converts an arbitrary schema to BCNF:

Inputs: schema R, set F of fds
Output: set Res of BCNF schemas (tables)

Res = {R};
while (any schema S ∈ Res is not in BCNF) {
    choose any fd X → Y on S that violates BCNF
    Res = (Res-S) ∪ (S-Y) ∪ XY
}

The last step means: make a table from XY; drop Y  from table S

The "choose any" step means that the algorithm is non-deterministic

❖ BCNF Decomposition (cont)

Example (the BankLoans schema):

BankLoans(branchName, branchCity, assets, custName, loanNo, amount)

Has functional dependencies F

• branchName → assets,branchCity
• loanNo → amount,branchName

The key for BankLoans is branchName,custName,loanNo

❖ BCNF Decomposition (cont)

Applying the BCNF algorithm:

• check BankLoans relation ... it is not in BCNF
  (branchName → assets,branchCity  violates BCNF criteria; LHS is not a key)
• to fix ... decompose BankLoans  into

      Branch(branchName, branchCity, assets)
      LoanInfo(branchName, custName, loanNo, amount)

• check Branch  relation ... it is in BCNF
  (the only nontrivial fd has LHS=branchName, which is a key)

(continued on next slide)

Notes:

• For Branch: key = branchname,   FDs are branchName → assets,branchCity
• For LoanInfo: key = loanNo,custName,   FDs are loanNo → amount,branchName

❖ BCNF Decomposition (cont)

Applying the BCNF algorithm (cont):

• check LoanInfo relation ... it is not in BCNF
  (loanNo → amount,branchName  violates BCNF criteria; LHS is not a key)
• to fix ... decompose LoanInfo into

      Loan(branchName, loanNo, amount)
      Borrower(custName, loanNo)

• check Loan ... it is in BCNF
• check Borrower ... it is in BCNF

❖ Exercise: BCNF Decomposition (1)

Consider the schema R and set of fds F

R  =  ABCDEFGH

F  =  { ABH → C, A → DE, BGH → F, F → ADH, BH → GE }

Produce a BCNF decomposition of R.

❖ Exercise: BCNF Decomposition (2)

Recall the following table (based on e.g. a spreadsheet):

P#  | When        | Address    | Notes         | S#   | Name  | CarReg
----+-------------+------------+---------------+------+-------+-------
PG4 | 03/06 15:15 | 55 High St | Bathroom leak | SG44 | Rob   | ABK754
PG1 | 04/06 11:10 | 47 High St | All ok        | SG44 | Rob   | ABK754
PG4 | 03/07 12:30 | 55 High St | All ok        | SG43 | Dave  | ATS123
PG1 | 05/07 15:00 | 47 High St | Broken window | SG44 | Rob   | ABK754
PG1 | 05/07 15:00 | 47 High St | Leaking tap   | SG44 | Rob   | ABK754
PG2 | 13/07 12:00 | 12 High St | All ok        | SG42 | Peter | ATS123
...

Recall the functional dependencies identified previously,

Use these to convert the table to a BCNF schema.

❖ Third Normal Form

A relation schema R is in 3NF w.r.t a set F of functional dependencies iff:

for all fds X → Y in F⁺

• either X → Y is trivial (i.e. Y ⊂ X)
• or X is a superkey
• or Y is a single attribute from a key

A DB schema is in 3NF if all relation schemas are in 3NF.

The extra condition represents a slight weakening of BCNF requirements.

❖ Third Normal Form (cont)

If we transform a schema into 3NF, we are guaranteed:

• lossless join decomposition
• the new schema preserves all of the fds from the original schema

However, we are not guaranteed:

• no update anomalies due to fd-based redundancy

Whether to use BCNF or 3NF depends on overall design considerations.

❖ Third Normal Form (cont)

The following algorithm converts an arbitrary schema to 3NF:

Inputs: schema R, set F of fds
Output: set Ri of 3NF schemas

let Fc be a minimal cover for F
Res = {}
for each fd X → Y in Fc {
    if (no schema S ∈ Res contains XY) {
        Res = Res ∪ XY
    }
}
if (no schema S ∈ Res contains a candidate key for R) {
    K = any candidate key for R
    Res = Res ∪ K
}

❖ Third Normal Form (cont)

Critical step is producing minimal cover F_c for F

A set F of fds is minimal if

• every fd X → Y is simple
  (Y is a single attribute)
• every fd X → Y is left-reduced
  (no Z ⊂ X such that Z → A could replace X → A in F and preserve F⁺)
• every fd X → Y is necessary
  (no X → Y can be removed without changing F⁺)

Algorithm: right-reduce, left-reduce, eliminate redundant fds

❖ Exercise: 3NF Decomposition (1)

Consider the schema R and set of fds F

R  =  ABCDEFGH

F  =  F_c  =  { BH → C, A → D, C → E, F → A, E → F, BGH → E }

Produce a 3NF decomposition of R.

❖ Exercise: 3NF Decomposition (2)

Recall the following table (based on e.g. a spreadsheet):

P#  | When        | Address    | Notes         | S#   | Name  | CarReg
----+-------------+------------+---------------+------+-------+-------
PG4 | 03/06 15:15 | 55 High St | Bathroom leak | SG44 | Rob   | ABK754
PG1 | 04/06 11:10 | 47 High St | All ok        | SG44 | Rob   | ABK754
PG4 | 03/07 12:30 | 55 High St | All ok        | SG43 | Dave  | ATS123
PG1 | 05/07 15:00 | 47 High St | Broken window | SG44 | Rob   | ABK754
PG1 | 05/07 15:00 | 47 High St | Leaking tap   | SG44 | Rob   | ABK754
PG2 | 13/07 12:00 | 12 High St | All ok        | SG42 | Peter | ATS123
...

Recall the functional dependencies identified previously,

Use these to convert the table to a 3NF schema.

❖ Database Design Methodology

To achieve a "good" database design:

• identify attributes, entities, relationships   →   ER design
• map ER design to relational schema
• identify constraints (including keys and functional dependencies)
• apply BCNF/3NF algorithms to produce normalised schema

Note: may subsequently need to "denormalise" if the design yields inadequate performance.