Re: Trouble understanding serializability

From: Laconic2 <laconic2_at_comcast.net>
Date: Thu, 17 Jun 2004 10:16:21 -0400
Message-ID: <BsCdnRRyDd3BOkzdRVn-ug_at_comcast.com>

"Stevens" <auto87829_at_hushmail.com> wrote in message news:40cc4bd3$0$11523$afc38c87_at_news.optusnet.com.au...
> This is a question out of Database System Concepts by Silberchatz.
>
> Consider the following two transactions, T1 and T2
>
> T1: read(A)
> read(B)
> if A=1 then B:=B-1
> write(B)
>
> T2: read(B)
> read(A)
> if B=1 then A:=A-1
> write(A)
>
> Initial values are A=B=1 and the consistency condition is (A=1) OR (B=1)
>
> The question: is there a concurrent execution of T1 and T2 that produces a
> serializable schedule? Prove your answer.
>
> Now to me this is confusing ... you'd only have to ensure the T1 reads(A)
> before T2 writes(A) or T2 reads(B) before T2 writes(B). No other
operations
> seem to conflict. What's the answer to this?

I don't know the theoretical answer, but I do know how DEC Rdb would have handled it back in 1994.

One scenario:

T1:  read (A)  ; there is now a shareable read lock on A.
T2:  read (B)  ; there is now a shareable read lock on B.
T1:  read (B)  ; there is still a shareable read lock on (B) with more than

one owner.
T2: read (A) ; there is still a shareable read lock on (A) with more than one owner.
T1: if A = 1 then B:= B -1 ; T1 is now waiting for an exclusive write lock on (B)
T2: if B = 1 then A:= A - 1 ; T2 is now waiting for an exclusive write lock on (A)

<deadlock timeout occurs>

T2: is issued an error return.

T2: ROLLBACK T1 comes out of wait status, completes transaction. T2 does the whole transaction again, but now uses a different value for B.

Note that there's no concurrency in this scenario.

Basically, the RDB locking mechanism is quite conservative. Received on Thu Jun 17 2004 - 16:16:21 CEST