RELATIONAL DATABASE THEORY ON NORMAL FORMS

Click here for audio-text lecture (for both this unit and the previous one) and feed it to the speech agent
Click here for an audio lecture that can be played using RealPlayer

FUNCTIONAL DEPENDENCY

X -> Y, or X functionally determines Y if and only if whenever two tuples of a relational instance r(R) of R agree on their X-value, they must also agree on the Y-value.

Example: SSN -> NAME

We say X determines Y, or Y is dependent on X

Example: {S#,P#} -> QTY

Since QTY depends on BOTH attributes S# and P#, this is called a FULL functional dependency.

Example: {SSN, NAME} -> ADDRESS

Since SSN -> ADDRESS, this is called a partial functional dependency.

We also write:

S# P# -> QTY
SSN NAME -> ADDRESS

NORMALIZATION

The relation on the left-hand side is unnormalized and contains nested relations. The relation on the right-hand side is normalized. This is the first normal form.

NORMAL FORMS

  • A relation is in a "normal form" if it satisfies a certain set of constraints.

  • First Normal Form (1NF): A relation's underlying domains contain atomic values only.

  • Second Normal Form (2NF): A relation's every nonkey attribute is fully dependent on the primary key.

  • Third Normal Form (3NF): A relation's nonkey attributes are: (a) mutually independent, and (b) fully dependent on the primary key.

  • EVERY RELATION MUST BE IN 1NF. This is one of the basic properties of a relation. Not all 1NF relation is in 2NF. Not all 2NF relation is in 3NF.

    EXAMPLE OF NORMALIZATION

    The following relation FIRST is in first normal form. 
    S#       STATUS     CITY      P#    QTY
---      ------   --------   ---   ----
 S1          20   London      P1   300
 S1          20   London      P2   200
 S1          20   London      P3   400
 S1          20   London      P4   200
 S1          20   London      P5   100
 S1          20   London      P6   100
 S2          10    Paris      P1   300
 S2          10    Paris      P2   400
 S3          10    Paris      P2   200
 S4          20   London      P2   200
 S4          20   London      P4   300
 S4          20   London      P5   400


    The FIRST relation has the following functional dependencies:



    The functional dependencies in relations S, P and SP:

    UPDATE ANOMALIES

  • Relation FIRST(S#,STATUS,CITY,P#,QTY)

  • INSERT anomaly

    We cannot insert (S5,20,London) into the relation FIRST.

  • DELETE anomaly

    If we delete (S3,10,Paris,P2,200), we lose the information that S3 is in Paris.

    SOLUTION

  • Decompose FIRST into two relations: SECOND(S#,STATUS,CITY) and SP(S#,P#,QTY)

  • Decompose SECOND into two relations: SC(S#, CITY) and CS(CITY, STATUS)

  • We end up with three 3NF relations SP, SC and CS.
    Functional dependencies in the relations SECOND and SP.

    KINDS OF NORMAL FORMS

    The following diagram illustrates the various kinds of normal forms.

    KINDS OF RELATIONS

    (duplicated page)

  • Base relations: The real relations. Called "base table" in SQL.

  • Views: The virtual relations. A view is a named, derived relation.

  • Snapshots: A snapshot is a real, not virtual, named derived relation.

  • Query results: The final output relation from a specified query. It may not be named and has no permanent existence.

  • Temporary relations: A nonpermanent named derived relation.

    INFERENCE RULES FOR FUNCTIONAL DEPENDENCIES


    IR1 (Reflective rule) IF X contains Y, then X -> Y
    IR2 (Augmentation rule) {X->Y} implies XZ -> YZ
    IR3 (Transitive rule) {X->Y,Y->Z} imples X->Z
    IR4 (Projection rule) {X->YZ} implies X->Y
    IR5 (Union rule) {X->Y,X->Z} implies X->YZ
    IR6 (Pseudotransitive rule) {X->Y,WY->Z} implies WX->Z

    Inference rules IR1 to IR3 (Armstrong) are SOUND and COMPLETE
    SOUND (inferred dependencies hold if the original set of dependencies hold for r(R))
    COMPLETE (don't need more rules)