INFO 340 - L09 - April 26, 2004
Notes By: Egaas, Fortier, Prins

Hypercard
Stack
Card
    File-Based
    Database
        TextMaterial
        ImageMaterial
        
Know everything up to 13 and selected parts of 13 for the midterm.

Topics
    > Normalization
        - Update anomalies
    > Functional Dependencies
    > Process of Normalization
        - First normal form
        - Second normal form
        - Third normal form
        - Boyce-Codd Normal Form

"Bottom up process"
"way of reducing data redundancy"
"solves data integrity problems"
"could take longer to produce results to queries if you have too much normalization"

Normalization
    > A technique for producing a set of relations with desireable properties given the data requirements of an enterprise
       - You simplify (decompose) relations to avoid data redundancy

Motivation
    > To avoid update anomalies relations need to be in third normal form.

Third Normal Form
    A relation is in 3rd normal form if, for all time, each tuple consists of a primary key value that identifies some entity, together with a set of zero or more mutually independent attribute values that describe the entity in some way.
        Common sense, sort of ....

Update Anomalies
    > Cause by data redundancy with relations
    > Three kinds of anomalies
        - INSERT
        - DELETE
        - UPDATE
Example Relation
    > PARTS(S#, status, Cit, P#, QTY)
        PRIMARY KEY(S#, P#)
    > Constraint: Status is functional dependent on city

Constraint:
    Status is *functional dependant* on city

Insert Anomalies:
+---------------------------------+
| S#  Status  City        P#  Qty |
+---------------------------------+
| S1  20      London      P1  300 |
| S1  20      London      P2  200 |
+---------------------------------+
//its so sad we do this
// I want RTF based SubEthaEdit....

To insert supplier information we must insert part information.

Q: Another example?
    

Delete Anomalies
+---------------------------------+
| S#  Status  City        P#  Qty |
+---------------------------------+
| S1  20      London      P1  300 |
| S1  20      London      P2  200 |
| S2  10      Paris       P1  300 |
+---------------------------------+
Q: What happens if we delete P1??

Update Anomalies
+---------------------------------+
| S#  Status  City        P#  Qty |
+---------------------------------+
| S1  20      London      P1  300 |
| S1  20      London      P2  200 |
| S2  10      Paris       P1  300 |
+---------------------------------+
Q: What happens if we need to change the city of S1?

Functional Dependancy
    > Describes the relationship between attriubtes in a relation. If A and B are attributes of R, B is functionally dependant on A(A -> B), if each value A is associated with exactly on value of B
    > Example: A cityID functionally determines a city name
    > Written: cityID --> cityName
    > (The Determinant) cityId --> cityName (The dependent)
        - cityID functionally determines cityName
        - cityName is functionally dependent on cityID

Exercise:
    Draw a diagram showing the functional dependencies in this relation
    
    PARTS(S#, Stat, City, P#, QTY)
        PRIMARY KEY (S#, P#)
    
    +---------------------------------+
    | S#  Status  City        P#  Qty |
    +---------------------------------+
    | S1  20      London      P1  300 |
    | S1  20      London      P2  200 |
    | S2  10      Paris       P1  300 |
    +---------------------------------+

As a Diagram
    [QTY]<-----+-------+
               | +---+-+-------->[City]
               | | S#| |     |      |
               | +---+ |     +----->|
               | +---+ |            |
               | | P#| |            V
               | +---+ |          [STAT]
               +-------+

As Sets
    {S#,P#} -> {QTY}
    {S#} -> {CITY}
    {S#} -> {STAT}
    {S#} -> {CITY,STAT}
    {CITY} -> {STAT}
    {S#,CITY} -> {STAT}

Key Properties of Functional Dependancies
    1) One-to-one relationship between determinant and dependent
        {S#, P#} -> {QTY}
    2) Relationship hols for all time (extenson of relations, must consider domain)
    3) Non-Trivial
    
    
1st Normal Form
All domains of a relation contain atomic values
        OR
The intersection of each row and column contains one and only one value

2nd Normal Form
A relation in 1st normal form and every non-primary-key attribute is fully functionally dependent on the primary key
What is fully functionally dependent?

Fully Functional Dependent
    If A and B are attributes of a relation, B is fully functionally dependent on A if B is functionally dependent on A, but not on any proper subset of A.
    Example: {S#, CITY} --> {STAT}
    (Not fully functional dependent)

3rd Normal Form
A relation that is first and second normal form and in which no non-primary-key is transitively dependent on the primary key.
What is transitive dependency?

Transitive Dependency
    If A,B, and C are attributes of a relation such that A -> B and B -> C, then C is transitively dependent on A via B
    Example:
        {S#} -> {CITY} -> {STAT}