基于版本樹(shù)的XML查詢研究.pdf

1、自從W3C發(fā)布了XMK1.0規(guī)范以來(lái)，XML日益成為網(wǎng)絡(luò)上信息交換的新興標(biāo)準(zhǔn)。由于XML被用來(lái)作為數(shù)據(jù)表示以及數(shù)據(jù)存儲(chǔ)手段的普遍性，針對(duì)XML文檔數(shù)據(jù)的查詢處理研究表現(xiàn)出越來(lái)越大的應(yīng)用價(jià)值。尤其是將XML文檔看成一個(gè)樹(shù)形結(jié)構(gòu)的數(shù)據(jù)模型，這種樹(shù)形模型能夠覆蓋XQuery和XPath查詢中非常有用的子集。近來(lái)，大量的基于這種XML樹(shù)形模型的查詢算法被相繼提出，這些XML查詢算法普遍存在的一個(gè)問(wèn)題是算法的輸入集規(guī)模和執(zhí)行時(shí)間將隨著XML文檔規(guī)

2、模的增長(zhǎng)而迅速增加，從而導(dǎo)致對(duì)大規(guī)模文檔進(jìn)行查詢非常低效。 本文提出了基于版本編碼模式的TwigVersion算法來(lái)解決這個(gè)問(wèn)題。本文的研究?jī)?nèi)容和特色如下： 1) 針對(duì)XML文檔中的普遍存在的重復(fù)結(jié)構(gòu)建立一種版本編碼模式，利用版本編碼模式對(duì)XML文檔中的重復(fù)結(jié)構(gòu)進(jìn)行識(shí)別和標(biāo)識(shí)。 2) 建立_個(gè)精簡(jiǎn)的數(shù)據(jù)結(jié)構(gòu)——版本樹(shù)來(lái)保存XML文檔中的數(shù)據(jù)的結(jié)構(gòu)信息?；诎姹揪幋a模式，TwigVersion算法通過(guò)對(duì)XML文檔進(jìn)

3、行兩次等價(jià)類劃分產(chǎn)生XML文檔的版本樹(shù)，它是一種保存了原始XML文檔的全部結(jié)構(gòu)信息的精簡(jiǎn)的數(shù)據(jù)結(jié)構(gòu)。 3) 設(shè)計(jì)與實(shí)現(xiàn)基于版本樹(shù)的TwigVersion查詢算法。針對(duì)一個(gè)XML查詢，TwigVersion算法利用版本樹(shù)上的信息，通過(guò)自底向上的版本推導(dǎo)和版本交集運(yùn)算產(chǎn)生查詢結(jié)果的版本過(guò)濾器，最終的查詢結(jié)果通過(guò)版本過(guò)濾器可以從數(shù)據(jù)庫(kù)中簡(jiǎn)便的過(guò)濾出來(lái)。 論文提供了理論證明和大量基于真實(shí)數(shù)據(jù)和人工數(shù)據(jù)的實(shí)驗(yàn)結(jié)果，證實(shí)了版本樹(shù)結(jié)構(gòu)