東北大學 碩士學位論文 XML復雜路徑表達式查詢處理技術研究 姓名 周博 申請學位級別 碩士 專業 計算機軟件與理論 指導教師 于戈 20031201 查 墜 翌主蘭堡壘墨 塑墨 齜復雜路徑表達式查淘處理技術研究 摘要 X M L 是可擴展標記語言 E x t e n s i b l e M a r k u pL a n g u a g e 的簡稱 它為W e b j 半結構化文檔和數據提供了通用格式 X M L 是一種元語言 通過對一組標簽設定 特定的意義 可以創建出其它的標記語言 隨著I n t e r a c t 的發展尤其是W e b 技術的 廣泛應用 越來越多的應用采用了X M L 技術作為信息表示和數據交換的標準 這 使得通過數據庫技術對X M L 數據進行存儲 查詢等操作變得越來越重要 在眾多X M L 查詢語言中 路徑查詢是最重要 使用最頻繁的組成部分 目前 提出的大多數查詢方法都是在實例空間中進行的 也就是說 使用這些方法查詢 時 直接面對的操作對象是X M L 文檔 這類方法中比較有代表性的是X M L 文檔 樹遍歷的方法和包含連接的方法 根據自動機技術 我們提出了一種通過用查詢 自動機匹配X M L 模式樹來計算查詢路徑表達式的方法 稱為自動機匹配算法 A u t o m a t aM a t c h A M 來解決X M L 正則路徑和復雜路徑查詢表達式的策略 自 動機匹配算法可以在模式空間內高效地計算路徑表達式 因此這種方法可以適應 在海量數據上執行復雜查詢的需要 本文提出了如何將具有各種運算符的正則表達式轉化為查詢自動機的方法 針對X P a t h 規范中規定的 操作符 即祖先一后代關系操作符 我們提出了一 個稱為模式自動機 S c h e m aA u t o m a t a 的數據結構 模式自動機可以接收所有可能 出現在X M L 文檔中的片斷 也就是說 它可以匹配任何可能出現在X M L 文檔中 的路徑模式 而傳統的自動機要想支持包含連接這一類非正則運算符是非常困難 的 為了進一步提高模式自動機的性能 本文還提出了兩種優化方法P S A 和R W S 前者將模式自動機作為索引的一部分存儲在磁盤上 避免了每次計算都要生成模 式自動機的開銷 后者則是通過f o l l o w i n g 集合和p r e c e d i n g 集合來過濾掉模式自動 機中多余的狀態和轉換函數來達到提高查詢效率的目的 為了支持自動機匹配算 法 本文還提出了高效地支持自動機匹配算法的數據結構 路徑模式樹和路徑實 例樹 通過與結構連接算法進行性能測試對比 我們發現自動機匹配算法的效率 遠遠高于結構連接算法 P S A 和R W S 對自動機匹配算法的優化也很顯著 與傳統的關系數據庫中的查詢不同 針對半結構化數據的查詢更多的是要找 到滿足某些特定模式的節點 近來 在簡單路徑查詢的問題得到較好解決的基礎 上 人們將注意力轉移到T w i g 查詢中來 本文提出了如何利用索引技術來更好地 解決T w i g 查詢的問題 根據路徑模式樹索引 我們給出了利用自動機匹配路徑模 式樹索引解決這一問題的方法 圍繞這一方法 本文對T w i g 查詢自動機的構建 I l 東北大學碩士學位論文 摘要 T w i g 查詢自動機與路徑模式樹的匹配等算法進行了討論 并與用傳統的結構連接 方法解決T w i g 查詢進行了實驗對比 結果證明 基于自動機的方法在性能上具有 較大優勢 關鍵詞 可擴展標記語言 自動機 模式自動機 路徑表達式查詢 T w i g 查詢 I I I 東北大學碩士學位論文 A B S T L 4 C T S t u d y o nX M L Q u e r yP r o c e s s i n gT e c h n i q u e so f C o m p l e x P a t hE x p r e s s i o n s A b s t r a c t X M I E x t e n s i b l eM a r k u pL a n g u a g e p r o v i d e sg e n e r a l f o r m a tf o r s e m i s t r u c t u r e dd o c u m e n t sa n dd a t ao nt h eW e b I ti sas i m p l ea n df l e x i b l e f o r m a ta n dw a s o r i g i n a l l yd e s i g n e d f o re l e c t r o n i c p u b l i s h i n g N o w a d a y s X M L p l a y sm o r ea n dm o r ei m p o r t a n tr o l ei nW e bb a s e da p p l i c a t i o n s I nX M L t a g s a r eu s e dt od e s c r i b et h es t r u c t u r ei n f o r m a t i o n so fd o c u m e n t s X M Li s w i d e l yu s e da s as t a n d a r dl a n g u a g ef o rr e p r e s e n t i n ga n de x c h a n g i n gd a t ai n W e bs i t e c o n s t r u c t i o n d i s t r i b u t e da p p l i c a t i o np l a t f o r m sa n do t h e rs y s t e m s T h e r e f o r e i tb e c o m e sm o r ea n dm o r ei m p o r t a n tt om a n a g eX M L d a t at h r o u g h d a t a b a s e s R e c e n t l yal o to f r e s e a r c hw o r kh a sb e e nd o n ef o rm a n a g i n gX M L d a t a P a t hq u e r yi so n eo ft h em o s tf r e q u e n t l yu s e dc o m p o n e n t sb yt h ev a r i o u s X M L q u e r yl a n g u a g e s M o s to f t h ep r o p o s e dm e t h o d sc o m p u t ep a t hq u e r i e si n i n s t a n c es p a c e s i e t h eX M Ld a t a s u c ha sX M L t r e et r a v e r s a la n dc o n t a i n m e n t jo i nw a y s A saq u e r ym e t h o db a s e do na u t o m a t at e c h n i q u e A u t o m a t a M a t c h i n gf A M lc a n e v a l u a t ep a t he x p r e s s i o nq u e r i e si ns c h e m as p a c es ot h a ti t a l l o w se f f i c i e n tc o m p u t a t i o no fc o m p l e xq u e r i e so nm a s s i v eX M L d a t a T h i st h e s i sf i r s ti n t r o d u c e sh o wt oc o n s t r u c tq u e r ya u t o m a t ai no r d e rt o e v a l u a t ev a r i o u sr e g u l a re x p r e s s i o nq u e r i e si n c l u d i n gt h o s ew i t hw i l d c a r d s F u r t h e r m o r e ad a t as t r u c t u r en a m e d s c h e m aa u t o m a t ai sp r o p o s e dt oe v a l u a t e c o n t a i n m e n tq u e r i e st h a ta r ev e r yd i m c u l tt oh a n d l ef r o mt h ec o n v e n t i o n a l a u t o m a t ap o i n to fv i e w T oi m p r o v et h ee f f i c i e n c yo fs c h e m aa u t o m a t a w e p r o p o s e dt w oo p t i m i z a t i o ns t r a t e g i e s P S Aa n dR W A F o rP S A w e s t o r et h e s c h e m aa u t o m a t ao nt h ed i s ka sap a r to ft h ei n d e x T h es c h e m a a u t o m a t an e e d n o tt ob ec o n s t r u c t e dd y n a m i c a l l ye v e r yt i m e w h i c ht h e r e b y r e d u c e st h e r e s p o n s et i m e W i t hr e s p e c t t oR W A w er e d u c et h es c h e m aa u t o m a t ab y f i l t e r i n g t h eu s e l e s ss t a t u s e sa n dt h et r a n s f o r mf u n c t i o n sa c c o r d i n gt o t h e f o l l o w i n gs e ta n dt h ep r e c e d i n gs e t I n t h i st h e s i s t w od a t as t r u c t u r e s p a t h i n s t a r t c eI r e ea n dp a t hs c h e m at r e e w e r ep r o p o s e dt os u p p o r tt h e a u t o m a t a m a t c h a l g o r i t h me f f i c i e n t l y T h e e x p e r i m e n t a l r e s u l t ss h o wt h a tt h eA M D e r f o r m sm u c hb e t t e rt h a nt h e c o n t a i n m e n tj o i n a n dP S Aa n dR W Sa r e 東北大學碩士學位論文 A B S T R A C l w H H H 一 H M H e f f e c t i v eo p t i m i z a t i o u so nA M D i f f e r e n tf r o mt h ec o n v e n t i o n a l q u e r i e s i nR D B M S X M L q u e r i e s t y p i c a l l ys p e c i f yt w i gp a t t e r n so fs e l e c t i o np r e d i c a t e so i lm u l t p l ee l e m e n t s t h a th a v es o m es p e c i f i e ds t r u c t u r a l r e l a t i o n s h i p s F i n d i n ga l l o c c u r r e n c e so f s u c hat w i gp a t t e r ni na nX M I d a t a b a s ei sac o r eo p e r a t i o nf o rX M L q u e r y p r o c e s s i n g At w i gq u e r yc a nb et r a n s f o r m e dt oa na u t o m a t o n P e r f o r m a n c eo f c o n v e n t i o n a le v a l u a t i o n a p p r o a c h e s b a s e do ns t r u c t u r a l j o i n s d e c l i n e sa s i n c r e a s i n go fd a t aa n dq u e r yc o m p l e x i t y I nt h i st h e s i s an o v e la p p r o a c hi s p r o p o s e dt oc o m p u t et w i gq u e r i e sb ym a t c h i n gt w i gq u e r ya u t o m a t aa n dp a t h s c h e m at r e e s M o r e o v e r w eg i v et h ep e r f o r m a n c ee v a l u a t i o nt od e m o n s t r a t e 1 t h eh i g hp e r f o r m a n c eo fo u rm e t h o d s K e yw o r d s X M L A u t o m a t a S c h e m aA u t o m a t a P a t hE x p r e s s i o nQ u e r y T w i g Q u e r y v 聲明 本人聲明所呈交的學位論文是在導師的指導下完成的 論 文中取得的研究成果除加以標注和致謝的地方外 不包含其他 人已經發表或撰寫過的研究成果 也不包括本人為獲得其他學 位而使用過的材料 與我一同工作的同志對本研究所做的任何 貢獻均已在論文中作了明確的說明并表示謝意 本人簽名 f 虱丁考 日 表弛走學碩士學位論文 第一章蔻言 第一章前言 睫蕾W e b 技術的飛速發展 基于嘲絡技術的應用領域舅瀕增多 網絡信息爨 也變褥越來越大 目前主要用于表示W e b 文檔和數據的H T M L 語言著重于數據的 外部表現形式 兩不是內部的數據結構 已經不能滿足W e b 上信息表示和數據交 換的要求 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 是一種簡單酶 自描述的 內容 與表現栩分離的語言 已經被大家廣泛接受作為W e b 上信息表示與數據交換的新 標準 隨著M i c r o s o f t 在箕 N E T 體系中全蟊使蘑X M L 佟為英各灝 幸蠲信惑載體 以及O r a c l e I B MD B 2 等大型商業數據庫產品紛紛將 地的存儲和查詢功能納入 箕核心部分 越窳越多瓣璃菇鼓及W e b 虛爰霞鵝TX M L 送行售意豹發東 W e b 上用X M L 表示的數據越來越多 X M L 已經成為目前W c b 上最蹙矚目以及被認為 跫援其笈震蓑最麴技術 然恧 瞧于X M L 鶼半結構化特性 饅褥簧統熊數據管耀 技術不能完全滿足對X M L 數據的存儲以及查詢管理的需要 因此 研究針對X M L 數據豹數據庫管理技術勢在必行 旦翦 X M L 數據庫的主要工作集中在查詢處理 及優化技術 知路徑表達式查詢優化技術 T w i g 查詢優化技術 包含連接查詢技 術研究 X M L 索引技術等 但是由于X M L 具肖十分復雜的半結構化特性 目黼 的研究成果還不能完全支持X M L 標準凌詢語言X Q u e r y 因虼在世界蒗圍肉 無 論是學術界還懸工業界 對X M L 查詢處理和優化技術都正在進行更加深入的研 究 1 1X M L 相關技術 1 1 1 一個X M L 數據實例 q x 攥lv e r s i o B 1 0 s t a n d a l o n e n o D O C T Y P Es i t eS Y S T E M s a m p l e d t d A c t A c ti nP r o l o g u e S t a r tt h ea c t 妮l n e S 鞋 e h A c l A c ti nE p i l o g u e F i n i s h t h ea c t1 燙l X M L 實鍘文梢 F i g u r e1 1X M Ls a m p l ed o c u m e n t 東北大學碩士學位論文第一章前言 鶩 1 怒一令X M L 文樓實翻 文禚靜蘩一雩亍是一令X M L 聲疆 繪鲞了X M L 文檔采用的X M L 版本號 怒否和外部D T D 配合使用 以及數據歷采用的編碼方 式等信塞 文檔熬籬2 雩亍據瞧了當曼示該X M L 文檔瓣獲應搜蠲的撐蔑文饞 文擋 第3 行是文檔的外部D T D 使用說明 從第4 行起是文檔所表示的數據 X M L 通 過元素寒韁織X M L 數提 元素是X M L 文摟內容鮑基本單元 X 1 W L 元素包攝標 記和字符數據 從譖法角度上看 一個元素包含了 個起始標記 一個結束標記 以及標記之闥的數據皮容 X M L 中宥元素 屬性 文本等幾攤基本的數據類型 因為本文主瓣探討X M L 文檔路徑查詢 因此我們主臻研究這幾種數據類型 每個 X M L 文檔有且僅有一個根元素 圖1 1 中的根元素的標簽為A c t 它有兩個子元 素 其標簽分剮是P r o l o g u e 鞠E p i l o g u e j 1 l 2D 0 搬模型及D O M 標準 圖1 2 怒與圖1 1 中的X M L 文檔相對應的D O M 樹 D O M 模型以有層次的結 點霹象耱款形式來襲疆文檔 這些蘩患中鴦熬可滋霄孩子結點 有懿只戇 擘雋時 子結點存在 通過用圖形表示的D O M 樹 我們可以很清楚地了解X M L 文檔的數 輾之闖戇縫穩 建繁籬頭數線段表示實倒之闕鮑實辯的父予關系或滋元素與屬性 之間的關系 圖形中的數字代表這一縮點實例的唯一標識 O b j e c t I D 如果D O M 鍵在內存中實理 它霹能是結點款擺針或旬援 如聚D O M 被持久他在數據庫中 它可能是記錄的主鑣或者對漿的I D 符號下面的字符串標明了元素結點或滿性結 點的名字 如標記為 9 的結點就對應于魏睡示例文檔中 A c t i nP r o l o g u e 這段 文本 它是A c t 元索 編號為5 節點的子節點 D O M D o c u m e mO b j e c tM o d e l 是W 3 C 報薦的 組應用于X M L 和H T M L 的編 程接口 D O M 定義了文檔靜邏輯結構以及文檔靜誘滔幫修瀲方法 警X M L 文擋 以D O M 的方式呈現時 可以被看作數據而不單純是文件 D O M 規范為程序開發 圖1 2 示例文檔的D O M 樹 F i g u r e 2 D O M t r e e o f s a m p l e d o c u m e n t 一 魚w 芝一 一 土 尚一一 瓣 一 查 查堂翌主堂堡笙查 莖二主墮童 者提供了一系列的應用程序接口的描述 通過D O M 程序開發者可以創建 個 X M L 文檔 按文檔的結構進行遍歷 增加 刪除或修改X M L 文檔中的元素和內 容 W 3 C 在制定D O M 接口時即要求該標準具有平臺無關性 使它能夠在任何平 臺上以任何語言實現 所以D O M 標準使用O M GI D L 編寫 D O M 標準定義的所 有的A P I 都是接口 i n t e r f a c e s 定義而不是類 c l a s s 定義 這意味著標準的任 何實現都只需要按照名字和定義好的操作來實現該方法 1 1 3D T D 簡介 圖1 3 給出了 個與圖 1 中的X M L 文檔對應的D T D 圖 仍蕊卜 設計并實現了支持自動機匹配方法所需的索引結構和其它相關數據結構 而且設計并實現了新的利用鍵樹來匹配自動機的算法 擴展了自動機的功能 同時提出了自動機匹配算法中路徑表達式 謂詞問題的計算方法和優化方法 該文最后給出了自動機匹配算法與其它兩種查詢算法在查詢性能上的比較并加以簡要分析 5 學位論文 柳娜 統一資源管理系統中查詢組件的設計與實現 2006 為了能有效地進行資源共享和交換 提高資源建設的效率和水平 本文提出了統一資源庫的概念一一即建立一個統一的資源平臺 通過資源類型注冊機制 對各種不同標準類型的資源提供統一的存取 檢索和管理 由于統一資源管理平臺數據量大 實時操作頻繁 數據類型多樣化 因此本文采用了目前比較先進的XML ExtensibleMarkupLanguage 可擴展標記語言 半結構化數據庫模型來進行數據庫的管理 對于其中的數據查詢功能利用XML文檔查詢技術來實現 通過對國內外XML文檔查詢算法的分析發現 大多數算法的實現是把被查詢文檔全部載入內存之后再進行處理 因此要消耗大量內存 尤其是在XML文檔很大以致無法全部載入內存的情況下 這些算法就無能為力了 針對這一問題 本文在統一資源管理平臺查詢組件中設計并實現了一種新的查詢算法 該算法的設計思路是 首先根據XPath查詢表達式 生成一個查詢自動機 并將查詢條件隱含在查詢自動機的結構和狀態中 然后通過SAX SimpleAPIsforXML XML簡單應用程序接口 解析程序將XML文本數據流轉化為SAX事件流 并將這些事件作為查詢自動機的輸入 來觸 發查詢自動機的狀態轉換 查詢自動機依據不同的輸入事件 在各個狀態之間進行轉換 一旦確認某一部分文檔完全匹配查詢表達式 查詢引擎程序就輸出查詢結果 文中詳細地介紹了由查詢表達式構造查詢自動機的步驟 實現了一個基于流的XML文檔查詢系統的原型 它可以在對XML流的一次單向讀取過程中處理XPath 輸出查詢結果 文中還對基于內存的XML查詢算法和基于流的XML查詢算法進行測試 比較 并對結果進行了分析 基于流的XML查詢算法是為了滿足一些數據密集型應用對數據查詢處理的需求而引入的 這類應用處理的數據不宜用持久穩定的關系建模 而應采用數據流建模 這類應用的領域包括金融服務 網絡監控 電信數據管理 生產制造 傳感檢測等 本論文的研究對這類實際應用將具有一定的理論意義和使用價值 6 會議論文 呂建華 周巍 孫冰 王國仁 于戈 XML查詢中RPE索引技術研究 2001 本文針對正則路徑達表達式的特點提出了一個基于自動機的正則路徑表達式索引方法 它把正則路徑表達式轉換成自動機 利用其相似性準確而有效地索引正則路徑表達式 從而提高正則路徑表達式的查詢處理效率 7 學位論文 許翼 XML樹模式查詢研究 2008 XML是可擴展標記語言的簡稱 為Web上半結構化文檔和數據提供了通用格式 隨著Internet的發展尤其是Web技術的廣泛應用 越來越多的應用采用了XML技術作為信息表示和數據交換的標準 這使得通過數據庫技術對XML數據進行存儲 查詢等操作變得越來越重要 由于XML文檔可看作樹型 對XML的查詢可以看成是基于值謂詞的子樹Twig匹配 也就是從 XML文檔找到和給定查詢條件相匹配的子樹 因此能夠高效找到子樹匹配成為XML中的一個核心問題 本文在介紹了XML查詢的研究現狀和研究成果的基礎上 針對Twig Stack算法在多層嵌套的XML文檔下性能不高的情況 提出了改進算法Nest Twig 并證明行之有效 Nest Twig算法和Twig Stack算法都是基于分解 匹配 合并的步驟來進行查詢匹配處理 容易產生大量無用的中間結果或者會對一些子模式樹進行重復匹配 為了解決這個問題 本文引入自 動機思想 對Twig查詢自動機與路徑模式樹的匹配進行了討論 提出了改進算法Pattern Match 對Pattern Match算法和Nest Twig算法進行了實驗對比證明基于自動機的方法在性能上具有較大優勢 8 期刊論文 方峻 劉長毅 徐誠 槍械方案設計系統中的基于實例推理框架研究 兵工學報2003 24 1 本文提出了一種基于實例推理 CBR 的面向對象框架原型 闡述了其結構組成和實現形式 研究了其在構建槍械方案設計系統中的應用 同時建立了基于可擴展標記語言 XML 的實例表達形式和一套面向對象的實例推理模型 在此基礎上開發了一套槍械自動機方案設計原型系統 并以一個設計實例對系統進行了驗證 9 學位論文 包小源 壓縮XML的索引與查詢方法研究 2005 XML由于為其中所保存內容的每個語義單元引入一個標記而使整個文件的內容迅速膨脹 這種情況下 在對數量龐大的XML數據進行管理時 進行壓縮就成為一種有效的基本解決方法 其實 XML作為一種數據交換標準 由于其頻繁在網絡上進行傳輸 為了節省寶貴的網絡資源 壓縮將是一種必然的選擇 對壓縮數據進行查詢的基本方法是首先解壓縮 然后再實施查詢 這種方法在數據量小的情形下尚可 對于所管理數據量龐大的情形下 如IR中的海量數據管理 大規模企業的海量XML客戶個性化數據等 每次查詢需要事先解壓縮所帶來的性能下降是無法承受的 于是 直接基于壓縮數據進行索引 查詢等就變得非常重要而且必要 這一點對壓縮XML數據 是同樣適用的 但目前已有的壓縮方法大多沒有兼顧結構保持 解壓縮效率 以及壓縮比等三個方面的要求 不能支持直接基于壓縮的查詢 同時 基于壓縮的XML索引 查詢 包括靜態 流兩方面的查詢 很少 而已有研究不能直接 或者根本不能應用于壓縮數據的索引和查詢 圍繞上述問題 本文提出了XML結構保持壓縮方法 基于壓縮的XML索引方法 基于壓縮XML靜態數據以及壓縮XML流的查詢及分發方法 主要的創新性成果包括 1 提出了基于Byte Huffman的XML結構保持壓縮思想和方法 目前已有的XML結構保持壓縮方法基本上自成系統 無法有效與其他應用系統集成 且其實現復雜 還有很重要的一點 在網絡環境下 對壓縮和解壓縮的速度要求是同等重要的 但目前的壓縮方法 無論是非結構保持壓縮或是結構保持壓縮 因主要集中于實際應用中XML傳輸及存儲效率的提高 從而對解壓縮的效率不夠重視 經過我們對現有的實驗系統測 試 其解壓縮的速度一般都很慢 本文提出了一種支持查詢的XML壓縮方法 QueXComp QuerableXMLCompression 它以XByteHuff為基本壓縮編碼方法 通過保留以 及 等定義的XML結構 以Word為基本壓縮統計單位對元素的Tag及元素值實施壓縮 可實現高效率的壓縮和解壓縮 為了能實現從壓縮XML數據中任意位置開始的查詢及解壓縮 我們對ByteHuffman編碼進行了改進 保留其MSB作為標志位以指示一個Word的開始 形成了XbyteHuff 同時 為了實現基于壓縮的高效查詢 我們提出了字典索引結構P Tries 并提出了基于ByteHuffman樹中附加Mark域信息以支持所提出的基于NFA 非有限自動機 的壓縮XML內容查詢 2 提出了基于壓縮的XML結構索引S