retagged by
3,518 views
9 votes
9 votes
I am looking for some clarity on this topic. Here is some random schedule as an example:

$r1(x) w1(x)  r2(x) w2(x) r3(y) r3(x) w3(x) c3 a1 c2$

I was told, that for conflict serializablity we simply ignore the aborted transaction, which would be transaction 1 here. Thus the conflicting pairs would be

$\{(r2(x), w3(x)), (w2(x), r3(x)), (w2(x),  w3(x))\}$

i.e. the conflict graph would have one edge $T2 -> T3$.

Then for view serializablity do we also ignore $T1$ here, i.e. we say that $r2(x)$ reads some inital value of $x$ instead of whatever $w1(x)$ was?

As for result serializability, I'd think that we would have to take into consideration that $T1$ wrote $x$ since $T2$ reads that changed value, writes to $x$ and commits. But do we also ignore $T1$ here for serializablity? If so, why exactly?

 

Also aborted transactions are not ignored for recoverability, strictness or avoidance of cascading rollbacks.

I would be grateful if the question would be answered since this really confuses me.
retagged by

1 Answer

Best answer
11 votes
11 votes

I was told, that for conflict serializablity we simply ignore the aborted transaction

Yes, Right. Let's dig deeper on this and derive some results (Source : Navathe) : 

Transactions :

transaction is effectively a sequence of read and write operations on atomic database items. A transaction may be incomplete because the (database) system crashes, or because it is aborted by either the system or the user (or application). Complete transactions are committed. Transactions must terminate by either aborting or committing.

                                                                         Complete Schedule :  

A schedule $S$ of $n$ transactions $T1, T2, ..., Tn$ is said to be a complete schedule if the following conditions hold:

1. The operations in $S$ are exactly those operations in $T1, T2, ..., Tn$, including a commit or abort operation as the last operation for each transaction in the schedule.
2. For any pair of operations from the same transaction $Ti$ , their relative order of appearance in $S$ is the same as their order of appearance in $Ti$ . (i.e Operation order in/of  every transaction must preserve.)
3. For any two conflicting operations, one of the two must occur before the other in the schedule.

Condition 1 simply states that all operations in the transactions must appear in the complete schedule. Since every transaction has either committed or aborted, a complete schedule will not contain any active transactions at the end of the schedule.

 In general, it is difficult to encounter complete schedules in a transaction processing system because new transactions are continually being submitted to the system. Hence, it is useful to define the concept of the committed projection $C(S)$ of a schedule $S$.

                                                                   Committed Projection of a Schedule :

Committed Projection $C(S)$ of a schedule $S$ includes only the operations in $S$ that belong to committed transactions—that is, transactions $Ti$ whose commit operation $Ci$ is in $S$. 

Given a schedule S, the committed projection C(S) is the subset of S consisting of operations (r1(X), w2(Y), etc) that are part of transactions that have committed (that is, r1(X) would be part of C(S) only if transaction 1's commit, c1, were also part of S). This is sometimes useful in analyzing schedules when transactions are continuously being added.
 


Now, as according to Navathe,

We can theoretically define a schedule $S$ to be serializable if its committed projection $C(S)$ is equivalent to some serial schedule, since only committed transactions are guaranteed by the DBMS.

And It applies to both Conflict and View Serializability.

for conflict serializablity we simply ignore the aborted transaction

 Ignoring Aborted transactions is nothing but taking committed projection of schedule $S$.

Schedules :

schedule is a sequence of read, write, abort and commit operations from a set of transactions. Each schedule must preserve the order of the operations in its constituent transactions. A schedule is serial if it is the concatenation of its constituent transactions. A schedule is serialisable if the effect of its committed projection (the restriction to its committed transactions) on any consistent database is identical to that of some serial schedule of its committed transactions.

 

(Conflict) Serialisability theorem :

Given a schedule $S$, define the serialisation graph(Precedence Graph) SG(S) to have the committed transactions of $S$ as its nodes, and a directed edge from $T1$ to $T2$ if $T1$ and $T2$ contain conflicting operations $O1$ and $O2$ such that $O1$ precedes $O2$ in $S.$ Then $S$ is serialisable if and only if SG(S) is acyclic.

http://www.ict.griffith.edu.au/~rwt/uoe/1.1.ccc.html

 

Also aborted transactions are not ignored for recoverability, strictness or avoidance of cascading rollbacks.

Right. See, Serializability is concerned about Correct schedule only. 

Whereas Recoverability is concerend about Atomicity, Durability etc.  For some schedules it is easy to recover from transaction and system failures, whereas for other schedules the recovery process can be quite involved. In some cases, it is even not possible to recover correctly after a failure. Hence, it is important to characterize the types of schedules for which recovery is possible, as well as those for which recovery is relatively simple. 

So, In Recoverability, Roll-backs/aborts are important concerns.


Committed Projection : A committed projection C(S) of a schedule S include the operations in S only from the committed transactions.

Transactions:

T1: r1(X); w1(X); r1(Y); w1(Y); c1;

T2: r2(Y); w2(Y); a2;

T3: r3(X); w3(X);

S1: r1(X); r2(Y); w1(X); w2(Y); r1(Y); a2; w1(Y); c1; r3(X); w3(X);

Then C(S1) = ??

Well, C(S1) will be same as $T1$ because T3 has No Commit/Abort operation as the last operation of the transaction and T2 is Not committed. So, by the definition of Committed Transaction, C(S1) = T1.

 

https://gateoverflow.in/66950/serializablity-and-recoverability-of-schedules?show=66950#q66950

edited by

Related questions

1 votes
1 votes
1 answer
1
1 votes
1 votes
1 answer
2
aditi19 asked Nov 17, 2018
1,160 views
Tl:W(X), T2:R(X), Tl:W(X), T2:Commit, Tl:Abortis this schedule conflict serializable?
3 votes
3 votes
2 answers
3