基于结构化连接的多版本XML文档查询处理

维普资讯

第２３卷第４期　

苏州科技学院学报（自然科学版）　

Ｖ０Ｉ．２３　Ｎｏ．４　

２００６年ｌ２月　

ｊｏｕｒｎａｌ　ｏｆ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ　ｏｆ　Ｓｕｚｈｏｕ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ）　

Ｄｅｃ．２ｏｏ６　

基于结构化连接的多版本ＸＭＬ文档查询处理　

丁　峥１，２，白　云　

ｆ１．苏州科技学院计算中心，江苏苏州２１５０１１；２．苏州大学计算机科学与技术学院，江苏苏州２１５ｏｏ￣　

摘要：阐述了现有ＸＭＬ文档的版本管理机制所采用的关键技术，总结其存在的不足，然后设计了新的ＸＭＬ文档　

节点的编码方案并生成结构化连接所需要的四元组结构，在此基础上对一个经典结构连接算法进行了扩展，使之支　

持多版本ｘＭＬ文档的查询。　

关键词：ＸＭＬ；多版本；结构化连接　

中圈分类号：ＴＰ３１　１　文献标识码：Ａ　文章编号：１６７２—０６７９（２００６）０４－－００６４－０５　

ＸＭＬ版本管理的目的是不仅可以让使用者操作最新版本的ＸＭＬ文件，还可以取回旧版本的ＸＭＬ文　

件，方便ＸＭＬ文件版本发展过程的追踪。最直接的方法是每一次ＸＭＬ文件变动后都另存一份，这样会造成　

许多资料重复存储。当文件内容比较多时，会占用大量的存储空间。为降低存储冗余，加快版本撷取速度，需　

要对ＸＭＬ文档进行有效的版本管理，ＸＭＬ版本管理的目标是以较小空间存储多个版本文件，以较快速度取　

回所需要的版本。　

１　ＸＭＬ版本管理现有方法及其不足　

目前已提出的ＸＭＬ文件版本管理技术有Ｄｉｆ－ｂａｓｅｄ［卜。１、Ｔｉｍｅｓｔａｍｐｓ—ｂａｓｅｄｌ４１等方式。　

Ｄｉｆｆ－ｂａｓｅｄ方法主要是利用ｅｄｉｔ—ｓｃｒｉｐｔ语法（ｉｎｓｅｒｔ，ｄｅｌｅｔｅ，ｕｐｄａｔｅ，ｍｏｖｅ）来记录同一份的ＸＭＬ文件不同　

版本之间的改变。文献［１】是存储最后一次修改的ＸＭＬ文件版本，利用ｆｏｒｗａｒｄ　ｃｏｍｐｌｅｔｅ　ｄｅｌｔａｓ来记录两个　

ＸＭＬ文件版本的改变。Ｆｏｒｗａｒｄ　ｃｏｍｐｌｅｔｅｄ　ｄｅｌｔａｓ用于获取之前的ＸＭＬ文件版本，并且经反转Ｆｏｒｗａｒｄ　ｃｏｍ—　

ｐｌｅｔｅｄ　ｄｅｌｔａｓ后，又可重新返回上一次修改的ＸＭＬ文件版本。文献【２】存储第一次和最后一次修改的ＸＭＬ文　

件版本，并加上ｆｏｒｗａｒｄ　ｃｏｍｐｌｅｔｅ　ｄｅｌｔａｓ的特性，改进了获取ＸＭＬ文件版本的速度。文献【３】首先完整地存储　

最原始的ＸＭＬ文件版本，当ＸＭＬ文件版本被连续修改时，只会存储新插入文件的部分，而未改变的部分则　

是使用ｒｅｆｅｒｅｎｃｅ　ｒｅｃｏｒｄ来指向前一版本相同数据的位置　文献【４Ｊ以Ｔｉｍｅｓｔａｍｐｓ—ｂａｓｅｄ方法为基础，提出了　

以时间戳与数值范围为ＸＭＬ文件版本中每个结点进行编码。但是没有讨论如何明确定义结点数值范围中　

的间距值ｒａｎｇｅ，也没有说明当新的ＸＭＬ文件版本加入时（例如，新增、删除和修改ＸＭＬ文档），原来ＸＭＬ文　

档结点的数值范围应该如何调整。　

这几种方法的一个共同缺点是无法直接取出中间某一个版本的内容。查询时需要从第一个版本往后推　

算或是从最后一个版本往前推算，恢复到特定ＸＭＬ文件版本，才能查询该版本的内容。本文笔者探讨了多　

版本ＸＭＬ文档的结构查询，并不需要以恢复版本为前提，而是利用新的结点编码方案和扩展的结构连接算　

法，直接查询特定版本中两结点之间的结构关系。　

２多版本ＸＭＬ文档的编码方法　

选择ＸＭＬ文件编码的方法。主要考虑３个因素：维护的成本、重建文件的效率和查询的速度。本文所采　

用的Ｎｕｍｂｅｒｉｎｇ　Ｓｃｈｅｍａ在Ｚｈａｎｇ编码的基础上进行了扩展。　

【收稿日期】２００６－０６－１４　

【作者简介】丁峥（１９７８－），女，江苏仪征人，硕士研究生，研究方向：ＸＭＬ数据。　

维普资讯

第４期　丁　峥等：基于结构化连接的多版本ＸＭＬ文档查询处理　６５　

结点编码的定义如下：　

（Ｉ）每个结点看作是一个四元组（Ｄｏｃｌｄ，Ｓｔａｒｔｐｏｓ：Ｅｎｄｐｏｓ，Ｌｅｖｅｌ，Ｖｓｔａｒｔ：Ｖｅｎｄ），其中Ｄｏｃｌｄ为结点所在的　

文档ＩＤ；Ｓｔａｒｔｐｏｓ为结点在文档中的开始值；Ｅｎｄｐｏｓ为结点在文档中的结束值；ｅｖＬｅｌ为结点在文档中所嵌套　

的深度，即在文档树中的层次。Ｖｓｔａｒｔ，Ｖｅｎｄ分别表示版本起始值和版本终止值。　

（２）叶子结点的Ｓｔａｒｔｐｏｓ值和Ｅｎｄｐｏｓ值相等　

图１是一个多版本ＸＭＬ文件及其结点编码，结点编码中省略了Ｄｏｃｌｄ。多版本ＸＭＬ文件是将原始版本　

及其后的版本差异整合成一个ＸＭＬ文件。这个多版本ＸＭＬ文件包含了３个版本，版本１只有ｂｏｏｋｓ结点和　

左边分支的ｂｏｏｋ结点，这些结点一直到版本３依然保留，因此每个节点的（Ｖｓｔａｒｔ：Ｖｅｎｄ）都是（１：３），版本２是　

ｂｏｏｋｓ结点增加了右边的ｂｏｏｋ结点以及４个子结点，因此，这些结点的Ｖｓｔａｒｔ是２，这些结点在第三个版本　

中继续保留，惟独删除了右边ｂｏｏｋ结点的第３个子结点ａｕｔｈｏｒ，因此，该ａｕｔｈｏｒ结点的Ｖｅｎｄ是２，其他结点　

的Ｖｅｎｄ均为３。　

图１　多版本ＸＭＬ文件（版本１—３）以及编码方式　

改进后的Ｎｕｍｂｅｒｉｎｇ　Ｓｃｈｅｍａ存在如下关系：　

（１）对于树Ｔ的相同版本中的两个给定结点ｕ和ｖ，ｕ是ｖ的父亲结点当且仅当ｕ．ｓｔｍ＇ｔｐｏｓ＜ｖ．ｓｔａｒｔｐｏｓ＜ｕ．　

ｅｎｄｐｏｓ，ｕ．Ｌｅｖｅｌ：ｖ．ｅＬｖｅｌ＋１；（２）对于树Ｔ的相同版本中的两个给定结点ｕ和ｖ，ｕ是ｖ的左兄弟结点当且仅当　

ｕ．ｓｔａｒｔｐｏｓ＜ｖ．ｓｔａｒｔｐｏｓ，ｕ．ｅｎｄｐｏｓ＜ｖ．ｅｎｄｐｏｓ，ｕ．ｅＬｖｅｌ＝ｖ．ｅＬｖｅｌ；（３）对于树Ｔ的相同版本中的两个给定结点ｕ和ｖ，　

ｕ是ｖ的祖先结点当且仅当ｕ．ｓｔａｒｔｐｏｓ＜ｖ．ｓｔａｒｔｐｏｓ＜ｕ．ｅｎｄｐｏｓ；（４）对于树Ｔ，如果要撷取版本Ｖ的结点，只需要　

结点ｕ满足ｕ．Ｖｓｔａｒｔ＜Ｖ＜ｖ．Ｖｅｎｄ条件即可。　

改进后的Ｎｕｍｂｅｒｉｎｇ　Ｓｃｈｅｍａ具有两方面优良的特性：（１）支持结点之间的包含关系，包括父子关系、兄　

弟关系、祖先关系；（２）支持直接获取特定版本的结点。这就为不恢复版本而直接查询特定版本的结点之间　

的结构关系奠定了基础，也为结构化连接的算法的扩展提供了可能。　

３多版本ＸＭＬ文档的结构查询　

３．１查询概述　

ＸＭＬ查询的核心是ＸＰａｔｈ路径表达式查询。通常，一个复杂的ＸＰａｔｈ路径表达式能够被分解为如下子　

表达式的组合：（１）由１个单一元素或单一属性构成的表达式；（２）由２个元素或１个元素与１个属性构成　

的满足包含关系（祖先／后裔关系、双亲／孩子关系）的表达式；（３）由１个元素或１个属性与１个搜索关键字　

构成的表达式；（４）由２个元素构成的位置关系的表达式（之前／之后关系、左兄弟／右兄弟关系等）。　

结构连接，是先将查询路径切断，也就是上面所说的表达式分解，以２个元素为一组的方式分别处理，　

最终需要将结构连接得到的结果组合起来得到最终查询结果。结构连接算法，是利用每个元素的Ｓｔａｒｔｐｏｓ：　

Ｅｎｄｐｏｓ值来判断父子或者祖先一后代关系。高效的算法是查询处理的关键。目前已经提出了许多结构连接的　

算法，但都不支持多版本的ＸＭＬ文档。文献【５】的Ｓｔａｃｋ—Ｔｒｅｅ—Ｄｅｓｃ连接算法代表了结构连接算法的先进水　

平，但是该算法不支持具有版本的ＸＭＬ文档，下面笔者在原算法基础上扩展版本查询的功能。　

维普资讯

苏州科技学院学报（自然科学版）　２０ｏ６年　

３．２查询算法的扩展　

算法扩展的前提是产生与结构关系（ｅ１）ｅ　）（祖先后代关系或者父子关系）中结点ｅ　匹配的列表Ａｌｉｓｔ＝　

（ａｌ，ａ　…）和结点ｅ　匹配的列表Ｄｌｉｓｔ（ｄ　。ｄ　…）。并且每个列表根据它的元素的（ＤｏｃＩｄ，Ｓｔａｒｔｐｏｓ）值进行排序。列　

表Ａｌｉｓｔ和列表Ｄｌｉｓｔ能够从存储ＸＭＬ的数据库中产生，例如，一个原生的ＸＭＬ数据库系统能够将ＸＭＬ数　

据树中每个元素结点存储为具有属性（Ｅｌｅｍｅｎｔｔａｇ，ＤｏｃＩｄ。Ｓｔａｒｔｐｏｓ，Ｅｎｄｐｏｓ，Ｌｅｖｅｌ，Ｖｓｔａｒｔ。Ｖｅｎｄ）的对象，利用　

索引查找与给定元素标签相匹配的结点集，然后该结点集按照（Ｄｏｃｌｄ，Ｓｔａｒｔ）值进行排序从而产生列表Ａｌｉｓｔ　

和列表Ｄｌｉｓｔ。　

Ｓｔａｃｋ—Ｔｒｅｅ—Ｄｅｓｃ—ＭＶ算法的基本思想是：引进了栈的机制来存放要连接的元素。栈用来存放一个嵌套　

祖先元素接点的序列，假设栈中自底到顶依次存放了ｎ个结　４｛ｓ－　…，Ｓｎ｝，对于每一个结点Ｓｔ（　∈【２，ｎ］），它是　

结点ｆｉ　。的后裔结点。在归并过程中，对于Ａｌｉｓｔ列表中扫描得到的一个新结点ａ，如果它是当前栈顶结点的　

后代时，并且它满足版本撷取的条件。即ａ．Ｖｓｔａｒｔ＜Ｖ＜ａ．Ｖｅｎｄ，那么该结点进栈。对于Ｄｌｉｓｔ列表中扫描得到的　

一

个新结点ｄ，如果满足版本撷取的条件，即ｄ．Ｖｓｔａｒｔ＜Ｖ＜ｄ．Ｖｅｎｄ，并且如果它是当前栈顶结点的后代时，那么　

它是栈中所有元素的后代。而且。可以保证它不是Ａ中其它任一结点的后代。因此，结点ｄ与栈中所有结点　

的连接结果就可以被输出了。对于Ｄｌｉｓｔ列表中扫描得到的一个新结点ｄ，如果它不是当前栈顶结点的后代，　

那么可以得出结论：目前的栈顶元素在Ｄｌｉｓｔ中没有进一步的后代结点，因此，可以将栈顶元素退栈了，并且　

判断结点ｄ是否是新的栈顶结点的后裔，直到栈为空。　

下面给出具体算法：　

算法Ｓｔａｃｋ—Ｔｒｅｅ—Ｄｅｓｃ—ＭＶ（１ｉｓｔ　Ａ，ｌｉｓｔ　Ｄ，ｉｎｔ　Ｖ）　

输入：两个参与连接的表Ａｌｉｓｔ和Ｄｌｉｓｔ。需要获取的ＸＭＬ文件的版本Ｖ　

输出：按后裔有序的连接结果ｏｕｔｐｕｔ　

（１）ａ＝Ａｌｉｓｔ一＞ｆｉｒｓｔＮｏｄｅ；ｄ＝Ｄｌｉｓｔ－＞ｆｉｒｓｔＮｏｄｅ；０ｕｔｐｕｔｌｉｓｔ＝ＮＵＬＬ；　

（２）ｄｏ　ｗｈｉｌｅ（ｔｈｅ　ｉｎｐｕｔ　ｌｉｓｔｓ　ａｒｅ　ｎｏｔ　ｅｍｐｔｙ　ｏｒ　ｔｈｅ　ｓｔａｃｋ　ｉｓ　ｎｏｔ　ｅｍｐｔｙ）　

（３）ｉｆ（ａ．ＳｔａｒｔＰｏｓ＞ｓｔａｃｋ一＞ｔｏｐ．ＥｎｄＰｏｓ）＆＆（ｄ．ＳｔａｒｔＰｏｓ＞ｓｔａｃｋ一＞ｔｏｐ．ＥｎｄＰｏｓ））ｔｈｅｎ　

（４）【ｕｐｌｅ＝ｓｔａｃｋ一＞ｐｏｐＯ；　

（５）ｅｌｓｅ　ｉｆ（ａ．ＳｔａｒｔＰｏｓ＜ｄ．ＳｔａｒｔＰｏｓ）ｔｈｅｎ　

／　进栈前需要对ａ的版本进行判断　／　

（６）ｉｆ　ａ．ｖｓｔａｒｔ＜ｖ＜ａ．ｖｅｎｄ　ｔｈｅｎ　

（７）ｓｔａｃｋ－＞ｐｕｓｈ（ａ）　

（８）ｅｎｄｉｆ　

（９）ａ＝ａ－＞ｎｅｘｔＮｏｄｅ　

（１０）ｅｌｓｅ　

／＊ｄ与栈中元素连接前需要进行版本的判断　／　

（１　１）ｉｆ　ｄ．ｖｓｔａｒｔ＜ｖ＜ｄ．ｖｅｎｄ　ｔｈｅｎ　

（１２）ｆｏｒ（ａ￣＝ｓｔａｃｋ一＞ｂｏｔｔｏｍ；ａｌ！＝ＮＵＬＬ；ａｌ＝ａ１一＞ｕｐ）　

（１　３）ａｐｐｅｎｄ（ａｊ，ｄ）ｔｏ　Ｏｕｔｐｕｔｌｉｓｔ　

（１４）ｅｎｄｉｆ　

（１　５）ｄ＝ｄ－＞ｎｅｘｔＮｏｄｅ　

（１６）ｅｎｄｉｆ　

（１７）ｌｏｏｐ　

父子关系的Ｓｔａｃｋ－Ｔｒｅｅ—Ｄｅｓｃ更简单，因为Ｄｌｉｓｔ节点只能跟栈顶节点合并。因此，算法ｌ２一ｌ５行的循环　

没有必要，只要将其替换为：ｉｆ（ｄ．ｅＬｖｅｌ＝ｓｔａｃｋ－＞ｔｏｐ．Ｉ￣ｖｅｌ＋１）｛ａｐｐｅｎｄ（ｓｔａｃｋ－＞ｔｏｐ，ｄ）ｔｏ　Ｏｕｔｐｕｔｌｉｓｔ｝即可。　

３３算法正确性证明　

给定两个输入序列Ａｌｉｓｔ、Ｄｌｉｓｔ，均按ＳｔａｒｔＰｏｓ的增序排列，算法Ｓｔａｃｋ—Ｔｒｅｅ—Ｄｅｓｃ—ＭＶ会正确地得出所有　

维普资讯

第４期　丁　峥等：基于结构化连接的多版本ＸＭＬ文档查询处理　６７　

的二元关系结果（越，ｄ　其中　∈Ａｌｉｓｔ与ｄ，∈Ｄｌｉｓｔ　

从两个方面来证明：　

（１）Ｖ　ａｉ，　∈Ａｌｉｓｔ，　∈Ｄｌｉｓｔ，若４，　存在结构化关系（父一子或祖先一后代关系），则　，　）必会被输出到　

Ｏｕｔｐｕｔｌｉｓｔ中。如果４＝＝）ｄ，，故必有ａ１，ａ２，．．．．，ａｌ－１］ｄ，（此处假设ａ。是４—１的后代）。算法Ｓｔａｃｋ－Ｔｒｅｅ－Ｄｅｓｃ－ＭＶ　

的第６条语句和第７条语句保证了ａ　，ａ：，．．．．，ａ¨和４中符合版本撷取条件的结点均会进栈，然后完成连接　

操作，从而　，　必然会被输出到Ｏｕｔｐｕｔｌｉｓｔ中；（２）（Ｖ　ａｉ，　）∈Ｏｕｔｐｕｔｌｉｓｔ，ａ　∈Ａｌｉｓｔ，　∈Ｄｌｉｓｔ，则４，　必存在包　

含关系，即ａｉｄ４。也就是说，Ｏｕｔｐｕｔｌｉｓｔ中输出的都是正确的二元包含关系。　

首先，整个算法保证了　，ｄＪ）∈Ｏｕｔｐｕｔｌｉｓｔ中的ａｉ，　必然来自于Ａｌｉｓｔ，Ｄｌｉｓｔ；其次，假设ａｉ，ｄ，不存在包含关　

系，那么，在算法的输出出口处必然会有不满足ａ，２ｄ￣的条件，使得ａ　，　不满足相应的包含条件却仍被输出，　

但考察算法Ｓｔａｃｋ—Ｔｒｅｅ—Ｄｅｓｃ—ＭＶ可知，唯一的退栈结构化连接运算输出在第４条语句，其严格的Ｉｆ包含条　

件使得上述情况不会发生。　

故不可能出现（ａ“　∈Ｏｕｔｐｕｔｌｉｓｔ，但ａｉ］ｄ『不成立的情况。　

３．４算法的执行过程　

下面将用一个查询实例来说明算法的执行过程。如图２所示，其中左边是一个多版本ＸＭＬ文档的树状　

结构（版本１～３），每个结点标出了＜Ｖｓｔａｒｔ：Ｖｅｎｄ＞，此时要查询版本２的祖孙／后代关系，即ａ／ｄ关系，则算法　

的执行过程如图２右侧所示（线段长度代表结点的［Ｓｔｍ＇ｔｐｏｓ：Ｅｎｄｐｏｓ］区间大小）。可以看出，算法仅需要对祖　

先列表和后代列表扫描一次就可以实现包含关系的结构连接，算法的执行只需要８步，每一步的含义图２　

亦有说明，不再赘述。　

因　

Ｓｔｅｐｌ　Ｓｔｅｐ２　Ｓｔｅｐ３　Ｓｔｅｐ４　Ｓｔｅｐ５　ＳｔｅＰ６　Ｓｔｅｐ７　

口　

Ｓｔｅｐ８　

图２　Ｓｔａｃｋ—Ｔｒｅｅ—Ｄｅｓｃ—ＭＶ的执行过程　

４结语　

多版本ＸＭＬ文档的研究是ＸＭＬ研究领域相对独立的一个研究方向，目前主要由加州大学洛杉矶分校　

和台湾嘉义大学从事这方面的研究，国内此项研究尚处于起步阶段。不同于以往研究，本文提出了一种改进　

的编码方法，并利用扩展的结构连接算法，突破版本恢复的限制，直接地查询任意版本的内容。至于如何提　

出一种新的支持多版本ＸＭＬ文档的索引机制，加快查询的速度，是笔者今后努力的方向。　

参考文献：　

ｌ１　Ｉ　Ｍａｒｉａｎ，Ａｂｉｔｅｂｏｕｌ　Ｓ，Ｃｏｂｅｎａ　Ｇ，ｅｔ　ａ１　Ｃｈａｎｇｅ－ｃｅｎｔｒｉｃ　ｍａｎａｇｅｍｅｎｔ　ｏｆ　ｖｅＩ＇ｓｉｏｎ８　ｉｎ蛐ＸＭＬ　ｗａｒｅｈｏｕｓｅ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　２７ｔｈ　ＶＬＤＢ，Ｒｏｍｅ：Ｓｐｒｉｎｇｅｒ　

２００１．　

［２１　Ｒａｙｍｏｎｄ　Ｋ　Ｗｏｎｇ。Ｎｉｃｏｈ　Ｌａｉｎ．Ｍａｎａｇｉｎｇ　ａｎｄ　Ｑｕｅｒｙｉｎｇ　Ｍｕｌｔｉ—Ｖｅｒｓｉｏｎ　ＸＭＬ　Ｄａｔａ　ｗｉｔｈ　Ｕｐｄａｔｅ　Ｉｘ，ｇｇｉｎｇ｛Ｃｌ／／ＡＣＭ，Ｂｅｒｌｉｎ：ＤＬＲ，２００２・　

【３Ｊ　Ｃｈｉｅｎ　Ｓ　Ｙ，Ｔｓｏｔｒａｓ　Ｖ　Ｊ，Ｚａｎｉｏｌｏ　Ｃ．Ｅｆｆｉｃｉｅｎｔ　Ｍａｎａｇｅｍｅｎｔ　ｏｆ　Ｍｕｈｉｖｅｒｓｉｏｎ　Ｄｏｃｕｍｅｎｔｓ　ｂｙ　Ｏｂｊｅｃｔ　Ｒｅｆｅｒｅｎｃｉｎｇ［Ｃ］／／ｌｎ　Ｐｒｃ　ＶＬＤＢ　２００１，Ｒｏｍｅ　ｏ

维普资讯

苏州科技学院学报（自然科学版）　２００６卑　

［４１　Ｃｈｉｅｎ　Ｓ￣，Ｔｓｏｔｒａｓ　ｖ　ｊ，ｚ明ｉｏｌ。Ｃ．ｅ￡ｌｌｆ．Ｓｔｏｒｉｎｇ　ａｎｄ　Ｑｕｅｙｒｉｎｇ　Ｍｕｌｔｉｖｅｒｓｉ。ｎ　ＸＭＬ　Ｄｏｃｕｍｅｎｔｓ　ｕｓｉｎｇ　Ｄｕｒａｂｌｅ　Ｎｏｄｅ　Ｎｕｍ　【ｃＪ／／Ｐ呲ｔＪｆ　ｗｌｓＥ，　

Ｎｅｗ　Ｏｒｌｅａｎｓ：Ｓｐｒｉｎｇｅｒ，２００１．　

１５】ＡＬ—Ｋｈａｌｉｆａ　ｓ，ＪａｇａｄｉＢｈ　Ｈ　Ｖ，Ｋ。ｕｄ聃Ｎ，ｅ￡　．Ｓｔｒｕｃｔｒａｌ　Ｊｏｉｎｓ：Ａ　Ｐｒｉｍｉｔｉｖｅ　ｆｏｒ　Ｅｆｉｆｃｉｅｎｌ　ＸＭＬ　Ｑｕｅｒｙ　Ｐａｔｔｅｒｎ　Ｍ　ａＩｃｈｊｎｇｌｃ】／／Ｐｒｏｃｅｅｄ　ｎｇｓ　０ｆ山ｅ　ｌ８【ｂ　

ｌＥＥＥ　ＩＣＤＥ　ｉｎｔｅⅡｌａ【ｊ０ｎａｌ　ｏｏｎｆｅｒｅｎｃｅ　ｏｎ　ｄａｔ８　ｅｎｇｉｎｅｅｒｌｎｇ．Ｓａｎ　Ｊｔ　，Ｃａｌｉｆｏｒｎｉａ．ＵＳＡ。Ｆ＇ｅｂｍａｒｙ　２６一ｍａｒｃｈ　１，２００２・１Ｊｏｓａｉｍｎｉｔｏｓ：１ＥＥＥ　Ｃ。ｍｐ　ｔ。　

ｃｌｅｔｖ．２Ｏ０２：ｌ４１－ｌ５２．　

Ｑｕｅｒｙ　Ｐｒｏｃｅｓｓｉｎｇ　ｆｏｒ　Ｍｕｌｔｉ－ｖｅｒｓｉｏｎ　ＸＭＬ　Ｂａｓｅｄ　ｏｎ　Ｓｔｒｕｃｔｕｒａｌ　ｊｏｉｎ　

ＤＩＮＧ　Ｚｈｅｎｇ　一，ＢＡＩ　Ｙｕｎ　

ｆ１。Ｃａｌｃｕｌａｔｉ。ｎ　Ｃｅｎｔｅｒ，ＵＳＴＳ，Ｓｕｚｈ。ｕ　２　１　５０　１　１，Ｃｈｉｎａ；２．Ｃ。ｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏ１。ｇＹ　Ｓｃｈｏ０１，Ｓｏｏｃｈｏｗ　ｕｎｉＶｅｒ－　

ｓｉｔｙ，Ｓｕｚｈｏｕ　２１　５００６，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ　ｗｅ　ｓｕｍｍａｒｉｚｅ　ｔｈｅ　ｖａｒｉ。ｕｓ　ｋｅｙ　ｔｅｃｈｎｉｑｕｅｓ　ｅｍｐｌ。ｙｅｄ　ｂｙ　ｍｕｌｔｉ—Ｖｅｒｓｉ。ｎ　ＸＭＬ　ｄ。ｃｕｍｅｎｔｓ　

ｍａｎａｇｅｍｅｎｔ，Ｐ。ｉｎｔｉｎｇ。ｕｔ　ｔｈｅ　ｄｅｆｅｃｔｓ，ａｎｄ　ｔｈｅｎ　ｄｅｓｉｇｎ　ａｎ　ｉｍｐｒｏｖｅｄ　ｃ。ｄｉｎｇ　ｍｅｔｈ。ｄ・Ｏｎ　ｔｈｅ　ｂａｓｉｓ　ｏｆ　ｔｈｉｓ，ｗｅ　ｅｘ—　

ｔｅｎｄ　ｃｌａｓｓｉｃ　ｓｔｒｕｃｔｕｒａｌ　ｊｏｉｎｉｎｇ　ａｌｇｏｒｉｔｈｍ　ＳＯ　ｔｈａｔ　ｉｔ　ｃａｎ　ｓｕｐｐｏｒｔ　ｍｕｌｔｉ—ｖｅｒｓｉｏｎ　ＸＭＬ　ｄｏｃｕｍｅｎｔｓ・　

Ｋｅｙ　ｗｏｒｄｓ：ＸＭＬ；ｍｕｌｔｉ—ｖｅｒｓｉｏｎ；ｓｔｒｕｃｔｕｒａｌ　ｊｏｉｎ　

矫　！　

・　采　

（上接第５４页）　

Ｒｅｓｅａｒｃｈ　ｏｆ　Ｍｅｔｈｏｄ　ｆｏｒ　ＧＰＳ　Ｌｅｖｅｌｉｎｇ　Ｆｉｔｔｉｎｇ　ｉｎ　Ｓｕｚｈｏｕ　

ＷＡＮＧ　Ｙｉｎｇ　．ＹＵＡＮ　Ｍｉｎｇ　，ＹＡＮ　Ｙｏｎｇ　，ＦＡＮ　Ｙｉ—ｗｅｌｌ　

（１．Ｄｅｐｔ、。ｆ　Ｕｒｂａｎ　ａｎｄ　Ｅｎｖｉｒｏｎｍｅｎｔａ１　Ｓｃｉｅｎｃｅ￣ＵＳＴＳ，Ｓｕｚｈ。ｕ　２　１　５０１　１，Ｃｈｉｎａ；２．Ｎａｔｉ。ｎａ１　Ｌａｂ。ｒａｔ。ｒｙ　ｆ０ｒ　Ｉｎｆｏ珊ａ－　

ｔｉｏｎ　Ｅｎｇｉｎｅ　ｎｇ　ｉｎ　Ｓｕｗｅｙｉｎｇ，Ｍａｐｐｉｎｇ　ａｎｄ　Ｒｅｍｏｔｅ　Ｓｅｎｓｉｎｇ，ｗｕｈａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｗｕｈａｎ　４３００７９，Ｃｈｉｎａ；３‘　

Ｓｕｚｈｏｕ　Ｓｕｒｖｅｙｉｎｇ　ａｎｄ　Ｍａｐｐｉｎｇ　Ｉｎｓｔｉｔｕｔｅ　Ｌｉｍｉｔｅｄ　Ｌｉａｂｉｌｉｔｙ　Ｃｏｍｐａｎｙ，Ｓｕｚｈ。ｕ　２　１　５００６，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｔｈｉｓ　ｐａｐｅｒ　ａｄｏｐｔｓ　ｔｈｅ　ｍｅｔｈｏｄ　ｏｆ　ｈｅｉｇｈｔ　ｆｉｔｔｉｎｇ　ｔｏ　ｓｏｌｖｅ　ｔｈｅ　ｎｏｒｍａｌ　ｈｅｉｇｈｔ　ｏｆ　ＧＰＳ　ｐｏｉｎｔｓ－Ｂａｓｅｄ　ｏｎ　ｔｈ。　

ｅｘａｍｐ１ｅ　ｏｆ　Ｓｕｚｈｏｕ　ＧＰＳ　ｎｅｔｗｏｒｋ，ｔｈｅ　ａｕｔｈｏｒｓ　ｉｎｔｒｏｄｕｃｅ　ｔｈｅ　ｐｒｉｎｃｉｐｌｅ　ａｎｄ　ｍｅｔｈｏｄ　ｏｆ　ＧＰＳ　ｌｅｖｅｌｉｎｇ　ｆｉｔｔｉｎｇ，ｔｈｅｎ　ａｎ—　

ａｌｖｚｅ　ｔｈｅ　ｆｉｔｔｉｎｇ　ｐｏｉｎｔ８　ｏｆ　ｄｉｆｆｅｒｅｎｔ　ｎｕｍｂｅｒ　ａｎｄ　ｔｈｅ　ｉｆｔｔｉｎｇ　ｒｅｓｕｌｔ　ｏｆ　ｎｏｍｒａｌ　ｈｅｉｇｈｔ　ｗｉｔｈ　ｄｉｆｅｒｅｎｔ　ｄｉｓｔｉｒｂｕｔｉｏｎ　ａｎｄ　

ｃｏｍｐａｒｅ　ｔｈｅ　ｒｅｓｕｉｔ　ｗｉｔｈ　ｔｈｉｒｄ　ａｎｄ　ｆｏｕｒｔｈ　ｃｌａｓｓｅｓ　ｌｅｖｅｌｉｎｇ　ａｃｈｉｅｖｅｍｅｎｔｓ．Ｉｔ　ｉｓ　ｃｏｎｃｌｕｄ。ｄ　ｔｈａｔ　ｔｈｅ　ｍｅｔｈ。ｄ　ｎ　ｅ　ｃｈ　

ｔｈｅ　ｌｅｖｅｌ　Ｇｒａｄｅ－３　ｐｒｅｃｉｓｉｏｎ　ｒｅｑｕｉｒｅｍｅｎｔ－　

Ｋｅｙ　ｗｏｒｄｓ：ＧＰＳ；ｈｅｉｇｈｔ　ａｎｏｍａｌｙ；ｑｕａｓｉ－ｇｅｏｉｄ；ｃｏｎｉｃｏｉｄ　ｆｉｔｔｉｎｇ