基于XML結(jié)構(gòu)性約束的模式樹查詢最小化.pdf

1、隨著計(jì)算機(jī)應(yīng)用技術(shù)和電子商務(wù)的快速發(fā)展，企業(yè)可獲取的信息數(shù)量和類型有了極大的增長。由于XML的可擴(kuò)展性、結(jié)構(gòu)性以及平臺(tái)無關(guān)性的優(yōu)點(diǎn)，XML已經(jīng)成為Internet數(shù)據(jù)交換事實(shí)上的標(biāo)準(zhǔn)，在Web中得到廣泛應(yīng)用。如通過Web搜索引擎找到XML是自然而然的事情。在搜索引擎查找符合特定條件的XML文檔時(shí)，即針對于XML數(shù)據(jù)庫的進(jìn)行查詢。因此XML的查詢優(yōu)化具有巨大的商業(yè)意義，成為目前研究的熱點(diǎn)。 XML是專為Web設(shè)計(jì)的，把XML看作

2、Web世界中的數(shù)據(jù)模型，目前流行的XML數(shù)據(jù)模式有多種，如DTD，XML，Schema，RELAX NG等。定義XML數(shù)據(jù)的模式時(shí)，常遇到這樣的情況，如定義的XML出現(xiàn)了某種形式的結(jié)構(gòu)時(shí)，必然有另一種形式的結(jié)構(gòu)同時(shí)出現(xiàn)，這便是一類基于XML結(jié)構(gòu)的完整性約束。DTD是一種基于語法的XML規(guī)范形式化定義，在考慮結(jié)構(gòu)完整性約束時(shí)，一種基于pattern的XML規(guī)范形式化定義XSCs模式可以與其聯(lián)合使用，使得生成的DTD具有更為豐富的語義。

3、 模式樹是對像XML和LDAP等樹形結(jié)構(gòu)數(shù)據(jù)進(jìn)行查詢的基礎(chǔ)。在樹形結(jié)構(gòu)數(shù)據(jù)庫上進(jìn)行樹模式匹配的效率取決于模式樹的大小，因而盡快發(fā)現(xiàn)和刪除模式中的冗余節(jié)點(diǎn)就顯得十分的重要。模式樹查詢最小化問題，經(jīng)證明是NP—Hard問題。 在本文中，我們研究引入XML結(jié)構(gòu)性約束時(shí)的XML模式樹查詢最小化問題。具體來說，我們將在XSCs模式下，基于幾種路徑的結(jié)構(gòu)性約束，實(shí)現(xiàn)模式樹查詢最小化。解決該問題的關(guān)鍵技術(shù)由Chase技術(shù)和刪除冗余節(jié)點(diǎn)算法

4、兩部分組成。首先，我們使用Chase技術(shù)對給定查詢對應(yīng)的模式樹進(jìn)行擴(kuò)展，利用已知的結(jié)構(gòu)性約束，在不改變查詢結(jié)果的前提下在模式樹中增加節(jié)點(diǎn)，得到與原模式樹查詢等價(jià)的一棵新的模式樹；然后，利用約束獨(dú)立情況下模式樹查詢最小化算法，刪除Chase階段生成的模式樹中的冗余節(jié)點(diǎn)以及在Chase過程中產(chǎn)生的新節(jié)點(diǎn)，得到最終的模式樹，此模式樹對應(yīng)的模式樹查詢即為原查詢等價(jià)的最小化查詢。 本文中我們提出的XSCM算法就是基于以上思路。經(jīng)分析，該算