碩士論文-_ML復(fù)雜路徑表達(dá)式查詢處理技術(shù)研究.pdf

東北大學(xué) 碩士學(xué)位論文 XML復(fù)雜路徑表達(dá)式查詢處理技術(shù)研究 姓名 周博 申請(qǐng)學(xué)位級(jí)別 碩士 專業(yè) 計(jì)算機(jī)軟件與理論 指導(dǎo)教師 于戈 20031201 查 墜 翌主蘭堡壘墨 塑墨 齜復(fù)雜路徑表達(dá)式查淘處理技術(shù)研究 摘要 X M L 是可擴(kuò)展標(biāo)記語(yǔ)言 E x t e n s i b l e M a r k u pL a n g u a g e 的簡(jiǎn)稱 它為W e b j 半結(jié)構(gòu)化文檔和數(shù)據(jù)提供了通用格式 X M L 是一種元語(yǔ)言 通過(guò)對(duì)一組標(biāo)簽設(shè)定 特定的意義 可以創(chuàng)建出其它的標(biāo)記語(yǔ)言 隨著I n t e r a c t 的發(fā)展尤其是W e b 技術(shù)的 廣泛應(yīng)用 越來(lái)越多的應(yīng)用采用了X M L 技術(shù)作為信息表示和數(shù)據(jù)交換的標(biāo)準(zhǔn) 這 使得通過(guò)數(shù)據(jù)庫(kù)技術(shù)對(duì)X M L 數(shù)據(jù)進(jìn)行存儲(chǔ) 查詢等操作變得越來(lái)越重要 在眾多X M L 查詢語(yǔ)言中 路徑查詢是最重要 使用最頻繁的組成部分 目前 提出的大多數(shù)查詢方法都是在實(shí)例空間中進(jìn)行的 也就是說(shuō) 使用這些方法查詢 時(shí) 直接面對(duì)的操作對(duì)象是X M L 文檔 這類方法中比較有代表性的是X M L 文檔 樹(shù)遍歷的方法和包含連接的方法 根據(jù)自動(dòng)機(jī)技術(shù) 我們提出了一種通過(guò)用查詢 自動(dòng)機(jī)匹配X M L 模式樹(shù)來(lái)計(jì)算查詢路徑表達(dá)式的方法 稱為自動(dòng)機(jī)匹配算法 A u t o m a t aM a t c h A M 來(lái)解決X M L 正則路徑和復(fù)雜路徑查詢表達(dá)式的策略 自 動(dòng)機(jī)匹配算法可以在模式空間內(nèi)高效地計(jì)算路徑表達(dá)式 因此這種方法可以適應(yīng) 在海量數(shù)據(jù)上執(zhí)行復(fù)雜查詢的需要 本文提出了如何將具有各種運(yùn)算符的正則表達(dá)式轉(zhuǎn)化為查詢自動(dòng)機(jī)的方法 針對(duì)X P a t h 規(guī)范中規(guī)定的 操作符 即祖先一后代關(guān)系操作符 我們提出了一 個(gè)稱為模式自動(dòng)機(jī) S c h e m aA u t o m a t a 的數(shù)據(jù)結(jié)構(gòu) 模式自動(dòng)機(jī)可以接收所有可能 出現(xiàn)在X M L 文檔中的片斷 也就是說(shuō) 它可以匹配任何可能出現(xiàn)在X M L 文檔中 的路徑模式 而傳統(tǒng)的自動(dòng)機(jī)要想支持包含連接這一類非正則運(yùn)算符是非常困難 的 為了進(jìn)一步提高模式自動(dòng)機(jī)的性能 本文還提出了兩種優(yōu)化方法P S A 和R W S 前者將模式自動(dòng)機(jī)作為索引的一部分存儲(chǔ)在磁盤(pán)上 避免了每次計(jì)算都要生成模 式自動(dòng)機(jī)的開(kāi)銷 后者則是通過(guò)f o l l o w i n g 集合和p r e c e d i n g 集合來(lái)過(guò)濾掉模式自動(dòng) 機(jī)中多余的狀態(tài)和轉(zhuǎn)換函數(shù)來(lái)達(dá)到提高查詢效率的目的 為了支持自動(dòng)機(jī)匹配算 法 本文還提出了高效地支持自動(dòng)機(jī)匹配算法的數(shù)據(jù)結(jié)構(gòu) 路徑模式樹(shù)和路徑實(shí) 例樹(shù) 通過(guò)與結(jié)構(gòu)連接算法進(jìn)行性能測(cè)試對(duì)比 我們發(fā)現(xiàn)自動(dòng)機(jī)匹配算法的效率 遠(yuǎn)遠(yuǎn)高于結(jié)構(gòu)連接算法 P S A 和R W S 對(duì)自動(dòng)機(jī)匹配算法的優(yōu)化也很顯著 與傳統(tǒng)的關(guān)系數(shù)據(jù)庫(kù)中的查詢不同 針對(duì)半結(jié)構(gòu)化數(shù)據(jù)的查詢更多的是要找 到滿足某些特定模式的節(jié)點(diǎn) 近來(lái) 在簡(jiǎn)單路徑查詢的問(wèn)題得到較好解決的基礎(chǔ) 上 人們將注意力轉(zhuǎn)移到T w i g 查詢中來(lái) 本文提出了如何利用索引技術(shù)來(lái)更好地 解決T w i g 查詢的問(wèn)題 根據(jù)路徑模式樹(shù)索引 我們給出了利用自動(dòng)機(jī)匹配路徑模 式樹(shù)索引解決這一問(wèn)題的方法 圍繞這一方法 本文對(duì)T w i g 查詢自動(dòng)機(jī)的構(gòu)建 I l 東北大學(xué)碩士學(xué)位論文 摘要 T w i g 查詢自動(dòng)機(jī)與路徑模式樹(shù)的匹配等算法進(jìn)行了討論 并與用傳統(tǒng)的結(jié)構(gòu)連接 方法解決T w i g 查詢進(jìn)行了實(shí)驗(yàn)對(duì)比 結(jié)果證明 基于自動(dòng)機(jī)的方法在性能上具有 較大優(yōu)勢(shì) 關(guān)鍵詞 可擴(kuò)展標(biāo)記語(yǔ)言 自動(dòng)機(jī) 模式自動(dòng)機(jī) 路徑表達(dá)式查詢 T w i g 查詢 I I I 東北大學(xué)碩士學(xué)位論文 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 東北大學(xué)碩士學(xué)位論文 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 聲明 本人聲明所呈交的學(xué)位論文是在導(dǎo)師的指導(dǎo)下完成的 論 文中取得的研究成果除加以標(biāo)注和致謝的地方外 不包含其他 人已經(jīng)發(fā)表或撰寫(xiě)過(guò)的研究成果 也不包括本人為獲得其他學(xué) 位而使用過(guò)的材料 與我一同工作的同志對(duì)本研究所做的任何 貢獻(xiàn)均已在論文中作了明確的說(shuō)明并表示謝意 本人簽名 f 虱丁考 日 表弛走學(xué)碩士學(xué)位論文 第一章蔻言 第一章前言 睫蕾W e b 技術(shù)的飛速發(fā)展 基于嘲絡(luò)技術(shù)的應(yīng)用領(lǐng)域舅瀕增多 網(wǎng)絡(luò)信息爨 也變?nèi)煸絹?lái)越大 目前主要用于表示W(wǎng) e b 文檔和數(shù)據(jù)的H T M L 語(yǔ)言著重于數(shù)據(jù)的 外部表現(xiàn)形式 兩不是內(nèi)部的數(shù)據(jù)結(jié)構(gòu) 已經(jīng)不能滿足W e b 上信息表示和數(shù)據(jù)交 換的要求 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 是一種簡(jiǎn)單酶 自描述的 內(nèi)容 與表現(xiàn)栩分離的語(yǔ)言 已經(jīng)被大家廣泛接受作為W e b 上信息表示與數(shù)據(jù)交換的新 標(biāo)準(zhǔn) 隨著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 等大型商業(yè)數(shù)據(jù)庫(kù)產(chǎn)品紛紛將 地的存儲(chǔ)和查詢功能納入 箕核心部分 越窳越多瓣璃菇鼓及W e b 虛爰霞鵝TX M L 送行售意豹發(fā)東 W e b 上用X M L 表示的數(shù)據(jù)越來(lái)越多 X M L 已經(jīng)成為目前W c b 上最蹙矚目以及被認(rèn)為 跫援其笈震蓑最麴技術(shù) 然恧 瞧于X M L 鶼半結(jié)構(gòu)化特性 饅褥簧統(tǒng)熊數(shù)據(jù)管耀 技術(shù)不能完全滿足對(duì)X M L 數(shù)據(jù)的存儲(chǔ)以及查詢管理的需要 因此 研究針對(duì)X M L 數(shù)據(jù)豹數(shù)據(jù)庫(kù)管理技術(shù)勢(shì)在必行 旦翦 X M L 數(shù)據(jù)庫(kù)的主要工作集中在查詢處理 及優(yōu)化技術(shù) 知路徑表達(dá)式查詢優(yōu)化技術(shù) T w i g 查詢優(yōu)化技術(shù) 包含連接查詢技 術(shù)研究 X M L 索引技術(shù)等 但是由于X M L 具肖十分復(fù)雜的半結(jié)構(gòu)化特性 目黼 的研究成果還不能完全支持X M L 標(biāo)準(zhǔn)凌詢語(yǔ)言X Q u e r y 因虼在世界蒗圍肉 無(wú) 論是學(xué)術(shù)界還懸工業(yè)界 對(duì)X M L 查詢處理和優(yōu)化技術(shù)都正在進(jìn)行更加深入的研 究 1 1X M L 相關(guān)技術(shù) 1 1 1 一個(gè)X M L 數(shù)據(jù)實(shí)例 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 實(shí)鍘文梢 F i g u r e1 1X M Ls a m p l ed o c u m e n t 東北大學(xué)碩士學(xué)位論文第一章前言 鶩 1 怒一令X M L 文樓實(shí)翻 文禚靜蘩一雩亍是一令X M L 聲疆 繪鲞了X M L 文檔采用的X M L 版本號(hào) 怒否和外部D T D 配合使用 以及數(shù)據(jù)歷采用的編碼方 式等信塞 文檔熬籬2 雩亍據(jù)瞧了當(dāng)曼示該X M L 文檔瓣獲應(yīng)搜蠲的撐蔑文饞 文擋 第3 行是文檔的外部D T D 使用說(shuō)明 從第4 行起是文檔所表示的數(shù)據(jù) X M L 通 過(guò)元素寒韁織X M L 數(shù)提 元素是X M L 文摟內(nèi)容鮑基本單元 X 1 W L 元素包攝標(biāo) 記和字符數(shù)據(jù) 從譖法角度上看 一個(gè)元素包含了 個(gè)起始標(biāo)記 一個(gè)結(jié)束標(biāo)記 以及標(biāo)記之闥的數(shù)據(jù)皮容 X M L 中宥元素 屬性 文本等幾攤基本的數(shù)據(jù)類型 因?yàn)楸疚闹靼晏接慩 M L 文檔路徑查詢 因此我們主臻研究這幾種數(shù)據(jù)類型 每個(gè) X M L 文檔有且僅有一個(gè)根元素 圖1 1 中的根元素的標(biāo)簽為A c t 它有兩個(gè)子元 素 其標(biāo)簽分剮是P r o l o g u e 鞠E p i l o g u e j 1 l 2D 0 搬模型及D O M 標(biāo)準(zhǔn) 圖1 2 怒與圖1 1 中的X M L 文檔相對(duì)應(yīng)的D O M 樹(shù) D O M 模型以有層次的結(jié) 點(diǎn)霹象耱款形式來(lái)襲疆文檔 這些蘩患中鴦熬可滋霄孩子結(jié)點(diǎn) 有懿只戇 擘雋時(shí) 子結(jié)點(diǎn)存在 通過(guò)用圖形表示的D O M 樹(shù) 我們可以很清楚地了解X M L 文檔的數(shù) 輾之闖戇縫穩(wěn) 建繁籬頭數(shù)線段表示實(shí)倒之闕鮑實(shí)辯的父予關(guān)系或滋元素與屬性 之間的關(guān)系 圖形中的數(shù)字代表這一縮點(diǎn)實(shí)例的唯一標(biāo)識(shí) O b j e c t I D 如果D O M 鍵在內(nèi)存中實(shí)理 它霹能是結(jié)點(diǎn)款擺針或旬援 如聚D O M 被持久他在數(shù)據(jù)庫(kù)中 它可能是記錄的主鑣或者對(duì)漿的I D 符號(hào)下面的字符串標(biāo)明了元素結(jié)點(diǎn)或滿性結(jié) 點(diǎn)的名字 如標(biāo)記為 9 的結(jié)點(diǎn)就對(duì)應(yīng)于魏睡示例文檔中 A c t i nP r o l o g u e 這段 文本 它是A c t 元索 編號(hào)為5 節(jié)點(diǎn)的子節(jié)點(diǎn) D O M D o c u m e mO b j e c tM o d e l 是W 3 C 報(bào)薦的 組應(yīng)用于X M L 和H T M L 的編 程接口 D O M 定義了文檔靜邏輯結(jié)構(gòu)以及文檔靜誘滔幫修瀲方法 警X M L 文擋 以D O M 的方式呈現(xiàn)時(shí) 可以被看作數(shù)據(jù)而不單純是文件 D O M 規(guī)范為程序開(kāi)發(fā) 圖1 2 示例文檔的D O M 樹(shù) 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 一 魚(yú)w 芝一 一 土 尚一一 瓣 一 查 查堂翌主堂堡笙查 莖二主墮童 者提供了一系列的應(yīng)用程序接口的描述 通過(guò)D O M 程序開(kāi)發(fā)者可以創(chuàng)建 個(gè) X M L 文檔 按文檔的結(jié)構(gòu)進(jìn)行遍歷 增加 刪除或修改X M L 文檔中的元素和內(nèi) 容 W 3 C 在制定D O M 接口時(shí)即要求該標(biāo)準(zhǔn)具有平臺(tái)無(wú)關(guān)性 使它能夠在任何平 臺(tái)上以任何語(yǔ)言實(shí)現(xiàn) 所以D O M 標(biāo)準(zhǔn)使用O M GI D L 編寫(xiě) D O M 標(biāo)準(zhǔn)定義的所 有的A P I 都是接口 i n t e r f a c e s 定義而不是類 c l a s s 定義 這意味著標(biāo)準(zhǔn)的任 何實(shí)現(xiàn)都只需要按照名字和定義好的操作來(lái)實(shí)現(xiàn)該方法 1 1 3D T D 簡(jiǎn)介 圖1 3 給出了 個(gè)與圖 1 中的X M L 文檔對(duì)應(yīng)的D T D 圖 仍蕊卜 設(shè)計(jì)并實(shí)現(xiàn)了支持自動(dòng)機(jī)匹配方法所需的索引結(jié)構(gòu)和其它相關(guān)數(shù)據(jù)結(jié)構(gòu) 而且設(shè)計(jì)并實(shí)現(xiàn)了新的利用鍵樹(shù)來(lái)匹配自動(dòng)機(jī)的算法 擴(kuò)展了自動(dòng)機(jī)的功能 同時(shí)提出了自動(dòng)機(jī)匹配算法中路徑表達(dá)式 謂詞問(wèn)題的計(jì)算方法和優(yōu)化方法 該文最后給出了自動(dòng)機(jī)匹配算法與其它兩種查詢算法在查詢性能上的比較并加以簡(jiǎn)要分析 5 學(xué)位論文 柳娜 統(tǒng)一資源管理系統(tǒng)中查詢組件的設(shè)計(jì)與實(shí)現(xiàn) 2006 為了能有效地進(jìn)行資源共享和交換 提高資源建設(shè)的效率和水平 本文提出了統(tǒng)一資源庫(kù)的概念一一即建立一個(gè)統(tǒng)一的資源平臺(tái) 通過(guò)資源類型注冊(cè)機(jī)制 對(duì)各種不同標(biāo)準(zhǔn)類型的資源提供統(tǒng)一的存取 檢索和管理 由于統(tǒng)一資源管理平臺(tái)數(shù)據(jù)量大 實(shí)時(shí)操作頻繁 數(shù)據(jù)類型多樣化 因此本文采用了目前比較先進(jìn)的XML ExtensibleMarkupLanguage 可擴(kuò)展標(biāo)記語(yǔ)言 半結(jié)構(gòu)化數(shù)據(jù)庫(kù)模型來(lái)進(jìn)行數(shù)據(jù)庫(kù)的管理 對(duì)于其中的數(shù)據(jù)查詢功能利用XML文檔查詢技術(shù)來(lái)實(shí)現(xiàn) 通過(guò)對(duì)國(guó)內(nèi)外XML文檔查詢算法的分析發(fā)現(xiàn) 大多數(shù)算法的實(shí)現(xiàn)是把被查詢文檔全部載入內(nèi)存之后再進(jìn)行處理 因此要消耗大量?jī)?nèi)存 尤其是在XML文檔很大以致無(wú)法全部載入內(nèi)存的情況下 這些算法就無(wú)能為力了 針對(duì)這一問(wèn)題 本文在統(tǒng)一資源管理平臺(tái)查詢組件中設(shè)計(jì)并實(shí)現(xiàn)了一種新的查詢算法 該算法的設(shè)計(jì)思路是 首先根據(jù)XPath查詢表達(dá)式 生成一個(gè)查詢自動(dòng)機(jī) 并將查詢條件隱含在查詢自動(dòng)機(jī)的結(jié)構(gòu)和狀態(tài)中 然后通過(guò)SAX SimpleAPIsforXML XML簡(jiǎn)單應(yīng)用程序接口 解析程序?qū)ML文本數(shù)據(jù)流轉(zhuǎn)化為SAX事件流 并將這些事件作為查詢自動(dòng)機(jī)的輸入 來(lái)觸 發(fā)查詢自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換 查詢自動(dòng)機(jī)依據(jù)不同的輸入事件 在各個(gè)狀態(tài)之間進(jìn)行轉(zhuǎn)換 一旦確認(rèn)某一部分文檔完全匹配查詢表達(dá)式 查詢引擎程序就輸出查詢結(jié)果 文中詳細(xì)地介紹了由查詢表達(dá)式構(gòu)造查詢自動(dòng)機(jī)的步驟 實(shí)現(xiàn)了一個(gè)基于流的XML文檔查詢系統(tǒng)的原型 它可以在對(duì)XML流的一次單向讀取過(guò)程中處理XPath 輸出查詢結(jié)果 文中還對(duì)基于內(nèi)存的XML查詢算法和基于流的XML查詢算法進(jìn)行測(cè)試 比較 并對(duì)結(jié)果進(jìn)行了分析 基于流的XML查詢算法是為了滿足一些數(shù)據(jù)密集型應(yīng)用對(duì)數(shù)據(jù)查詢處理的需求而引入的 這類應(yīng)用處理的數(shù)據(jù)不宜用持久穩(wěn)定的關(guān)系建模 而應(yīng)采用數(shù)據(jù)流建模 這類應(yīng)用的領(lǐng)域包括金融服務(wù) 網(wǎng)絡(luò)監(jiān)控 電信數(shù)據(jù)管理 生產(chǎn)制造 傳感檢測(cè)等 本論文的研究對(duì)這類實(shí)際應(yīng)用將具有一定的理論意義和使用價(jià)值 6 會(huì)議論文 呂建華 周巍 孫冰 王國(guó)仁 于戈 XML查詢中RPE索引技術(shù)研究 2001 本文針對(duì)正則路徑達(dá)表達(dá)式的特點(diǎn)提出了一個(gè)基于自動(dòng)機(jī)的正則路徑表達(dá)式索引方法 它把正則路徑表達(dá)式轉(zhuǎn)換成自動(dòng)機(jī) 利用其相似性準(zhǔn)確而有效地索引正則路徑表達(dá)式 從而提高正則路徑表達(dá)式的查詢處理效率 7 學(xué)位論文 許翼 XML樹(shù)模式查詢研究 2008 XML是可擴(kuò)展標(biāo)記語(yǔ)言的簡(jiǎn)稱 為Web上半結(jié)構(gòu)化文檔和數(shù)據(jù)提供了通用格式 隨著Internet的發(fā)展尤其是Web技術(shù)的廣泛應(yīng)用 越來(lái)越多的應(yīng)用采用了XML技術(shù)作為信息表示和數(shù)據(jù)交換的標(biāo)準(zhǔn) 這使得通過(guò)數(shù)據(jù)庫(kù)技術(shù)對(duì)XML數(shù)據(jù)進(jìn)行存儲(chǔ) 查詢等操作變得越來(lái)越重要 由于XML文檔可看作樹(shù)型 對(duì)XML的查詢可以看成是基于值謂詞的子樹(shù)Twig匹配 也就是從 XML文檔找到和給定查詢條件相匹配的子樹(shù) 因此能夠高效找到子樹(shù)匹配成為XML中的一個(gè)核心問(wèn)題 本文在介紹了XML查詢的研究現(xiàn)狀和研究成果的基礎(chǔ)上 針對(duì)Twig Stack算法在多層嵌套的XML文檔下性能不高的情況 提出了改進(jìn)算法Nest Twig 并證明行之有效 Nest Twig算法和Twig Stack算法都是基于分解 匹配 合并的步驟來(lái)進(jìn)行查詢匹配處理 容易產(chǎn)生大量無(wú)用的中間結(jié)果或者會(huì)對(duì)一些子模式樹(shù)進(jìn)行重復(fù)匹配 為了解決這個(gè)問(wèn)題 本文引入自 動(dòng)機(jī)思想 對(duì)Twig查詢自動(dòng)機(jī)與路徑模式樹(shù)的匹配進(jìn)行了討論 提出了改進(jìn)算法Pattern Match 對(duì)Pattern Match算法和Nest Twig算法進(jìn)行了實(shí)驗(yàn)對(duì)比證明基于自動(dòng)機(jī)的方法在性能上具有較大優(yōu)勢(shì) 8 期刊論文 方峻 劉長(zhǎng)毅 徐誠(chéng) 槍械方案設(shè)計(jì)系統(tǒng)中的基于實(shí)例推理框架研究 兵工學(xué)報(bào)2003 24 1 本文提出了一種基于實(shí)例推理 CBR 的面向?qū)ο罂蚣茉?闡述了其結(jié)構(gòu)組成和實(shí)現(xiàn)形式 研究了其在構(gòu)建槍械方案設(shè)計(jì)系統(tǒng)中的應(yīng)用 同時(shí)建立了基于可擴(kuò)展標(biāo)記語(yǔ)言 XML 的實(shí)例表達(dá)形式和一套面向?qū)ο蟮膶?shí)例推理模型 在此基礎(chǔ)上開(kāi)發(fā)了一套槍械自動(dòng)機(jī)方案設(shè)計(jì)原型系統(tǒng) 并以一個(gè)設(shè)計(jì)實(shí)例對(duì)系統(tǒng)進(jìn)行了驗(yàn)證 9 學(xué)位論文 包小源 壓縮XML的索引與查詢方法研究 2005 XML由于為其中所保存內(nèi)容的每個(gè)語(yǔ)義單元引入一個(gè)標(biāo)記而使整個(gè)文件的內(nèi)容迅速膨脹 這種情況下 在對(duì)數(shù)量龐大的XML數(shù)據(jù)進(jìn)行管理時(shí) 進(jìn)行壓縮就成為一種有效的基本解決方法 其實(shí) XML作為一種數(shù)據(jù)交換標(biāo)準(zhǔn) 由于其頻繁在網(wǎng)絡(luò)上進(jìn)行傳輸 為了節(jié)省寶貴的網(wǎng)絡(luò)資源 壓縮將是一種必然的選擇 對(duì)壓縮數(shù)據(jù)進(jìn)行查詢的基本方法是首先解壓縮 然后再實(shí)施查詢 這種方法在數(shù)據(jù)量小的情形下尚可 對(duì)于所管理數(shù)據(jù)量龐大的情形下 如IR中的海量數(shù)據(jù)管理 大規(guī)模企業(yè)的海量XML客戶個(gè)性化數(shù)據(jù)等 每次查詢需要事先解壓縮所帶來(lái)的性能下降是無(wú)法承受的 于是 直接基于壓縮數(shù)據(jù)進(jìn)行索引 查詢等就變得非常重要而且必要 這一點(diǎn)對(duì)壓縮XML數(shù)據(jù) 是同樣適用的 但目前已有的壓縮方法大多沒(méi)有兼顧結(jié)構(gòu)保持 解壓縮效率 以及壓縮比等三個(gè)方面的要求 不能支持直接基于壓縮的查詢 同時(shí) 基于壓縮的XML索引 查詢 包括靜態(tài) 流兩方面的查詢 很少 而已有研究不能直接 或者根本不能應(yīng)用于壓縮數(shù)據(jù)的索引和查詢 圍繞上述問(wèn)題 本文提出了XML結(jié)構(gòu)保持壓縮方法 基于壓縮的XML索引方法 基于壓縮XML靜態(tài)數(shù)據(jù)以及壓縮XML流的查詢及分發(fā)方法 主要的創(chuàng)新性成果包括 1 提出了基于Byte Huffman的XML結(jié)構(gòu)保持壓縮思想和方法 目前已有的XML結(jié)構(gòu)保持壓縮方法基本上自成系統(tǒng) 無(wú)法有效與其他應(yīng)用系統(tǒng)集成 且其實(shí)現(xiàn)復(fù)雜 還有很重要的一點(diǎn) 在網(wǎng)絡(luò)環(huán)境下 對(duì)壓縮和解壓縮的速度要求是同等重要的 但目前的壓縮方法 無(wú)論是非結(jié)構(gòu)保持壓縮或是結(jié)構(gòu)保持壓縮 因主要集中于實(shí)際應(yīng)用中XML傳輸及存儲(chǔ)效率的提高 從而對(duì)解壓縮的效率不夠重視 經(jīng)過(guò)我們對(duì)現(xiàn)有的實(shí)驗(yàn)系統(tǒng)測(cè) 試 其解壓縮的速度一般都很慢 本文提出了一種支持查詢的XML壓縮方法 QueXComp QuerableXMLCompression 它以XByteHuff為基本壓縮編碼方法 通過(guò)保留以 及 等定義的XML結(jié)構(gòu) 以Word為基本壓縮統(tǒng)計(jì)單位對(duì)元素的Tag及元素值實(shí)施壓縮 可實(shí)現(xiàn)高效率的壓縮和解壓縮 為了能實(shí)現(xiàn)從壓縮XML數(shù)據(jù)中任意位置開(kāi)始的查詢及解壓縮 我們對(duì)ByteHuffman編碼進(jìn)行了改進(jìn) 保留其MSB作為標(biāo)志位以指示一個(gè)Word的開(kāi)始 形成了XbyteHuff 同時(shí) 為了實(shí)現(xiàn)基于壓縮的高效查詢 我們提出了字典索引結(jié)構(gòu)P Tries 并提出了基于ByteHuffman樹(shù)中附加Mark域信息以支持所提出的基于NFA 非有限自動(dòng)機(jī) 的壓縮XML內(nèi)容查詢 2 提出了基于壓縮的XML結(jié)構(gòu)索引S