MHB Transactions & schedules - Dependency relations

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Relations
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :giggle:

The below transactions are given :
1639954138539.png


and the below schedules :
1639954207327.png


Give the respective dependency relations as well as the precedence graphs. Which schedules are conflict serializable? Which schedules are equivalent?
I reread some notes and looked also for some examples in Google and now I have done the following :

Are the below dependent in $S_1$ ?
$(T_1, R, B) \to (T_3, W,B)$
$(T_1, R, C) \to (T_2, W, C)$
$(T_3, R, A) \to (T_4, W, A)$
$(T_1, W, C) \to (T_4, R, C)$
$(T_4, R, C) \to (T_2, W, C)$
$(T_1, W, B) \to (T_3, W, B)$
$(T_2, R, B) \to (T_3, W, B)$

Then we would get \begin{align*}\text{DEP}(S_1)&=\{(T_1,B,T_3), (T_1, C, T_2), (T_3, A, T_4), (T_1, C, T_4), (T_4, C, T_2), (T_1, B, T_3), (T_2, B, T_3)\}\\ & =\{(T_1,B,T_3), (T_1, C, T_2), (T_3, A, T_4), (T_1, C, T_4), (T_4, C, T_2), (T_2, B, T_3)\}\end{align*}

Is that correct? :unsure:If that is correct then for the other schedules we have :

The dependent ones in $S_2$ are :
$(T_1, R, B) \to (T_3, W,B)$
$(T_1, R, C) \to (T_2, W, C)$
$(T_1, W, C) \to (T_2, W, C)$
$(T_2, R, B) \to (T_1, W, B)$
$(T_1, W, B) \to (T_3, W, B)$
$(T_2, W, C) \to (T_4, R, C)$
$(T_3, R, A) \to (T_4, W, A)$

Then we would get \begin{align*}\text{DEP}(S_2)&=\{(T_1,B,T_3), (T_1, C, T_2), (T_1, C, T_2), (T_2, B, T_1), (T_1, B, T_3), (T_2, C, T_4), (T_3, A, T_4)\}\\ &=\{(T_1,B,T_3), (T_1, C, T_2), (T_2, B, T_1), (T_2, C, T_4), (T_3, A, T_4)\}\end{align*}
The dependent ones in $S_3$ are :
$(T_1, R, B) \to (T_3, W,B)$
$(T_1, R, C) \to (T_2, W, C)$
$(T_1, W, C) \to (T_2, W, C)$
$(T_1, W, B) \to (T_2, R, B)$
$(T_2, R, B) \to (T_3, W, B)$
$(T_2, W, C) \to (T_4, R, C)$
$(T_3, R, A) \to (T_4, W, A)$

Then we would get \begin{align*}\text{DEP}(S_3)&=\{(T_1,B,T_3), (T_1, C, T_2), (T_1, C, T_2), (T_1, B, T_2), (T_2, B, T_3), (T_2, C, T_4), (T_3, A, T_4)\}\\ & =\{(T_1,B,T_3), (T_1, C, T_2), (T_1, B, T_2), (T_2, B, T_3), (T_2, C, T_4), (T_3, A, T_4)\}\end{align*}
The dependent ones in $S_4$ are :
$(T_1, R, B) \to (T_3, W,B)$
$(T_1, R, C) \to (T_2, W, C)$
$(T_1, W, C) \to (T_2, W, C)$
$(T_1, W, B) \to (T_2, R, B)$
$(T_2, R, B) \to (T_3, W, B)$
$(T_2, W, C) \to (T_4, R, C)$
$(T_3, R, A) \to (T_4, W, A)$

Then we would get \begin{align*}\text{DEP}(S_4)&=\{(T_1,B,T_3), (T_1, C, T_2), (T_1, C, T_2), (T_1, B, T_2), (T_2, B, T_3), (T_2, C, T_4), (T_3, A, T_4)\}\\ & =\{(T_1,B,T_3), (T_1, C, T_2), (T_1, B, T_2), (T_2, B, T_3), (T_2, C, T_4), (T_3, A, T_4)\}\end{align*}Is everything correct so far? :unsure:From the precedence graphs we check which are acyclic and these ones are conflict serializable, right?
So $S_3$ and $S_4$ are conflict serializable, right? :unsure:We have that $\text{DEP}(S_3)=\text{DEP}(S_4)$. We have to check if $S_3$and $S_4$ have the same transactions so that we can say that these two schedules are equivalent, right? But exactly does it mean that they have the same transactions? Is it maybe that the schedules $S_3$ and $S_4$ are the same if we reorder some elements? Is that the desired condition that we need? :unsure:
 
Last edited by a moderator:
Physics news on Phys.org
The notes that I am looking at are these ones from the end of the pdf-page 87.
 
Hi all, I've been a roulette player for more than 10 years (although I took time off here and there) and it's only now that I'm trying to understand the physics of the game. Basically my strategy in roulette is to divide the wheel roughly into two halves (let's call them A and B). My theory is that in roulette there will invariably be variance. In other words, if A comes up 5 times in a row, B will be due to come up soon. However I have been proven wrong many times, and I have seen some...
Thread 'Detail of Diagonalization Lemma'
The following is more or less taken from page 6 of C. Smorynski's "Self-Reference and Modal Logic". (Springer, 1985) (I couldn't get raised brackets to indicate codification (Gödel numbering), so I use a box. The overline is assigning a name. The detail I would like clarification on is in the second step in the last line, where we have an m-overlined, and we substitute the expression for m. Are we saying that the name of a coded term is the same as the coded term? Thanks in advance.
Back
Top