Database Storage & Design Chapter 14 Homework Database Design Theory Introduction Normalization Using Functional And Multivalued Dependencies

Chapter 14: Database Design Theory: Introduction to Normalization Using Functional and

Multivalued Dependencies

1

CHAPTER 14: Database Design Theory: Introduction to Normalization Using

Functional and Multivalued Dependencies

Answers to Selected Exercises

14.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 grade record refers to a student (Ssn), 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.

Answer:

From the above description, we can presume that the following functional dependencies

hold on the attributes:

FD1: {SSSN} -> {SNAME, SNUM, SCADDR, SCPHONE, SPADDR, SPPHONE, BDATE,

Chapter 14: Database Design Theory: Introduction to Normalization Using Functional and

Multivalued Dependencies

2

FD7: {SECCOURSE, SEMESTER, YEAR, SECNUM, SSSN} -> {GRADE}

These are the basic FDs that we can define from the given requirements; using inference

rules IR1 to IR3, we can deduce many others. FD1 and FD2 refer to student attributes;

we can define a relation STUDENT and choose either SSSN or SNUM as its primary key.

Similarly, FD3 and FD4 refer to department attributes, with either DEPTNAME or

The foreign keys will be as follows:

STUDENT.MAJOR -> DEPARTMENT.DEPTCODE

STUDENT.MINOR -> DEPARTMENT.DEPTCODE

COURSE.CDEPT -> DEPARTMENT.DEPTCODE

SECTION.SECCOURSE -> COURSE.CNUM

14.20 – What update anomalies occur in the EMP_PROJ and EMP_DEPT relations of

Figure 15.3 and 15.4?

Answer:

In EMP_PROJ, the partial dependencies {SSN}->{ENAME} and {PNUMBER}->{PNAME,

PLOCATION} can cause anomalies. For example, if a PROJECT temporarily has no

14.21 – In what normal form is the LOTS relation schema in Figure 15.12(a) with respect to

the restrictive interpretations of normal form that take only the primary key into account?

Would 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 .

14.22 – Prove that any relation schema with two attributes is in BCNF.

Answer:

Consider a relation schema R={A, B} with two attributes. The only possible (non-trivial)

FDs are {A} ->{B} and {B} ->{A}. There are four possible cases:

Chapter 14: Database Design Theory: Introduction to Normalization Using Functional and

Multivalued Dependencies

5

Answer:

To help in solving this problem systematically, we can first find the closures of all

single attributes to see if any is a key on its own as follows:

Based on the above analysis, we decompose as follows, in a similar manner to problem

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}

14.26 – No solution provided.

14.27 – Consider a relation R(A,B,C,D,E) with the following dependencies:

AB –> C

CD –> E

DE –> B

Is AB a candidate key of this relation? If not, is ABD? Explain your answer.

14.28 – 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}

Chapter 14: Database Design Theory: Introduction to Normalization Using Functional and

Multivalued Dependencies

6

Try to determine which sets of attributes form keys of R. How would you normalize this

relation?

Answer:

Let us use the following shorthand notation:

C = CourseNo, SN = SecNo, OD = OfferingDept, CH = CreditHours, CL = CourseLevel,

Y, I, C, SN}. But {C}+ contains {OD, CH, CL} so these are also contained in {RM, D, S,

Y}+ since C is already there. Finally, since {C, SN, S, Y} are now all in {RM, D, S, Y}+

and {C, SN, S, Y}+ contains {NS} (from (2) above), we get:

{RM, D, S, Y}+ = {RM, D, S, Y, I, C, SN, OD, CH, CL, NS} = R

Hence, both K1 = {C, SN, S, Y} and K2 = {RM, D, S, Y} are (candidate) keys of R. By

applying the general definition of 2NF, we find that the functional dependency {C} ->

14.29 – 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.)

14.30 – 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?

Answer:

Given the relation schema

Car_Sale(Car#, Salesman#, Date_sold, Commission%, Discount_amt)

with the functional dependencies

Date_sold Discount_amt

Salesman# Commission%

Chapter 14: Database Design Theory: Introduction to Normalization Using Functional and

Multivalued Dependencies

9

14.33 – Consider the following relation:

R (Doctor#, Patient#, Date, Diagnosis, Treat_code, Charge)

In this relation, a tuple describes a visit of a patient to a doctor along with a treatment code

and daily charge. Assume that diagnosis is determined (uniquely) for each patient by a

doctor. Assume that each treatment code has a fixed charge (regardless of patient). Is this

relation in 2NF? Justify your answer and decompose if necessary. Then argue whether

further normalization to 3NF is necessary, and if so, perform it.

Answer:

From the question’s text, we can infer the following functional dependencies:

{Doctor#, Patient#, Date}→{Diagnosis, Treat_code, Charge}

{Treat_code}→{Charge}

14.34 – Consider the following relation:

CAR_SALE (CarID, Option_type, Option_Listprice, Sale_date, Discounted_price)

This relation refers to options installed on cars (e.g.– cruise control) that were sold at a

dealership and the list and discounted prices for the options.

If CarID → Sale_date and Option_type→ Option_Listprice, and

CarID, Option_type → Discounted_price, argue using the generalized definition of the 3NF

that this relation is not in 3NF. Then argue from your knowledge of 2NF, why it is not in 2NF.

Answer:

For this relation to be in 3NF, all of the nontrivial functional dependencies must both be fully

14.35 – Consider the relation:

BOOK (Book_Name, Author, Edition, Year)

with the data:

Book_Name

Author

Edition

Year

DB_fundamentals

Navathe

4

2004

DB_fundamentals

Elmasri

4

2004

DB_fundamentals

Elmasri

5

2007

DB_fundamentals

Navathe

5

2007

a. Based on a common-sense understanding of the above data, what are the possible

candidate keys of this relation?

b. Does the above have one or more functional dependency (do not list FDs by applying

derivation rules)? If so, what is it? Show how you will remove it by decomposition.

c. Does the resulting relation have an MVD? If so, what is it?

d. What will the final decomposition look like?

Answer:

a. The only candidate key is {Book_Name, Author, Edition}. From the example, it would

b. Yes, we have the following FD: Book_Name, Edition → Year. We can decompose to

remove this FD in the following way:

d. The final decomposition would look like: