Blog

INFO20003 Exam – Semester 1
Suggested Solutions and Marking Scheme
Oscar Correa and Colton Carner
July 2020
0.1 ER Modelling I (Exam Q8 – 15 marks)
0.1.1 VicRoads
VicRoads wants to upgrade its database and it hired you to be in charge of the design of the roadwor-
thiness certificates section. The relevant information is as follows:
Every vehicle has a registration number, and each vehicle is of a specific category.
VicRoads consider several categories, and each category is identified by code (e.g., LV for light
vehicles), maximum capacity, and average weight.
Several certified mechanics can issue roadworthiness certificates. You need to store the name,
driver’s license, address, phone number, and cost per hour of each mechanic.
Each mechanic is an expert on one or more vehicle category(ies), and his or her expertise may
overlap with that of other mechanics. This information about mechanics must also be recorded.
All mechanics belong to a union. You must store the union membership number of each mechanic.
You can assume that each mechanic is uniquely identified by her/his driver’s license as every
mechanic needs one to test the vehicle on the road.
VicRoads has several tests that are required whenever a vehicle is to be sold, re-registered, or to
clear some defect notices. Each test has a code (e.g., W&T) and a name (e.g., wheels and tyres),
and a minimum score.
VicRoads requires to store the issued certificates (one per vehicle). Each certificate comprises a set
of tests by a given mechanic. The information needed for each certificate is the date, the number
of hours the mechanic spent doing the test, and the score the vehicle received on each test.
Draw a conceptual model using Chen’s notation for the roadworthiness tests section. Be sure to
indicate the various attributes of each entity and relationship set; also specify the key and participation
constraints for each relationship set. Be sure to write down any assumptions you make.
Solution
Figure 1: VicRoads Conceptual Model
1
0.1.2 Record Label
A record label company wants to upgrade its albums database and it hires you to do the job. The
relevant information is as follows:
They want to keep information about singers, their names (which is unique), active since, whether
it’s a band or not.
For each album, the singer (band), the year it was recorded, its unique title, its cover photo, and
its price must be stored.
Genres and their hierarchy are also stored. Some genres have emerged from others. For example,
a genre can be the parent of 0 or many genres, and another genre can be the child of 0 or 1 genres.
Each genre is identified by a unique name.
A given album may belong to more than one genre, which could be at any level in the hierarchy.
Songs of each album are to be stored. For each song, the company stores its title and duration,
and the album/albums it belongs to, i.e., all songs must be in some album, but can be in many
albums.
Finally, the record company keeps the information about the managers. For each manager, the
company keeps the name, address, the total amount of dollars owed. Managers can manage multiple
artists and genres. We still store the managers even if they are no longer managing genres/artists.
Draw a conceptual model using Chen’s notation for the record label company. Be sure to indicate the
various attributes of each entity and relationship set; also specify the key and participation constraints
for each relationship set. Be sure to write down any assumptions you make.
Solution
Figure 2: Record Company Conceptual Model
Assumptions:
Album can be authored by more than one band/singer, e.g., compilation albums.
2
Marking Scheme
Total marks: 15
Entities: 5 marks
1 mark for each table
Deduct 1 mark for each unnecessary entity
Attributes: 5 marks
Max of 1 mark for each entity’s attributes (summed)
– 1 mark for each entity that has ALL attributes
– 0.5 for each entity that has some attributes
Correct Key Constraints: 2 marks
Correct Participation Constraints: 2 marks
Legibility: 1 mark
MARKER NOTE: Ensure that before taking marks off, you check if they have any reasonable as-
sumptions which allows them to change the constraints. E.g. do they make the assumption that Album
has only one band/singer
3
0.1.3 Toy Library (Supp. Exam)
You are hired to design the database model of a new toy library to be open here in Melbourne. Toy
libraries are non-profit organisations that give toys on loan to their members for a fixed period of time.
They rely on partnerships and volunteers to work. Memberships are on a yearly basis and they can be
renewed. The database application must store information as follows:
Every member has a unique ID, first name, last name and the date he/she joined the library.
A member should volunteer once a year to help arrange toys. A flag that indicates whether the
member has already volunteered in his/her membership year must be stored.
The names, sex, and dates of birth of each member’s children are also stored in the system.
Toys are classified into categories, have a unique ID, name and a short description.
A toy may be comprised of parts that are also stored. For example, a toy can be a ”Polar Igloo
Set” and one of its parts is a ”Chair”.
Each member can have up to 5 toys on loan, and at least two of them must be from the ”Puzzles”
category. The system must keep a record of the current loans of each member as well as the loan
history. The loan date, due date and the number of renewals of a toy must be stored. Also, a flag
indicating whether a toy has been returned is needed.
An important part of a toy library is sponsorship. The system must store information about the
sponsor’s name and address. More importantly, the system must store which toys were donated
by the sponsor and when.
Draw a conceptual model using Chen’s notation for the toy library. Be sure to indicate the various
attributes of each entity and relationship set; also specify the key and participation constraints for each
relationship set. Be sure to write down any assumptions you make.
Solution
Figure 3: Toy Library Conceptual Model
4
0.2 ER Modelling II (Exam Q9 – 8 marks)
0.2.1 Option 1
Write the CREATE TABLE statements resulting from the following conceptual model:
Figure 4: DDL Option 1
Be sure to specify primary and foreign keys. You NEED to specify whether the fields are NULL/NOT
NULL. Where the data type is not obvious, feel free to choose an appropriate data type.
Solution
CREATE TABLE A (
aid INT NOT NULL,
PRIMARY KEY (aid)
);
CREATE TABLE B (
bid INT NOT NULL,
PRIMARY KEY (bid)
);
CREATE TABLE C (
cid INT NOT NULL,
aid INT NOT NULL UNIQUE,
bid INT NOT NULL,
PRIMARY KEY (cid),
FOREIGN KEY (aid) REFERENCES A (aid),
FOREIGN KEY (bid) REFERENCES B (bid)
);
5
0.2.2 Option 2
Write the CREATE TABLE statements resulting from the following conceptual model:
Figure 5: DDL Option 2
Be sure to specify primary and foreign keys. You NEED to specify whether the fields are NULL/NOT
NULL. Where the data type is not obvious, feel free to choose an appropriate data type.
Solution
CREATE TABLE B (
bid INT NOT NULL,
PRIMARY KEY (bid)
);
CREATE TABLE C (
cid INT NOT NULL,
PRIMARY KEY (cid)
);
// need extra table rather than 2 optional FKs in A, since that
// would allow one to be null. Also need aid in this relationship so that we
// only allow for ternary relationships (a solution with a FK A to R and R with
// bid + cid only allows for a binary relationship between B+C in R
CREATE TABLE R (
aid INT NOT NULL,
bid INT NOT NULL,
cid INT NOT NULL,
// a needs to be unique
PRIMARY KEY (aid),
FOREIGN KEY (aid) REFERENCES A (aid),
FOREIGN KEY (bid) REFERENCES B (bid),
FOREIGN KEY (cid) REFERENCES C (cid)
);
CREATE TABLE A (
aid INT NOT NULL,
PRIMARY KEY (aid)
);
Note: other options for cases with more key constraints like option #4 won’t work here. . .
6
0.2.3 Option 3
Write the CREATE TABLE statements resulting from the following conceptual model:
Figure 6: DDL Option 3
Be sure to specify primary and foreign keys. You NEED to specify whether the fields are NULL/NOT
NULL. Where the data type is not obvious, feel free to choose an appropriate data type.
Solution
CREATE TABLE B (
bid INT NOT NULL,
PRIMARY KEY (bid)
);
CREATE TABLE C (
cid INT NOT NULL,
PRIMARY KEY (cid)
);
CREATE TABLE A (
aid INT NOT NULL,
bid INT NOT NULL,
cid INT NOT NULL,
PRIMARY KEY (aid),
FOREIGN KEY (bid) REFERENCES B (bid),
FOREIGN KEY (cid) REFERENCES C (cid)
);
7
0.2.4 Option 4
Write the CREATE TABLE statements resulting from the following conceptual model:
Figure 7: DDL Option 4
Be sure to specify primary and foreign keys. You NEED to specify whether the fields are NULL/NOT
NULL. Where the data type is not obvious, feel free to choose an appropriate data type.
Solution
CREATE TABLE A (
aid INT NOT NULL,
PRIMARY KEY (aid)
);
CREATE TABLE B (
bid INT NOT NULL,
PRIMARY KEY (bid)
);
CREATE TABLE C (
cid INT NOT NULL,
PRIMARY KEY (cid)
);
CREATE TABLE R (
aid INT NOT NULL UNIQUE,
bid INT NOT NULL UNIQUE,
cid INT NOT NULL UNIQUE,
PRIMARY KEY (aid, bid, cid),
FOREIGN KEY (aid) REFERENCES A (aid),
FOREIGN KEY (bid) REFERENCES B (bid),
FOREIGN KEY (cid) REFERENCES C (cid)
);
Alternative Solution I
CREATE TABLE A (
aid INT NOT NULL,
rid INT UNIQUE,
PRIMARY KEY (aid),
FOREIGN KEY (rid) REFERENCES B (rid),
FOREIGN KEY (rid) REFERENCES C (rid)
);
CREATE TABLE B (
bid INT NOT NULL,
rid INT UNIQUE,
PRIMARY KEY (bid),
— FOREIGN KEY (rid) REFERENCES A (rid),
— FOREIGN KEY (rid) REFERENCES C (rid)
);
CREATE TABLE C (
cid INT NOT NULL,
rid INT UNIQUE,
PRIMARY KEY (cid),
— FOREIGN KEY (rid) REFERENCES A (rid),
— FOREIGN KEY (rid) REFERENCES B (rid)
);
Alternative Solution II [requires constraining ids]
CREATE TABLE A (
aid INT NOT NULL,
rid INT UNIQUE,
PRIMARY KEY (aid),
— This requires that bid and cid are
— constrained…
FOREIGN KEY (rid) REFERENCES B (bid),
FOREIGN KEY (rid) REFERENCES C (cid)
);
CREATE TABLE B (
bid INT NOT NULL,
PRIMARY KEY (bid),
);
CREATE TABLE C (
cid INT NOT NULL,
PRIMARY KEY (cid),
);
8
Marking Scheme
Total marks: 8
Correct implementation of Key Constraints (FK positioning + UNIQUE) : 3 marks
– No demonstration of dealing with key constraints (even if many are ’incidentally’ correct): -2
marks
– Didn’t capture ternary relationship constraint that one set of (a,b,c) participates only once:
-1 mark
– Would have received 0 marks for this and next criteria (ie 0/6), but did have some FK notation
present: 1 mark
Correct implementation of Participation Constraint (NULL/NOT NULL): 3 marks
– No demonstration of dealing with participation constraints (even if many are ’incidentally’
correct): -2 marks
– Allowed for other binary relations in model (ie no participation constraint that ALL of a,b,c
participate in a relationship): -1 mark
Working table implementation (can store attributes): 1 marks
Uses correct syntax + PKs for tables: 1 mark
9
0.3 SQL
Australia has carried out several censuses. The following diagram shows the tables corresponding to
preferred means of transportation, residency location, and origins and destinations of the frequent trips.
Figure 8: Australia’s Censuses Model
Write a single SQL statement to correctly answer each of the following questions. DO NOT USE
VIEWS or VARIABLES to answer questions. Query nesting is allowed.
10
0.4 SQL I (Exam Q10 – 2 marks)
0.4.1 Option 1
How many different people, across all censuses, have said they live in Brunswick
Solution
SELECT COUNT(DISTINCT R.PID)
FROM residency AS R
NATURAL JOIN suburb AS S
WHERE S.SName = ’Brunswick’;
0.4.2 Option 2
How many different people, across all censuses, have said they prefer public transport
Solution
SELECT COUNT(DISTINCT PT.PID)
FROM preferredtransportation AS PT
NATURAL JOIN transportmeans AS TM
WHERE TM.TName = ’Public Transport’;
0.4.3 Option 3
How many different people, across all censuses, have said they frequently travel to Brunswick
Solution
SELECT COUNT(DISTINCT FT.PID)
FROM frequenttrip AS FT
INNER JOIN suburb AS S ON FT.to = S.SID
WHERE S.SName = ’Brunswick’;
Marking Scheme
Total marks: 2
Correct Answer: 2 marks
– Missing COUNT: -0.5
– Incorrect JOIN: -1
– Missing/Incorrect condition: -0.5
– Missing DISTINCT: -0.5
– Other error(s): -0.5 (each)
11
0.5 SQL II (Exam Q11 – 3 marks)
0.5.1 Option 1
List the name of the suburbs and the number of people who lives in each, according to the 2016 census,
ordered from the most to the least populated.
Solution
SELECT S.SName
, COUNT(R.PID)
FROM suburb AS S
NATURAL JOIN residency AS R
NATURAL JOIN censusrecord AS CR
WHERE CR.CRYear = 2016
GROUP BY
S.SName
ORDER BY
COUNT(R.PID) DESC;
MARKER NOTE: OK to group by S.SID instead, and thus have multiple rows with suburbs of the same
names. Grouping just by name as done above is OK too.
0.5.2 Option 2
List the name of the transport means and the number of people who use each, according to the 2016
census, ordered from the most to the least preferred.
Solution
SELECT TM.TName
, COUNT(PT.PID)
FROM transportmeans AS TM
NATURAL JOIN preferredtransportation AS PT
NATURAL JOIN censusrecord AS CR
WHERE CR.CRYear = 2016
GROUP BY
TM.TName
ORDER BY
COUNT(PT.PID) DESC;
Marking Scheme
Total marks: 3
Correct Answer: 3 marks
– Missing COUNT: -0.5
– Incorrect JOIN: -1.5
– Missing/Incorrect condition: -0.5
– Missing GROUP BY: -1
– Missing/Incorrect ORDER BY: -0.5
– Other error(s): -0.5 (each)
12
0.6 SQL III (Exam Q12 – 4 marks)
0.6.1 Option 1
It was found that the suburbs that are the worst affected by COVID-19 are Brunswick, Epping, and
Port Melbourne. Calculate how many different people, according to the 2016 census, frequently travels
from or to those suburbs.
Solution
SELECT COUNT(DISTINCT FT.PID)
FROM frequenttrip AS FT
NATURAL JOIN censusrecord AS CR
INNER JOIN suburb AS S_FROM ON FT.from = S_FROM.SID
INNER JOIN suburb AS S_TO ON FT.to = S_TO.SID
WHERE (
S_FROM.SName IN (’Brunswick’, ’Epping’, ’Port Melbourne’)
OR
S_TO.SName IN (’Brunswick’, ’Epping’, ’Port Melbourne’)
)
AND CR.CRYear = 2016;
0.6.2 Option 2
How many different people, according to the 2016 census, frequently travels from Brunswick to a suburb
other than Epping and Port Melbourne
Solution
SELECT COUNT(DISTINCT FT.PID)
FROM frequenttrip AS FT
NATURAL JOIN censusrecord AS CR
INNER JOIN suburb AS S_FROM ON FT.from = S_FROM.SID
INNER JOIN suburb AS S_TO ON FT.to = S_TO.SID
WHERE CR.CRYear = 2016
AND S_FROM.SName = ’Brunswick’
AND S_TO.SName NOT IN (’Epping’, ’Port Melbourne’);
0.6.3 Option 3
How many different people who live in Brunswick frequently travel to the CBD, according to the 2016
census
Solution
SELECT COUNT(DISTINCT R.PID)
FROM frequenttrip AS FT
NATURAL JOIN residency AS R
NATURAL JOIN censusrecord AS CR
INNER JOIN suburb AS S_LIVE ON R.SID = S_LIVE.SID
INNER JOIN suburb AS S_TO ON FT.to = S_TO.SID
WHERE CR.CRYear = 2016
AND S_LIVE.SName = ’Brunswick’
AND S_TO.SName = ’CBD’;
13
Marking Scheme
Total marks: 4
Correct Answer: 4 marks
– Missing COUNT: -0.5
– Incorrect JOIN: -2
– Missing/Incorrect condition: -1.5 (-0.5 for each)
– Other error(s): -0.5 (each)
14
0.7 SQL IV (Exam Q13 – 6 marks)
0.7.1 Option 1
Of people who prefer public transport, from which suburb do the largest number of different people make
frequent trips, according to the 2016 census
Solution
SELECT S_FROM.SName
, COUNT(FT.PID)
FROM frequenttrip AS FT
INNER JOIN suburb AS S_FROM ON FT.from = S_FROM.SID
NATURAL JOIN preferredtransportation
NATURAL JOIN censusrecord AS CR
NATURAL JOIN transportmeans AS TM
WHERE CR.CRYear = 2016
AND TM.TName = ’Public Transport’
GROUP BY
S_FROM.SName
ORDER BY
COUNT(FT.PID) DESC
LIMIT 1;
0.7.2 Option 2
Of people who prefer public transport, in which suburb do the largest number of different people live,
according to the 2016 census
Solution
SELECT S.SName
, COUNT(R.PID)
FROM residency AS R
NATURAL JOIN suburb AS S
NATURAL JOIN preferredtransportation
NATURAL JOIN censusrecord AS CR
NATURAL JOIN transportmeans AS TM
WHERE CR.CRYear = 2016
AND TM.TName = ’Public Transport’
GROUP BY
S.SName
ORDER BY
COUNT(R.PID) DESC
LIMIT 1;
Marking Scheme
Total marks: 6
Correct Answer: 6 marks
– Missing COUNT: -0.5
– Incorrect JOIN: -3
– Missing/Incorrect condition: -1 (-0.5 for each)
– Missing GROUP BY: -1
– Missing/Incorrect ORDER BY: -0.5
– Missing LIMIT: -1
– Other error(s): -0.5 (each)
15
0.8 SQL III (Supp. Exam)
0.8.1 Option 1
How many people have reported in the 2016 census to live in more residencies compared with

what they
reported in the 2011 census
IMPORTANT: Consider also people who did not report in the 2011 census but they did in 2016.
HINT: You can use the IFNULL() function.
Solution
SELECT COUNT(*)
FROM (
SELECT COUNT(R.SID) no_2016, R.PID
FROM residency AS R NATURAL JOIN censusrecord AS CR
WHERE CR.CRYear = 2016
GROUP BY
R.PID
) AS R_2016 LEFT JOIN
(
SELECT COUNT(R.SID) no_2011, R.PID
FROM residency AS R NATURAL JOIN censusrecord AS CR
WHERE CR.CRYear = 2011
GROUP BY
R.PID
) AS R_2011 ON R_2016.PID = R_2011.PID
WHERE
R_2016.no_2016 – IFNULL(R_2011.no_2011, 0) > 0;
0.8.2 Option 2
How many people have reported a greater number of preferred transportation means in the 2016 census
compared with what they reported in the 2011 census
IMPORTANT: Consider also people who did not report in the 2011 census but they did in 2016.
HINT: You can use the IFNULL() function.
Solution
SELECT COUNT(*)
FROM (
SELECT COUNT(PT.TID) no_2016, PT.PID
FROM preferredtransportation AS PT NATURAL JOIN censusrecord AS CR
WHERE CR.CRYear = 2016
GROUP BY
PT.PID
) AS PT_2016 LEFT JOIN
(
SELECT COUNT(PT.TID) no_2011, PT.PID
FROM preferredtransportation AS PT NATURAL JOIN censusrecord AS CR
WHERE CR.CRYear = 2011
GROUP BY
PT.PID
) AS PT_2011 ON PT_2016.PID = PT_2011.PID
WHERE
PT_2016.no_2016 – IFNULL(PT_2011.no_2011, 0) > 0;
16
0.8.3 Marking Scheme
Total marks: 4
Correct Answer: 4 marks
– Missing COUNT: -0.5
– Incorrect JOIN: -2
– Missing/Incorrect condition: -1
– Do not consider when there is no records in 2011: -0.5
– Other error(s): -0.5 (each)
17
0.9 SQL IV (Supp. Exam)
0.9.1 Option 1
What is the means of transportation preferred the most by people who frequently travel to Brunswick,
according to the 2016 census
IMPORTANT: There may be more than one transportation means. If that is the case, all must be
shown.
Solution
SELECT TM.TName
FROM preferredtransportation AS PT
NATURAL JOIN transportmeans TM
NATURAL JOIN censusrecord AS CR
NATURAL JOIN frequenttrip AS FT
INNER JOIN suburb AS S ON FT.to = S.SID
WHERE CR.CRYear = 2016
AND S.SName = ’Brunswick’
GROUP BY
PT.TID
HAVING COUNT(PT.PID) =
(
SELECT MAX(TM_BRWK.no_people)
FROM (
SELECT COUNT(PT.PID) no_people
FROM preferredtransportation AS PT
NATURAL JOIN censusrecord AS CR
NATURAL JOIN frequenttrip AS FT
INNER JOIN suburb AS S ON FT.to = S.SID
WHERE CR.CRYear = 2016
AND S.SName = ’Brunswick’
GROUP BY
PT.TID
) AS TM_BRWK
);
0.9.2 Option 2
What is the means of transportation preferred the most by people who frequently travel from Brunswick,
according to the 2011 census
IMPORTANT: There may be more than one transportation means. If that is the case, all must be
shown.
Solution
SELECT TM.TName
FROM preferredtransportation AS PT
NATURAL JOIN transportmeans TM
NATURAL JOIN censusrecord AS CR
NATURAL JOIN frequenttrip AS FT
INNER JOIN suburb AS S ON FT.from = S.SID
WHERE CR.CRYear = 2011
AND S.SName = ’Brunswick’
GROUP BY
PT.TID
HAVING COUNT(PT.PID) =
18
(SELECT MAX(TM_BRWK.no_people)
FROM (
SELECT COUNT(PT.PID) no_people
FROM preferredtransportation AS PT
NATURAL JOIN censusrecord AS CR
NATURAL JOIN frequenttrip AS FT
INNER JOIN suburb AS S ON FT.from = S.SID
WHERE CR.CRYear = 2011
AND S.SName = ’Brunswick’
GROUP BY
PT.TID
) AS TM_BRWK
);
19
0.10 RA I (Exam Q14 – 2 marks)
Based on the same diagram above (i.e., Australia censuses), write a relational algebra expression for each
of the following questions:
0.10.1 Option 1
List the DOB of people whose residency is in Brunswick, according to the 2011 census.
Solution
Any of these:
piDOB(((σSName=′BSW ′(S) ./ R) ./ σCRY ear=2011(CR)) ./ P )
piDOB(σSName=′BSW ′∧CRY ear=2011((S ./ R) ./ CR) ./ P )
piDOB(σSName=′BSW ′∧CRY ear=2011(((S ./ R) ./ CR) ./ P ))
MARKER NOTE: Also consider conditional joins if correct, could include the selection criteria.
0.10.2 Option 2
List the DOB of people whose preferred means of transportation is public transport, according to the
2016 census.
Solution
Any of these:
piDOB(((σTName=′PT ′(TM) ./ PT ) ./ σCRY ear=2016(CR)) ./ P )
piDOB(σTName=′PT ′∧CRY ear=2016((TM ./ PT ) ./ CR) ./ P )
piDOB(σTName=′PT ′∧CRY ear=2016(((TM ./ PT ) ./ CR) ./ P ))
MARKER NOTE: Also consider conditional joins if correct, could include the selection criteria.
Marking Scheme
Total marks: 2
Correct / Logically Equivalent Answer: 2 marks
– Correct projection: +0.5
– Correct selections: +0.5
– Correct joins: +1
20
0.11 RA II (Exam Q15 – 3 marks)
Based on the same diagram above (i.e., Australia censuses), write a relational algebra expression for each
of the following questions:
0.11.1 Option 1
List the DOB of people who prefer public transport and frequently travel to ’Brunswick’, according to
the 2016 census.
Solution
piDOB(((((σTName=′PT ′(TM) ./ PT ) ./ σCRY ear=2016(CR)) ./ FT ) ./to=SID σSName=′BSW ′(S)) ./ P )
MARKER NOTE: Also consider conditional joins if correct, could include the selection criteria.
0.11.2 Option 2
List the DOB of people who live in ’Brunswick’ and prefer public transport, according to the 2016 census.
Solution
piDOB(((((σSName=′BSW ′(S) ./ R) ./ σCRY ear=2016(CR)) ./ PT ) ./ σTName=′PT ′(TM)) ./ P )
MARKER NOTE: Also consider conditional joins if correct, could include the selection criteria.
Marking Scheme
Total marks: 3
Correct / Logically Equivalent Answer: 3 marks
– Correct projection: +0.5
– Correct selections: +1
– Correct joins: +1.5
21
0.12 Query Processing – Join (Exam Q16 – 6 marks)
0.12.1 Option 1
Consider two relations called Customer and DocumentHeader. Imagine that the relation Customer has
250 pages and DocumentHeader has 1000 pages. Consider the following SQL statement:
SELECT *
FROM Customer LEFT JOIN DocumentHeader
ON Customer.CID = DocumentHeader.CID
WHERE Customer.CName = ’ACME’;
There are 502 buffer pages available in memory. Both relations are stored as simple heap files. Neither
relation has any indexes built on it.
Evaluate block-oriented NLJ, SMJ and HJ using the number of disk I/O’s as the cost. Provide the
formulae you use to calculate your cost estimates.
Which join would be the optimizer’s choice Consider Customer as the outer relation in all alterna-
tives. Assume that sorting can be performed in two passes for both relations. All selections are performed
on-the-fly after the join.
Solution
NPages(C) = 250, NPages(DH) = 1000, B = 502, NBlocks(C) = 1
CostBNLJ = NPages(C) +NBlocks(C)×NPages(DH)
CostBNLJ = 250 + 1× 1000 = 1250 I/Os
CostSMJ = CostSORT (C) + CostSORT (DH) + CostMERGE(C,DH)
CostSORT (C) = 2× 2×NPages(C)
CostSORT (DH) = 2× 2×NPages(DH)
CostMERGE(C,DH) = NPages(C) +NPages(DH)
CostSMJ = 2× 2× 250 + 2× 2× 1000 + 250 + 1000 = 6250 I/Os
CostHJ = 3×NPages(C) + 3×NPages(DH)
CostHJ = 3× 250 + 3× 1000 = 3750 I/Os
Optimizer’s choice would be BNLJ.
0.12.2 Option 2
Consider two relations called DocumentHeader and DocumentDetail. Imagine that the relation Docu-
mentHeader has 1000 pages and DocumentDetail has 10000 pages. Consider the following SQL statement:
SELECT *
FROM DocumentHeader RIGHT JOIN DocumentDetail
ON DocumentHeader.DID = DocumentDetail.DID
WHERE DocumentHeader.DType = ’Cheque’;
There are 502 buffer pages available in memory. Both relations are stored as simple heap files. Neither
relation has any indexes built on it.
Evaluate block-oriented NLJ, SMJ and HJ using the number of disk I/O’s as the cost. Provide the
formulae you use to calculate your cost estimates.
Which join would be the optimizer’s choice Consider DocumentHeader as the outer relation in all
alternatives. Assume that sorting can be performed in three passes for both relations. All selections are
performed on-the-fly after the join.
22
Solution
NPages(DH) = 1000, NPages(DD) = 10000, B = 502, NBlocks(DH) = 2
CostBNLJ = NPages(DH) +NBlocks(DH)×NPages(DD)
CostBNLJ = 1000 + 2× 10000 = 21000 I/Os
CostSMJ = CostSORT (DH) + CostSORT (DD) + CostMERGE(DH,DD)
CostSORT (DH) = 2× 3×NPages(DH)
CostSORT (DD) = 2× 3×NPages(DD)
CostMERGE(DH,DD) = NPages(DH) +NPages(DD)
CostSMJ = 2× 3× 1000 + 2× 3× 10000 + 1000 + 10000 = 77000 I/Os
CostHJ = 3×NPages(DH) + 3×NPages(DD)
CostHJ = 3× 1000 + 3× 10000 = 33000 I/Os
Optimizer’s choice would be BNLJ.
Marking Scheme
Total marks: 6
Correct calculation of BNLJ: 2 marks
– Some good work: 0.5 marks
Correct calculation of SMJ: 2 marks
– Some good work: 0.5 marks
Correct calculation of HJ: 1 mark
Correct lowest cost [NO consequential marks]: 1 mark
0.12.3 Option 3 (Supp. Exam)
Consider two relations called DocumentHeader and DocumentDetail. Imagine that the relation Docu-
mentHeader has 500 pages and DocumentDetail has 10000 pages. Consider the following SQL statement:
SELECT *
FROM DocumentHeader LEFT JOIN DocumentDetail
ON DocumentHeader.DID = DocumentDetail.DID
WHERE DocumentHeader.DType = ’Cheque’;
There are 502 buffer pages available in memory. Both relations are stored as simple heap files. Neither
relation has any indexes built on it.
Evaluate block-oriented NLJ, SMJ and HJ using the number of disk I/O’s as the cost. Provide the
formulae you use to calculate your cost estimates.
Which join would be the optimizer’s choice Consider DocumentHeader as the outer relation in all
alternatives. Assume that sorting can be performed in two passes for both relations. All selections are
performed on-the-fly after the join.
Solution
NPages(DH) = 500, NPages(DD) = 10000, B = 502, NBlocks(DH) = 1
CostBNLJ = NPages(DH) +NBlocks(DH)×NPages(DD)
CostBNLJ = 500 + 1× 10000 = 10500 I/Os
CostSMJ = CostSORT (DH) + CostSORT (DD) + CostMERGE(DH,DD)
23
CostSORT (DH) = 2× 2×NPages(DH)
CostSORT (DD) = 2× 2×NPages(DD)
CostMERGE(DH,DD) = NPages(DH) +NPages(DD)
CostSMJ = 2× 2× 500 + 2× 2× 10000 + 500 + 10000 = 52500 I/Os
CostHJ = 3×NPages(DH) + 3×NPages(DD)
CostHJ = 3× 500 + 3× 10000 = 31500 I/Os
Optimizer’s choice would be BNLJ.
24
0.13 Query Processing – Extra index change cost (Exam Q17 –
2 marks)
Would the cost of Sort-Merge Join have changed if we would have had an unclustered B+ tree index
created on the attribute in the WHERE condition If yes, explain how (no need to recalculate). If no,
explain why.
Solution
There are three accepted answers:
1. No effect. Unclustered indexes = data file not sorted so not going to affect SMJ.
2. No effect. Index is not on the join attribute so even if sorted not going to affect SMJ.
3. Yes. The data could be filtered before the join takes place, reducing the number of pages entering
the SMJ.
Marking Scheme
Total marks: 2
Correct Answer & Reason: 2 marks
– Gave incorrect reason: 0/2 marks
25
0.14 Query Processing – Indexes Question
0.14.1 Option 1
Consider a relation called Loans that stores information about loans given by a bank. Imagine that the
relation Loans consists of 800 pages and each page stores 50 tuples. Imagine that the catalog manager
provides statistics about the distribution of some attributes of this relation as the following:
Type: {’A’: 10%, ’B’: 30%, ’C’: 45%, ’D’: 15%}
ApprovalYear: {2018: 10%, 2019: 60%, 2020: 30%}
Suppose that the following SQL query is executed frequently using the given relation:
SELECT Type
FROM Loans
WHERE Type IN (’B’, ’C’)
AND ApprovalYear > 2019;
0.14.2 Option 2
Consider a relation called Loans that stores information about loans given by a bank. Imagine that the
relation Loans consists of 500 pages and each page stores 100 tuples. Imagine that the catalog manager
provides statistics about the distribution of some attributes of this relation as the following:
Type: {’A’: 10%, ’B’: 25%, ’C’: 45%, ’D’: 15%, ’E’: 5%}
ApprovalYear: {2017: 10%, 2018: 40%, 2019: 40%, 2020: 10%}
Suppose that the following SQL query is executed frequently using the given relation:
SELECT Type
FROM Loans
WHERE Type IN (’B’, ’C’)
AND ApprovalYear > 2018;
0.14.3 Option 3 (Supp. Exam)
Consider a relation called Loans that stores information about loans given by a bank. Imagine that the
relation Loans consists of 1000 pages and each page stores 50 tuples. Imagine that the catalog manager
provides statistics about the distribution of some attributes of this relation as the following:
Type: {’A’: 10%, ’B’: 25%, ’C’: 45%, ’D’: 15%, ’E’: 5%}
ApprovalYear: {2017: 10%, 2018: 40%, 2019: 40%, 2020: 10%}
Suppose that the following SQL query is executed frequently using the given relation:
SELECT Type
FROM Loans
WHERE Type IN (’B’, ’C’)
AND ApprovalYear > 2017;
26
0.15 Query Processing – Indexes I (Exam Q18 – 2 marks)
Compute the estimated result size (in number of tuples) for the query, and the reduction factor of each
predicate.
0.15.1 Solution Option 1
RF(Type IN (’B’, ’C’)) = 0.75
RF(ApprovalYear > 2019) = 0.3
Result size = 800 * 50 * 0.75 * 0.3 = 9,000 tuples
0.15.2 Solution Option 2
RF(Type IN (’B’, ’C’)) = 0.7
RF(ApprovalYear > 2018) = 0.5
Result size = 500 * 100 * 0.7 * 0.5 = 17,500 tuples
0.15.3 Solution Option 3
RF(Type IN (’B’, ’C’)) = 0.7
RF(ApprovalYear > 2017) = 0.9
Result size = 1000 * 50 * 0.7 * 0.9 = 31,500 tuples
0.15.4 Marking Scheme
Total marks: 2
Correct Results: 2 marks
– 1 error (forgive consequential errors): 1/2 marks
27
0.16 Query Processing – Indexes II (Exam 19 – 2 marks)
0.16.1 Option 1
Compute the estimated cost of plan alternatives and state which plan is the best assuming that an
unclustered B+ tree index on (ApprovalYear) is (the only index) available. Suppose there are 100
index pages.
Solution Option 1
Cost = (100 + 800 * 50) * 0.3 = 12,030 I/Os
HeapScan = 800 I/Os
Best option is Heap Scan
Solution Option 2
Cost = (100 + 500 * 100) * 0.5 = 25,050 I/Os
HeapScan = 500 I/Os
Best option is Heap Scan
Solution Option 3
Cost = (100 + 1000 * 50) * 0.9 = 45,090 I/Os
HeapScan = 1000 I/Os
Best option is Heap Scan
0.16.2 Option 2
Compute the estimated cost of plan alternatives and state which plan is the best assuming that a
clustered B+ tree index on (ApprovalYear) is (the only index) available. Suppose there are 100 index
pages.
Solution Option 1
Cost = (100 + 800) * 0.3 = 270 I/Os
HeapScan = 800 I/Os
Best option is Index Scan
Solution Option 2
Cost = (100 + 500) * 0.5 = 300 I/Os
HeapScan = 500 I/Os
Best option is Index Scan
Solution Option 3
Cost = (100 + 1000) * 0.9 = 990 I/Os
HeapScan = 1000 I/Os
Best option is Index Scan
0.16.3 Marking Scheme
Total marks: 2
Correct Index Scan Cost: 1 mark
Identifies HS as option + states HS cost + chooses best: 1 mark
28
0.17 Query Processing – Indexes III (Exam Q20 – 2 marks)
What would happen if our query changed and became:
SELECT *
FROM Loans
WHERE 2018 < ApprovalYear AND ApprovalYear < 2020 AND Type IN (’B’, ’C’); Will this change impact the result size If yes, calculate the new result size. If no, explain why. 0.17.1 Solution Option 1 Yes, it will change the result size. [Unchanged] RF(Type IN (’B’, ’C’)) = 0.75 [New] RF(2020 > ApprovalYear > 2018) = 0.6
Result size = 800 * 50 * 0.75 * 0.6 = 18,000 tuples
0.17.2 Solution Option 2
Yes, it will change the result size.
[Unchanged] RF(Type IN (’B’, ’C’)) = 0.7
[New] RF(2020 > ApprovalYear > 2018) = 0.4
Result size = 500 * 100 * 0.7 * 0.4 = 14,000 tuples
0.17.3 Marking Scheme
Total marks: 2
”Yes it will change the result size”: 1 marks
Correct new result size calculated: 1 marks
29
0.18 Query Optimization
0.18.1 Option 1
Consider three relations called Account, AccountDetail, and TransactionType. Imagine that the relation
Account has 500 pages, AccountDetail has 5000 pages, and TransactionType has 100 pages. Each page
stores 100 tuples. The AccountType attribute has values in the set {’Savings’, ’CreditCard’}. There is a
clustered B+ tree index on AccountType, which is 100 pages in size. Consider the following query:
SELECT *
FROM Account AS A, AccountDetail AS AD, TransactionType AS TT
WHERE A.Account_ID = AD.Account_ID AND AD.TranType_ID = TT.TranType_ID
AND A.AccountType = ’Savings’;
0.18.2 Option 2
Consider three relations called Account, AccountDetail, and TransactionType. Imagine that the relation
Account has 250 pages, AccountDetail has 5000 pages, and TransactionType has 50 pages. Each page
stores 100 tuples. The AccountType attribute has values in the set {’Savings’, ’CreditCard’}. There is a
clustered B+ tree index on AccountType, which is 50 pages in size. Consider the following query:
SELECT *
FROM Account AS A, AccountDetail AS AD, TransactionType AS TT
WHERE A.Account_ID = AD.Account_ID AND AD.TranType_ID = TT.TranType_ID
AND A.AccountType = ’Savings’