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

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

0 引言

隨著水利信息化的發(fā)展，各類水利信息系統(tǒng)的建設(shè)日益豐富。這些系統(tǒng)內(nèi)部的數(shù)據(jù)來(lái)源存在著很大差異，有來(lái)自關(guān)系數(shù)據(jù)庫(kù)中存儲(chǔ)的結(jié)構(gòu)化水利業(yè)務(wù)數(shù)據(jù)，也有半結(jié)構(gòu)化的水利空間業(yè)務(wù)數(shù)據(jù)等。平臺(tái)架構(gòu)、通信方式和數(shù)據(jù)結(jié)構(gòu)的差異阻礙了不同水利信息系統(tǒng)之間數(shù)據(jù)的有效共享。XML（可擴(kuò)展標(biāo)記語(yǔ)言）作為一種半結(jié)構(gòu)化語(yǔ)言，具有良好的信息表達(dá)功能，因此在信息交換、數(shù)據(jù)存儲(chǔ)及異構(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ù)平臺(tái)信息共享的標(biāo)準(zhǔn)語(yǔ)言[3]，以及水利遙感元數(shù)據(jù)的存儲(chǔ)[4]。

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

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

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

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

1）對(duì)元素進(jìn)行 Dietz 編碼，分別獲得元素經(jīng)過(guò)先序和后序遍歷后得到的值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)識(shí)的向量代替為止；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

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