Consider the following schedule S, consisting of transactions T₁, T₂ and T₃

• Give the precedence graph for S
• Is S conflict serializable ? Justify your answer.
• Is S view serializable ? Justify your answer.

Two transactions are not interleaved in a schedule S if every operation of one transaction precedes every operation of the other. (Note, the schedule may not be serial.) Give an example of a serializable schedule S that has all of the following properties:

• transactions T₁ and T₂ are not interleaved in S
• T₁ precedes T₂ in S
• in any serial schedule equivalent to S, T₂ precedes T₁

Hint: The schedule may include more than two transactions.

Consider two non-identical schedules S and S’ consisting of transactions T₁,…, T_n where n>1. For each of the following set of conditions decide whether S and S’

• have to be equivalent,
• have to be nonequivalent,
• is impossible to decide whether they are equivalent or not using the given conditions
• the described conditions can not hold

The conditions are

1. S only reads, S and S’ are serial and n=2
1. All transactions T₁,…, T_n write a specific item A exactly once and S and S’ are serial.
1. The precedence graphs of S and S’ are identical and acyclic.
1. S is serializable but S’ is not serializable.
1. No two serial schedules (of T₁,…, T_n) are equivalent and S and S’ are serializable.

For each one of the following schedules decide whether

• they are serializable
• they can be produced by a Two Phase Lock (2PL) scheduler
• they can be produced by a strict 2PL scheduler

and check in the table below all entries that apply. Justify your answers in a concrete way. For example, if a schedule is 2PL show a series of lock/unlock operations that are compatible with the 2PL rules (you can use the empty lines of the schedules to place lock/unlock operations.) Answers of the form "it is serializable because I can see that I can swap the operations" will not get full credit. Assume that shared locks can be used if in this way you can make a schedule 2PL or strict 2PL.

1. Undo logging requires that before an item X is modified on disk the log records pertaining to X are in the disk. (This is the WAL rule.) Show using an example that an inconsistent database may result if log records for X are not output to the disk before X.
1. Redo logging: Show using an example that an inconsistent database may result if some items are written on the disk before the commit is written on the log, even if WAL holds.
1. Undo logging: Show using an example that an inconsistent database may result if some items are not written in the disk by the time the commit is written. Assume that WAL holds.

Your examples should involve a crash and should clearly show (I) the write actions of the transaction, (II) the state of the log and the database at the time of the crash, and (III) why successful recovery can not be accomplished.

We know that non strict 2PL may cause cascading aborts. Even worse, it could be the case that a crash occurs while cascading aborts take place. The goal of this exercise is to develop an Undo logging system that can handle cascading aborts, i.e., upon restart it can abort the transactions that have to be aborted and so on.

1. What additions are needed in the Undo logging data for handling cascading aborts
1. Write the rules of your enhanced "cascading abort Undo logging" (in the spirit of the notes). Try to pose rules that are not very restrictive.
1. Write an algorithm for recovery (restart) using notation similar with the notes.

Clarification on notes: In the slide of "Undo Logging Recovery" the condition "NO <T, Commit> (or <T, Abort>) in log" is parenthesized as "(NO <T, Commit>) OR <T, Abort> in log".

Consider a transaction that performs the following actions in the given order

1. Write object A
1. Write object B
1. Commit

Decide whether each one of the following snapshots of the database and the log are possible or impossible at any point during or after the end of the transaction. The snapshots refer to data that are actually in the disk. Assume that if we do not mention explicitly that something is stored on the disk then it is not stored on the disk. For each item give an answer for both Undo and Redo logging.

1. Log has entry for write(A) and the database has the new value of A
1. The database has the new value for A
1. The log has entries for write(A) and write(B) and also has the commit entry
1. The log has entries for write(A) and write(B). The database has the new values for A and B
1. The log has entries for write(A), write(B), and the commit entry. The database has the new value for A
1. Log has entry for write(A) and commit and the database has the new value of A

.Consider the following query:

SELECT *

FROM R, S, T

WHERE R.A = S.A and R.B = T.B AND T.C = S.C

AND R.D = 16 AND S.F = 17

1. Give six algebraic expressions that (I) contain no cartesian product, (II) have pushed selections down, (III) each join is associated with an atomic condition (not a conjunctive condition).
1. Find the optimum plan, i.e., an algebraic expression where selections and projections are annotated with execution primitives. The execution primitives are SCAN and INDEX for the selection operator and LOOPS, INDEX, MERGE, and HASH for join. Compute an estimation of the optimal plan’s cost.

• R(A, B, D, E) has 1 million tuples, an index on D, V(D,R)=1000, V(A,R)=1000000, V(B,R)=1000000.
• S(A, C, F, G) has 1 million tuples, an index on F, V(F,S)=1000, V(A,S)=1000000, and V(C,S)=1000000
• T(B, C, H, I) has 1 million tuples, an index on B, with V(B,T)=1000000, V(C,T)=1000000.

Assume the block size is 4096 Bytes, the block header size is 96 bytes, each indexed attribute occupies 5 bytes and the tuple size of each relation is 80 bytes.

To estimate the size of the joins use the following information:

• For every tuple of R there is exactly one tuple of S with the same A value and one tuple of T with the same B value. Equivalently, the chances that a given S tuple joins a given R tuple are 1/1000000.
• For every tuple of S there is exactly one tuple of R with the same A value and one tuple of T with the same C value.
• For every tuple of T there is exactly one tuple of R with the same B value and one tuple of S with the same B value.

Assume there is one megabyte of main memory available. Hint: You should use the main memory to avoid copying intermediate results to the disk, if there is enough space in main memory.

1. Solution