（计算机应用技术专业论文）xml数据库查询优化技术的研究.pdf

哈尔滨t 车i f 1 大学硕十学位论文 摘要 随着i n t e m e t 技术的发展，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 数据库的查询结构，并对查询处理过程中的每一阶段 进行了详细的分析，重点研究了逻辑优化和物理优化阶段的优化策略，并研 究了三种常用的x m l 数据库查询优化技术：基于路径索引的优化技术、基 于编码的优化技术和基于模式的优化技术。 基于模式的优化是x m l 查询优化中的一个重要技术，它利用x m l 的模 式信息对查询表达式进行查询过滤、模式消减，从而达到查询优化的目的。 本文研究了一种基于x m ls c h e m a 模式的查询优化技术_ x s i s ，它结合模 式优化技术和路径索引技术来实现x m l 的查询优化。它分别采用p b i t r e e 、 区间编码对s c h e m a 文档和x m l 文档进行编码，对s c h e m a 文档和x m l 文 档分别建立索引，并同时给出了相应的查询处理方式；针对s c h e m a 模式中 出现的环模式这种特殊情况提出了一种建立消减树的解决方案；并将x s i s 与x i s s 进行了对比试验，进行了查询优化性能分析。最后，在对单s c h e m a 优化技术研究的基础上，对多s c h e m a 查询优化技术进行了探讨。 关键词：x m l ；x m l 数据库；s c h e m a ；查询优化 哈尔滨一i ：程人学硕十学何论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n t e r n e t ，x m lh a sg r a d u a l l yb e c o m et h es t a n d a r d f o rd a t ae x c h a n g i n go ni n t e r n e t ，i th a sa l s od e v e l o p e dan e wf i e l df o rt h e a p p l i c a t i o n o fd a t a b a s e - - x m ld a t a b a s e h o w e v e lt h e s e m i s t r u c t u r e c h a r a c t e r i s t i co fx m ld a t aa n dt h ed i f f e r e n c eb e t w e e nt h eq u e r yo fs p e c i a lx m l p a t he x p r e s s i o na n dt h es t r u c t u r e dq u e r yl a n g u a g eo fr e l a t i o n a ld a t a b a s e ，m a k et h e q u e r yo p t i m i z a t i o nt e c h n o l o g i e so f t h er e l a t i o n a ld a t a b a s en ol o n g e ra p p l i c a b l ef o r x m ld a t a b a s e t h e r e f o r e ，x m lq u e r yo p t i m i z a t i o nt e c h n o l o g i e sb e c o m ea n i m p o r t a n t f i e l di nx m ld a t a b a s er e s e a r c h t h i st h e s i sr e s e a r c h e st h eq u e r ys t r u c t u r eo fx m ld a t a b a s e ，a n da n a l y z e st h e s t e p s o ft h e q u e r yp r o c e s s i n g ，w h i c h f o c u s e so nt h e s t r a t e g y o f l o g i c a l o p t i m i z a t i o na n dp h y s i c a lo p t i m i z a t i o n t h e n ，i tr e s e a r c h e st h r e em e t h o d so f q u e r yo p t i m i z a t i o nt e c h n o l o g i e so fx m ld a t a b a s e t h e ya r eo p t i m i z a t i o nb a s e d o np a t hi n d e x ，o p t i m i z a t i o nb a s e do ne n c o d i n ga n do p t i m i z a t i o nb a s e do nx m l s c h e m a o p t i m i z a t i o nb a s e do ns c h e m a i sa ni m p o r t a n tm e t h o do fx m l q u e r y , w h i c h c a nc u td o w nt h eq u e r ye x p r e s s i o nb yt h ei n f o r m a t i o no fs c h e m at oo p t i m i z et h e q u e r yo fx m l t h i st h e s i sb r i n g sf o r w a r da k i n do fx m l o p t i m i z a t i o nt e c h n o l o g y b a s e do nx m ls c h e m a - - x s i s x s i si n t r o d u c e sp b i t r e ee n c o d i n ga n dr e g i o n e n c o d i n gt oe n c o d ex m ls c h e m ad o c u m e n ta n dx m l d o c u m e n ts e p a r a t e l y , a n d b u i l d si n d e x i n gf o rs c h e m ad o c u m e n ta n dx m ld o c u m e n t ，t h e ni n t r o d u c e st h e p r o c e s s i n go fq u e r y i n gi nx s i s x s i sa l s ob r i n g sf o r w a r da k i n do fb u i l d i n g r e d u c e t r e et or e s o l v et h el o o po fx m ls c h e m a t h i st h e s i sa l s oc o m p a r e st h e r e s p o n s et i m eo fq u e r y i n gb e t w e e nx i s sa n dx s i s f i n a l l y , t h i st h e s i ss h o w st h e d i s c u s s i o no fm u l t i - s c h e m at e c h n o l o g yb a s e do nt h er e s e a r c ho fs i n g l e - s c h e m a o p t i m i z a t i o nt e c h n o l o g y k e y w o r d s ：x m l ；x m ld a t a b a s e ；s c h e m a ；q u e r yo p t i m i z a t i o n 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除了文中 已注明引用的内容外，本论文不包换任何其它个人或者集 体已经公开发表的作品成果。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确的方式注明。本人完全 意识到本声明的法律结果由本人承担。 作者( 签字) ：主叁囡土璺 e l 期：砂甥年2 - 月硝e t 哈尔滨 ：程大学硕士学位论文 第1 章绪论 1 1 课题研究背景和意义 经过十多年的发展，i n t e m e t 已经成为新经济时代的标志，它极大地影响 着人们的生活方式、商业模式，对人类社会的进步起到巨大的推动作用。同 时伴随着i n t e m e t 的发展，i n t e r n e t 上的信息的数量级已由发展初期的m b 发 展到2 1 世纪初的g b ，现在已上升到t b 。面对庞大的信息海洋，人们遇到 了w e b 上存在的一个大问题：虽然可以在线获得各种信息，但是要找到所需 要的信息却极为困难。在新的需求的驱动下，人们提出了一种新的着重描述 页面内容的可扩展标记语言- x ml f l l ( e x t e n s i b l em a r k u pl a n g u a g e ，可扩展 标识语言) 。 x m l 是w 3 c ( w o r l dw i d ew e bc o n s o r t i u m ) 为适应i n t e m e t 的发展，解决 数据的结构化问题而推出的新型w e b 语言，它并不是类似于h t m l 的预定 义的标识语言，而是用于定义其它标识语言的一种元语言。与h t m l 中有固 定数量的标识不同，x m l 用于描述信息的各种标识都可以由设计者自行建 立，以强化特定专业数据的结构和关联。和h t m l 相比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 数据库是w e b 数据库中的一种，它从数据库的角度来研究以 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 查询技术研究还很不成熟。所以，进行x m l 数据库查询优化 的理论研究和应用研究，具有很高的理论意义和现实意义。 1 2 国内外研究现状 目前，对于x m l 数据库的研究主要集中在两方面：一种是在已有的关 系数据库系统或面向对象数据库系统的基础上扩充相应的功能，使其能够胜 任x m l 数据的查询处理，这种方式叫做x m l 使能数据库( x m l e n a b l e d d a t a b a s e ) 。第二种则是为x m l 数据量身定做的数据库纯x m l 数据库 ( n a t i v e x m ld a t a b a s e ) 。纯数据库充分考虑到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 数据库查询 优化的研究主要集中在下面几个方面： ( 1 ) 基于路径表达式的优化方法。该方法通常利用x m l 文档的模式信息 产生优化规则，对路径表示式进行重写以实现优化目的。s p h i n x 幢，是第一个 利用x m l 文档模式d t d 对x m l 文档进行索引的方法。路燕等人b 提出了 d b x i ( d t d b a s e dx m li n d e x i n g ) 方法，是一种基于d t d 的优化机制，它利 用了d t d 模式信息对于查询进行表达式优化，可以大大减小搜索空间，提高 查询效率。 ( 2 ) 关于x m l 查询代数的研究。通过建立一个查询代数，并定义各种代 数操作，利用这些代数操作来实现查询优化。s t a n d f o r d 大学开发的x m l 数 2 哈尔滨丁程大学硕十学位论文 据库l o r e 系统h 刊针对系统本身提供的访问操作和索引情况，提出了一套独特 的代数操作，包括逻辑代数、物理代数和相应的转换规则。孟晓峰教授等人 订，在研究o r i e n t x 数据库和x q u e r y 查询语言的基础上，给出了o r i e n t x a 代数 的定义。 ( 3 ) 查询最小化。查询最小化问题的实质是等价问题，因为求一个查询 的最小化查询就是找与之等价的一个规模最小的查询，而等价问题的实质又 是查询的包含问题。目前包含的问题主要是针对x p a t h 进行研究，最早提出 x p a t h 最小化的w o o d 伸指出：一个x p a t h 可以表示为合取范式，对x p a t h 等 价性检查的复杂度等价于对合取范式的等价性检查。 ( 4 ) 查询结构连接次序优化。结构连接是x m l 查询中的核心操作，而且 越来越多的实现将结构连接作为基本的物理操作符之一。因此，x m l 查询结 构连接顺序的选择是x m l 查询优化的中研究的热点。连接顺序的选择主要 涉及到两个问题：第一，有效的估计连接代价方法，文献【9 ，l o 中指出可以采 用位置直方图、区间模型；第二，搜寻枚举空间的策略，文献 1 1 】提出穷举 式动态规划法、带剪枝的动态规划法、全流水线方式。 目前，关于x m l 查询优化及其相关技术研究已经取得了一些成果，但 是仍存在一些不足： ( 1 ) x m l 的查询优化都没有充分利用x m l 的模式信息和语义信息。一 些使用x m l 模式的系统，如：d b x i 也只是考虑了x m ld t d 模式的一些简 单情况，对模式信息中比较复杂的环模式都没有进行深入的研究，并且很少 有专门针对x m ls c h e m a 模式的查询优化研究。 ( 2 ) 关于x m l 查询代数的研究目前才刚刚起步，还没有统一的x m l 查 询代数标准；目前，研究的重点在于查询代数的定义和从查询语言到查询代 数的转换方面，对查询优化方面涉及到的很少。 1 3 论文的主要研究内容 查询优化技术一直是数据库界研究的热点，但是查询优化是比较难实现 的。作为x m l 模式语言s c h e m a 描述了x m l 文档的结构信息，它为x m l 文档结构、内容和数据类型建模提供了严格而完整的标准，由于出现的比较 晚，目前在x m l 中应用并不是很广泛，所以现有的大部分索引方法中没有 3 哈尔滨工稃大学硕士学何论文 利用x m ls c h e m a 这一有效资源。在实际应用中，虽然x m l 标准并不要求 必须使用s c h e m a ，但是在是电子商务、电子政务、电子数据集成系统中由于 要统一数据格式，x m l 文档都使用x m ls c h e m a 来统一数据格式。因此， 研究使用s c h e m a 的索引机制来实现x m l 查询优化是一条应当重视的有效途 径。 本文对x m l 查询优化的研究主要集中在以下几个方面： ( 1 ) 在研究和分析x m l 数据库查询处理结构的基础上，从逻辑优化和物 理优化这两个层次上分别对x m l 数据库的查询优化技术展开研究；研究了 三种x m l 查询优化技术：基于路径索引的优化技术、基于编码的优化技术、 基于模式的优化技术。 、 ( 2 ) 针对目前大部分的x m l 的查询优化技术没有充分利用到x m l 的模 式信息和语义信息，本文提出了一种利用s c h e m a 模式信息来实现x m l 查询 优化的技术x s i s ( x m ls c h e m ai n d e x i n gs y s t e m ) ，在x s i s 中重点研究和 解决：s c h e m a 模式中环模式的处理方式；s c h e m a 文档和x m l 文档的编码方 式；x s i s 的索引结构和机制；x s i s 中x m l 查询处理方式；通过与x i s s 进 行效能分析，验证x s i s 的查询性能。 1 4 论文的组织结构 本文总共分为四章，各章内容组织如下： 第1 章介绍本课题的研究背景、意义，及国内外研究现状，并指出本课 题的主要研究工作。 第2 章介绍x m l 数据库的一些关键技术，在介绍x m l 的基础上介绍了 x m l 数据库系统及纯x m l 数据库系统，随后对纯x m l 数据库的存储方式、 索引机制和查询语言进行了论述，这些将会为后面的研究提供基础理论支持。 第3 章研究x m l 数据库查询处理结构，主要从逻辑优化和物理优化这 两个层次上分别对x m l 数据库的查询优化技术展开研究，并提出一些可行 的优化策略，并介绍了三种查询优化技术：基于路径索引的优化技术、基于 编码的优化技术和基于模式的优化技术。 第4 章研究了一种新的x m l 查询优化技术：基于s c h e m a 的查询优化技 术- x s i s ，详细说明这种技术的具体的实现方式；并通过对比试验，验证 4 哈尔滨丁稗人学硕士学位论文 了x s i s 的查询性能：并在单s c h e m a 机制的基础上对多s c h e m a 的机制进行 了探讨和研究。 最后，对本文在课题中所做的工作进行全面的总结，并指出下一阶段要 完成的后续工作。 5 哈尔滨丁程大学硕十学1 _ 奇= 论文 第2 章x m l 数据库技术简介 随着i n t e m e t 的发展，数据库领域面临着前所未有的挑战。传统的关系 数据库管理w e b 上的不规则和非结构化的x m l 数据时显得力不从心，针对 这一情况提出了x m l 数据库的概念。x m l 数据库就是从数据库的角度来研 究以x m l 表达的数据，它包括x m l 数据的存储、模式管理、查询处理等。 x m l 在数据库领域相关的研究，主要集中在三个方面：x m l 数据的存储技 术、索引技术和查询处理技术。 2 1x m l 技术简介 2 1 1 m l 文档类型 x m l 文档按其文件内容可以分成两大类：以文档为中心的文档和以数据 为中心的文档n ”。 以文档为中心的文档是指利用x m l 来获取自然语言的那些文档，如用 户手册。它们以复杂或无规则的结构和混合内容为特征，而且文档的物理结 构非常重要。这些文档的处理侧重于给用户提供信息的最终表示，因此它们 也被称作面向表示的文档。 以数据为中心的文档主要利用x m l 来传送数据，这些文档包括销售订 单、病人记录和科学数据等。面向数据处理的x m l 文档的物理结构，如元 素的顺序，或者数据被存储为属性还是子元素，通常不是很重要。它们的特 征是高度有序的结构，并且同时带有那些数据结构的多个副本，类似于关系 数据库系统中的多条记录。这些文档的处理通常侧重于应用程序间的数据交 换，因此它们也被称作面向消息的文档。同时，这两类文档有时也简称为面 向文档的文档和面向数据的文档。 以数据为中心的文档主要用作数据传输，是一种面向机器的文档。其结 构规整、数据粒度精细，但其物理结构( 即兄弟元素的顺序、数据是存放在属 性中还是p c d a t a 元素中、是否使用实体等) 并不重要。以文档为中心的文 6 哈尔滨丁程人学硕十学位论文 档是面向人的文档，具有1 、= 规则结构和混合内容，其物理结构是重要的。面 向数据处理和面向文档处理的x m l 文档之间的区别不大，然而文档上需要 执行的操作是不一样的。在一个面向文档处理的x m l 文档中，需要执行的 操作包括检索整个文档、搜索关键词、修改一部分或重排一部分。在一个面 向数据处理的x m l 文档中，需要执行的操作包括检索文档的一个指定部分、 搜索元素和数据的一个特定的结合、修改或删除一个简单的元素或一块简单 的数据，或者给文档添加一个新元素。 2 1 2x m l 数据模型 数据模型是人们对现实世界的抽象，它是随着应用的需求和人类对信息 管理研究的不断深入而逐渐发展的。1 9 7 0 年e e c o d d 提出了关系模型，在此 基础上建立的关系数据库获得了巨大的成功。后来又出现了面向对象的数据 模型，它能表达数据间的嵌套、递归关系，并且具有面向对象技术的封装性 和结构性的特点，基于对象的数据库系统也应用而生。模式的作用在于检验 数据和查询优化，而x m l 数据的模式却是不规则、不固定的。目前，比较 常用的数据模型有两种：d o m ( d o c u m e n to b j e c tm o d e l ) 和o e m ( o b j e c t e x c h a n g em o d e l ) 。 w 3 c 组织为x m l 数据定义了文件对象模型d o m ，用于将x m l 数据映 像到一定的数据结构中，在d o m 模型树中有几种类型的结点：d o c u m e n t 、 r o o t 、t e x t 、e l e m e n t 、a t t r i b u t e 。当使用d o m 对x m l 文本文件进行操作时， 它首先解析文件，将文档中的元素、属性、注释、处理指令都看作结点( n o d e ) ， 然后在内存中以结点树的形式创建x m l 的文件表示。d o m 树，除了r o o t 或d o c u m e n t 结点以外的每个结点都有一个父结点。a t t r i b u t e 结点总是和一个 e l e m e n t 结点相关联，而用来封装元素的起始标记和结束标记中的文本是映 射到一个t e x t 结点的；t e x t 结点是e l e m e n t 结点的一个子结点；t e x t 结点表 示在x m l 文件中的一段文本；e l e m e n t 结点表示x m l 文件；而a t t r i b u t e 结 点表示一个元素内部的属性名和值。d o m 定了一整套访问x m l 元素和属性 的接口，程序可以很容易地存取文件的结构和内容。支持d o m 的x m l 解析 器按照d o m 规范，把x m l 文档分解为一颗包含文件中所有元素的树结构， 程序可以通过d o m 定义的接口访问和更新x m l 文件的样式、结构和内容。 7 哈尔滨。= 群大学硕十学何论文 但是，d o m 规范定义的是一棵树的形式，并不直接支持图结构，在x m l 中 通过i d 和i d r e f 属性来解决这个问题。基本原理是一个元素可以有一个类 型为i d 的简单属性，它提供了一个唯一的标识符，而这个标识符可以为其它 元素的i d r e f 或i d r e f s 属性所引用。在d o m 中，把i d r e f 或i d r e f s 的值作为字符串值，并没有体现了链接关系。 1 9 9 5 年，斯坦福大学的研究人员提出了o e m ( o b j e c te x c h a n g em o d e l ) 模 型“”，用于描述半结构化数据。它定义于斯坦福大学的t s i m m i s 系统中，该 系统用于异构数据源的集成。后来，很多类似的系统也使用该模型或它的变 体，因此它已经成为通用的半结构化数据模型。 一 o e m 模型中，半结构化数据可以用一个有向的标记图来表示。一个o e m 对象由一个四元组 表示，其每个域的意义如下： ( 1 ) l a b e l ( 标注) ，变长字符串，描述对象的意义； ( 2 ) t y p e ( 类型) ，对象值的类型，包括两种：一种为原子型( a t o m i c ) ，如 i n t e g e r , r e a l ，s t r i n g ，i m a g e ，p r o g r a m 等；另外一种为复杂类型( c o m p l e x ) ，包含零 个或多个子对象，每个子对象用一条带标记的边与其相连。对象类型为原子 型的称为原子对象，而对象类型为复杂类型的称为复杂对象； ( 3 ) v a l u e ( 值) ，对象的值； ( 4 ) o l d ( 对象标识) ，用于唯一标识每个o e m 对象。 而且在o e m 中，每个对象允许有多个父对象，因此在有向图中允许环 的存在。x m l 具有半结构化数据的许多特征，如描述性、结构不固定和易变 性。o e m 模型中标记、对象、原子值分别对应于x m l 中的标记、元素和 p c d a t a 。但是x m l 和o e m 模型之间也有很大的区别，主要体现在以下几 个方面： ( 1 ) o e m 模型不是一个有序的数据模型，对象的各个子对象之间没有固 定的顺序，而x m l 则是有序的数据： ( 2 ) o e m 中没有属性的概念，只有子对象； ( 3 ) x m l 不允许同一个元素有多个父元素，是一种树形结构的数据，但 它采用特殊类型的属性i d 和i d r e d 来实现元素到元素之间的链接，从而可 以演变成一种图形结构。 8 哈尔滨工程大学硕十学位论文 2 1 3x 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 、 s c h e m a 。 d t d “( d o c u m e n tt y p ed e f i n i t i o n ，文档类型定义) 用不同于x m l 的独立 语法来规定x m l 文档中各种元素集合的内容模式，它主要采用元素类型声 明和属性表声明限制x m l 文档中元素的结构。 一个d t d 通过具体说明每一个元素和属性的名称、元素与子元素之间的 嵌套关系、子元素的出现次数来定义x m l 文档的结构模型，其中可以利用 操作符宰( o 次或多次) 、+ ( 1 次或多次) 、? ( 0 次或1 次) 、i ( 或选) 来定义子元素 的出现次数。在d t d 文档中，e l e m e n t 表示元素，a t t l i s t 表示属性， 撑p c d a t a 表示数据。x m l 的强大功能就在于多个文档可以共享常用的d t d 。 这些d t d 可以由不同的人编写，它为形成一直的标记标准并使其文档化提供 了_ 种方式。 d t d 是x m l 由s g m l 处继承而来并加以发展的文档类型定义方法，有 着一定的缺陷：它本身不是用x m l 书写的；不支持名字空间；提供了非常 有限的数据类型；不能表达元素中字符数据的数据类型；虽然有扩展机制， 但这个机制太复杂而且很脆弱，一组被定义的参数体的属性之间不能建立任 何联系。 针对d t d 存在的不足，w 3 c 又提出了x m ls c h e m a 来表达x m l 的内 容和结构n “。x m ls c h e m a 是一种描述信息结构的模型。它用来定义x m l 文 档的文本结构、数据类型等x m l 文档描述规则。它为一类文档建立一个模 式，规范了文档中的标记和文本的可能组合形式。它不仅包括了d t d 所能实 现的多有功能还提供了一系列的新特色。 x m ls c h e m a 本身就是x m l 文档，使用标准x m l 语法，因此可直接用 一般的x m l 解析器对其进行语法分析，并有强大、易用的扩展功能。x m l 9 哈尔滨t 程大学硕士学何论文 s c h e m a 支持丰富的数据类型包括数字型、布尔型、整型、日期时间、u r l ( 统 一资源标识符) 、十进制数等等。它允许对数据进行更严格的合法性检查，而 且还支持由这些简单的类型生成更复杂的类型。x m ls c h e m a 内容模型是开 放的，可以随意扩充、更新。 2 2x m l 数据库系统 2 2 1x m l 数据库的分类 所谓数据库就是一组相互有关联的数据集合，而l 数据库是一个 x m l 文档的集合，这些文档是持久的并且是可操作的。目前x m l 数据库主 要有三种类型n 副： ( 1 ) x m le n a b l e dd a t a b a s e ( x e d b ) ，即支持x m l 的数据库。其特点是在 原有的数据库系统上扩充对x m l 数据的处理功能，使之能适应x m l 数据存 储和查询的需要。一般的做法是在数据库系统之上增加x m l 映射层，这可 以由数据库供应商提供，也可以由第三方厂商提供。映射层管理x m l 数据 的存储和检索，但原始的x m l 元数据和结构可能会丢失，而且数据检索的 结果不能保证是原始的x m l 形式，它的基本存储单位与具体的实现紧密相 关。这种方法的优点是可以利用已有的非常成熟的关系数据库技术，目前一 些主流的关系数据库如s q ls e r v e r 2 0 0 0 、o r a c l e 9 i 等都实现了对x m l 的查询 支持。 ( 2 ) n a t i v ex m ld a t a b a s e ( n x d b ) ，即纯x m l 数据库。其特点是以自然 的方式处理x m l 数据，以x m l 文档作为基本的逻辑存储单位，针对x m l 的数据存储和查询特点专门设计适用的数据模型和处理方法。同时访问x m l 数据时不需要执行任何转换工作，因而能够提供更好的性能。t a m i n o 和e x i s t “7 1 就是纯x m l 数据库。 ( 3 ) h y b r i dx m ld a t a b a s e ( h x d b ) ，即混合x m l 数据库。可以根据应用 的需求，可以视其为支持x m l 的数据库或纯x m l 数据库。 综上所述，支持x m l 的数据库将x m l 文档的数据存入关系数据库中， 破坏了原文档的结构，同时在存储、查找数据时要进行分解、映射等预处理。 造成了效率的低下。纯x m l 数据库由于保存了文档的原始结构，在存储查 1 0 哈尔滨工程大学硕十学位论文 找时不需要进行格式转换，从而能够提供更好的性能，因而是当前x m l 数 据库研究的热点。本文的对x m l 数据库的查询优化工作就是基于纯x m l 数 据库的。 2 2 2 纯x m l 数据库的定义 对于纯x m l 数据库，r b o u r r e t 在文献 1 2 1 0 0 给出了一个定义，即只有 满足一下3 个条件的x m l 数据库系统才能称之为纯x m l 数据库： ( 1 ) 为x m l 文档定义了一个逻辑模型，x m l 数据的存储和查询都是基 于这个模型，这个模型至少要包含元素、属性、以及p c d a t a 等，并保持文 档顺序。 ( 2 ) 将x m l 文档作为( 逻辑) 存储的基本单位，正如关系数据库将行作为 存储的基本单位一样。 ( 3 ) 不要求只能使用某一种特定的底层物理模型或某种专有的存储格 式。 其中第一个条件要求纯x m l 数据库必须基于某种模型。这是因为各种 数据库都基于不同的模型，就像关系数据库基于关系模型，层次数据库基于 层次模型一样。第二个条件的含义是：在纯x m l 数据库中，数据只有在_ 个x m l 文档中才有意义。尽管定义规定纯x m l 数据库系统中的基本存储单 位是x m l 文档，当然这并不妨碍以一个更小的数据单位来读取数据，比如 查询一个文档的片段，就像关系数据库中仍然可以查询一个元组的片段( 属性 值) 一样。第三个条件的含义是：底层的存储格式并不重要。事实上，很多纯 x m l 数据库系统是采用一些传统的数据库系统作为底层存储引擎，当然也有 采用专有存储格式的。 该定义强调了三个主要观点：( 1 ) 纯x m l 数据库专用于原封不动地存储 x m l 数据和x m l 模型的所有部件；( 2 ) 存入纯x m l 数据库中的是文档，从 纯x m l 数据库中取出的仍是文档；( 3 ) 从本质上看，纯x m l 数据库不是一 个独立的数据库。从上述定义中可以看出，纯x m l 数据库的核心在于其模 式，即它的逻辑模式必须是某种特殊的模型，而不能是关系的或面向对象的。 换句话说，纯x m l 数据库与支持x m l 的数据库的本质区别是其模式不同， 而不是其底层的存储方式不同。 1 1 哈尔滨t 程大学硕七学位论文 i 2 2 3 纯x m l 数据库的特性 一般认为纯 a v i l 数据应该具有以下几个特性：文档集合、查询、更新、 事务、锁和并发控制、二次开发接口等。 “文档集合 的概念比文档更高一层。一个“文档集合”把一类文档聚 集在一起方便用户操作。集合级别上的查询、修改操作都会反映到集合内的 每一个文档中。“文档集合 与文档的关系类似于关系数据库中“关系模式 和“关系 的关系。一般说来，一个文档集合关联一种模式。将文档加入到 有模式的文档集合时，会对要加入的文档进行模式验证。只有符合文档集合 模式的文档才可以加入。不同于关系数据库管理系统中模式的严格性，纯 x m l 数据库系统还提供了“无模式”的文档集合。即将一个文档放入该集合 中时，不必验证该文档的模式。这种文档集合一般用来存放存储格式很难统 一的半结构化的x m l 文档。 纯x m l 数据库系统至少要支持某种或集中查询语言，这些语言可以是 专有的也可以是有标准化组织指定的。目前x p a t h 是主流的查询语言，各种 产品都提供了或多或少的支持，但是x p a t h 作为数据库查询语言还有不少缺 陷，如不能分组、排序、连接等。作为x p a t h 的替代品w 3 c 提出的x q u e r y 则要强大的多，它支持循环、分组、排序、连接等。因此人们希望x q u e r y 能够像s q l 一样在纯x m l 数据库中一统天下，成为纯x m l 数据库查询语 言的标准。 相对于查询，更新和删除也许是纯x m l 数据库的一块心病，因为目前 对x m l 更新考虑的并不多。目前，一些主流的纯x m l 数据库系统对更新数 据方面的支持做的都不好( 比如通过d o m 来更新，或者提供自己的一套更新 机制) ，也没有统一的标准还是业界也学术界正在讨论的领域。 纯x m l 数据库都支持事务处理和并发控制。目前，x m l 数据库产品在 这一方面的支持也很弱，锁定的粒度较大，通常都是对整个文档( 而不是片段 进行锁定) ，所以并发度相对较低，远远达不到关系数据库那样令人满意。 纯x m l 数据库也提供了应用程序接口( a p p l i c a t i o np r o g r a m m i n g i n t e r f a c e s ，a p i ) 。如d o m 、s a x 等，它们提供了连接数据库、浏览元数据、 执行查询和返回结果的方法( m e t h o d s ) 。返回的结果通常是x m l 字符串、d o m 1 2 哈尔滨丁程人学硕十学何论文 树、s a x 事件等。如果查询返回结果是多个文档，a p i 通常会提供列举( i t e r a t i n g ) 这些结果的方法。对以数据为中心的应用，纯x m l 数据库的a p i 具有将应 用程序变量与返回文档的特定元素或属性相关联的能力，省去了应用程序为 构建内部数据对象而不得不对文档进行解析的工作，方便了应用程序的设计。 随着x m l 数据绑定技术应用的普及，这个特性还会得到更广泛的支持。 作为一个新的数据库纯x m l 数据库系统在很多方面都很不成熟，比如 规范化、引用完整性方面都很不成熟。总之，纯x m l 数据库技术作为一个 新的技术，要走向成熟还有很长的路。 2 3x m l 数据库查询语言 由于) ( 1 v l l 文档是一种半结构化数据，不能直接使用传统的s q l 查询语 言，而需要一种新型的x m l 查询语言对x m l 文档进行查询。同时这种新的 x m l 查询语言还必须满足这些的特点：采用规则路径表达的方法、不同x m l 数据源的集成、支持模糊查询、根据需要构建输出。x m l 查询语言的研究已 经取得了一些研究成果，提出了很多x m l 查询语言：l o r e l n 、x m l q l 、 x p a t h 和x q u e r y m l 等。 l o r e l 是通过半结构化查询语言发展过来的被认为是最早的x m l 查询语 言，它最初是由斯坦福大学设计实现的一种面向半结构化数据的查询语言， 后来又增加了对x m l 的支持。它结合了s q l o q l 的许多特征，能够处理灵 活多变的数据类型，并处理复杂的路径表达式，适用于半结构化数据的数据 模式预先不知道的情况。 x m l q l 是由a t & t 实验室提出的一种x m l 查询语言，它扩展了s q l ， 增加了c o n s t r u c t 语法，用于从查询的返回结果构造结果x m l 文件。 x m l q l 与s q l 很相似，有类似s e l e c t _ f r o m w h e r e 的查询结构，并 借鉴了一些半结构化数据查询语言的思想。 x p a t h 是w 3 c 组织推荐的一种路径导航式的简单x m l 查询语言，x p a t h 的主要目的是对一个x m l 文档进行寻址。x p a t h 在x m l 文档上的一个抽象、 逻辑结构上进行操作，而不是在它的表面语法上。它的主要目的是为对一个 x m l 文档进行寻址，主要构件是表达式。其中，最重要的表达式是定位路径 ( 1 0 c a t i o np a t h ) 表达式，简称路径表达式，它与计算机系统使用的文件系统极 13 哈尔滨丁程大学硕十学何论文 为相似。定位路径有两种，分别是相对定位路径和绝对定位路径。每个定位 路径表达式都由一个或多个定位步( 1 0 c a t i o ns t e p ) 组成。绝对路径以“ 开始， 它从文档树的根结点开始定位路径；而相对路径则以“ 开始，它直接从某 个定位步开始定位路径。x p a t h 中用上下文结点集来描述定位路径的求值过 程是如何进行的。上下文结点集定义为：表达式中给定点确定的当前结点集， 上下文定义为：正在处理的当前结点。 x q u e r y 是w 3 c 提出的一种基于标准的通用的x m l 查询语言，对于 x q u e r y 的一种比较恰当的说法是：x q u e r y 对于x m l 数据，就像s q l 对于 关系数据库一样。本文后续章节中提到的x m l 查询表达式都是采用x q u e r y 的。x q u e r y 是基于x p a t h 的，它具备x p a t h 的所有功能，除此之外，x q u e r y 还扩充了部分其他功能，如支持对范围的限定表达式： p u b b o o k y e a r = 2 0 0 0 ” a u t h o r 1t o3 】就表示选择x m l 文档中符合查询条件 的第一个到第三个a u t h o r 元素。每个x q u e r y 查询包括一个或多个查询表达 式。常用的x q u e r y 语法有：路径表达式、序列表达式、算术表达式与布尔 表达式、f l w o r 表达式、条件表达式、构造器、定量表达式以及函数调用 等。 2 4x m l 数据库的关键技术 2 4 1x m l 数据库存储技术 ：x 3 v l 数据库中的x m l 文档存储方式主要有三种：以文本形式存储整个 文档、基于模型的方式和混合模式啪，z u 。 ( 1 ) 基于文本存储的方式：即将x j m l 数据转换为字节流。这种方式将 ：x 3 m l 作为字节存储为文件系统中的文档、关系数据库中的b l o b 或其他特 定格式的文档，然后通过在这些文件或字段上建立一些索引，通过这种方式 来提供某些数据库的功能。从这个意义讲，一个支持c l o b ( c h a r a c t e rl a r g e o b j e c t ) 字段且具有x m l 处理功能的关系数据库也可以称为纯x m l 数据库。 对基于文本的纯x m l 数据库可以在文档级别上和文档内元素或属性级别