基于DMB手机EPG系统的XML数据存储与传输技术研究

维普资讯

计算机科学２００７Ｖｏ１．３４Ｎ０．１　

基于ＤＭＢ手机ＥＰＧ系统的ＸＭＬ数据存储与传输技术研究　）　

吴君林许龙飞赵聚雪司徒浩臻　

（暨南大学计算机科学系　广州５１０６３２）　

摘要数字多媒体广播电子节目指南（Ｄ　ＥＰＧ）是数字电视行业内一项重要的应用，也是用户通过手机获取节目　

信息的必不可少的工具。在ＤＭＢ　ＥＰＧ系统中，减小文档大小、改善传输性能非常重要。本文探讨了ＥＰＧ系统的　

ＸＭＬ数据存储技术和基于传输性能的ＸＭＬ数据编码问题　在分析研究ＤＭＢ　ＥＰＧ协议原理的基础上，设计和实现　

了ＤＭＢ　ＥＰＧ系统的ＸＭＬ数据存储和二元编码过程，并对三种编码方案的性能进行了分析比较。　

关键词数字多媒体广播，电子节目指南，纯ＸＭＬ数据库，－－％ＸＭＬ　

Ｓｔｕｄｙ　ｏｆ　ＸＭＬ　Ｄａｔａ　Ｓｔｏｒａｇｅ　ａｎｄ　Ｔｒａｎｓｐｏｒｔａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ　Ｂａｓｅｄ　ｏｎ　ＤＭＢ　ＥＰＧ　

ＷＵ　Ｊｕｎ－Ｌｉｎ　ＸＵ　Ｌｏｎｇ－Ｆｅｉ　ＺＨＡＯ　Ｊｕ－Ｘｕｅ　ＳＩＴＵ　Ｈａｏ－Ｚｈｅｎ　

（Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｊｉｎａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｇｕａｎｇｚｈｏｕ　５１０６３２）　

Ａｂｓｔｒａｃｔ　Ｄｉｇｉｔａｌ　Ｍｕｌｔｉｍｅｄｉａ　Ｂｒｏａｄｃａｓｔｉｎｇ　Ｅｌｅｃｔｒｏｎｉｃ　Ｐｒｏｇｒａｍｍｅ　Ｇｕｉｄｅ（ＤＭ　ＥＰＧ），ｉｓ　ａｎ　ｉｍｐｏｒｔａｎｔ　ａｐｐｌｉｃａｔｉｏｎ　ｏｆ　

ｄｉｇｉｔａｌ　ＴＶ　ａｎｄ　ａｎ　ｉｎｄｉｓｐｅｎｓａｂｌｙ　ｔｏｏｌｓ　ｆｏｒ　ｕｓｅｒｓ　ｔｏ　ｋｎｏｗ　ａｂｏｕｔ　ｐｒｏｇｒａｍｓ　ｂｙ　ｍｏｂｉｌｅ　ｔｅｌｅｐｈｏｎｅ．Ｉｎ　ｔｈｅ　ＤＭＢ　ＥＰＧ　ｓｙｓｔｅｍ．　

ｉｔ’ｓ　ｖｅｒｙ　ｉｍｐｏｒｔａｎｔ　ｔｏ　ｒｅｄｕｃｅ　ｔｈｅ　ｄｏｃｕｍｅｎｔ　ｓｉｚｅ　ｏｆ　ｔｒａｎｓｐｏｒｔａｔｉｏｎ　ａｎｄ　ｉｍｐｒｏｖｅ　ｔｒａｎｓｐｏｒｔａｔｉｏｎ　ｅｆｆｉｃｉｅｎｃｙ．Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ．　

ＸＭＬ　ｄａｔａ　ｓｔｏｒｅ　ｔｅｃｈｎｏｌｏｇｙ　ｂａｓｅｅｌ　ｏｎ　ＥＰＧ　ｓｙｓｔｍｅ　ａｎｄ　ＸＭＬ　ｄａｔａ　ｅｎｃｏｄｉｎｇ　ｐｒｏｂｌｅｍ　ｂａｓｅｄ　ｏｎ　ｔｒａｎｓｐｏｒｔａｔｉｏｎ　ｅｆｆｉｃｉｅｎｃｙ　

ａｒｅ　ｄｉｓｃｕｓｓｅｄ．Ｏｎ　ｔｈｅ　ｂａｓｉｓ　ｏｆ　ｓｔｕｄｙｉｎｇ　ａ　ｓｅｒｉｅｓ　ｏｆ　ｐｒｏｔｏｃｏｌｓ，ｐｒｉｎｃｉｐｌｅｓ　ｏｆ　ＤＭＢ　ＥＰＧ。ｔｈｅ　ＤＭＢ　ＥＰＧ　ＸＭＬ　ｄｏｃｕｍｅｎｔ　

ｓｔｏｒａｇｅ　ｓｃｈｅｍｅ　ａｎｄ　ｂｉｎａｒｙ　ｅｎｃｏｄｉｎｇ　ｐｒｏｃｅｓｓ　ａｒｅ　ｄｅｓｉｇｎｅｄ　ａｎｄ　ｉｍｐｌｅｍｅｎｔｅｄ．Ａｄｄｉｔｉｏｎａｌｌｙ，ｔｈｅ　ｅｆｆｉｃｉｅｎｃｙ　ｏｆ　ｔｈｒｅｅ　ｅｎｃｏ—　

ｄｉｇｎ　ｓｃｈｅｍｅｓ　ｉｓ　ａｎａｌｙｚｅｄ　ａｎｄ　ｃｏｍｐａｒｅｄ．　

Ｋｅｙｗｏｒｄｓ　ＤＭ咀，ＥＰＧ，Ｎａｔｉｖｅ￣ＸＭＬ　ｄａｔａｂａｓｅ，１３ｉａｎｒｙ　ＸＭＬ　

１　引言　

电子节目指南（Ｅｌｅｃｔｒｏｎｉｃ　Ｐｒｏｇｒａｍｍｅ　Ｇｕｉｄｅ），简称　

ＥＰＧ，是数字电视技术中一项极其重要的应用，是用户获取　

大量电视节目信息必不可少的工具，也是优良的广告载体。　

随着在ＤＡＢ基础上发展起来的ＤＭＢ技术标准已成为移动　

手机电视的主流标准。ＤＭＢ手机电视的电子节目指南　

（Ｄ　ＥＰＧ）成为数字电视的新兴领域和研究热点。由于　

ＤＭＢ　ＥＰＧ系统采用了基于ＸＭＬ的数据交换技术，减少数据　

传输量改进传输性能就变得尤为重要。本文介绍了该系统前　

端机的ＸＭＬ数据存储技术以及基于传输性能的ＸＭＬ数据　

编码问题，并采用二元ＸＭＬ设计和实现了ＤＭＢ　ＥＰＧ的编　

码器。　

目前国际上研究　手机电视（ＥＰＧ是ＤＭＢ手机电视　

图１　ＤＭＢ　ＥＰＧ数据流程图　

系列产品之一）的主要有英国Ｇｃａｐ媒体集团、德国蓝宝、韩　

如图１所示，ＥＰＧ数据的转换过程经历３层，分别是　

国三星，ＬＧ、英国１ｖｒＰ、荷兰爱迪德等。国内的有北京悦龙　

数字广播、上海东方明珠、广东移动电视、香港商业电台等。　

Ｓｅｓｓｉｏｎ　Ｌａｙｅｒ（会话层）、传输层（ｔｒａｎｓｐｏｒｔ　Ｌａｙｅｒ）和网络层　

（ｎｅｔｗｏｒｋ　ｌａｙｅｒ）。　

ＤＭＢ　ＥＰＧ国内标准尚未出台，国内一些著名高校的专家对　

以下仅介绍会话层的数据流程。会话层的输人是一般的　

ＥＰＧ系统的研究主要是基于ＤＶＢ协议的数字电视ＥＰＧ，还　

较少看到基于啪（ＤＡＢ）协议方面的ＥＰＧ研究成果。　

无结构的ＥＰＧ数据，我们将它统一转换为关系数据库数据，　

ＥＰＧ系统是一组系统，我们称之为前端系统和后端系　

然后再转换为ＸＭＬ格式的ＥＰＧ数据。这里的ＸＭＬ数据符　

统　前端也就是ＥＰＧ数据的发送端，后端就是接收终端。因　

合ＥＰＧ的Ｓｃｈｅｍａ模式文档定义的数据规范；ＸＭＬ文档经过　

篇幅关系，本文研究仅涉及其前端系统的相关部分。　

二进制编码转换成二进制的ＥＰＧ数据；这些数据和一些　

Ｈｅａｄｅｒ参数经过ＭＯＴ编码器被封装成ＭＯＴ对象，ＭＯＴ对　

２　ＤＭＢ　ＥＰＧ系统的数据存储　

象的组成如图２所示。　

图１是ＤＭＢ　ＥＰＧ系统的前端机的ＥＰＧ数据的转换图。　

其中的Ｈｅａｄｅｒ　ｃｏｒｅ和ｈｅａｄｅｒ　ｅｘｔｅｎｓｉｏｎ由前面ｈｅａｄｅｒ　

吴君林硕士研究生，主要研究方向为数据库系统与知识工程，许龙飞教授，主要研究方向为数据库系统与知识工程等。　

・　９２・　

维普资讯

ｐａｒａｍｅｔｅｒｓ获得，ｂｏｄｙ由前面的ｂｉｎａｒｙ　ＥＰＧ　ｄａｔａ得到　这些　

ＭＯＴ　ｏｂｊｅｃｔｓ被分成一系列的片段（Ｓｅｇｍｅｎｔ），这些．Ｓｅｇｍｅｎｔｓ　

就是会话层的输出，如图３所示。　

７　ｂｙｔｅｓ　ｖａｒｉａｂｌｅ　ｖａｒｉａｂｌｅ　

ｈｅａｄｅｒＣＯｆ＇ｅ　Ｉ　ｈｅａｄ￣ｅｘｔｅｎｓｉｏｎ　

模式文档作为ＥＰＧ　ＸＭＬ数据库文档的逻辑模型。下面介绍　

该模型的工作机制及每个模块的功能。　

（１）ｘＭＬ资源库Ⅺ儿资源库是为ＸＭＬ文件的存储　

所申请的空间。由于ＸＭＬ文件按照处理流程可以分为４　

类：Ｏｒｉｇｉｎａｌ　ＸＭＬ，Ｂａｓｉｃ　ＸＭＬ，Ａｄｖａｎｃｅ　ＸＭＬ，Ｂｉｎａｒｙ　ＸＭＬ，　

图２　ＭＯＴ对象的结构　

ＦｉＩｅ　

因此在ＸＭＬ资源库中开辟四个子库分别用来存储对应的　

ＸＭＬ文件。在图５中，Ｏｒｉｇｉａｌｎ　ＸＭＬ是用来存储从关系数　

据库中的结构化数据并经过ＸＭＬ生成器后转换成的ＸＭＬ　

文件；Ｂａｓｉｃ　ＸＭＬ和Ａｄｖａｎｃｅ　ＸＭＬ分别用来存储从Ｏｒｉｇｉｎａｌ　

ＸＭＬ文档经过ＸＭＬ文件分级器后生成的Ｂａｓｉｃ　ＸＭＬ文档　

和Ａｄｖａｎｃｅ　ＸＭＬ文档；而Ｂｉａｒｎｙ　ＸＭＬ则用来存储从Ｂａｓｉｃ　

　Ｉ

ｅ

￣

ｒ

Ｍ　

。。∞

ｈｅａ　ｄ

Ｉ

ｔｅ

ｅ

Ｉ　

。。叩

ｒ　Ｂｏｄｙ　ｓｅｇｒｏａｎｔ１　Ｂ呻钾ｓ—ｚＩ．．．１呐ｓｅ唧ｎｔｎ　

、／‘＼　≮　…／一＼　／　＼　／　

Ｓｅｇｍｅｎｔａｔｉｏｎ　Ｓｅｇｍｅｎｔ　Ｓｅｇｍｅｎｔａｔｉｏｎ　Ｓｅｇｍｅｎｔ　

ｈｅａｄｅｒ　ｈｅｓｄｅｒ　

图３对象分块图　

我们针对会话层的数据转换过程设计了一种数据处理模　

型，如图４所示。　

图４　ｓｅｓｓｉｏｎ　Ｌａｙｅｒ数据处理模型　

在这个模型中有４个子模块，分别是ＸＭＬ文档转换器、　

ＸＭＬ分级器、ＸＭＬ文档编码器以及位于这３个模块中心的　

ＸＭＬ文档数据库，我们称之为ＥＰＧ　ＸＭＬ数据库。ＤＭＢ　

ＥＰＧ以ＸＭＬ文件作为分级编码的单位，所以ＸＭＬ数据库　

以文件作为ＥＰＧ数据的存储单位。下面根据ＥＰＧ数据的特　

点提出一种ＥＰＧ　ＸＭＬ数据库设计方案。　

在这个模型中，数据源经过ＸＭＬ转换器转换为符合　

Ｓｃｈｅｍａ模式的ＸＭＬ文档，这些文档存储在ｘＭＬ文档数据　

库资源库中。ＸＭＬ文档分级器取出资源库中的ＸＭＬ文件，　

将其分割成Ｂａｓｉｃ　Ｐｒｏｆｉｌｅ和Ａｄｖａｎｃｅ　ｐｒｏｆｉｌｅ　２个级别的文件，　

并将分级后的文件存储在ＸＭＬ资源库中。编码器取出分级　

后的ＸＭＬ文件将其编码成Ｂｉａｎｒｙ　ＸＭＬ文件，再将其存入　

ＸＭＬ资源库中。数据源在经过以上处理过程后，便可以将资　

源库中Ｂｉａｎｒｙ　ｘｍｌ文件上传到ＭＯＴ编码器进行后续处理。　

Ⅺ咀　级器　文件分　ｌ　ｏｒｉｇｉｎａ１Ⅺ儿ｌ　

｝关系Ｉ　ＸＭＬ　

编　

程　Ｉ　ＢａｓｉｃⅪ儿ｌ　

塑塑壁Ｆ　生成嚣　接　ｌ　－　ＡｄｖａｎｃｅＸＭＬ　ｌ　

ＸＭＬ　口　Ｉ　ＢｉｎａｒｙＸＭＬ　Ｉ　

文档编码器　ＸＭＬ资源库　

　＿

图５　ＥＰＧ　ＸＭＬ数据库模型　

如图５所示，它是基于文本的纯ＸＭＬ数据库，以文档作　

为数据的存储单位，对ＸＭＬ数据库的读取查询更新操作都　

是以文本进和文本出的方式进行的　该数据库中的每个文档　

都对应一个逻辑模型，由于ＥＰＧ数据是采用Ｓｃｈｅｍａ模式定　

义的，ＸＭＬ文档也必须符合ｅｐｇＳｃｈｅｄｕｌｅ－１１．ｘｓｄ，ｅｐｇＳＩ…　

１１．ｘｓｄ．，ｅｐｇＤａｔａＴｙｐｅｓ．ｘｓｄ三个模式文档，我们便将这三个　

ＸＭＬ和Ａｄｖａｎｃｅ　ＸＭＬ中的文档经过ＸＭＬ文档编码器生成　

的二进制ＸＭＬ文件。　

（２）编程接口ＥＰＧ　ｘＭＬ数据库根据需要提供了一系　

列供客户端调用的编程接口，包括将Ｏｒｉｇｉａｎｌ　ＸＭＬ文件分级　

的接口，生成ｘＭＬ文件的接口　ＸＭＬ文档编码的接口，还保　

留了一些暂未实现的接口，如ＸＭＬ文件的查询添加修改删　

除等接口。　

（３）索引管理在ｘＭＬ资源库中建立如下的索引方案，　

用户可根据这种索引来查询获取需要的文件。由于资源库以　

文件作为存储的基本单位，因此建立索引也是通过文件名来　

建立索引。　

（４）存储管理ＥＰＧ　ＸＭＬ数据库的存储管理是以ＸＭＬ　

文件为存储单位进行的。　

３　ＸＭＬ的传输性能问题　

随着基于ＸＭＬ的数据交换技术的应用的深入，业界发　

现ＸＭＬ的一个越来越无法忍受的缺点，即：效能缓慢。该问　

题促使我们设法加速ＸＭＬ的流量，改善ＸＭＬ的传输性能，　

这就引出了ＸＭＬ的数据表示问题，也有人称之为ＸＭＬ数据　

的“肥胖”问题。　

在改进ＸＭＬ传输性能的这个问题上，目前可用的方案　

有：ＡＳＣＩＩ编码，压缩编码如ＧＺＩＰ，为ＸＭＬ专门设计的编码　

以及二元ｘＭ　等。　

（１）ＡｓＣＩＩ编码。为计算机提供了一种存储数据和与其　

他计算机及程序交换数据的方式。ＸＭＬ文档最原始的编码　

方式便是采用ＡＳＣＩＩ的编码机制。　

（２）压缩编码，如ＧＺＩＰ。这种编码严格遵循ＸＭＬ文本　

特性，是基于文本的转换。这种类型的转换主要和文档大小　

有关。这种类型的任何算法都能方便地用于ＸＭＬ文档的文　

本表示。这类算法一般不会改善文档的处理速度，因为增加　

了压缩和解压缩的时间。　

（３）专门设计的ＸＭＬ编码，如ＸＭｉｌｌ，ＸＢＩＳ等。这类编　

码比一般的基于文本的转换更进一步。设计这种类型的方法　

是为了通过某种编码表示，以能够减少文档大小、降低处理开　

销或者二者兼具的方式利用ＸＭＬ的结构。从编码形式上重　

构原来的文档，仅仅损失ＸＭＬ认为无关的那些信息。由于　

损失了信息，原始文档和重构后的文档进行直接文本比较，可　

能不同，但是对于符合ＸＭＬ规则的任何应用程序而言它们　

是等价的。　

（４）二元ＸＭＬ。目前还没有一个通用的标准，一般根据　

应用程序使用的文档结构量身定做，发送方和接收方必须事　

先就具体的结构达成一致，并且实现适当的编码程序／解码程　

序，针对应用程序定制编码的多数方法都是基于交换文档的　

・　９３　・　

维普资讯

Ｗ３Ｃ　ＸＭＬ　Ｓｃｈｅｍａ规范。模式中包含的类型和结构信息用　每个二进制对象只含有一个顶级元素（ｔｏｐ　ｌｅｖｅｌ　ｅｌｅ—　

于生成定制的编码程序／解码程序代码，可能包括能够代表文　

ｍｅｎｔ）。　

档数据内容并直接与编码程序／解码程序交互的对象［５］。它　

４．１．２元素编码结构　

的优势在于采用二元格式后。传输代价和执行效能都有了显　

ｅｌｅｍｅｎｔ－ｔａｇ这个字节用来标志元素类型，每个ｅｌｅ—　

著提高。然而它的劣势也是明显的，目前只应用于特定行业、　

ｍｅｎｔ－ｔａｇ标示一个唯一类型的元素，它和ｅｌｅｍｅｎｔ之间是１—１　

特定用途，存在应用范围小，不兼容、丧失互通性的问题［７］。　

对应的关系，如果将来需要添加新的元素扩展，这里保留的未　

美国的二元ｘＭＬ标准化工作组已申请国家专利研究该课　

定义的Ｔａｇ可供将来扩展之用。Ｅ１ｅｍｅｎｔ－ｌｅｎｇｔｈ这个字节　

题　。　

用来标示这个元素包含的ｄａｔａ的长度，注意它不包括本身的　

二元ＸＭＬ有ＷＢＸＭＬ，ＰＩＸ）Ｍ，采用ＡＳＮ．１规则的二进　

ｔａｇ和ｌｅｎｇｔｈ部分，但是包括子元素或属性的ｔａｇ和ｌｅｎｇｔｈ部　

制ＸＭＬ编码三类编码方式＿ｇＪ。　

分。如果ｄａｔａ的长度大于０ｘＦＤ，小于等于２　一１，则用一个　

额外的１６位的ｅｘｔｅｎｄｅｄ－－ｅｌｅｍｅｎＬｌｅｎｇｔｈ来标示数据长度，　

４采用二元ＸＭＬ为ＤＭＢ　ＥＰＧ编码　

此时ｅｌｅｍｅｎｔ－ｌｅｎｇｔｈ等于０ｘＦＥ，当解码时读到ｅｌｅｍｅｎｔ－　

由于ＤＭＢ　ＥＰＧ的带宽有限，终端接收设备的内存容量　

ｌｅｎｇｔｈ等于ＯｘＦＥ，则自动根据下２个字节来确定ｄａｔａ的长　

以及处理器都是非常宝贵的资源，尽量压缩数据的传输量对　

度。如果ｄａｔａ的长度大于等于２　小于２　一１，则用一个额外　

于降低传输消耗，减小终端设备的负担是非常必要的，ＤＭＢ　

的２４位的ｅｘｔｅｎｄｅ（Ｌ＿ｅｌｍｅｅｎＬｌｅｎｇｔｈ来标示数据长度，此时　

ＥＰＧ采用Ｂｉｎａｒｙ　ＸＭＬ的编码方案［２］，由于Ｗ３Ｃ尚没有建立　

ｅｌｍｅｅｎｔ　ｌｅｎｇｔｈ等于０ｘＦＦ，同理当解码时读到ｅｌｍｅｅｎｔ－ｌｅｎｇｔｈ　

一

套通用的标准，ＥＴＳＩ建立一套广播系统（行业内）通用的二　

等于０ｘＦＦ，则自动根据下２个字节来确定ｄａｔａ的长度。Ｅｌ－　

进制编码规范口　］。采用二元ＸＭＬ显著降低了数据的传输　

ｅｍｅｎｔ－ｄａｔａ＿＿ｔｙｐｅ：这段字节包含了该元素的属性，ＣＤＡＴＡ　

量，改善了传输性能。下面重点介绍ＤＭＢ　ＥＰＧ的二进制编　

（字符串）以及子元素的编码。它们按照属性。子元素，ＣＤＡ—　

码协议以及我们针对该协议所设计的编码算法。　

ＴＡ的顺序进行编码。　

４．１　Ｂｉｎａｒｙ　ＸＭＬ编码协议　

４．１．３属性编码　

４．１．１编码模式　

Ｓｙｎｔａｘ　Ｓｉｚｅ　Ｔｙｐｅ　

ＥＰＧ采用ｔａｇ－ｌｅｎｇｔｈ－ｖａｌｕｅ的模式进行编码，每个元素和　

ａｔｔｒｉｂｕｔｅ０｛　

属性都有一个其独有的标识Ｔａｇ，然后是标示该元素或属性　

ａｔｔｒｉｂｕｔｅ

＿

ｔａｇ　８ｂｉｔｓ　ｕｉｍｓｂｆ　

含有数据的长度（以字节数为单位）Ｌｅｎｇｔｈ标识，最后是数据　

ａｔｔｒｉｂｕｔｅＪｅｎｇｔｈ　８ｂｉｔｓ　ｕｉｍｓｂｆ　

ｉｆ（ａｔｌａ＇ｉｂｕｔｅＪｅｎｇｔｈ＝＝ＯｘｌａＥ）｛　

部分，如图６所示。　

ｅｘｔｅｎｄｅｄ＿ａｔｔｒｉｂｕｔｅＪｅｎｇｔｈ　１６ｂｉｔｓ　ｕｉｍｓｂｆ　

｝　

Ｔａｇ　ｌ￣ｎｇｔｈ　ｌ　Ｖａｌｕｅ　ｌ　ａＴｇ　Ｉ　Ｌｅｎｓ￣　

ｉｆ（ａｔＵｉｂｕｔｅ．．１ｅｎｇｔｈ－－－ＯｘＦＦ）｛　

ｅｘｔｅｎｄｅｄ＿ａｔｍ＇ｂｕｔｅＪｅｎｇｆｌａ　２４ｂｉｓｔ　ｕｉｍｓｂｆ　

｝　

图６编码模式结构　

ｆｏｒ（ｉ＝Ｏ；ｉ＜ａｔｔｆｉｂｕｔｅ　ｌｅｎｇｔｈｏｒ　

ｅｘｍｎｄｅ￣ａｔｔｉｆｂｕｔｅ＿ｌｅｎｇｔｈ；ｉ＋＋）｛　８　ｂｉｓｔ　ｕｉｍｓｂｆ　

这种编码结构可以使接收终端很方便地跳过那些它不需　

ａｔｔｒｉｂｕｔｅ

＿

ｄａｔａ＿ｂｙｔｅ　

｝】　

要的数据或者终端无法识别的数据。为了便于描述协议，可　

使用类似于Ｃ语言的伪代码描述，某些词语是缩写词，如　

图９属性编码结构　

Ｕｉｍｓｂ表示Ｕｎｓｉｇｎｅｄ　ｉｎｔｅｇｅｒ，Ｍｏｓｔ　ｓｉｇｎｉｆｉｃａｎｔ　ｂｉｔ　ｆｉｒｓｔ。生成　

最终二进制对象可以用图７描述。　

如图９所示，属性编码结构类似于元素结点的编码，这里　

不再做详细解释。需要注意的是；如果一个属性存在默认的　

Ｓｙｎｔａｘ　Ｓｉｚｅ　Ｔｙｐｅ　

属性值，当该属性取默认值时，该属性不必编码，其所在的元　

ｂｉｎａｒｙ＿ｏｂｊｅｃｔ０｛　

素结点无须将该属性的编码包含进去，因为如果一个属性取　

ｔｏｐ＿Ｊｅｖｅｌ＿ｅｌｅｍｅｍａｎ（）　

默认值，当终端解码时找不到该属性的ｔａｇ时就自动认为该　

图７二进制对象结构　

属性取默认值，从而减少信息通信的代价。　

４．１．４　ＣＤＡＴＡ和Ｓｔｒｉｎｇ的编码　

Ｓｙｎｔａｘ　Ｓｉｚｅ　Ｔｙｐｅ　

Ｓｙｎｔａｘ　Ｓｉｚｅ　Ｔｙｐｅ　

ｅｌｅｍｅｎｔＯ｛　ｃｄ８‘ａ（）｛　

ｅｌｅｍｅｎｔ．ｔａｇ　８ｂｉｔｓ　ｕｉｍｓｂｆ　

￣ｄａ￣．．ｔａｇ　８　ｂｉｔｓ　ｕｌｍｓｂｆ　

ｅｌｅｍｅｎｔＡｅｎｇｔｈ　８ｂｉｓｔ　ｕｉｍｓｂｆ　

ｅｄａｔａ　ｌｅｎｇｔｈ　８ｂｉｓｔ　ｕｉｍａｂｆ　

ｉｆ（ｅｌｅ咖Ｕｅｎｇｔｌｌ；　ｘ　｛　

ｉｆ（ｃｄａｔａ＿ｌｅｎｇｔｈ－－＝Ｏｘｌ￣）｛　

ｅｘｔｅｎｄｅｄ

＿

ｅｌｅｍｅｎｔＪｅｎｇｔｈ　１６　ｂｊｔｓ　ｕｉｍｓｂｆ　

ｅｘｔｅｎｄｅｄ

ｃｄａｔａ．．１ｅｎｇｔｈ　１６ｂｉｓｔ　ｕｉｍｓｂｆ　

＿

｝　

ｉｆ（ｅｉｃｍｅａｔＡｅｎ￣｛　

ｉｆ（‘　ｌａ　ｌｅｎｇ出神ｘＦＦ）｛　

Ｅｘｔｅｎｄｅｄ

＿

ｃｌｅｍｅｎｔ

＿

ｌｅｎｇｔｈ　２４　ｂｉｔｓ　ｕｉｍｓｂｆ　

Ｅｘｔｅｎｄｅｄ　ｃｄａｔａ

＿

ｌｅｎｇｔｈ　４２ｂｉｔｓ　ｕｉｍｓｂｆ　

｝　｝　

ｆｏｒ（ｉ＝Ｏ；ｉ＜ｅｌｅｍｅｎｄｅｎｇｔｈ　ｏｒ　ｆｏｒ（ｉ＝０；ｉ＜ｃｄａｔａ＿ｉｅｎｇｔｈｏｒ　

ｅｘｔｅｎｄｅｄ＿ｅｌｅｍｅｎｔ＿ｌｅｎｇｔｈ；ｉ＋＋）｛　８ｂＲｓ　ｕｉｍｓｂｆ　

ｅｘｔｅｎｄｅｄ

＿

ｅｌｅｍｅｎｔ＿ｌｅｎｇｔｈ；ｉ＋＋）｛　８　ｂｉｔｓ　ｕｉｍｓｂｆ　

ｅｌｅｍｅｎｔ＿ｄａｔａ

＿

ｂｙｔｅ　ｃｄａｔａ＿ｄａｔａ．ｂｙｔｅ　

｝】　

｝】　

图８元素编码结构图　

图１０　ＣＤＡＴＡ和Ｓｔｒｉｎｇ的编码结构　

・９４・　

维普资讯

所有的ＣＤＡＴＡ和Ｓｔｒｉｎｇ部分（除了属性值Ｓｔｒｉｎｇ外）的　

编码结构如图１Ｏ所示，所有的ｃｄａｔａ－－ｔａｇ都为ＯｘＯ１，其他部　

分含义类似于上面的解释。值得提出的是，这里ＣＤＡＴＡ和　

Ｓｔｒｉｎｇ只适合对元素结点值，而不适合属性值，所有的ＣＤＡ—　

ＴＡ和Ｓｔｒｉｎｇ将采用ＵＴＦ＿８编码（见ＩＳＯ／ＩＥＣ　１０６４６＿４］），在　

０ｘＥ０００和Ｏ）【Ｆ８ＦＦ之间的用户自定义字符区的编码将被忽　

Ｐｕｂｌｉｃ　ｂｙｔｅ［］ｃｏｄｅ（ｎｏｄｅＴｙｐｅ　ｎｏｄｅ）　

｛　

ｂｙｔｂｅ￣！ｂｉｎａｒｙＤａｔａ；／／存储的编码后的ｂｙｔｅ数组　

ｂｙｔｅ口ａｔｔｒｉｂｕｔｅ，／／存储所有属性的编码　

ｂｙｔｅ口ｅｌｅｍｅｎｔ￣／／存储子元素的编码　

ｙｔｅ　ＬＪ　ｔｅｍｐ＝ｎｕｌｌ，／／连接各个编码部分的临时ｂｙｔｅ数组　

ｂｙｔｅ［］ｃｄａｔａ；／／存储节点ｃｄａｔａ部分编码　

ｂｙｔｅ　ｔａｇ－－ｎｏｄｅ．ｔａｇ；／／由协议定义　

ｂｙｔｅ口ｌｅｎｇｔｈ，／／根据ｄａｔａ字节的长度来确定使用几个字节的　

ｌｅｎｇｔｈ来标示长度　

ｉｆ（ｎｏｄｅ＝＝ｎｕｌ１）　

Ｒｅｔｕｒｎ　ｎｕｌｌ　ｉ　

略，因为终端是无法对这些编码解码展示的　

４．１．５枚举类型编码　

由于枚举类型的属性值的数量有限，可以对每种属性采　

Ｗｈｉｌｅ（ｎｏｄｅ　ｈａｓ　ａｔｔｒｉｂｕｔｅｓ　ｗｈｉｃｈ　ｉｓｎ　ｔ　ｃｏｄｅｄ）｛　

Ａｔｔｒｉｂｕｔｅ＝ｃｏｄｅＡｔｔ　ｕｔｅ（ａｔｔ　ｕｔｅ（ｉ））；／／对属性编码　

用一个字节的编码，终端解码器读取该字节时便自动将其影　

射为相应的枚举属性值。　

ｔｅｍｐ－－ＣｏｎｅａｔＢｙｔｅｓ（ｔｅｍｐ，ａｔｔｉｒｂｕｔｅ）；／／返回连接ｔｅｍｐ和ａｔｔｒｉｂ—　

ｕｔｅ字节数组）　

Ｗ　ｈｉｌｅ（ｎｏｄｅ　ｈａｓ　ｍｏｒｅ　ｃｈｉｌｄ　Ｅｌｅｍｅｎｔｓ）　

｛　ｅｌｅｍｅｎｔ＝ｃｏｄｅ（ＣｈｉｌｄＥｌｅｍｅｎｔ）　

／／对子节点编码，同一类型的节点可共用一个编码接１２１，不同节点　

４．１．６其他公共数据类型编码　

其他公共类型编码根据数据的特有的类型和结构设计编　

码，譬如属性ｖｅｒｓｉｏｎ采用１６位无符号整数等。　

４．２基于ＥＩＳＩ　３７１协议编码器的设计　

基于ＥＴＳＩ　３７１协议编码算法的设计思路：　

（１）首先根据协议，属性编码结构设计所有共用的属性类　

型编码为：　

属性ｔａｇ　ｌ　属性ｌｅｎｇｔｈ　ｌ　属性值ｄａｔａ　

（ｚ）根据编码协议，枚举类型属性编码结构设计所有的枚　

举类型编码是：　

（３）根据协议，设计节点类型的编码结构ｊａｖａ的ｂｙｔｅ［］　

数组对象Ａ，由八ｌｅｎｇｔｈ得到该节点的长度。　

（４）解析ＸＭＬ文件生成树，然后对ＸＭＬ树进行深度优　

先搜索的一次遍历。如图ｌ１所示，遍历的顺序依次是１，２，　

５，３，６，７，１Ｏ，ｌ１，８，４，９。　

图１１　ＸＭＬ树的遍历（深度优先搜索）　

当访问节点时：　

ａ）如果属性部分不为空，则对属性部分编码；　

ｂ）如果是非叶子节点，访问各个子节点的编码，并返回子　

节点的编码的ｂｙｔｅ数组；　

ｃ）如果存在节点值ＣＡＤＡ或者Ｓｔｒｉｇｎ，则对Ｓｔｒｉｇｎ部分　

编码｝　

ｄ）连接以上编码ｂｙｔｅ数组得到该节点的ｌｅｎｇｔｈ￣　

ｅ）连接该节点的ｔａｇ，ｌｅｎｇｔｈ，ｄａｔａ部分，组成该节点的　

编码ｂｙｔｅ数组　

伪码表示为：　

类型重载此接口。　

ｔｅｍｐ　ｃｏｎｃａｔＢｙｔｅｓ（ｔｅｍｐ，ｅｌｅｍｅｎＯ；　

／／返回连接ｔｅｍｐ和ａｔｔｒｉｂｕｔｅ字节数组　

）　

ｉｆ（ｎｏｄｅ　ｈａｓ　ＣＤＡＴＡ　ｏｒ　Ｓｔｒｉｎｇ）ｆ　

ｃｄａｔａ＝Ｃｏｄｅ（ｅｄａｔａ　ｏｒ　ｓｔｒｉｎｇ）；　

ｔｅｍｐ—ｃｏｎｅａｔＢｙｔｅｓ（ｔｅｍｐ，ｅｄａｔａ）；　

／／返回连接ｔｅｍｐ和ｃｄａｔａ字节数组　

｝　

ｉｆ（ｔ哪ｐ一＝ｎｕｌ１）　

／／此元素没有属性也没有子元索和ＣＤＡＴＡ部分　

（Ｌｅｎｇｔｈ＝ｎｅｗ　ｂｙｔｅ［１／　Ｌｅｎｇｔｈ（ｏ］＝ｏｘｏｌ；｝　

ｅｌｓｅ　

ｌｅｎｇｔｈ７　ｇｅｔＬｅｎｇｔｈＦｒｏｍＤａｔａ（ｔｅｍｐ．１ｅｎｇｔｈ）｝　

／／根帮ｄａｔａ的长度确定ｌｅｎｇｔｂ的罕节长度（１，３，４）并返回Ｌｅｎｇｔｈ　

部分的编码，ｔｅｍｐ．１ｅｎｇｔｈ表示ｔｅｍｐ数组的长度．　

ｅｌｅｍｅｎｔ＝ＣｏｎｅａｔＢｙｔｅｓ（ｔａｇ，ｌｅｎｇｔｈ，ｔｅｍｐ）；　

ｒｅｔｕｒｎ　ｅｌｅｍｅｎｔ，　

、

４．３　ＢｉｎａｒｙＸＭＬ性能分析　

在采用Ｂｉｎａｒｙ　ＸＭＬ为ＥＰＧ编码后，我们从理论分析和　

实验上分别采用ＡＳＣＩＩ编码，ＧＺＩＰ压缩编码，以及采用Ｂｉｎａ－　

ｒｙ　ｘＭＬ编码，读一个ＥＰＧ　ＸＭＬ文件，写一个ＥＰＧ　ＸＭＬ文　

件所需要的时间，以及各种编码文档占用的存储空间，结果如　

表１所示。　

表１　３种编码性能的比较表　

—＼

．

性能指标、＼

编码方案　

　ＡＳＣＩＩ　ＧＺＩＰ　Ｅｎ

Ｂｉ

ｃ

ｎａｒｙ　

ｄｏｉｎｇ　

Ｒｅａｄ　Ｔｉｍｅ　较快　较慢　较快　

Ｗｒｉｔｅ　Ｔｉｍｅ　较快　较慢　较慢　

Ｄｏｃｕｍｅｎｔ　Ｓｉｚｅ　大　较小　较小　

在表１中，先看读时间，由于读ＧＺＩＰ文本时首先要解压　

缩还原成ＸＭＬ文挡，因此相对ＡＳｃＩＩ编码读速度较慢，而在　

读Ｂｉｎａｒｙ　ＸＭＬ时，可以直接根据二进制编码结构读取，不需　

要还原成ＸＭＬ文挡，所以读速度较快。再看写时间，由于　

ＧＺＩＰ增加了压缩时间，Ｂｉｎａｒｙ编码增加了解析ＸＭＬ结构然　

后编码的时间，因此后两种写速度都较慢。最后看三种编码　

方案后文挡大小，由于ＧＺＩＰ的压缩，二元编码的重构，后两　

种方案在不同程度上都减小了文挡大小。由于终端更为关注　

文档的表示大小以及读取的速度，因此二元ＸＭＬ得到了青　

睐。　

由于ＸＭＬ文档的传输性能主要取决于ｘＭＬ文档转换　

后的大小，经过一定数量ＥＰＧ　ＸＭＬ文档的实验后，就ＸＭＬ　

文档的几种编码后的大小进行比较，可见ＧＺＩＰ和二元编码　

在减小文档大小上效果突出，如图１２所示。值得注意的是不　

同的文档由于内容不同，即使其ＡＳＣＩＩ编码大小相同，经过　

ＧＺＩＰ压缩或经过本文的Ｂｉｎａｒｙ　Ｅｎｃｏｄｉｇｎ编码后其文档大小　

也会可能不同，所以针对某个具体的文档，二元编码不一定比　

ＧＺＩＰ压缩比高。　

・９５・　

维普资讯

参考文献　

１　ＥＴＳＩ　ＴＳ　１０２　８１８（２００５　Ｏ１），ＸＭＬ　Ｓｐｅｃｉｉｆｃａｔｉｏｎ　ｆｏｒ　ＤＡＢ　ＥＰＧ．　

ｈｔｔｐ：／／ｗｗｗ．ｗｏｒｌｄｄａｈ．ｏｒｇ／ｉｒｅ，ａｓｐｘ？ｓｕｂ一１Ｏ　

２　ＥＴＳＩ　ＴＳ　１０２　３７１（２００５一Ｏ１）．Ｔｒａｎｓｐｏｒｔａｔｉｏｎ　ａｎｄ　Ｂｉｎａｒｙ　ｅｎｃｏｄｉｇ　ｎ

ｆｏｒ　Ｂ　ＥＰＧ．　ｈｔｔｐ　｝｜　．ｗｏｄｄｄａｂ，　ｏｒｇ／ｉｒｃ．ａｓｐｘ？ｓｕｂ＝１０　

３　ＥＴＳＩ　ＥＮ　３０１　２３４（１９９９一Ｏ２）．Ｍｕｌｔｉｍｅｄｉａ　Ｏｂｊｅｃｔｓ　Ｔｒａｎｓｐｏｒｔａｔｉｏｎ—　

Ｐｒｏｔｏｃｏ１．ｈｔｔｐ：／／ｗｅｂａｐｐ．ｅｔｓｉ．ｏｒｇ／ａｃｔｉｏｎ／ｑ０Ｐ／ＯＰ２００６０５１９／ｅ￣　

３Ｏ１２３４ｖ０２０１０１ｏ．ｐｄｆ　

４　ＥＴｓＪ　ＴＳ　３００　４０１（２００１　０５）．Ｒａｄｉｏ　Ｂｒｏａｄｃａｓｔｉｎｇ　ｔｏｔｅｍｓ　Ｄｉｇｉｔａｌ　

Ａｕｄｉｏ　Ｂｒｏ：ａｃａｓｔｄｉｎｇ（ＤＡＢ）ｔｏ　ｍｏｂｉｌｅ，ｐｏｒｔａｂｌｅ　ａｎｄ　ｆｉｘｅｄ　ｒｅｃｅｉｖ—　

图１２　ＸＭＬ的文档编码后的性能比较　

总结本文在分析研究了ＤＭＢ　ＥＰＧ相关协议原理的基　

ｅｒｓ．ｈｔｔｐｔ｜｜　ｎ　ｗｏｒｌｄｄａｂ．　ｏｒｇ／ｉｍ　ａｓｐｘ？ｓｕｂ＝１０　

５　万常选．ＸＭＬ数据库技术．清华大学出版社，２００５　

６　Ｓｏｓｎｏｓｋｉ　Ｅ．改善ＸＭＬ的传输性能．ｈｔｔｐ；／／　．ｉｂｍ　ｅｏｍ／ｄｅ—　

ｖｅｌｏｐｅｒｗｏｒｋｓ／ｃｎ／ｘｍｌ／　

７　Ｂａｙａｒｄｏ　Ｒ　Ｊ，Ｇｒｕｈｌ　Ｄ，ｅｔ　ａ１．Ａｎ　ＥｖＭｕａｔｉｏｎ　ｏｆ　Ｂｉｎａｒｙ　ＸＭＬ　Ｅｎ—　

ｃｏｄｉｎｇ　ＯＩＰｐｔｉｍｉｚａｔｉｏｎｓ　ｏｒ　Ｆａｆｔｓｔ　Ｓｔｒｅａｍ　Ｂａｓｅｄ　ＸＭＬ　Ｐｒｏｃｅｓｓｉｎｇ．ｈｔ—　

础上，设计实现了ＤＭＢ　ＥＰＧ的数据存储方案，分析了ＸＭＬ　

传输性能问题，并采用二元ＸＭＬ设计，实现了ＤＭＢ　ＥＰＧ的　

编码器，最后分析比较了三种编码的性能。　

ｔｐ：／／ｗｗｗ２００４．ｏｒｇ／ｐｒｏｃｅｅｄｉｎｇｓ／ｄｏｅｓ／ｌｐ３４５．．ｐｄｆ　

８　ＸＭＬ　Ｂｉｎａｒｙ（３　１１ａｒａｃｔｅｒｉｚａｔｉｏｎ　Ｗｏｒｋｉｎｇ　Ｇｒｏｕｐ．ｈｔｔｐ：／／　Ⅳｗ．ｗ３．　

进一步的工作有以下几个方面值得研究，如数据经过编　

码后的后续处理过程，即文挡封装成ＭＯＴ对象、分段、打包　

和传输技术以及终端如何进一步改善解码技术等。　

（上接第８０页）　

３．３　ＸＲ树＋ＸＲ－Ｓｔａｅｋ算法　

ｏｒｇ／ＸＭＩ　／Ｂｉｎａｒｙ／　

９　李莉明．二进制ＸＭＬ浅析．计算机与数字工程，２００５，３３（２２）：１～　

５　

的ＸＭＬ索引查询方法能够有效地解决分支路径查询，但是　

在Ａｎｃ＿＿Ｄｅｓｃ－Ｂ　算法中，利用Ｂ＋树索引能够有效地跳　

过后裔列表中所有不参加连接的结点，但是对于祖先列表中　

所有不参加的结点，并不能利用Ｂ＋树索引来有效地跳过，这　

这种方法都对相应的ＸＭＬ文档有要求，其所要查询的ｘＭＬ　

文档为树形结构。怎样很好地将上述两种ＸＭＬ查询方法中　

的优点结合起来，是将来研究的热点之一。　

是因为：在祖先列表中无法利用Ｂ＋树索引直接定位结点的第　

一

参考文献　

１　Ｇｏｌｄｍａｎ　Ｒ，Ｗ＇ｉｄｏｍ　Ｊ．ＤａｔａＧ＇，ｕｉｄｅ：ｅｎａｂｌｉｎｇ　ｑｕｅｒｙ　ｆｏｒｍｕｌａｔｉｏｎ　

ａｎｄ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｉｎ　ｓｅｍｉｓｔｒｕｃｔｕｒｅｄ　ｄａｔａｂａｓｅｓ．Ｉｎ：２３ｔｈ　Ｉｎｔｅｒｎａ－　

ｉｏｎａｌｆ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｖｅｒｙ　Ｌａｒｇｅ　ＤａＬｔａ　Ｂａｓｅｓ。ｐａｇｅｓ。Ａ１ｔｈｅｎｓ，　

Ｇｒｅｅｃｅ。１９９７；４３６￣４４５　

２　Ｍｉｌｏ　Ｔ，Ｓｕｄｕ　ｎ　Ｉｎｄｅｘ　ｓｔｒｕｃｔｕｒｅｓ　ｆｏｒ　ｐａｔｈ　ｅｘｐｒｅｓｓｉｏｎｓ　Ｉｎ：７　

个可能的祖先结点，需要多次定位才能跳到结点的第一个　

可能的祖先结点。为了解决这个问题，ＸＲ树索引被提出Ｌｌ　，　

基于ＸＲ树索引不仅能够有效地跳过后裔列表中所有不参加　

连接的结点，而且能够跳过祖先列表中所有不参加连接的结　

点。例如，图３中若要找到后裔结点９的父结点８，在Ａｎｃ－－　

Ｄｅｓｃ￣１３＋算法中不能够一次定位到结点９的父结点，需要多　

次在祖先列表中进行定位才能够找到结点９的父结点８，而　

ＸＲ树＋ＸＲ－Ｓｔａｃｋ算法能够在祖先列表中一次定位到结点９　

的父结点８。　

３．４　ＸｌＳ￥系统　

ＩｎｔｅｒｎａｔｉｏｎａｌＩ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａｂａｓｅ　Ｔｈｅｏｒｙ，Ｊｅｒｕｓａｌｅｍ，Ｉｓｒａｅｌ【，　

１９９９．２７７～２５５　

３　Ｋ，ａｕｓｈｉｋ　Ｒ，　ｍｎｏｙ　Ｐ，Ｂｏｈａｎｎｏｎ　Ｐ，ｅｔ　ａ１．，Ｅｘｐｌｏｉｉｔｎｇ　Ｌｏｃａｌ　Ｓｉｍｉ—　

ｌａｒｉｔｙ　ｆｏｒ　Ｅｆｊ￣ｄｅｎｔ　Ｉｎｄｅ：ｄｎｇ　ｏｆ　Ｐａｔｈｓ　ｉｎ　Ｇｒａｐｈ　Ｓｔｒｕｃｔｕｒｅｄ　Ｄａｔａ．　

Ｉｎ：１０ｔｈ　Ｉｎｔｅｍａｔｉｏｎａ１　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａｂａｓｅ　Ｔｈｅｏｒｙ，Ｓａｎ　Ｊｏｓｅ，　

Ｃａｌｉｏ：ｆｍｉａ，ＵＳＡ，２００２．１２９～１４Ｏ　

４　Ｃｈｅｎ　Ｑ，Ｌｉｍ　Ａ，Ｏｒｌｇ　Ｋ　Ｗ．Ｄ（ｋ）ｉｎｄｅｘ：Ａｎ　ａｄａｐｔｉｖｅ　ｓｔｒｕｃｔｕｒａ１　

ｓｕｍｍａｒｙ　ｆｏｒ　ｇｒａｐｈ－ｓｔｒｕｃｔｕ￣ｅｄ　ｄａｔａ．Ｉｎ：Ｐｒｏｃ．ｏｆ　ｔｈｅ　２００３　ＡＣＭ　

ＳＩＧＭＯＤ　Ｉｎｔ１．Ｃｏｎｆ．ｏｎ　Ｍａｎａｇｅｍｅｎｔ　ｏｆ　Ｄａｔａ，Ｓａｎ　Ｄｉｅｇｏ，Ｃａｌｌ－　

ｏｍｉａ，ＵＳＡ，２００３．１３４～１４４　ｆ

ＸＩＳＳ系统＿１蛆的主要思想是：将一个正则路径表达式分　

解成子路径表达式，将子路径表达式产生的中间结果进行结　

５　Ｈｅ　Ｈａｏ，Ｙａｎｇ　Ｊｕｎ，．Ｍｕｌｔｉｒｅｓｏｌｕｔｉｏｎ　Ｉｎｄｅｘｉｎｇ　ｏｆ　ＸＭＬ　ｆｏｒ　Ｆｒｅ－　

ｑｕｅｎｔ　Ｑｕｅｒｉｅｓ．Ｉｎ：Ｐｒｏｃｅｅｃｌｉｎｇ　ｏｆ　ｔｈｅ　２０ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ【Ｃｏｎｆｅｒ－・　

ｅｎｃｅ　ｏｎ　Ｄａｔｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ．Ｂｏｓｔｏｎ，ＵＳＡ，２００４．．６８３～６９４　

６　Ｃｈｔｕｎｇ　Ｃ，Ｍｉｎ　Ｊ，Ｓｈｉｍ　Ｋ．ＡＰＥｘ：Ａｎ　ａｄａｐｔｉｖｅ　ｐａｔｈ　ｉｎｄｅｘ　ｆｏｒ　

构连接操作得到最终的查询结果，并且该系统支持文档更新　

操作。　

ＸＩＳＳ系统主要由五个索引组成：元素索引、属性索引、结　

构索引、名称索引、值索引。这五个索引采用Ｂ＋树作为索引　

结构。　

ＸＭＬ　ｄａｔａ．Ｉｎ：Ｐｒｏｅ．ｏｆ　ｔｈｅ　２００２　ＡＣＭ　ＳＩＧＭＯＤ　Ｉｎｔ１．Ｃｏｎｆ．ｏｎ　

Ｍａｎａｇｅｍｅｎｔ　ｏｆ　Ｄａｔａ，Ｍａｄｉｓｏｎ，Ｗｉｓｃｏｎｓｉｎ，２００２．１２１～１３２　

７　Ｃｏｏｐｅｒ　Ｂ　Ｆ。Ｓａｍｐｌｅ　Ｎ。Ｆ＂ｒａｎｋｌｉｎ　Ｍ　Ｊ，ｅｔ　ａ１．Ａ　Ｆａｓｔ　Ｉｎｄｅｘ　ｆｏｒ　

Ｓｅｍｉｓｔｒｕｃｔｕｒｅｄ　Ｄａｔａ．Ｉｎ：Ａｐｅｒｓ　Ｐ　Ｍ　Ｇ，ｅｄｓ．Ｐｒｏｅｅ￣甜ｉｎｇｓ　ｏｆ　ｔｈｅ　

２７ｔｈ　ＶＩＬＤＢ　Ｉｎｔｅｍａｔｉｏｎａ１　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｖｅｒｖ　Ｌａｒｇｅ　Ｄａｌｔａｂａｓｅ，　

Ｒｏｍｅ。Ｉｔａｌｙ，ＳａｎＦｒａｎｃｉｓｃｏ：ＭｏｒｇａｎＫａｕｆｍａｎｎＰｕｂｌｌｓｈｅｒｓ，２００１．　

３４１～３５０　

ｘＩＳＳ系统将正则路径表达式分解成五个基本的子表达　

式：（１）单元素单属性子表达式：通过查找元素索引、属性索引　

得到查找结果。（２）一个元素和一个属性子表达式：ＥＡ．ｊｏｉｎ。　

（３）具有两个元素的子表达式：ＥＥ－ｊｏｉｎ　（４）Ｋｌｅｅｎｅ　ｅｌｏｕｒｅ　

８　Ｊｉａｎｇ　Ｈａｉｆｅｎｇ，Ｌｕ　Ｈｏｎｇｊｕｎ，Ｗａｎｇ　Ｗｅｉ，ｅｔ　ａ１．．Ｘ１　Ｔｒｅｅ：Ｉｎｄｅ　

ｘｉｎｇ　ＸＭＬ　Ｄａｔｔａ　ｆｏｒ　Ｅｆｉｃｉｆｅｎｔ　Ｓｔｕｃｔｕｒａ：Ｉ　Ｊｏｉｎｓ．Ｉｎ；Ｃａｓａｔｉ　Ｆ，ｅｔ　ａ１．　

ｅｄｓ．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　１９　ｈ　ＩＥＥＥ　ＩｃＤＥ　Ｉｎｔｅｍａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　

ＤａＬｔａ　Ｅｎｇｉｎｅｅｒｉｇ，Ｂａｎｇａｌｎｏｒｅ，Ｉｎｄｉａ，２００３．２５３～２６３　

９　Ｃｈｉｅｎ　Ｓ　Ｙ，Ｖａｇｅｎａ　Ｚ，Ｚｈａｎｇ　Ｄｏｎｇｈｕｉ，ｅｔ　ａ１．Ｅｆｆｉｃｉｅｎｔ　Ｓｔｒｕｃｔｕｒａ１　

Ｊｏｉｎｓ　ｏｎ　Ｉｎｄｅｘｅｄ　ＸＭＬ　Ｄｏｃｕｍｅｎｔｓ．Ｉｎ：Ｐａｐａｄｉａｓ　Ｄ，ｅｔ　ａｌ，．ｅｄｓ．　

Ｐｒｏｃｅ，　ｉｎｇｓ　ｏｆ　ｔｈｅ　２８，ｈ　ＶＬＤＢ　Ｉｎｔｅｒｎａｔｉｏｎａｌ【Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｖｅｒｙ　

Ｌａｒｇｅ　Ｄａｔｔａｂａｓｅ，Ｈｏｎｇ　Ｋｏｎｇ，Ｃｈｉｎａ，２００２．２６３￣２７４　

（＋，＊）：ＫＧｊｏｉｎ。（５）子表达式之问的联合操作。将分解的　

子表达式所得的中间结果进行连接得到最终的正则路径表达　

式的查询结果。　

ｘｌＳｓ缺点：只能解决单路径查询，对于分支路径查询效　

率较低。　

结束语本文主要研究了ＸＭＬ查询技术中的两种主要　

１Ｏ　Ｌｉ　Ｑｕａｎｚｈｏｎｇ，Ｍｏｏｎ＆Ｉｎｄｅ）【ｉｒｉｇ　ａｎｄ　Ｑｕｅｒｙｉｎｇ　ＸＭＬ　Ｄａｔａ　ｆｏｒ　

Ｒｅｇｕｌａｒ　Ｐａｔｈ　Ｅｘｐｒｅｓｓｉｏｎａ．Ｉｎ：Ｐｒｏｃｅｅｄｉｇｓ　ｎｏｆ　ｔｈｅ　２７ｔｈⅥ．ＤＢ　Ｏｎ－Ｃ－　

ｆｅｒｅｎｃｅ，Ｒｏｍａ，Ｉｔａｌｙ，２００１．３６１～３７０　

１１　Ｗｉｒｔｈ　５１．Ｔｙｐｅ　Ｅｘｔｅｎｓｌｏｎｓ．ＡＣＭ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｐｒｏｇｒａｍｍｉｇ　ｎ

Ｌａｎｇｕａｇｅ　ａｎｄ　Ｓｙｓｔｅｍｓ，１９８８，１６（２）：２０４　２１４　

１２　Ｄｉｍｔｚ　Ｐ　Ｅ　Ｍａｉｎｔａｉｎｉｎｇ　ＣｔＰｒｄｅｒ　ｉｎ　ａ　Ｌｉｎｋｅｄ　ＬＡｓｔ．Ｉｎ：Ｌｅｗｉｓ　Ｈ　Ｒ　ｅｄ．　

Ｐｒｃｏｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１４ｔｈ　Ａｎｎｕａｌ【Ａ　ｑＣＭ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｔｈｅｏｒｙ　ｏｆ　

Ｃｏｍｐｕｔｉｎｇ．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ，Ｃａ１ｊ．ｏｍｉｆａ，ＵＳＡ，１９８２．１２２～１２７　

方法，其中基于路径索引的ＸＭＬ查询方法只能够解决单路　

径查询，但是路径索引的创建不受ＸＭＬ文档结构的约束，即　

ＸＭＬ文档可以是树结构，也可以是图结构．。基于编码方式下　

・　９６　・　

１３　Ｂｒｕｎｏ　Ｎ，Ｋｏｕｄａｓ　Ｎ，Ｓｒｉｖａｓｔａｖａ　Ｉ３．Ｉ－ｈｏｌｉｓｔｉｃ　Ｔ＂ｗｉｇ　Ｊｏｉｎｓ：Ｏｐｔｉｍａｌ　

ＸＭＬ　Ｐａｔｔｅｒｎ　Ｍａｔｃｈｉｇ．Ｉｎ：Ｆｒａｎｋｌｎｉｎ　Ｍ　Ｊ，ｅｄ．Ｐｒｏｅｅｅｄｌ［ｉｎｇｓ　ｏｆ　ｔｈｅ　

２１ｔｈ　ＡＣＭ　ＳＩＧＭＯＤ　Ｉｎｔｅｒｎａｔｉｏｎａｌ【Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍａｎａｇｅｍｅｎｔ　ｏｆ　

Ｄａｔａ．Ｍａｄｉｌｓｏｎ，Ｗｉｓｃｏｎｓｉｎ，ＵｒＳＡ，２００３．３１Ｏ～３２１