基于XML結構性約束的模式樹查詢最小化.pdf

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

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

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

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