XML上基于SLCA的關(guān)鍵字查詢研究.pdf

1、隨著互聯(lián)網(wǎng)的發(fā)展，XML格式逐漸成為數(shù)據(jù)展現(xiàn)和傳輸?shù)氖聦崢?biāo)準(zhǔn)。XML上信息獲取技術(shù)研究也越發(fā)重要。自XML語言誕生以來，各種各樣的XML結(jié)構(gòu)化查詢語言被開發(fā)出來，如XPath、XQuery等。但結(jié)構(gòu)化查詢語言對用戶要求較高，不僅要求掌握一門復(fù)雜的查詢語言，還要求了解目標(biāo)XML文件的結(jié)構(gòu)知識。而關(guān)鍵字查詢的方式，簡單易用，受到用戶的喜歡。XML上關(guān)鍵字查詢已成為研究的熱點。
　　本文工作主要包括:1.通過引入兩個有效的剪枝策略和三個

2、定義明確的匹配節(jié)點組合概念提出了一個高效的基于SLCA語義的關(guān)鍵字查詢算法MMPS;2.提出了關(guān)鍵字查詢的返回結(jié)果快速分類的算法。
　　為了返回有意義的關(guān)鍵字查詢返回結(jié)果，SLCA（最小最低公共祖先）的概念被引入到數(shù)據(jù)管理領(lǐng)域，即返回一棵同時滿足兩個條件的子樹(a)包含所有關(guān)鍵字，(b)這棵樹上不包含滿足條件b的子樹。然而現(xiàn)有的基于SLCA語義的算法在計算SLCA過程中通常會引入大量中間結(jié)果的計算，即使最后的返回結(jié)果集很小，剪枝策

3、略較簡單，效率不高。針對這些不足，本文深入研究SLCA候選和XML上的節(jié)點間的關(guān)系，提出了兩個有效的剪枝策略和三個匹配節(jié)點組合概念，基于這些策略和概念提出了一個高效的SLCA關(guān)鍵字查詢算法MMPS。在本文實驗部分重新實現(xiàn)了當(dāng)前較優(yōu)的IMS算法與MMPS算法，并通過在真實數(shù)據(jù)集和人工數(shù)據(jù)集上的對比試驗，驗證了MMPS算法的高效性。
　　另一方面，基于關(guān)鍵字查詢返回結(jié)果較多，返回的結(jié)果有些差別較大的事實，本文提出了對返回結(jié)果的快速分類