XML非完全結(jié)構(gòu)查詢技術(shù)的研究.pdf

1、分類號UDC密級學(xué)校代碼10497劣屬程歹大署學(xué)位論文英文題I三IResearchonNonfullyStructuralXMLQuery——研究生姓名聶晶姓名因壁萱職稱絲撞學(xué)位鱟指導(dǎo)教師單位名稱鹽簋查墾盤堂魚圭垂盔鱟睦郵編箜鯉魚申請學(xué)位級別論文提交日期墊13：壘論文答辯日期20135學(xué)位授予單位迦蘭盤堂學(xué)位授予日期絲區(qū)笸答辯委員會主席’2013年5月閽^千馮m閱人]絲翌么Z縫摘要XML非完全結(jié)構(gòu)查詢是指滿足用戶在缺乏完整的XML文檔結(jié)

2、構(gòu)信息情況下的查詢需求，其主要面向缺少完整的結(jié)構(gòu)信息說明以及異構(gòu)環(huán)境下的查詢需求。XML數(shù)據(jù)查詢算法按照查詢模式描述的不同分為兩類，即XML結(jié)構(gòu)查詢和XML關(guān)鍵字查詢。前者多采用了正則表達式的描述方法，偏向于傳統(tǒng)的結(jié)構(gòu)化的查詢方式，能夠清楚的表述用戶的查詢意圖；后者融入了信息檢索領(lǐng)域常用的查詢思想和方法，允許用戶僅僅輸入關(guān)鍵字就能夠進行查詢。XML關(guān)鍵字查詢與XML結(jié)構(gòu)化查詢比較起來更靈活，它只需要用戶提供簡單的關(guān)鍵字信息，而無需懂得任

3、何查詢語言或文檔結(jié)構(gòu)就可方便使用，因此該模式被廣泛采用，有著重要的研究價值。XML關(guān)鍵字查詢方式中最關(guān)鍵的問題是如何求解包含所有關(guān)鍵字的最小片段，即SLCA(SmallestLowestCommonAncestors)l商J題。論文的主要研究內(nèi)容如下：首先介紹了XML關(guān)鍵字查詢方面的知識，包括XML樹型結(jié)構(gòu)、XML編碼方案、包含關(guān)鍵字的最小片斷理論以及XML關(guān)鍵字查詢的思路。在三種XML編碼方案中，因為Dewey編碼包含更多的節(jié)點信息，

4、所以選擇它作為實驗的編碼方案。其次研究已存在的關(guān)于XML關(guān)鍵字查詢的經(jīng)典算法，并對各算法進行比較，分析它們的優(yōu)點和不足，重點研究了LISA算法。LISA不僅需要頻繁掃描節(jié)點，而且需要引入集合交操作，耗費了大量CPU周期。LISAII雖然在避免不必要掃描方面改進了LISA算法，但卻使用了自己獨有的編碼，不僅引入了編碼映射，而且也使得該算法的通用性大大削弱。這兩種算法即便作為一種僅在內(nèi)存中執(zhí)行的算法，以上缺點也影響了查詢速度。為此，本文提出