沖突可串行化判別

1、沖突可串行化的判定沖突可串行化的判定一.問題的提出在數(shù)據(jù)庫工程師的考試中，對事務(wù)的并發(fā)操作多次考到，且占有很高的分值。這部分知識(shí)學(xué)習(xí)不難，但考試得分不高，糾其原因是不太理解。在設(shè)計(jì)并發(fā)控制機(jī)制時(shí)，必須保證由該機(jī)制產(chǎn)生的調(diào)度是可串行化的。在此我們只討論沖突可串行化的判定。二.沖突可串行化的判定判定方法分為兩個(gè)步驟：步驟1：產(chǎn)生調(diào)度的優(yōu)先圖步驟2：采用一個(gè)合適的算法(如基于深度優(yōu)先或廣度優(yōu)先的環(huán)檢測算法，這是《圖論》課程中的內(nèi)容)檢查優(yōu)

2、先圖中是否有有向環(huán)。如果有，則該調(diào)度就不是沖突可串行化的，否則就是沖突可串行化的。設(shè)S是一個(gè)調(diào)度，由S構(gòu)造一個(gè)有向圖，稱為優(yōu)先圖。該圖由兩部分G=(VE)組成，其中V是頂點(diǎn)集，E是邊集。頂點(diǎn)集由所有參與調(diào)度的事務(wù)組成。邊集由滿足下列三個(gè)條件之一的邊Ti→Tj組成：Ti的write(Q)在Tj的read(Q)之前執(zhí)行Ti的read(Q)在Tj的write(Q)之前執(zhí)行Ti的write(Q)在Tj的write(Q)之前執(zhí)行如果有向圖中