基于版本樹的XML查詢研究.pdf

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

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

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