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.
