2020/3/24 CSCI 370 Spring 2020 - Assignment 4
csci.viu.ca/~liuh/370/assignments/A4.html 1/4
CSCI 370 Spring 2020 - Assignment 4
Due: 13:00, 9 April 2020, Thursday
This assignment is worth 6% of your overall course grade.
Questions:
1. Given an instance of a relation R where A and B are two of the attributes in R, describe
an algorithm that checks whether a functional dependency A → B holds on R.
2. Given a relation with schema R(A, B, C, D, E) and a set of FD's F = {AD → E, AB → C, C →
D, E → B}.
a. List all the candidate keys of R?
b. R is not in BCNF. Why?
c. Find a lossless join decomposition to decompose R into collections of relations that
are in BCNF.
d. Is R in third normal form? Justify your answer.
3. Suppose that you are the DBA of the HR schema (used in our lab exercises).
a. Define a view called DeptInfo with attributes departmentName staffCount and averageSalary
which lists the name of each department, the number of employees working in this
department and the average salary of these employees. If a department doesn't
have any employees, the staff count and the average salary should both be zero.
Order the result according to the department name ascending.
b. Write a SQL command to let everyone who has a database account to be able to
read the data in DeptInfo.
c. Write a SQL command to let a user with the user name "millerks" to be able to read
the relation Employees and update records in Employees but not add records into or
delete records from Employees.
d. Write a SQL command to let the user "millerks" to have the authority to allow other
users to read the Employees table.
4. For each of the following two schedules:
i. R4(y);R4(z);W1(x); R1(z);W3(x);R2(x); R3(y);R1(y);W3(y); W2(x);W4(x);R2(z); W2(y);R1(y);
ii. R3(y);R2(y);R4(z); R3(y);W4(z);R4(x); R1(z);W4(x);R3(z); R2(x);W2(x);R1(x); W2(y);W1(x);
Answer the following questions:
a. Draw the precedence (serialization) graph for the schedule.
b. Is the schedule conflict-serializable? If your answer is yes, list all the equivalent
serial schedules. If your answer is no, which transaction(s) should be aborted to
make the schedule conflict-serializable?
c. Is the schedule recoverable and/or cascadeless? Justify your answer.
5. Suppose a scheduler's job is to output cascadeless schedules. Design 4 sequences of
requests where
in the first sequence, every request will be executed immediately;
in the second sequence, at least one request will be delayed;
in the third sequence, at least one request will be ignored; and
in the fourth sequence, at least one request will be denied. These 4 sequences don't
need to be related.
2020/3/24 CSCI 370 Spring 2020 - Assignment 4
csci.viu.ca/~liuh/370/assignments/A4.html 2/4
6. When a database system restarts, the following log file is loaded into the system, where
T1, T2, T3, and T4 are three transactions, and u, v, w, and x are four database objects.
Start of the log ⇒ T1, begin
T1, u, 31.5, 27.3
T1, v, 'FALSE', 'TRUE'
T2, begin
T2, w, 15, 0
T1, u, 27.3, 34.2
T2, x, 80, 20
T2, w, 0, -10
T3, begin
T2, commit
T3, x, 20, 60
T3, abort
T2, end
T1, x, 20, 60
T4, begin
T3, end
End of the log ⇒ T4, w, -10, 15
a. Inferring from the above WAL log, try to determine which isolation level
(serializable, repeatable read, read committed or read uncommitted) the database
ran on before the crash. Briefly justify your answer.
b. Can the scheduler generates a schedule that's consistent with the above WAL log
using strict 2PL (strict two phase locking) protocol? How about if the scheduler
used 2PL (two phase locking) protocol? Justify your answer.
c. Regardless whether the schedule is a cascadeless schedule, if the recovery manager
still uses ARIES algorithm to recover from the crash, what would be the values
stored in the database objects u, v, w and x respectively after the recovery is
successfully completed?
7. A database table, Customers, has many columns. Two of these columns are customer_id
and last_name. The following 25 tuples are inserted into this table:
customer_id last_name other columns
1001 Smith ...
1002 Brown ...
1003 Tremblay ...
1004 Martin ...
1005 Roy ...
1006 Wilson ...
2020/3/24 CSCI 370 Spring 2020 - Assignment 4
csci.viu.ca/~liuh/370/assignments/A4.html 3/4
1007 Macdonald ...
1008 Gagnon ...
1009 Johnson ...
1010 Taylor ...
1011 Cote ...
1012 Campbell ...
1013 Anderson ...
1014 Leblanc ...
1015 Lee ...
1016 Jones ...
1017 White ...
1018 Williams ...
1019 Miller ...
1020 Thompson ...
1021 Gauthier ...
1022 Young ...
1023 Van ...
1024 Morin ...
1025 Bouchard ...
You are asked to construct two B+ tree indices on the table Customers. One is a primary
index using customer_id as the search key, and the other a secondary index using
last_name as the search key.
Suppose that, no matter what data to be stored on each page, each leaf node can hold
at most 4 data items and 2 page pointers, and each internal node can hold at most 4
search keys and 5 pointers.
Draw these two B+ tree indices.
How to Submit
Submit a hard copy of your solution before the submit deadline. Make your answer precise
and concise. Make your document easily understandable.
If you prefer to submit your assignment electronically, you can login to otter and go to the
directory that has the file(s) you want to submit, and run the following command:
~liuh/bin/submit 370 A4 .
You can check what you have submitted for this assignment by running the following
command:
~liuh/bin/checksubmit 370 A4
2020/3/24 CSCI 370 Spring 2020 - Assignment 4
csci.viu.ca/~liuh/370/assignments/A4.html 4/4
Currently, the submit script accepts any file with one of the following extension names: .pdf or
.txt. If you want to submit any file with other extension names, please contact the instructor
before you submit.
Remember that the electronic submission has a hard submit deadline at 11:30am, 10 April
2019, Wednesday.