Transcript Boyce-Codd NF

Boyce-Codd NF
Takahiko Saito
Spring 2005
CS 157A
Purpose of Normalization
• To reduce the chances for anomalies
to occur in a database.
• normalization prevents the possible
corruption of databases stemming
from what are called "insertion
anomalies," "deletion anomalies," and
"update anomalies."
Insertion Anomaly
• A failure to place a new database
entry into all the places in the
database where that new entry needs
to be stored.
• In a properly normalized database, a
new entry needs to be inserted into
only one place in the database
Deletion Anomaly
• A failure to remove an existing
database entry when it is time to
remove that entry.
• In a properly normalized database,
an old, to-be-gotten-rid-of entry
needs to be deleted from only one
place in the database
Update anomaly
• An update of a database involves
modifications that may be additions,
deletions, or both. Thus "update
anomalies" can be either of the kinds of
anomalies discussed above.
1st Normal Form
• A table (relation) is in 1NF if
1. There are no duplicated rows in the
table.
2. Each cell is single-valued
3. Entries in a column are of the same
kind.
2nd Normal Form
• A table is in 2NF if it is in 1NF and if all
non-key attributes are fully dependent on
each candidate key.
• A partial dependency occurs when a nonkey attribute is dependent on only a part
of the (composite) key
1NF but not 2NF
• Supplier (supplier#, status, city, part#,
quantity)
– (supplier#, part#) -> quantity
– supplier# -> status
– supplier# -> city
– city -> status
• => status and city are dependent on just
part of the key, namely supplier#.
1NF but not 2NF (cont’d)
• Decomposition (into 2NF):
– Supplier (supplier#, status, city)
– Supplier_Part (supplier#, part#,
quantity)
3rd Normal Form (3NF)
• A table is in 3NF if it is in 2NF and if it has
no transitive dependencies.
• Transitive dependency is a functional
dependency between non-key attributes.
2NF but not 3NF
• Supplier (supplier#, status, city)
– supplier# -> status
– supplier# -> city
– city -> status
=> Lacks mutual independence among non-key
attributes.
2NF but not 3NF (cont’d)
• Decomposition (into 3NF):
– SUPPLIER_CITY (supplier#, city)
– CITY_STATUS (city, status)
Boyce-Codd NF
• A table is in BCNF if it is in 3NF and if
every determinant is a candidate key.
• the definition of 3NF does not deal with a
relation that:
– has multiple candidate keys, where
– Those candidate keys are composite, and
– the candidate keys overlap (i.e., have at least
one common attribute)
3NF but not boyce-codd NF
• SUPPLIER_PART (supplier#, supplier_name,
part#, quantity)
– Two candidate keys:
• (supplier#, part#) and (supplier_name, part#)
– (supplier#, part#) -> quantity
– (supplier#, part#) -> supplier_name
– (supplier#, part#) -> quantity
– (supplier#, part#) -> supplier#
– supplier_name -> supplier#
– supplier# -> supplier_name
Another example of boyce-codd NF
title
Star Wars
year length filmType studioNam
e
1977 124
color
Fox
starName
Star Wars
1977
124
color
Fox
Hamill
Star Wars
1977
124
color
Fox
Ford
Mighty Ducks 1991
104
color
Disney
Esteves
Wayne’s World 1992
95
color
Paramount
Carvey
Wayne’s World 1992
95
color
Paramount
Meyers
Fisher
Example (cont’d)
• {title, year, starName} as candidate key
• title, year  length, filmType, studioName
• The above FD (Functional Dependency)
violates the BCNF condition because title
and year do not determine the sixth
attribute, starName
Example (cont’d)
• We solve this BCNF violation by decomposing
relation Movies into
1. The schema with all the attributes of the FD
{title, year, length, filmType,
studioName}
2. The schema with all attributes of Movies
except the three that appear on the right of
the FD
{title, year, starName}
Summary of Boyce-Codd NF
• When there is more than one candidate key, a relational
•
•
table may be in 3NF and anomalies may still result.
This occurs when there is a composite primary key, and
there are two equally valid candidates to make up part
of this composite primary key. If there is an attribute
(one or more columns) on which any other attribute is
fully dependent, and this attribute is NOT itself a
candidate key, then the table is not in Boyce-Codd
Normal form (BCNF).
We fix this by breaking the table up into two tables, both
in BCNF.