熊中敏 王佳艷 汪 博 陳 明

(上海海洋大學(xué)信息學(xué)院 上海 201306)(農(nóng)業(yè)部漁業(yè)信息重點(diǎn)實(shí)驗(yàn)室 上海 201306)

0 引 言

隨著移動互聯(lián)網(wǎng)和數(shù)字化操作平臺的發(fā)展，信息系統(tǒng)都支持并發(fā)用戶，從而產(chǎn)生了大量的并發(fā)事務(wù)[1-3]。為了提高系統(tǒng)的性能，現(xiàn)代數(shù)據(jù)庫技術(shù)支持并發(fā)事務(wù)的調(diào)度執(zhí)行；為了維護(hù)整個系統(tǒng)上操作的正確性，必須確保并發(fā)事務(wù)調(diào)度是可串行化調(diào)度。并發(fā)事務(wù)的可串行化檢測是事務(wù)并發(fā)管理的一項(xiàng)重要任務(wù)，也是系統(tǒng)執(zhí)行并發(fā)控制的前提[4-6]。

當(dāng)前事務(wù)管理的研究大量集中在對新型應(yīng)用中出現(xiàn)的新事務(wù)的并發(fā)控制協(xié)議的研究上，以便確保并行事務(wù)執(zhí)行的可串行化調(diào)度。但對并行事務(wù)調(diào)度是否具有可串行化的判定，仍然基于傳統(tǒng)的執(zhí)行圖的判定方法[7-9]。執(zhí)行圖的判定方法原理比較簡單，首先判斷在一個調(diào)度中、并發(fā)沖突事務(wù)集合中事務(wù)之間的執(zhí)行優(yōu)先關(guān)系，然后以有向圖這種數(shù)據(jù)結(jié)構(gòu)存儲：事務(wù)表示為圖中的節(jié)點(diǎn)，事務(wù)之間的執(zhí)行優(yōu)先關(guān)系表示為節(jié)點(diǎn)之間的有向邊；在建立好完全的圖結(jié)構(gòu)后，通過圖搜索方法遍歷整個圖，如果圖中不存在環(huán)這種結(jié)構(gòu)，就判斷并發(fā)事務(wù)集的當(dāng)前調(diào)度是可串行化的，否則就是不可串行化的。要實(shí)現(xiàn)這種傳統(tǒng)的判定方法，需要建立復(fù)雜的圖數(shù)據(jù)結(jié)構(gòu)，并要建立便于圖中節(jié)點(diǎn)的遍歷和回溯的索引結(jié)構(gòu)來實(shí)現(xiàn)圖的搜索[10]，直接的圖搜索算法沒有相應(yīng)的環(huán)的識別，還需要改進(jìn)的圖搜索算法來支持環(huán)的識別。

本文從關(guān)系運(yùn)算的代數(shù)方法出發(fā)，提出了基于事務(wù)執(zhí)行優(yōu)先關(guān)系的閉包運(yùn)算和由此建立的聯(lián)合邏輯公式的計(jì)算，通過邏輯判定來檢驗(yàn)并發(fā)事務(wù)的可串行化。通過定理證明和實(shí)例驗(yàn)證，所提出的基于邏輯公式的代數(shù)判定方法取得了同執(zhí)行圖判定相同的效果，而且判定更直觀，更易于操作實(shí)現(xiàn)，不需要建立復(fù)雜的圖數(shù)據(jù)結(jié)構(gòu)和在圖搜索中檢測環(huán)是否出現(xiàn)。

1 定義及概念

1.1 事務(wù)的并發(fā)調(diào)度及可串行化調(diào)度

例如：從賬戶A向賬戶B轉(zhuǎn)賬1 000元，系統(tǒng)查找到賬戶A，檢查賬戶的余額大于1 000時，讀出余額并從中減去1 000元，然后把減去的余額寫回到A賬戶中。找到B賬戶，讀出B賬戶余額后加上1 000元，再把加后的余額寫回到B賬戶中。這一系列的過程要么全部都發(fā)生，要么全不發(fā)生，這就是事務(wù)。

定義1[11]事務(wù)(Transaction)是構(gòu)成單一邏輯工作單元的操作集合，要么完整的執(zhí)行，要么完全不執(zhí)行。無論發(fā)生何種情況，DBS必須保證事務(wù)能正確、完整的執(zhí)行。

以銀行系統(tǒng)中多個事務(wù)對多個賬戶進(jìn)行存取操作為例。事務(wù)T1從賬戶A轉(zhuǎn)100元到賬戶B，定義如下：

T1：Read(A);A:=A-100;Write(A);Read(B);

B:=B+100;Write(B);

T2從賬戶A中轉(zhuǎn)10%的存款到賬戶B，定義如下：

T2：Read(A);X=A×0.1;A:=A-X;Write(A);

Read(B);B:=B+X;Write(B)

如系統(tǒng)先執(zhí)行T1的前3條指令，然后轉(zhuǎn)向T2，并執(zhí)行它的前四條指令，接著再轉(zhuǎn)向T1，執(zhí)行T1的后3條指令，最后轉(zhuǎn)向T2，執(zhí)行它的后3條指令。在這種類型的執(zhí)行順序中，兩個事務(wù)的指令交替執(zhí)行，稱為并發(fā)調(diào)度。

定義2[11]事務(wù)的執(zhí)行次序稱為調(diào)度。如果多個事務(wù)依次執(zhí)行，則稱為事務(wù)的串行調(diào)度；如果利用分時的方法同時處理多個事務(wù)，稱為事務(wù)的并發(fā)調(diào)度。

定義3[12]如果事務(wù)的并發(fā)調(diào)度對數(shù)據(jù)庫狀態(tài)的影響與某個串行調(diào)度相同，那么這個并發(fā)調(diào)度能保持?jǐn)?shù)據(jù)庫狀態(tài)的一致，這樣的調(diào)度是正確的，并稱為可串行化調(diào)度。

一個可串行化的并發(fā)調(diào)度與某個串行調(diào)度對數(shù)據(jù)庫的影響相同。例如文獻(xiàn)[12]定義了兩個事務(wù)T1、T2，兩個數(shù)據(jù)項(xiàng)A、B，初始狀態(tài)都為50。事務(wù)T1、T2的定義及其一個串行化調(diào)度如圖1所示，將圖1中的調(diào)度稱為調(diào)度1。

T1T2Read(A)A:=A+100Write(A)Read(B)B:=B+100Write(B)Read(A)A:=A?2Write(A)Read(B)B:=B?2Write(B)

圖1 串行化調(diào)度1：T1先于T2執(zhí)行

再給出這兩個事務(wù)的并發(fā)調(diào)度的例子，如圖2所示，圖2的調(diào)度稱為調(diào)度2。

T1T2Read(A)A:=A+100Write(A)Read(A)A:=A?2Write(A)Read(B)B:=B+100Write(B)Read(B)B:=B?2Write(B)

圖2 并發(fā)調(diào)度2

通過對并發(fā)調(diào)度2分析可知，由于T1中的操作“Read(B);B:=B+100;Write(B)”和T2中的操作“Read(A);A:=A*2;Write(A)”可以非沖突交換(即相鄰操作交換執(zhí)行的先后次序不會影響操作的結(jié)果)至先執(zhí)行T1后執(zhí)行T2，即調(diào)度2對數(shù)據(jù)庫狀態(tài)的影響與調(diào)度1是相同的，故它是一個可串行化的并發(fā)調(diào)度[12]。

定義4[12]對于兩個調(diào)度S1和S2，如果S1的一系列相鄰動作經(jīng)過非沖突交換能轉(zhuǎn)換成S2；同樣地，如果S2的一系列相鄰動作經(jīng)過非沖突交換能轉(zhuǎn)換成S1，則這兩個調(diào)度是沖突等價的。當(dāng)一個調(diào)度沖突等價于一個串行調(diào)度時，這個調(diào)度就是沖突可串行化的。

調(diào)度2沖突等價于調(diào)度1，而且調(diào)度2是沖突可串行化的。

1.2 基于執(zhí)行圖的沖突可串行化判定

判斷一個調(diào)度是否是沖突可串行化，只要檢查該調(diào)度中出現(xiàn)沖突的操作的順序是否與一個串行調(diào)度中出現(xiàn)的順序相同即可。如果相同，則說明是沖突可串行化的；如果不同，就不是沖突可串行化的。

定義5[12]已知調(diào)度S，其中事務(wù)T1、T2，如果T1的動作A1和T2的動作A2滿足下面的情況，則T1的執(zhí)行優(yōu)先于T2，記為T1

(1) 在調(diào)度S中，A1在A2前；

(2)A1和A2都涉及同一個數(shù)據(jù)庫元素；

(3)A1和A2中至少有一個是寫。

此時，任何一個與S沖突等價的調(diào)度中，A1都要出現(xiàn)在A2前。如果這個調(diào)度是與S沖突等價的串行調(diào)度，則T1一定出現(xiàn)在T2前。所以只要檢查出一個調(diào)度中任何兩個沖突操作的順序，并確定其是否與沖突等價的串行調(diào)度中的事務(wù)的順序相同。如果相同，該調(diào)度就是可串行化調(diào)度[12]。

定義6[12]優(yōu)先圖由節(jié)點(diǎn)和有向弧兩種元素構(gòu)成，節(jié)點(diǎn)代表事務(wù)，有向弧表示事務(wù)執(zhí)行的先后次序。如果T1

利用優(yōu)先圖判斷是否是沖突可串行化的準(zhǔn)則：如果調(diào)度S的優(yōu)先圖中沒有環(huán)，則S是沖突可串行化的，如果優(yōu)先圖中有環(huán)，則S不是沖突可串行化的[12]。

例1下面的調(diào)度由3個事務(wù)T1、T2、T3的動作構(gòu)成[12]：

S1：r2(A);r1(B);w2(A);r3(A);w1(B);w3(A);r2(B);w2(B)

在調(diào)度S中，可以找到的相鄰沖突操作有w2(A)和r3(A)，w1(B)和r2(B)。w2(A)在r3(A)前，說明T2

圖3 調(diào)度S1的執(zhí)行圖

如果將調(diào)度S1中r2(B)向前移動3個位置，該調(diào)度就變?yōu)椋?/p>

S2：r2(A);r1(B);w2(A);r2(B);r3(A);w1(B);w3(A);w2(B)

在該調(diào)度中可以找到相鄰的沖突操作有r2(B)和w1(B)，w2(A)和r2(A)，w1(B)和w2(B)。

r2(B)在w1(B)之前，說明T2

圖4 調(diào)度S2的執(zhí)行圖

圖3無環(huán)說明調(diào)度S1是可串行化的，而且沖突等價于串行調(diào)度(T1,T2,T3)；圖4有環(huán)說明調(diào)度S2不是沖突可串行化的，因?yàn)檎也坏揭粋€沖突等價的串行化調(diào)度[12]。這種執(zhí)行圖判定方法在實(shí)現(xiàn)時，需要系統(tǒng)存貯“圖”這種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)和便于圖節(jié)點(diǎn)遍歷和回溯訪問的索引結(jié)構(gòu)[10]，并需要在圖的搜索方法中識別“環(huán)”，而我們的方法完全基于關(guān)系運(yùn)算的代數(shù)方法，直接根據(jù)邏輯公式的運(yùn)算進(jìn)行判定，簡單易行。

1.3 事務(wù)執(zhí)行優(yōu)先關(guān)系的閉包計(jì)算

事務(wù)執(zhí)行優(yōu)先關(guān)系T1

定義7設(shè)F是并發(fā)事務(wù)集上的執(zhí)行優(yōu)先關(guān)系集合，T是其中任一個事務(wù)，那么(相對于F)事務(wù)T的閉包用T+表示，它是一個從F集使用傳遞推理規(guī)則推出的、或?yàn)镕包含的所有滿足T

T+={事務(wù)A|F?T

算法1求事務(wù)T相對于執(zhí)行優(yōu)先關(guān)系集F的閉包T+

輸入：事務(wù)T；事務(wù)執(zhí)行優(yōu)先關(guān)系集F

輸出：T相對于F的閉包T+

步驟：

{T+:=T;

Do {

OldT+:=T+;

For eachY

IfY?T+thenT+:=T+∪{Z};

} while(T+≠oldT+);

T+:=T+-{T};

Return(T+);

}

和函數(shù)依賴屬性集閉包計(jì)算中函數(shù)依賴關(guān)系[11]不同的是，事務(wù)執(zhí)行優(yōu)先關(guān)系并不具有自反性，即不存在T1

定義8設(shè)F是并發(fā)事務(wù)集上的執(zhí)行優(yōu)先關(guān)系集合，根據(jù)傳遞推理性規(guī)則得到的所有執(zhí)行優(yōu)先關(guān)系和F自身包含的優(yōu)先關(guān)系構(gòu)成的全體集合，稱為F的閉包,記為F+。形式化表達(dá)為：

F+=F∪{X

算法2求并發(fā)事務(wù)集TU的優(yōu)先執(zhí)行關(guān)系集閉包F+

輸入：并發(fā)事務(wù)集合TU，事務(wù)優(yōu)先執(zhí)行關(guān)系集F

輸出：F+

步驟：

{

F+:=?;

For eachT∈TUdo

{

調(diào)用算法1，計(jì)算T+；

IfT+≠? then

{

For eachA∈T+do

F+:=F+∪{T

}

}

Return(F+);

}

例2已知并發(fā)事務(wù)TU={T1,T2,T3},事務(wù)執(zhí)行優(yōu)先關(guān)系集合F={T1

根據(jù)算法2，當(dāng)T=T1時，調(diào)用算法1得到T+={T2,T3}，所以F+={T1

根據(jù)定義5，如果T1

定義9如果一對事務(wù)T1、T2，已知T1

定義10類似(T1

1.4 謂詞邏輯公式

謂詞表示個體性質(zhì)或個體之間的關(guān)系，一些更復(fù)雜的關(guān)系和性質(zhì)可用多元謂詞或謂詞與聯(lián)結(jié)詞復(fù)合形式描述[13]。例如“3小于2”可以表示為：L(3,2)。

定義11[13]原子公式、量詞和聯(lián)結(jié)詞按照一定規(guī)則組成的，用以表示復(fù)雜命題的符號串，稱為謂詞邏輯合適公式，簡稱為謂詞邏輯公式或謂詞公式。謂詞公式按如下方式生成：

(1) 原子公式是謂詞公式；

(3) 如果A和B是謂詞公式,則(A∧B)、(A∨B)、(A→B)、(A?B)是謂詞公式；

(4) 如果A是謂詞公式，(?x)A、(?x)A是謂詞公式；

(5) 有限次使用(1)、(2)、(3)、(4)后得到的字符串才是謂詞公式。

2 本文算法

以下定理及證明作為本文提出的判定算法的理論基礎(chǔ)，即表明該算法設(shè)計(jì)的正確性。

定理1若調(diào)度S中一對沖突事務(wù)只有唯一的可串行化交換方向，則調(diào)度S中T1和T2可串行化，且得到?jīng)_突等價可串行化調(diào)度的交換方向?yàn)樵摲较颍駝t調(diào)度S中T1和T2必不可串行化。

證明：假定T1和T2存在兩個可串行化交換方向，T1和T2是可串行化的。不妨設(shè)T1和T2的一個可串行化方向?yàn)門1，即O1和O2是不可交換的；如果T1

我們的判定方法需完全檢測沖突事務(wù)集合，在事務(wù)集的兩兩事務(wù)檢測中累積(T1

定理2沖突事務(wù)集的并發(fā)調(diào)度S中存在的每一對沖突事務(wù)的可串行化交換方向Tm

由定理1可知，在調(diào)度S中Ti和Tj不可串行化，即調(diào)度S沒有沖突等價的可串行化調(diào)度；反之，若(T1

根據(jù)以上定理，我們設(shè)計(jì)以下算法判定并發(fā)事務(wù)集TU的調(diào)度S是否可串行化。

算法3根據(jù)邏輯公式判定并發(fā)調(diào)度S的可串行性

輸入：并發(fā)事務(wù)集TU和并發(fā)調(diào)度S

輸出：若具有可串行性則返回true,否則返回false

Step1根據(jù)定義5，得到并發(fā)調(diào)度S中TU上事務(wù)之間的優(yōu)先執(zhí)行關(guān)系，所有這種優(yōu)先關(guān)系形成集合F；

Step2根據(jù)算法2，求F+，將事務(wù)集TU上事務(wù)分配一個識別碼Tid,按Tid由小到大排序；

Step4將所有謂詞按邏輯“與”組合成合取公式：

ξ=Small(T1,T2)∧…∧Small(Tm,Tn)

由定理1和定理2的證明可知算法3是正確的，由文獻(xiàn)[11]可知改進(jìn)的閉包計(jì)算是可終止的，即算法3是可終止的。

3 實(shí)例分析

為了驗(yàn)證本文提出算法的實(shí)用性和有效性，采用文獻(xiàn)[12]中的實(shí)例，并用本文算法進(jìn)行詳細(xì)分析。

例3如下調(diào)度由3個事務(wù)T1、T2、T3的動作構(gòu)成。

S：r2(A);r1(B);w2(A);r3(A);w1(B);w3(A);r2(B);w2(B)。

即有并發(fā)事務(wù)集TU={T1,T2,T3}，按算法3分析如下：

第一步：根據(jù)定義5在調(diào)度S中可以找到的相鄰沖突操作有w2(A)和r3(A)，w1(B)和r2(B)。w2(A)在r3(A)前，說明T2

第二步：調(diào)用算法2，計(jì)算F+。

當(dāng)T=T1時，T+={T2,T3}，F(xiàn)+={T1

當(dāng)T=T2時，T+={T3}，F(xiàn)+={T1

當(dāng)T=T3時，T+=?，F(xiàn)+={T1

第三步：根據(jù)F+，建立謂詞：Small(T1,T2)，Small(T1,T3)，Small(T2,T3)。

第四步：組成合取公式：ξ=Small(T1,T2)∧Small(T1,T3)∧Small(T2,T3)=true，即TU={T1,T2,T3}的調(diào)度S可串行化，該結(jié)論與文獻(xiàn)[12]中分析結(jié)果一致。

例4調(diào)度S：r2(A);r1(B);w2(A);r2(B);r3(A);w1(B);w3(A);w2(B)。即有并發(fā)事務(wù)集TU={T1,T2,T3}，按算法3處理如下：

第一步:根據(jù)定義5在該調(diào)度中可以找到相鄰的沖突操作有r2(B)和w1(B)、w2(A)和r2(A)、w1(B)和w2(B)。r2(B)在w1(B)之前，說明T2

第二步：調(diào)用算法2，計(jì)算F+。

當(dāng)T=T1時，T+={T2,T3},F+={T1

當(dāng)T=T2時，T+={T3,T1},F+={T1

當(dāng)T=T3時，T+=?,F+={T1

例5考慮下面的調(diào)度S:r2(A);w2(A);r3(A);w1(B);w3(A);r2(B);w2(B);r1(A);w1(A)。即有并發(fā)事務(wù)集TU={T1,T2,T3}，按算法3分析如下：

第一步：根據(jù)定義5在調(diào)度S中可以找到相鄰沖突操作有w2(A)和r3(A)、w1(B)和r2(B)、w3(A)和r1(A)。w2(A)在r3(A)之前，則T2

第二步：調(diào)用算法2，計(jì)算F+。

當(dāng)T=T1時，T+={T2,T3},F+={T1

當(dāng)T=T2時，T+={T3,T1},F+={T1

當(dāng)T=T3時，T+={T1,T2},F+={T1

根據(jù)文獻(xiàn)[12]可以建立如圖5所示的執(zhí)行圖。

圖5 例5中調(diào)度S的執(zhí)行圖

由于圖5中出現(xiàn)了環(huán)，可以判斷調(diào)度S不可串行化，即本文算法3可取得利用文獻(xiàn)[12]中執(zhí)行圖判定同樣的效果。但本文方法完全是基于關(guān)系閉包計(jì)算和謂詞公式計(jì)算的代數(shù)方法，算法實(shí)現(xiàn)時不用轉(zhuǎn)換為圖結(jié)構(gòu)存貯，也無需在圖搜索算法中“識別”環(huán)。

4 結(jié) 語

并發(fā)事務(wù)可串行化判定是事務(wù)并發(fā)控制的重要任務(wù)之一，現(xiàn)有方法采用執(zhí)行圖判定，具體實(shí)現(xiàn)判定功能時需要存貯為圖這種復(fù)雜數(shù)據(jù)結(jié)構(gòu)，而且需要用圖搜索方法識別“環(huán)”的存在。與這種傳統(tǒng)的、基于圖論的方法不同，本文提出一種基于事務(wù)執(zhí)行優(yōu)先關(guān)系閉包運(yùn)算和一階二元謂詞邏輯公式計(jì)算的代數(shù)方法，算法設(shè)計(jì)邏輯簡明，不需要復(fù)雜的數(shù)據(jù)結(jié)構(gòu)和算法流程。通過理論論證和實(shí)例分析，驗(yàn)證了本文所提方法的正確性和有效性。未來，將結(jié)合并發(fā)事務(wù)控制中鎖機(jī)制和基于時間戳的版本控制方法，提出更加有效的并發(fā)事務(wù)控制方法。