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

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