實時事務正確性(數(shù)據(jù)庫)

時間：2022-11-12 04:30:01 | 來源：信息時代

時間：2022-11-12 04:30:01 來源：信息時代

    實時事務正確性 : 在任何給定時刻,數(shù)據(jù)庫變更的結果狀態(tài)是正確的、時間一致的。換句話說,每一事務都是結果正確的,且滿足時間一致(包括外部和相互一致)性限制。外部一致乃指事務對任一數(shù)據(jù)對象的操作時間都落在該數(shù)據(jù)的外部有效期內(nèi)。實時事務往往要與對應于實時世界對象(RWO)的同一“快照”(snapshot)的多個數(shù)據(jù)對象打交道,這些數(shù)據(jù)必須屬于同一相互一致集,即一個實時事務的讀集是一個相互一致集,必須滿足其相互一致性限制。
1.事務正確性經(jīng)歷模型
一個事件可定義為一種系統(tǒng)行為在一定時刻的瞬時發(fā)生。系統(tǒng)行為可以是數(shù)據(jù)庫的各種操作、事務管理活動、時間行為或與外部環(huán)境的交互活動等。故可以有各種類型的事件:①對象事件:一個(數(shù)據(jù))對象的一種操作的執(zhí)行; ②事務事件: 一個事務管理原語的執(zhí)行; ③時間事件: 一個時限管理原語的執(zhí)行; ④外部事件: 與外部環(huán)境的交互活動。
一個相關事件的集合所構成的關于其發(fā)生順序關系的偏序集稱為一事件經(jīng)歷。令E表示一事件集,<_s表示其中事件發(fā)生的順序關系,H表示事件經(jīng)歷,則H=<E, 。
與一個事務t相聯(lián)的所有事件的事件經(jīng)歷稱為該事務的經(jīng)歷,記為H_t:H_t＝<E_t,<_s>。其中,E_t為與事務t相聯(lián)的事件集,<_s為t中各事件發(fā)生的順序關系。
設T為一組事務,與T中各事務相聯(lián)的所有事件的事件經(jīng)歷稱為T的并發(fā)執(zhí)行經(jīng)歷,記為H_T:H_T＝<E_T,<_T>。其中,E_T為T中各事務相聯(lián)的所有事件集合,<_T為T中事件發(fā)生的順序關系。
每一數(shù)據(jù)操作總產(chǎn)生一個結果輸出和一個結果狀態(tài),它們都與對象的當初狀態(tài)相關。以R(s,p)和S(s,p)分別表示在當初狀態(tài)s下數(shù)據(jù)操作p產(chǎn)生的結果輸出和結果狀態(tài)。
設p、q是兩個數(shù)據(jù)操作,稱它們是沖突的,記為CT(p,q),當且僅當S(S(s,p),q)≠S(S(s,q),p)∨R(s,q)≠R(S(s,p),q)∨R(s,p)≠R(S(s,q),p)。
其中,對象的當初狀態(tài)s其實可以省掉。所以,兩個操作是沖突的,就是將它們施加于一個數(shù)據(jù)的最終結果(輸出和狀態(tài))依賴其執(zhí)行順序。若兩個事務分別包含了兩個沖突的操作,則說明它們有(二元)沖突關系。更準確地,對于經(jīng)歷H_T的任兩個事務t_i、t_j, t_i≠t_j, 若∃p∈t_i, q∈t_j,(CT(p, q)∧(p<_Tq)), 則說事務t_j對t_i有一個沖突關系。記為t_jCRt_i。
2. 事務正確性內(nèi)容及其說明
RTDB事務之間存在著結構、行為及時間上的相關性,因而其正確性也要包含這些方面。
(1)結果正確性:除了結果狀態(tài)正確外,由于時間一致性限制的關系,對事務結果正確性還引入了“正確性程度”的概念。依此,結果正確性可分為:①絕對正確:事務的結果反映了正確的數(shù)據(jù)庫狀態(tài);②相對正確: 事務的結果不具絕對正確性,但在正確結果狀態(tài)的允許偏差范圍之內(nèi)。
(2)行為正確性:指有關對象事件的發(fā)生及所涉及對象的行為限制的滿足。它涉及到系統(tǒng)控制(如并發(fā)、一致性控制)以便產(chǎn)生正確經(jīng)歷,以及可能需要的額外處理(如隔離度、提交限制的實現(xiàn)),分別稱為行為沖突與行為模式處理。
(3)結構正確性:指復雜事務內(nèi)部及事務之間的結構依賴性的實現(xiàn)。各種事務模型的結構正確性由相應的結構依賴關系來表示。結構依賴性是復雜事務特有的一種行為特性。
(4)時間正確性:指事務事件發(fā)生時間的正確性及彼此之間依賴性的滿足。
各種正確性都可以基于經(jīng)歷模型來準確說明。例如,“事務集T的并發(fā)經(jīng)歷H_T是可串行化的”可說明為: 當且僅當∀t∈T(tCR*t) (CR*為CR的傳遞閉包)。
3. 正確性準則
事務的正確性準則是事務處理的若干個不能違反的限制,或必需滿足的條件。對RTDB而言,包括內(nèi)部一致性、外部一致與相互一致性限制。
可串行性是維持傳統(tǒng)數(shù)據(jù)庫內(nèi)部一致性的正確性準則。但對于非傳統(tǒng)應用,它表現(xiàn)出了不同的局限性: ①太強: 例如對連續(xù)變更的大量數(shù)據(jù)的統(tǒng)計應用和只讀事務,可以接受具有一定的不一致性的近似值。且外部一致性和相互一致性限制本身就意味著可容納一定的不一致性或相似度。②不可能:例如對于那些具有循環(huán)、長壽(longlife)或開端(openend)活動的應用。③不合適:例如對于那些要彼此交互、通信、協(xié)調的合作計算的應用; ④不正確: 例如對于包含復雜對象(如B-樹)上的各種操作的層次事務、嵌套事務。
這些情況在實時應用環(huán)境中是常見的,因而人們開發(fā)了各種RTDB的正確性準則,如ε-可串行性、Δ-可串行性、準一致性可串行性等。它們都對經(jīng)典的可串行性限制有不同程度的放松,通過臨時犧牲某個很小程度的數(shù)據(jù)庫一致性,可獲得更多實時事務定時限制的滿足。