Two transactions T1 and T2 are given as
where ri(V) denotes a read operation by transaction Ti on a variable V and wi(V) denotes a write operation by transaction Ti on a variable V. The total number of conflict serializable schedules that can be formed by T1 and T2 is ____________.
Following two conflict actions are possible:
∴# Permutations = 4 × 3 = 12
#permutations = 4 × 1 = 4
∴ Total no. of conflict serial schedules possible = 70 - 12 - 4 = 54
NOT a part of the ACID properties of database transactions?
So, Deadlock – freedom is not there in the ACID properties.
Suppose a database schedule S involves transactions T1, ..., Tn. Construct the precedence graph of S with vertices representing the transactions and edges representing the conﬂicts. If S is serializable, which one of the following orderings of the vertices of the precedence graph is guaranteed to yield a serial schedule?
Ascending order of transaction indices
But BFS and DFS are also potssible for cyclic graphs.
And topological sort is not possible for cyclic graph.
Moreover option (D) is also wrong because in a transaction with more indices might come before lower one.
Consider the following database schedule with two transactions, T1 and T2.
S = r2(X); r1(X); r2(Y); w1(X); r1(Y); w2(X); a1; a2
where ri(Z) denotes a read operation by transaction Ti on a variable Z, wi(Z) denotes a write operation by Ti on a variable Z and ai denotes an abort by transaction Ti.
Which one of the following statements about the above schedule is TRUE?
S is non-recoverable
S is recoverable, but has a cascading abort
S does not have a cascading abort
S is strict
Now let's check statements one by one,
A) False, because there is no dirty read. So, it is recoverable.
B) False, because there is to dirty read. So, no cascading aborts.
D) False, because there is Transaction T2 which written the value of x which is written by T1 before T1 has aborted. So, not strict.
Undo T3, T1; Redo T2
Undo T3, T1; Redo T2, T4
Undo: none; redo: T2, T4, T3, T1
Undo T3, T1; T4; Redo: T2
T2 must be aborted and then both T1 and T2 must be re-started to ensure transaction atomicity
Schedule S is non-recoverable and cannot ensure transaction atomicity
Only T2 must be aborted and then re-started to ensure transaction atomicity
Schedule S is recoverable and can ensure atomicity and nothing else needs to be done
r1 (x); r2 (x); w1 (x); r3 (x); w2 (x)
r2 (x);r1 (x);w2 (x);r3 (x);w1 (x)
r3 (x);r2 (x);r1 (x);w2 (x);w1 (x)
r2 (x);w2 (x);r3 (x);r1 (x);w1 (x)
- Polygraph contains cycle. So, not a conflict serializable.
- Acyclic, so conflict serializable.
S is conflict-serializable but not recoverable
S is not conflict-serializable but is recoverable
S is both conflict-serializable and recoverable
S is neither conflict-serializable nor is it recoverable
In the precedence graph, there are no cycles. So, it is conflict serializable and recoverable also.
a serializable schedule
a schedule that is not conflict serializable
a conflict serializable schedule
a schedule for which a precedence graph cannot be drawn
The above schedule is not conflict serializable.
Both I and II
Neither I nor II
― Timestamp ordering protocol ensures conflict serializability and free from deadlock.
T1 → T3 → T2
T2 → T1 → T3
T2 → T3 → T1
T3 → T1 → T2
― Precedence graph for the above schedule is,
― From the precedence graph the correct serialization is,
S1 and S2
S2 and S3
Dependency graph is,
So, there is no cycle.
Dependency graph is,
S4 also has a cycle T1→T2 and T2→T1.
So, S2 and S3 are conflict serializable.
S1, S2 and S3 are all conflict equivalent to each other
No two of S1, S2 and S3 are conflict equivalent to each other
S2 is conflict equivalent to S3, but not to S1
S1 is conflict equivalent to S2, but not to S3
Hence, S1 is conflict equivalent to S2, but not to S3.
Both S1 and S2 are conflict serializable.
S1 is conflict serializable and S2 is not conflict serializable.
S1 is not conflict serializable and S2 is conflict serializable.
Both S1 and S2 are not conflict serializable.
In precedence graph of S1 since cycle is formed so not conflict serializable.
But in precedence graph of S2 No cycle is formed so it is conflict serializable.
We must redo log record 6 to set B to 10500.
We must undo log record 6 to set B to 10000 and then redo log records 2 and 3.
We need not redo log records 2 and 3 because transaction T1 has committed.
We can apply redo and undo operations in arbitrary order because they are idempotent.
So from above theory we can say that option (B) is the correct answer.
A transaction writes a data item after it is read by an uncommitted transaction
A transaction reads a data item after it is read by an uncommitted transaction
A transaction reads a data item after it is written by a committed transaction
A transaction reads a data item after it is written by an uncommitted transaction
The schedule is serializable as T2; T3; T1
The schedule is serializable as T2; T1; T3
The schedule is serializable as T3; T2; T1
The schedule is not serializable
Cycle formed so not serializable.
This schedule is serialized and can occur in a scheme using 2PL protocol
This schedule is serializable but cannot occur in a scheme using 2PL protocol
This schedule is not serialiable but can occur in a scheme using 2PL protocol
This schedule is not seralisable and cannot occur in a scheme using 2PL protocol.
Since cycle exist so not conflict serializable.
And we know that if the schedule is not serializable then it is not 2PL.
Hence correct option is (D).