熊中敏 王佳艷 汪 博 陳 明

(上海海洋大學信息學院 上海 201306)(農業(yè)部漁業(yè)信息重點實驗室 上海 201306)

0 引 言

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

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

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

1 定義及概念

1.1 事務的并發(fā)調度及可串行化調度

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

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

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

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

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

T2從賬戶A中轉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條指令，然后轉向T2，并執(zhí)行它的前四條指令，接著再轉向T1，執(zhí)行T1的后3條指令，最后轉向T2，執(zhí)行它的后3條指令。在這種類型的執(zhí)行順序中，兩個事務的指令交替執(zhí)行，稱為并發(fā)調度。

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

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

一個可串行化的并發(fā)調度與某個串行調度對數(shù)據庫的影響相同。例如文獻[12]定義了兩個事務T1、T2，兩個數(shù)據項A、B，初始狀態(tài)都為50。事務T1、T2的定義及其一個串行化調度如圖1所示，將圖1中的調度稱為調度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 串行化調度1：T1先于T2執(zhí)行

再給出這兩個事務的并發(fā)調度的例子，如圖2所示，圖2的調度稱為調度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ā)調度2

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

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

調度2沖突等價于調度1，而且調度2是沖突可串行化的。

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

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

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

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

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

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

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

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

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

例1下面的調度由3個事務T1、T2、T3的動作構成[12]：

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

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

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

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

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

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

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

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

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

1.3 事務執(zhí)行優(yōu)先關系的閉包計算

事務執(zhí)行優(yōu)先關系T1

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

T+={事務A|F?T

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

輸入：事務T；事務執(zhí)行優(yōu)先關系集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ù)依賴屬性集閉包計算中函數(shù)依賴關系[11]不同的是，事務執(zhí)行優(yōu)先關系并不具有自反性，即不存在T1

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

F+=F∪{X

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

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

輸出：F+

步驟：

{

F+:=?;

For eachT∈TUdo

{

調用算法1，計算T+；

IfT+≠? then

{

For eachA∈T+do

F+:=F+∪{T

}

}

Return(F+);

}

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

根據算法2，當T=T1時，調用算法1得到T+={T2,T3}，所以F+={T1

根據定義5，如果T1

定義9如果一對事務T1、T2，已知T1

定義10類似(T1

1.4 謂詞邏輯公式

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

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

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

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

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

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

2 本文算法

以下定理及證明作為本文提出的判定算法的理論基礎，即表明該算法設計的正確性。

定理1若調度S中一對沖突事務只有唯一的可串行化交換方向，則調度S中T1和T2可串行化，且得到沖突等價可串行化調度的交換方向為該方向，否則調度S中T1和T2必不可串行化。

證明：假定T1和T2存在兩個可串行化交換方向，T1和T2是可串行化的。不妨設T1和T2的一個可串行化方向為T1，即O1和O2是不可交換的；如果T1

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

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

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

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

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

輸入：并發(fā)事務集TU和并發(fā)調度S

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

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

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

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

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

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

3 實例分析

為了驗證本文提出算法的實用性和有效性，采用文獻[12]中的實例，并用本文算法進行詳細分析。

例3如下調度由3個事務T1、T2、T3的動作構成。

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

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

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

第二步：調用算法2，計算F+。

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

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

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

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

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

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

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

第二步：調用算法2，計算F+。

當T=T1時，T+={T2,T3},F+={T1

當T=T2時，T+={T3,T1},F+={T1

當T=T3時，T+=?,F+={T1

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

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

第二步：調用算法2，計算F+。

當T=T1時，T+={T2,T3},F+={T1

當T=T2時，T+={T3,T1},F+={T1

當T=T3時，T+={T1,T2},F+={T1

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

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

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

4 結 語

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