Megelőzési gráfok - (precedence graph)

Ha adott S ütemezésben konfliktusban álló műveletek vannak, akkor a tranazkcióik sorrendje változatlan kell maradjon a konfliktus-ekvivalens soros ütemezésben

A konfliktusban álló műveletpárok megszorítást adnak az ütemezésben a tranzakciók sorrendjére
Ha a megkötések együdd nem vezetnek ellentmondáshoz, akkor létezik konfliktus-ekvivalens soros ütemezés
- Ellenkező esetben $\nexists$

Megelőzés

Adott $S$ ütemezésben $T_1$ és $T_2$ tranzakciók, ahol $T_1$-ben $A_1$, $T_2$-ben $A_2$ művelt szerepel

$T_1$ megelőzi $T_2$-t, ha

$A_1$ megelőzi $A_2$-t $S$-ben
$A_1$ és $A_2$ ugyanarra az adatbáziselemre vonatkoznak
$A_1$ és $A_2$ közül legalább az egyik írás művelet

Tehát $A_1$ és $A_2$ konfliktuspárt alkotna, ha szomszédos műveletek lennének.

Jelölés

$T_1 <_S T_2$

Nyilván, ezek a feltételek az alap konfliktushelyzetekkel megegyeznek, és éppen ezért a soros ütemezésben $T_1$-nek meg kell előznie $T_2$-t (feltéve, hogy létezik oc)

Megelőzési gráf alak

$T_i <_S T_j$ esetén

$i$ jelöli a $T_i$ tranzakciót, annak $i$ csúcsából irányított él vezet $j$ csúcsba

Megelőzési gráf Példa

Adott $T_1,~T_2,~T_3:$

\[ S:r_2(A);\,r_1(B);\,w_2(A);\,r_3(A);\,w_1(B);\,w_3(A);\,r_2(B);\,w_2(B); \]

$S$-hez tartozó megelőzési gráf:

Konfliktus gráf példa: 1

Lemma

$S_1, S_2~\text{konfliktusekvivalensek}~\Rightarrow \text{gráf}(S_1)=\text{gráf}(S_2)$

$\contradiction\;$ $\text{gráf}(S_1)\ne\text{gráf}(S_2)$

$\Longrightarrow \exist él= T_i \to T_j:\; (él\in \text{gráf}(S_1) \land él \not\in \text{gráf}(S_2))\quad\lor\quad(él\in \text{gráf}(S_2) \land él \not\in \text{gráf}(S_1))$

$\Longrightarrow S_1=\ldots p_i(A)\ldots q_j(A)\ldots\quad\lor\quad S_2=\ldots q_j(A)\ldots p_i(A)\ldots $

$\Longrightarrow p_i, q_j~\text{konfliktusos pár}~\contradiction$

$\Longrightarrow S_1, S_2~\text{nem konfliktusekvivalens}\quad\blacksquare$

Megjegyzés

\[ \text{gráf}(S_1)=\text{gráf}(S_2) \not\Rightarrow S_1, S_2~\text{konfliktusekvivalens} \]

Ellenpélda:

\[ S_1=w_1(A)\,r_2(A)\,w_2(B)\,r_1(B) \]

\[ S_1=r_2(A)\,w_1(A)\,r_1(B)\,w_2(B) \]

Így nem lehet semmit sem cserélni

0:10:41 - 1:31:24