一種支持動態(tài)XML文檔的存儲模式設(shè)計(jì)與應(yīng)用

賀 挺，楊 柳，陳真玄，楊 非

（水利部信息中心，北京 100053）

0 引言

隨著水利信息化的發(fā)展，各類水利信息系統(tǒng)的建設(shè)日益豐富。這些系統(tǒng)內(nèi)部的數(shù)據(jù)來源存在著很大差異，有來自關(guān)系數(shù)據(jù)庫中存儲的結(jié)構(gòu)化水利業(yè)務(wù)數(shù)據(jù)，也有半結(jié)構(gòu)化的水利空間業(yè)務(wù)數(shù)據(jù)等。平臺架構(gòu)、通信方式和數(shù)據(jù)結(jié)構(gòu)的差異阻礙了不同水利信息系統(tǒng)之間數(shù)據(jù)的有效共享。XML（可擴(kuò)展標(biāo)記語言）作為一種半結(jié)構(gòu)化語言，具有良好的信息表達(dá)功能，因此在信息交換、數(shù)據(jù)存儲及異構(gòu)數(shù)據(jù)集成方面擁有廣泛的應(yīng)用前景，并成為當(dāng)前互聯(lián)網(wǎng)上信息交換的主要標(biāo)準(zhǔn)。在水利信息系統(tǒng)數(shù)據(jù)集成方面，XML 被用于結(jié)構(gòu)化和半結(jié)構(gòu)化水利數(shù)據(jù)的表達(dá)[1]，異構(gòu)水利業(yè)務(wù)數(shù)據(jù)的集成工具[2]，水利業(yè)務(wù)平臺信息共享的標(biāo)準(zhǔn)語言[3]，以及水利遙感元數(shù)據(jù)的存儲[4]。

XML 的存儲主要有關(guān)系式和 NoSQL 2 種模式。對于 XML 文檔的關(guān)系式存儲，常采用 XRel模式，采用與關(guān)系數(shù)據(jù)庫兼容的邏輯存儲模式和索引方法對 XML 文檔進(jìn)行存儲和檢索[5]。XRel 通過SQL 語句實(shí)現(xiàn) XML 文檔的存儲，能夠很好地支持基于元素路徑關(guān)系的 XML 數(shù)據(jù)查詢（XPath）。但XRel 模式存在以下缺點(diǎn)：1）XRel 模式中 XML 文檔的結(jié)構(gòu)通過基于前序-后序關(guān)系的 Dietz 編碼[6]存儲，對動態(tài) XML 文檔的操作效率很低。原因在于當(dāng)面臨新元素插入或元素刪除的情景時(shí)，XRel 模式需要重新對整個(gè)文檔樹進(jìn)行編碼，這不但改變了原有元素的編碼值，更降低了文檔的存儲和檢索效率。2）關(guān)系存儲模式具有高度結(jié)構(gòu)化特點(diǎn)，對于某些沒有提供內(nèi)部結(jié)構(gòu)說明的 XML 文檔，在存儲過程中容易導(dǎo)致信息的丟失。為此，對 XRel 模式中的Dietz 編碼方案進(jìn)行改進(jìn)，引入向量方法[7]，設(shè)計(jì)一個(gè)支持 XML 文檔元素的動態(tài)插入或刪除的編碼方案——NewDietz，并且基于區(qū)間編碼機(jī)制設(shè)計(jì)了新的 XML文檔關(guān)系存儲模式。

1 NewDietz 編碼方案設(shè)計(jì)

在 Dietz 編碼中，XML 文檔的每一個(gè)元素的Dietz 編碼表示為一個(gè)整數(shù)對 [Pre，Post]，Pre，Post分別為對 XML 文檔進(jìn)行先序和后序遍歷后獲得的元素?cái)?shù)值。在直角坐標(biāo)系中，對于 XML文檔的任意 2 個(gè)元素V1[Pre1，Post1] 和V2[Pre2，Post2]，若V1的長度大于V2的長度，即Pre1＜Post2且Pre2＜Post1，則V1為V2的祖先元素。通過這種方式，XML 文檔的每個(gè)元素被賦予唯一的 Dietz 編碼。 Dietz 編碼的優(yōu)點(diǎn)是通過簡單的遍歷機(jī)制獲得元素的編碼值，并采用簡易的判別方法得到 XML 文檔任意 2 個(gè)元素的祖先-后裔關(guān)系，能夠方便地實(shí)現(xiàn)文檔在關(guān)系數(shù)據(jù)庫中的存儲。

在 NewDietz 編碼方案中，XML 文檔中的任意元素表示為一個(gè)三元數(shù)組 [Prev，Postv，L]，Prev和Postv分別稱為元素的前序和后序向量編碼，L表示元素在文檔中的層次，用于判斷任意 2 個(gè)元素的祖先-后裔關(guān)系。NewDietz 編碼對 XML 文檔元素的編碼過程表示如下：

1）對元素進(jìn)行 Dietz 編碼，分別獲得元素經(jīng)過先序和后序遍歷后得到的值i和j（i，j∈N）；

2）取i的最小值 1 和j的最大值n，分別賦予單位向量 [1，0] 和 [0，1]，取 1 和n的中值元素則中值元素的向量值為 [[1 + 0]，[0 + 1]]；

3）循環(huán)執(zhí)行第 2 步，直到所有元素的先序遍歷值都能夠被一個(gè)可以唯一標(biāo)識的向量代替為止；

4）由于所有元素經(jīng)過先序和后序 2 種遍歷得到的值的集合中的元素?cái)?shù)值相同，只是在順序上存在不同，因此元素的后序遍歷值的向量可以通過與先序遍歷值進(jìn)行唯一映射表示，編碼執(zhí)行結(jié)束。

NewDietz 編碼的基本原理是對 XML 文檔樹元素的 Dietz 編碼值進(jìn)行向量表示，因此在 NewDietz編碼方案下對元素的祖先-后裔判斷原理與 Dietz 編碼是相似的，對于任意 2 個(gè)經(jīng)過 NewDietz 編碼的元素V1[[x1，y1]，[x2，y2]] 和V2[[x3，y3]， [x4,，y4]]，如果，且則V為V的祖先元素。12

對動態(tài) XML 文檔進(jìn)行編碼時(shí)需要考慮到文檔在插入新元素或者刪除元素過程中的編碼問題，限于篇幅，本研究主要探討對 XML 文檔進(jìn)行元素插入過程中的 NewDietz 編碼過程。按照插入位置的不同，可以將元素的插入過程分為以下 4 種情況：在2 個(gè)兄弟元素之間插入新的兄弟元素，在祖先元素下插入新的最左后裔元素，在祖先元素下插入新的最右后裔元素，在后裔元素下插入新的后裔元素，如圖 1 所示。

為了能夠判斷新插入元素的祖先-后裔關(guān)系，并且保證元素編碼在關(guān)系模式中合理的存儲長度，對4 種方法中的 4 種元素插入類型的 NewDietz 編碼進(jìn)行如下定義：

1）對于任意 2 個(gè)經(jīng)過 NewDietz 編碼的元素V1和V2，若V1和V2為 XML 文檔中的 2 個(gè)兄弟元素，則定義新插入的元素V3的 NewDietz 編碼為V3[[x1+x3，y1+y3]，[x2+x4，y2+y4]]。

2）對于 XML 文檔樹中的任意元素V1，若V2為V1在插入新元素前的最左邊后裔元素，則在V1下插入 1 個(gè)新的最左邊后裔元素V3后的 NewDietz 編碼表示為V3[[x1+x3，y1+y3], [2x1+x3，2y1+y3]]。

圖1 對 XML 文檔元素進(jìn)行插入操作的 4 種方式

3）若V1為 XML 文檔中的任意元素，V2為V1在插入新元素前的最右邊后裔元素，則在V1下插入1 個(gè)新的最右邊后裔元素V4后的 NewDietz 編碼表示為V4[[x2+x4，y2+y4]，[2x2+x4，2y2+y4]]。

4）若V1為一葉子元素，則在V1下插入 1 個(gè)后裔元素V3的 NewDietz 編碼為

根據(jù)這 4 個(gè)定義，對于每個(gè)新插入元素，只需要對其本身進(jìn)行 NewDietz 編碼而無需對所有元素重新編碼；此外，新插入元素的 NewDietz 編碼的定義也符合編碼的祖先-后裔判斷，并且這種判斷在關(guān)系模式中也是明顯的。

2 支持 NewDietz 編碼的 XML 文檔關(guān)系存儲模式設(shè)計(jì)

在對 XML 文檔的相關(guān)研究中，與關(guān)系數(shù)據(jù)庫的交互是一個(gè)重要的研究方向[8]，但關(guān)系數(shù)據(jù)庫中元素-屬性之間嚴(yán)格的二元結(jié)構(gòu)特點(diǎn)與 XML 文檔的半結(jié)構(gòu)化特性之間存在著不可調(diào)和的矛盾，因此，在建立存儲模式時(shí)需要提供 XML 文檔結(jié)構(gòu)的說明，且針對 XML 文檔元素的祖先-后裔判斷算法與關(guān)系模式應(yīng)當(dāng)具有良好的互補(bǔ)性，進(jìn)而實(shí)現(xiàn)文檔的存儲。目前對 XML 文檔的關(guān)系存儲模式主要有以下 2 種模式：1）基于模式的存儲。建立 DTD（文檔類型定義） 或 Schema 模式圖，通過模式圖中對元素結(jié)構(gòu)順序的描述建立 XML 文檔的存儲索引算法，以進(jìn)一步實(shí)現(xiàn) XML 文檔的關(guān)系存儲。2）基于文檔編碼的存儲。先按照文檔-元素-屬性-文本的結(jié)構(gòu)對文檔進(jìn)行拆分、存儲，然后采用預(yù)先定義的編碼方法判斷任意元素之間祖先-后裔關(guān)系，并對文檔進(jìn)行重構(gòu)，這也是 XRel 模式采用的方式。本研究對第 2 種情況進(jìn)行研究，即設(shè)計(jì) NewDietz 編碼在關(guān)系數(shù)據(jù)庫中的存儲模式。

基于 NewDietz 編碼的關(guān)系存儲模式由以下關(guān)系表組成：

1）文檔表（Document table）。文檔表用來存儲XML 文檔的基本信息，具體字段包括 XML 文檔編號、名稱、存儲路徑和時(shí)間。

2）元素表（Element table）。元素表存儲 XML文檔的元素信息，具體字段包括 XML 文檔編號、元素名稱、元素和父元素的先序-后序 NewDietz 編碼，元素表通過 XML 文檔編號和文檔表建立關(guān)聯(lián)。

3）元素屬性表（Attribute table）。元素屬性表存儲 XML 文檔的元素屬性信息，具體字段包括 XML文檔編號，以及元素的先序-后序 NewDietz 編碼、屬性名稱、屬性值、前綴，元素屬性表通過 XML文檔編號和元素的先序-后序 NewDietz 編碼與文檔表及元素表建立關(guān)聯(lián)。

4）文本表（Text table）。文本表用來存儲 XML文檔元素的文本和數(shù)值信息，具體字段包括 XML文檔編號、元素的先序-后序 NewDietz 編碼、元素文本值，文本表通過 XML 文檔編號和元素的先序-后序 NewDietz 編碼，與文檔表、元素表、元素屬性表建立關(guān)聯(lián)。

根據(jù)關(guān)系存儲模式的定義，對于動態(tài) XML 文檔的關(guān)系存儲具體實(shí)現(xiàn)過程表達(dá)如下：

1）使用 JDOM 工具包對 XML 文檔進(jìn)行解析，構(gòu)建 XML 文檔樹；

2）對 XML 文檔元素進(jìn)行 NewDietz 編碼；

3）對文檔中所有元素的屬性（名稱、NewDietz編碼、屬性和數(shù)值）依照構(gòu)建的關(guān)系邏輯模式進(jìn)行存儲。

對于新插入元素在基于 NewDietz 編碼的關(guān)系模式中的存儲，通過在 XML 文檔樹中新插入元素的NewDietz 編碼定義，只需要提供新插入元素編碼和父元素信息就可以直接在元素表中執(zhí)行插入操作，而無需對整個(gè) XML 文檔在邏輯模式中的存儲信息進(jìn)行修改。

3 應(yīng)用實(shí)例

為驗(yàn)證基于 NewDietz 編碼模式的動態(tài) XML 文檔存儲模式的可行性，采用 W3C 標(biāo)準(zhǔn)下的 JDom[9]和 XQEngine[10]及開源的 GeoTools 工具包設(shè)計(jì)了一個(gè)水利空間數(shù)據(jù)存儲與展示模塊。該模塊以地理標(biāo)記語言（GML）文檔作為輸入。GML 是開放地理信息系統(tǒng)協(xié)會（OGC）制定的一種基于 XML 的傳輸和存儲地理信息的解決方案，是一種平臺無關(guān)的空間信息公共編碼標(biāo)準(zhǔn)。本研究對 4 類水利空間數(shù)據(jù)（水文站、水庫、行政區(qū)劃和河流）進(jìn)行了 GML表達(dá)，具體存儲和展示過程如下：1）存儲過程。首先對待存儲的空間數(shù)據(jù)進(jìn)行 NewDietz 編碼，然后按照定義的新關(guān)系模式對經(jīng)過編碼的 GML 文檔進(jìn)行分解存儲。2）展示過程。按照 NewDietz 編碼對GML 文檔中元素的祖先-后裔規(guī)則，從關(guān)系模式中對文檔進(jìn)行重構(gòu)并展示。

在算法復(fù)雜度分析方面，將基于 NewDietz 編碼方案的存儲模式與原有 XRel 的存儲模式進(jìn)行比較，對模塊中存儲的水利空間數(shù)據(jù)文檔，分別執(zhí)行 10，100，1 000，10 000 個(gè)元素的插入操作，性能比較的結(jié)果如圖 2 所示，可以看出對于 10 和 100 個(gè)元素的插入操作，2 種模式之間沒有顯著的性能差別，而對于超過 1 000 個(gè)元素的插入操作，新的存儲模式完成時(shí)間明顯低于原有模式。與 Dietz 編碼模式相比，NewDietz 編碼方案可以很好地支持 XML 文檔的動態(tài)更新，而且根據(jù) NewDietz 編碼方案設(shè)計(jì)的關(guān)系邏輯存儲模式與 XRel 關(guān)系邏輯存儲模式相比，不但支持文檔在關(guān)系模式下的存儲及重構(gòu)，而且也兼顧到動態(tài) XML 文檔在關(guān)系模式下的存儲。

4 結(jié)語

XML 作為一種數(shù)據(jù)格式描述的元語言標(biāo)準(zhǔn)，它的充足性、條理性、可擴(kuò)展性和自描述性成為其作為數(shù)據(jù)模型描述語言的優(yōu)勢，在水利元數(shù)據(jù)庫構(gòu)建、異構(gòu)水利信息系統(tǒng)業(yè)務(wù)數(shù)據(jù)集成和信息共享中起著重要的作用。目前關(guān)于 XML 文檔在水利信息系統(tǒng)中的存儲實(shí)踐還鮮有研究，本研究針對 XRel 關(guān)系存儲模式在動態(tài) XML 文檔存儲方面的低效率問題，設(shè)計(jì)了一個(gè)基于 NewDietz 編碼方案的動態(tài) XML數(shù)據(jù)存儲模式，并開發(fā)了一個(gè)以 XML 方式表達(dá)的水利空間數(shù)據(jù)的存儲與展示模塊。具體的設(shè)計(jì)開發(fā)表明，與 XRel 關(guān)系邏輯模式相比，新的存儲方案可以有效地支持 XML 文檔在關(guān)系存儲模式中的更新，并具有可操作性。隨著近年來非關(guān)系型數(shù)據(jù)存儲模式的發(fā)展和新的 XML 文檔編碼技術(shù)的出現(xiàn)[11-13]，為 XML 等非結(jié)構(gòu)化或半結(jié)構(gòu)化文檔的高效存儲與檢索提供了更多可能，下一步將擴(kuò)展本方案的應(yīng)用范圍，更好地支持基于 XML 數(shù)據(jù)的水利信息系統(tǒng)建設(shè)。

圖2 基于 NewDietz 編碼和 XRel 2 種關(guān)系存儲模式的性能