（計(jì)算機(jī)軟件與理論專業(yè)論文）時(shí)態(tài)xml文檔更新的一致性檢查及處理.pdf

時(shí)態(tài)x m l 文檔更新的一。致性檢查及處理( 2 0 1 0 )摘要 時(shí)態(tài)x m l 文檔更新的一致性檢查及處理 專業(yè)：計(jì)算機(jī)軟件與理論專業(yè) 碩士生：石磐 指導(dǎo)老師：湯庸教授 湯娜講師 摘要 隨著時(shí)態(tài)信息處理技術(shù)和互聯(lián)網(wǎng)應(yīng)用的廣泛深入，為了更方便地反映現(xiàn)實(shí)世 界的時(shí)態(tài)數(shù)據(jù)，實(shí)現(xiàn)不同網(wǎng)絡(luò)環(huán)境之間的信息共享和數(shù)據(jù)交換，時(shí)態(tài)x m l 的研 究已成為當(dāng)今的一個(gè)研究熱點(diǎn)。目前對時(shí)態(tài)x m l 研究主要集中在時(shí)態(tài)x m l 索 引、查詢優(yōu)化等方面，對時(shí)態(tài)x m l 文檔的一致性約束研究相對較少。 時(shí)態(tài)x m l 的一致性作為規(guī)范時(shí)態(tài)v i l 的重要約束條件，如何更有效地保 證時(shí)態(tài)x m l 滿足現(xiàn)實(shí)世界的時(shí)態(tài)語義約束成為時(shí)態(tài)x m l 一致性研究首先要解 決的問題。盡管國內(nèi)外對時(shí)態(tài)x m l 一致性取得了一些研究成果，但很多研究都是 對時(shí)態(tài)x m l 進(jìn)行致性的全文檢查，它們忽略了更新操作所帶來的新的一致性 沖突，從而出現(xiàn)一致性的重復(fù)檢查和修復(fù)，在一定程度上影響了更新操作的執(zhí)行 效率。 針對當(dāng)前時(shí)態(tài)x m l 一致性研究的不足，本文借鑒了傳統(tǒng)x m l 一致性約束 增量檢查的研究思想，將其運(yùn)用到時(shí)態(tài)x m l 更新的一致性檢查和處理上。本文 首先給出了一個(gè)時(shí)態(tài)x m l 數(shù)據(jù)模型，在此模型的基礎(chǔ)上，分別定義了基于 s c h e m a 的傳統(tǒng)x m l 一致性和時(shí)態(tài)x m l 致性約束，從這兩方面進(jìn)行一致性增 量檢查的研究：一方面是基于s c h e m a 模式驗(yàn)證進(jìn)行一致性的增量檢查；另一方 面，從時(shí)態(tài)約束性的角度對四種不同的時(shí)態(tài)x m l 一致性進(jìn)行增量檢查。進(jìn)而將 時(shí)態(tài)x m l 更新操作與一致性增量檢查和修復(fù)相結(jié)合，并給出了滿足時(shí)態(tài)x m l 一致性的增量更新算法，進(jìn)一步對時(shí)態(tài)x m l 更新查詢語句t x p a t h 進(jìn)行一致性 檢查和修復(fù)的語義擴(kuò)展。 最后，本文通過仿真實(shí)驗(yàn)，對時(shí)態(tài)x m l 致性增量檢查算法以及滿足時(shí)態(tài) 時(shí)態(tài)x m l 文檔更新的一致性檢查及處理( 2 0 1 0 ) 摘要 x m l 一致性的增量更新算法進(jìn)行實(shí)驗(yàn)驗(yàn)證，通過實(shí)驗(yàn)比較和對算法性能的分析， 本文所提出的算法具一定的可行性和靈活性。同時(shí)保證在更新之前就發(fā)現(xiàn)一致性 的沖突并及時(shí)修復(fù)，避免了更新后的重復(fù)檢查和修復(fù)，提高了時(shí)態(tài)x m l 更新操 作的執(zhí)行效率。 關(guān)鍵詞：時(shí)態(tài)x m l ，一致性約束，增量檢查，時(shí)態(tài)x m l 更新，t x p a t h 擴(kuò)展 i i 時(shí)態(tài)x m l 文檔更新的一致性檢查及處理( 2 0 1 0 )a b s t r a c t c h e c k i n ga n df i x i n go fc o n s i s t e n c yw h e nt e m p o r a l x m ld o c u m e n t u p d a t e d m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：s h ip a n s u p e r v i s o r ：p r o f e s s o rt a n gy o n g l e c t u r e rt a n gn a a b s t r a c t w i t ht h ed e v e l o p m e n to ft h et e c h n o l o g yo ft e m p o r a li n f o r m a t i o np r o c e s s i n ga n d t h ea p p l i c a t i o no fi n t e m e t ，t h es h a r i n ga n de x c h a n g i n go ft e m p o r a ld a t ah a sb e c o m e m o r ea n dm o r ep o p u l a r i no r d e rt or e f l e c tt e m p o r a ld a t ai nt h er e a lw o r l d c o n v e n i e n t l ya n di m p l e m e n tt h es h a r i n go fi n f o r m a t i o nb e t w e e nd i f f e r e n tn e t w o r k e n v i r o n m e n t s ，t h er e s e a r c ho nt e m p o r a lx m lh a sb e e nb e c o m i n gt h eh i ts p o t t h e r e s e a r c ho nt e m p o r a lx m lf o c u sr n a i l yo nt h et e m p o r a lx m li n d e xa n dq u e r y o p t i m i z a t i o n , b u tl i t t l ei sc o n c e r n e d o nt e m p o r a lx m l c o n s i s t e n c y t e m p o r a lx m lc o n s i s t e n c y a sa l li m p o r t a n tc o n s t r a i n to ft e m p o r a lx m l d o c u m e n t ，h o wt oe n s u r et h a tt e m p o r a lx m lc o n f o r mt ot h et e m p o r a ls e m a n t i c c o n s t r a i n t si nt h er e a lw o r l de f f e c t i v e l yh a sb e c o m et h ep r i n c i p a lp r o b l e m a l t h o u g h s o m er e s e a r c ha c h i e v e m e n t sw e r ea t t a i n e do nt e m p o r a lx m lc o n s i s t e n c y , m o s to f t h e mf o c u so nf u l l - t e x tv a l i d a t i o no ft e m p o r a lx m l t l l e yi g n o r et h ec o n f l i c to f t e m p o r a lx m lc o n s i s t e n c yw h e n t h ed o c u m e n tu p d a t e ds ot h a tt h ec o n s i s t e n c yh a st o b ec h e c k e da n df i x e di t e r a t i v e l y , w h i c hw i l li n f l u e n c et h ee x e c u t i n ge f f i c i e n c yt o s o m ee x t e n t w i t hr e s p e c tt ot h ed i s a d v a n t a g e so fc u r r e n tr e s e a r c ho nt e m p o r a lx m l c o n s i s t e n c y , w el e a mt h er e l a t i v e r e s e a r c ho ni n c r e m e n t a l c h e c k i n g o ft h e c o n v e n t i o n a lx m l c o n s i s t e n c yf o rr e f e r e n c ea n da p p l yt ot h em e t h o do nt h ec h e c k i n g a n df i x i n gw h e nt e m p o r a lx m l u p d a t e d i nt h i sp a p e r , w ep r o p o s eat e m p o r a lx m l 1 1 1 時(shí)態(tài)x m l 文檔更新的一致性檢查及處理( 2 0 1 0 ) a b s t r a c t d a t am o d e la tf i r s t o nt h eb a s i so ft h em o d e l ，w ep r o p o s et h ed e f i n i t i o no nt h e c o n s i g e n c yo ft r a d i t i o n a lx m lb a s e ds c h e m aa n dt e m p o r a l x m ld o c u m e n t s e p a r a t e l y t h e n ，w eg i v et h ea l g o r i t h m so fi n c r e m e n t a lc h e c k i n gr e f e r e dt od i f f e r e n t k i n d so ft e m p o r a lx m l c o n s i s t e n c yi ti sd i s c u s s e df r o mt w oa s p e c t s ：o n ec h e c k i n gi s b a s e do ns c h e m av a l i d a t i o n ，t h eo t h e rc h e c k i n gf o c u s e so nt h et e m p o r a lc o n s t r a i n t s n e x t ，w ed i s c u s st h et e m p o r a lx m lu p d a t i n ga l g o r i t h m so nc o n d i t i o nt h a tn o u p d a t i n go p e r a t i o n w o u l dv i o l a t et h e t e m p o r a lc o n s i s t e n c y w ee x p a n dt h e i n c r e m e n t a lc h e c k i n ga n df i x i n go fc o n s i s t e n c yi n t ot h et e m p o r a lx m lu p d a t i n g o p e r a t i o na n de x t e n dt h es e m a n t e m eo ft x p a t hq u e r yl a n g u a g e a tl a s t ，p r e l i m i n a r ye x p e r i m e n t sa n da n a l y s i so fo u ra l o g r i t h m ss h o wt h a tt h e r e s e a r c ho nc h e c k i n ga n df i x i n go fc o n s i s t e n c yw h e nt e m p o r a lx m ld o c u m e n t u p d a t e di sn o to n l yf e a s i b l eb u ta l s of l e x i b l e a tt h es a m et i m e ，o u rm e t h o d sw i l l a s s u r et h a tt h ec o n f l i c to ft e m p o r a lx m l c o n s i s t e n c yc a nb ed e t e c t e db e f o r eu p d a t i n g a n db ef i x e di nt i m e ，w h i c hw i l la v o i dc h e c k i n ga n df i x i n gi t e r a t i v e l ya f t e ru p d a t e d a n di m p r o v et h ee x e c u t i n ge f f i c i e n c yo ft e m p o r a lx m lu p d a t i n go p e r a t i o n k e y w o r d s ：t e m p o r a lx m l ，t e m p o r a lc o n s i s t e n c y , i n c r e m e n t a lc h e c k i n go f c o n s i s t e n c y , u p d a t i n go ft e m p o r a lx m l ，t x p a t he x p a n d i n g i v 本人鄭重聲明： 論文原創(chuàng)性聲明 所呈交的學(xué)位論文，是本人在導(dǎo)師的指導(dǎo)下，獨(dú)立進(jìn)行研究工作所取得的成 果。除文中已經(jīng)注明引用的內(nèi)容外，本論文不包含任何其他個(gè)人或集體已經(jīng)發(fā)表 或撰寫過的作品成果。對本文的研究作出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以 明確方式標(biāo)明。本人完全意識到本聲明的法律結(jié)果由本人承擔(dān)。 敝作者虢乃鋤 日期：p 1 一年y 曩) 日 學(xué)位論文使用授權(quán)聲明 本人完全了解中山大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，即：學(xué)校有權(quán)保留 學(xué)位論文并向國家主管部門或其指定機(jī)構(gòu)送交論文的電子版和紙質(zhì)版，有權(quán)將學(xué) 位論文用于非贏利目的的少量復(fù)制并允許論文進(jìn)入學(xué)校圖書館、院系資料室被查 閱，有權(quán)將學(xué)位論文的內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用復(fù)印、縮印或其 他方法保存學(xué)位論文。 學(xué)位論文作者簽名： 日期：鏟l 口年r 月i 日 導(dǎo)師簽名：f 飛力 日期：叫律舌月 日 時(shí)態(tài)x m l 文檔更新的一致性檢查及處理( 2 0 1 0 )第一章引言 第一章引言 近些年來，隨著計(jì)算機(jī)技術(shù)和信息技術(shù)的飛速發(fā)展以及個(gè)人計(jì)算機(jī)和互聯(lián)網(wǎng) 的進(jìn)一步普及，人類進(jìn)入了一個(gè)信息膨脹和數(shù)據(jù)爆炸的時(shí)代。為了方便處理人們 現(xiàn)實(shí)生活中日益復(fù)雜的數(shù)據(jù)，數(shù)據(jù)庫與信息系統(tǒng)面臨著許多新的應(yīng)用和新的挑 戰(zhàn)。時(shí)間作為自然界客觀存在的物質(zhì)屬性，常常需要反映在實(shí)際的信息系統(tǒng)中， 因此對時(shí)態(tài)信息處理的需求也越來越迫切。時(shí)態(tài)信息處理已成為許多信息系統(tǒng)與 新一代數(shù)據(jù)庫的核心技術(shù)，特別是在數(shù)據(jù)倉庫【7 1 【引、數(shù)據(jù)挖掘【9 】【10 1 、決策支持系 統(tǒng)【1 、電子商務(wù)、電子政務(wù)、計(jì)算機(jī)輔助設(shè)計(jì)【1 2 】【1 3 】等信息系統(tǒng)中扮演著e j 益重 要的角色。 隨著信息共享和數(shù)據(jù)交換的日益頻繁，傳統(tǒng)的關(guān)系數(shù)據(jù)庫在處理數(shù)據(jù)時(shí)也遇 到了瓶頸：首先數(shù)據(jù)庫技術(shù)的實(shí)現(xiàn)是基于數(shù)據(jù)庫管理系統(tǒng)之上的，各種商業(yè)的數(shù) 據(jù)庫管理系統(tǒng)之間差異較大，且它們所依賴操作系統(tǒng)更是風(fēng)格迥異，在一定程度 上限制了數(shù)據(jù)共享和信息交換；另外，數(shù)據(jù)庫技術(shù)對現(xiàn)實(shí)世界的語義描述能力較 差，復(fù)雜的概念模型在異構(gòu)應(yīng)用數(shù)據(jù)交換時(shí)，不利于計(jì)算機(jī)描述現(xiàn)實(shí)語義，進(jìn)行 準(zhǔn)確的數(shù)據(jù)處理和應(yīng)用。x m l 文檔正是為了解決數(shù)據(jù)庫中的這些瓶頸應(yīng)運(yùn)而生 的。 1 1 研究背景 x m l ( e x t e n s i b l em a r k u pl a n g u a g e ，可擴(kuò)展標(biāo)記語言) ，于1 9 9 8 年2 月由 w o r l dw i d ew e bc o n s o r t i u m ( w 3 c ) 工作組提出，它與h t m l 類似，也是一種 基于標(biāo)記的標(biāo)記語言，繼承了s g m l 語言的很多特性，但使用了較為簡單的實(shí) 現(xiàn)技術(shù)。x m l 具有高效可擴(kuò)展性，自描述性，國際化性【4 】等，特別是在數(shù)據(jù)傳 送方面，x m l 使數(shù)據(jù)的傳送獲得真正的獨(dú)立性、跨平臺性【3 】。正如w 3 c 工作組 描述的那樣：“x m l 是s g m l 的子集，其目標(biāo)是允許普通的s g m l 在w e b 上以 目前h t m l 的方式被服務(wù)和處理。它是易于實(shí)現(xiàn)，且可在s g m l 和h t m l 之間 互相操作d , 2 】?！绷硗?，由于其數(shù)據(jù)表示形式靈活，使其更容易地在異構(gòu)環(huán)境下 進(jìn)行數(shù)據(jù)的傳輸與交換。尤其是在互聯(lián)網(wǎng)領(lǐng)域，它將成為異構(gòu)環(huán)境下新一代w e b 應(yīng)用的通用數(shù)據(jù)語言和轉(zhuǎn)換協(xié)議。x m l 作為數(shù)據(jù)訪問領(lǐng)域的最新技術(shù)，x m l 數(shù) 時(shí)態(tài)x m l 文檔更新的一致性檢查及處理( 2 0 1 0 ) 第章引言 據(jù)管理成為當(dāng)前信息系統(tǒng)研究熱點(diǎn)f 5 】f 6 】。 時(shí)態(tài)信息處理技術(shù)伴隨著數(shù)據(jù)庫技術(shù)的產(chǎn)生與發(fā)展，已成為新一代數(shù)據(jù)庫技 術(shù)與信息技術(shù)的重要領(lǐng)域。時(shí)態(tài)數(shù)據(jù)庫領(lǐng)域的權(quán)威學(xué)者a t a n s e l 等人在1 9 9 3 年共 同主編的 t e m p o r a ld a t a b a s e s ：t h e o r y , d e s i g n ，a n di m p l e m e n t a t i o n ) ) 【1 4 】中收集了 此前時(shí)態(tài)數(shù)據(jù)庫幾乎所有的重要研究成果。關(guān)于時(shí)態(tài)信息技術(shù)的起源與發(fā)展我們 大致可分成以下三個(gè)重要時(shí)期：開創(chuàng)性( 1 9 8 2 年以前) 、理論與模型探索階段 ( 1 9 8 3 1 9 9 3 年) 、應(yīng)用與發(fā)展階段( 1 9 9 4 年以來) 1 5 1 。 國內(nèi)外在基于x m l 的時(shí)態(tài)擴(kuò)展的研究都比較活躍，包括建立時(shí)態(tài)x m l 的數(shù) 據(jù)模型【1 6 】，時(shí)態(tài)信息在x m l 文檔中的表示【1 7 】【博1 ，以及時(shí)態(tài)x m l 的存儲1 8 1 【19 1 等方 面都進(jìn)行了深入的研究。中山大學(xué)協(xié)同軟件技術(shù)實(shí)驗(yàn)室時(shí)態(tài)數(shù)據(jù)庫研究小組從 2 0 0 4 年開始對時(shí)態(tài)x m l 進(jìn)行研究，在x m l 時(shí)態(tài)表示、時(shí)態(tài)x m l 數(shù)據(jù)模型、時(shí)態(tài) x m l 查詢、時(shí)態(tài)索引、時(shí)態(tài)更新等方面都取得了比較多的研究成果。本文在這 些研究成果的基礎(chǔ)上，對時(shí)態(tài)x m l 數(shù)據(jù)模型，時(shí)態(tài)信息在x m l 文檔中表示及時(shí) 態(tài)l 一致性約束等更進(jìn)一步研究，擴(kuò)展時(shí)態(tài)x m l 更新操作，對時(shí)態(tài)x m l 更新 進(jìn)行了一致性約束的檢查和修復(fù)，從而保證了時(shí)態(tài)x m l 更新操作滿足時(shí)態(tài)一致 性的約束。 1 2 研究的出發(fā)點(diǎn)及意義 伴隨著人們對時(shí)態(tài)信息處理需求的日益增加，以及互聯(lián)網(wǎng)上異構(gòu)數(shù)據(jù)交換的 日益頻繁，結(jié)合時(shí)態(tài)數(shù)據(jù)庫與x m l 語言的優(yōu)點(diǎn)，研究時(shí)態(tài)x m l 具有理論和現(xiàn) 實(shí)的意義。 一方面，x m l 作為反映現(xiàn)實(shí)世界的數(shù)據(jù)表示，文檔的內(nèi)容與結(jié)構(gòu)隨著時(shí)間 的變化而變化。雖然目前已經(jīng)提出了很多存儲x m l 文件的方法和形式【2 0 l ，但仍 然無法有效存儲對文件一連串修改痕跡，對于x m l 來說，其面臨的版本管理和 實(shí)時(shí)的查詢，驅(qū)動其引入“時(shí)態(tài)”的相關(guān)技術(shù)。 另一方面，隨著時(shí)態(tài)信息處理技術(shù)研究的不斷深入，出現(xiàn)了大量關(guān)于在傳統(tǒng) 關(guān)系數(shù)據(jù)庫中支持“時(shí)態(tài)信息，的研究【2 l 】，例如文獻(xiàn)列舉出多種不同的支持“時(shí) 態(tài)信息”解決方案。針對傳統(tǒng)關(guān)系模型靈活性較差，c l i f f o r d 等人在文獻(xiàn)【2 3 l 中證明 了像x m l 這種支持“非結(jié)構(gòu)化”數(shù)據(jù)的格式，可以很好的支持 t e m p o r a l l yg r o u p e d ” 2 時(shí)態(tài)x m l 文檔更新的致性檢查及處理( 2 0 1 0 )第一4 章引言 數(shù)據(jù)模型；另外和s q l 不同的是，x m l 的查詢語言x q u e r y 2 4 】具有“圖靈完備” 和自身可擴(kuò)展( n a t i v e l ye x t e n s i b l e ) 的特性【2 5 2 6 1 ，這些都為x m l 的時(shí)態(tài)擴(kuò)展提 供了理論的依據(jù)。 本文正是從這兩方面出發(fā)，結(jié)合x m l 和時(shí)態(tài)信息處理近些年的研究成果， 對x m l 進(jìn)行時(shí)態(tài)的擴(kuò)展，提出時(shí)態(tài)x m l 數(shù)據(jù)模型，并在此模型的基礎(chǔ)上研究 了時(shí)態(tài)一致性的約束。但是作為時(shí)態(tài)x m l 數(shù)據(jù)模型的重要約束條件，如何更有 效地保證時(shí)態(tài)x m l 文檔滿足現(xiàn)實(shí)世界的時(shí)態(tài)語義約束成為時(shí)態(tài)x m l 一致性研 究的一個(gè)難點(diǎn)，特別是當(dāng)時(shí)態(tài)x m l 文檔不斷進(jìn)行更新時(shí)，如何保證每次更新操 作不會帶來時(shí)態(tài)x m l 一致性的沖突，如何更高效地進(jìn)行時(shí)態(tài)x m l 文檔一致性 約束的檢查和修復(fù)，這些都成為時(shí)態(tài)x m l 一致性研究必然要解決的問題。 針對現(xiàn)今時(shí)態(tài)x m l 一致性研究的不足，本文改進(jìn)時(shí)態(tài)x m l 文檔更新一致 性檢查算法，提出增量更新以及沖突修復(fù)的算法，避免傳統(tǒng)更新的時(shí)態(tài)x m l 全 文檢查和重復(fù)檢查，不僅提高了時(shí)態(tài)x m l 更新一致性檢查的效率，也改善了一 致性沖突修復(fù)的正確率。 除了在理論方面，時(shí)態(tài)x m l 一致性的研究對于完善x m l 和推動時(shí)態(tài)信息 技術(shù)的發(fā)展都具有重要的意義。在實(shí)際應(yīng)用領(lǐng)域，時(shí)態(tài)x m l 一致性也具有廣闊 的應(yīng)用范圍，諸如電子政務(wù)中處理具有時(shí)效規(guī)范性的政策信息和與時(shí)間約束相關(guān) 的統(tǒng)計(jì)數(shù)據(jù)等，工作流中各種異構(gòu)時(shí)態(tài)數(shù)據(jù)的傳輸與校驗(yàn)，以及數(shù)據(jù)倉庫中進(jìn)行 時(shí)態(tài)數(shù)據(jù)的挖掘，在滿足一定約束條件下進(jìn)行實(shí)時(shí)的決策支持等。 1 3國內(nèi)外研究現(xiàn)狀 1 3 1x m l 的時(shí)態(tài)擴(kuò)展 時(shí)態(tài)信息在x m l 上進(jìn)行擴(kuò)展一般有兩種擴(kuò)展方法，屬性擴(kuò)展法和元素?cái)U(kuò)展 法。c l i f f o r d 對時(shí)態(tài)數(shù)據(jù)模型進(jìn)行分類：t e m p o r a l l yt m g r o u p e d 和t e m p o r a l l y g r o u p e d t 2 3 1 ，從這里最早提出了不同的x m l 時(shí)態(tài)擴(kuò)展方法。在屬性擴(kuò)展法中， f u s h e n gw a n g 將t e m p o r a l l yg r o u p e d 模型引入x m l ，提出了x b i t 數(shù)據(jù)模型2 7 1 ； 在元素?cái)U(kuò)展法中，b e l as t a n t i c 等人利用f e r n a n d e z t 2 8 j 等人的方法進(jìn)行元素?cái)U(kuò)展， 并提出d i r e c t 數(shù)據(jù)模型2 9 。盡管x m l 的時(shí)態(tài)信息擴(kuò)展模型提出很多，且很多模 時(shí)態(tài)x m l 文檔更新的一致性檢查及處理( 2 0 1 0 )第一章引言 型都涉及了定性分析，但在性能上的做定量分析對比的還比較少。 1 3 2 時(shí)態(tài)x m l 數(shù)據(jù)模型 v a i s m a n 等人提出了“版本結(jié)點(diǎn)”的概念，并為每條邊增加一個(gè)“時(shí)態(tài)元素標(biāo) 簽”來記錄有效時(shí)間，將時(shí)態(tài)x m l 模型轉(zhuǎn)化為有向無環(huán)圖【3 0 1 。除此之外，他們還 研究了在映射后的時(shí)態(tài)x m l 文檔中，在任何一個(gè)屬性或元素上添加一個(gè)有效時(shí) 間區(qū)間字符串，簡化了時(shí)態(tài)x m l 文檔的表示。在時(shí)態(tài)查詢上，擴(kuò)充x p a t h 語言， 增加一些“時(shí)態(tài)函數(shù)”( b u i l t i nf u n c t i o n s ) 來實(shí)現(xiàn)時(shí)態(tài)查詢1 3 0 1 。 s z h a n g 和c d y r e s o n 對時(shí)態(tài)x m l 文檔的每個(gè)結(jié)點(diǎn)增加“有效時(shí)間戳”來支 持“有效時(shí)間”；在時(shí)態(tài)信息查詢上則是通過擴(kuò)展x p a t h 語句增加一個(gè)“有效時(shí)間 軸來實(shí)現(xiàn)【3 l 】。 t o s h i y u k ia m a g a s a 等人通過對x p a t h 數(shù)據(jù)模型進(jìn)行擴(kuò)展，增加“有效時(shí)間”的 時(shí)態(tài)標(biāo)簽，建立時(shí)態(tài)x m l 數(shù)據(jù)模型，該數(shù)據(jù)模型將一個(gè)時(shí)態(tài)x m l 文檔表示成一 棵帶有“時(shí)態(tài)邊標(biāo)記( 有效時(shí)間戳) ”的有向樹【3 2 1 。在對該數(shù)據(jù)模型映射成時(shí)態(tài) x m l 文檔方面，他們采用了f u l li m p l e m e n t a t i o n 和s i m p l i f i e di m p l e m e n t a t i o n 兩種 方法進(jìn)行映射。在映射后的時(shí)態(tài)x m l 文檔中，每個(gè)元素都帶有一個(gè)“t i m e ：v a l i d 屬性來描述該元素的有效時(shí)剮3 2 1 。 另外，他們還討論了如何在時(shí)態(tài)關(guān)系數(shù)據(jù)庫中實(shí)現(xiàn)該數(shù)據(jù)模型，并進(jìn)一步將 此模型轉(zhuǎn)化為一個(gè)有向無環(huán)圖，給出了簡單的查詢操作，卻沒有對更新方面進(jìn)行 細(xì)致的討論【3 3 1 。 1 3 3 時(shí)態(tài)x m l 一致性研究 對于傳統(tǒng)的x m l 文檔的一致性研究，很多學(xué)者提出了增量驗(yàn)證x m l 文檔 一致性的模型和方法。其中k a n e 等人提出了x m l 文檔約束規(guī)則的模型，對x m l 更新操作提出了一種約束檢查機(jī)制，保證每次對x m l 文檔的更新都滿足相應(yīng)的 一致性約束1 3 8 】，這種方法主要是通過重寫更新x m l 的查詢語句，實(shí)現(xiàn)增量的檢 查。c h i e n 等人提出利用s c h e m a 模式來記錄更新x m l 文檔的版本信息，對每次 版本的改動進(jìn)行一致性的校驗(yàn)【3 9 】，這種方法由于要維護(hù)s c h e m a 文件，對于致 性的校驗(yàn)開銷較大。 4 時(shí)態(tài)x m l 文檔更新的一致性檢查及處理( 2 0 1 0 )第一章引言 以上大量學(xué)者對一致性的研究基本是基于傳統(tǒng)的x m l 文檔，據(jù)我們掌握的 資料，目前國內(nèi)外對于時(shí)態(tài)x m l 一致性的研究還處于一個(gè)嶄新的階段。其中 f l a v i or i z z o l o 和a a v a i s m a n 在文獻(xiàn)【4 0 】中討論到了有效時(shí)間的時(shí)態(tài)約束問題， 并給出了其定義下時(shí)態(tài)沖突的解決算法。m a r c e l ac a m p o 在這個(gè)的基礎(chǔ)之上，在 文獻(xiàn)】中進(jìn)一步探討將時(shí)態(tài)不一致問題的解決方法，并給出各類時(shí)態(tài)約束類別 之間的聯(lián)系。雖然這些研究成果給出了時(shí)態(tài)x m l 一致性沖突的解決方法，但都 是基于全文檔的檢查，未能進(jìn)行增量的驗(yàn)證和修復(fù)，會導(dǎo)致更新的一致性沖突以 至于修復(fù)不完全或者反復(fù)檢查，影響更新操作的實(shí)現(xiàn)效率。 1 3 4 時(shí)態(tài)x m l 的更新操作 從目前的研究現(xiàn)狀來看，學(xué)者們的研究重點(diǎn)主要集中在時(shí)態(tài)x m l 查詢語言 上，對時(shí)態(tài)x m l 的更新問題研究的甚少，對于在時(shí)態(tài)x m l 文檔上的更新，以及 更新操作所帶來的時(shí)態(tài)一致性約束的沖突，就更少了。然而，對時(shí)態(tài)x m l 來說， 必然會面臨時(shí)態(tài)x m l 更新時(shí)一致性約束沖突的問題，這種滿足時(shí)態(tài)x m l 一致性 約束的更新操作萌生了極大的研究需求。 關(guān)于x m l 文檔更新的研究，“e x c e l o nx m lr e p o s i t o r y ”是其中較少支持x m l 更新的一種系統(tǒng)，它主要是通過擴(kuò)展x p a t h 語言來支持一些簡單的插入和刪除操 作【3 4 】。i g o rt a t a r i n o v 和z a c h a r yg i v e s 等人是通過擴(kuò)展x q u e r y 語言來討論x m l 的 更新機(jī)制，他們還討論在關(guān)系數(shù)據(jù)庫上進(jìn)行x m l 更新的問趔3 5 1 。k u ny u e 等人在 文獻(xiàn)m 中提出將關(guān)系數(shù)據(jù)庫中的完整性約束以函數(shù)依賴的規(guī)則映射到相應(yīng)的 x m l 數(shù)據(jù)模型，用來保證更新操作的數(shù)據(jù)完整性約束。 與傳統(tǒng)x m l 文檔更新研究不同，時(shí)態(tài)x m l 文檔的更新涉及時(shí)態(tài)元素的更新， 很難通過傳統(tǒng)的關(guān)系數(shù)據(jù)庫來實(shí)現(xiàn)。另外，由于時(shí)態(tài)x m l 文檔的查詢都是基于 時(shí)態(tài)x m l 索引進(jìn)行的，時(shí)態(tài)x m l 文檔的更新操作需要保證索引文件與時(shí)態(tài)x m l 同步更新。f l a v i or i z z o l o 和a a v a i s m a n 在文獻(xiàn)【4 0 】中通過擴(kuò)展的t x p a t h 更新語句 來支持時(shí)態(tài)元素的更新，并通過更新時(shí)態(tài)x m l 索引文件，將更新后的索引文件 映射到時(shí)態(tài)x m l 文檔上來實(shí)現(xiàn)的。但這種方法仍然會面臨時(shí)態(tài)x m l 更新時(shí)一致 性約束沖突的問題。 時(shí)態(tài)x m l 文檔更新的一致性檢查及處理( 2 0 1 0 )第一章引言 1 4 研究思路與本文貢獻(xiàn) 針對以上關(guān)于時(shí)態(tài)x m l 的最新研究成果，本文分別從傳統(tǒng)x m l 文檔和時(shí)態(tài) 數(shù)據(jù)庫兩方面出發(fā)，在x m l 文檔上擴(kuò)展時(shí)態(tài)屬性，給出時(shí)態(tài)x m l 數(shù)據(jù)模型，提 出一種易于表達(dá)時(shí)態(tài)x m l 一致性的模型映射，在此模型映射的基礎(chǔ)上，對時(shí)態(tài) x m l 文檔進(jìn)行一致性的檢查。 考慮到當(dāng)前研究成果 4 0 , 4 1 】主要集中在時(shí)態(tài)x m l 一致性的全文檢查，忽略了 更新所帶來的新的一致性沖突。因此，本文借鑒了文獻(xiàn)f 3 8 1 中所提出的增量檢查 傳統(tǒng)x m l 一致性約束的思想，將其運(yùn)用到時(shí)態(tài)x m l 文檔更新的一致性檢查和處 理上，分別從兩方面進(jìn)行了時(shí)態(tài)x m l 一致性的增量檢查：方面從傳統(tǒng)x m l 文 檔約束出發(fā)，通過增量的驗(yàn)證s c h e m a 模式文檔，發(fā)現(xiàn)x m l 文檔的一致性沖突； 另一方面從時(shí)態(tài)x m l 一致性出發(fā)，分別對四種一致性沖突進(jìn)行增量的檢查和修 復(fù)，并擴(kuò)展重寫了時(shí)態(tài)x m l 更新查詢語句t x p a t h ，更新操作與增量的一致性檢 查和修復(fù)相結(jié)合，這樣可以在更新之前就發(fā)現(xiàn)一致性的沖突并及時(shí)修復(fù)，避免了 更新后的全文檢查和反復(fù)校驗(yàn)更新。最后通過仿真實(shí)驗(yàn)來分析和驗(yàn)證以上的研究 思路。 因此，本文研究工作的主要貢獻(xiàn)和創(chuàng)新點(diǎn)可以概括如下： ( 1 ) 討論了一種x m l 時(shí)態(tài)擴(kuò)展的數(shù)據(jù)模型，并給出了一種易于表達(dá)時(shí)態(tài) ) a l 一致性的模型映射，詳細(xì)探討了四種時(shí)態(tài)x m l 一致性約束； ( 2 ) 討論了時(shí)態(tài)x m l 一致性增量檢查的算法，分別從傳統(tǒng)x m l 一致性增量 檢查和四種時(shí)態(tài)x m l 一致性增量檢查出發(fā)，設(shè)計(jì)了時(shí)態(tài)l 一致性檢測引擎的 框架流程以及各個(gè)一致性增量檢查的實(shí)現(xiàn)算法； ( 3 ) 討論了時(shí)態(tài)x m i 一致性沖突的增量修復(fù)算法，結(jié)合基于索引的增量更 新操作，對時(shí)態(tài)x m l 的更新操作進(jìn)行一致性增量檢查的擴(kuò)展，并給出滿足時(shí)態(tài) x m l 一致性的更新算法，最后還擴(kuò)展了時(shí)態(tài)x m l 更新查詢語句t x p a t h ，使得更 新語句具備時(shí)態(tài)x m l 一致性增量檢查和修復(fù)的功能； ( 4 ) 通過較大數(shù)據(jù)量的仿真實(shí)驗(yàn)，分析以上時(shí)態(tài)x m l 模型的性能，驗(yàn)證時(shí) 態(tài)) ( m l 一致性增量檢查及修復(fù)的算法的性能，并與當(dāng)今的滿足時(shí)態(tài)一致性的時(shí) 態(tài)x m l 更新算法進(jìn)行比較，從相對寬泛角度說明了基于時(shí)態(tài)x m l 文檔更新的一 致性檢查和處理的可行性和靈活性。 6 時(shí)態(tài)x m l 文檔更新的一致性檢查及處理( 2 0 1 0 )第一章引言 1 5 論文組織結(jié)構(gòu) 本文共分七章，論文組織結(jié)構(gòu)如下： 第一章首先引入時(shí)態(tài)x m l 的研究背景和研究意義，然后介紹了時(shí)態(tài)x m l 相關(guān)領(lǐng)域的國內(nèi)外研究現(xiàn)狀，又介紹了本文的研究思路和創(chuàng)新點(diǎn)等。 第二章介紹了本文研究需要的相關(guān)理論與技術(shù)基礎(chǔ)，包括時(shí)態(tài)數(shù)據(jù)庫的基礎(chǔ) 知識和) ( 】l 相關(guān)的基礎(chǔ)知識。 第三章給出了x m l 數(shù)據(jù)模型和一個(gè)時(shí)態(tài)x m l 數(shù)據(jù)模型，并探討和實(shí)現(xiàn)了 四種將時(shí)態(tài)x m l 數(shù)據(jù)模型映射到一個(gè)具體的x m l 文檔的映射方案。 第四章給出了x m l 數(shù)據(jù)模型一致性和時(shí)態(tài)x m l 數(shù)據(jù)模型一致性的定義， 給出了時(shí)態(tài)x m l 一致性檢查的算法，并設(shè)計(jì)出時(shí)態(tài)x m l 一致性檢測引擎的框 架流程。 第五章給出了時(shí)態(tài)x m l 一致性沖突的修復(fù)算法，以及滿足時(shí)態(tài)x m l 一致 性的更新操作的算法，包括結(jié)點(diǎn)插入、刪除算法以及對t x p a t h 語句進(jìn)行時(shí)態(tài) x m l 一致性檢查修復(fù)的擴(kuò)展。 第六章通過大量的仿真實(shí)驗(yàn)分析時(shí)態(tài)x m l 一致性檢查與修復(fù)的性能，以及 驗(yàn)證滿足時(shí)態(tài)x m l 一致性的更新操作的可行性和靈活性。 第七章對前面的工作進(jìn)行了總結(jié)，并提出了下一步研究工作的展望。 7 時(shí)態(tài)x m l 文檔更新的，致性檢查及處理( 2 0 1 0 ) 第二章相關(guān)背景知識 第二章相關(guān)理論與技術(shù)基礎(chǔ) 2 1時(shí)態(tài)數(shù)據(jù)庫基礎(chǔ)知識 自2 0 世紀(jì)8 0 年代初時(shí)態(tài)數(shù)據(jù)庫技術(shù)產(chǎn)生以來，經(jīng)過2 0 多年的研究和實(shí)踐， 時(shí)態(tài)數(shù)據(jù)庫在基礎(chǔ)理論、數(shù)據(jù)模型、數(shù)據(jù)庫語言、應(yīng)用技術(shù)等方面都取得了豐盛 的成果，已經(jīng)成為數(shù)據(jù)庫與信息系統(tǒng)中一個(gè)重要的、充滿活力的學(xué)科方向b 】。 我國學(xué)者唐常杰也對時(shí)態(tài)數(shù)據(jù)庫技術(shù)的發(fā)展進(jìn)行了研究和總結(jié) 3 6 , 3 7 】。下面，本文 就涉及到的相關(guān)的時(shí)態(tài)數(shù)據(jù)庫概念進(jìn)行介紹。 2 1 1 基本術(shù)語 以下是基本的時(shí)態(tài)術(shù)語： ( 1 ) 時(shí)間粒度：時(shí)間在時(shí)間軸上是客觀存在，單向連續(xù)的，但從計(jì)算機(jī)的 數(shù)字化特點(diǎn)來說，要對時(shí)態(tài)信息進(jìn)行研究，需要先對時(shí)間進(jìn)行離散化處理，將時(shí) 間表示為離散的時(shí)間點(diǎn)，其中最小的基本單位就是時(shí)間粒度。例如，以小時(shí)作為 時(shí)間粒度，則表示時(shí)間時(shí)就只能以小時(shí)作為最小的單位。 ( 2 ) 時(shí)間點(diǎn)：又稱為時(shí)刻，是建立在時(shí)間粒度之上，可以看成是某個(gè)離散 的時(shí)間點(diǎn)。例如2 0 1 0 年7 月1 日，就是一個(gè)時(shí)間點(diǎn)。 ( 3 ) 時(shí)間區(qū)間：用于描述某一段連續(xù)的時(shí)間段，它有固定的起始時(shí)間點(diǎn)和 終止時(shí)間點(diǎn)。例如，從2 0 1 0 年7 月1 日到2 0 1 0 年7 月1 9 日，這就是一個(gè)時(shí)間 區(qū)間。 ( 4 ) 時(shí)間跨度：指時(shí)間區(qū)間上持續(xù)的一段時(shí)間，表示時(shí)間的長度。例如對 于2 0 1 0 年7 月1 日到2 0 1 0 年7 月1 9 日，時(shí)間跨度就是1 9 天了( 其中以“天” 作為時(shí)間粒度) 。 2 1 2 三種基本時(shí)間 ( 1 ) 用戶自定義時(shí)間【1 5 】 指用戶根據(jù)自己的需要或理解定義的時(shí)間。這種時(shí)間的屬性值一般是時(shí)間 8 時(shí)態(tài)x m l 文檔更新的一致性檢查及處理( 2 0 1 0 )第一章相關(guān)背景知識 點(diǎn)，用戶本身會解釋他所給出的時(shí)間信息，數(shù)據(jù)庫系統(tǒng)不需要解釋該數(shù)據(jù)的含義， 只需將此時(shí)間域等同于其他般的屬性域來理解，對它的操作和對普通字符串的 操作幾乎沒有什么差別。例如，“生日”本來不是一種標(biāo)準(zhǔn)數(shù)據(jù)類型，但是當(dāng)用戶 根據(jù)自己的需要定義了一個(gè)“生日”類型的屬性，一個(gè)記錄相對應(yīng)的該屬性的值為 “1 9 8 5 0 9 2 3 ”，那么這個(gè)時(shí)間就是一種用戶自定義時(shí)間。系統(tǒng)不會對它有特別的 處理，它的提供和更新都是由用戶自己完成的。 用戶在一般傳統(tǒng)數(shù)據(jù)庫中都可以使用自定義數(shù)據(jù)類型，即在原來數(shù)據(jù)類型的 基礎(chǔ)上定義自己的數(shù)據(jù)類型。在數(shù)據(jù)表建立或結(jié)構(gòu)被修改時(shí)，這些用戶自定義的 數(shù)據(jù)類型和其它標(biāo)準(zhǔn)數(shù)據(jù)類型一樣被用戶使用。同樣，用戶也可以在時(shí)態(tài)數(shù)據(jù)庫 中使用自定義數(shù)據(jù)類型。時(shí)態(tài)數(shù)據(jù)庫不對用戶自定義時(shí)間做任何處理，不需要專 門的語言支持。用戶自定義時(shí)間值是完全依賴應(yīng)用的，由用戶和系統(tǒng)以常規(guī)方式 存取。 ( 2 ) 有效時(shí)間 有效時(shí)間指一個(gè)對象( 事件) 在現(xiàn)實(shí)世界中發(fā)生并保持的那段時(shí)間，即該對 象在現(xiàn)實(shí)世界中為真的時(shí)間。既可以反映過去和現(xiàn)在的時(shí)間，也可以反映將來的 時(shí)間，記錄了現(xiàn)實(shí)模型隨時(shí)間而變化的狀態(tài)信息?！? 5 】 有效時(shí)間可以是單一的時(shí)間點(diǎn)、單一的時(shí)間區(qū)間，或者是時(shí)間點(diǎn)的集合、時(shí) 間區(qū)間的有限集合，也可以是整個(gè)時(shí)間域。和用戶自定義時(shí)間不同，當(dāng)查詢語句 被檢測到有時(shí)態(tài)語義的時(shí)候，有效時(shí)間是由數(shù)據(jù)庫系統(tǒng)解釋的。有效時(shí)間的提供 和更新都是由用戶來完成的?！? 5 】 有效時(shí)間對事物的描述比較直觀、容易理解。下表是一個(gè)有效時(shí)間的例子。 表2 - 1 一個(gè)包含有效時(shí)間的歷史關(guān)系 姓名身份 起始有效時(shí)間終止有效時(shí)間 石小碩高中生 2 0 0 1 9 12 0 0 4 7 1 石小碩大學(xué)生2 0 0 4 9 12 0 0 8 7 1 石小碩研究生2 0 0 8 9 1n o w ( 3 ) 事務(wù)時(shí)間 9 時(shí)態(tài)x m l 文檔更新的一致性檢查及處理( 2 0 1 0 )第- 章榭關(guān)背景知識 記錄了對數(shù)據(jù)庫修改或更新的各種操作歷史，對應(yīng)于現(xiàn)有事務(wù)或現(xiàn)有數(shù)據(jù)庫 狀態(tài)變遷的歷史。事務(wù)時(shí)間是應(yīng)用獨(dú)立的，用戶不可以修改事務(wù)時(shí)間。數(shù)據(jù)庫中 的數(shù)據(jù)錄入數(shù)據(jù)庫的時(shí)間、修改和刪除的時(shí)間是由系統(tǒng)時(shí)鐘決定的，而修改后的 數(shù)據(jù)也是不能夠改變的。1 1 5 1 事務(wù)時(shí)間可能與有效時(shí)間相同，但在大多數(shù)應(yīng)用中兩者并不一致。例如，在 2 0 0 4 年7 月1 9 日，某大學(xué)通知學(xué)生石小碩已經(jīng)被錄取，9 月1 號去報(bào)到，同時(shí) 該大學(xué)將石小碩錄入新生數(shù)據(jù)庫。那么7 月1 9 日是新的學(xué)生記錄的事務(wù)時(shí)間， 而9 月1 日是新的學(xué)生記錄的有效時(shí)間起點(diǎn)。在這個(gè)例子中，事務(wù)時(shí)間是早于有 效時(shí)間的。如果石小碩2 0 0 3 年已入學(xué)，但該大學(xué)2 0 0 4 年才將石小碩錄入數(shù)據(jù)庫， 則事務(wù)時(shí)間就會晚于有效時(shí)間。 事務(wù)時(shí)間不能晚于現(xiàn)在時(shí)間，因?yàn)樗从持鴶?shù)據(jù)庫實(shí)際操作的時(shí)間。與有效 時(shí)間不同，事務(wù)時(shí)間不能指未來。1 1 5 ( 4 ) 3 種時(shí)間數(shù)據(jù)的應(yīng)用 在目前的時(shí)態(tài)數(shù)據(jù)庫中，3 種基本時(shí)間都得到了廣泛的應(yīng)用。一個(gè)時(shí)態(tài)關(guān)系 是一個(gè)歷史狀態(tài)的序列，每個(gè)歷史狀態(tài)是能夠表示有效時(shí)間的完整的歷史關(guān)系。 每個(gè)事務(wù)的提交將導(dǎo)致一個(gè)新的歷史狀態(tài)的產(chǎn)生，因此時(shí)態(tài)關(guān)系是不斷增加的。 表2 - 2 是一個(gè)三種時(shí)間的綜合應(yīng)用示例。 t 5 1 表2 2 三種時(shí)間的綜合應(yīng)用示例 姓名 出生年月工資部門 2 0 0 9 0 ，9 4 】數(shù)學(xué)系 9 0 ，9 2 】 張三 1 9 7 0 0 1 0 8 3 6 0 9 5 ，9 8 】 物理系 9 3 ，9 8 】 5 5 0 9 9 ，n o w 軟件所 9 9 ，n o w 1 9 0 1 8 9 ，9 1 】物理系 8 9 ，9 5 】 2 5 0 9 2 ，9 5 】軟件所 9 6 ，9 9 】 李四 1 9 6 8 0 8 1 8 4 0 0 9 6 ，9 9 】 計(jì)算機(jī)系 6 0 0 2 0 0 0 ，n o w 【2 0 0 0 ，n o w 在表2 2 中，每一個(gè)元組的工資屬性值都是由兩個(gè)部分構(gòu)成的，前一個(gè)部分 1 0 時(shí)態(tài)x m l 文檔更新的。致性檢查及處理( 2 0 1 0 )第二章相關(guān)背景知識 是工資的值，后一部分是工資的有效時(shí)間，例如張三的工資中的2 0 0 元對應(yīng)的 【9 0 ，9 4 ，即張三工資為2 0 0 元的時(shí)間有效值，也就是我們所說的有效時(shí)間。出生 年月中的時(shí)間1 9 7 0 0 1 0 8 就是數(shù)據(jù)庫的設(shè)計(jì)者或用戶定義的時(shí)間，即用戶自定 義時(shí)間。在這個(gè)圖表中沒能清楚的表明出事務(wù)時(shí)間，但是至少該圖表建立的時(shí)間 就是一個(gè)事務(wù)時(shí)間。 2 1 3 時(shí)態(tài)數(shù)據(jù)庫 按表示時(shí)態(tài)信息的方式，可以將數(shù)據(jù)庫分成基本的4 種類型：快照數(shù)據(jù)庫 ( s n a p s h o td a t a b a s e ) 、回滾數(shù)據(jù)庫( r o l l b a c kd a t a b a s e ) 、歷史數(shù)據(jù)庫( h i s t o r i c a l d a t a b a s e ) 和雙時(shí)態(tài)數(shù)據(jù)庫( b i t e m p o r a ld a t a b a s e ) 。通常將后3 種稱為時(shí)態(tài)數(shù)據(jù) 庫( t e m p o r a ld a t a b a s e ) 1 1 0 1 。 ( 1 ) 快照數(shù)據(jù)庫：舊 快照數(shù)據(jù)庫是指以特定時(shí)刻的瞬間快照來建立模型，考慮現(xiàn)實(shí)世界。一般由 靜態(tài)的二維關(guān)系表組成：屬性維與元組維?？煺諗?shù)據(jù)庫無法表示屬性與時(shí)間的關(guān) 系，只能進(jìn)行當(dāng)前數(shù)據(jù)庫狀態(tài)的增、刪、查、改等操作。從時(shí)態(tài)數(shù)據(jù)庫的觀點(diǎn)來 看，快照數(shù)據(jù)庫不區(qū)分事務(wù)時(shí)間和有效時(shí)間。 ( 2 ) 回滾數(shù)據(jù)庫：【1 5 】 回滾數(shù)據(jù)庫( r o l l b a c kd a t a b a s e ) 支持事務(wù)時(shí)間，它按事務(wù)時(shí)間進(jìn)行編址， 保存了過去每次事務(wù)提交、狀態(tài)演變之前的狀態(tài)。 回滾數(shù)據(jù)庫由三維的回滾關(guān)系組成，在屬性維和元組維的基礎(chǔ)上增加了事務(wù) 時(shí)間維，因此可看作是一個(gè)按時(shí)間編址的瞬象的序列。其中每一個(gè)時(shí)間點(diǎn)都對應(yīng) 于一個(gè)二維的快照數(shù)據(jù)庫。 每個(gè)事務(wù)都產(chǎn)生一個(gè)新的靜態(tài)關(guān)系保留在數(shù)據(jù)庫中，即使數(shù)據(jù)庫毫無變遷， 回滾數(shù)據(jù)庫也保持了數(shù)據(jù)變遷的歷史，這樣就會產(chǎn)生很多冗余。 回滾數(shù)據(jù)庫記錄了數(shù)據(jù)庫事務(wù)變化歷史。任何一個(gè)更新語句的執(zhí)行將產(chǎn)生一 個(gè)新的數(shù)據(jù)庫狀態(tài)，新狀態(tài)不會覆蓋舊的狀態(tài)，因此沒有數(shù)據(jù)會被物理刪除。通 過將一個(gè)元組的事務(wù)結(jié)束時(shí)間設(shè)為執(zhí)行語句的當(dāng)前時(shí)間，從而實(shí)現(xiàn)元組在語義上 的“刪除”。事務(wù)時(shí)間區(qū)間可以看成是該元組在快照數(shù)據(jù)庫中存在的歷史。 ( 3 ) 歷史數(shù)據(jù)庫：f 1 5 】 時(shí)態(tài)x m l 文檔更新的一致性檢查及處理( 2 0 1 0 ) 第一章棚關(guān)背景知識 記錄事實(shí)的有效時(shí)間的數(shù)據(jù)庫稱為歷史數(shù)據(jù)庫，它由“歷史關(guān)系”組成，每一 個(gè)元組記錄了數(shù)據(jù)的一個(gè)“歷史”的狀態(tài)，可以是過去、現(xiàn)在或?qū)?，存儲和管?客觀對象在有效時(shí)間點(diǎn)的事件或狀態(tài)變化的經(jīng)歷。 真實(shí)世界中事實(shí)的每一個(gè)變化將產(chǎn)生一個(gè)新的狀態(tài)。歷史數(shù)據(jù)庫支持有效時(shí) 間，數(shù)據(jù)冗余度小，結(jié)構(gòu)相對簡單。但是它不支持事務(wù)時(shí)間，不可以像回滾數(shù)據(jù) 庫一樣對以前的某一個(gè)狀態(tài)進(jìn)行查詢。 ( 4 ) 雙時(shí)態(tài)數(shù)據(jù)庫：f 1 5 j 雙時(shí)態(tài)數(shù)據(jù)庫既支持事務(wù)時(shí)間又支持有效時(shí)間，集成了前3 種類型數(shù)據(jù)庫的 功能特性，儲存了數(shù)據(jù)庫和現(xiàn)實(shí)世界兩者發(fā)展的歷史。這種數(shù)據(jù)庫才是真正的對 數(shù)據(jù)時(shí)態(tài)屬性支持的數(shù)據(jù)庫。但是應(yīng)當(dāng)值得注意的是，雙時(shí)態(tài)數(shù)據(jù)庫是以犧牲大 容量的存儲空間為代價(jià)的，對雙時(shí)態(tài)數(shù)據(jù)庫的儲存進(jìn)行優(yōu)化是時(shí)態(tài)數(shù)據(jù)庫研究的 一個(gè)重要工作。 2 2x m l 基礎(chǔ)知識 2 2 1 x m l 簡介 x m l ( e x t e n s i b l em a r k u pl a n g u a g e ，可擴(kuò)展標(biāo)記語言) ，是一種可由用戶自行 創(chuàng)建標(biāo)記的標(biāo)記語言。它由w 3 c ( w r o r l dw i d ew e bc o n s o r t i u m ，萬維網(wǎng)協(xié)會) 的工作組創(chuàng)建，用以克服h t m l 的局限。這個(gè)工作組這樣描述該語【1 ，2 】：“x m l 是s g m l ( s t a n d a r dg e n e r a l i z e dm a r k u pl a n g u a g e ，標(biāo)準(zhǔn)通用標(biāo)記語言) 的子集， 其目標(biāo)是允許普通的s g m l 在w e b 上以目前h t m l 的方式被服務(wù)、接收和處 理?！?x