Questions

1. For each of the following two schedules:
   1. R₁(x);R₄(x);R₃(z); R₁(x);W₃(z);R₃(y); R₂(z);W₃(y);R₁(z); R₄(y);W₄(y);R₂(y); W₄(x);W₂(y);
   2. R₁(x);R₁(y);W₃(z); R₃(y);W₄(z);R₂(z); R₄(x);R₃(x);W₄(x); W₂(z);W₁(z);R₂(y); W₂(x);R₃(x);
   Answer the following questions:
   1. Draw the precedence (serialization) graph for the schedule.
   2. Is the schedule conflict-serializable? If your answer is yes, list all of its equivalent serial schedules. If your answer is no, how can we abort the least number of transaction(s) so that the rest of the schedule becomes conflict-serializable?
   3. Could the original or updated (by aborting some transactions) conflict serializable schedule be recoverable and/or cascadeless? Justify your answer.
   
   
2. Suppose the following log records (except the CHECKPOINT) are added into the memory copy of a log file, where T₁ to T₄ are transactions, and u, v, w, x are database objects.

   CHECKPOINT

   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, abort

   T3, x, 80, 60

   T3, x, 60, 35

   T3, commit

   T2, end

   T1, x, 35, 50

   T1, u, 34.2, 22.6

   T4, begin

   T3, end

   T4, w, 15, 20

   1. If WAL protocol is adopted, which record(s) is/are guaranteed to cause the log file records be flushed out to the disk?
   2. Suppose the above records are also the ones loaded into the database system after a system crash happened, and the recovery manager 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?
   
   
3. A database table, Employees, has many columns. Two of these columns are Emp_ID and Last_Name. The following 28 tuples are inserted into this table:

   Emp_ID	Last_Name	other columns
   1001	Smith	...
   1002	Brown	...
   1003	Tremblay	...
   1004	Martin	...
   1005	Roy	...
   1006	Wilson	...
   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	Beesbrook	...
   1024	Morin	...
   1025	Bouchard	...
   1026	Bamford	...
   1027	Crawford	...
   1028	Tang	...

   You are asked to construct two B+ tree indices on the table Employees. One is a primary/sparse/clustered index using Emp_ID as the search key, and the other a secondary/dense/unclustered index using Last_Name as the search key.
   Suppose that, no matter what type of data to be stored in each page, for both trees, 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 page pointers.
   Your tasks:
   1. Draw these two above mentioned B+ tree indices.
   2. Identify the nodes (in your index trees and data pages) that may be loaded into memory when the database executes the following query efficiently by using the appropriate index:

      select *
      from Employees
      where Last_Name = 'Moss';
      

   3. Identify the nodes (in your index trees and data pages) that may be loaded into memory when the database executes the following query efficiently by using the appropriate index:

      select *
      from Employees
      where Emp_ID = '1006';
      

   4. Describe what would happen (in the data pages and indices) if the following SQL statement is executed:

      insert into Employees (Emp_ID, Last_Name)
      values ('1029', 'O\'Brian');
      

   How to Submit

   You can submit your assignment solutions using one of the following two ways:

   • Submit a hard copy before the due date/time.
   • Login to csci server, in the directory that holds all the files you want to submit, execute the following command:
     ~liuh/bin/submit 370 AA .
     This submit script currently accepts .txt, .pdf and .md files. If your file has other extension names, please ask me to update the submit list before you submit.
     You can use the following command to check what you have submitted to A9:
     ~liuh/bin/checksubmit 370 AA

   ---

   Last updated: March 27, 2025