THE AUSTRALIAN NATIONAL UNIVERSITY
Second Semester Examination – November 2012
RELATIONAL DATABASES
(COMP2400/COMP6240)
Writing period: 3 hours duration
Study period: 15 minutes duration
Permitted materials: A4 paper (one sheet) with handwritten notes one side only
Instructions:
• This exam booklet contains 5 questions, totaling 65 marks.
• You need to answer all questions. Whenever you feel that some information is
missing, add an assumption and make it explicit in your solution.
• All your answers must be written in the spaces provided in this booklet. You may be provided with scrap paper for working, but it must not be used to write final answers. There is additional space at the end of the booklet in case the spaces provided under questions are insufficient.
• Do not remove this booklet from the examination room. Student Number
Question 1 17
Official use only:
1 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
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)
2 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
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?
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)}
3 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
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 (
pssnINT REFERENCESPROFESSOR(ssn)ON DELETE NO ACTION, gidINT REFERENCESGRADUATE(gid)ON DELETE SET NULL, pidINT REFERENCESPROJECT(pid)ON DELETE CASCADE, PRIMARY KEY(pssn, gid, pid)
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.
True False
4 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
Statements (a) (b) (c) (d)
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].
bid 1 2 3 4
The Cat in the Hat The Hobbit
The Lord of the Rings
AUTHOR aid name
1 J.R.R.Tolklen 2 Dr. Seuss
3 S.E.Hinton 4
title The Plague
language French English English English
date aid 1947 4 1957 2 1937 1 1954 1
Writing SQL
is not covered
in the final exam.
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.
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.
INSERT INTO BO O K
VALUES (NULL, “Fire”, English, 1980, 1);
Figure 1: Relation BOOK and AUTHOR
5 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
Question 2: ER Modelling and Translation [8 marks]
ER Modelling [4 marks]
Canberra Employment Centre (CEC) places temporary workers in compa- nies during peak periods. CEC maintains a file of candidates who wish to work. If the candidate has worked before, that candidate has a specific job history. (Naturally, no job history exists if the candidate has never worked.)
Each candidate may have several qualifications. CEC also has a list of companies that request temporaries. Each time a company requests a tem- porary employee, CEC makes an entry in the openings folder. This folder contains an opening number, company name, required qualifications, start- ing date, anticipated ending date, and hourly pay. Each opening requires only one specific qualification.
Draw an ER diagram that captures the above information, which should include: 1. identifying the entities, relationships and their attributes;
2. indicating the key attributes which you have chosen.
Answer: See Figure 2, in which the following assumptions are made:
• One opening will match with one qualification only.
• A qualification may be good for a number of openings.
• A company may or may not have an opening.
• Qualification will be identified by QualificationID and will be written in terms of type such as Typing, IT, Management etc. One may choose a surrogate key for Qualification.
6 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
COMPANY OPENI NG
QUALOIFICATION
CANDI DATE
QualificationID
ER-to-Relational Translation[4 marks]
candidateID
Figure 2: Answer for Q2.a
The following ER diagram is drawn from a business case where a vendor provides a quotation for the supply of a part.
VendorID Address
QuotedQuantity Price
Transform the ER diagram to a relational database schema and identify the primary and foreign keys for each relation schema.
Applying the translation rules in the lecture notes, we have:
• VENDOR(VendorID, Address) with the primary key {VendorID};
• PART(PartNo, Details) with the primary key {PartNo};
• QUOTES(VendorID,PartNo,QuoteQuantity,Price)withtheprimarykey{VendorID, PartNo} and the foreign keys: [VendorID] ⊆ VENDOR[VendorID] and [PartNo]
⊆ PART[PartNo].
7 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
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) ABCD 1231 4532 4332 1523
r2 (R) ABCD 1232 1453 3424
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.
A ��B AB ��C
A ��BC DC ��B
BC ��B AD ��C
r1 (R) no yes no
no yes yes
r2 (R) no yes no yes yes yes
Table 1: Functional dependencies
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.
8 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
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 of R that satisfies Σ? If so, 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.
• 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:
– ACwith{A ��C}
– DEwith{D ��E}
– ABDwith{AB ��D,AD ��B}
9 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
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}
10 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
2NF in S2 2018, you can skip this question when preparing for the final exam.
• 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.
• {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 of functional discussed 1NF anddependencies? Explain the reason.
11 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
As we have not discussed 2NF
in S2 2018, please ignore the sample solution to this question when preparing for
the final exam.
• Normalise MEETING into 2NF along OfficerID �� CustName:
– OFFICE(OfficeID, OfficeName) with the FD: OfficerID
– CUSTOMER(CustNo, CustName) with the FD: CustNo
– MEETING’(OfficerID, CustNo, Date, Time, Room) with the FDs:
�� OfficerID;
3. c (iv) [3 marks]
Normalise the relation schema MEETING into BCNF. Answer: There are several steps:
∗ OfficerID, Date
∗ CustNo, Date, Time ∗ Date, Time, Room
�� CustNo.
• Normalise MEETING’ into BCNF along OfficerID, Date
– MEETING”(OfficerID, Date, Room) with the FD: OfficerID, Date
�� – 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”’
12 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
�� OfficerName and CustNo
�� OfficerName �� CustName
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”?
• πname(σtitle=“T he Cat in the Hat”(BOOK) �� AUTHOR), or • πaid,name(σtitle=“T he 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.
• πname((πaid(σLanguage=“English”(BOOK))��πaid(σLanguage=“Japanese”(BOOK)))��
• πname((πaid(σLanguage=“English”(BOOK))∩πaid(σLanguage=“Japanese”(BOOK)))��
13 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
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))
14 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
4. b Evaluation [5 marks]
Suppose that we have the relations ANIMAL and COLOR shown in Figure 3.
ANIMAL COLOR ABCDE
1 white cat 2 brown rabbit 3 white bird 4 red bird
1 brown 2 white 3 blue
Figure 3: Relations ANIMAL and COLOR
Evaluate the following relational algebra expressions. Show your answer as a table, like those in Figure 3.
4. b (i) [1 mark]
Evaluate πC(σB=�white� (ANIMAL)). Answer:
C cat bird
4. b (ii) [1 mark]
Evaluate πB(ANIMAL) ∪ ρ(B)(πE(COLOR)). Answer:
brown red blue
15 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
4. b (iii) [1 mark]
Evaluate πA,C,E (ANIMAL ��B=E COLOR). Answer:
1 cat white
2 rabbit brown
3 bird white
4. b (iv) [2 marks]
Evaluate (σB=�white� (ANIMAL)) × πE(COLOR)
Answer: ABCE
1 white 1 white 1 white 3 white 3 white 3 white
cat brown cat white cat blue bird brown bird white bird blue
16 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
4. c Relational Algebra Operators [5 marks]
4. c (i) [1 mark]
List the six basic relational algebra operators that constitute a complete set in relational algebra.
1. selection σ;
2. projection π;
3. renaming ρ;
4. union ∪;
5. difference –;
6. Cartesian product ×.
4. c (ii) [1 mark]
Define the operator join in terms of the six basic operators in relational algebra. Answer:
• R 1 �� φ R 2 = σ φ ( R 1 × R 2 ) 4. c (iii) [1 mark]
Suppose that two relations R and Q have exactly the same schema. Which of the following statements are true in relational algebra?
1. R∩Q=R−(R−Q) 2. R∩Q=Q−(Q−R) 3. R∩Q=R×Q
4. R ∩ Q = R �� Q
• (1), (2) and (4)
17 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
4. c (iv) [2 marks]
Consider the following statements of relational algebra. Does each of them hold for any relation R? Justify your answer.
1. σA(σB(R)) = σB(σA(R)) Answer:
Yes, it holds by the commutativity property of σ.
2. πX(πY(R))=πX(R) Answer:
No, it only holds under the condition X ⊆ Y .
18 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
4. d Query Processing [4 marks]
Consider the following relation schemas:
• MOVIE(title, production year, country) with the primary key {title, production year};
• PERSON(id, first name, last name, year born) with the primary key {id}; • DIRECTOR(pid, title, production year) with the primary key {pid}
and the foreign keys:
[pid] ⊆ PERSON[id];
[title, production year] ⊆ MOVIE[title, production year]. 4. d (i) [2 marks]
Translate the following SQL query into a relational algebra expression, and then draw the query tree correspondingly.
SELECT MOVIE.title, PERSON.first name FROM MOVIE, PERSON, DIRECTOR
WHERE MOVIE.title = DIRECTOR.title AND DIRECTOR.pid=PERSON.id
AND MO V I E.country= ’USA’;
• Relational algebra expression:
– πMovie.title,Person.first name (σMovie.title=Director.title∧Director.pid=Person.id∧Movie.country=�USA� (MOVIE × DIRECTOR × PERSON))
19 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
4. d (ii) [2 marks]
Optimise your tree by applying at least two different transformation rules of relational algebra studied in lectures.
• Since country is an attribute of MOVIE, by the rule σφ(R1 �� R2) ≡ R1 ��
σφ(R2), if R1 is unaffected by φ, we have
– πMovie.title,Person.first name
(σM ovie.title=Director.title∧Director.pid=P erson.id (σcountry=�USA� (MOVIE) × DIRECTOR × PERSON))
• Since first name is an attribute of PERSON, by the rule πX (R1 �� R2) ≡ πX (πX1 (R1) �� πX2 (R2)), where Xi contains attributes both in Ri and X, and ones both in R1,
– πMovie.title,Person.first name
(σM ovie.title=Director.title∧Director.pid=P erson.id (πtitle,pid(σcountry=�USA�(MOVIE)×DIRECTOR)×πid,first name(PERSON)))
• Furtheroptimizationcanbeapplied,forexample,pushingtheselectioncondition Movie.title = Director.title ∧ Director.pid = Person.id down into the joins, i.e.,
– πMovie.title,Person.first name
(πtitle,pid(σcountry=�USA� (MOVIE) ��Movie.title=Director.title DIRECTOR) ��Director.pid=Person.id (πid,first name(PERSON)))
The general idea is to apply push-down selection and push-down projection.
20 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
Question 5: Transactions and Security [7 marks]
5. a [1 mark]
What are the ACID properties?
(1) atomicity, constant, isolation, durability (2) atomicity, consistency, isolation, duration (3) atomicity, consistency, isolation, durability (4) atomicity, consistency, indexing, durability (5) atomicity, constant, indexing, durability
Answer: (3)
5. b [2 marks]
Suppose that there is no concurrency control for the following transactions T1 and T2. What kind of problem can occur in this case?
T1 T2 readItem(Y)
writeItem(Y)
readItem(X)
readItem(Y)
writeItem(Y) readItem(X)
Answer: The dirty read problem. The explanation about how this problem might occur in this case should be provided (refer to the text book and the lecture notes).
21 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
5. c [2 marks]
Consider the following SQL code built by an application, in which the email address was entered by the user:
SELECT name, password FROM PERSON WHERE email =
Show how an SQL injection attack can happen in this case.
Answer: an SQL injection injects a string input through the Web application which
changes the SQL statement to their advantage.
SELECT name, password
FROM PERSON
WHERE email = OR ‘x’=‘x’;
5. d [2 marks]
Consider the table PROJECT that has been created in a relational database.
5. d (i) [1 mark]
Use SQL to give the read and update privileges on table PROJECT to Bob. Answer:
• grant SELECT, UPDATE on PROJECT TO Bob; 5. d (ii) [1 mark]
Use SQL to cancel Bob’s update privilege on table PROJECT. Answer:
• revoke UPDATE on PROJECT from Bob;
22 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
23 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
24 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
25 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)