CHAPTER 10: FUNCTIONAL DEPENDENCIES AND NORMALIZATION FOR RELATIONAL DATABASES
CHAPTER 10: FUNCTIONAL DEPENDENCIES AND NORMALIZATION FOR RELATIONAL DATABASES
Answers to Selected Exercises
15.19 Suppose we have the following requirements for a university database that is
used to keep track of students transcripts:
(a) The university keeps track of each student’s name (SNAME), student number
(SNUM), social security number (SSSN), current address (SCADDR) and phone
(SCPHONE), permanent address (SPADDR) and phone (SPPHONE), birthdate
(BDATE), sex (SEX), class (CLASS) (freshman, sophomore, …, graduate),
major department (MAJORDEPTCODE), minor department (MINORDEPTCODE)
(if any), and degree program (PROG) (B.A., B.S., …, Ph.D.). Both ssn and
student number have unique values for each student.
(b) Each department is described by a name (DEPTNAME), department code
(DEPTCODE), office number (DEPTOFFICE), office phone (DEPTPHONE), and
college (DEPTCOLLEGE). Both name and code have unique values for each
department.
(c) Each course has a course name (CNAME), description (CDESC), code number
(CNUM), number of semester hours (CREDIT), level (LEVEL), and offering
department (CDEPT). The value of code number is unique for each course.
(d) Each section has an instructor (INSTUCTORNAME), semester (SEMESTER), year
(YEAR), course (SECCOURSE), and section number (SECNUM). Section numbers
distinguish different sections of the same course that are taught during the same
semester/year; its values are 1, 2, 3, …; up to the number of sections taught
during each semester.
(e) A transcript refers to a student (SSSN), refers to a particular section, and
grade (GRADE).
Design an relational database schema for this database application. First show all
the functional dependencies that should hold among the attributes. Then, design
relation schemas for the database that are each in 3NF or BCNF. Specify the key
attributes of each relation. Note any unspecified requirements, and make
appropriate assumptions to make the specification complete.
10.18 Prove or disprove the following inference rules for functional dependencies. A
proof can be made either by a proof argument or by using inference rules IR1 through IR3. A disproof should be done by demonstrating a relation instance that satisfies the conditions and functional dependencies in the left hand side of the inference rule but do not
satisfy the conditions or dependencies in the right hand side.
(a) {W ->Y, X ->Z} |= {WX ->Y }
(b) {X ->Y} and Z subset-of Y |= { X ->Z }
(c) { X ->Y, X ->W, WY ->Z} |= {X ->Z}
(d) {XY ->Z, Y ->W} |= {XW ->Z}
(e) {X ->Z, Y ->Z} |= {X ->Y}
(f) {X ->Y, XY ->Z} |= {X ->Z}
10.19 Consider the following two sets of functional dependencies F= {A ->C, AC ->D,
E ->AD, E ->H} and G = {A ->CD, E ->AH}. Check whether or not they are
equivalent.
10.22 What update anomalies occur in the EMP_PROJ and EMP_DEPT relations of
Figure 14.3 and 14.4?
10.23 In what normal form is the LOTS relation schema in Figure 10.11(a) with the
respect to the restrictive interpretations of normal form that take only the
primary key into account? Will it be in the same normal form if the general
definitions of normal form were used?
Answer:
If we only take the primary key into account, the LOTS relation schema in Figure 14.11
(a) will be in 2NF since there are no partial dependencies on the primary key .
However, it is not in 3NF, since there are the following two transitive dependencies on
the primary key:
PROPERTY_ID# ->COUNTY_NAME ->TAX_RATE, and
PROPERTY_ID# ->AREA ->PRICE.
Now, if we take all keys into account and use the general definition of 2NF and 3NF, the
LOTS relation schema will only be in 1NF because there is a partial dependency
COUNTY_NAME ->TAX_RATE on the secondary key {COUNTY_NAME, LOT#}, which
violates 2NF.
10.24 Prove that any relation schema with two attributes is in BCNF.
10.25 Why do spurious tuples occur in the result of joining the EMP_PROJ1 and
EMPLOCS relations of Figure 14.5 (result shown in Figure 14.6)?
10.26 Consider the universal relation R = {A, B, C, D, E, F, G, H, I} and the set of
functional dependencies F = { {A, B} -> {C}, {A} -> {D, E}, {B} -> {F}, {F} ->
{G, H}, {D} -> {I, J} }. What is the key for R? Decompose R into 2NF, then 3NF
relations.
10.27 Repeat exercise 10.26 for the following different set of functional dependencies
G = { {A, B} -> {C}, {B, D} -> {E, F}, {A, D} -> {G, H}, {A} -> {I}, {H} -> {J} }.
14.26, starting with the following relation R:
R = {A, B, D, C, E, F, G, H, I}
The first-level partial dependencies on the key (which violate 2NF) are:
{A, B} -> {C, I}, {B, D} -> {E, F}, {A, D}+ -> {G, H, I, J}
Hence, R is decomposed into R1, R2, R3, R4 (keys are underlined):
R1 = {A, B, C, I}, R2 = {B, D, E, F}, R3 = {A, D, G, H, I, J}, R4 = {A, B, D}
Additional partial dependencies exist in R1 and R3 because {A} -> {I}. Hence, we remove
{I} into R5, so the following relations are the result of 2NF decomposition:
R1 = {A, B, C}, R2 = {B, D, E, F}, R3 = {A, D, G, H, J}, R4 = {A, B, D}, R5 = {A, I}
Next, we check for transitive dependencies in each of the relations (which violate 3NF).
Only R3 has a transitive dependency {A, D} -> {H} -> {J}, so it is decomposed into R31
and R32 as follows:
R31 = {H, J}, R32 = {A, D, G, H}
The final set of 3NF relations is {R1, R2, R31, R32, R4, R5}
10.28 Solution to come
10.29 Given relation R(A,B,C,D,E) with dependencies
C.AB
E.CD
B.DE
is AB a candidate key?
is ABD a candidate key?
10.30 Consider the relation R, which has attributes that hold schedules of courses and
sections at a university; R = {CourseNo, SecNo, OfferingDept, CreditHours,
CourseLevel, InstructorSSN, Semester, Year, Days_Hours, RoomNo,
NoOfStudents}. Suppose that the following functional dependencies hold on R:
{CourseNo} -> {OfferingDept, CreditHours, CourseLevel}
{CourseNo, SecNo, Semester, Year} ->
{Days_Hours, RoomNo, NoOfStudents, InstructorSSN}
{RoomNo, Days_Hours, Semester, Year} -> {InstructorSSN, CourseNo, SecNo}
Try to determine which sets of attributes form keys of R. How would you
normalize this relation?
Answer:
10.31 Consider the following relations for an order-processing application database at ABC, Inc.
ORDER (O#, Odate, Cust#, Total_amount)
ORDER-ITEM (O#, I#, Qty_ordered, Total_price, Discount%)
Assume that each item has a different discount. The Total_price refers to one item, Odate is the date on which the order was placed, and the Total_amount is the amount of the order. If we apply a natural join on the relations Order-Item and Order in this database, what does the resulting relation schema look like? What will be its key? Show the FDs in this resulting relation. Is it in 2NF? Is it in 3NF? Why or why not? (State any assumptions you make.)
O# .Total_amount
It is not in 2NF, as attributes Odate, Cut#, and Total_amount are only partially
dependent on the primary key, O#I#
Nor is it in 3NF, as a 2NF is a requirement for 3NF.
10.32 Consider the following relation:
CAR_SALE(Car#, Date_sold, Salesman#, Commision%, Discount_amt
Assume that a car may be sold by multiple salesmen and hence {CAR#, SALESMAN#} is the primary key. Additional dependencies are:
Date_sold ->Discount_amt
and
Salesman# ->commission%
Based on the given primary key, is this relation in 1NF, 2NF, or 3NF? Why or why not? How would you successively normalize it completely?
10.33 Consider the following relation for published books:
BOOK (Book_title, Authorname, Book_type, Listprice, Author_affil, Publisher)
Author_affil referes to the affiliation of the author. Suppose the following dependencies exist:
Book_title -> Publisher, Book_type
Book_type -> Listprice
Author_name -> Author-affil
(a) What normal form is the relation in? Explain your answer.
(b) Apply normalization until you cannot decompose the relations further. State the reasons behind each decomposition.
(a)The key for this relation is Book_title,Authorname. This relation is in 1NF and not in
2NF as no attributes are FFD on the key. It is also not in 3NF.
(b) 2NF decomposition:
Book0(Book_title, Authorname)
Book1(Book_title, Publisher, Book_type, Listprice)
Book2(Authorname, Author_affil)
This decomposition eliminates the partial dependencies.
3NF decomposition:
Book0(Book_title, Authorname)
Book1-1(Book_title, Publisher, Book_type)
Book1-2(Book_type, Listprice)
Book2(Authorname, Author_affil)
This decomposition eliminates the transitive dependency of Listprice
8 years ago
30