CSCI 370 Spring 2024 - Assignment A
Due: 23:59, 12 April 2023, Friday
Questions
- For each of the following two schedules:
- 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);
- 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:
- Draw the precedence (serialization) graph for the schedule.
- 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?
- Could the original or updated (by aborting some transactions)
conflict serializable schedule
be recoverable and/or cascadeless? Justify your answer.
- 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.
- When a database system restarts, the following log file is loaded
into the system, where T1, T2, T3,
and T4
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 |
- 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.
- 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?
- 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:
- Draw these two above mentioned B+ tree indices.
- 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';
- 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.
Last updated: April 2, 2024