XML關(guān)鍵字查詢中最緊致片段問題的研究.pdf

1、XML（eXtensible Markup Language）在Web服務(wù)、電子商務(wù)、數(shù)字圖書館等諸多網(wǎng)絡(luò)相關(guān)應(yīng)用領(lǐng)域已經(jīng)成為描述數(shù)據(jù)的事實上的標(biāo)準(zhǔn)。為了方便用戶從海量的XML數(shù)據(jù)中提取他們所需要的信息，許多XML數(shù)據(jù)查詢算法應(yīng)運而生，使得XML數(shù)據(jù)查詢成為XML數(shù)據(jù)管理領(lǐng)域的一個熱點。 本文將這些XML數(shù)據(jù)查詢算法按照查詢模式描述的不同分為兩類，即XML結(jié)構(gòu)查詢和XML關(guān)鍵字查詢。前者多采用了正則表達式的描述方法，偏向于傳統(tǒng)的

2、結(jié)構(gòu)化的查詢方式，能夠清楚的表述用戶的查詢意圖；后者融入了信息檢索領(lǐng)域常用的查詢思想和方法，允許用戶僅僅輸入關(guān)鍵字就能夠進行查詢。 XML結(jié)構(gòu)查詢算法根據(jù)精確的查詢條件，能夠輸出理想的查詢結(jié)果。然而，該算法對進行查詢的用戶也提出了更高的要求，即不僅要熟悉結(jié)構(gòu)查詢算法所采用的查詢語言，而且還要了解待查詢的XML文檔樹結(jié)構(gòu)。以上要求對于絕大多數(shù)用戶而言是不切實際的，所以從用戶的角度出發(fā)，XML關(guān)鍵字查詢是一種能夠被廣泛使用的查詢方

3、法。 XML關(guān)鍵字查詢方式中最關(guān)鍵的問題是如何求解包含所有關(guān)鍵字的最緊致片段，即SLCA（Smallest Lowest Common Ancestors）問題。目前已有許多求解算法，包括Stack、ILE、SE、LISA和LISAⅡ等。ILE和SE在與Stack的實驗對比中表現(xiàn)得效率更高，適合需要頻繁I/O操作的海量XML查詢，他們僅需要順序讀取XML數(shù)據(jù)一遍；相比ILE和SE，LISA和LISAⅡ在輕量級XML查詢中，無論

4、是在理論分析上還是試驗對比中都表現(xiàn)出了更好的性能。 然而，LISA不僅需要頻繁掃描節(jié)點，而且需要引入集合交操作，耗費了大量CPU周期。LISAⅡ雖然在避免不必要掃描方面改進了LISA算法，但卻使用了自己獨有的編碼，不僅引入了編碼映射，而且也使得該算法的通用性大大削弱。這兩種算法即便作為一種僅在內(nèi)存中執(zhí)行的算法，以上缺點也影響了查詢速度。 為此，本文提出一種輕量級的、使用XML關(guān)鍵字查詢通用的Dewey編碼的新算法，NDT