Please refer to questions in slides, labs and assignments for more examples. More details about the final exam will be given in week 12.
THE AUSTRALIAN NATIONAL UNIVERSITY
Second Semester Examination – November 2012
RELATIONAL DATABASES
Copyright By PowCoder代写 加微信 powcoder
(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: 2 3
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,
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 queries 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]
6 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
•
•
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 ADandD 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}
– ABD with {AB D,AD
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)
• {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.
2NF in oSu2r2c0our,se, 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.
11 of 25 – RELATIONAL DATABASES – (COMP2400/COMP6240)
As we have not discussed 2NF in lSe2ct2u0res, 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 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”’
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)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com