Questions

1. For each of the following two schedules:
   1. R₄(y);R₄(z);W₁(x); R₁(z);W₃(x);R₂(x); R₃(y);R₁(y);W₃(y); W₂(x);W₄(x);R₂(z); W₂(y);R₁(y);
   2. R₃(y);R₂(y);R₄(z); R₃(y);W₄(z);R₄(x); R₁(z);W₄(x);R₃(z); R₂(x);W₂(x);R₁(x); W₂(y);W₁(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. Oracle database system can be set to run on one of the following 4 isolation levels:
   

   Isolation Level	Dirty Reads	Non-Repeatable Reads	Phantoms
   read uncommitted	allowed	allowed	allowed
   read committed	not allowed	allowed	allowed
   repeatable read	not allowed	not allowed	allowed
   serializable	not allowed	not allowed	not allowed

   
   On our csci server, Oracle database system runs on the level of "read committed". We may encounter some data inconsistency. But these anomalies can be tolerated in our lab environment where we read public data (in HR schema) and perform updates only in our own individual schema.
   Is there any application environment in which the Oracle database system can and should even run on the level of "read uncommitted"? If your answer is yes, describe a simple example of such an environment. If your answer is no, justify your answer.
   
   
3. When a database system restarts, the following log file is loaded into the system, where T₁, T₂, T₃, and T₄ are four transactions, and u, v, w, and x are four database objects, and the log record follow the format of [transaction, object, old_value, new_value].

   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

   1. 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.
   2. 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 process is successfully completed?
   
   
4. 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	...
   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/sparse/clustered index using customer_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 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.
   Your tasks:
   1. Draw these two above mentioned B+ tree indices.
   2. Clearly identify the nodes/pages that should be brought into memory in order to retrieve the data for the following query efficiently:

      SELECT *
      FROM Customers
      WHERE last_name = 'Jones';
      

   3. A new customer whose last name is Cameron is assigned with the customer id 1026. Update your data page and the two indices you just build in the previous question to accommodate the new tuple for this new customer.

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 VIU Learn, upload all your PDF and/or text solution files to AA under CSCI 370's assessment and assignments tab.