（计算机软件与理论专业论文）基于dvbb索引的xml结构连接技术研究.pdf

东北大学硕士学位论文 摘要 基于d v b b 索引的x m l 结构连接技术研究 摘要 随着i n t e m e t 技术的发展，越来越多的应用采用x m l 作为信息表示和数据交 换的标准，这使得通过数据库技术对x m l 数据进行存储、查询等操作变得日益重 要，同时也为数据库研究者提出了新的挑战。然而，随着对于x m l 文档的容量的 增大和复杂性的增加，现有的查询处理算法已经不能够满足，因此，越来越多的 算法被提出来，以解决这个问题。 与传统数据库查询不同，x m l 数据库查询不仅查找数据，还查找数据之间的 结构关系。路径表达式是一种能够很好地满足这些查询要求的途径。因此，基于 路径表达式的查询问题成为x m l 数据查询的关键。而作为路径表达式中最基本的 单元，“父子”和“祖先后代”关系查询也就成为x m l 查询的核心问题。最近， 用结构连接算法处理这些结构关系十分流行。 为了迅速找到x m l 格式文件中的基本结构关系，很多种算法已经被提出。最 近提出的算法中，包括s t a c k t r e e 算法，b + t r e e 算法和x r t r e e 算法都是为了解 决这个问题而提出的。本文在现有结构连接算法的基础上，以d e w e y 向量为基础， 提出了基于d e w e y 向量的b + 树( d e w e yv e c t o rb a s e db + t r e e ，简称为d v b b ) 双栈 结构连接算法。该算法利用了两个栈，在这两个栈的基础上，利用d v b b 索引， 能够最大限度地避免那些不能产生连接结果的元素参加连接运算。与x r t r e e 不 同，d v b b 算法并没有任何辅助索引，可以最大限度的降低算法中的冗余度。一 系列的实验结果表明，基于d v b b 的双栈结构连接算法，无论是对于有效的跳过 “祖先”还是“后代”节点，都具有很高的性能。 关键词：x m l ；结构连接；d e w e y 向量；b + 树索弓 i i 东北大学硕士学位论文 a b s t r a c t s t u d yo nd v b b - b a s e dt e c h n i q u e sf o rs t r u c t u r a lj o i n so f x m ld a t a a b s t r a c t x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) h a sb e e ni n c r e a s i n g l yu s e di nw e b a p p l i c a t i o n sa n db e c o m eas t a n d a r df o rd a t ai n t e r c h a n g eo v e rt h ei n t e r n e t n e v e r t h e l e s s ， a l o n gw i t ht h ei n c r e a s i n gs i z eo fx m ld o c u m e n t sa n dc o m p l e x i t yo fe v a l u a t i n gx m l q u e r i e s ，e x i s t i n gq u e r yp r o c e s s i n gp e r f o r m a n c ei nt r a d i t i o n a lw a yw i l lm e e tal i m i t a t i o n i ti sw e l l k n o w nt h a tm o r ea n dm o r en e wm e t h o d sh a v eb e e na v a i l a b l et ot h i sp r o b l e m u n l i k ei nt r a d i t i o n a ld a t a b a s e s ，q u e r i e so nx m ld o c u m e n t sa i ma tn o to n l y e l e m e n tc o n t e n t sb u ta l s os t r u c t u r a l r e l a t i o n s h i p sb e t w e e nt a g g e de l e m e n t s p a t h e x p r e s s i o ni so n eo ft h ea p p r o a c h e so fm e e t i n gt h eq u e r yr e q u i r e m e n t s t h e r e f o r e ，q u e r y p r o c e s s i n gb a s e do np a t he x p r e s s i o nb e c o m e st h ek e yf o rs u c hq u e r i e s c o n s e q u e n t l y , e v a l u a t i n g t h e p r i m i t i v e s t r u c t u r a l r e l a t i o n s h i p s o f p a t he x p r e s s i o n ，i n c l u d i n g p a r e n t 。c h i l da n da n c e s t o r - d e s c e n d a n t ，i st h ec o r ei s s u ef o rt h eq u e r yp r o c e s s i n go fx m l d a t a r e c e n t l yp r o p o s e ds t r u c t u r a lj o i na l g o r i t h m sa r ep o p u l a ri np r o c e s s i n g ，s u c h r e l a t i o n s h i p s i no r d e rt oe v a l u a t et h e p r i m i t i v es t r u c t u r a lr e l a t i o n s h i p s ，p a r e n t c h i l da n d a n c e s t o r - d e s c e n d a n t ，m a n ya l g o r i t h m sh a v eb e e nc r e a t e d r e c e n t l yp r o p o s e ds t r u c t u r a l jo i n sa l g o r i t h m s ，i n c l u d i n gs t a c k t r e e ，b + t r e ei n d e xa n dx r s t a c ka r et os o l v et h u s p r o b l e m a l lt h e s ea l g o r i t h m st a k et h ea d v a n t a g eo fn u m b e r i n gs c h e m a sb a s e do n r e g i o nc o d i n g u n l i k et r a d i t i o n a lw a y ，w ee m p l o y st h ed e w e yv e c t o r ，a n dp r o p o s ea n e wa l g o r i t h md v b b ( d e w e yv e c t o rb a s e db + t r e e ) t os o l v et h es t r u c t u r a l i o i n s p r o b l e m s t h i sa l g o r i t h mc a ne f f e c t i v e l ys k i pt h ee l e m e n t sw h i c hc a n n o tp r o d u c et h e j o i nr e s u l t su s i n gt w o s t a c km o d e l u n l i k ex r s t a c k ，w ed on o th a v et ou s ea n y a s s i s t a n ti n d e xa n dr e d u c et h er e d u n d a n c i e sa tt h em o s t a f t e ras e r i e so f e x p e r i m e n t s ，a i i i 东北大学硕士学位论文 a b s t r a c t c o n c l u s i o nc a nb ed r a w nt h a tt h ed v b ba l g o r i t h mc a l lg a i nt h eb e s te f f i c i e n c yi n s t r u c t u r a lj o i n s k e yw o r d s ：x m l ；s t r u c t u r a lj o i n s ；d e w e yv e c t o r ；b + t r e ei n d e x i v 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除 加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人 为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在 论文中作了明确的说明并表示谢意。 学位论文作者躲琴例趸德 日期： 2 o o67 辛2 同7 钟日 卜i 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规 定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文 被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据 库进行检索、交流。 学位论文作者签名： 日期： 另外，如作者和导师同意网上交流， 学位论文作者签名： 签字日期： 请在下方签名；否则视为不同意。 导师签名： 签字日期： 东北大学硕士学位论文 第一章引言 第一章引言 i n t e r n e t 和各种基于网络技术的商业应用冲击着整个世界，为全球经济发展带 来了巨大的便利与空前的繁荣，网上信息也呈几何数级“膨胀爆炸”。但是由于交 流信息格式上的多样性和异构性以及缺乏成熟有效的管理和分析手段，使得网络 数据的交换过程越来越复杂，越来越混乱，出现了信息极大丰富，知识相对贫乏 的现象。这就对传统的数据库技术提出了一个新的挑战：如何存储和查询网络信 息，首先是网络文档信息。作为网络信息的载体，网络文档必须遵守统一的文档 编码规范。为此而诞生x m l 标准【l 2 l 注定将成为新互联时代舞台上的主角。x m l 是一个半结构化文档数据交换的国际标准，为基于w e b 的应用提供了描述和交换 数据的有效手段，具有广阔的应用前景，被称为“计算机革命的最新方向”，将成 为“第二次网络浪潮的推动力”。然而，由于x m l 的半结构化特性，传统的数据 管理技术不能完全满足x m l 数据的存储、查询等管理需要。因此，针对x m l 的 数据库管理技术的研究势在必行。目前，x m l 数据库的研究工作集中在查询处理 及优化技术，如路径表达式查询优化技术、结构连接查询技术研究等。而现在的 研究成果还不能完全支持针对x m l 标准查询语言【3 j ，因此对x m l 查询处理和优 化技术都正在进行更加深入的研究。 1 1x m l 简介 1 1 1x m l 的产生与发展 1 9 6 9 年，i b m 公司由g o l d f a r b 领导的研究项目组创建了通用标记语言( g m l ， g e n e r a lm a r k u pl a n g u a g e ) 用来编辑和格式化文本以及在子系统之间实现信息检 索。g m l 可用于标记任何数据集合的结构，是一种元语言( m e t a 1 a n g u a g e ) 能够描述其它语言及其语法和词汇表的语言。1 9 8 6 年1 0 月，g m l 被国际标准化 组织采纳为国际性的数据存储和交换标准，并被更名为“标准通用标记语言” ( s g m l ) 。 s g m l 是一门非常强大同时也相当复杂的标记语言，它很很庞大，功能很强， 东北大学硕士学位论文 第一章引言 可选项也很多，适用于需要有严格文档标准的各大组织。在8 0 年代，s g m l 较多 用于科技文献和政府办公文件中。许多国际组织在发布文档时也常常建议用s g m l 的格式。比如世界专利组织( w i p o ) 就制定了很多的基于s g m l 的规范来记录专 利文献资料。s g m l 的复杂性使得它十分不适合在w e b 中快速而简便地发布。而 且，s g m l 文档的处理非常复杂，成本非常高，因此s g m l 的软件通常非常昂贵。 w e b 发布需要更简单的语言。 1 9 8 9 年，。欧洲粒子物理实验室的t i mb e r n e r s l e e 提出了适合h t t p 传输的超 文本标记语言( h y p e rt e x tm a r k u pl a n g u a g e ，h t m l ) 。t i mb e m e r s l e e 借鉴了 s g m l 的成果，删繁就简。在i n t e r n e t 工程任务组( i e t f ) 的支持下，在1 9 9 4 年 末通用的标记规则被制定为h t m l2 0 。现在h t m l 已经毫无争议地成为了w e b 上的通用语言。但是h t m l 尽管在人机界面方面非常擅长，但是它却不利于机器 之间的相互交流和信息的传递。h t m l 中的标记大多是设计来呈现网页布局和外 观的，而并不能说明所呈现网页的数据含义，它在可扩展性、结构化和语义规范 方面存在严重的不足。当h t m l 发展到4 0 版本以后，人们越来越发现该标准实 在到了积重难反的程度，从1 9 9 6 年开始，w 3 c 开始考虑制定新的标记语言 x m l ，它既具有s g m l 的强大功能和可扩展性，同时又具有h t m l 的简单性。 1 9 9 6 年7 月开始，w 3 c 组织6 0 多位精心挑选的s g m l 信息结构专家专门成 立了一个s g m l 专家小组，提出了“网络上的s g m l ”计划。该小组由s u n 公司 的j o nb o s a k 担任组织和领导者。该小组删除了s g m l 中非核心的、未被使用的和 含义模糊的部分，剩下了短小精干的标记工具x m l 。x m l 保留了s g m l8 0 的功能，而将其复杂程度降低到原来的2 0 。1 9 9 7 年春，可扩展链接语言x l l 草 案已被拟定。最后，w 3 c 于1 9 9 8 年批准了x m l 的1 0 版本。 1 1 2 一个x m l 文档实例 x m l 文档的标签之间具有层次结构，同层次的标签之间具有有序性，下面举 例说明。从外观上看，x m l 文档很像人们所熟知的i t t m l 文档，每一个节点元素 用“ ”包含起来，不同的节点元素可能表达不同的意思，但是在本质上， x m l 和h t m l 有很大区别，它可以自己定义需要的节点元素，表1 1 给出了一个 x m l 文档的例子。 2 表1 1x m l 文档示例 t a b l e1 1x m ld o c u m e n ts a m p l e d a v i dm a i e r c o m p u t i n gw i t hl o g i c ：l o g i cp r o g r a m m i n gw i t hp r o l o g b e n j a m i n c u m m i n g s l9 8 8 o 8 0 5 3 6 6 8 1 - 4 h a m i d e ha f s a r m a n e s h j i mg r a y s t o n eb r e a k e r l3 - 2 4 v l d b d b c o n f v l d b v l d b 8 5 h t m l # a f s a r m a n e s h m k p 8 5 表1 1 即为x m l 的一个示例文档，文档的第l 行是一个x m l 声明，x m l 声 明是x m l 处理指令的一种，x m l 文档中的处理指令以“ ”标识，一 个x m l 文档最好以一个x m l 声明作为开始。x m l 声明给出了x m l 文档采用的 x m l 版本号，是否和外部d t d 配合使用，以及数据所采用的编码方式等信息。 文档第2 行同样是一个x m l 处理指令，它指明了当显示该x m l 文档时所应使用 的样式文件。文档第3 行是文档的外部d t d 使用说明，关于d t d 的相关知识在 下一节中有详细介绍。 下面开始是x m l 文档的实质内容。x m l 通过标签( t a g n a m e ) 组织数据结构， 在标签之间可以包括字符数据或者下一层次的标签。标签必须成对出现。x m l 中 有元素、属性、文本等几种基本的数据类型。每个x m l 文档只有唯一的根元素， 3 东北大学硕士学位论文 第一章引言 任何元素都是根元素的后代，出现在根元素内部。表中标签为d b l p 的元素即为根 元素。d b l p 元素有b o o k 和i n p r o c e e d i n g 两个子元素。b o o k 和i n p r o c e e d i n g 元素都 具有属性k e y ，通过这个属性为每一个b o o k 和i n p r o c e e d i n g 分配一个文档内唯一的 标识。a u t h o r 元素是b o o k 和i n p r o c e e d i n g 元素的子元素，它有一个文本类型的元 素作为其子结点以表示其取值，例子中b o o k 元素有一个名为a u t h o r 的子元素，其 值为“d a v i dm a i e r ”，而i n p r o c e e d i n g 元素有多个a u t h o r 子元素，表示有多个作者 名字出现。c i t e 子元素具有属性l a b e l ，通过这个属性可以表示对文档中的 i n p r o c e e d i n g 元素的引用。 1 2d t d 和x m ls c h e m a 自x m l l 0 发布起，关于x m l 新技术和规范不断涌现。关于x m l 数据模型 的规范主要包括d t d 和x m ls c h e m a 。 1 2 1x m l d t d x m l 解析器利用d t d 来验证x m l 文档的正确性。正是由于x m l 提供了 d t d 机制来描述和定义x m l 文档的模式信息，才使x m l 数据不同于一般的半结 构化数据。同时，d t d 本身是可以动态改变的，这为x m l 的扩展提供了方便。 d t d 描述了标识语言的语法和词汇表，也就是定义了文档的整体结构以及文 档的语法。符合x m l 规范的x m l 文档仅仅是格式良好( w e l l f o r m e d ) ，只有符合 该文档的d t d 定义才是有效的( v a l i d a t e d ) x m l 文档。 通过d t d 可以允许文档的编写者制定基于信息描述、体现数据之间逻辑关系 的自定义标记，确保文档的易读性、清晰的语义和易检索性。一个d t d 可以是内 部的，包含在x m l 文档的前导说明部分：也可以是外部的，作为一个外部文档被 引用。外部d t d 的优点是可以被多个x m l 文档所引用。对于表1 1 来说，就需 要有一个名称为d b l p d t d 的外部d t d ，它用来对该文档进行信息描述。表1 2 给出 了表1 1 中的x m l 文档的d t d 。 4 东北太学硕士学住论文 第一章引言 任何元素都是根元素的后代，出现在根元素内部。表中标签为d b l p 的元素即为根 元素。d b l p 元素有b o o k 和i n p r o c e c d i r t g 两个子元素。b o o k 和i n p r o c e e d i n g 元素都 具有属性k e y ，通过这个属性为每一个b o o k 和i n p r o c c e d i n g 分配一个文档内唯一的 标识。a u t h o r 元素是b o o k 和i n p r o c e e d i n g 元素的子元素，它有一个文本类型的元 素作为其子结点以表示其取值，例子中b o o k 元素有一个名为a u t h o r 的子元素其 值为“d a v i dm a i e r ”，而i t l p r c 日e e d m g 元素有多个a u t h o r 子元素，表示有多个作者 名字出现。c i t e 子元素具有属性l a b e l ，通过这个属性可以表示对文档中的 i n p r o c e e d i n g 元素的引用。 1 2d t d 和x m l s c h e m a 自x m l i 0 发布起关于x m l 新技术和规范不断涌现。关于x m l 数据模型 的规范主要包括d t d 和x m ls c h e m a 。 1 2 1x m ld t d x m i 解析器利用d t d 来验证x m l 文档的正确性。f 是由于x m i 。提供丁 d t d 机制来描述和定义x m l 文档的模式信息，才使x m l 数据不同于一般的半结 构化数据。同时，d t d 本身是可以动态改变的，这为x l v l l 的扩展提供了方便。 d t d 描述了标识语言的语法和词汇表，也就是定义了文档的整体结构以及文 f 的语法。符合x m l 规范的x m l 文档仅仅是格式良好( w e l l ，f o r m e d ) ，只有符合 该文档的d t d 定义才是有效雕j ( v a l i d a t e d ) x m l 文档。 通过d t d 可以允许文档的编写者制定基于信息描述、体现数据之问逻辑关系 的自定义标记，确保文档的易读性、清晰的语义和易检索性。一个d t d 可以是内 部的，包含在x m l 文档的前导说明部分；也可以是外部的，作为一个外部文档被 引用。外部d t d 的优点是可以被多个x m l 文档所引用。对于表ll 来蜕，就需 要有一个名称为d b l p d t d 的外部d t d ，它用来对该文档进行信息描述。袁1 2 给出 了表1 1 中的x m l 文档的d t d 。 了表1 1 中的x m l 文档的d t d 。 4 东北大学硕士学位论文 第一章引言 任何元素都是根元素的后代，出现在根元素内部。表中标签为d b l p 的元素即为根 元素。d b l p 元素有b o o k 和i n p r o c e e d i n g 两个子元素。b o o k 和i n p r o c e e d i n g 元素都 具有属性k e y ，通过这个属性为每一个b o o k 和i n p r o c e e d i n g 分配一个文档内唯一的 标识。a u t h o r 元素是b o o k 和i n p r o c e e d i n g 元素的子元素，它有一个文本类型的元 素作为其子结点以表示其取值，例子中b o o k 元素有一个名为a u t h o r 的子元素，其 值为“d a v i dm a i e r ”，而i n p r o c e e d i n g 元素有多个a u t h o r 子元素，表示有多个作者 名字出现。c i t e 子元素具有属性l a b e l ，通过这个属性可以表示对文档中的 i n p r o c e e d i n g 元素的引用。 1 2d t d 和x m ls c h e m a 自x m l l 0 发布起，关于x m l 新技术和规范不断涌现。关于x m l 数据模型 的规范主要包括d t d 和x m ls c h e m a 。 1 2 1x m l d t d x m l 解析器利用d t d 来验证x m l 文档的正确性。正是由于x m l 提供了 d t d 机制来描述和定义x m l 文档的模式信息，才使x m l 数据不同于一般的半结 构化数据。同时，d t d 本身是可以动态改变的，这为x m l 的扩展提供了方便。 d t d 描述了标识语言的语法和词汇表，也就是定义了文档的整体结构以及文 档的语法。符合x m l 规范的x m l 文档仅仅是格式良好( w e l l f o r m e d ) ，只有符合 该文档的d t d 定义才是有效的( v a l i d a t e d ) x m l 文档。 通过d t d 可以允许文档的编写者制定基于信息描述、体现数据之间逻辑关系 的自定义标记，确保文档的易读性、清晰的语义和易检索性。一个d t d 可以是内 部的，包含在x m l 文档的前导说明部分：也可以是外部的，作为一个外部文档被 引用。外部d t d 的优点是可以被多个x m l 文档所引用。对于表1 1 来说，就需 要有一个名称为d b l p d t d 的外部d t d ，它用来对该文档进行信息描述。表1 2 给出 了表1 1 中的x m l 文档的d t d 。 4 东北大学硕士学位论文 第一章引言 表1 2d t d 的举例 t a b l e1 2a ne x a m p l eo fd t d d t d 中使用元素类型声明( e l e m e n tt y p ed e c l a r a t i o n ) 来定义x m l 文档中的元 素和属性。类型声明结构如下： d t d 中元素有以下四种类型： ( 1 ) 父元素类型。这种类型元素只可以包含子元素，没有文本值。在这种 定义中还给出x m l 文档中子元素的出现次数，可以是“+ ”( 出现一次或多次) ， “( 出现0 次或多次) ，或者“? ”( 出现o 次或1 次) 。在上面的例子中，b o o k 元素可以有一个或多个a u t h o r 子元素。同时，还规定了兄弟子元素之间的关系， 可以是“， ( 顺序关系) ，也可以是“i ( 或关系) ； ( 2 ) 混合元素类型。这种类型元素可以包含文本或子元素。定义方式： 5 东北大学硕士学位论文 第一章引言 。在这种 类型中也可以定义子元素的出现次数； ( 3 ) a n y 元素类型。x m l 文档里该元素中可以包含任何内容。通常只把 文档的根元素规定为a n y 类型。定义方式： ( 4 ) 空元素类型。这类元素在x m l 文档中使用空元素标记，元素中没有 内容。定义方式： 。上面例子中c i t e 元素即为 空元素类型。 以上四种类型都可以定义元素的属性，定义方式： 上面例子中b o o k 元素具有名为k e y 的属性，属性类型是i d ，有效性约束是 # r e q u i r e d 。通常采用图形的方式来表示d t d 的结构。表1 2 所示的d t d 文档 可以表示成d t d 图的形式，如图1 1 所示。 o 一曲巾_ 门 o 口 元素节点 属性节点 文本节点 卤卤卤卤专卤卤吉卤 图1 1 实例文档的d t d 图 f i g u r e1 1d t dg r a p ho ft h es a m p l ed o c u m e n t 系 图1 1 中用不同的形状表示不同类型的x m l 结点，其中圆形表示元素 ( e l e m e n t ) 结点，菱形表示属性( a t t r i b u t e ) 结点，方形表示文本( t e x t ) 结点。 带箭头的线段表示元素问父子关系或者元素与属性之间的父子关系，如b o o k 是 d b l p 的子结点，k e y 是b o o k 的属性结点等等。在一些线段上标记有“ 或“+ ， 6 东北大学硕士学位论文 第一章引言 这些符号为d t d 中的元字符。例如，从结点i n p r o c e e d i n g 到a u t h o r 的线段上的“+ ” 符号表示i n p r o c e e d i n g 可能有一个或多个名为a u t h o r 的子结点。 1 2 2x m ls c h e m a x m ls c h e m a ，即x m l 模式，目前已成为w 3 c 用于描述x m l 的推荐标准， 目的是为了克服d t d 的局限性，为x m l 文档提供丰富的语法结构。尽管作为 描述结构化信息的一种机制，d t d 成功地为s g m l 和h t m l 开发人员服务了 2 0 年，但与x m ls c h e m a 相比，它存在着严重的局限性。具体表现如下： ( 1 ) d t d 是基于正则表达式的，描述能力有限； ( 2 ) d t d 基本没有数据类型的支持，在大多数应用环境下表现能力不足； ( 3 ) d t d 的约束定义能力不足，无法对x m l 实例文档作出更细致的语义 限制； ( 4 ) d t d 的结构不够结构化，重用的代价相对较高； ( 5 ) d t d 并非使用x m l 作为描述手段，而d t d 的构建和访问并没有标准 的编程接口，无法使用标准的编程方式进行d t d 维护。 x m ls c h e m a 如同d t d 一样是负责定义和描述x m l 文档的结构和内容模式。 它可以定义x m l 文档中存在哪些元素和元素之间的关系，并且可以定义元素和属 性的数据类型。它提供了一种比d t d 更强大、更灵活的语法机制，以下是x m l s c h e m a 的优点： ( 1 ) x m ls c h e m a 基于x m l ，没有专门的语法。它与d t d 的区别最明显 的地方就是x m ls c h e m a 是真正在x m l 中写的。w 3 cx m ls c h e m a 规范列出 了可以用来限制x m l 文档的词汇表。这意味着所有可以用来生成和操作x m l 文档的工具都可以用来操作x m ls c h e m a 。 ( 2 ) x m ls c h e m a 支持丰富的数据类型。这是x m ls c h e m a 最大的优点之 一。利用x m ls c h e m a 可以在模式中指定元素内容和属性值的数据类型，包括 字符串、整数、布尔数、浮点数或是其他任何一种类型。这样，应用程序可以 利用有效性验证组件保证文档是有效的，同时保证其中的信息和预期的数据类 型相匹配。 ( 3 ) 对内容模型的有力支持。x m ls c h e m a 考虑到了更复杂和灵活的内容 模型，可以用它来验证混合内容的有效性，也可以用它来指定元素出现的确切 7 东北大学硕士学位论文 第一章引言 次数，还可以用它来为元素组命名。不论你要处理文本还是其他形式的数据， 这些特性都是很有价值的。 ( 4 ) x l v i ls c h e m a 提供可扩充的数据模型。使用x m ls c h e m a 可以更强大 的扩充能力，主要体现在：在另一个模式中复用模式部分功能的能力。定 义在不同模式中复用复杂结构的能力。从已有数据类型出发定制自己的新数 据类型的能力。在一个文档实例中引用多个模式的能力。 ( 5 ) x m ls c h e m a 支持综合命名空间； ( 6 ) x m ls c h e m a 支持属性组。 s c h e m a 中主要包括几种部件：元素( e l e m e n t ) 、属 生( a t t r i b u t e ) 、类型( 简单类 型s i m p l e t y p e 、复杂类型c o m p l e x t y p e ) 和注释( n o t a t i o n ) 。元素代表对应的x m l 实 例文档的基本要素，由名称和类型组成。属性表示元素的必要补充，在x m l 实例 文档中不能单独存在，只能包含在元素中。类型表示元素的结构和取值限制，其 中具有简单类型的元素中只能包含数字、字符串或其他数据，而不能包含子元素 和属性；具有复杂类型的元素可以包含子元素和属性，也可以包含数字和字符串 等其他数据。 1 3d o m 及s a x 标准 1 3 1d o m 标准简介 d o m 2 1 ( d o c u m e n to b j e c t m o d e l ) 是w 3 c 提出的一组应用与x m l 的编程接口。 它定义了x m l 文档的逻辑结构以及文档的访问和修改方法，因此d o m 可以用来 管理x m l 文档中的信息和数据，同时w 3 cd o m 是独立于语言和平台的定义， d o m 没有提供特定的实现，因此d o m 能够通过任何编程语言实现。 d o m 是x m l 文档的编程基础。有了d o m ，程序员可以创建一个文档，按文 档的结构进行遍历、增加、删除和修改x m l 文档中的元素( e l e m e n t ) 和内容 ( c o n t e n t ) 。w 3 c 组织在制定d o m 接口时即要求该标准具有平台无关性，使它能 够在任何平台上以任何语言实现，所以d o m 标准是使用o m gi d l 语言编写的。 利用对象模型，d o m 确定了用来表示和操纵文档的接口和对象；同时确定了这些 接口和对象的语义，包括各种行为和属性。 d o m 标准是为文档操作制订的一组程序a p i 。它建立在一个与它要表现的文 8 东北大学硕士学位论文 第一章引言 件非常相似的对象结构上。与d t d 所表示的文档类型和约束不同，d o m 表示x m l 文档的内容。 举例说明：对应于表1 1 的实例文档的d o m 树如图1 2 所示。其中圆圈代表 元素节点，矩形代表文本值节点，三角代表属性节点，这里我们省略了属性值的 表示。 t e x t ( ) o e y 厂 i - j 图1 2 示例文档的d o m 树 f i g u r e1 2d o m t r e eo ft h es a m p l ed o c u m e n t 争 一j 元素节点 属性节点 文本节点 父子关系 引用关系 虽然d o m 只是访问x m l 文件的方法之一，可是相对于其它的访问机制，d o m 有以下特点： ( 1 ) d o m 标准不是一个二进制标准，用同一种语言实现的d o m 绑定时具有 跨平台性，d o m 标准中并没有定义任何形式的二进制互用性； ( 2 ) d o m 标准不是一种永久性存储x m l 和h t m l 数据的方法，它仅仅定 义了如何以对象的方式存储x m l 和h t m l 数据的方法； ( 3 ) d o m 标准不是一套数据结构，它只是定义了接口的对象模型； ( 4 ) d o m 没有定义文档中哪些信息是相关的或这些信息是如何组织的； ( 5 ) d o m 标准不是c o m 标准的竞争者。c o m 同c o r b a 一样，是一种定 义接口的方法，与对象的语言无关，d o m 是一套用来操作x m l 和h t m l 数据 的接口和对象。 1 3 2s a ) ( 标准简介 s a x ( s i m p l ea p i f o rx m l ) 是一个用于分析x m l 的事件驱动的编程接口。 9 东北大学硕士学位论文 第一章引言 s a x 不像d o m 那样是w 3 c 的推荐标准，它是由x m l d e v 邮件列表的成员开发 维护的。实际上，s a x 不是一个x m l 分析器，而是其他兼容s a x 的解析器要实 现的接口和帮助类的集合，它采用基于事件驱动的处理模式，它将x m l 文档转化 成一系列的事件，由单独的事件处理器来决定如何处理。s a x 不是通过构造一棵 节点树，而是通过一系列的事件让你访问x m l 文档中的信息。它并不在文档之上 创建对象模型，因此它能更快地处理文档而且使用更少的内存。所有的s a x 解析 器要做的工作就是遍历整个x m l 文档，并且根据遇到的标记激活事件。因此， s a x 可以看作是一个低层的分析方法：它比其他的分析方法( 如d o m ) 速度更快 而且使用更少的内存，但需要更多的编程工作。 s a x 的基本原理是由接口的用户提供符合定义的处理器，x m l 分析时遇到特 定的事件，就去调用处理器中特定事件的处理函数。一般s a x 接口都是用j a 、，a 实现的。在s a x 接口规范中，有六个基本a p i 接口：s a x p a r s e r f a c t o r y 、p a r s e r 、 d o c u m e n t h a n d l e r 、e r r o r h a n d l e r 、d t d h a n d l e r 、e n t i t y r e s o l v e r 。几个基本的接口 中的作用如下： ( 1 ) s a x p a r s e r f a c t o r y 接口的对象用来按照系统属性中的定义创建一个分析 器的实例。 ( 2 ) p a r s e r 接口定义了类似s e t d o c u m e n t h a n d l e r 的方法来创建事件处理函数。 另外，该接口中还定义了p a r s e r ( u r e ) 方法来对x m l 文档进行实际的分析工 作。 ( 3 ) d o c u m e n t h a n d l e r 接口。当分析器遇到x m l 文档中的标记时，就会激活 该接口中的s t a r t d o c u m e n t ，e n d d o c u m e n t ，s t a r t e l e m e n t 以及e n d e l e m e n t 等方 法。 ( 4 ) e r r o r h a n d l e r 接口。当分析器在分析过程中遇到不同的错误时， e r r o r h a n d l e r 接口中的e r r o r 、f a t a l e r r o r 或者w a r n i n g 方法就会被激活。 ( 5 ) d t d h a n d l e r 接1 2 。当处理d t d 中的定义时，就会调用该接口中的方法。 ( 6 ) e n t i t y r e s o l v e r 接口。当分析器要识别由u r i 定义的数据时，就会调用该 接口中的r e s o l v e e n t i t y 方法。 d o m 接口和s a x 接口有着各自的优缺点。也正是如此，它们一直长期并存 着，在不同的应用中发挥不同的作用。 1 0 东北大学硕士学位论文 第一章引言 1 4x m k 的特点与优势 x m l 作为一种性能卓越的标记语言，有许多特点： 首先，x m l 很简单。x m l 经过精心设计，整个规范简单明了，它由若干规 则组成，这些规则可用于创建标记语言，并能用一种常常称作分析程序的简明程 序处理所有新创建的标记语言。x m l 能创建一种任何人都能读出和写入的世界语， 这种创建世界语的功能叫做统一性功能。如x m l 创建的标记总是成对出现，以及 依靠称作统一代码的新的编码标准。 其次，x m l 是个开放的标准。x m l 是s g m l 在市场上有许多成熟的软件可 用来帮助编写、管理等，开放式标准x m l 的基础是经过验证的标准技术，并针对 网络做最佳化。众多业界顶尖公司，与w 3 c 的工作群组并肩合作，协助确保交互 作业性，支持各式系统和浏览器上的开发人员、作者和使用者，以及改进x m l 标 准。x m l 解释器可以使用编程的方法来载入一个x m l 的文档，当这个文档被载 入以后，用户就可以通过x m l 文件对象模型来获取和操纵整个文档的信息，加快 了网络运行速度。 再次，x m l 具有高效且可扩充的特性。支持复用文档片断，使用者可以发明 和使用自己的标签，也可与他人共享，可延伸性大，在x m l 中，可以定义无限 量的一组标注。x m l 提供了一个标示结构化资料的架构。一个x m l 组件可以宣 告与其相关的资料为零售价、营业税、书名、数量或其它任何数据元素。随着世 界范围内的许多机构逐渐采用x m l 标准，将会有更多的相关功能出现：一旦锁定 资料，便可以使用任何方式透过电缆线传递，并在浏览器中呈现，或者转交到其 他应用程序做进一步的处理。x m l 提供了一个独立的运用程序的方法来共享数据， 使用d t d ，不同组中的人就能够使用共同的d t d 来交换数据。你的应用程序可以 使用这个标准的d t d 来验证你接受到的数据是否有效，你也可以使用一个d t d 来验证你自己的数据。 最后，x m l 支持国际化。标准国际化，且支持世界上大多数文字。这源于依 靠它的统一代码的新的编码标准，这种编码标准支持世界上所有以主要语言编写 的混合文本。在h t m l 中，就大多数字处理而言，一个文档一般是用一种特殊语 言写成的，不管是英语，还是日语或阿拉伯语，如果用户的软件不能阅读特殊语 言的字符，那么他就不能使用该文档。但是能阅读x m l 语言的软件就能顺利处理 东北大学硕士学位论文 第一章引言 这些不同语言字符的任意组合。因此，x m l 不仅能在不同的计算机系统之间交换 信息，而且能跨国界和超越不同文化疆界交换信息。 x m l 给基于w e b 的应用软件赋予了强大的功能和灵活性，因此它给开发者和 用户带来了许多好处： ( 1 ) 更便利的搜索手段：数据可被x m l 唯一的标识。，搜索软件不必了解 每个数据库是如何构建的。 ( 2 ) 更灵活w e b 应用软件开发方式：数据