CS632 Final Exam Part AA. Demers2 May 2003A couple more questions will appe ar by Monday. Nothing will be due less thana week after it appears here.As usual, you may consult others for ideas and proof approaches, but pleasereference your sources and write up answers independently.1 The Oracle(tm) Isolation RulesHere is a somewhat simplified description of the isolation rules used by Oracle.The system maintains an event counter called the System Change Number(SCN), which is effectively a clock. For any entity x and any SCN (or time) t,the system can return the last value written to x by a transaction that commit-ted before t. Thus, for any time t a transaction can arrange to get a consistentsnapshot of the database, consisting of the values written by those transactionsthat committed before t.Dirty reads do not happen. Each entity x is tagged with the transaction thatlast wrote it. If that transaction has not (yet) committed, the value of theentity is never returned to a reader, but instead data from the rollback segment(which is essentially an undo log) is used to find and return the appropriatevalue written by a committed transaction.The operations are supporting this model areR(x, t): Return the value written to entity x by the last transactionto commit before t.R(x): Equivalent to R(x, C) where C is the current SCN.L(x): Acquire an exclusive lock on entity x.U(x): Release the lock on entity x.1W(x): Write entity x.C: Commit the transaction.A: abort the transaction.As usual, we shall assume a transaction is not allowed to re-read an entity thatit has already written.Problem 1a: Sketch how an ARIES-like recovery algorithm can support theoperations described above. Obviously, the interesting operation is R(x, t).Don’t worry about fine-granularity locking – you may assume a lo cked entity oc -cupies exactly one page. But don’t oversimplify either – your algorithm shouldsupport a transaction that modifies more entities than will fit in the bufferpool, and committing a transaction should require forcing the log but not wait-ing for dirty pages to be flushed from the buffer pool. Discuss checkpointingand archiving/truncating the log.Problem 1b: By default, the locking protocol used by Oracle is strict 2-phase locking on writes, and no locking at all on reads. Each read is done atthe current SCN (that is, transactions use R(x) rather than R(x, t) in the abovedescription).Show by example that the default Oracle locking protocol can generate nonse-rializable schedules.(In practice, a transaction consists of multiple SQL queries, each of which ac-cesses many entities. All the read access of a single SQL query are performed asof the same SCN, so that each SQL query sees a consistent snapshot. However,different SQL queries in the same transaction are executed at different SCNsand thus see different snapshots. Feel free to ignore this detail, and think ofeach SQL query as a single read.)Problem 1c: An alternative rule associates with each transaction A a “snap-shot timestamp” tA, which is the SCN when the transaction was started. Everyread in A is performed at time tA– that is, each read R(x) is replaced byR(x, tA). In addition, the following test is performed for each lock operationLA(x):After the lock has been granted, if the commit time of the last trans-action that wrote x is greater than tA, then abort A.Show that this protocol can also generate nonserializable schedules.2Problem 1d: (We are trying desperately to find some way to guarantee se-rializable schedules in Oracle.) Consider static 2-phase locking, that is, strict2-phase locking with the additional requirement that all locks must be acquiredat the beginning of the transaction, before the first read or write operation.Let the snapshot timestamp of a transaction be the SCN after all locks havebeen acquired. Using this rule, are nonserializable schedules possible? Give anexample, or prove that no such example exists.Under rule (1d), what happens to transactions / schedules that caused transac-tion aborts under rule