一种支持动态XML文档的存储模式设计与应用

贺 挺，杨 柳，陈真玄，杨 非

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

0 引言

随着水利信息化的发展，各类水利信息系统的建设日益丰富。这些系统内部的数据来源存在着很大差异，有来自关系数据库中存储的结构化水利业务数据，也有半结构化的水利空间业务数据等。平台架构、通信方式和数据结构的差异阻碍了不同水利信息系统之间数据的有效共享。XML（可扩展标记语言）作为一种半结构化语言，具有良好的信息表达功能，因此在信息交换、数据存储及异构数据集成方面拥有广泛的应用前景，并成为当前互联网上信息交换的主要标准。在水利信息系统数据集成方面，XML 被用于结构化和半结构化水利数据的表达[1]，异构水利业务数据的集成工具[2]，水利业务平台信息共享的标准语言[3]，以及水利遥感元数据的存储[4]。

XML 的存储主要有关系式和 NoSQL 2 种模式。对于 XML 文档的关系式存储，常采用 XRel模式，采用与关系数据库兼容的逻辑存储模式和索引方法对 XML 文档进行存储和检索[5]。XRel 通过SQL 语句实现 XML 文档的存储，能够很好地支持基于元素路径关系的 XML 数据查询（XPath）。但XRel 模式存在以下缺点：1）XRel 模式中 XML 文档的结构通过基于前序-后序关系的 Dietz 编码[6]存储，对动态 XML 文档的操作效率很低。原因在于当面临新元素插入或元素删除的情景时，XRel 模式需要重新对整个文档树进行编码，这不但改变了原有元素的编码值，更降低了文档的存储和检索效率。2）关系存储模式具有高度结构化特点，对于某些没有提供内部结构说明的 XML 文档，在存储过程中容易导致信息的丢失。为此，对 XRel 模式中的Dietz 编码方案进行改进，引入向量方法[7]，设计一个支持 XML 文档元素的动态插入或删除的编码方案——NewDietz，并且基于区间编码机制设计了新的 XML文档关系存储模式。

1 NewDietz 编码方案设计

在 Dietz 编码中，XML 文档的每一个元素的Dietz 编码表示为一个整数对 [Pre，Post]，Pre，Post分别为对 XML 文档进行先序和后序遍历后获得的元素数值。在直角坐标系中，对于 XML文档的任意 2 个元素V1[Pre1，Post1] 和V2[Pre2，Post2]，若V1的长度大于V2的长度，即Pre1＜Post2且Pre2＜Post1，则V1为V2的祖先元素。通过这种方式，XML 文档的每个元素被赋予唯一的 Dietz 编码。 Dietz 编码的优点是通过简单的遍历机制获得元素的编码值，并采用简易的判别方法得到 XML 文档任意 2 个元素的祖先-后裔关系，能够方便地实现文档在关系数据库中的存储。

在 NewDietz 编码方案中，XML 文档中的任意元素表示为一个三元数组 [Prev，Postv，L]，Prev和Postv分别称为元素的前序和后序向量编码，L表示元素在文档中的层次，用于判断任意 2 个元素的祖先-后裔关系。NewDietz 编码对 XML 文档元素的编码过程表示如下：

1）对元素进行 Dietz 编码，分别获得元素经过先序和后序遍历后得到的值i和j（i，j∈N）；

2）取i的最小值 1 和j的最大值n，分别赋予单位向量 [1，0] 和 [0，1]，取 1 和n的中值元素则中值元素的向量值为 [[1 + 0]，[0 + 1]]；

3）循环执行第 2 步，直到所有元素的先序遍历值都能够被一个可以唯一标识的向量代替为止；

4）由于所有元素经过先序和后序 2 种遍历得到的值的集合中的元素数值相同，只是在顺序上存在不同，因此元素的后序遍历值的向量可以通过与先序遍历值进行唯一映射表示，编码执行结束。

NewDietz 编码的基本原理是对 XML 文档树元素的 Dietz 编码值进行向量表示，因此在 NewDietz编码方案下对元素的祖先-后裔判断原理与 Dietz 编码是相似的，对于任意 2 个经过 NewDietz 编码的元素V1[[x1，y1]，[x2，y2]] 和V2[[x3，y3]， [x4,，y4]]，如果，且则V为V的祖先元素。12

对动态 XML 文档进行编码时需要考虑到文档在插入新元素或者删除元素过程中的编码问题，限于篇幅，本研究主要探讨对 XML 文档进行元素插入过程中的 NewDietz 编码过程。按照插入位置的不同，可以将元素的插入过程分为以下 4 种情况：在2 个兄弟元素之间插入新的兄弟元素，在祖先元素下插入新的最左后裔元素，在祖先元素下插入新的最右后裔元素，在后裔元素下插入新的后裔元素，如图 1 所示。

为了能够判断新插入元素的祖先-后裔关系，并且保证元素编码在关系模式中合理的存储长度，对4 种方法中的 4 种元素插入类型的 NewDietz 编码进行如下定义：

1）对于任意 2 个经过 NewDietz 编码的元素V1和V2，若V1和V2为 XML 文档中的 2 个兄弟元素，则定义新插入的元素V3的 NewDietz 编码为V3[[x1+x3，y1+y3]，[x2+x4，y2+y4]]。

2）对于 XML 文档树中的任意元素V1，若V2为V1在插入新元素前的最左边后裔元素，则在V1下插入 1 个新的最左边后裔元素V3后的 NewDietz 编码表示为V3[[x1+x3，y1+y3], [2x1+x3，2y1+y3]]。

图1 对 XML 文档元素进行插入操作的 4 种方式

3）若V1为 XML 文档中的任意元素，V2为V1在插入新元素前的最右边后裔元素，则在V1下插入1 个新的最右边后裔元素V4后的 NewDietz 编码表示为V4[[x2+x4，y2+y4]，[2x2+x4，2y2+y4]]。

4）若V1为一叶子元素，则在V1下插入 1 个后裔元素V3的 NewDietz 编码为

根据这 4 个定义，对于每个新插入元素，只需要对其本身进行 NewDietz 编码而无需对所有元素重新编码；此外，新插入元素的 NewDietz 编码的定义也符合编码的祖先-后裔判断，并且这种判断在关系模式中也是明显的。

2 支持 NewDietz 编码的 XML 文档关系存储模式设计

在对 XML 文档的相关研究中，与关系数据库的交互是一个重要的研究方向[8]，但关系数据库中元素-属性之间严格的二元结构特点与 XML 文档的半结构化特性之间存在着不可调和的矛盾，因此，在建立存储模式时需要提供 XML 文档结构的说明，且针对 XML 文档元素的祖先-后裔判断算法与关系模式应当具有良好的互补性，进而实现文档的存储。目前对 XML 文档的关系存储模式主要有以下 2 种模式：1）基于模式的存储。建立 DTD（文档类型定义） 或 Schema 模式图，通过模式图中对元素结构顺序的描述建立 XML 文档的存储索引算法，以进一步实现 XML 文档的关系存储。2）基于文档编码的存储。先按照文档-元素-属性-文本的结构对文档进行拆分、存储，然后采用预先定义的编码方法判断任意元素之间祖先-后裔关系，并对文档进行重构，这也是 XRel 模式采用的方式。本研究对第 2 种情况进行研究，即设计 NewDietz 编码在关系数据库中的存储模式。

基于 NewDietz 编码的关系存储模式由以下关系表组成：

1）文档表（Document table）。文档表用来存储XML 文档的基本信息，具体字段包括 XML 文档编号、名称、存储路径和时间。

2）元素表（Element table）。元素表存储 XML文档的元素信息，具体字段包括 XML 文档编号、元素名称、元素和父元素的先序-后序 NewDietz 编码，元素表通过 XML 文档编号和文档表建立关联。

3）元素属性表（Attribute table）。元素属性表存储 XML 文档的元素属性信息，具体字段包括 XML文档编号，以及元素的先序-后序 NewDietz 编码、属性名称、属性值、前缀，元素属性表通过 XML文档编号和元素的先序-后序 NewDietz 编码与文档表及元素表建立关联。

4）文本表（Text table）。文本表用来存储 XML文档元素的文本和数值信息，具体字段包括 XML文档编号、元素的先序-后序 NewDietz 编码、元素文本值，文本表通过 XML 文档编号和元素的先序-后序 NewDietz 编码，与文档表、元素表、元素属性表建立关联。

根据关系存储模式的定义，对于动态 XML 文档的关系存储具体实现过程表达如下：

1）使用 JDOM 工具包对 XML 文档进行解析，构建 XML 文档树；

2）对 XML 文档元素进行 NewDietz 编码；

3）对文档中所有元素的属性（名称、NewDietz编码、属性和数值）依照构建的关系逻辑模式进行存储。

对于新插入元素在基于 NewDietz 编码的关系模式中的存储，通过在 XML 文档树中新插入元素的NewDietz 编码定义，只需要提供新插入元素编码和父元素信息就可以直接在元素表中执行插入操作，而无需对整个 XML 文档在逻辑模式中的存储信息进行修改。

3 应用实例

为验证基于 NewDietz 编码模式的动态 XML 文档存储模式的可行性，采用 W3C 标准下的 JDom[9]和 XQEngine[10]及开源的 GeoTools 工具包设计了一个水利空间数据存储与展示模块。该模块以地理标记语言（GML）文档作为输入。GML 是开放地理信息系统协会（OGC）制定的一种基于 XML 的传输和存储地理信息的解决方案，是一种平台无关的空间信息公共编码标准。本研究对 4 类水利空间数据（水文站、水库、行政区划和河流）进行了 GML表达，具体存储和展示过程如下：1）存储过程。首先对待存储的空间数据进行 NewDietz 编码，然后按照定义的新关系模式对经过编码的 GML 文档进行分解存储。2）展示过程。按照 NewDietz 编码对GML 文档中元素的祖先-后裔规则，从关系模式中对文档进行重构并展示。

在算法复杂度分析方面，将基于 NewDietz 编码方案的存储模式与原有 XRel 的存储模式进行比较，对模块中存储的水利空间数据文档，分别执行 10，100，1 000，10 000 个元素的插入操作，性能比较的结果如图 2 所示，可以看出对于 10 和 100 个元素的插入操作，2 种模式之间没有显著的性能差别，而对于超过 1 000 个元素的插入操作，新的存储模式完成时间明显低于原有模式。与 Dietz 编码模式相比，NewDietz 编码方案可以很好地支持 XML 文档的动态更新，而且根据 NewDietz 编码方案设计的关系逻辑存储模式与 XRel 关系逻辑存储模式相比，不但支持文档在关系模式下的存储及重构，而且也兼顾到动态 XML 文档在关系模式下的存储。

4 结语

XML 作为一种数据格式描述的元语言标准，它的充足性、条理性、可扩展性和自描述性成为其作为数据模型描述语言的优势，在水利元数据库构建、异构水利信息系统业务数据集成和信息共享中起着重要的作用。目前关于 XML 文档在水利信息系统中的存储实践还鲜有研究，本研究针对 XRel 关系存储模式在动态 XML 文档存储方面的低效率问题，设计了一个基于 NewDietz 编码方案的动态 XML数据存储模式，并开发了一个以 XML 方式表达的水利空间数据的存储与展示模块。具体的设计开发表明，与 XRel 关系逻辑模式相比，新的存储方案可以有效地支持 XML 文档在关系存储模式中的更新，并具有可操作性。随着近年来非关系型数据存储模式的发展和新的 XML 文档编码技术的出现[11-13]，为 XML 等非结构化或半结构化文档的高效存储与检索提供了更多可能，下一步将扩展本方案的应用范围，更好地支持基于 XML 数据的水利信息系统建设。

图2 基于 NewDietz 编码和 XRel 2 种关系存储模式的性能