Functional Dependencies and Normalization

CLO 4: Apply normalization forms (1st, 2nd, 3rd, BCNF forms) and functional dependencies to optimize relational model.

Chapter objectives:

 Debate the pros and cons of redundancy in a database.

 Provide examples of update, insertion, and deletion

anomalies.

 Learn all the different types of Normal Forms (1, 2, 3,

st nd rd

and BCNF)

 Show that a table is/isn’t in 3NF or BCNF.

 Decompose a table into a set of tables that are in 3NF, or

• We first discuss informal guidelines for good relational design
• Then we discuss formal concepts of functional dependencies and normal forms
  • 1NF (First Normal Form)
  • 2NF (Second Normal Form)
  • 3NF (Third Normal Form)
  • BCNF (Boyce-Codd Normal Form)

• 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” means this update must be made for all 100 employees working on project P1.

• Consider the relation: EMP_PROJ(Emp#, Proj#, Ename, Pname, No_hours)
• Insert Anomaly:
  • Cannot insert a project unless an employee is assigned to it.

Conversely

• Cannot insert an employee unless he/she is assigned to a project.

• Consider the relation: EMP_PROJ(Emp#, Proj#, Ename, Pname, No_hours)
• Delete Anomaly:
  • When a project is deleted, it will result in deleting all the employees who work on that project.
  • Alternately, if an employee is the sole employee on a project, deleting that employee would result in deleting the corresponding project.

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

 In some schema designs many attributes may be grouped together

into a “fat” relation.

 If many of the attributes do not apply to all tuples in the relation,

many null values will appear in those tuples.

Problems:

 Space is wasted at the storage level and may lead to the problems

with understanding the meaning of the attributes and with specifying JOIN operations at the logical level.

 The same word NULL is used for multiple interpretations (does not

apply, unknown, known but absent) which compromises the different meanings they may have.

• Bad designs for a relational database may result in erroneous (wrong) results for certain JOIN operations.
• GUIDELINE 4:

Design relation schemas so that they can be joined with equality conditions on attributes that are either primary keys and foreign key in a way that guarantees that no spurious (false) tuples are generated.

Redundancy wastes space and can result in many anomalies.

Anomalies cause redundant work to be done during insertion into and modification of a relation. They may also cause accidental loss of information during a deletion from a relation.

Waste of storage space due to NULLs and difficulty interpreting the meaning of NULL.

Generation of invalid and spurious data during joins on base relations with matched attributes.

A formal tool for analysis of relational schemas that enable us to detect and describe some of the problems discussed earlier in precise form.

Functional dependencies (FDs) are a form of constraint, finding them is part of database design. Used in normalization later.

Informally, if two tuples agree on attributes A1, A2, .., An then they must also agree on attributes B1, B2, .., Bn.

We say: A1, A2, .., An → B1, B2, .., Bn

y

• X → Y holds if whenever two tuples have the same value for X, they must have the same value for Y
  • For any two tuples t1 and t2 in any relation instance r(R): If t1[X]=t2[X], then they must have also t1[Y]=t2[Y]
• X → Y in R specifies a constraint on all relation instances r(R)
• Written as X → Y; can be displayed graphically denoted by the arrow.
• FDs are derived from the real-world constraints on the attributes

• 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

If a constraint on R states that there cannot be more than one tuple with a given X -value in any relation instance r (R )—that is, X is a candidate key of R — this implies that X → Y for any subset of attributes Y of R (because the key constraint implies that no two tuples in any legal state r (R) will have the same value of X ).

If X is a candidate key of R, then X → R.

since we never have two distinct tuples with t1[X]=t2[X].

• An FD is a property of the attributes in the schema R
• The constraint must hold on every relation instance r(R).
• If X → Y in R, this does not say whether or not Y → X in R.
• In X → Y, we refer to X as t he left-hand-side attributes of the FD and Y as the right-hand-side attributes.

• Note that in order to define the FDs, we need to understand the meaning of the attributes involved and the relationship between them.
• An FD is a property of the attributes in the schema R
• Given the instance (population) of a relation, all we can conclude is that an FD may exist between certain attributes.
• What we can definitely conclude is – that certain FDs do not exist because there are tuples that show a violation of those dependencies.

3.1 Normalization of Relations 3.2 Practical Use of Normal Forms 3.3 Definitions of Keys and Attributes Participating in Keys 3.4 First Normal Form 3.5 Second Normal Form 3.6 Third Normal Form

• Normalization: The 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

• Normalization is carried out in practice so that the resulting designs are of high quality and meet the desirable properties
• The practical utility of these normal forms becomes questionable when the constraints on which they are based are hard to understand or to detect
• The database designers need not normalize to the highest possible normal form
  • (usually up to 3NF and BCNF. 4NF rarely used in practice.)
• Denormalization:

Full Dependency Partial Dependency Transitive Dependency

• Does not allow:  composite attributes  multivalued attributes  and their combinations which called nested relations or repeated groups.
• Considered to be part of the definition of a relation
• Most RDBMSs allow only those relations to be defined that are in First Normal Form

To achieve first normal form for multivalued attributes you can either:

1. Remove the attributes that violate 1NF and place them into a separate relation along with the primary key. The primary key of the new relation will be the combination of them.
2. Expand the key so that there will be a separate tuple in the original relation for each vale of the multivalued attributes. This solution has the disadvantage of introducing redundancy in the relation.

To achieve first normal form for nested relations you should remove the nested relation attributes into a new relation along with the primary key. The primary key of the new relation will combine the primary key of the original relation with a candidate key of the nested relation.

• Uses the concepts of FDs, primary key
• Definitions
  • Prime attribute: An attribute that is member of the primary key K
  • Full functional dependency: a FD Y -> Z where removal of any attribute from Y means the FD does not hold any more
• Examples:
  • {SSN, PNUMBER} -> HOURS is a full FD since neither SSN -> HOURS nor PNUMBER -> HOURS hold
  • {SSN, PNUMBER} -> ENAME is not a full FD (it is called a partial dependency) since SSN -> ENAME also holds

• A relation schema R is in second normal form (2NF) if every non-prime attribute A in R is fully functionally dependent on the primary key.
• R can be decomposed into 2NF relations via the process of 2NF normalization or “second normalization”

• Definition:
  • Transitive functional dependency: a FD X → Z that can be derived from two FDs X → Y and Y → Z
• Examples:
  • SSN → DMGRSSN is a transitive FD
    • Since SSN → DNUMBER and DNUMBER → DMGRSSN hold
  • SSN → ENAME is non-transitive
    • Since there is no set of attributes X where SSN → X and X → ENAME

• A relation schema R is in third normal form (3NF) if it is in 2NF and no non-prime attribute A in R is transitively dependent on the primary key
• R can be decomposed into 3NF relations via the process of 3NF normalization
• NOTE:
  • In X -> Y and Y -> Z, with X as the primary key, we consider this a problem only if Y is not a candidate key.
  • When Y is a candidate key, there is no problem with the transitive dependency
  • E.g., Consider EMP (SSN, Emp#, Salary ).
    • Here, SSN -> Emp# -> Salary and Emp# is a candidate key.

• The previous definitions consider the primary key only
• The following more general definitions take into account relations with multiple candidate keys
• Any attribute involved in a candidate key is a prime attribute
• All other attributes are called non-prime attributes.

Consider the relation schema LOTS shown the previous slide, which describes parcels of land for sale in various counties of a state.

Suppose that there are two candidate keys: property_id# and (County_name, Lot#); i.e. lot numbers are unique only within each county but Property_id# numbers are unique across counties for the entire state.

FD1 and FD2 dependencies hold true based on the above two candidate keys.

FD3: County_name → Tax_rate FD4: Area → Price FD3 indicates that the tax rate is fixed for a given county (i.e. does not vary lot by lot) FD4 indicates that the price of a lot is determined by its area regardless of which county it is in.

• A relation schema R is in second normal form (2NF) if every nonprime attribute A in R is not partially dependent on any key of R.
• In Figure 14.12 the FD County_name → Tax_rate violates 2NF.

So second normalization converts LOTS into LOTS1 (Property_id#, County_name, Lot#, Area, Price) LOTS2 (County_name, Tax_rate)

From the definition: A relation schema R is in third normal form (3NF) if whenever a FD X → A holds in R, then either:

a) X is a superkey of R, or b) A is a prime attribute of R

• Condition (a) catches two types of violations:
  • A nonprime attribute determines another nonprime attribute. Here we typically have a transitive dependency that violates 3NF.
  • A proper subset of a key of R functionally determines a nonprime attribute. Here we have a partial dependency that violates 2NF.

Thus, condition (a) alone addresses the problematic dependencies that were causes for second and third normalization as we discussed.

When a relation has more than one candidate key, anomalies may result even though the relation is in 3NF.

3NF does not deal satisfactorily with the case of a relation with overlapping candidate keys i.e. composite candidate keys with at least one attribute in common.

BCNF is based on the concept of a determinant.

A determinant is any attribute (simple or composite) on which some other attribute is fully functionally dependent.

A relation is in BCNF, if and only if, every determinant is a candidate key.

Suppose there are thousands of lots in the relation but the lots are from only two counties: DeKalb and Fulton.

Suppose also the lot sizes in DelKab County are only 0.5,0.6, 0.7, 0.8, 0.9 and 1.0 acres, whereas lot sizes in Fulton County are restricted to 1.1, 1.2, ....1.9, 2.0 acres.

In such as situation, the additional functional dependency

FD5: Area → County_name

By adding FD5 to LOTS1A, the relation is still in 3NF because County_name is a prime attribute.

• Two FDs exist in the relation TEACH:
  • fd1: {student, course} -> instructor
  • fd2: instructor -> course
• {student, course} is a candidate key for this relation and that the dependencies shown follow the pattern in Figure 14.13 (b).
  • So this relation is in 3NF but not in BCNF
• A relation NOT in BCNF should be decomposed to meet this property, while possibly forgoing the preservation of all functional dependencies in the decomposed relations.

Decomposition of this relation schema into two schemas is not straightforward because it may be decomposed into one of the three following possible pairs:

1. D1: R1 (Student, Instructor) and R2(Student, Course)
2. D2: R1 (Course, Instructor) and R2(Course, Student)
3. D3: R1 (Instructor, Course) and R2(Instructor, Student)

All three decompositions lose the functional dependency FD1.

We have to settle for sacrificing the functional dependency preservation. But we cannot sacrifice the non-additive join property after decomposition.

We have to apply a non-additive test to the resulting relations.

We have to make sure that joining the two decomposed tables gives us the original table.

A relation R not in BCNF can be decomposed to meet the nonadditive join property by the following procedure. It decomposes R successively into a set of relations in BCNF:

Let R be the relation not in BCNF, let X ⊆ R, and let X → A be the FD that causes a violation of BCNF. R may be decomposed into two relations:

R1 = R – A R2 = XA If either R – A or XA. is not in BCNF, repeat the process.

We will not go any deeper into this methodology in this course.

A trivial FD determines what you already have, eg., AB -> B.

A key is a minimal set of attributes determining the rest of the attributes of a relation A superkey is a set of attributes determining the rest of the attributes in the relation, but does NOT have to be minimal (e.g., the key above, or adding in either of City and Province) Given a set of (explicit) functional dependencies, we can determine other FDs:

Remember this? X

 Y, Y Z implies X Z





An FD fd is implied by a set of FDs F if fd holds whenever all FDs in F hold.

We have a set of rules for determining FDs and finding closures.

Armstrong’s Axioms (X, Y, Z are sets of attributes):

 Reflexivity:

If Y ⊆ X, then X

 Y e.g. AB B



 Augmentation: If X Y, then XZ YZ for any Z





 Transitivity: If X Y and Y Z then X Z







These are proven and complete inference rules for FDs.

From these axioms, we also have:







 Union: If X

Y and X

Z, then X Y Z







 Decomposition: If X

Y Z, then X

Y and X

Z

Definition: For each such set of attributes X, we determine the set X

+ of

attributes that are functionally determined by X based on F; X

+ is called the

closure of X under F.

A key contains a full set of attributes in its closure.

We use an algorithm to find the closure set of an attribute.

Algorithm: Determining X

+ , the Closure of X under F

Input: A set F of FDs on a relation schema R, and a set of attributes X, which isa subset of R.

X + := X; //Set closure of X as all attributes of X repeat old X + := X + ; // Set old X as current X for each functional dependency Y → Z in F do if X + ⊇ Y then X + := X + ∪ Z; //Add attributes to the closure

// using transitive and decomp rules

until (X + = old X + ); //Stop when the set no longer changes

Given the relation: SupplierPart(sname, city, status, p#, pname, qty) With the following functional dependencies:



1. fd1: sname city 
2. fd2: city status 
3. fd3: p# pname 
4. fd4: sname, p# qty

Show that (sname, p#) is a key!

1. fd1: sname city 

F I N D I N G T H E K E Y

1. fd2: city status 
2. fd3: p# pname 
3. fd4: sname, p# qty

First step: Show that (sname, p#) is a super key.



1. sname, p# sname, p# (trivial)
2. sname  city (fd1) 
3. sname status (transitive, fd2)  city, p# (augmentation 2)
4. sname, p#
5. sname, p#  status, p# (augmentation 3) 
6. sname, p# sname, status, p# (union 1 and 5) 
7. sname, p# sname, status, city, p# (union 4 and 6) 
8. sname, p# sname, status, city, p#, qty (union 7 and fd4)
9. sname, p# sname, pname (augmentation fd3)  
10. sname, p# sname, status, city, p#, qty, pname (union 8 and 9)

1. fd1: sname city 

F I N D I N G T H E K E Y

1. fd2: city status 
2. fd3: p# pname 
3. fd4: sname, p# qty

Second step: Show that (sname, p#) is minimal. Which means showing sname isn’t a key and p# isn’t a key.

p# isn’t on the right hand side of any FD, nothing determines p#.



sname p# does not hold so sname is not a key.

The same goes for p# So (sname, p#) is minimal and thus it is a key

Finding the closure sets of left-hand side attributes:

1. PatNo+ ={PatNo, PatName}  PatName (transitive)
2. (PatNo, AppNo)+ = {PatNo, AppNo, Time, Doctor} Since PatNo {PatNo, PatName, AppNo, Time, Doctor} PatNo, AppNo is a candidate key because all attributes are in its closure set.
3. (PatNo, Time)+ = {PatNo, Time}  PatName and Time AppNo  Since PatNo (PatNo, Time)+ = {PatNo, PatName, Time, AppNo} Since (PatNo,AppNo)  Doctor (PatNo, Time)+ = {PatNo, PatName, Time, AppNo, Doctor} (PatNo, Time) is also a candidate key