- - - - CENAPAD-MGCO

A seguir: Escalonamento Serial Equivalente Acima: Travamentos Anterior: Teorema das transações duas-fases

Aciclicidade da relação de dependência

Consideremos a relação $\prec$ definida por

$T_{i} \prec T_{j}$ se e somente se $\exists e, (T_{i}, e, T_{j}) \in DEP(S)$

onde S é um escalonamento legal qualquer. Vamos provar que $\prec$ é acíclica.

O escalonamento S define também para cada transação T_i o inteiro shrink(T_i), que é a posição em S do primeiro unlock de T_i.

Proposição: $T_{1} \prec T_{2} \Longrightarrow shrink(T_{1}) < shrink(T_{2})$

Prova: se $(T_{1}, e, T_{2}) \in DEP(S)$, então

$$S = [\ldots,(T_{1}, a_{1}, e), \ldots ,(T_{2},a_{2},e),\ldots]$$

e se não existe nenhuma ação (T_j, a_j, e) escalonada no intervalo $(T_{1}, a_{1}, e), \ldots ,(T_{2},a_{2},e)$. Portanto, a₁ é unlock e, e a₂ é lock e, e shrink(T₁) < shrink(T₂).

De onde $\prec$ é uma relação acíclica.