11

I was reading about serializability in schedules of transactions and therefore read about conflict serializable and view serializable schedules.

Now because conflict serializable is more stringent than view serializable , it is obvious that there will be schedules that are view serializable but not conflict serializable.In the book I read the following:

Blind writes appear in any schedule that is view serializable but not conflict seralizable.

I have been trying to come up with a proof of the above statement but could not do it.

My question is : Is there a formal proof of the above mentioned statement?

1
  • Just FYI, I think these type of question it's really better to be answered in stack exchange theoretical computer science... Apr 14, 2018 at 3:16

4 Answers 4

3

Main idea of a view serializable schedule is that each read operation of a transaction should read the result of the same write operation in all schedules, thereby having the same "view" of the database.

For a schedule that is not conflict serializable but is view serializable, there exists a conflict in the schedules but the "view" of the DB is maintained. This would imply that each read operation reads the same results/values across schedules, and that the conflicting operations are writes. As the conflicting operations do not change the view of the database, it must mean that the write operations are blind, as they are not writing a new or different value by reading an updated or old value from the database. Thus, these operations must be blind writes.

2

Blind write means A transaction writes the database, without reading the database variable.

That means, if we know the database variable name. If we write using that variable with some values.

The transaction is like the below, that is blind writes.

Example:-

Transaction T1                           Transaction T2

  Write(X)
                                            Write(X)
  Write(Y)
                                            Write(Y)

In the above example, we didn't read the variable X, but we are writing the X.

If we write the database without using the old value, There is no conflict serializability. In here we have to replace the old value in the database. The blind writes is done in two transactions with using the same database variable name.That time also it is a serializable.

0

Just a sketch proof since I am not very familiar with the language they use & not sure good ways to fill in the details...

Assume we have a View Serializable Schedule G that is not Conflict Serializable. Consider a circle of conflict action on the same object in G which must exists by definition.

Consider the write actions in the circle, denote as W(A).

Assume none of them are blind write.

Consider the earliest W(A) in the circle which must exists by definition, WLG denote it from T1 and denote this write as W1(A)

Assume this circle exists only 1 W(A). Then the schedule is not view serializable since it means that there exists a schedule that have R(A) before the current W(A) and R(A) after the current W(A), contrary.

Then consider some W(A) come after T1 which will exists, denote the set of transactions that have these W(A) come after W1(A) be S.

We know that S != {T1} because if so, the schedule is again not view serializable since it implies there is a T3 that includes R(A) that happens between two W(A).

Then consider the non-empty set of S - T1.

Case 1: Assume that in this circle of conflict, there is no other action on A that predates W1(A). This mean that T1 conduct some action on A after W1(A). Subcase 1: the action of T1 that are in the conflict circle is a R(A) Then it is not view serializable since in a serial schedule the R(A) read what W1(A) wrote. Subcase 2: the action of T1 that are in the conflict circle is a W(A), denote as W2(A). Again, to make it view serializable, there should be no R(A) between W1(A) and W2(A) for all transaction. So the conflict should at least involved some W(A) between W1(A) and W2(A) which is a transaction in S - T1. It has an R(A) come before its W(A) and by requirement it will be before W1(A)

Case 2: Assume that in this circle of conflict, there is an action that predates W1(A) By definition it has to be R(A) and the transaction that have this early R(A) should be in a part of S - T1, otherwise the action after this R(A) would be another R(A) which conflict view serializability.

Combine 2 cases: there exists a transaction in S - T1 that have a R(A) before W1(A) of T1 and W(A) after W1(A) of T1. Denote this transaction as T2 and the two action as T2(A) and W2(A) respectively.

Consider the R1(A) in T1 before W1(A). Then T1 can not be view serializable to T2, since in a view serial schedule, either R1(A) read W2(A) or R2(A) read W1(A) will happen, but both can't occur. Contrary.

Then our assumption is wrong, some of them are blind write.

-1

The below example is both a view serializable and a conflict serializable schedule

schedule

Now if we want to convert it into schedule which is view serializable but not conflict serializable,we have to either do one of the changes:

  1. Change W(B) to W(A) in T1
  2. Change R(A) to W(A) in T2

In 1st case the schedule will be not conflict serializable as well as it wont be view serializable too

Thus 2nd case ensures our task which gives rise to blind write. Therefore Blind writes are necessary.

Blind writes are necessary to satisfy view serializability and contradict conditions for conflict serializabilty

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.