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}