1引言1.1多數(shù)據(jù)庫系統(tǒng)的研究背景在過去幾十年中，文件系統(tǒng)、層次數(shù)據(jù)庫系統(tǒng)、網(wǎng)狀數(shù)據(jù)庫系統(tǒng)、關(guān)系數(shù)據(jù)庫系統(tǒng)等都曾作為數(shù)據(jù)管理平臺(tái)廣泛使用，而且基于不同的數(shù)據(jù)庫管理系統(tǒng)建立了大量的應(yīng)用程序。隨著網(wǎng)絡(luò)技術(shù)的成熟和信息時(shí)代的到來，大范圍內(nèi)的信息共享與分布式事務(wù)成為計(jì)算機(jī)應(yīng)用的迫切要求，越來越多的應(yīng)用要存取的數(shù)據(jù)可能涉及到這些分布在不同網(wǎng)絡(luò)節(jié)點(diǎn)上的、不同種類的數(shù)據(jù)庫管理系統(tǒng)。然而，這些數(shù)據(jù)庫管理系統(tǒng)可能在物理和邏輯上都存在著很大的差異，物理上，硬件平臺(tái)可能是不同的；邏輯上則表現(xiàn)為操作系統(tǒng)可能不同，而且不同的數(shù)據(jù)庫可能會(huì)涉及不同的數(shù)據(jù)格式、訪問控制、并發(fā)控制、恢復(fù)策略等。70年代末，人們開始了對(duì)分布式數(shù)據(jù)庫系統(tǒng)（DistributedDatabaseManagementSystems,簡(jiǎn)稱DDBMS）［i,2］的研究。在分布式數(shù)據(jù)庫系統(tǒng)中，數(shù)據(jù)物理上雖然分布在不同的場(chǎng)地，但邏輯上是一個(gè)統(tǒng)一的整體，存在一個(gè)全局的模式，數(shù)據(jù)訪問能實(shí)現(xiàn)場(chǎng)地透明性。但是DDBMS的局部數(shù)據(jù)是同構(gòu)的，若要集成多個(gè)異構(gòu)的數(shù)據(jù)庫管理系統(tǒng)（DBMS）和文件系統(tǒng)，DDBMS則遇到困難。而且在分布式數(shù)據(jù)庫系統(tǒng)中，整個(gè)數(shù)據(jù)庫系統(tǒng)被看成一個(gè)單元，由一個(gè)DBMS來管理，局部數(shù)據(jù)庫系統(tǒng)不具備自治性。而在實(shí)際應(yīng)用中，允許局部數(shù)據(jù)庫系統(tǒng)在局部數(shù)據(jù)庫及在其數(shù)據(jù)上運(yùn)行的事務(wù)保持較高程度的自治是很重要的。目前，應(yīng)用最廣泛也是最成功的解決分布、異構(gòu)和自治的數(shù)據(jù)庫互操作問題34］的方案就是多數(shù)據(jù)庫系統(tǒng)（MultidatabaseSystem，簡(jiǎn)稱MDBS）。多數(shù)據(jù)庫系統(tǒng)w】（MDBS）是在一組已經(jīng)存在的、分布的、異構(gòu)的、自治的數(shù)據(jù)庫管理系統(tǒng)以及文件系統(tǒng)之上為用戶提供一個(gè)統(tǒng)一的存取數(shù)據(jù)的環(huán)境。一個(gè)MDBS是由一組獨(dú)立發(fā)展起來的局部數(shù)據(jù)庫系統(tǒng)（LocalDatabaseSystem，簡(jiǎn)稱LDBS）組成，并在這些LDBS之上為用戶建立一個(gè)統(tǒng)一的存取數(shù)據(jù)的層次，使得用戶像使用一個(gè)統(tǒng)一的數(shù)據(jù)庫系統(tǒng)一樣使用MDBS。另外，多庫系統(tǒng)中的LDBS具有自治性，加入多庫系統(tǒng)對(duì)LDBS上原來的應(yīng)用程序應(yīng)該沒有任何影響，即LDBS上原來的應(yīng)用程序及軟件在LDBS加入多庫系統(tǒng)以后仍能繼續(xù)運(yùn)行，并且這些LDBS上的局部事務(wù)不為MDBS所知，更不受MDBS控制。1.2多數(shù)據(jù)庫系統(tǒng)的主要研究方向關(guān)于多數(shù)據(jù)庫系統(tǒng)的研究工作主要集中在以下幾個(gè)方向：（1）多數(shù)據(jù)庫中的事務(wù)管理⑺：由于MDBS中底層數(shù)據(jù)庫具有自治性，這種自治性主要包括數(shù)據(jù)庫的設(shè)計(jì)自治和執(zhí)行自治兩個(gè)方面，底層數(shù)據(jù)庫的事務(wù)不為MDBS中的事務(wù)管理器所知，因此如何在MDBS中保證事務(wù)執(zhí)行的ACID特性一直是研究的熱點(diǎn)。（2）異構(gòu)模式消解⑻：多數(shù)據(jù)庫系統(tǒng)建立在一組獨(dú)立的局部數(shù)據(jù)庫之上，為用戶提供一個(gè)統(tǒng)一的虛擬的全局?jǐn)?shù)據(jù)模式，而由于局部數(shù)據(jù)庫本身帶有自己的數(shù)據(jù)模式，這樣會(huì)造成MDBS中數(shù)據(jù)沖突，所以多數(shù)據(jù)庫系統(tǒng)中的異構(gòu)數(shù)據(jù)模式的消解問題也是其存在的難點(diǎn)。（3）查詢處理技術(shù)9:在MDBS中采用統(tǒng)一的全局查詢語言，而全局查詢語言與局部數(shù)據(jù)庫的查詢語言可能不同，因此需要轉(zhuǎn)換為對(duì)應(yīng)的局部數(shù)據(jù)庫查詢語言交由局部數(shù)據(jù)庫執(zhí)行，然后再合并各局部查詢結(jié)果產(chǎn)生最終用戶查詢結(jié)果，MDBS中的查詢處理主要包括查詢分解、查詢轉(zhuǎn)換和全局優(yōu)化等部分。（4）全局視圖維護(hù)[io]:在MDBS中對(duì)全局視圖的存取操作要分解為多個(gè)針對(duì)局部數(shù)據(jù)庫的子操作，可能還要對(duì)數(shù)據(jù)模式及查詢語言進(jìn)行相應(yīng)的轉(zhuǎn)換。每當(dāng)局部數(shù)據(jù)庫中的關(guān)系變化時(shí)，MDBS中的全局視圖都要隨之而改變，因此一個(gè)高效的全局視圖維護(hù)算法對(duì)多數(shù)據(jù)庫系統(tǒng)是非常重要的。1.3多數(shù)據(jù)庫系統(tǒng)和事務(wù)管理研究的國(guó)內(nèi)外現(xiàn)狀1.3.1國(guó)內(nèi)外關(guān)于多數(shù)據(jù)庫系統(tǒng)的研究概況自從八十年代中期多數(shù)據(jù)庫系統(tǒng)的概念首次提出后，立即引起了數(shù)據(jù)庫方面研究人員及數(shù)據(jù)庫廠商的密切關(guān)注，到1987年左右，多數(shù)據(jù)庫系統(tǒng)的理論研究已形成體系，并出現(xiàn)了第一批原型系統(tǒng)，同時(shí)各主要數(shù)據(jù)庫廠商也分別推出了支持多數(shù)據(jù)庫系統(tǒng)的商業(yè)產(chǎn)品，包括Sybase、EmpressV2>Ingres/Star、Oracle等。目前數(shù)據(jù)庫廠商推出的多數(shù)據(jù)庫系統(tǒng)產(chǎn)品主要包括：Sybase：Sybase數(shù)據(jù)庫是加利福尼亞的Berkeley大學(xué)研制的，是一個(gè)高性能的關(guān)系數(shù)據(jù)庫系統(tǒng)。Sybase的查詢語言是SQL語言的擴(kuò)展，稱為Transac-SQL，是市場(chǎng)上最先出現(xiàn)的MDBS語言，Sybase后來又推出了更便于用戶使用的MDBS語言VQL(VisualQueryLanguage)oSybase把很多一直在討論之中的MDBS的概念具體實(shí)現(xiàn)了，是一個(gè)標(biāo)志性的產(chǎn)品。EmpressV2:該系統(tǒng)是加拿大多倫多的Rhodius研究中心研制的，EmpressV2可以支持很多平臺(tái)，包括Sun、Vax、Apolio、IBM-PC/PS等。EmpressV2的另一個(gè)特點(diǎn)是它支持多媒體數(shù)據(jù)，是MDBS與多媒體數(shù)據(jù)庫的有機(jī)結(jié)合。DistributedIngres:也稱為Ingres/Star，該系統(tǒng)的特點(diǎn)是可以定義任意數(shù)量的全局?jǐn)?shù)據(jù)模式，全局?jǐn)?shù)據(jù)模式一旦定義，就可以作為Ingres的一個(gè)虛擬數(shù)據(jù)庫來使用，但I(xiàn)ngres不支持對(duì)虛擬數(shù)據(jù)庫的修改。Oracle：Oracle支持的MDBS語言為SQL*PLUS，Oracle也不支持分布式修改，即不支持對(duì)全局?jǐn)?shù)據(jù)模式的修改。雖然越來越多的數(shù)據(jù)庫廠商都聲稱提供對(duì)MDBS的支持，但通過對(duì)這些產(chǎn)品的分析可以發(fā)現(xiàn)，這種支持往往只是對(duì)異地?cái)?shù)據(jù)庫訪問的支持，有很大的局限性，而對(duì)MDBS中的事務(wù)管理、異構(gòu)模式消解、全局視圖維護(hù)等關(guān)鍵技術(shù)都沒有提供很好的解決方案。而且一個(gè)數(shù)據(jù)庫廠商的MDBS產(chǎn)品一般只支持自己的數(shù)據(jù)庫加入MDBS中，對(duì)底層數(shù)據(jù)庫異構(gòu)性的支持還遠(yuǎn)遠(yuǎn)不夠。目前還有一些多數(shù)據(jù)庫系統(tǒng)項(xiàng)目方面的研究，如Pegasus是惠普(HP)開發(fā)的多數(shù)據(jù)庫系統(tǒng)［⑴，它能提供對(duì)本地和外部自治數(shù)據(jù)庫的訪問。Pegasus的系統(tǒng)結(jié)構(gòu)包括三層:智能信息訪問層，協(xié)作信息管理層和局部數(shù)據(jù)訪問層，它的公共數(shù)據(jù)模型是稱為Iris的面向?qū)ο竽Ｐ?，包括三個(gè)部分:對(duì)象、類型和函數(shù)。Pegasus使用一種叫做HOSQL的語言作為數(shù)據(jù)定義和數(shù)據(jù)操作語言，HOSQL是OSQL的超集，它使用非過程化的表達(dá)來操作多個(gè)數(shù)據(jù)庫，支持在Pegasus以及成員數(shù)據(jù)庫中建立類型、函數(shù)和對(duì)象。此外，美國(guó)通用電信公司的GTE實(shí)驗(yàn)室開發(fā)的分布對(duì)象管理系統(tǒng)DOMSm是一個(gè)面向?qū)ο蟮沫h(huán)境，這個(gè)環(huán)境能集成分布異構(gòu)的局部系統(tǒng)，能操作本地對(duì)象。DOMS系統(tǒng)建立在基于分布對(duì)象的一般原則基礎(chǔ)上，DOM作為對(duì)象管理器提供服務(wù)。一個(gè)局部應(yīng)用接口LAI(LocalApplicationInterface)為DOM和局部系統(tǒng)提供接口，它允許DOM訪問局部數(shù)據(jù)，同時(shí)允許局部系統(tǒng)提出對(duì)其它成員系統(tǒng)中的對(duì)象的訪問請(qǐng)求或使用DOM服務(wù)的請(qǐng)求。國(guó)內(nèi)近年來才開始展開關(guān)于多數(shù)據(jù)庫系統(tǒng)的研究，而且大部分集中在多數(shù)據(jù)庫系統(tǒng)集成方面，出現(xiàn)了一些多數(shù)據(jù)庫原型系統(tǒng)。東北大學(xué)的SCOPE/CIMS131.321是為滿足CIMS環(huán)境下信息集成需求而設(shè)計(jì)、實(shí)現(xiàn)的基于CORBA的面向?qū)ο蟮亩鄶?shù)據(jù)庫信息集成系統(tǒng)［13］，它采用了對(duì)象數(shù)據(jù)庫標(biāo)準(zhǔn)ODMG-93中規(guī)定的對(duì)象數(shù)據(jù)模型和對(duì)象查詢語言O(shè)QL作為公共數(shù)據(jù)模型和全局查詢語言。SCOPE/CIMS系統(tǒng)中定義了模式集成操作以及基于模式集成語義的基本查詢處理規(guī)則和路徑表達(dá)式的查詢處理規(guī)則和查詢處理方法，設(shè)計(jì)了一種彈性事務(wù)管理系統(tǒng)，但未考慮并發(fā)控制機(jī)制，對(duì)查詢計(jì)劃的生成及查詢優(yōu)化研究也不多。中國(guó)科學(xué)院軟件研究所設(shè)計(jì)的IS-Global是一個(gè)關(guān)系型多數(shù)據(jù)庫系統(tǒng)［14］，它的全局事務(wù)管理部分只考慮了簡(jiǎn)單的并發(fā)控制機(jī)制，并且各個(gè)局部數(shù)據(jù)庫系統(tǒng)是通過ODBC與多數(shù)據(jù)庫系統(tǒng)相連的，因此效率不高。華中理工大學(xué)開發(fā)的原型系統(tǒng)為Panoramas〕，可以給用戶提供一個(gè)公共數(shù)據(jù)模型和一種全局查詢語言PanoSQL，通過它們將不同的數(shù)據(jù)庫集成到系統(tǒng)中。該系統(tǒng)的主要構(gòu)件包括:集成到Panorama中的局部DBMS的接口、一個(gè)事務(wù)管理器、一個(gè)公共數(shù)據(jù)模型、一個(gè)模式集成器、一種全局查詢語言、一個(gè)全局查詢處理和優(yōu)化器，它支持分布式計(jì)算、跨平臺(tái)操作、不指定數(shù)據(jù)庫源、具有并發(fā)控制機(jī)制可以多用戶進(jìn)行數(shù)據(jù)查詢操作、能處理更改Update語句、并且能處理嵌套事務(wù)。另外，還有北京航空航天大學(xué)研制的MQI是一個(gè)適用于由多種RDBMS組成的多數(shù)據(jù)庫的綜合查詢接口軟件，以SQL作為查詢語言。1.3.2國(guó)內(nèi)外關(guān)于多數(shù)據(jù)庫事務(wù)管理的研究多數(shù)據(jù)庫事務(wù)管理的研究可以追溯到上個(gè)世紀(jì)八十年代，當(dāng)時(shí)最初的工作并沒有考慮事務(wù)管理問題，建立的原型系統(tǒng)如MULTIBASE［16］，僅支持?jǐn)?shù)據(jù)查詢，不允許更新，當(dāng)然也沒有并發(fā)控制機(jī)制來協(xié)調(diào)全局事務(wù)的執(zhí)行。后來，Gligor和Popescu-Zeletin［17］于1986年最早提出多數(shù)據(jù)庫事務(wù)管理問題并分析了多數(shù)據(jù)庫系統(tǒng)中事務(wù)管理的必要性和潛在的困難，給出了多數(shù)據(jù)庫事務(wù)管理的一系列公開問題。從此，多數(shù)據(jù)庫事務(wù)管理成為國(guó)內(nèi)外學(xué)者研究的焦點(diǎn)之一。不幸的是，直到現(xiàn)在這些公開的問題中的大多數(shù)仍沒有得到很好的解決。當(dāng)前給出的實(shí)現(xiàn)方法在一致性或者正確性上作了一定讓步，因?yàn)樵S多研究表明保持局部系統(tǒng)的自治性可能更加重要。在將近二十年的時(shí)間里，多數(shù)據(jù)庫事務(wù)管理的研究成果主要體現(xiàn)在如下幾個(gè)方面。事務(wù)模型及事務(wù)正確性標(biāo)準(zhǔn)多數(shù)據(jù)庫系統(tǒng)中存在全局事務(wù)，全局子事務(wù)和局部事務(wù)，這種兩級(jí)嵌套結(jié)構(gòu)使得傳統(tǒng)的平坦事務(wù)模型不適合多數(shù)據(jù)庫環(huán)境，需要研究新的事務(wù)模型。盡管Moss［i8］提出的嵌套事務(wù)模型能對(duì)父子事務(wù)間的沖突關(guān)系和提交、回退依賴關(guān)系以及子事務(wù)的可見性規(guī)則等進(jìn)行很好地描述，但由于多數(shù)據(jù)庫系統(tǒng)的局部自治性，直接用于多數(shù)據(jù)事務(wù)的建模，也會(huì)遇到困難。需要對(duì)嵌套事務(wù)模型進(jìn)行擴(kuò)展，以適應(yīng)多數(shù)據(jù)庫環(huán)境。P.K.Chrysanthis和K.Ramamrithamw］提出的ACTA形式化框架理論從事務(wù)的行為和事務(wù)之間的相互作用出發(fā)，給出了一個(gè)描述事務(wù)模型系統(tǒng)行為的形式化框架，通過對(duì)事務(wù)的提交、回退、補(bǔ)償和分裂等行為的描述，能很好地對(duì)不同事務(wù)模型進(jìn)行分類、比較和評(píng)價(jià)。以后的一些學(xué)者提出了許多事務(wù)模型，如長(zhǎng)事務(wù)模型、切分事務(wù)模型、彈性事務(wù)模型、可恢復(fù)的通信事務(wù)模型PCA、合作事務(wù)模型和事務(wù)組模型等等。不過這些研究或者性能不令人滿意，或者違反了局部自治性。原子性維護(hù)在多數(shù)據(jù)庫系統(tǒng)中，全局事務(wù)的嚴(yán)格的原子性很難甚至不可能得到保證，應(yīng)當(dāng)修改為語義上的原子性。在分布式數(shù)據(jù)庫系統(tǒng)中，分布事務(wù)的原子性通常采用2PC協(xié)議來實(shí)現(xiàn)。但在多數(shù)據(jù)庫環(huán)境下，并不是每一個(gè)局部數(shù)據(jù)庫均支持2PC協(xié)議，在不支持2PC的情況下，事務(wù)原子性維護(hù)方法可分成下面三種。重做方法:此種方法最先由Y.Breitbart等［20］提出，在假設(shè)每一局部數(shù)據(jù)庫均采用嚴(yán)格的2PL并發(fā)控制機(jī)制前提下，通過執(zhí)行一個(gè)重做事務(wù)來裝入失敗子事務(wù)的寫操作來保證全局事務(wù)的原子性，它包括該全局事務(wù)的子事務(wù)執(zhí)行的所有寫操作。由于局部DBMS不支持準(zhǔn)備-提交狀態(tài)，各個(gè)局部DBMS的全局事務(wù)可以在任何時(shí)候取消，即使GTM已經(jīng)決定提交該事務(wù)。如果在GTM決定提交事務(wù)之后，全局子事務(wù)被局部DBMS取消了，那么在子事務(wù)取消的站點(diǎn)，GTM將發(fā)送一個(gè)重做事務(wù)給局部DBMS，它由子事務(wù)執(zhí)行的所有寫操作組成。在重做事務(wù)失敗的情況下，GTM可重復(fù)發(fā)送直到該重做事務(wù)提交，由于重做事務(wù)僅由寫操作組成，因而不會(huì)出現(xiàn)邏輯錯(cuò)誤。重試方法：S.Mehrotra和A.Zhang等［21,22］對(duì)此方法進(jìn)行了研究，不像重做方法僅對(duì)寫操作重新執(zhí)行，重試方法則對(duì)失敗的整個(gè)全局事務(wù)重新提交執(zhí)行。通過重新提交事務(wù)的成功來保證事務(wù)的原子性，此種方法假設(shè)全局事務(wù)在重試一定的次數(shù)內(nèi)一定能執(zhí)行成功。補(bǔ)償方法：Korth和Levy等⑵］采用補(bǔ)償方法來保證全局事務(wù)的原子性。補(bǔ)償方法是當(dāng)全局事務(wù)回退時(shí)，為已提交的每一全局子事務(wù)生成一個(gè)反向補(bǔ)償事務(wù)，通常提交補(bǔ)償事務(wù)來消除己提交全局子事務(wù)的影響。此種方法需要假設(shè)每一全局子事務(wù)均存在反向補(bǔ)償事務(wù)，同時(shí)局部數(shù)據(jù)庫應(yīng)該滿足可恢復(fù)性，否則不可能全部消除全局子事務(wù)對(duì)局部數(shù)據(jù)庫的影響。此外，我們希望將補(bǔ)償事務(wù)嚴(yán)格地限制在子事務(wù)提交的站點(diǎn)，需要注意兩點(diǎn):一是在子事務(wù)的補(bǔ)償事務(wù)執(zhí)行之前，防止其它全局事務(wù)看到該子事務(wù)所寫的狀態(tài)。二是限制全局事務(wù)的子事務(wù)之間不存在數(shù)據(jù)依賴性。在這種情況下，需要補(bǔ)償?shù)奶峤蛔邮聞?wù)的結(jié)果不會(huì)用于其它站點(diǎn)，這就可將補(bǔ)償限制在事務(wù)提交的站點(diǎn)。除了獨(dú)立運(yùn)用上述三種方法來保證事務(wù)的原子性，研究人員提出了結(jié)合三種方法的混合原子性保證策略2。同時(shí)值得注意的是，當(dāng)支持2PC的局部數(shù)據(jù)庫和不支持2PC的局部數(shù)據(jù)庫并存的情況下，Perrizo等提出了對(duì)不支持2PC的局部數(shù)據(jù)庫模擬一個(gè)準(zhǔn)備提交狀態(tài)，將其轉(zhuǎn)化成支持2PC的局部數(shù)據(jù)庫，通過2PC協(xié)議來保證原子性的方法。目前國(guó)內(nèi)在多數(shù)據(jù)庫事務(wù)管理方面的探討卻寥寥無幾，東南大學(xué)研制的Galaxy是一個(gè)基于CORBA的分布式異構(gòu)數(shù)據(jù)源集成系統(tǒng)四，使用對(duì)象集成模型(OIM)作為數(shù)據(jù)集成的公共模型，對(duì)象集成查詢語言(OIQL)作為其查詢語言。OIQL在SQL語言的基礎(chǔ)上增加了一些構(gòu)造符，用于完成對(duì)象之間的導(dǎo)航式查詢以及對(duì)一些集合類型對(duì)象的查詢。Galaxy給出了一種事務(wù)失敗的恢復(fù)方法和基于混和圖的并發(fā)控制機(jī)制，可以查詢數(shù)據(jù)庫、啊叩數(shù)據(jù)等信息源，但對(duì)查詢優(yōu)化考慮得并不多。中山大學(xué)研究了一個(gè)聯(lián)邦數(shù)據(jù)庫GD-MDBS，它是緊耦合型系統(tǒng)，具有統(tǒng)一全局模式也主要是集中在模式集成；用戶可透明訪問各類關(guān)系數(shù)據(jù)庫，但不能更改操作，沒有并發(fā)控制與事務(wù)處理能力。1.4本文的工作通過總結(jié)目前多數(shù)據(jù)庫系統(tǒng)以及事務(wù)管理方面的國(guó)內(nèi)外研究概況，針對(duì)多數(shù)據(jù)庫系統(tǒng)在以上幾個(gè)關(guān)鍵技術(shù)上還存在的不足之處，而事務(wù)管理器在多數(shù)據(jù)庫系統(tǒng)中處于核心部件的地位，本文選取多數(shù)據(jù)庫系統(tǒng)中的事務(wù)管理方向進(jìn)行研究，著重討論MDBS中事務(wù)管理器模型的并發(fā)控制策略和保證全局事務(wù)的正確性和一致性，然后借助TPC-C測(cè)試工具模擬并發(fā)用戶得出實(shí)驗(yàn)結(jié)論。本文大致結(jié)構(gòu)是第2節(jié)將介紹多數(shù)據(jù)庫系統(tǒng)的三層體系結(jié)構(gòu)及其事務(wù)模型，設(shè)計(jì)其中核心部件一一全局事務(wù)管理器，并描述事務(wù)的工作流程以及狀態(tài)管理，同時(shí)還說明了全局事務(wù)管理器中的恢復(fù)管理器所采用的事務(wù)恢復(fù)機(jī)制。第3節(jié)進(jìn)一步在MDBS的全局事務(wù)管理中引入謂詞級(jí)的多粒度事務(wù)并發(fā)控制概念以及通過檢測(cè)謂詞沖突圖的方式來避免全局事務(wù)間的死鎖。第4節(jié)為了保證GTM中并發(fā)全局事務(wù)的沖突可串行化，我們改進(jìn)了以事務(wù)提交圖控制事務(wù)提交順序的事務(wù)調(diào)度管理算法。第5節(jié)概述了TPC-C基準(zhǔn)測(cè)試的特征，在搭建的通用實(shí)驗(yàn)平臺(tái)上采用TPC-C測(cè)試工具模擬多個(gè)并發(fā)客戶端通過標(biāo)準(zhǔn)接口訪問多數(shù)據(jù)庫系統(tǒng)，在此基礎(chǔ)上測(cè)試比較了全局事務(wù)管理器中謂詞級(jí)與表級(jí)兩種多粒度的事務(wù)處理的并發(fā)度，同時(shí)還對(duì)改進(jìn)的事務(wù)提交圖調(diào)度算法進(jìn)行了對(duì)比測(cè)試。最后一節(jié)得出結(jié)論全局事務(wù)管理器中的事務(wù)并發(fā)控制策略是提高多數(shù)據(jù)庫系統(tǒng)性能的關(guān)鍵因素，同時(shí)還總結(jié)了該MDBS中的全局事務(wù)管理器在事務(wù)方面所需要做的進(jìn)一步工作。2多數(shù)據(jù)庫系統(tǒng)中全局事務(wù)管理器的設(shè)計(jì)2.1多數(shù)據(jù)庫系統(tǒng)體系結(jié)構(gòu)多數(shù)據(jù)庫系統(tǒng)是一種C/S(Client/Server)模式下的三層體系結(jié)構(gòu)，多個(gè)全局客戶端用戶可以通過MDBS對(duì)單個(gè)或多個(gè)局部數(shù)據(jù)庫進(jìn)行存取操作。MDBS作為中間層主要由全局事務(wù)管理器(GlobalTransactionManager，簡(jiǎn)稱GTM)和局部代理(LocalAgent，簡(jiǎn)稱LA)兩大部分構(gòu)成，圖1中給出了多數(shù)據(jù)庫系統(tǒng)的體系結(jié)構(gòu)，其中全局事務(wù)管理器建立在多個(gè)局部DBMS之上，向上層提供統(tǒng)一的用戶接口，使用戶能同時(shí)訪問多個(gè)局部DBMS中的數(shù)據(jù)。全局事務(wù)管理器中存儲(chǔ)和管理所有全局?jǐn)?shù)據(jù)庫系統(tǒng)的控制信息，包括全局模式、全局查詢的處理以及全局事務(wù)的提交和控制等。全局事務(wù)管理器從全局用戶接受全局事務(wù)請(qǐng)求，并根據(jù)全局控制信息把全局事務(wù)劃分成在對(duì)應(yīng)局部站點(diǎn)上執(zhí)行的全局子事務(wù)，然后通過局部代理(LA)分別提交到相應(yīng)的局部數(shù)據(jù)庫(LDBS)上執(zhí)行，最后將執(zhí)行的結(jié)果合并后返回給全局用戶。此外，為了保證全局事務(wù)的一致性和執(zhí)行的原子性，全局事務(wù)管理器還負(fù)責(zé)全局事務(wù)的調(diào)度及事務(wù)失敗時(shí)的恢復(fù)管理OMDBS中的局部代理是GTM與LDBS的接口，負(fù)責(zé)向LDBS提交從全局得到的全局子事務(wù)，為GTM返回全局子事務(wù)的執(zhí)行結(jié)果，同時(shí)局部代理還是全局事務(wù)原子提交協(xié)議的協(xié)調(diào)參與者。在本地站點(diǎn)上的局部用戶仍然以原來的方式向LDBS提交局部事務(wù)，對(duì)局部DBMS而言，全局子事務(wù)和局部事務(wù)并沒有什么區(qū)別，均由局部DBMS的事務(wù)調(diào)度和恢復(fù)機(jī)制保證正確的執(zhí)行。圖1多數(shù)據(jù)庫系統(tǒng)體系結(jié)構(gòu)從MDBS的體系結(jié)構(gòu)可以看出，構(gòu)成MDBS的各個(gè)站點(diǎn)上的局部數(shù)據(jù)庫沒有做任何改動(dòng)，因此本地站點(diǎn)上的用戶仍可以對(duì)局部數(shù)據(jù)庫進(jìn)行直接訪問，具有接收用戶事務(wù)、執(zhí)行事務(wù)直到事務(wù)終止(或提交或失敗)以及返回結(jié)果的功能。局部數(shù)據(jù)庫上原來的應(yīng)用程序還可以直接運(yùn)行于原來的數(shù)據(jù)庫之上，保證了局部數(shù)據(jù)庫的自治性。對(duì)于MDBS的全局用戶而言，他所看到的只是MDBS，他只與MDBS打交道，從而就屏蔽了局部數(shù)據(jù)庫的分布性和異構(gòu)性。2.2MDBS中的事務(wù)處理模型在多數(shù)據(jù)庫系統(tǒng)中，全局用戶的事務(wù)是由全局事務(wù)管理器進(jìn)行調(diào)度和并發(fā)控制的，而局部用戶的事務(wù)是由本地站點(diǎn)上局部數(shù)據(jù)庫本身的事務(wù)管理器進(jìn)行管理的，由于局部數(shù)據(jù)庫上的事務(wù)管理器是設(shè)計(jì)自治和執(zhí)行自治的，這里文中只考慮相對(duì)于在MDBS中全局事務(wù)管理器所執(zhí)行的事務(wù)處理模型，我們把只在一個(gè)站點(diǎn)上執(zhí)行的事務(wù)稱為局部事務(wù)或本地事務(wù)：局部事務(wù)定義1：一個(gè)提交到某個(gè)站點(diǎn)上的數(shù)據(jù)庫LDBj執(zhí)行的事務(wù)￡?是局部TOC\o"1-5"\h\z事務(wù)，當(dāng)且僅當(dāng)BSoLDBj，BS=RSDWS,RS={R(x)|R(x)eL},WS={W(x)lII11IIIW(x)eL}。其中BS表示事務(wù)L在局部站點(diǎn)上的所有操作集合，RS表示事務(wù)L?????在局部站點(diǎn)上的讀操作集，WS,表示事務(wù)L.在局部站點(diǎn)上的寫操作集。而全局事務(wù)是需要在多個(gè)本地站點(diǎn)上執(zhí)行的事務(wù)：假設(shè)多數(shù)據(jù)庫集合為MDB=jLDBL全局事務(wù)定義［2鈕：一個(gè)事務(wù)是全局事務(wù)G，當(dāng)且僅當(dāng)(VLDBjeMDB)(BS屯LDBj),BS=RSDWS,RS={R(x)|llllllR(x)eG},WS={W(x)|W(x)eG.}。該定義表示全局事務(wù)管理器中調(diào)度的全局事務(wù)存取的讀寫集不僅僅只包含于一個(gè)站點(diǎn)上數(shù)據(jù)庫執(zhí)行而是跨多個(gè)站點(diǎn)的。由以上定義可知局部事務(wù)僅在一個(gè)站點(diǎn)數(shù)據(jù)庫上執(zhí)行，而全局事務(wù)需要發(fā)送到多個(gè)站點(diǎn)數(shù)據(jù)庫上執(zhí)行，而全局事務(wù)經(jīng)過全局事務(wù)管理器分解為多個(gè)子事務(wù)，子事務(wù)是僅對(duì)應(yīng)一個(gè)站點(diǎn)數(shù)據(jù)庫執(zhí)行的事務(wù)，因此子事務(wù)就是僅在一個(gè)站點(diǎn)上執(zhí)行的局部事務(wù)。在多數(shù)據(jù)庫系統(tǒng)中存在著由全局用戶提交的在單個(gè)或多個(gè)站點(diǎn)執(zhí)行的全局事務(wù)，也存在由本地站點(diǎn)上的局部用戶提交到局部數(shù)據(jù)庫系統(tǒng)上的局部事務(wù),所以在每個(gè)本地站點(diǎn)的局部數(shù)據(jù)庫系統(tǒng)既可以執(zhí)行由全局事務(wù)劃分的全局子事務(wù)又可以

執(zhí)行本地用戶的局部事務(wù)，它們都在本地站點(diǎn)上被看作局部事務(wù)，所不同的是本地用戶的局部事務(wù)執(zhí)行結(jié)果返回給局部用戶，而全局子事務(wù)則由全局事務(wù)管理器處理后返回給全局用戶。2.3全局事務(wù)管理器的結(jié)構(gòu)設(shè)計(jì)全局事務(wù)管理器負(fù)責(zé)將全局事務(wù)劃分成多個(gè)全局子事務(wù)，提交給站點(diǎn)上的局部數(shù)據(jù)庫執(zhí)行,協(xié)調(diào)全局子事務(wù)執(zhí)行，全局事務(wù)要保證事務(wù)執(zhí)行的原子性、正確性,因而必需設(shè)計(jì)全局事務(wù)的調(diào)度和并發(fā)控制算法。本文在側(cè)重于MDBS中全局事務(wù)管理的設(shè)計(jì)過程中，為了簡(jiǎn)化操作，局部代理由全局事務(wù)管理器調(diào)用相應(yīng)的代理線程完成局部代理功能，而對(duì)于局部站點(diǎn)上數(shù)據(jù)庫由于具有自治性，其事務(wù)的一致性和原子性由本地事務(wù)管理器來控制，不需要MDBS中的全局事務(wù)管理器參與。全局事務(wù)管理的內(nèi)部結(jié)構(gòu)包括：上層通信連接模塊，語法分析模塊，事務(wù)劃分模塊，事務(wù)調(diào)度模塊，恢復(fù)管理器，查詢集成管理模塊，統(tǒng)一訪問接口模塊等功能模塊以及全局?jǐn)?shù)據(jù)字典和全局日志等全局控制信息。如下圖2所示：上層通信連接語法分析GTM-+-■-T--'LDB1?士LDBn圖2上層通信連接語法分析GTM-+-■-T--'LDB1?士LDBn其中全局?jǐn)?shù)據(jù)字典存放MDBS中各站點(diǎn)上局部數(shù)據(jù)庫的表或關(guān)系和數(shù)據(jù)分布信息，各個(gè)局部站點(diǎn)中的表或關(guān)系可以相同也可以不同，表中數(shù)據(jù)在站點(diǎn)間分布的方式包括Range或Hash等水平劃分方法，GTM依此來判斷全局事務(wù)中的SQL操作所訪問劃分表或復(fù)制表以及所在的站點(diǎn)，以便發(fā)送到對(duì)應(yīng)的站點(diǎn)上執(zhí)行。另外，還需說明的是GTM中的全局日志信息，它不同于傳統(tǒng)數(shù)據(jù)庫中的日志記錄格式，在全局日志中記錄劃分的全局子事務(wù)原始語句和在局部站點(diǎn)上的狀態(tài)信息使恢復(fù)管理器能夠跟蹤和恢復(fù)失敗的全局事務(wù)。GTM中的查詢集成管理是專門用于處理各局部站點(diǎn)上返回的查詢數(shù)組記錄，而對(duì)其它如增加，刪除，更新等操作不需要進(jìn)行結(jié)果集處理。全局事務(wù)在GTM中的工作流程為：上層通信管理通過標(biāo)準(zhǔn)ODBC或JDBC接口接受客戶端應(yīng)用程序發(fā)送的SQL語句或其他命令，通信模塊啟動(dòng)線程與每個(gè)客戶端建立相應(yīng)的會(huì)話連接。語法分析模塊對(duì)每個(gè)客戶端的請(qǐng)求語句首先進(jìn)行詞法分析，然后語法分析，并生成中間結(jié)構(gòu)。在事務(wù)劃分模塊中根據(jù)全局?jǐn)?shù)據(jù)字典中記錄的全局控制信息如表劃分或表復(fù)制的信息以及查詢謂詞等，對(duì)生成的語句中間結(jié)構(gòu)進(jìn)行進(jìn)一步地分解或轉(zhuǎn)換。事務(wù)調(diào)度模塊負(fù)責(zé)事務(wù)的并發(fā)調(diào)度和決定提交或回滾事務(wù)以確?？缯军c(diǎn)事務(wù)的可串行化，接受上層模塊傳遞已分解或變換的SQL語句結(jié)構(gòu)，在全局日志中登記其訪問信息，并將子語句通過統(tǒng)一數(shù)據(jù)訪問接口分發(fā)到局部站點(diǎn)上執(zhí)行。底層局部數(shù)據(jù)庫將事務(wù)執(zhí)行結(jié)果經(jīng)統(tǒng)一數(shù)據(jù)訪問接口返回給查詢集成管理模塊緩存，同時(shí)還將事務(wù)的執(zhí)行返回代碼發(fā)回事務(wù)調(diào)度模塊中保存事務(wù)狀態(tài)。事務(wù)調(diào)度模塊等待所有子語句執(zhí)行完畢后，收集完整的全局事務(wù)狀態(tài)信息，控制查詢集成管理模塊對(duì)全部查詢結(jié)果以及執(zhí)行信息進(jìn)行合并處理，然后把統(tǒng)一的查詢結(jié)果和執(zhí)行信息返回給客戶端請(qǐng)求?；謴?fù)管理器模塊跟蹤事務(wù)執(zhí)行狀態(tài)根據(jù)全局事務(wù)日志在異常情況下進(jìn)行事務(wù)的恢復(fù)操作。2.4全局事務(wù)執(zhí)行狀態(tài)管理MDBS中全局事務(wù)管理器以會(huì)話方式與客戶端建立連接，在每一個(gè)連接內(nèi)串行執(zhí)行SQL語句，我們把兩次連續(xù)成功的commit之間的操作，稱為一個(gè)全局事務(wù)。在應(yīng)用程序中，只要遇到以下操作語句：delete、insert、select、update、open和exec，就表示事務(wù)開始。當(dāng)遇到操作commitwork或rollbackwork時(shí)就表示事務(wù)結(jié)束。也就是說commit和rollback表示當(dāng)前事務(wù)結(jié)束，下一個(gè)事務(wù)開始。全局事務(wù)管理器在ODBC編程的時(shí)候通過使用SQLSetConnectOption()函數(shù)來選擇顯式的全局事務(wù)提交模式，此外當(dāng)全局事務(wù)管理器遇到DDL語句時(shí)就以自動(dòng)方式提交全局事務(wù)。全局事務(wù)管理器主要保證全局事務(wù)的一致性，處理事務(wù)的沖突，確定全局事務(wù)的子事務(wù)的執(zhí)行順序和狀態(tài)。事務(wù)調(diào)度模塊記錄全局事務(wù)在個(gè)子站點(diǎn)上的執(zhí)行狀態(tài)，由于本地自治的數(shù)據(jù)庫系統(tǒng)只提供支持事務(wù)的接口：begin，abort，commit操作。為了保持本地站點(diǎn)的自治性全局事務(wù)執(zhí)行狀態(tài)可分為：active，abort，commit，prepared四種，它們相互間的狀態(tài)轉(zhuǎn)換如圖3所示表示事務(wù)的終結(jié)狀態(tài)圖3事務(wù)狀態(tài)轉(zhuǎn)換圖當(dāng)全局事務(wù)被全局事務(wù)管理器調(diào)度時(shí)就進(jìn)入了活躍狀態(tài)(active)，然后經(jīng)檢測(cè)如果有死鎖發(fā)生就被事務(wù)管理器取消也就是進(jìn)入abort狀態(tài)，如果無死鎖就在第一階段事務(wù)管理器調(diào)用代理線程向全局日志寫記錄同時(shí)通過底層接口發(fā)送到發(fā)往局部站點(diǎn)上執(zhí)行，如果全局子事務(wù)都成功執(zhí)行則向事務(wù)調(diào)度模塊返回事務(wù)準(zhǔn)備(prepared)狀態(tài)，等待第二階段接收提交(commit)請(qǐng)求在局部站點(diǎn)上提交。如果部分全局子事務(wù)執(zhí)行失敗處理就較復(fù)雜，事務(wù)調(diào)度模塊收到返回值后報(bào)告給全局日志，恢復(fù)管理根據(jù)日志中跟蹤的全局事務(wù)狀態(tài)決定重做(redo)或回滾(rollback)該事務(wù)，如果重做失敗就要恢復(fù)其他已成功執(zhí)行的子事務(wù)對(duì)局部數(shù)據(jù)庫產(chǎn)生的影響。如果要回滾全局事務(wù)，事務(wù)就進(jìn)入abort狀態(tài)。此外，進(jìn)入準(zhǔn)備(prepared)狀態(tài)的全局事務(wù)在提交過程中也可能被本地站點(diǎn)上的局部數(shù)據(jù)庫中止，這樣不能成功提交的全局事務(wù)也要被終止(abort)。能成功提交的全局事務(wù)只有在所有子事務(wù)都成功提交時(shí)，才進(jìn)入最終的提交(commit)狀態(tài)。以上是全局事務(wù)管理器采用兩階段提交協(xié)議(2PC)[27]來保證全局事務(wù)執(zhí)行的原子性，它是多數(shù)據(jù)庫系統(tǒng)的事務(wù)管理器中標(biāo)準(zhǔn)的事務(wù)管理協(xié)議，在這種協(xié)議中全局事務(wù)在各場(chǎng)地的局部子事務(wù)執(zhí)行完后，并不立即釋放占用的資源，而是進(jìn)入準(zhǔn)備提交狀態(tài)，向全局事務(wù)管理器發(fā)送全部子事務(wù)執(zhí)行正確的消息，事務(wù)管理器只有收到所有全局子事務(wù)的執(zhí)行狀態(tài)信息之后，才能決定全局事務(wù)是否提交或回退，當(dāng)且僅當(dāng)各全局子事務(wù)均正確執(zhí)行時(shí)，全局事務(wù)才能提交，否則該全局事務(wù)就被撤消。當(dāng)各全局子事務(wù)接受到事務(wù)管理器的事務(wù)提交消息時(shí)，全局子事務(wù)如果提交成功，則對(duì)各站點(diǎn)上的數(shù)據(jù)庫做永久更改并釋放占用的資源，否則各局部數(shù)據(jù)庫就回滾(rollback)全局子事務(wù)。2.5全局事務(wù)的恢復(fù)全局事務(wù)管理器中全局事務(wù)執(zhí)行的原子特性是由其恢復(fù)管理器來保證的，恢復(fù)管理器根據(jù)全局日志中記錄的全局事務(wù)狀態(tài)信息通常采用重做(redo)，重試(retry)或補(bǔ)償(compensate)等方式來恢復(fù)全局事務(wù)在全部或部分站點(diǎn)上的失敗。當(dāng)GTM收到處于準(zhǔn)備狀態(tài)的全局事務(wù)的提交操作時(shí)，各站點(diǎn)上執(zhí)行的全局子事務(wù)如果被某個(gè)局部DBMS取消了，那么在子事務(wù)取消的站點(diǎn)，恢復(fù)管理器將發(fā)送一個(gè)重做(redo)事務(wù)給局部DBMS,它僅由該全局子事務(wù)執(zhí)行的所有寫操作組成，在重做子事務(wù)失敗的情況下，恢復(fù)管理器可重復(fù)發(fā)送，直到該重做事務(wù)提交，這種情況要求局部DBMS所調(diào)度的子事務(wù)是非級(jí)聯(lián)的才能保證全局事務(wù)的原子性。當(dāng)全局事務(wù)處于活躍狀態(tài)時(shí)，考慮全局事務(wù)Ti，它在站點(diǎn)s1和s2執(zhí)行。當(dāng)全局事務(wù)操作完成后，GTM發(fā)送一個(gè)“準(zhǔn)備”消息給各個(gè)執(zhí)行該事務(wù)的站點(diǎn)。站點(diǎn)上的各局部DBMS便馬上發(fā)送一個(gè)提交Ti的操作，Ti可能在s1提交而在s2被取消。這樣Ti的原子性就被破壞了，并且由于全局事務(wù)可以讀、寫局部數(shù)據(jù)，因而不能使用上述重做方法，在這種情況下有兩種選擇:重試和補(bǔ)償。如果采用重試方法，該方法重新執(zhí)行整個(gè)被取消的子事務(wù)而不僅僅是寫操作。這時(shí)恢復(fù)管理器將根據(jù)日志信息重新發(fā)送失敗的子事務(wù)Ti2給s2，作為一個(gè)新的子事務(wù)L，，這并不等于簡(jiǎn)單地重新生成Ti2的寫操作。Ti2,需要被運(yùn)行，并可能讀、寫不同的值。只有當(dāng)事務(wù)管理器中的日志保存了為Ti2所用的Ti的執(zhí)行狀態(tài)(例如執(zhí)行Ti的程序中的局部變量)時(shí)才可這樣做。同時(shí)要求子事務(wù)Ti2必須是可重試的，也就是說，如果Ti2重試了足夠多的次數(shù)（從任何數(shù)據(jù)庫狀態(tài)）最終將被提交。這一點(diǎn)非常重要，因?yàn)樵谧邮聞?wù)重試之前，由于其它局部事務(wù)的執(zhí)行，該局部DBMS的狀態(tài)可能發(fā)生變化。如果采用補(bǔ)償方法，恢復(fù)管理器在該全局事務(wù)的子事務(wù)提交的各個(gè)站點(diǎn)運(yùn)行一個(gè)補(bǔ)償事務(wù)，從語義上撤消已提交子事務(wù)的結(jié)果，再次考慮上述情況，事務(wù)Ti在站點(diǎn)si提交而在s2被取消。這可以通過在站點(diǎn)si處執(zhí)行一個(gè)補(bǔ)償事務(wù)CT來實(shí)現(xiàn)，i1從語義的觀點(diǎn)來看它撤消Tii所做的工作。注意在該情況中，為了補(bǔ)償子事務(wù)孔，補(bǔ)償事務(wù)僅在執(zhí)行Ti】的站點(diǎn)si上執(zhí)行。然而，如果Ti】的結(jié)果已被用于其它站點(diǎn)，那么我們同樣需要在那些站點(diǎn)補(bǔ)償Tii，這不太符合實(shí)際，因?yàn)橥ǔ碚f對(duì)于在一個(gè)站點(diǎn)上提交的子事務(wù)，其補(bǔ)償事務(wù)需要在所有站點(diǎn)上執(zhí)行。另外，如果GTM中處于活躍狀態(tài)的全局事務(wù)在所有的站點(diǎn)上都執(zhí)行失敗，那么恢復(fù)管理器就直接中止該全局事務(wù)而不需采用以上方法進(jìn)行恢復(fù)操作，這樣全局事務(wù)的原子性比較容易得到保證。3全局事務(wù)管理器中并發(fā)控制策略3.iGTM現(xiàn)有的全局事務(wù)并發(fā)控制方法保持跨站點(diǎn)執(zhí)行的并發(fā)全局事務(wù)的正確性是多數(shù)據(jù)庫系統(tǒng)的全局事務(wù)管理需要解決的核心問題之一。沖突可串行化一直作為數(shù)據(jù)庫系統(tǒng)的事務(wù)正確性準(zhǔn)則，相應(yīng)地，全局事務(wù)執(zhí)行的全局可串行化通常作為多數(shù)據(jù)庫系統(tǒng)的事務(wù)一致性標(biāo)準(zhǔn)。Y.Breitbart提出了可串行化準(zhǔn)則"：一個(gè)全局調(diào)度是全局可串行化的，當(dāng)且僅當(dāng)提交給多數(shù)據(jù)庫系統(tǒng)的所有全局事務(wù)滿足一種全序關(guān)系，并且這種全序關(guān)系與全局事務(wù)在每一場(chǎng)地的串行化次序保持一致。處理此問題的方法有Y.Breitbart等［28］提出了SGT(SerializationGraphTesting)算法，D.Georgakopoulos等［29］提出的Ticket算法和A.Zhang等［30］提出的基于沖突鏈串行化(Chain-conflictserializability)和全共享串行化(Full-sharingserializability)的方法，所有這些算法均是保證事務(wù)正確性的充分非必要條件。由于全局事務(wù)間可能存在間接沖突，同時(shí)多數(shù)據(jù)庫系統(tǒng)需要維護(hù)局部系統(tǒng)的自治性，滿足全局可串行化的許多方法會(huì)帶來低的事務(wù)并發(fā)度，因而另一種解決問題的辦法是研究比全局可串行化更弱的事務(wù)正確性標(biāo)準(zhǔn)°W.Du等［31,32］提出的近似可串行化(quasiserializability)是一個(gè)比全局可串行化弱的一致性方法，但只有在局部數(shù)據(jù)庫之間沒有共同的數(shù)據(jù)集且全局事務(wù)存取的不同場(chǎng)地的數(shù)據(jù)項(xiàng)間不存在值依賴關(guān)系的條件下才能保證全局事務(wù)的正確性。S.Mehrotra等邸提出的兩級(jí)可串行化(2LSR)標(biāo)準(zhǔn)比近似可串行化更弱，只要適當(dāng)?shù)貙?duì)事務(wù)的完整約束加以限制，就能保證全局事務(wù)的正確執(zhí)行。Elmagarmid［34］從80年代中期開始研究多數(shù)據(jù)庫事務(wù)處理，他提出了quasi串行性來解決由于局部事務(wù)造成的間接沖突。另外，還有一些學(xué)者給出了對(duì)局部數(shù)據(jù)庫增加一定限制的并發(fā)控制方案［35］。本文將要提出的是基于謂詞的多粒度并發(fā)控制方法，沖突謂詞構(gòu)造的謂詞沖突圖既克服了兩個(gè)或多個(gè)全局事務(wù)間由直接沖突或間接沖突而產(chǎn)生的死鎖，又提高了全局事務(wù)處理效率，同時(shí)也不需對(duì)局部數(shù)據(jù)庫做任何限制。3.2GTM的事務(wù)沖突可串行化及提交策略3.2.1謂詞級(jí)多粒度并發(fā)控制GTM中多個(gè)并發(fā)的全局事務(wù)間的沖突可分為直接沖突和間接沖突，全局事務(wù)間的沖突歸根結(jié)底是由兩個(gè)或兩個(gè)以上的事務(wù)在相同站點(diǎn)上同時(shí)訪問相同的數(shù)據(jù)對(duì)象而引起的。這種全局事務(wù)間沖突類型有讀一寫、寫一寫和寫一讀沖突三種。兩個(gè)全局事務(wù)間的直接沖突定義3：當(dāng)且僅當(dāng)下列條件成立時(shí)稱兩操作p和q是直接沖突的，記為pCTq:i.peT，qeT,T尹T；(3xeS)(p(x)=W(x)Vq(x)=W(x))；「3(peT,qeT)((pYq)V(qYp)),其中Y表示先序關(guān)系。兩個(gè)全局事務(wù)G,G產(chǎn)生的直接沖突可表示為：GrG。由定義可知，兩個(gè)或多個(gè)數(shù)據(jù)操作產(chǎn)生沖突的條件是：1)兩操作屬于不同的全局事務(wù)；2)兩操作訪問相同站點(diǎn)上的同一數(shù)據(jù)項(xiàng)且其中至少有一個(gè)為寫操作否則就不會(huì)產(chǎn)生沖突；3)兩操作都同時(shí)訪問數(shù)據(jù)對(duì)象亦即兩全局事務(wù)在時(shí)間上同時(shí)發(fā)生才可能產(chǎn)生沖突。兩個(gè)或以上的全局事務(wù)間的間接沖突定義［364:兩個(gè)全局事務(wù)G,G,.是間接沖突的，當(dāng)且僅當(dāng)存在一個(gè)調(diào)度S的事務(wù)序列T,T,…，T,12k3TeS,TeS,…，TeS((GrT)A(TrT)A?A(TrG))nGr…12ki112kjirG。兩個(gè)全局事務(wù)G,Gj產(chǎn)生的間接沖突表示為：GWrGj.?；跊_突檢測(cè)的方法不對(duì)本地?cái)?shù)據(jù)庫中的并發(fā)控制部分作任何修改，僅修改沖突的定義，以支持多數(shù)據(jù)庫系統(tǒng)的要求，所有的全局事務(wù)都由多數(shù)據(jù)庫中的全局事務(wù)管理器調(diào)度?；谥^詞的沖突檢測(cè)全局事務(wù)在以SQL語句形式執(zhí)行時(shí)只有對(duì)應(yīng)的DML操作會(huì)產(chǎn)生讀一寫、寫一寫和寫一讀三種沖突，而DML操作有四種：select、update、insert和delete,它們的沖突矩陣圖如圖4：selectupdateinsertdeleteselectYN-NupdateNN-Ninsert--Y-deleteN圖4NSQL語-句沖突矩N陣圖其中圖中Y表示操作在元組級(jí)上沖突是相容的，N表示在元組級(jí)上是不相容的，一表示在元組級(jí)上無法沖突(因?yàn)闊o法對(duì)未知插入元組加鎖，只能加表級(jí)鎖)，進(jìn)而退化到表級(jí)是沖突不相容的，該矩陣圖防止了數(shù)據(jù)庫中出現(xiàn)的幻象現(xiàn)象。我們把SQL語句中的DML操作select、update、insert和delete等效于讀寫操作來代替，select等于讀操作，insert，update和delete等于寫操作，insert與insert都是在關(guān)系中插入新的元組，因此如果允許關(guān)系中存在重復(fù)元組時(shí)insert與insert是相容的。沖突的判斷采用謂詞方法［37］謂詞一般可分為謂詞常項(xiàng)（表示具體性質(zhì)和關(guān)系的詞）和謂詞變項(xiàng)（表示抽象的或泛指的謂詞）。亦就是根據(jù)全局事務(wù)的SQL語句中DML四種操作所帶的where分詞條件進(jìn)行沖突判斷，這種分詞條件可以是謂詞常項(xiàng)，例如：書名=’數(shù)據(jù)庫原理’；也可以是謂詞變項(xiàng)，例如：數(shù)量Between50And100。在進(jìn)行全局事務(wù)多粒度的沖突判斷時(shí)，首先根據(jù)SQL語句沖突矩陣圖檢測(cè)全局事務(wù)中的SQL操作在相同站點(diǎn)上的關(guān)系或表上是否相容，如果不相容就有可能產(chǎn)生直接沖突，然后再判斷所帶謂詞條件是否有交集，如果交集不空就存在沖突，否則全局事務(wù)不會(huì)直接產(chǎn)生沖突。謂詞的直接沖突判斷算法流程如圖5所示：全局事務(wù)在表級(jí)操作是否沖突N?加入謂詞沖突圖圖5謂詞直接沖突流程該過程不需具體的上鎖操作，因此可以提高事務(wù)處理的并發(fā)度，全局事務(wù)間直接沖突判斷的粒度能精確到謂詞級(jí)。SQL語句中的where分詞條件可以分為三類：復(fù)合條件、相關(guān)子查詢和集合，對(duì)于復(fù)雜的子句條件和不帶where條件的insert操作，我們就直接鎖定在表級(jí)進(jìn)行沖突判斷，而不需進(jìn)一步精確到謂詞級(jí)。全局事務(wù)進(jìn)行謂詞沖突判斷的整個(gè)過程是：對(duì)于支持多數(shù)據(jù)庫系統(tǒng)的全局事務(wù)管理器首先判斷分解的全局事務(wù)在不同站點(diǎn)產(chǎn)生是否沖突，然后再判斷全局子事務(wù)在站點(diǎn)上的關(guān)系（表級(jí)）是否沖突，最后縮小沖突判斷粒度到謂詞級(jí)根據(jù)SQL沖突矩陣圖判斷操作是否相容，如相容就讓全局子事務(wù)并發(fā)執(zhí)行，如果可能不相容就根據(jù)謂詞集條件判斷是否有相交的元組存在以進(jìn)一步確定是否沖突，如果存在沖突就把該全局事務(wù)加入到謂詞沖突圖中；如果謂詞集條件不在相同屬性上就無法判斷元組是否有交集，因此不能縮小粒度就直接在表級(jí)判斷為沖突?？傊疀_突判斷粒度級(jí)依次為：站點(diǎn)級(jí)T表級(jí)T謂詞級(jí)，整個(gè)檢測(cè)粒度是”自粗而細(xì)”逐漸升級(jí)的過程。多個(gè)并發(fā)的全局事務(wù)可能因?yàn)橹苯記_突或間接沖突而形成死鎖，以上首先對(duì)全局事務(wù)間的直接沖突判斷，還需要借助謂詞沖突圖進(jìn)一步判斷全局事務(wù)是否形成死鎖。針對(duì)兩個(gè)全局事務(wù)由直接沖突產(chǎn)生死鎖條件：（1）至少存在兩對(duì)直接沖突（2）必須存在兩個(gè)不同時(shí)序關(guān)系的沖突對(duì)，這樣才可能在謂詞沖突圖中形成環(huán)。對(duì)于全局事務(wù)的間接沖突由以上定義可知，是由兩個(gè)以上全局事務(wù)間的直接沖突產(chǎn)生的，所以死鎖檢測(cè)也比較復(fù)雜，需要檢測(cè)謂詞沖突圖中形成間接沖突的每個(gè)全局事務(wù)是否形成環(huán)來判斷死鎖，如果形成環(huán)就需要立即解除死鎖的發(fā)生，這里全局事務(wù)管理器采取回滾（rollback）最近加入環(huán)的全局事務(wù)，以保證資源利用的最大化。（2）謂詞沖突圖中的死鎖檢測(cè)傳統(tǒng)的解決死鎖問題的方法有三種：預(yù)防死鎖、檢測(cè)死鎖及避免死鎖。死鎖預(yù)防要求用戶進(jìn)程事先申報(bào)所需的資源或按嚴(yán)格的規(guī)程申請(qǐng)資源，而死鎖檢測(cè)原則上應(yīng)允許死鎖發(fā)生，在適當(dāng)?shù)臅r(shí)機(jī)檢查，若發(fā)生死鎖，則設(shè)法排除之。與預(yù)防死鎖相比，后者過于放手，致使死鎖頻繁。而避免死鎖則以事務(wù)撤消為前提，當(dāng)不能獲得資源批準(zhǔn)時(shí)，立刻進(jìn)行死鎖檢測(cè)。它既不象預(yù)防死鎖那樣過于保守，也不象死鎖檢測(cè)那樣過于放開而且檢測(cè)及時(shí)，所以檢測(cè)算法比較簡(jiǎn)單。我們采用構(gòu)造謂詞沖突圖方法來檢測(cè)死鎖，如果謂詞沖突圖中存在環(huán)就證明全局事務(wù)會(huì)形成死鎖。全局事務(wù)在謂詞沖突圖中形成的環(huán)可分為兩類：兩個(gè)全局事務(wù)由直接沖突形成的環(huán)和兩個(gè)以上全局事務(wù)由間接沖突形成的環(huán)。謂詞沖突圖的構(gòu)建方法：謂詞沖突圖中的結(jié)點(diǎn)集由沖突的全局事務(wù)集構(gòu)成，對(duì)于產(chǎn)生直接沖突的兩個(gè)全局事務(wù)G,Gj并且GGj（G先于巳執(zhí)行的順序）在沖突圖中用帶注釋的有向箭頭邊表示為：G「1七，S表示G,Gj產(chǎn)生直接沖突的站點(diǎn)。兩個(gè)全局事務(wù)由直接沖突形成的環(huán)的條件：必須存在至少兩對(duì)以上直接沖突操作我們稱為兩個(gè)全局事務(wù)間存在多沖突。該條件是全局事務(wù)由直接沖突形成環(huán)的必要條件。

對(duì)于一個(gè)全局事務(wù)只在一個(gè)站點(diǎn)上而另一全局事務(wù)卻是跨站點(diǎn)執(zhí)行情況，即如圖6所示圖6跨站點(diǎn)的全局事務(wù)沖突此情況不具備成環(huán)條件，在該站點(diǎn)1上沖突交由底層局部站點(diǎn)處理即可。兩個(gè)全局事務(wù)由直接沖突產(chǎn)生沖突環(huán)分為在同一站點(diǎn)和不在同一站點(diǎn)上兩種情況：（a）在同一站點(diǎn)上產(chǎn)生環(huán)（a）在同一站點(diǎn)上產(chǎn)生環(huán)（b）在不同站點(diǎn)上產(chǎn)生環(huán)圖7兩個(gè)全局事務(wù)產(chǎn)生環(huán)的可能情況其圖7對(duì)應(yīng)產(chǎn)生的謂詞沖突圖分別為:（a）在同一站點(diǎn)上產(chǎn)生環(huán)（b）（a）在同一站點(diǎn)上產(chǎn)生環(huán)（b）在不同站點(diǎn)上產(chǎn)生環(huán)對(duì)于全局事務(wù)在同一站點(diǎn)上可能形成環(huán)的沖突例如圖8（a）不必由多數(shù)據(jù)庫中的全局事務(wù)管理器處理，因?yàn)槿质聞?wù)的子事務(wù)都是局部化到一個(gè)站點(diǎn)上執(zhí)行的，而本地站點(diǎn)上的DBMS有相應(yīng)的并發(fā)控制機(jī)制。由于本地站點(diǎn)由于自治性無法知道其他站點(diǎn)全局事務(wù)間的關(guān)系，所以全局事務(wù)管理器需要處理的是在跨站點(diǎn)的全局事務(wù)產(chǎn)生的環(huán)，而這種環(huán)可能是兩個(gè)全局事務(wù)由直接沖突產(chǎn)生的如圖8（b），也

可能是由間接沖突產(chǎn)生的。對(duì)于兩個(gè)以上全局事務(wù)由間接沖突產(chǎn)生環(huán)的條件：如果一個(gè)全局事務(wù)G通過間接沖突與自己沖突即G-O-G那么在謂詞沖突圖中也會(huì)產(chǎn)生環(huán)。如圖9所示:間接沖突與自己沖突即G-O-G那么在謂詞沖突圖中也會(huì)產(chǎn)生環(huán)。如圖9所示:，全局事務(wù)間的間接沖突產(chǎn)生的環(huán)圖9其對(duì)應(yīng)的謂詞沖突圖如圖10所示:圖10全局事務(wù)間的間接謂詞沖突圖全局事務(wù)管理器只處理跨站點(diǎn)的全局事務(wù)形成的死鎖，當(dāng)在謂詞沖突圖中檢測(cè)到?jīng)_突的全局事務(wù)形成環(huán)(包括本身形成的間接環(huán)如G—…—G和兩個(gè)全局事務(wù)形成的直接環(huán)如G1—G2和G2—G1)時(shí)，就立即回滾(rollback)其中最近加入環(huán)中的一個(gè)全局事務(wù)就可以解除死鎖了。如果全局事務(wù)管理器調(diào)度的沖突全局事務(wù)在謂詞沖突圖中沒有形成環(huán)或無沖突時(shí)，就可以繼續(xù)發(fā)送到底層局部站點(diǎn)上執(zhí)行。在后面的章節(jié)中，我們將會(huì)在全局事務(wù)管理器中實(shí)現(xiàn)謂詞級(jí)的多粒度事務(wù)并發(fā)控制并且經(jīng)過TPC-C測(cè)試證明該并發(fā)控制策略有效防止了全局事務(wù)間的死鎖，比表級(jí)粒度的并發(fā)控制在事務(wù)回滾率上有明顯的降低。4GTM中事務(wù)提交圖管理算法在多數(shù)據(jù)庫系統(tǒng)中全局事務(wù)管理器采用事務(wù)提交圖［2。，38］控制全局事務(wù)的提交順序，事務(wù)提交圖是一個(gè)無向的二分圖G=({T,S},E)，圖中的頂點(diǎn)集由全局事務(wù)集T和局部站點(diǎn)集S組成，在二分圖中對(duì)于VTeT,TeTnE了wEvE.wE，同理對(duì)于VSeS，SeSnEwEvEwE，E表示全局事務(wù)T與T之間的邊，E表TOC\o"1-5"\h\zikikkiijij示二分圖的邊集，因此由上式關(guān)系可知，二分圖G中的邊集僅連接事務(wù)結(jié)點(diǎn)T和i站點(diǎn)結(jié)點(diǎn)S，事務(wù)T與站點(diǎn)S之間的邊表示事務(wù)T在站點(diǎn)S上已執(zhí)行了讀寫操作kikik并正在提交。全局事務(wù)可以只在一個(gè)站點(diǎn)上執(zhí)行所有的操作如圖11(a)，也可以跨多個(gè)站點(diǎn)執(zhí)行操作如圖11(b)。當(dāng)一個(gè)全局事務(wù)只在一個(gè)站點(diǎn)上執(zhí)行時(shí)，就局部化成前面所定義的局部事務(wù)了。T1T1/AS1S1S2(a)子事務(wù)僅在站點(diǎn)S1上執(zhí)行(b)全局事務(wù)跨站點(diǎn)S1和S2執(zhí)行圖11全局事務(wù)提交圖全局事務(wù)在執(zhí)行提交操作時(shí)首先要與訪問過的站點(diǎn)建立臨時(shí)邊聯(lián)系，然后在事務(wù)提交圖中判斷是否與其他正在提交的全局事務(wù)形成環(huán)(一個(gè)全局事務(wù)到另一個(gè)全局事務(wù)間的無向路徑)，如果沒有形成提交環(huán)就可以直接執(zhí)行提交操作，如果形成了提交環(huán)就要加入到等待隊(duì)列中，等待環(huán)中其他事務(wù)先提交后才能提交。當(dāng)全局事務(wù)T成功執(zhí)行提交操作時(shí)，那么T與對(duì)應(yīng)的執(zhí)行站點(diǎn)S的提交邊就要立即從iik提交圖中刪除，所以全局事務(wù)在執(zhí)行提交操作時(shí)通過檢測(cè)事務(wù)提交圖中是否存在提交環(huán)來保證全局事務(wù)提交順序的可串行化。參考文獻(xiàn)［38］中Mehrotra等人提出了兩種事務(wù)管理算法TM1和TM2，它們都是通過提交圖來保證全局事務(wù)執(zhí)行順序的可串行化。對(duì)于算法TM1是通過阻止事務(wù)提交圖形成環(huán)來保證全局可串行化，但只適合于全局事務(wù)間沒有沖突的情況。算法TM2在此基礎(chǔ)做了改進(jìn)，保證了兩個(gè)全局事務(wù)在相同站點(diǎn)上無讀-寫或?qū)?讀沖突的情況下并發(fā)提交，同時(shí)該算法還保持了全局事務(wù)執(zhí)行的一致性，當(dāng)全局事務(wù)的提交操作被局部數(shù)據(jù)庫終止時(shí)，全局事務(wù)管理器將級(jí)聯(lián)回滾其他受影響的全局事務(wù)，全局事務(wù)管理器調(diào)度算法TM2如下：Stepl.當(dāng)全局事務(wù)管理器（GTM）收到全局事務(wù)T的提交操作后，先臨時(shí)把Tii和對(duì)應(yīng)的執(zhí)行站點(diǎn)組成的邊＜T,七＞加入到提交圖中。Step2.然后檢測(cè)經(jīng)過擴(kuò)充的提交圖是否形成環(huán)，如果提交圖包含環(huán)，GTM就把該全局事務(wù)T放入等待隊(duì)列中并在圖中刪除與之相連的局部站點(diǎn)的邊。iStep3.如果提交圖中不包含環(huán)，GTM檢查是否有未被中止并且還未提交的另一全局事務(wù)T.在站點(diǎn)S上與T沖突即T與T有讀寫或?qū)懽x沖突并且T還沒有jkiikjkjk在站點(diǎn)Sk提交。Step4.如果存在與T相沖突的全局事務(wù)T，GTM就把T.放入到等待隊(duì)列并從提交圖中刪除相連的臨時(shí)邊。Step5.如果不存在與T沖突的全局事務(wù)T，GTM就對(duì)T按EC：39］（EarlyCommit，GTM對(duì)R-Server發(fā)送提交消息而對(duì)W-Server發(fā)送投票消息）協(xié)議提交，那么加入的臨時(shí)邊在提交圖中變成永久的。Step6.如果在某站點(diǎn)S上，在GTM決定提交全局事務(wù)T后而子事務(wù)T卻被kiik本地?cái)?shù)據(jù)庫中止時(shí)，那么每個(gè)讀過被子事務(wù)T^寫過的數(shù)據(jù)的全局事務(wù)二也必須中止。然后代理Server在站點(diǎn)S^上就重做（redo）該子事務(wù)T的寫操作直到重做事務(wù)在站點(diǎn)sk上提交。而且每當(dāng)重做事務(wù)在站點(diǎn)sk被中止時(shí)，對(duì)于每個(gè)與子事務(wù)七有數(shù)據(jù)依賴且未提交的全局事務(wù)二也都要被中止。Step7.對(duì)于在所有本地站點(diǎn)上完成提交操作的全局事務(wù)T就從提交圖中刪i除與事務(wù)T相連的邊以便使事務(wù)T沒有到其他還未完成提交操作的全局事務(wù)的路ii徑。Step8.當(dāng)全局事務(wù)從提交圖中被刪除相連的邊后或全局事務(wù)在完成提交或中止后，GTM取出等待隊(duì)列中的其他全局事務(wù)七使用步驟1，2和3在提交圖中檢查提交操作能否提交到本地站點(diǎn)上執(zhí)行。由算法TM2可知，事務(wù)提交圖中的邊是全局事務(wù)正在站點(diǎn)上提交且還未完成的邊，而這些邊只有形成環(huán)時(shí)全局事務(wù)間才產(chǎn)生提交順序的不一致性，提交圖中的全局事務(wù)并不是在執(zhí)行時(shí)檢測(cè)是否有提交環(huán)存在，而是在提交時(shí)才檢測(cè)環(huán)的存在，這種情況下如果存在環(huán)就進(jìn)入等待隊(duì)列中，另一種情況是雖然在提交圖中無提交環(huán)，但在進(jìn)一步檢測(cè)與其他正在執(zhí)行的全局事務(wù)有讀寫或?qū)懽x沖突時(shí)也進(jìn)入等待隊(duì)列中。正是由于這兩種情況導(dǎo)致算法TM2全局事務(wù)處理效率低下，存在一些缺點(diǎn)。算法TM2首先在保證了全局事務(wù)提交順序的全局可串行化后再進(jìn)行沖突檢測(cè)，但其缺點(diǎn)是并沒有保證全局事務(wù)執(zhí)行的沖突可串行化，另外無沖突的全局事務(wù)間的其提交順序是可以并行的，因?yàn)闊o沖突的并發(fā)提交操作順序的先后是不會(huì)造成數(shù)據(jù)不一致性的。例如圖12中所示，當(dāng)全局事務(wù)T1要在站點(diǎn)S1和S2上提交時(shí)，按照算法TM2首先加入臨時(shí)邊到提交圖中經(jīng)檢測(cè)無環(huán)后進(jìn)入Step3進(jìn)行沖突檢測(cè)也無沖突時(shí)分別在站點(diǎn)S1和S2上提交，同時(shí)當(dāng)T1還未完成提交操作時(shí)另一全局事務(wù)T2也在站點(diǎn)S1和S2上提交假設(shè)T2與T1并無沖突，在加入邊到提交圖中后檢測(cè)到了提交環(huán)，那么按照算法T2要?jiǎng)h除加入提交圖中的臨時(shí)邊同時(shí)進(jìn)入等待隊(duì)列。這樣無沖突的全局事務(wù)本來可以同時(shí)提交的卻讓T2進(jìn)入等待隊(duì)列變成T1和T2的串行提交，降低了事務(wù)處理的并發(fā)度。S1S2圖12T1和T2在提交圖中構(gòu)成環(huán)所以算法TM2雖然保證了事務(wù)提交順序的全局可串行化，但降低了全局事務(wù)執(zhí)行及提交的并發(fā)度。此外，當(dāng)全局事務(wù)無提交環(huán)存在進(jìn)一步與其他全局事務(wù)判斷執(zhí)行沖突時(shí)，如果有沖突存在就不能繼續(xù)提交，實(shí)際上如果該事務(wù)的讀寫操作是先執(zhí)行的即使產(chǎn)生沖突也是可以提交的，可以看出這種全局事務(wù)提交時(shí)才進(jìn)行沖突檢測(cè)的方式并沒有保證其執(zhí)行的沖突可串行化，同時(shí)這種讓雖然有沖突但可能無死鎖的全局事務(wù)也進(jìn)入了等待隊(duì)列的方式也進(jìn)一步降低了并行度。因此算法TM2的先提交再?zèng)_突檢測(cè)的方式可以進(jìn)一步改進(jìn)。我們首先稍修改一下事務(wù)提交圖，圖中全局事務(wù)與執(zhí)行站點(diǎn)的邊建立時(shí)機(jī)由收到提交操作時(shí)建立改進(jìn)為全局事務(wù)在開始執(zhí)行讀寫操作時(shí)就建立，因?yàn)槿质聞?wù)既然開始執(zhí)行了就必然要結(jié)束（要么commit要么abort），其提交或中止操作終歸要在其已經(jīng)進(jìn)行過讀寫操作的站點(diǎn)上執(zhí)行。建議對(duì)算法TM2進(jìn)行改進(jìn)的方法是全局事務(wù)在執(zhí)行時(shí)先進(jìn)行沖突判斷和死鎖檢測(cè)等到提交時(shí)再進(jìn)行提交環(huán)檢測(cè)，如果全局事務(wù)雖然有沖突但不會(huì)產(chǎn)生死鎖，那么仍然繼續(xù)執(zhí)行而不需進(jìn)入等待隊(duì)列，這樣也符合全局事務(wù)執(zhí)行的邏輯，改進(jìn)算法TM3如下：Stepl.當(dāng)事務(wù)管理器（GTM）調(diào)度全局事務(wù)T時(shí)，GTM查找該全局事務(wù)所分i解的子事務(wù)對(duì)應(yīng)的局部站點(diǎn)七上是否與其他未提交的全局事務(wù)t?的子事務(wù)有讀—寫、寫一寫和寫一讀沖突。Step2.如果全局事務(wù)T與全局事務(wù)T之間存在直接沖突但無死鎖，把T,T和對(duì)應(yīng)的執(zhí)行站點(diǎn)組成的臨時(shí)邊＜T，S＞和＜T，S＞加入到提交圖G中同時(shí)把Tikjki發(fā)送到相應(yīng)的局部站點(diǎn)上執(zhí)行，否則全局事務(wù)T就被GTM回滾。iStep3.如果T與T之間沒有直接沖突，就直接發(fā)送到相應(yīng)的局部站點(diǎn)上執(zhí)ij行。Step4.然后GTM當(dāng)收到提交全局事務(wù)T操作時(shí)，如果不在提交圖中，就直接i執(zhí)行提交操作，否則就在圖中檢測(cè)是否與其它全局事務(wù)形成環(huán)，如果提交圖中形成環(huán)，GTM就把該全局事務(wù)T放入事務(wù)提交隊(duì)列中并在圖中刪除與之相連的局部站i點(diǎn)的邊。Step5.如果提交圖中不包含環(huán)，全局事務(wù)繼續(xù)發(fā)送到對(duì)應(yīng)的局部站點(diǎn)上去執(zhí)行，加入提交圖中的臨時(shí)邊就變成永久邊。Step6.如果在某站點(diǎn)S上，在GTM決定提交全局事務(wù)T后而子事務(wù)T卻被kiik本地?cái)?shù)據(jù)庫中止時(shí)，那么每個(gè)讀過被子事務(wù)Tkk寫過的數(shù)據(jù)的全局事務(wù)T.也必須中止。然后代理Server在站點(diǎn)S^上就重做（redo）該子事務(wù)T的寫操作直到重做事務(wù)在站點(diǎn)sk上提交。而且每當(dāng)重做事務(wù)在站點(diǎn)sk被中止時(shí)，對(duì)于每個(gè)與子事務(wù)T^有數(shù)據(jù)依賴且未提交的全局事務(wù)T也都要被中止。Step7.對(duì)于在所有本地站點(diǎn)上已完成提交操作或中止的全局事務(wù)T，GTM刪i除提交圖中結(jié)點(diǎn)T同時(shí)也刪除T.所附帶的邊。Step8.當(dāng)全局事務(wù)從提交圖中被刪除相連的邊后或全局事務(wù)在完成提交或中止后，GTM取出事務(wù)提交隊(duì)列中的其他全局事務(wù)T使用步驟4和5在提交圖中檢i查提交操作能否繼續(xù)提交。由改進(jìn)后的算法TM3可知，事務(wù)提交圖中的邊是全局事務(wù)正在站點(diǎn)上執(zhí)行且還未提交的邊，而這些邊只有產(chǎn)生沖突時(shí)才被加入到提交圖中，因?yàn)橹挥袥_突的全局事務(wù)在提交時(shí)形成的提交環(huán)才需要處理，而無沖突的全局事務(wù)不出現(xiàn)在提交圖中，因此提高了無沖突全局事務(wù)執(zhí)行的并發(fā)度，并且也保證了全局事務(wù)提交的順序及狀態(tài)。此外，改進(jìn)的算法TM3還克服了算法TM2直到提交時(shí)才進(jìn)行沖突檢測(cè)的缺點(diǎn)，算法TM3中全局事務(wù)首先在執(zhí)行時(shí)就進(jìn)行沖突檢測(cè)，這樣就能按照事務(wù)執(zhí)行次序及時(shí)判斷沖突，而不會(huì)引起全局事務(wù)執(zhí)行混亂，從而保證了全局事務(wù)執(zhí)行的沖突可串行化。因此經(jīng)過改進(jìn)的事務(wù)管理算法TM3讓無沖突的全局事務(wù)并行執(zhí)行，提高了全局事務(wù)的并行度，同時(shí)也保證了全局事務(wù)執(zhí)行的沖突可串行化。下面將在全局事務(wù)管理器中通過實(shí)驗(yàn)對(duì)比改進(jìn)事務(wù)管理算法TM3與事務(wù)調(diào)度算法TM2的全局事務(wù)處理性能。5TPC-C測(cè)試及性能比較5.1TPC-C基準(zhǔn)測(cè)試及實(shí)驗(yàn)平臺(tái)（1）TPC-C測(cè)試簡(jiǎn)介TPC-C性能基準(zhǔn)測(cè)試［40,是目前國(guó)際上公認(rèn)的廣泛應(yīng)用于數(shù)據(jù)庫聯(lián)機(jī)事務(wù)處理及其相關(guān)硬件的性能測(cè)試軟件。TPC-C測(cè)試的模式由九張基表所組成，其中七張的主關(guān)鍵字包含倉(cāng)庫號(hào)，它模擬了現(xiàn)實(shí)世界里一個(gè)批發(fā)商業(yè)活動(dòng)，批發(fā)公司擁有許多倉(cāng)庫，每個(gè)倉(cāng)庫（warehouse）含有10個(gè)分店（district）和有100K（1K=1000）個(gè)貨架（stock），每個(gè)貨架上放一類商品（item），每個(gè)分店為3K個(gè)顧客（customer）提供服務(wù)。顧客訂貨產(chǎn)生訂單（orders）和新訂單（new_order），訂單所涉及的每一類貨物均對(duì)應(yīng)訂單明細(xì)表（order_line）中的一項(xiàng)，已發(fā)貨的訂單記錄在歷史訂單（history）中。在TPC-C測(cè)試運(yùn)行過程中有五種事務(wù)類型，其中包括三個(gè)更新事務(wù)：訂貨（new_order）、付款（payment）、發(fā)貨（delivery）；兩個(gè)查詢事務(wù)：訂單（order_status）查詢和庫存（stock_level）查詢，這五種事務(wù)組成了一個(gè)完整的商業(yè)處理過程。這些事務(wù)按規(guī)定的比例運(yùn)行，按照規(guī)定的時(shí)間延時(shí)，按照規(guī)定的方法產(chǎn)生隨機(jī)數(shù)據(jù)：訂貨-插入新的客戶訂單，45%；付款-更新帳目，43%；發(fā)貨-批量處理，4%；查詢訂單-查詢訂單狀態(tài)4%；查詢庫存-查詢倉(cāng)庫庫存，4%；并且事務(wù)的比率和負(fù)載的混合都不會(huì)隨著系統(tǒng)的負(fù)載和響應(yīng)時(shí)間的增大而改變。TPC-C報(bào)告的性能度量是一個(gè)“商業(yè)吞吐量”，吞吐量（MQTh）的度量是每分鐘處理的訂單數(shù)量，用tpmC表示。基準(zhǔn)測(cè)試的目的是測(cè)量仿真用戶經(jīng)歷的響應(yīng)時(shí)間，其有效性要求90%的事務(wù)要求響應(yīng)時(shí)間控制在5秒以內(nèi)，而庫存查詢要求低一些，響應(yīng)時(shí)間控制在20秒以內(nèi)。此外，運(yùn)行基準(zhǔn)測(cè)試的被測(cè)系統(tǒng)還必須支持事務(wù)所具備的ACID(Atomicity-原子性，Consistency-一致性，Isolation-隔離性,Durability-持久性)基本特性。本文使用TPC-C作為客戶端工具模擬多個(gè)終端用戶的并發(fā)事務(wù)的訪問，測(cè)試多數(shù)據(jù)庫系統(tǒng)中全局事務(wù)管理器的并發(fā)控制性能和衡量事務(wù)處理的最大吞吐量。(2)實(shí)驗(yàn)平臺(tái)搭建為了在多數(shù)據(jù)庫的全局事務(wù)管理器中實(shí)現(xiàn)謂詞級(jí)的多粒度并發(fā)控制和保證全局事務(wù)的一致性和正確性，我們使用五臺(tái)機(jī)器建立一個(gè)三層結(jié)構(gòu)的試驗(yàn)框架：下層是局部數(shù)據(jù)庫站點(diǎn)，中間層為多數(shù)據(jù)庫的全局事務(wù)管理器，通過ODBC標(biāo)準(zhǔn)接口與下層各個(gè)局部數(shù)據(jù)庫連接，然后上層是TPC-C客戶端測(cè)試工具，也通過ODBC或JDBC等接口與中間層的全局事務(wù)管理器連接，這個(gè)測(cè)試框架中的機(jī)器配置如下：客戶端的一臺(tái)機(jī)器采用CII1.0G的CPU和128M內(nèi)存，多數(shù)據(jù)庫系統(tǒng)的全局事務(wù)管理器在一臺(tái)配置較好的機(jī)器上運(yùn)行，其配置為PIV2.0G的CPU，512M內(nèi)存和40G硬盤，三臺(tái)數(shù)據(jù)庫服務(wù)器都采用PIV1.6G的CPU，256M內(nèi)存和40G硬盤。這五臺(tái)機(jī)器組成一個(gè)小型局域網(wǎng)，每臺(tái)機(jī)器上有10M/100M自適應(yīng)網(wǎng)卡，通過快速以太網(wǎng)交換機(jī)進(jìn)行通信。軟件環(huán)境配置為：客戶端機(jī)器上運(yùn)行Windows98操作系統(tǒng)和TPC-C測(cè)試工具模擬多個(gè)并發(fā)用戶，采用ODBC標(biāo)準(zhǔn)數(shù)據(jù)源連接多數(shù)據(jù)庫的全局事務(wù)管理器，數(shù)據(jù)庫服務(wù)器運(yùn)行Windows2000操作系統(tǒng)，然后安裝Microsoft的SQLServer2000數(shù)據(jù)庫或其它異構(gòu)數(shù)據(jù)庫，全局事務(wù)管理器也通過ODBC與底層數(shù)據(jù)庫連接，整個(gè)系統(tǒng)的測(cè)試架構(gòu)如下圖13所示：圖13多數(shù)據(jù)庫GTM測(cè)試框架

下面將采用TPC-C模擬并發(fā)用戶測(cè)試比較GTM的全局事務(wù)多粒度并發(fā)控制效率和事務(wù)提交改進(jìn)算法的性能。5.2測(cè)試性能比較5.2.1謂詞級(jí)與表級(jí)多粒度并發(fā)控制比較我們?cè)诙鄶?shù)據(jù)庫的事務(wù)管理器中實(shí)現(xiàn)并發(fā)事務(wù)在表級(jí)和謂詞級(jí)粒度的對(duì)比測(cè)試，首先分別在三個(gè)站點(diǎn)S1，S2，S3上安裝SQLServer2000數(shù)據(jù)庫服務(wù)器，然后用TPC-C客戶端工具向每個(gè)站點(diǎn)上裝載一個(gè)倉(cāng)庫，模擬現(xiàn)實(shí)世界里一個(gè)批發(fā)商業(yè)活動(dòng)，其每個(gè)倉(cāng)庫大約包含60萬條記錄占用100M磁盤空間，在TPC-C客戶端虛擬450個(gè)并發(fā)用戶共享15個(gè)連接池通過全局事務(wù)管理器對(duì)三個(gè)站點(diǎn)上的倉(cāng)庫進(jìn)行并發(fā)操作，測(cè)試兩種粒度的并發(fā)控制當(dāng)所有并發(fā)用戶負(fù)載都加載到多數(shù)據(jù)庫系統(tǒng)上時(shí)（運(yùn)行600秒）的實(shí)驗(yàn)結(jié)果。這里全局事務(wù)管理器提供兩種方式為表級(jí)和謂詞級(jí)多粒度的死鎖檢測(cè)提供對(duì)比測(cè)試平臺(tái)，經(jīng)過多次試驗(yàn)統(tǒng)計(jì)其結(jié)果如表1和表2所示。表1表級(jí)粒度死鎖檢測(cè)表2謂詞級(jí)粒度死鎖檢測(cè)試驗(yàn)次數(shù)試驗(yàn)次數(shù)總提交事務(wù)數(shù)總回滾事務(wù)數(shù)事務(wù)回滾61%26985302843.35%37211327445.40%47339350947.81%57224324044.85%67309309342.31%77150304342.55%87138314944.11%試驗(yàn)次數(shù)總提交事務(wù)數(shù)總回滾事務(wù)數(shù)事務(wù)回滾53%27503176823.56%37512199826.59%47519190825.37%57592182624.05%67235191426.45%77607193025.37%87173166923.26%全局事務(wù)管理器分別在表級(jí)和謂詞級(jí)粒度檢測(cè)到并發(fā)全局事務(wù)死鎖后都要回滾該事務(wù)，由表1，表2的8次實(shí)驗(yàn)結(jié)果對(duì)比可知，表級(jí)并發(fā)控制的粒度比謂詞級(jí)大，可能產(chǎn)生的直接或間接沖突也比較多，形成死鎖的幾率也就大，因而體現(xiàn)在事務(wù)的回滾率r（r=Tr/Tc）上，Tr表示總回滾事務(wù)數(shù)，Tc表示總提交事務(wù)數(shù)。表級(jí)粒度的平均］是38.96%,而謂詞級(jí)的［則平均為25.15%。由此可見，在相同的用戶負(fù)載下運(yùn)行相同時(shí)間后者（謂詞級(jí)粒度）成功執(zhí)行和提交的事務(wù)數(shù)量較多，成功提交的事務(wù)數(shù)=總提交事務(wù)數(shù)一總回滾事務(wù)數(shù)，而表級(jí)并發(fā)控制的粒度較粗從而也導(dǎo)致沖突和死鎖較多，成功提交的有效事務(wù)較少所做的無用工作較多，也占用了大量系統(tǒng)處理時(shí)間，所以謂詞級(jí)多粒度控制的事務(wù)并發(fā)度比表級(jí)有了較大的提高。通過以上試驗(yàn)可以看出，我們?cè)诙鄶?shù)據(jù)庫的全局事務(wù)管理器中解決了檢測(cè)全局事務(wù)由直接沖突和間接沖突可能產(chǎn)生死鎖的方法，全局事務(wù)管理器對(duì)SQL語句中的DML操作采用謂詞技術(shù)進(jìn)行沖突判斷從而生成謂詞沖突圖進(jìn)行死鎖檢測(cè)而不需具體的上鎖操作，使并發(fā)控制粒度達(dá)到謂詞級(jí)。多數(shù)據(jù)庫系統(tǒng)在保持局部站點(diǎn)數(shù)據(jù)庫自治性的條件下，提高了全局事務(wù)執(zhí)行的并行度。5.2.2事務(wù)提交圖改進(jìn)算法性能測(cè)試上文提到的算法TM2中全局事務(wù)在提交時(shí)才加入到提交圖中檢測(cè)環(huán)是否存在，雖然保證了全局事務(wù)提交順序的全局可串行化，但其在提交時(shí)才進(jìn)行沖突檢測(cè)方式?jīng)]有保證全局事務(wù)執(zhí)行的沖突可串行化，同時(shí)還降低了事務(wù)執(zhí)行的并行度，而改進(jìn)后的算法TM3在全局事務(wù)執(zhí)行時(shí)先進(jìn)行沖突判斷然后等到提交時(shí)才在提交圖中檢測(cè)提交環(huán)，不僅保證了全局事務(wù)提交順序的全局可串行化，而且還提高了無沖突事務(wù)提交的并行度。這種先進(jìn)行沖突判斷然后再檢測(cè)提交環(huán)的方式，不僅符合事務(wù)執(zhí)行的邏輯，而且還保證了全局事務(wù)的執(zhí)行的沖突可串行化。為了比較事務(wù)提交圖算法TM2和改進(jìn)算法TM3的性能，我們采用以上框架用TPC-C性能基準(zhǔn)測(cè)試做客戶端模擬450個(gè)用戶的并發(fā)事務(wù)，比較多數(shù)據(jù)庫的全局事務(wù)管理器中的兩種事務(wù)提交圖算法在同樣的并發(fā)控制粒度下，事務(wù)處理的吞吐量（MQTh）。

圖14提交圖算法TM2的吞吐率圖15改進(jìn)算法TM3的吞吐率圖中縱坐標(biāo)MQTh表示最大可信吞吐率，橫坐標(biāo)表示時(shí)間以秒為單位，由以上測(cè)試結(jié)果可知，算法TM2的最大吞吐量為386,而經(jīng)過改進(jìn)的算法TM3有了較大的提高達(dá)到466，當(dāng)所有并發(fā)用戶負(fù)載加到全局事務(wù)管理器中時(shí)，算法TM3表現(xiàn)比較穩(wěn)定，而算法TM2隨著并發(fā)用戶的增加吞吐量有下降趨勢(shì)，因此在運(yùn)行相同時(shí)間（603秒）的情況下算法TM2總提交事務(wù)數(shù)比算法TM3少，實(shí)際結(jié)果是算法TM2總提交事務(wù)6989個(gè)，而算法TM3總提交事務(wù)達(dá)到7517個(gè)，另外兩種事務(wù)管理算法處理沖突和提交順序的方式也影響了全局事務(wù)執(zhí)行的并發(fā)度，算法TM2的全局事務(wù)回滾率達(dá)到17.81%，而改進(jìn)的算法TM3不僅讓盡管有沖突但無死鎖的全局事務(wù)繼續(xù)并發(fā)執(zhí)行，而且讓無沖突的并發(fā)全局事務(wù)間不必保證事務(wù)的提交順序，所以算法TM3的回滾率只有7.15%，由此可得出算法TM2成功提交的事務(wù)量也較算法TM3少。從以上試驗(yàn)結(jié)果可知，改進(jìn)算法TM3在全局事務(wù)沖突和提交控制方面的處理效率比算法TM2有了較大的提高。6結(jié)論及展望本文所做的主要工作是針對(duì)目前國(guó)內(nèi)外多數(shù)據(jù)庫系統(tǒng)的研究概況，設(shè)計(jì)了多數(shù)據(jù)庫系統(tǒng)的核心部件全局事務(wù)管理器，在全局事務(wù)管理器中調(diào)度全局事務(wù)的子事務(wù)在多個(gè)站點(diǎn)上執(zhí)行時(shí)由于資源競(jìng)爭(zhēng)會(huì)產(chǎn)生沖突以及死鎖，而局部站點(diǎn)數(shù)據(jù)庫的自治性使其只能控制子事務(wù)的并發(fā)執(zhí)行而無法保證全局事務(wù)的沖突可串行化和全局事務(wù)提交順序的一致性，此外事務(wù)管理器還必須負(fù)責(zé)對(duì)全局事務(wù)進(jìn)行死鎖檢測(cè)，因此本文提出了在全局事務(wù)管理器中實(shí)現(xiàn)謂詞級(jí)多粒度的并發(fā)控制方式，并通過檢測(cè)謂詞沖突圖中是否存在環(huán)來判斷全局事務(wù)間的死鎖，這種多粒度的并發(fā)控制有效提高了全局事務(wù)執(zhí)行的并發(fā)度。我們還研究了的多數(shù)據(jù)庫中全局事務(wù)調(diào)度管理算法，針對(duì)事務(wù)管理算法TM2在提交時(shí)才進(jìn)行沖突檢測(cè)方式不僅沒有保證全局事務(wù)執(zhí)行的沖突可串行化，同時(shí)還降低了事務(wù)執(zhí)行的并行度的缺點(diǎn)，提出了改進(jìn)的事務(wù)提交圖管理算法保證了全局事務(wù)提交的順序一致性，還實(shí)現(xiàn)了并發(fā)全局事務(wù)執(zhí)行的沖突可串行化。實(shí)驗(yàn)證明多數(shù)據(jù)庫的全局事務(wù)管理器中的謂詞級(jí)多粒度并發(fā)控制和改進(jìn)的事務(wù)提交圖算法都有效提高了全局事務(wù)處理的并發(fā)度，增大了全局事務(wù)吞吐量，同時(shí)也提高了多數(shù)據(jù)庫系統(tǒng)的全局事務(wù)處理性能。目前在多數(shù)據(jù)庫的全局事務(wù)管理器中只解決了簡(jiǎn)單謂詞常項(xiàng)及變項(xiàng)以及關(guān)系條件的范圍提取技術(shù)，對(duì)于復(fù)雜的謂詞如嵌套結(jié)構(gòu)的謂詞提取比較困難，將來需要做進(jìn)一步的討論，使之滿足更加廣泛的SQL92或SQL93標(biāo)準(zhǔn)。此外，事務(wù)恢復(fù)管理器也是全局事務(wù)管理器中的一個(gè)重要部件，雖然本文側(cè)重全局事務(wù)管理器的設(shè)計(jì)和并發(fā)控制方面的研究，但全局事務(wù)的恢復(fù)也是保證全局事務(wù)執(zhí)行的原子性和多數(shù)據(jù)庫一致性狀態(tài)的重要工作，這是我們需要進(jìn)一步解決的難題。同時(shí)我們對(duì)全局事務(wù)管理器中的查詢優(yōu)化和結(jié)果集成技術(shù)研究也比較少，這是多數(shù)據(jù)庫系統(tǒng)的一個(gè)研究發(fā)展方向。參考文獻(xiàn)：G.B.Rothnie,P.A.Bernstein,S.Fox,N.Goodman,etal.Introductiontoasystemfordistributeddatabases(SDD-1).ACMTrans.DatabaseSyst.5,1,March1980,1-17I.L.Traiger,J.Gray,C.Galtieri,andB.G.Lindsay.Transactionsandconsistencyindistributeddatabasesystems.ACMTrans.DatabaseSyst.7,3Sept1982,323-343Y.Breitbart,P.L.Olson,andG.R.Thompson.DatabaseIntegrationinaDistributedHeterogeneousDatabaseSystem.InProceedingoftheSecondIEEEConferenceonDataEngineering,1986,LosAngels.M.W.Bright,A.R.Hueson,andS.H.Pakzard.ATaxonomyandCurrentIssuesinMultidatabaseSystems.Computer.vol.26,No.3,1992,50-60LandersT.,andRosenbergR.,AnOverviewofMultidatabase.DistributedDatabaseSystems,EdHSchneider.North-Holland,1982,153-184盧正鼎，李兵，肖衛(wèi)軍,李瑞軒.基于CORBA/XML的多數(shù)據(jù)庫系統(tǒng)研究與實(shí)現(xiàn).計(jì)算機(jī)研究與發(fā)展,April2002,39(4)Y.Breitbart,H.Garcia-Molina,A.Silberschatz.Overviewofmultidatabasetransactionmanagement.InProceedingsofthe1992conferenceoftheCentreforAdvancedStudiesonCollaborativeresearch,November1992KimW.,ChoiI.,andScheevelM.,OnResolvingSchematicHeterogeneityinMultidatabaseSystems.JournalofDistributedandParallelDatabases,1993,1(3)D.Keim,H.Kriegel,andA.Meithsam.Object-OrientedQueryingofExistingRelationalDatabase.LectureNotesinComputerScience720(DEXA’93).1993J.V.Harrison,andJ.V.Dietrich.MaintenanceofMaterializedViewinaDeductiveDatabase:AnUpdatePropagationApproach.InProceedingofthe1992JICISPWorkshoponDeductiveDatabase,1992R.Ahmed,P.D.Smedt,WDu,etal.ThePegasusHeterogeneousMultidatabaseSystem.IEEEComputer,1991,24(12):19-27F.Manola,S.Heiler,D.Georgakopoulos,etal.DistributedObjectManagement.InternationalJournalofCooperativeInformationSystems,1992,1(1):5-42石祥濱，張斌，王國(guó)仁等.SCOPE/CIMS系統(tǒng)中模式集成的形式化基礎(chǔ).計(jì)算機(jī)學(xué)報(bào)，1998,21(11):1015-1021姚卿達(dá)，何聽，黃曉春等.LNFDBS的查詢優(yōu)化算法及聯(lián)邦條件下的考慮.軟件學(xué)報(bào)，1998,9(6):453—45MudarSarem，李瑞軒，盧正鼎，陳傳波.Panorama多數(shù)據(jù)庫原型系統(tǒng).華中科技大學(xué)學(xué)報(bào).Dec2001,29(12)T.Landers,R.L.Rosenberg.AnOverviewofMultibase.in:H.J.Schneidered.DistributedDataBase.Amsterdam.NorthHolland,1982.391-421V.Gligor,R.Popescu-Zeletin.TransactionManagementinDistributedHeterogeneousDatabaseManagementSystems.InformationSystems,1986,11(4):287-297J.E.B.Moss.NestedTransactions:AnApproachtoReliableDistributedComputing:PhDThesis.Cambridge:MassachusettsInstituteofTechnology,1981P.K.Chrysanthis,K.Ramamritham.SynthesisofExtendedTransactionModelsUsingACTA.ACMTransactionsonDatabaseSystems,1994,19(3):450-491Y.Breitbart,A.Silberschatz,G.R.Thompson.ReliableTransactionManagementinaMultidatabaseSystem.SIGMODRecord,1990,19(2):215-224S.Mehrotra,R.Rastogi,Y.Breitbart,etal.EnsuringTransactionAtomicityinMultidatabaseSystems.inProceedingsoftheEleventhACMSIGACT-SIGMOD-SIGARTSymposiumonPrinciplesofDatabaseSystems.SanDiego.1992.ACMPress.164-175A.Zhang,M.H.Nodine,B.K.Bhargava,etal.EnsuringRelaxedAtomicityforFlexibleTransaction