Re: Trouble understanding serializability

"Laconic2" <laconic2_at_comcast.net> wrote in message news:<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.

i believe that the generally accepted definition of 'serial transaction' doesn't permit this: T1 and T2 can see different states of the database, depending on how the actions are interleaved.

the simple 'proof' is that all transactions accessing distinct data do so in the same order. 'same order' is a synonym for serialization, so the proof may be considered circular; at least axiomatic.

>
> Note that there's no concurrency in this scenario.
>
> Basically, the RDB locking mechanism is quite conservative.
Received on Tue Jun 22 2004 - 23:44:27 CEST