COMP207 Assignment 2 – Query Processing
Page 1 of 6


COMP207 Assignment 2 – Query Processing
Issue Date: Monday, 18 November 2019
Submission Deadline: Tuesday, 03 December 2019, 17:00

About This Assignment
This is the second of two assignments for COMP207. It is worth 10% of the total marks
for this module. It consists of four questions, which you can find at the end of this
document.
Submit your solutions to these questions in PDF format by the given submission deadline.
Your solutions must be submitted on Vital (see the detailed submission instructions below).
Accuracy and relevance are more important in your answers, so don’t write large volumes in
your submission, but do ensure that what you write covers what is asked for and keeps to the
problem statement.

Submission Details
Please submit one PDF file with your solutions. Name your file as follows:
-Assignment-2.pdf

If your student ID is 12345678, then your file should be named:
12345678-Assignment-2.pdf.

Please submit only this file (no archives).

To act as your ‘signature’ for the assignment, at the top of your PDF document put your
Student ID number.
COMP207 Assignment 2 – Query Processing
Page 2 of 6


Your solutions must be submitted on Vital (see Vital for submission instructions).

The submission deadline for this assignment is Tuesday, 03 December 2019, 17:00. Earlier
submission is possible, but any submission after the deadline attracts the standard lateness
penalties. Plagiarism and collusion guidelines will apply throughout the assignment
submission. For details on late submissions, how to claim extenuating circumstances, etc.,
please see the undergraduate student handbook, which can be found at
http://intranet.csc.liv.ac.uk/student/ug-handbook.pdf , or in Section 6 of the Code of Practice
on Assessment.1

Assessment information at a glance

Assignment Number 2 (of 2)

Assignment Circulated Monday, 18 November 2019

Submission Mode Electronically on Vital

Purpose of Assessment Assessment of knowledge of SQL query processing



Submission necessary in N/A
order to satisfy module
requirements?




1 https://www.liverpool.ac.uk/media/livacuk/tqsd/code-of-practice-on-
assessment/code_of_practice_on_assessment.pdf










Weighting 10% of the final module mark
Deadline Tuesday, 03 December 2019, 17:00
LO2: Demonstrate an understanding of advanced SQL topics Learning Outcome Assessed
Marking Criteria See description of this assignment
Late Submission Penalty Standard UoL Policy
COMP207 Assignment 2 – Query Processing
Page 3 of 6


Question 1 (10 marks)

The following tables form part of a hotel booking database held in a relational DBMS
(primary keys are underlined):

Hotel (hotelNo, hotelName, city)
Room (roomNo, hotelNo, type, price)
Booking (hotelNo, guestNo, dateFrom, dateTo, roomNo)
Guest (guestNo, guestName, guestAddress)

• Hotel contains hotel details and hotelNo is the primary key.
• Room contains room details for each hotel and (roomNo, hotelNo) forms the primary
key.
• Booking contains details of the bookings and (hotelNo, guestNo, dateFrom) forms the
primary key.
• Guest contains guest details and guestNo is the primary key.

Give the relational algebra expressions to return the results for the following two queries:
(a) List the names and cities of those hotels who charge more than £85 for a room. (5 marks)
(b) List the names and addresses of guests who have made a booking to stay Christmas Day
2019. (5 marks)


























COMP207 Assignment 2 – Query Processing
Page 4 of 6



Question 2 (10 marks)
Consider the following database schema and example instance for a property management
system:
property

pId price owner sqrFeet location
1 100,000 Alice 560 Lake View
2 3,400,000 Bob 2,000 Hyde Park
3 1,200,000 Bob 1,200 Hyde Park
4 5,000,000 Martha 800 Evanston

repairs

rId pId company date type
1001 1 M.M. Plumbing Ltd. 2013-12-12 Bathroom
1002 2 M.M. Plumbing Ltd. 2013-12-13 Kitchen
1003 4 Rob’s Double Glazing 2012-01-01 Windows

Hints:
• Attributes with a grey background form the primary key of a relation (e.g, pId for relation
property).
• The attribute pId of relation repairs is a foreign key to relation property.


Give the relational algebra expressions to return the results for the following two queries:
(a) Get the pId, owner and location details of all properties that are larger than 900 square feet
(sqrFeet). (5 marks)
(b) Get the names of repair companies (company) that did a repair on a property in Hyde
Park. (5 marks)

COMP207 Assignment 2 – Query Processing
Page 5 of 6


Question 3 (20 marks)
(a) Consider the following relation:
studentCourses(StudentID, CourseNo, Quarter, Year, Units, Grade)

The relation contains the grades for the courses completed by students. Assume that in
studentCourses there are 200,000 different students, each identified by their StudentID. On
average, a student took 40 different courses.

If the file blocks hold 2000 bytes and each studentCourses tuple requires 50 bytes, how many
blocks will then be needed to store the relation studentCourses? (5 marks)

(b) A database includes two relations Student (S) and Program (P).
S P


Give a relational expression that could possibly return the following result:


F_Name L_Name P_Name
Alicia Smith Computing
John Smith Computing
(5 marks)

(c) Translate the following relational algebra into SQL:
πstudId,lName(Ϭ course=’BSc’(STUDENT)) (5 marks)

(d) Given these relations, write the SQL statement that produced the equivalent queries below:
Course (courseNo, courseDept, courseLeader)
Student (studNo, name, type, tutorId, courseNo)
Two sample equivalent corresponding queries have been produced:

πstudno,name(Ϭ(type=’undergrad’)^(courseDept=’CompSci’)(Student⋈s.courseNo=c.courseNo Course))
and
πstudno,name(Ϭ type=’undergrad’(Student))⋈s.courseNo=c.courseNo(Ϭ courseDept=’Comp Sci’(Course))
(5 marks)
Prog_Code P_Name
0001 Computing
0002 Software Engineering
Student_No F_Name L_Name Prog_Code
04009991 Alicia Smith 0001
04009992 Alan Smith 0002
04009995 Alicia Bush 0001
04009996 John Smith 0001

COMP207 Assignment 2 – Query Processing
Page 6 of 6


Question 4 (60 marks)
Consider a database with relations R(A, B,C), S(D, E), and T (F, G).
(a) Give the initial query plan (constructed as in Lecture 13) for the SQL query
SELECT B, E, G
FROM R, S, T
WHERE A = 10 AND C = D AND E = F AND A > G;
Then use the heuristics from Lecture 16 to transform the initial query plan into an optimised (logical)
query plan. Perform the transformation step-wise, pushing a single operator over a single operator in
each step, and indicate the heuristics you apply. (20 marks)
(b) Suppose that
• |R| = 1000, |πA(R)| = 1000, |πB(R)| = 100, |πC(R)| = 500;
• |S| = 5000, |πD(S)| = 300, |πE (S)| = 10;
• |T | = 4000, |πF (T )| = 4000, |πG(T )| = 1500.
Estimate the number of tuples returned by the following queries. Explain your calculations.
i) σA=10(R) (6 marks)
ii) σA=10 OR B=b(R) (6 marks)
iii) R ⋈C=D S (6 marks)
(c) Suppose that in addition to the assumptions on R, S, and T from part (ii), we also have the following:
• Each disk block can hold up to 10 tuples.
• All relations are stored in consecutive blocks on disk.
• No indexes are available.
What is the best physical query plan (in terms of the number of disk access operations) you can find for
σB=b AND E=100(R ⋈C=D S)? Describe your plan and show the calculation of the number of disk access
operations. (22 marks)