7 6揚州大學(xué)碩十學(xué)位論文 揚州大學(xué)學(xué)位論文原創(chuàng)性聲明和版權(quán)使用授權(quán)書 ，學(xué)位論文原創(chuàng)性聲明 本人聲明：所呈交的學(xué)位論文是在導(dǎo)師指導(dǎo)下獨立進(jìn)行研究工作所取得的 研究成果。除文中已經(jīng)標(biāo)明引用的內(nèi)容外，本論文不包含其他個人或集體已經(jīng) 發(fā)表的研究成果。對本文的研究做出貢獻(xiàn)的個人和集體，均已在文中以明確方 式標(biāo)明。本聲明的法律結(jié)果由本人承擔(dān)。 學(xué)位論文作者簽名： t | 糾：濰 l 】廠月巧日 學(xué)位論文版權(quán)使用授權(quán)書 本人完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，即：學(xué)校有權(quán)保留并 向國家有關(guān)部門或機(jī)構(gòu)送交學(xué)位論文的復(fù)印件和電子文檔，允許論文被查閱和 借閱。本人授權(quán)揚州大學(xué)可以將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn) 行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存、匯編學(xué)位論文。同時授 權(quán)中國科學(xué)技術(shù)信息研究所將本學(xué)位論文收錄到中國學(xué)位論文全文數(shù)據(jù)庫， 并通過網(wǎng)絡(luò)向社會公眾提供信息服務(wù)。 學(xué)位論文作者簽名： 卻? 海 導(dǎo)師簽名：鶘 簽字日期：咄婦婦 簽字日期衢丁序，日 ( 本頁為學(xué)位論文末頁。如論文為密件可不授權(quán)，但論文原創(chuàng)必須聲明。) 劉海東：基于瑚l 的數(shù)據(jù)共享與查詢技術(shù)及其應(yīng)用研究 摘要 隨著大量l 數(shù)據(jù)的出現(xiàn)，如何有效地存儲、管理、共享和查詢這些l 數(shù) 據(jù)，就成為一個值得研究的重要課題。目前，x 1 訂l 數(shù)據(jù)管理技術(shù)是數(shù)據(jù)庫領(lǐng)域的 研究熱點。本文對l 的數(shù)據(jù)共享與數(shù)據(jù)查詢技術(shù)的一些關(guān)鍵技術(shù)進(jìn)行了研究， 包括x m l 索引、x m l 流數(shù)據(jù)查詢執(zhí)行器的增量維護(hù)、x m l 數(shù)據(jù)交換的模型。取得 的成果體現(xiàn)在以下三個方面： 1 ) 在) ( 1 l 的發(fā)展過程中，如何有效的查詢刪l 數(shù)據(jù)已成為一個研究熱點。 其中如何快速和有效的判斷兩元素是否具有祖先后裔( 咖e s t o r d e s c e n d 觚t ) 關(guān)系 最為關(guān)鍵。目前已有的素數(shù)編碼方法需要大量素數(shù)和很多大素數(shù)，為此，本文提 出一種改進(jìn)的素數(shù)編碼方法最多親兄弟素數(shù)( m o s tb r o t h e r sp r i m e ，簡稱 m b p r i m e ) ，該方法不必每個節(jié)點都使用新素數(shù)。m b p r i m e 素數(shù)編碼方法大大減 少了素數(shù)的使用量，減少了所用的大素數(shù)，加快了x m l 查詢的速度。 2 ) 提出了基于樹型結(jié)構(gòu)的l 查詢增量維護(hù)算法t s q m ( 1 r e es n u c t u i ea b o u t q u e 巧m a i m e n a c e ) 。t s q m 算法使用樹型結(jié)構(gòu)來表達(dá)x p a t h 查詢的l 數(shù)據(jù)流之上 持續(xù)查詢執(zhí)行器的增量維護(hù)方法，該方法使用樹型結(jié)構(gòu)表示，廣、“ ) ( 1 l 結(jié)點關(guān) 系的合并，使用自動機(jī)表示狀態(tài)轉(zhuǎn)換。t s q m 算法對x m l 樹型結(jié)構(gòu)進(jìn)行動態(tài)維 護(hù)，避免了在沒有d t d 情況下出現(xiàn)的環(huán)形結(jié)構(gòu)的復(fù)雜操作，減少了維護(hù)的時間和 狀態(tài)轉(zhuǎn)換的數(shù)量。t s q m 算法能夠以有限轉(zhuǎn)換路徑為代價，有效完成l 數(shù)據(jù)流 持續(xù)查詢執(zhí)行器的動態(tài)維護(hù)，減少了增量維護(hù)的時間，和狀態(tài)轉(zhuǎn)換數(shù)量。 3 ) 提出了基于訂l 技術(shù)的信息交換模型，采用x m l 文檔作為底層的信息 交換載體，建立了i n t e m e t i 衄- 鋤e t 環(huán)境下的信息集成交換平臺，開發(fā)實現(xiàn)了相應(yīng) 的軟件構(gòu)件，為低層本地實現(xiàn)異構(gòu)數(shù)據(jù)庫系統(tǒng)間信息的集成與共享提供了一種有 力的方法和手段。并在重大環(huán)境污染事故危險源管理系統(tǒng)中加以實現(xiàn)，實現(xiàn)了各 級環(huán)保部門之間的l 數(shù)據(jù)交換，同時對x m l 在企業(yè)間信息交換的工作機(jī)理和 應(yīng)用模式進(jìn)行了探討。 2 揚州大學(xué)碩士學(xué)位論文 關(guān)鍵詞：x i l ；素數(shù)編碼；最多親兄弟素數(shù)；t s q m ；增量維護(hù)；x m l 數(shù)據(jù)流； 信息交換 劉海東：基于煳l 的數(shù)據(jù)共享與查詢技術(shù)及其應(yīng)用研究 3 a b s t r a c t w 油m ee m e 略e n c eo fal a r g en 啪b e ro fx m ld 旭h o wt 0s t o r ee 船c t i v e l y ， m a n a g e ，s h a r e ，a n dq u e 巧t h e s ex m l 訛i m sb e c o m ea ni m p o r t a n tt o p i c 、o r ( 1 1 yo f 咖d y a tp r e s e n t ，n l et e c l l i l o l o g yo fx m l d a t am a l l a g e m e n ti sah o tt o p i ci nm ef i e l do f d a 油a s e i nt h i sp a p e r ，w er c s e a r c ho nm ek e yt e c l l i l o l o g i e so fm ex m ld a t as 蜥n ga i l d q r y i n g ，i n c l u d i n gx m li n d e x ， m ex m ld o c 啪e n t c l u s c e r ， t h ei i l c r e m e n t a l m a i m e n a l l c eo fc o n t i n u o u sq u e 巧e v a l u a t o ro v e rx m ld a 協(xié)s 訊；a mb a s e do nt 1 1 et r e e 咖l c n 玳a i l dad a t ae x c h a l l g i n gm o d e lb 嬲e do nx m l t e c i l l l i q u e 1 1 1 em a i nc o n t r i b u t i o l l s a i l di n n o v a t i o n so f t l l i sd i s s e r t a t i o na i l ea sf o u o w s ： 1 ) h lt h ed e v e l o p m e n to f t h ex m l ，l l o wt oq u e 巧x m ld o c 啪e n t sh a sb e e nah o t t o p i c h o wt 0q u i c h ya n de f j f i c i e n t l yj u d g ew h e t h e r l et v 舊e l e m e n t sh a v ear e l a t i o n s l l i p o fa i l c e s t o r d e s c e n d a l l ti sv e 巧i m p o r t 觚t n o wt l l ee x i s t e dp r i m en 啪b e rl a b e l i i 瑪r l e e d sa n u m b e ro fp r i m e s 鋤dm a i l yb i gp r i m e s ，t h e r e f o r e ，趾i m p v e dp r i i l l en 啪b e rla _ b e l i n g s c h e m ei sp r o p o s e d n sn on e e dt ou s en e wp r i m en u 【l i l b e r sf o re a c hn o d ei nt h i sm e t h o d 1 1 1 en m n b e r so f 研m e 觚d 恤l 鶘e 面m ea r er e d u c e di nt h em b p r i m es c h e m e t h u s ， t 1 1 em b p r i m es c h e m es p e e d su pt l l eq u e 巧i n g 2 ) ax m l q u e r ) ，m a i n t e n a n c eb a s e do n 仃e es t m c t l l r e 卜- t s q mi sp r o p o s e d t s q m a l g o r i i s a l li n c r e l n e 刪m a i n t e n a n c eo fc o m i n u o u sq u e 巧e v a l u a t o ro v e rx m ld a t a s t r e 鋤u s i n gt h e 仃e es t n l c t u r et oe x p r e s st 1 1 ex p a t hq u e 巧t s q ma l g o r i t h mu s e s 仃e e s 臼m c t u r et oe x p r e s st l l ec o a l i t i o no ft h er e l a t i o n s l l i p sb e t 、e e nt h ex m li l o d e ss u c ha s 緲，”棗”a 1 1 du s e st h ea u 幻m a _ t at oe x p r e s st h ec o n v e r s i o no fs t a t e t s q ma l g o r i 蚰 、析t h o u ta d d i i 培t l l ei i l i t i a ls t a t e si sa i m e da tt h ed y n 鋤i cm a 缸e r m n c eo ft r e es t 九j c t u r e ， w h i c ha v o i d st h ec 嬲e so ft 1 1 ea i l i l u l a rs n - u c t u l eo p e r a t i o ni n 廿l ea b s e n c eo fad t da n d r e d u c e sm et i m eo fm a i n t e n a l l c ea n dt h en 啪b e ro fm et r a l l s i t i o n so fs t a t e t s q m a l g o r i 恤 1 lc a i le 伍c i e n t l ym a i n t a j nt t l ee v a l 咖ro ft h ec o n t i n u o u sq u e r ) ，o v e rx i ld a t a s 仃e 鋤a tal o wc o s to fe x 衄t r a n s i t i o n so fp a t h s ，a l l dr e d u c e st h et i m eo fm a i n t e n a n c e 4 揚州人學(xué)碩士學(xué)位論文 a i l dt h en 啪b e ro ft 1 1 et r a n s i t i o n so fs 乜l t e 3 ) ad a t ae x c h a l l g i n gm o d e lb 舔e d0 nx m lt e c t h l i q u ei sp r o p o s e d u s i n gx m l d o c 啪e n t sa sm eb a s eo fd a t ac o n l i i l u i l i c a t i o nc a r r i e r t h ei n f o n n a t i o nc o m m u i l i c a t i o n p l a t f o 珊u i l d e ri n t e m e t i n t r a n e te n v i r o 衄e n ti se s 切b l i s h e da i l dt h es o f h a r ec o i n p o n e m i sd e v e l o p e d ，、) i ，! 1 1 i c hp r o v i d e sa ne f f e c t i v el o 、v - c o s tm e t h o da 1 1 dt 0 0 1t oi 1 1 t e 黟a t ea i l d s l l 乏旺ed i f r e r e n tf 0 珊a td a t ab e t 、e e nh e t e r o g e n e o u s 出也山a s e s i nt l l i sa r t i c l e 、v er e a l i z e t h ed a t a e x c h a n g i n gb 嬲e do nt 1 1 e lt e c h i l i q u e ，舡c h i s d u r i n g t l i ec l 嬲s e d e n v i r o m n e md 印a r t m e n t si nt h ed a t a b ；a s em 齜l a g e m e ms y s t e mo ff a t a le n v i r o m n e m m c o 觸眥i n a t o ra c c i d e md a l l g e r ，a i l dd i s c u s st l l eo p e r a t i o np r i n c i p l e s 鋤da p p l i c a t i o n m o d e so fx m li o m a t i o ne x c h a l l g e 鋤o n ge m e 印r i s e s k 叼啊o r d s ：x m l ；p r i m el m m b e rl a b e l i n g ；m b p r i m e ；t s q m ；m e i n c r c m e n t a l m a i n t e n a n c e ；x m ld a t as t r e a m ；i i l f o n n a t i o ne x c h a i l g e 劉海東：基于x m l 的數(shù)據(jù)共享與查詢技術(shù)及其應(yīng)用研究 5 第一章引言 在本章中，我們將介紹目前x m l 的發(fā)展、x m l 數(shù)據(jù)庫系統(tǒng)研究的主要途徑， 目前x m l 研究的主要內(nèi)容，基于這些背景知識的介紹，我們提出本文的主要工 作，即提出了一種改進(jìn)的素數(shù)編碼方法郴p r i m e 、提出了基于樹型結(jié)構(gòu)的 x m l 查詢增量維護(hù)算法t s q m ( 1 r e es 仃u c t u r ea b o u tq u e 巧m a i n t e n a c e ) 、提出了基 于l 技術(shù)的信息交換模型。本章的最后列出了本論文的組織結(jié)構(gòu)。 1 1 研究背景 網(wǎng)絡(luò)技術(shù)的飛速發(fā)展改變了人們的生活、工作方式和思維方式，拓寬了人們 獲取知識和信息的途徑。x m l ( e e n s i b l em a r k u pl 趾g u a g e ，可擴(kuò)展標(biāo)記語言) 就是這樣飛速發(fā)展的技術(shù)之一。 l 起初主要是為了增強(qiáng)應(yīng)用程序從w e b 上獲取文檔的解釋和操作能力而產(chǎn) 生的。然而，從數(shù)據(jù)庫的角度看，隨著大量x m l 數(shù)據(jù)的出現(xiàn)，如何有效地存儲、 管理、共享和查詢這些x m l 數(shù)據(jù)，就成為一個值得研究的重要課題。目前，x m l 數(shù)據(jù)庫技術(shù)是數(shù)據(jù)庫領(lǐng)域的研究熱點。 對x m l 數(shù)據(jù)庫系統(tǒng)的研究主要有兩種途徑：一是純( n a t i v e ) x m l 數(shù)據(jù)庫系統(tǒng)， 它是為x m l 數(shù)據(jù)量身定做的數(shù)據(jù)庫系統(tǒng)。它的優(yōu)點是充分考慮到x m l 數(shù)據(jù)的特 點，以一種自然的方式來處理x m l 數(shù)據(jù)，能夠從各個方面較好地支持) ( 】l 的存儲 和查詢，但是，純x m l 數(shù)據(jù)庫要走向成熟還有很長的路。二是l 使能( x m l e i 劬l e d ) 數(shù)據(jù)庫系統(tǒng)，它是在已有的關(guān)系數(shù)據(jù)庫系統(tǒng)或面向?qū)ο髷?shù)據(jù)庫系統(tǒng)的基礎(chǔ) 上擴(kuò)充相應(yīng)的功能，使其能夠勝任x m l 數(shù)據(jù)的處理。目前，l 使能數(shù)據(jù)庫的研 究主要是基于關(guān)系數(shù)據(jù)庫的。這種方法的優(yōu)點是可以充分利用已有的非常成熟的 關(guān)系數(shù)據(jù)庫技術(shù)，集成現(xiàn)有的大量存儲在關(guān)系數(shù)據(jù)庫中的商用數(shù)據(jù)，本論文第三 章提出的m b p r i m e 算法就是將x m l 文檔編碼，然后用關(guān)系數(shù)據(jù)庫保存，將對x m l 文檔的查詢轉(zhuǎn)化為對關(guān)系數(shù)據(jù)庫的查詢。 6 揚州大學(xué)碩士學(xué)位論文 對x m l 數(shù)據(jù)庫系統(tǒng)的研究主要集中在7 個方面：一是對x m l 數(shù)據(jù)的編碼方案 和索引結(jié)構(gòu)進(jìn)行研究；二是對一些數(shù)據(jù)挖掘技術(shù)在v i l 文檔上的應(yīng)用，如：x m l 文檔的聚類、x m l 流數(shù)據(jù)的查詢、更新。三是對基于關(guān)系的) ( 1 l 使能數(shù)據(jù)庫進(jìn)行 研究，包括x m l 數(shù)據(jù)的關(guān)系存儲模式、x m l 查詢技術(shù)和查詢算法，以x m l 文檔發(fā) 布關(guān)系數(shù)據(jù)的技術(shù)，以及通過中間件實現(xiàn)以x m l 格式和x m l 查詢語言查詢關(guān)系數(shù) 據(jù)并進(jìn)行異構(gòu)數(shù)據(jù)源的信息集成等；四是對純x m l 數(shù)據(jù)庫系統(tǒng)進(jìn)行研究，包括存 儲結(jié)構(gòu)、索引技術(shù)、查詢技術(shù)和事務(wù)管理等；五是對x m l 的查詢技術(shù)、查詢算 法，x m l 查詢的包含與等價、樹模式查詢最小化，以及查詢優(yōu)化技術(shù)等進(jìn)行研 究；六是對l 查詢測試數(shù)據(jù)集、測試查詢范例進(jìn)行研究；七是對l 的查詢數(shù) 據(jù)模型、查詢語言和查詢代數(shù)等進(jìn)行研究。 1 2 課題的引出 l 查詢主要有以下兩種方法：( 1 ) 值查詢：在元素內(nèi)容上的選擇，即通過 限定在元素內(nèi)容或?qū)傩灾瞪系娜≈刀M(jìn)行的選擇查詢；( 2 ) 結(jié)構(gòu)查詢：通過路徑 表達(dá)式，對文檔中標(biāo)記的元素之間的結(jié)構(gòu)關(guān)系進(jìn)行查詢。元素之間的結(jié)構(gòu)關(guān)系包 括雙親孩子( p a r e n 訛h i l d ) 關(guān)系、祖先后裔( a i l c e s t o r d e s c e n d a n t ) 關(guān)系、之前之 后( p r e c e d i n f o l l o 麗n g ) 關(guān)系、左兄弟右兄弟( p r e c e d i n g - s i b l i n f o l l o 謝n g - s i b l i n g ) 關(guān)系等。對上述查詢，一種方法是建立x m l 文檔樹的路徑索引，并通過 路徑索引加速x m l 的查詢；另一種方法是對) ( 】l 文檔結(jié)點編碼，直接判斷結(jié)點之 間的關(guān)系，其中如何快速和有效的判斷祖先后裔( 觚c e s t o r d e s c e n d a n t ) 關(guān)系最為 關(guān)鍵，因此一個好的簡潔的編碼方案非常關(guān)鍵。目前已提出了一些x m l 數(shù)據(jù)的各 種編碼方案和索引技術(shù)【l ，2 ，3 ，4 】。由于兒的一個重要特點是可擴(kuò)展性，但這些文獻(xiàn) 編碼方案都不易更新，可擴(kuò)展性差。 流數(shù)據(jù)處理系統(tǒng)特點與傳統(tǒng)管理系統(tǒng)不同，傳統(tǒng)的數(shù)據(jù)庫管理系統(tǒng)主要特點 是數(shù)據(jù)持久存儲，在某一時刻執(zhí)行查詢并通過穩(wěn)定查詢計劃給出精確的回答；流 數(shù)據(jù)處理系統(tǒng)強(qiáng)調(diào)數(shù)據(jù)在線到達(dá)，查詢持久存儲，其主要應(yīng)用：傳感器網(wǎng)絡(luò)、位 置搜尋、網(wǎng)絡(luò)監(jiān)控、金融分析、在線拍賣等。x m 流數(shù)據(jù)查詢的特點是：用戶查詢 通常用a t l l 表示，一個用戶一次提交若干查詢。目前兒流查詢主要有基于自 劉海東：基于x m l 的數(shù)據(jù)共享與查詢技術(shù)及其應(yīng)用研究 7 動機(jī)的方法【5 ，6 ，7 ，引、索引的方法【9 1 、基于b l o o m f i l t e r 【1 0 1 方法、f i s t 【1 1 1 方法。目前 x m l 數(shù)據(jù)流查詢的相關(guān)研究大多假定數(shù)據(jù)流的查詢是持續(xù)的，即查詢提交之后不 會發(fā)生變化。然而，考慮到整個i n t e m e t 環(huán)境的不確定性，整個查詢集合進(jìn)行調(diào)整 的可能性卻非常大，這種調(diào)整必然導(dǎo)致一個問題：如何維護(hù)已經(jīng)建立的查詢執(zhí)行 器，從而滿足最新查詢處理的要求，解決上述問題一般可以采取兩種策略：重新 構(gòu)建和增量維護(hù)?？紤]到x m l 數(shù)據(jù)流環(huán)境中存在的海量查詢，重新構(gòu)造查詢執(zhí)行 器的代價非常高；另外，數(shù)據(jù)流環(huán)境要求系統(tǒng)能夠?qū)崟r處理輸入的數(shù)據(jù)，不允許 頻繁中斷現(xiàn)有操作來重新建立整個查詢執(zhí)行器。所以，查詢執(zhí)行器的維護(hù)只能采 用增量維護(hù)的策略。 對企業(yè)而言，產(chǎn)品質(zhì)量和成本差異曾是競爭力的要素，但隨著更多的企業(yè)采 用新技術(shù)，加上i i l t e m e t 的透明性，質(zhì)量和成本固然仍是重要因素，但是準(zhǔn)確、及 時的數(shù)據(jù)交換將更快上升到企業(yè)的關(guān)鍵競爭力的地位。企業(yè)間準(zhǔn)確、可靠、及時 的信息交換在電子商務(wù)中起著至關(guān)重要的作用。眾多的供應(yīng)商、合作伙伴和客 戶，都有各自的信息系統(tǒng)，這些信息系統(tǒng)不可能都出自于一個軟件開發(fā)商，所生 成的信息格式必然是不同的。因此，實現(xiàn)信息系統(tǒng)問的相異格式的數(shù)據(jù)的相互高 效傳遞就成為解決問題的關(guān)鍵。x m l 已逐漸成為數(shù)據(jù)庫與應(yīng)用程序之間和在多對 應(yīng)用程序之間進(jìn)行數(shù)據(jù)交換的技術(shù)標(biāo)準(zhǔn)，異構(gòu)數(shù)據(jù)源的集成是數(shù)據(jù)庫領(lǐng)域一直關(guān) 注的研究方向，過去主要是面向傳統(tǒng)的數(shù)據(jù)模型【1 2 ，1 3 ，14 1 ，近年來對l 數(shù)據(jù)源進(jìn) 行集成，成為新的研究熱點，出現(xiàn)了一些) ( 】l 數(shù)據(jù)的集成系統(tǒng)【1 5 ，1 6 ，1 7 ，1 引。 國內(nèi)外對于l 的數(shù)據(jù)共享與數(shù)據(jù)查詢技術(shù)的研究尚有些問題還有待解決， 因此，我們的課題研究圍繞這些方面展開，集中在以下幾點： 1 ) 基于x m l 結(jié)點編碼的研究； 2 ) 基于x m l 流數(shù)據(jù)查詢執(zhí)行器的增量更新的研究； 3 ) 基于l 的數(shù)據(jù)交換技術(shù)的研究。 1 3 論文的主要工作 在論文中我們首先介紹x m l 的相關(guān)概念及一些基本算法，然后對x m l 的數(shù)據(jù) 共享與數(shù)據(jù)查詢技術(shù)作了具體的介紹，在借鑒國內(nèi)外在x m l 的數(shù)據(jù)共享與數(shù)據(jù)查 8 揚州大學(xué)碩士學(xué)位論文 詢技術(shù)方面的已有成果的基礎(chǔ)上，本文提出了一種改進(jìn)的素數(shù)編碼方法 m b p r i m e 、基于樹型結(jié)構(gòu)的x m l 查詢增量維護(hù)算法t s q m ( t r e es 仃u c t u r ea b o u t q u e 巧m a i n t e n a c e ) 、以及基于x m l 技術(shù)的信息交換模型。 本文的主要研究工作及成果如下： 1 ) 本文在目前l(fā) 索引相關(guān)研究工作的基礎(chǔ)上，提出了一種改進(jìn)的素數(shù)編碼 方法m b p r i r n e ，該編碼方法在深度遍歷x m l 文檔時，為當(dāng)前節(jié)點的孩子分配 新素數(shù)，新的素數(shù)與待分配節(jié)點的上層節(jié)點( 層次比該節(jié)點小的所有節(jié)點) 和左 親兄弟分配的素數(shù)不同，即每一層中不同節(jié)點為孩子節(jié)點分配素數(shù)時，它們分配 的素數(shù)可以重復(fù)，減少了素數(shù)使用量，減少了所用的大素數(shù)，加快了查詢的速 度。 2 ) 本文在目前x m l 查詢、查詢的增量更新相關(guān)研究工作的基礎(chǔ)上，提出了算 法t s q m ，該算法是基于x m l 樹型結(jié)構(gòu)的動態(tài)維護(hù)，以增加少量的路徑轉(zhuǎn)換為代 價，避免了在沒有d t d 情況下出現(xiàn)的對環(huán)形結(jié)構(gòu)復(fù)雜操作，最后通過實驗分析， 說明算法t s q m 減少了維護(hù)的時間和狀態(tài)轉(zhuǎn)換的數(shù)量。 3 ) 本文最后結(jié)合重大環(huán)境污染事故危險源管理系統(tǒng)具體實現(xiàn)了) ( 】l 數(shù)據(jù)交 換。同時通過基于n e t 架構(gòu)的組件技術(shù)和l 技術(shù)完成了重大環(huán)境污染事故危 險源基礎(chǔ)數(shù)據(jù)信息集成，通過l 數(shù)據(jù)交換技術(shù)方便的實現(xiàn)危險源上報單位和各 級環(huán)保部門之間的數(shù)據(jù)上報和下達(dá)。通過基于w e b 方式的統(tǒng)一的重大環(huán)境污染事 故危險源數(shù)據(jù)庫數(shù)據(jù)申報平臺和監(jiān)控管理平臺，實現(xiàn)了危險品數(shù)據(jù)自動上報、分 類建庫。同時為各級環(huán)境保護(hù)機(jī)構(gòu)提供了區(qū)域重大環(huán)境污染事故危險源信息查詢 統(tǒng)計分析，及時對城市重大環(huán)境污染事故危險源和重大環(huán)境污染事故隱患進(jìn)行動 態(tài)監(jiān)控管理和分析，為快速、準(zhǔn)確制定環(huán)境污染事故應(yīng)急處理方案提供了科學(xué)依 據(jù)。 1 4 論文組織 以下章節(jié)內(nèi)容組織如下： 第二章主要介紹了x m l 的基本概念和一些基本算法。 第三章給出了一種改進(jìn)的x m l 素數(shù)編碼算法m b p r i m e 。 劉海東：基于瑚l 的數(shù)據(jù)共享與查詢技術(shù)及其應(yīng)用研究 9 第四章給出了一種基于樹型結(jié)構(gòu)的x 】l 數(shù)據(jù)流查詢執(zhí)行器的增量維護(hù)方法 t s q m 。 第五章給出了基于兒的數(shù)據(jù)交換技術(shù)研究與實現(xiàn)。 最后，第六章是論文的總結(jié)和研究工作的展望。 1 0 揚州大學(xué)碩士學(xué)位論文 第二章基本理論 本章主要介紹x m l 的一些基本概念，包括x m l 簡介、d t d 簡介、s c h e m a 簡介、x m l 查詢語言、x m l 索引的基本算法、x m l 的應(yīng)用程序接口等。 2 1x ，簡介 定義2 1 ( 訂l 文檔) x m l 文檔由三部分組成：l 聲明、文檔類型定義 和x m l 文檔主體。其中，一個x m l 文檔主體只能有一個根元素，它的內(nèi)容不能 嵌套在任何其他元素中。根元素內(nèi)部由一組嵌套元素序列組成，每個元素由一組 開始和結(jié)束標(biāo)簽對或是一個空標(biāo)簽界定。 定義2 2 ( x m l 文檔樹) 一個x m l 文檔可以表示成為一棵節(jié)點標(biāo)記樹t r e e = ( n ，e ，r o o t ，6 ) ，其中n 表示節(jié)點的集合，e 表示邊的集合，r o o t 表示根節(jié)點， 6 表示標(biāo)簽的有限集合。函數(shù)l a b e l ：n 一6 定義所有節(jié)點的標(biāo)簽。邊的集合是n 上的二元關(guān)系，每一對( u ，v ) e 建立n 中兩個節(jié)點之間的關(guān)系。如果( u ，v ) e ，則稱u 是v 的父親，v 是u 的孩子。如圖2 2 為圖2 1 s 鋤p l e x m l 所示l 文檔的樹型表示。 劉海東：基于l 的數(shù)據(jù)共享與查詢技術(shù)及其應(yīng)用研究 1 1 a l b l c 1 a 2 b ， c ， a 1 b 3 c 3c 4c 5c 6 圖2 1s a n l p l e x m l 圖2 2s 姍p l e x m l 對應(yīng)的x m l 樹 1 2揚州火學(xué)碩士學(xué)位論文 x m l ( e x t e n s i b l em a r k u pl a l l g u a g e ，可擴(kuò)展標(biāo)記語言) 是s g m l ( s t a n d a r d g e n e r a l i z e dm a r k u pl a i l g u a g e ，標(biāo)準(zhǔn)通用標(biāo)記語言) 的子集，x m l 目標(biāo)是允許普通 的s g m l 在w 曲上以目前h t m l ( h y p e rt e x tm 咖l a l l g u a g e ) 的方式被服務(wù)、接 收和處理。) ( i l 被設(shè)計成易于實現(xiàn)，并且可在s g m l 和h t m l 之間互操作。 ) a l 保留了s g m l 的一些特點，并克服了h t m l 的局限性。x m l 的主要特 點是： 。 1 ) x m l 支持w r e b 的各種不同的應(yīng)用，并使用了一種類屬的方法使其具有可 擴(kuò)展性。h t m l 則不支持，它需要借助使用用于鏈接h t m l 和應(yīng)用的腳本語言才 支持w - e b 的各種不同的應(yīng)用。 2 ) x m l 與s g m l 兼容，所以大多數(shù)s g m l 應(yīng)用可以向x m l 轉(zhuǎn)化。 3 ) 與h t m l 文檔一樣，x m l 文檔易于創(chuàng)建和閱讀。x m l 文檔內(nèi)容和結(jié)構(gòu)清 晰易懂，所以即使對非專業(yè)人員來說也易于閱讀和使用。 4 ) l 的設(shè)計嚴(yán)謹(jǐn)，所以x m l 中標(biāo)記的信息可以很容易地被計算機(jī)程序所 處理。 5 ) 訂l 標(biāo)準(zhǔn)定義精練，這就保證了其下載和處理的速度。 6 ) 訂l 是自描述的。x m l 不僅允許定義自己的一套標(biāo)記，而且這些標(biāo)記不 必局限于對于顯示格式的描述。x 1 l 允許根據(jù)各種不同的規(guī)則來制定標(biāo)記，比如 根據(jù)商業(yè)規(guī)則，根據(jù)數(shù)據(jù)描述，數(shù)據(jù)關(guān)系來制定標(biāo)記。x m l 實現(xiàn)了用定義它們自 己的標(biāo)記集來說明文檔內(nèi)容的功能，這些說明的精確度是實現(xiàn)者自己制定的。 7 ) x m l 支持對文檔內(nèi)容的驗證。x m l 文檔的結(jié)構(gòu)和內(nèi)容是由語法定義的。 文檔類型定義( d o c u m e n tt ) ，p ed e 觚t i o n ，d t d ) 就是這類語法的一種，還有訂l 模式。使用模式，可以方便地驗證文檔的有效性。 8 ) 支持高級搜索。因為可以知曉文檔內(nèi)容的結(jié)構(gòu)和含義( 根據(jù)它的語法規(guī) 則) ，所以很容易在l 文檔中進(jìn)行搜索。在n e m e t 上如果w r e b 頁是x i l 格式 的，則搜索會更高效，而且不僅可以搜索數(shù)據(jù)，還可以在搜索中加入與數(shù)據(jù)相關(guān) 的上下文信息，這樣就形成了更精確的搜索機(jī)制。 劉海東：基于x m l 的數(shù)據(jù)共享與查詢技術(shù)及其應(yīng)用研究1 3 2 2 瑚，文檔 下面先看一個x m l 文檔的實例，如例2 1 所示。 例2 1 訂l 文檔： 江蘇省單位基礎(chǔ)代碼以3 2 為前綴媚z 叫d q b m 1 ) x m l 聲明( ) i m ld e c i a r a t i o n ) 例2 1 中的x m l 文檔第l 行為x m l 聲明： 聲明指出x m l 的版本號為1 0 ；u t f 8 表示文檔所用的編碼為u t f 8 ，它是 i s o 所制訂的一種通用字符編碼，每個字符可用8 位4 8 位編碼。在聲明中還可 以指出該x m l 文檔是獨立的( 如例2 1 為一個獨立的x m l 文檔) ，還是引用其它的 文檔。 如果l 文檔不獨立，那么聲明要寫成如下形式： 注意這里的標(biāo)簽用” ”結(jié)束，稱之為處理指令。除了上面看到的 處理指令外，還可以在x m l 文檔中包含其它的處理指令，比如用來制訂x m l 文檔 樣式的樣式表等。 2 ) 元素( e l e m e n t ) 元素是x m l 文檔中最基本和最常用的語法成分。其基本結(jié)構(gòu)為 元素內(nèi)容姬l e m e n t n 鋤e 1 4 揚州大學(xué)碩士學(xué)位論文 x m l 元素標(biāo)簽的組成部分如表2 1 所示。 表2 1x m l 元素標(biāo)簽 符號含義示例 起始標(biāo)簽 標(biāo)簽結(jié)束 空元素標(biāo)簽 從表2 1 可以看出x m l 的標(biāo)簽不是預(yù)先定義好的，這點不同于h t m l 使用的 是固定標(biāo)簽集合。 注意起始標(biāo)簽與結(jié)束標(biāo)簽必須嚴(yán)格地按照嵌套規(guī)則匹配。下面的x m l 元素描 述是錯誤的： s i m p l e _ _ - e l e m e n 伊t l l i si saw r o n ge l e m e n ts 鋤p l e ，也可以寫成 ，這兩種形式是等價的。 3 ) 元素屬性 屬性是依附元素存在的。元素可以具有屬性，屬性是由屬性名和屬性值組 成，元素的每個屬性在元素的開始標(biāo)簽里。屬性值用單引號或雙引號括起來。例 如： 15 0 0 吲咖d e 艫 這里有2 個屬性：屬性s c h o o l 值為”y z u ”；屬性d 1 1 a m e 值為”計算機(jī)”。元素 內(nèi)容為1 5 0 0 ( 表示y z u 學(xué)校，計算機(jī)系有1 5 0 0 個學(xué)生) 。 元素屬性和子元素的關(guān)系。如例2 1 中d q b m 的子元素可以用屬性表示。 劉海東：基于刪l 的數(shù)據(jù)共享與查詢技術(shù)及其應(yīng)用研究 1 5 江蘇省 江蘇省單位基礎(chǔ)代碼以3 2 做前綴 但并不是所用情況，都可以用屬性代替子元素，它們之間至少有2 點差別： ( 1 ) 在同一元素中屬性不能重名，但其子元素可以重名；( 2 ) 屬性次序無關(guān)緊 要，而子元素按書寫次序排序。一般來說，凡是元素的組成部分適合用子元素表 示，凡表示元素性質(zhì)的內(nèi)容適合用屬性來表示；簡短的內(nèi)容宜使用屬性表示；嵌 套或較長內(nèi)容適合用子元素來表示。有些元素只有屬性，沒有內(nèi)容，稱為空元 素，這里稱為“空”的含義為元素內(nèi)容為空。如： 是一個空元素。該空元素可以簡寫為： 。在語法檢查 時，簡寫元素當(dāng)做非簡寫元素處理。 4 ) 引用( e n i 衄f e r e n c e s ) 在x m l 文檔中，支持重用文檔或者其它文檔的內(nèi)容?？梢詫⒅赜玫膬?nèi)容定義 為e n t i t ) r ，其格式為： 是l 的定義語句格式。 是一條定義e n t 時的語句。在引 用時，使用”& 引用名；”即可，像c 語言里調(diào)用函數(shù)一樣，使用函數(shù)名及相應(yīng)的參 數(shù)就可以實現(xiàn)對一段函數(shù)的調(diào)用。引用的內(nèi)容可以是任意內(nèi)容，如h t m l 文檔、 圖形、聲音、影視等。如果這些內(nèi)容包含x m l 中特定意義的符號，如開始結(jié)束標(biāo) 簽 ，引用號& 等。如果對引用內(nèi)容中出現(xiàn)的這類符號不加以處理，則會引起語 法的錯誤，或語義上的混淆。為此，引用內(nèi)容改寫成如下形式： c d a t a 段是一種用來包含文本的方法，它的內(nèi)部的所有內(nèi)容都會被l 解 析器忽略，所以任何符號都不會被認(rèn)為是標(biāo)記符。這樣e n t i t y 定義可以寫成： 5 ) 注釋( c o m m e n t s ) x m l 支持注釋。注釋可以作為元素的后裔出現(xiàn)，也可以作為文檔的項層結(jié)構(gòu) 出現(xiàn)在根元素的前面或后面。注釋格式如下： 1 6 揚州大學(xué)碩士學(xué)位論文 注釋僅供人閱讀，實際程序在處理x m l 文檔時不予處理，這點就像c + + 語言 里的注釋。注釋可以是任意內(nèi)容，但為了語義上的混淆，不能包含”- - 字符串。 如例2 1 中有段注釋，表示使用x m l s p y 編輯l 。 所有的x m l 文檔都應(yīng)該是良構(gòu)的，如例2 2 所示。良構(gòu)的x m l 文檔應(yīng)該是 這樣的：所有的構(gòu)造從語法上都是正確的；只有一個根元素；所有的起始標(biāo)記都 有與之相應(yīng)的終止標(biāo)記，或者使用空元素速記語法；所有的標(biāo)記都正確嵌套：每 個元素的所有屬性都是不重名的。 例2 2 一個良構(gòu)的x m l 文檔 2 5 2 5 0 叫c z l j l ， 2 1 0 0 5 叫w x w b m 一氧化碳 2 5 2 1 0 0 8 w x w b m 甲烷【液化的】 劉海東：基于x m l 的數(shù)據(jù)共享與查詢技術(shù)及其應(yīng)用研究 1 l o 2 3d t d 簡介 x m l 文檔本質(zhì)上是保存信息的結(jié)構(gòu)化載體。為了得到有效的x m l 文件，提 領(lǐng)x m l 的結(jié)構(gòu)信息，需要一種用來描述x m l 文檔中結(jié)構(gòu)信息的數(shù)據(jù)模型。這種 模型不單要建立x 池文檔中可以使用的x m l 詞匯表，還要定義x m l 文件中元 素的順序和元素的嵌套關(guān)系，并建立文檔數(shù)據(jù)的數(shù)據(jù)類型。解決方案之一是 d t d ( d o c 哪e mt y p ed e f i n i t i o n ，文檔類型定義) 。 例2 3d t d 實例 ? x m lv e r s i o n = ”1 0 ”e n c o d i n g = ”u t f 一8 ” ! d o c n 伊eh b z d x y g l 【 。 ! e l e n 淵th b z d x y g l ( d ，c ) ! e i ，e n 陀：n tb m ( 掙p c d a t a ) ! e l e n tm c ( 拌p c d a t a ) ! e l e i e n tb z ( 群p c d a t a ) ! e l e m e n tw x w m c 滯p c d i a t a p ! e l e 棚巳 n ts c l j l ( 拌p c d l a t a ) 1 8揚州大學(xué)碩士學(xué)位論文 從例2 3 可以看出，d t d 的基本格式為： 表示其中的內(nèi)容為文檔類型定義，其后方括號里的內(nèi)容是定 義的內(nèi)容。 2 - 3 1d t d 元素的定義 1 ) 元素的聲明 d t d 中使用的第一聲明中是元素聲明。其形式為： 其中，徹m e 是一個標(biāo)準(zhǔn)的訂l 標(biāo)記的名字。c o n t e n t 由以下兩種之一組成： 元素內(nèi)容類型 描述包含在本元素的子元素的順序和重復(fù)次數(shù)的內(nèi)容模型； 2 ) 元素內(nèi)容類型( e l e m e n tc o n t e n tm o d e l ) 元素內(nèi)容通常有五種情況：e m p t y 、a n y 、撐p c d a l a 、子元素和混合型。 2 3 2d t d 屬性定義 1 ) 屬性聲明 屬性聲明的語法如下： 其中1 y p e 是屬性的類型，最常用的類型是c d a t a ，d e f a u l l v a l u e 是屬性的 默認(rèn)值。 2 ) 屬性的類型 ( 1 ) c d a t a 屬性類型 這種類型的屬性值是文本串，用c d a t a 關(guān)鍵字進(jìn)行聲明，它與群p c d a t a 元 素聲明類似。如： ( 2 ) 枚舉屬性類型 劉海東：基丁) 硼。的數(shù)據(jù)共享與查詢技術(shù)及其應(yīng)用研究 這種類型的值為指定的文本串列表中的某一個文本串。聲明時使用括號把這 些文本串括起來，并用豎線分隔開。如： 在使用v a l u e 屬性時，其值只能是m 或f ，且默認(rèn)值為m ( 3 ) i d 屬性類型 i d 類型的屬性用于標(biāo)識文檔中的元素。i d 屬性的值必須是一個合法的x m l 標(biāo)識符，并且該值在文檔中必須是唯一的。同時，每個元素最多只能有一個i d 類 型的屬性。如： 它為d q b m 元素定義了i d 類型的屬性w x w b m ，其屬性值可以唯一地標(biāo)識 每個d q b m 元素。 ( 4 ) i d i 也m d r e f s 類型 i d r e f 類型的屬性用來引用同一個文檔中的另一元素的i d 屬性。i d i 冱f 屬 性的值必須是文檔中某個元素的i d 屬性值。通過使用i d r e f ，可以使一個元素和 另一個元素發(fā)生聯(lián)系，如例2 4 所示。 例2 4i d r e f i d i 砸f s 類型使用實例 ! d ( ) c t y p eh b z d x y g l 【 ， ! e l e h 誣n tb m ( 群p c d a t a ) ! e l e m e n tb z ( 撐p c d a t a ) 2 0 揚州大學(xué)碩士學(xué)位論文 ! e l e 棚e n ts c l j l ( 樣p c d a t a ) d w x x 元素的d w b m ，w x w b m 屬性分別引用d q b m ，c d w x y l 兒元素 的i d 屬性。關(guān)于d t d 的詳細(xì)介紹，可以參考文獻(xiàn)【1 9 ，2 0 1 。 2 4x ，模式 d t d 是l 從s g m l 繼承而來。s g m l 是為描述文檔( 例如書籍、宣傳資 料、網(wǎng)頁等) 而設(shè)計的，d t d 用來滿足這類文檔的需要，已經(jīng)做得很好。但是 ) ( i l 超過了s g m l 的使用范圍，x m l 可用于股票交易、遠(yuǎn)程調(diào)用、圖形文件格 式以及很多看上去與傳統(tǒng)的描述性無關(guān)的應(yīng)用，在這些新的應(yīng)用領(lǐng)域中，d t d 就 顯示出局限性。 d t d 主要有以下幾個缺點： 1 ) d t d 幾乎完全沒有數(shù)據(jù)定義，特別是對元素的內(nèi)容而言。d t d 中，一切 都基于字符串，在計算機(jī)與計算機(jī)之間進(jìn)行信息交換時，涉及到數(shù)據(jù)格式 是常見的事，因此，d t d 就顯得不足。 2 ) d t d 的本身定義不符合l 語法，即處理d t d 和x m l 文檔需要兩種 不同的規(guī)則。例如： 。從前面x i l 元素的定義可知，這不是個合法的訂l 元素，這就給處理上帶來麻煩， 如果x m l 本身比較健全，那么它就應(yīng)該能夠描述自身，不需要另外一種 語法來描述有關(guān)信息結(jié)構(gòu)的元信息。 3 ) d t d 只能有限地進(jìn)行擴(kuò)展。 劉海東：基于潮l 的數(shù)據(jù)共享與查詢技術(shù)及其應(yīng)用研究 2 1 4 ) d t d 的約束定義能力不足，無法對x m l 實例文檔做出細(xì)致的語法限制。 5 ) d t d 不支持命名空間，無法檢查標(biāo)記的合法性。， 而x m l 模式( x 1 ls c h e m a ) 正是試圖解決這些問題。模式的功能有： ( 1 ) 豐富的數(shù)據(jù)類型； ( 2 ) 基于命名空間的u 的有效性驗證； ( 3 ) 可擴(kuò)展性和可伸縮性； ( 4 ) 可重用性 訌l 模式是一個文本文件，它獨立于l 文檔。模式文件以x s d 為文件擴(kuò) 展名。 ? ) ( i i l lv e r s i o n _ 1 0 ”e n c o d i n g - u t f - 8 ” x s d ：s c h e m ax m l n s ：x s d = h t t p ：力r w w ，3 o r g 2 0 0 l = i 【m l s c h e m a e l e m e n t f 0 m d e f a u l 仁”q 岫l i 6 e d f a j c t r i b u t e f o 肌d e f a u l 仁”咖q 嘲l(fā) m e d 脅 在x m