Question 1: SQL and the Relational Model [17 marks]

1. a General Concepts [4 marks]

1. a (i) [2 marks]

Explain the relationship of data independence with the ANSI/SPARC three level archi- tecture.

Answer: Refer to the text book and lecture notes.

1. a (ii) [1 mark]

Which of the following statements are true for a relation?

(1) Each superkey is a candidate key.

(2) Each candidate key is a superkey.

(3) The primary key is a candidate key, but there may be a candidate key that is not a primary key.

Answer: (2) and (3)

1. a (iii) [1 mark]

Given the sets A = {Sue,Ali}, B = {white,black} and C = {cat,dog}, what is the Cartesian product A ◊ B ◊ C?

Answer:

A ◊ B ◊ C =     {(Sue, white, cat)

(Sue, white, dog)

(Sue, black, cat)

(Sue, black, dog)

(Ali, white, cat)

(Ali, white, dog)

(Ali, black, cat)

(Ali, black, dog)}

1. b Writing SQL [4 marks]

Not relevant to the final examination this year

1. c SQL Evaluation [5 marks]

Not relevant to the final examination this year

1. d Integrity Constraints [4 marks]

1. d (i) [2 marks]

Suppose that the relation SUPERVISE was created as follows:

CREATE  TABLE SUPERVISE (

pssn INT  REFERENCES PROFESSOR(ssn) ON  DELETE  NO  ACTION, gid INT  REFERENCES GRADUATE(gid) ON  DELETE  SET  NULL,

pid INT  REFERENCES PROJECT(pid) ON  DELETE  CASCADE,

);

Which of the following statements are true, and which are false?

(a) If we delete a tuple from SUPERVISE, any tuples in PROJECT referred to by this tuple are also deleted.

(b) If we delete a tuple from GRADUATE, some tuples of SUPERVISE may have their values of attribute gid set to NULL.

(c) If we try to insert a tuple into PROFESSOR, with an ssn that does not exist in SUPERVISE, the operation is rejected.

(d) If we try to insert a tuple into SUPERVISE, with a gid that does not exist in GRAD - UATE, the operation is rejected.

Provide your answer in the following table.

1. d (ii) [2 marks]

Consider the relation BOOK in Figure 1, which has the primary key {bid} and the foreign key [aid] ⇥ AUTHOR[aid].

Figure 1: Relation BOOK and AUTHOR

. Write down an SQL statement to modify an existing tuple in AUTHOR which would yield a key integrity violation. The modification should not violate any other integrity constraints.

Writing SQL queries

is not covered

in the inal exam .

Answer:

UPDATE AUTHOR

SET aid = 2

WHERE name = "S .E .Hinton";

. Write down an SQL statement to insert a tuple into BOOK which would yield an

entity integrity violation. The insertion should not violate the existing foreign key constraint.

Answer:

INSERT INTO BOOK

VALUES (NULL, "Fire", English, 1980, 1);

Question 2: ER Modelling and Translation [8 marks]

ACTRides is a car rental company which has been founded recently in       Canberra. It currently has 5 branches opened in Acton, Belconnen,             Dickson, Braddon and Woden, respectively. ACTRides is planning to         expand to areas such as Tuggeranong and Manuka in the future. A branch has a unique address but may have multiple telephone numbers. Each        rental car must be associated with exactly one ACTRides branch. A rental car can be identiied by its registration number and has the information     about the model and the production year. Each employee working at

ACTRides has a tax ile number (TFN), a name and an address. ACTRides

employees consist of managers, mechanics and customer service                representatives. Every employee must work at exactly one branch. A          customer of ACTRides should provide their drivers license number, their name and a contact number. A customer can rent a car from an                  ACTRides branch and details about the rental such as the rental period     and price should be recorded. If a customer is not satisied with the rental service provided, this customer may submit a complaint to a customer      service representative and thus a distinct reference number and detailed   description of the complaint should be recorded. The manager of a            branch will handle all the complaints with respect to this branch and has  an urgent contact number in case of emergency. Mechanics working at a  branch inspect the cars associated with the branch and record the               condition and inspection date. A car must be inspected at least two times per year. Each mechanic has a skill level and might have another                 mechanic as the supervisor. The supervisor must have a higher skill level  compared to the mechanics supervised by this supervisor.

Your task is to design an Enhanced Entity Relationship (EER) diagram for the above database, which should include entities, relationships, attributes and constraints wherever appropriate (you can make more assumptions if necessary).

YoualsoneedtoidentifytherequirementsthatcannotbecapturedinanEER- diagram.

RequirementsthatcannotbecapturedintheEER-diagram:

• Acarmustbeinspectedatleasttwotimesperyear.

•  Thesupervisormusthaveahigherskilllevelcomparedtothemechanicssupervised bythissupervisor.

Question 3: Functional Dependencies and Normal Forms [15 marks]

3. a Satisfaction of Functional Dependencies [4 marks]

3. a (i) [3 marks]

Consider two relations r1 (R) and r2 (R) over the same relation schema R(A,B,C,D).

r1 (R)

r2 (R)

The following is a table (i.e., Table 1) with a column for each of these relations and a row for a functional dependency. Enter“yes”or“no”in each cell of the table, indicat- ing whether the relation satisfies the functional dependency.

Answer:

r1 (R) r2 (R)

A 一(~) B no no

AB 一(~) C yes yes

A 一(~) BC no no

DC 一(~) B no yes

BC 一(~) B yes yes

AD 一(~) C yes yes

Table 1: Functional dependencies

3. a (ii) [1 mark]

Are there any trivial functional dependencies shown in Table 1? If any, specify them and explain why they are trivial.

Answer:BC 一(~) B is trivial.

3. b Candidate Keys and Normal Forms [4 marks]

Given a relation schema R(A,B,C,D,E) with the following set Σ of functional de- pendencies:

Σ = {A 一(~) C, CE 一(~) B, BC 一(~) AD and D 一(~) E}.

3. b (i) [1 mark]

Does AB 一(~)E hold on any relation ofR that satisfies Σ? Ifso, explain why; otherwise, give a counterexample.

Answer: Compute the closure of AB w.r.t. Σ: (AB)+ = (ABC)+ = (ABCD)+ = (ABCDE)+ =ABCDE. Because E ⇤ (AB)+ holds, AB 一(~) E holds on any relation of R that satisfies Σ .

3. b (ii) [3 marks]

Is R in BCNF? If not, normalise R into BCNF. Explain your answer.

Answer:

. Step 1: check whether the left hand side of each FD is a superkey:

– (A)+ = AC

– (CE)+ = (BCE)+ = (ABCDE)+ =ABCDE

– (BC)+ = (ABCD)+ = (ABCDE)+ =ABCDE

– (D)+ = DE

. Step 2: A 一(~) C and D 一(~) E are problematic, so we decompose R along them into:

– AC with {A 一(~) C}

– DE with {D 一(~) E}

– ABD with {AB  一(~)

3. c Candidate Keys and Normal Forms [7 marks]

Consider the relation schema

MEETING(OfficerID, OfficerName, CustNo, CustName, Date, Time, Room), and the following set of functional dependencies on MEETING:

• OfficerID 一(~) OfficerName;

• OfficerID, Date 一(~) Room;

• CustNo 一(~) CustName;

• CustNo, Date, Time 一(~) OfficerID;

• Date, Time, Room 一(~) CustNo.

3. c (i) [1 mark]

Discuss the anomalies in the current schema MEETING and identify at least two poten- tial problems.

Answer: Refer to the text book and the lecture notes about insert anomalies, delete anomalies and modification anomalies.

3. c (ii) [2 marks]

Find out all the candidate keys and prime attributes of MEETING.

Answer: Compute the closure of attributes (refer to the lecture nodes). The candi- date keys are:

• {CustNo, Date, Time}

• {OfficerID, Date, Time}

• {Data, Time, Room}

The prime attributes are {CustNo, OfficeID, Date, Time, Room}.

3. c (iii) [1 mark]

As we have not      What is the highest normal form of MEETING with respect to the given set offunctional

discussed 1NF anddependencies? Explain the reason.

2NF iin oSr2c2u0r,se,

question when

inal exam.

Note:

• We only consider the normal forms 1NF, 2NF, 3NF and BCNF (in increasing order of strength).

• No primary keys are given, so the relevant definitions of the normal forms are the ones that refer to all candidate keys.

Answer: The highest normal form of MEETING is 1NF because OfficerID 一(~)

OfficerName and CustNo 一(~) CustName are partial dependencies with respect to the candidate keys.

3. c (iv) [3 marks]

Normalise the relation schema MEETING into BCNF.

Answer: There are several steps:

As we have not

discussed 2NF in

lSet, please

solution to this

question when

the inal exam.

• Normalise MEETING into 2NF along OfficerID 一(~) OfficerName and CustNo

一 CustName:

– OFFICE(OfficeID, OfficeName) with the FD: OfficerID 一(~) OfficerName

– CUSTOMER(CustNo, CustName) with the FD: CustNo 一(~) CustName

– MEETING’(OfficerID, CustNo, Date, Time, Room) with the FDs:

⌅ OfficerID, Date 一(~) Room;

⌅ CustNo, Date, Time 一(~) OfficerID;

⌅ Date, Time, Room 一(~) CustNo.

• Normalise MEETING’into BCNF along OfficerID, Date 一(~) Room:

– MEETING”(OfficerID, Date, Room) with the FD: OfficerID, Date 一(~) Room;

– MEETING”’(OfficerID, CustNo, Date, Time) with the FD: CustNo, Date, Time 一(~) OfficerID.

Hence, MEETING can be decomposed into the following four relations in BCNF:

• OFFICE, CUSTOMER,MEETING”and MEETING”’

Question 4: Relational Algebra and Query Processing [18 marks]

4. a Relational Algebra Expressions [4 marks]

Consider the following relation schemas:

AUTHOR(aid, name) with the primary key {aid};

BOOK(bid, title, language, date, aid) with the primary key {bid} and

the foreign key [aid]⇥ AUTHOR[aid]. Write relational algebra expressions for the following queries.

4. a (i) [1 mark]

Who wrote the book titled“The Cat in the Hat”?

Answer:

. πname (⇥title=“The Cat in the Hat”(BOOK) ⇤⌅ AUTHOR), or

. πaid,name (⇥title=“The Cat in the Hat”(BOOK) ⇤⌅ AUTHOR)

4. a (ii) [1 mark]

List the names of authors who have published at least one book in English and one book in Japanese.

Answer:

. πname ((πaid (⇥Language=“English”(BOOK)) ⇤⌅ πaid (⇥Language=“Japanese”(BOOK))) ⇤⌅ AUTHOR)

. πname ((πaid (⇥Language=“English”(BOOK))⇧πaid (⇥Language=“Japanese”(BOOK))) ⇤⌅ AUTHOR)

4. a (iii) [2 marks]

Find out the authors who have never published a book in English.

Answer:

•  πaid,name (AUTHOR) ⌃ πaid,name (⇥language=“English”(BOOK ⇤⌅ AUTHOR))