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

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

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

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