XML樹模式匹配查詢研究.pdf

1、隨著Internet和Web技術(shù)的迅猛發(fā)展，XML已經(jīng)逐漸成為了數(shù)據(jù)表達(dá)和交換的主要標(biāo)準(zhǔn)和載體。日益增長的XML數(shù)據(jù)對已有的數(shù)據(jù)管理技術(shù)提出了新的要求，如何有效地對XML數(shù)據(jù)進(jìn)行管理和查詢已經(jīng)成為了目前數(shù)據(jù)庫領(lǐng)域的研究重點。
　　 本文工作圍繞XML數(shù)據(jù)的樹模式匹配進(jìn)行，它可被看作是多步的結(jié)構(gòu)連接，但這些連接操作被當(dāng)成一個整體進(jìn)行處理，避免了大量的無關(guān)結(jié)點參與運算，從而提高了查詢效率。樹模式匹配可作為XQuery查詢的一個操作符

2、，并且已經(jīng)被普遍認(rèn)為是XML查詢的核心操作。目前在該方面已經(jīng)提出了一系列有效的實現(xiàn)方法，早期的工作多是按兩個階段執(zhí)行，首先將查詢分解為多條從根到葉結(jié)點的子路徑，通過索引或者其他過濾算法獲取匹配的局部結(jié)果，然后再對這些結(jié)果進(jìn)行歸并。這種方式在查詢包含父子關(guān)系時可能會產(chǎn)生不能構(gòu)造最終輸出的中間結(jié)果，同時路徑歸并會花費較多的時間開銷。之后提出的算法，其設(shè)計思路大多是為了盡量減少執(zhí)行過程中產(chǎn)生的無關(guān)結(jié)果，同時避免歸并操作，但是它們采用的數(shù)據(jù)結(jié)構(gòu)

3、較為復(fù)雜，實現(xiàn)起來代價較高，特別的，最壞情況下可能要在內(nèi)存構(gòu)建整棵文檔樹。
　　 本文在研究已有樹模式匹配算法的基礎(chǔ)上，提出了新的解決方法。本文的主要工作如下：(1)研究分析了現(xiàn)有的樹模式匹配算法，并總結(jié)其實現(xiàn)方法；(2)基于路徑索引，同時考慮到查詢通常只需要獲取某幾個結(jié)點的匹配結(jié)果，提出了針對輸出結(jié)點的TwigFilter算法，算法過程根據(jù)要處理的輸出結(jié)點進(jìn)行，這樣減少了參與運算的無關(guān)結(jié)點的數(shù)量，節(jié)省了相應(yīng)的I/O和匹配開銷，