The following functional dependencies are defined on the relation R(A,B,C,D,E.F): (a) Find the candidate keys?

for R.


(b) Is R normalized? If not, create a set on normalized relations by decomposing R using only the given set of functional dependencies.


(c) If a new attribute F is added to R to create a new relation R'(A,B,C,D,E.F) without any addition to the set of functional dependencies, what would be the new set of candidate key for R' ?


(d) What is the new set of normalized relations that can be derived by decomposing R' for the same set of functional dependencies?


e) If a new dependency is declared as follows:


For each value of A, attribute F can have two values,


what would be the new set of normalized relations that can be created by decomposing R' ?

The following functional dependencies are defined on the relation R(A,B,C,D,E.F): (a) Find the candidate keys?
Normal Forms (1st to 3rd)





Guest lecture by K. Yue (November 29th, 2001)





This supplementary note is for a guest lecture on Dr. Boetticher's class on November 29th, 2001. Refer to the main note by Dr. Boetticher. The notes are based on my old notes in database classes.





Lossless Decomposition





It is assumed that the students are already familiar with the theory of lossless decomposition, including the concepts of closure, minimal covers, etc, as well as the 'matrix algorithm' for testing lossless decomposition.





I have written several Lisp programs long time ago for getting closure, cover and determining lossless decomposition. If you are interesting in reading, they are here:





* closure.lisp: finding the closure of a set of attributes.


* cover.lisp: finding a minimal cover of a set of functional dependencies.


* preserve.lisp: testing whether a decomposition is lossless.





Relational Database Designs





* Bad designs results in:


o redundancy: inefficient storage.


o anomalies: data inconsistency, difficulties in maintenance





Example:





Relation Scheme:





EMPLOYEE(EMP_NO, NAME, DEPT_NO, MANAGER_NO).





with the following assumptions:





* Every employee works for only one department.


* Every department has only one manager.


* Every manager manages only one department.





An instance of the relation:


EMP_NO NAME DEPT_NO MANAGER_NO


10000 Paul Simon D123 54321


20000 Art Garfunkel D123 54321


13000 Tom Jones D123 54321


21000 Nolan Ryan D225 42315


22000 Magic Johnson D225 42315


31000 Carl Sagan D337 33323





Redundancy:





The fact Manager 54321 manages department D123 is stored three times.





Update Anomalies:





Update: 44444 is now the new manager of department D123





* inefficiency in update.


* potential inconsistency.





EMP_NO NAME DEPT_NO MANAGER_NO


10000 Paul Simon D123 44444


20000 Art Garfunkel D123 44444


13000 Tom Jones D123 54321


21000 Nolan Ryan D225 42315


22000 Magic Johnson D225 42315


31000 Carl Sagan D337 33323





Update: Magic Johnson now works for department D337:





* need to know the manager of D337 before insertion.


* Potential inconsistency.





EMP_NO NAME DEPT_NO MANAGER_NO


10000 Paul Simon D123 54321


20000 Art Garfunkel D123 54321


13000 Tom Jones D123 54321


21000 Nolan Ryan D225 42315


22000 Magic Johnson D337 ?????


31000 Carl Sagan D337 33323





Update: Nolan Ryan now works for the new department D822, which does not have a manager yet.


EMP_NO NAME DEPT_NO MANAGER_NO


10000 Paul Simon D123 54321


20000 Art Garfunkel D123 54321


13000 Tom Jones D123 54321


21000 Nolan Ryan D822 ?????


22000 Magic Johnson D225 42315


31000 Carl Sagan D337 33323





Insertion Anomalies:





Insert: a new department D888, with manager 77111, currently with no employee is not possible.


EMP_NO NAME DEPT_NO MANAGER_NO


10000 Paul Simon D123 54321


20000 Art Garfunkel D123 54321


13000 Tom Jones D123 54321


21000 Nolan Ryan D225 42315


22000 Magic Johnson D225 42315


31000 Carl Sagan D337 33323


????? ????? D888 77111








Deletion Anomalies:





Delete: Carl Sagan no longer works here.


EMP_NO NAME DEPT_NO MANAGER_NO


10000 Paul Simon D123 54321


20000 Art Garfunkel D123 54321


13000 Tom Jones D123 54321


21000 Nolan Ryan D225 42315


22000 Magic Johnson D225 42315





* The information 33323 is the manager of the department D337 (now without employees) is lost.





Solution





Decomposition to relations that satisfy desirable normal forms.





EMP(EMP_NO, NAME, DEPT_NO)


DEPARTMENT(DEPT_NO, MANAGER_NO)





All anomalies mentioned above are now gone.





Normal Forms





* A set of rules to avoid redundancy and inconsistency.


* Require the concepts of:


o functional dependency (most important: up to BCNF)


o multivalued dependency (4NF)


o join dependency (5NF)


* Seven Common Normal Forms: 1NF, 2NF, 3NF, BCNF, 4NF, 5NF, DKNF. (There are more.)


* Higher normal forms are more restrictive.


* A relation is in a higher normal form implies that it is in a lower normal form, but not vice versa.


* Assumption: students are already familiar with functional dependencies (FD).





First Normal Form





* A relation is in 1NF if all attribute values are atomic: no repeating group, no composite attributes.


* Formally, a relation may only has atomic attributes. Thus, all relations satisfy 1NF.





Example:





Consider the following table. It is not in 1 NF.


DEPT_NO MANAGER_NO EMP_NO EMP_NAME


D101 12345 20000


20001


20002


Carl Sagan


Magic Johnson


Larry Bird


D102 13456 30000


30001 Jimmy Carter


Paul Simon





The corresponding relation in 1 NF:


DEPT_NO MANAGER_NO EMP_NO EMP_NAME


D101 12345 20000 Carl Sagan


D101 12345 20001 Magic Johnson


D101 12345 20002 Larry Bird


D102 13456 30000 Jimmy Carter


D102 13456 30001 Paul Simon





* Problem of NFNF (non-first normal form): relational operations treat attributes as atomic.





Second Normal Form





* A relation R is in 2NF if


o (a) R is in 1NF, and


o (b) all non-prime attributes are fully dependent on the candidate keys.


* A prime attribute appears in a candidate key.


* There is no partial dependency in 2NF. For a nontrivial FD X -%26gt; A and X is a subset of a candidate key K, then X = K.





Example:





The following relation is not in 2NF. The relation has the following FD:





Student_ID, Course -%26gt; Grade


Course -%26gt; Credit





Note the redundancy and anomalies.


Student_ID Course Credit Grade


S1 CSCI 5333 3 A


S1 CSCI 4230 3 A


S2 CSCI 5333 3 B-


S2 CSCI 4230 3 C


S3 CSCI 5333 3 B+





Third Normal Form





* A relation R is said to be in the third normal form if for every nontrivial functional dependency X --%26gt; A,


o (1) X is a superkey, or


o (2) A is a prime (key) attribute.


* An attribute is prime (a key attribute) if it appears in a candidate key. Otherwise, it is non-prime.





Example:





The example relation for anomalies is not in 3NF.





EMPLOYEE(EMP_NO, NAME, DEPT_NO, MANAGER_NO).





with the following assumptions:





* Every employee works for only one department.


* Every department has only one manager.


* Every manager manages only one department.





An instance of the relation:


EMP_NO NAME DEPT_NO MANAGER_NO


10000 Paul Simon D123 54321


20000 Art Garfunkel D123 54321


13000 Tom Jones D123 54321


21000 Nolan Ryan D225 42315


22000 Magic Johnson D225 42315


31000 Carl Sagan D337 33323





* Note that it is important to consider only non-trivial FD in the definitions of both 2NF and 3NF.





Example:





Consider R(A,B,C) with the minimal cover F: {A -%26gt; B}. Note that F |- B -%26gt; B, or B -%26gt; Bis in F+. For B -%26gt; B, B is not a superkey and B is non-prime. However, B -%26gt; B is not a violation of 3NF as it is trivial and should not be considered for potential violation.





* 3NF cannot eliminate all redundancy due to functional dependencies.





Example:





Consider the relation





S(SUPP#, PART#, SNAME, QUANTITY) with the following assumptions:





(1) SUPP# is unique for every supplier.


(2) SNAME is unique for every supplier.


(3) QUANTITY is the accumulated quantities of a part supplied by a supplier.


(4) A supplier can supply more than one part.


(5) A part can be supplied by more than one supplier.





We can find the following nontrivial functional dependencies:





(1) SUPP# --%26gt; SNAME


(2) SNAME --%26gt; SUPP#


(3) SUPP# PART# --%26gt; QUANTITY


(4) SNAME PART# --%26gt; QUANTITY





Note that SUPP# and SNAME are equivalent.





The candidate keys are:





(1) SUPP# PART#


(2) SNAME PART#





The relation is in 3NF.





However, the relation has unnecessary redundancy:


SUPP# SNAME PART# QUANTITY


S1 Yues P1 100


S1 Yues P2 200


S1 Yues P3 250


S2 Jones P1 300
Reply:Google is your friend. :)


http://www.google.com/search?num=100%26amp;hl=...