（计算机软件与理论专业论文）xml数据管理系统的研究与实现.pdf

摘要 f 随着互联网技术的发展，x m l 的应用也越柬越广泛，因此如何有效地管理和利 用好这种半结构化数据成为一个需要迫切解决的问题，x m l 数据管理系统是其中一 x 。 个重要的研究方向。在讨论了现有x m l 数据存储管理方法的基础上，本文探讨了一 种新的x m l 数掘存储管理方法，首先提出了一个形式化的x m l 数据模型，并对已 有的查询代数进行了扩充和改进，并建立了x m l 形式化查询代数系统，进而对x m l 查询语言进行了扩展和规范化处理，实现了一个x m l 数据管理系统原型x m l d m s ， 此外，还对x m l d m s 系统的查询优化技术进行了相关的研究。在x m l d m s 中把存 储和数据模型相分离，有利于用不同的方法实现该系统。实验表明，本文提出的新方 法能够有效存储和管理x m l 数据，查询优化技术也在一定程度上提高了查询效率。 关键字：x m l ；半结构化数据；数据模型；逐堑至至匣匿堑二垂畛夕。7 型咝业坐塑f 5 幽坐型 a b s t r a c t w i t nt h ed e v e l o p m e n to f i n t e r n e t x m lh a sb e e ng a i n i n gm o r ea n dm o r e a t t e n t i o n s m e a n w h i l e ，h o wt om a n a g ea n du s et h i sk i n do fs e m i s t r u c t u r e dd a t ae f i e c t i v e l yr e m a i n s a b i gp r o b l 。m x m ld a t am a n a g e m e n t s y s t e mi so n eo ft h eh o p i n ga p p r o a c h e st os 0 1 v et h i s p r o b l e no nt h eb a s eo ft h ee x i s t i n gx m ld a t am a n a g e m e n ts y s t e m ，t h i s d a p e rp u t s t o m r d8n o v e lm e t h o df o rt h e s t o r a g ea n dm a n a g e m e n to fx m l d a t a f i r s t ，t h ep a p e r b u i l d sax m lf o r m a ld a t a m o d e l ( x f d m ) t h r o u g he x t e n d i n ga n di m p r o v i n gt h e 。1 3 1 n gq u e r y8 i g e b r 8 ，w ec r e a t ean e wx m l f o r m a lq u e r ya l g e b r a s y s t e m ( x f q a s ) lh e n , w 。m a k 。3 0 m e e x t e n s i o n sa n ds t a n d a r d i z a t i o n so n x m l q l a n d i m p t e m e n t a 1 1x m l d a t am a n a g e m e n t s y s t e m ( x m l d m s ) f i n a l l y , w es t u d yt h e q u e r yo p t i m i z a t i o no n x m l d m s x m l d m sd e a l sw i t hs t o r a g ea n dd a t am o d e lr e s p e c t i v e l y w h i c hh e l p st o 1 m p i e m e mt h es y s t e mu s i n gd i f f e r e n tm e t h o d s e x p e r i m e n ts h o w st h a tt h cm e t h o d d u t t e d t o 8 r dmt h l s p a p 。a r t 。f f i c i e n t l y s t o r ea n d m a n a g ex m ld a t aa n dt h e q u e r y o p t i m i z a t i o nc a ni m p r o v e q u e r y sp e r f o r m a n c e s k 。y w o r d 5 ：x m l ；s e m i - s t r u c t u r e dd a t a ；d a t am o d e l ；x m lq u e r ya l g e b r a ；q u e r y d p t l m i z a t i o n i 柯 ：| _ j 几“、自儿人人、r 坝卜：j f 沦义 一 第一章引言 本章首先阐述了x m l 数据管理系统的研究背景，然后探讨了目自“x m l 数据管 理系统的研究现状、x m l 查询语言。最后提出了x m l 数据管理系统x m l d m s 的 系统结构和本文的组织结构。 1 i 研究背景 1 1 1 网络的兴起 8 0 年代以来t 随着计算机技术和通讯技术的发展，通过计算机网络互连实现信 息的共享已成为一种普遍要求。在这种情况下，原来只限于教育、科研工具的全美科 学技术网逐步发展成为包罗万象的i n t e r n e t 。 i n t e r n e t 在其建立和发展的过程中，始终遵循开放的原则，任何个人或机构既可 以使用它，也能为它的发展做出贡献，因此它拥有极其庞大的用户队伍。这种开放性 改变了网络的工作方式，对用户来说i n t e m e t 不仅使他们不再局限于单机状态，同时 也脱离了特定网络的约束。任何人只要进入i n t e r n e t ，就可以共享其中各个网络和计 算机上的资源，同世界各地的人们自由通信和交换信息。 在为人们提供计算机网络通信的同时，i n t e m e t 还为广大用户提供了友好的访问 方式。i n t e m e t 的出现使计算机网络技术和信息资源不仅被科学家、工程师和计算机 专业人员使用，也为广大的普通用户提供服务。正因为i n t e m e t 提供了便捷的数据发 御和访问方式，它在9 0 年代得以迅猛发展，深刻地改变着人们的生活、工作、学习 和思维方式。这一革命性的变化在很大程度上依赖于t i mb e m e r s l e e 所发明的超文 本标记语言，正是这种语言的易学易用性使网络上的信息发布变得更加简便，也使互 联网上的信息变得更加丰富多彩。 1 1 2 文本标记语言 h t m l 是在文本处理技术的基础上发展而来的，最初的文本处理把数据的格式描 述和数据本身混合起束，使计算机能够按照要求的格式进行排版和显示。 在这种方式中，格式信息由制作人员用特殊记号来描述，这种记号就成为“格式 化标记”。如果仅要求表现此类文档，格式化标记方式就已经能够满足要求了。但是 要对其做进一步的处理，则由于没有统一的标准而无法实现。 为了解决这一问题，i b m 公司总结出三条规则i l j ： x m 敬抛铺娌系统f 内彻，l j j7 艾脱 1 文档处理程序必须支持同种公共文档表现形式。 2 对于刁i 同的应用，这些公共格式必须能提供不同的标记以方便处理。 3 对文档进行一定的合法性检查。 1 9 7 4 年，g o i d f a r d 证明了“进行合法性检查的语法分析器”概念的可行性。从 此以后，国际标准化组织i s o 萨式设立一个小组根据这些规则来制定标准通用标记语 言s g m l ，作为复杂文档的交换标准。 s g m l 语言过于复杂，使用不方便，1 9 8 9 年t i m 经过几大简化，结合超文本概 念提出h t m l 。虽然h t m l 的丌发时间不长，但是它提供了超链接概念，用尖括号 作为标记而使其可以用任何文本编辑器来创建，更重要的是简单易用，这些特点使它 成为近1 0 年来i n t e m e t 上的主要信息发布方式。 但是，h t m l 主要是面向表示的，它的格式固定，比如 h t m l 只是将 h t m l 作为一号标题来显示，不能提供更多的信息。而随着网络技术的飞速发展，这 种专用的格式化标记对其互操作性的妨碍愈加明显。于是，人们又重新注意到了 s g m l 所遵循的三条原则，决定将更为丰富的s g m l 功能与h t m l 的简单性结合到 i n t e m e t 应用中去。由此提出了作为s g m l 子集，但同时又兼具h t m l 简单性的可扩 展性标识语言x m l 。 1 1 3 建立x m l 数据管理系统的必要性 和h t m l 类似，x m l 提供了标记的、分级的格式来表示文档。然而，和h t m l 不同，x m l 的标记不但用来表示数据项，而且也描述了数据本身的意义。所以用x m l 表示数据时可以做到不丢失任何语义的信息，并且使应用程序来解释x m l 文档成为 可能。一个应用程序获得x m l 文档后可以多方面解释该文档，它可以基于该文档的 内容进行查询，也可以根据实际需要重新构造相应的结构等。正是由于x m l 的这些 优点，使得x m l 成了目前i n t e m e t 上数据交换和表示的酋选。 数据交换和数据表示对x m l 的数据管理和各种操作提出了更高的要求。假如文 档用x m l 的方式表示和存储，那么从x m l 文档中提取、分析其内容就成为可能。 和h t m l 基于关键字的数据搜索不同，x l l 文档的查询有较高的准确性，能够准确 地定位到相应的数据，而不是简单地进行关键字搜索。 目前，关系型数据库管理系统依然是数据管理领域中最主要的工具，不同系统和 不同平台间的数据交换形式如图1 1 ，常常需要把关系表中的元组转化为x m l 文档 或是双方都认可的文档格式进行传输，而接收端再把x m l 文档转换为关系型数据。 因此数据传输过程中多了一层数据转化的工作。如果能够建立一个v i l 数据管理系 统，所有的数据表示和数据传输统一使用x m l 文档来表示，这样也就实现了数据应 用的系统无关性。 x m l x m lx 。m l 图1 1 不同系统问的信息交换模型 1 2 x m l 数据库管理系统的研究现状 1 2 1x m l 与数据库 在i n t e r n e t 发展的今天，数据库技术首先要解决的问题是：在数据库与i n t e m e t 之上所架构的信息系统之间寻找可结合的共同点。原有数据库技术面对的是若千个数 据库在一定的网络空间上连接起来的系统，在这个系统上它使用户有效地管理各自的 数据库，并集成起来完成一定的任务。在w e b 中这一情况发生了根本的改变，w e b 上存储的是一些无结构、无法组织管理的数据，每一个站点上的数据都是在无序的状 态下自生自灭。因此，对这些数据的管理和对传统结构化数据的管理有着本质差别。 w e b 到底是不是一个数据库? 一种观点认为w e b 并没有使数据库产生本质的改 变，改变的是w e b 上信息系统组织及管理的方式。t 9 9 8 年的一份报告形成了这样的 观点f8 j ：w e b 在改变一切，w e b 是一个巨大的数据库。但数据库技术没有在w e b 技 术的发展中扮演重要的角色，w e b 在迅速发展，但大量的数据并没有依赖于数据库技 术架构。从广义数据库的角度来说，w e b 是一个数据库，它是一组有用的相关信息的 集合；从狭义的角度来说，w e b 不是一个数据库，因为它不是按一定数据模型组织的 数掘集合。 目前x m l 已成为事实上的i n t e m e t 数据组织和交换标准，为w e b 的数据管理提 供了新的数据模型，随着并且大量的x m l 数据将出现在w e b 上。实质上，x m l 。 可以预见，很多成熟的数据库技术将进入w e b 信息处理领域，把w e b 变成一个巨大 的数据库，x m l 正是朝这个方向迈出的第一步。目前对x m l 数据的存储和查询方 面的研究方兴未艾。x m l 数据模型与半结构化数据模型有许多相似性，可以说它是 w w w 上的半结构化数据。它既为半结构化数据的研究提供了广阔的应用前景，同时 也推动了半结构化数据研究的发展。 凰龟 x m i 一数拟一：羁l 天系型数掘有许多年似之处，山十i h 者址种典型的! 仁结构化数据 1 , 2 , 3 , 9 1 “n 此二者又存在不同点： - 5 e ，x m l 数掂模型表达能力要l e 关系模型和对象 模型更蚀；其次，x m l 数据有自己的特点，简单地应用传统的数据库技术不能使其 得剑完伞的体现；第三，x m l 主要应用于互联网上的信息表示和信息交换，而传统 的数掘牌技术对这些应用并不擅长；第四，w 3 c 在x m l 工作文本中为其定义了很多 数掘库的特性。针对于x m l 和数掘库，表11 归纳了它们的特点 表11x m l 和数掘库的比较 1 2 2 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 o m 或s a x 对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 4 。于是提出了利用现有的关系数据库、面向对象数据库对x m l 数据进行 管理的方法1 , 2 1 。该方法先把x m l 文档转化为结构化的数据 1 3 , 1 4 1 ，然后利用现有 的数据库管理系统存储x m l 数据，对数据的查询就相应地转化为对结构化数据的查 询( s q l 、o q l 、s t r u q l ) ，最后把查询结果转化为x m l 文档。这成了大多数研究 x m l 文档查询的主要方法。它的优点主要在于可以利用现有的一些数据库管理系统 ( 如：关系数据库管理系统、对象关系数据库管理系统和面向对象数据库管理系统) 较为成熟的技术。它的主要缺点在于：首先，由于x m l 文档是一种半结构化数据， m 父系数挪：库管f 4 系统或书是向刘象数拆 库管理系统鄙赴而阳结构化数抛的，z i j 阳 厅之| 1 j 进行数圳的转化必然要丢失一一定的信息：而且为了适应x m l 文档表示方式的 随意f ，必定要产生大量的冗余数据，这就破坏了表结构的紧凑性，【i 土浪赞了磁盘空 州：其次，由于x m l 文档具有结构多变的特点，结构上的每一次变化部可能引起所 对应数据库管理系统表结构的改变，这对现有的数据库系统的性能产生很大的影响， 不符合列结构化数据进行管理的特点；此外在对x m l 数掘进行增、删操作时，这种 x m l 数掘的管理方法会因数据的改变引起结构上的变化，使数据表结构要进行改变。 这种方法没有统一的数据模型，查询代数系统，因此称不上是一种真f 的x m l 数据 库管理系统。 最后一种方法是根据x m l 文档的特点，建立专门适用于x m l 文档的x m l 数据 管理系统i l “。这样的系统拥有x m l 查询语言、数据存储和各种操作都是专门针对 x m l 数据而设计的，所以在性能上有较好的表现。目前在这方面所作的研究比较多， 但是还没有成型的产品。这种方法的主要缺点是要从头丌始，包括对x m l 数据的数 据模型的建立等基础性工作，因此也是比较难实现的。 1 2 3 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 数据是树结构，单纯的值索引远不够用，需要新 的索引类型。l o r e 在这方面作了许多研究，这里参考l o r e ，例举出主要的一些索 引技术。值索引v i n d e x ：可以根据元素名或属性名和值上的谓词条件找到满足条件 的元素或属性。父子索引l i n d e x ：可以根据元素名找到所有由该元素名连接的父子元 素对。路径索引p i n d e x ：可以根据路径找到所有该路径可以到达的元素。 和传统的数据库管理系统类似，x m l 数据查询优化也有几个关键问题：搜索空 间、代价估算、计划枚举等。x m l 查询由多种执行策略，通过对这些执行方法的调 整可以提高查询处理的效率。由于x m l 数据结构的不确定性，查询搜索空间往往很 大，可以利用启发式规则来缩小搜索空间，或者在可达路径中找最短的路径，从而减 少路径导航时间，如路径缩短技术【l6 1 等。 x m l 数据模型、x m l 查询代数系统和查询语言7 1 8 ，1 9 l 一直以来都是争论的焦点， 但是最具有代表性的是斯坦福大学提出的o e m 模型 2 0 , 2 1 1 。查询语言也是百花齐放， 如：l r o e l i ”】、x m l o l l 、x m l g l l 、x s l 1 舶、x q l z z z 3 j 等。 x m l 数据是一种特殊的半结构化数据，和结构化数据有一定的联系，因此对 x m l 数据完整性、依赖性的研究也成为了一种方向。x m l 数据的完整性主要体现在 对各种键约束的满足上，如绝对键、唯一键1 2 4 1 等。 随着x m l 技术的不断发展，x m l 应用的更加广泛，对x m l 相关技术的研究也 s 越束越多。l - 断仪仅列举了和x m l 数据管理系统有关的几个研究方向。 1 3 x m l 数据查询语言 x m l 数据是一种特殊的半结构化数据，它的查询语言也必然具有和半结构化数 据相似的发展和功能，基本上也经历了两个阶段的发展。目前有许多针对x m l 数据 的查询语言，本小节对其中最常用的五种做了一个简单的介绍，同时对比了它们在数 据查询各个方面的功能。由于x m l q l 查询语言功能强大、还具有易于使用的特点， 本文选取它作为本文查询语占的蓝本。 1 3 1x m l 查询要求 尽管目前已经有许多针对x m l 的查询语言5 ，m “，1 2 ，2 2 2 3j ，但仍存在许多不足之 处。主要表现在：( 1 ) 在理论上没有给出x m l 数据查询表达能力的标准及形式化描 述：( 2 ) 查询语法繁杂；( 3 ) 这些查询语言基于的模型各有差别，语言的语法各异， 语义功能也不同，没有一个实现x m l 数据查询的统一方法；( 4 ) x m l 数据查询是被 动的，仅仅能够根据用户提出的查询要求看是否合法，而不能主动从这些查询中推出 用户的查询意图。为此在文献【9 】中提出了对未来w e b 查询语言的评价因素。主要从以 下几个方面考虑： 1 x m l 查询语言的表达能力主要包括：1 ) 查询语言应具有与关系演算或s q l 相同的表达能力，可以表达传统查询语言中的操作或限定。2 ) 对一些特殊的结构( 如 超链接) ，应能够通过“导航”遍历链接路径。3 ) 对半结构的特征语言应能通过正规 路径表达式( 或递归规则) 匹配未知结构，并通过文本的模式表达式匹配内容，对数 据类型的限制是宽松的。4 ) 由于x m l 文档及查询的特殊性，查询语言的结果重构能 力也应该作为评价语言表达能力的一个方面。 2 x m l 查询语言应该有精确的语义，有利于实现查询语言的转换和优化。 3 埘l 查询语言的合成能力对建立视图是非常有用的。同时也可以用来评价语 言是否具有重构能力和语法上的引用透明性。 4 x m l 文档模式与查询的构造要求在事先不知道模式的情况下，查询语言支持 对部分模式信息的查询，构造更复杂的查询则需要依赖模式提取技术。 5 x m l 查询语言的可生成性要求能用应用程序生成所需的查询语言。 6x m l 查询语言与其它技术的集成要求w e b 查询语言能和其它技术结合。开发 出更完善的功能，或者支持用户自定义的函数或谓词等。 下一节先对目前在研究和应用领域中比较常用的五种x m l 查询语言作简要介绍， 比较它们在查询能力上的区别。 1 3 2 最二t 要的五种x m l 查询语言 w e b 查询是两个任务的合成：基于内容的查询和基于不同页面之间链接结构的查 咖。根据模型描述信息的不同粒度和查询语言的功能，大敛可以将w e b 查询语言分 为第一代w e b 查询语言和第二代w e b 查询语言i ! “。 l 第一代查询语言，其主要特点包括：图的节点是w e b 页面，边是页面之间的链 接：利用现有的搜索引擎实现基于内容的查询，并从借鉴数据库的技术出发实现基于 结构的查询。它的典型代表有w e b s q l 、w e b l o g 和早期的w 3 q l 。 2 第二代查询语言，其主要特点包括：图的节点是页面内部的数掘，其粒度较小， 边既可以是页面内部的链接也可以是页面之间的链接。一些模型还支持表达更为自然 的有序集合和记录；支持查询结果重构成复杂的结构，更多地依赖于半结构化数据的 查询“。它的典型的代表是w e b o q l ，s t r u q l 。 x m l 数据是一种特殊的半结构化数掘，所以对x m l 数据查询语言的发展在很 大程度上受到了半结构化数据查询语言的影响，有的就是对半结构化查询语言的改 进。目前对x m l 文档进行查询所用到的查询语言主要有如下五种： 1 l r o e l | l 副：斯坦福大学数据库研究者设计l o r e l 的初始目的就是查询半结 构化数据，现已进行了扩展，以适应对x m l 数据的查询。l o r e l 采用类似于 s q l o q l 的查询表示形式，支持类型强制转换和强有力的路径表达式等。 2 x m l - q l 【l 州：x m l q l 是a t & t 实验室中的数据库研究者设计的。它使用元 素模式匹配进行查询处理，通过加入明确的构造语句c o n s t r u c t 扩展了类s q l 查 询，使其能构造出具有复杂结构的结果文档。x m l q l 能够表达对多数据源的x m l 查询和转换。该语言现已成为了w 3 c 推荐的标准。 3x m l g l 】：x m l g l 是意大利p o l k e c n i c od im i l a n o 大学设计的种图形化 查询语言，它利用边标记图来图形化x m l 数据和d t d 。在x m l g l 中，所有的元 素都是可视的，适合作为友好的人机交互界面。 4x s l i l 2 1 ：x s l 由w 3 c 的x s l 工作组设计，一段x s l 程序包含一组模板规则， 每一个模板规则都由两部分组成：与数据源中菜类节点匹配的模式和一个示例模板构 成的输出树。x m l 利用x p a t h l 2 7 1 定义的语言处理选择、条件和文本的产生。 5 x o l l 2 2 日j ：x q l 是微软公司设计的针对x m l 的查询语言，它的作用是选择 和过滤x m l 文档的元素和文本。x q l 可以看成是x s l 模式语法的自然扩展，它的 设计目标是简单、紧凑，可以作为u r l 的一部分，所以降低了部分表达能力。 1 3 3 各种x m l 查询语言的比较 对上一节中介绍的几种查询语言，进行比较，其中一些主要功能的支持说明如表 1 2 ，本节的内容主要参考了1 2 甚2 9 1 。 + 一一! 坠竺型生型墨丝j i 坐! ! i l 墨里 衷12 血种查询语言的比较 l r o e l x m l q lx m l g lx s l x q c 连接 查询结果的语义 o i d 集x m l 文档x m l 文档x m l 文档x m l 文档 音| j 分路径表达式 路径的循环检测4依赖于实现 依赖于实现 存在量词 全称量词 间接支持间接支持间接支持 取殴 0o j0 简约间接支持 间接支持间接支持间接支持 仓u 建元素 分组操作 s k o l e m 函数 聚集操作 奄询嵌套 从上面的分析中可以看出，在这五种x m l 查询语言中，l o r e l 和x m l 。o l 的 表达能力最强，x m l g l 次之，而x s l 和x q l 连通常的连接操作都无法表达，所以 其表达能力最弱。在l o r e l 和x m l q l 中，前者查询表达的灵活性比后者强，而后 者在查询结果的构造上则略胜筹。 1 4 x m l d m s 的系统结构 本文所实现的x m l 数据管理系统( “l d m s ) 采用的是通用数据管理和专用数 据管理两种方法的结合。该系统建立了专门针对x m l 这种半结构化文档的数据模型 和数据查询代数，但是在对数据的存储和查询代数的底层实现上，利用关系数据库管 理系统作为其数据的存储载体。由于有了相应的数据模型和x m l 查询代数，所以要 把该系统转换到专用数据管理方法也是比较容易的。该方法能把存储和实际数据结构 分开，能够充分利用现有的数据库管理系统成熟的技术，甚至在并发控制、数据统一 性等方面也可以通过对现有的数据库加以扩充得到。和其它方法比较，由于其存储的 粒度较小，所以数据更新、结构更新等操作不会影响整个存储方法和存储结构。当然 该方法也有一些不足之处，主要是在进行精确的数据导航查找操作时，产生较多的数 据连接操作，会对系统的性能产生一定的影响。对此，本文利用一些查询优化方法和 查询执行策略对查询进行优化，提高了查询的效率。总的说来，该方法是一种比较合 理的x m l 数据管理方法。 与现有的关系数据库或者面向对象数据库不同，x m l 数据管理系统有其自身的 系统结构。关系数据库利川二维表的方式管理结构化数据，面向列象数掘库利用面向 对象的方法末管理结构化数据，本文的x m l 数据管理系统利用图的方式束管理x m l 这争1 特殊的半结构化数掘。本文介绍的x m l 数据管理系统有其自身的数据模型和代 数操作，但是在具体实现时，使用关系数据库作为数掘存储的工具。其目的是充分利 用关系数据库管理系统的一些成熟技术。 根据上文的叙述，可以建立如图1 2 所示的x m l 数据管理系统结构。 b ( m l 文档 x m l q l 查询随回结果 l上tr l x m l 数据管理系统的用户接口和应用接口 畸7 - t l 查询执行计划和查询优化模块 1 尸 = j 、岁 基于x m l 查询代数的各种元操作 i丁 之、j 7 一 j 关系数据库管理系统 图1 2 以l d m s 系统结构 从图1 2 中可以看出，x m l d m s 主要包括以下几个部分：访问界面、查询计划 构造、查询优化、数据字典管理和x m l 数据构造。本文主要介绍x m l 查询处理部 分，因此对x m l 数据的更新、增加和删除操作仅仅做一个简要的说明。 该系统的访问界面，用树的形式列出用户所要查询数据的文档结构，以便于用户 构造更加准确的查询语句。返回的文档也遵循x m l 文档显示方式( 如子元素缩进等) 。 在用户输入查询语句后，首先分析该查询语句，得到相应的语法结构，并构造查询计 划树。对查询的优化主要通过调整查询计划树、改变执行顺序、利用模式信息简化查 询计划等方法。由于x m l q l 这种查询语言允许用户按照自己的需要构造要返回的 x m l 文档，因此加入了x m l 数据构造来实现这一功能。 1 5 本文的主要研究内容 本文通过对x m l 技术的研究，针对x m l 的特点建立个新的x m l 数据模型 ( x f d m ) 和查询代数系统( x f q a s ) 。基于该模型和查询代数系统，提出一套可行 的建立x m l 数据管理系统的方案，并在此基础上建立一个x m l 数据管理系统。因 此，本文的主要研究工作包含以下几个方面： 9 1 分析吲内外列x m l 技术和x m l 数据管理的研究现状，提出一套可行的建、z x m l 数据管理系统的方案，并在此基础上实现一个具有x m l 数掘管理功能的x m l 数抓：管理系统。 2 建立一个专门针对于x m l 数据的形式化数据模型，使之充分满足x m l 数据 管理系统的数据组织要求。 3 扩充并改进x m l 查询代数，对其中的一些基本操作做出新的语义上的解释。 4 利用不同的方法对x m l 数据管理系统进行查询优化，提高x m l 数据管理系 统的查询效率。 5 对x m l q l 查询语言的一些扩展和规范化处理。 1 6 本文的结构组织 本文主要由七部分组成： 第一章主要首先介绍了x m l 数据管理系统的研究背景，讨论了目前x m l 数据 管理系统不同实现方法的优缺点和其它的相关研究。然后分析了最主要的五种x m l 查询语言。最后提出了x m l d m s 的系统结构和本文的主要研究内容。 第二章简要介绍了x m l 和x m l q l 查询语言，最后对x m l q l 查询语言作了 一定的扩展。 第三章提出了x m l 数据管理系统建立的基础和x m l 数据管理系统查询的基础： 带根连通有向图、先后序关系、形式数据模型( x f d m ) ，x m l 查询代数( x f q a s ) 。 第四章分析了x m l d m s 的数据存储、查询语言规范处理、查询实现的具体方法， 为了建立x m l d m s 的数据字典，这一章中还提出了x m l 模式x g r a m m a r 和模式的 提取算法。 第五章主要针对不同的情况，对查询采取不同的优化方法，提高查询效率。同时 还对实验结果进行了分析，说明了查询优化能够提高系统效率。 第六章是对本文工作的总结。 第二章x m l 与x m l q l 查询语言 本章简要介绍了x m l 和x m l q l 查询语言，同时对x m l q l 查询语言作了 定的扩充。 2 1x b l l 简介 2 1 1 x m l 的目标和优点 在x m l 设计之初，就已经提出了它所要达到的一些目标，主要有如下几点2 】： 1 x m l 应该可以直接应用于i n t e r n e t 。 2 l 可以同时支持大量不同的应用。 3x m l 能与s g m l 兼容。 4 处理x m l 文档的程序应该容易编写。 5x m l 中的可选项应该尽量减少，最好的状况是没有可选项。 6 x m l 文档应该清晰明了、容易理解、可读性强。 7x m l 文档应该易于设计和编写 8x m l 的设计应该正式而简洁。 9x m l 文档应该易于创建。 1 0x m l 标记的简洁性相对次要，主要着重于易懂。 正是由于在设计x m l 标准之初就提出了这些基本的目标，所以x m l 技术具有 下列特性，而正是因为它的这些特性，有人认为它带来了“i n t e m e t 的第二次革命”。 l 简单性 x m l 为程序员和文档作者提供了一个友好的环境。x m l 的严格定义和规则集使 人和计算机都能够更加容易地阅读文档。x m l 文档语法包含一个非常小的规则集， 使开发者能立刻开始工作。其中的基本结构可以被用来表示复杂的信息集合，而不需 要改变结构本身。 2 可扩展性 x m l 在两个意义上是可扩展的。首先，它允许开发者创建它们自己的文档描述 方式( d t d 、x m l s c h e m a 、r e l a x 等) ，有效地创建可用于多种应用的“可扩展的” 标记集。其次，有许多附加的标准对x m l 的能力进行扩展，它们可以向x m l 增加 样式、链接和引用能力。 3 互操作性 x m l 是平台无关的，它可以在多种平台上使用，而且可以用不同的工具进行解 州j 故拼 苷删系统的川丸jj 实观 释。j i 文档的结构是相容的，所以解释它们的语法分析器就比较容易创建。x m l 支持j j 于字符编码的许多标准，允y l ：它在全世界不同的计算机坏境中使用。 4 ) _ r 放性 x m l 标准在w e b 上是完全丌放的，可以免费下载。x m l 文档本身也是丌放的， 任何人都可以对一个x m l 文档进行语法分析和检查其有效性。x m l 也可以让不同 的用户创建其特有的格式，这也充分漉明了它的丌放性。 x m l 之所以受到如此重视，并且大有替代h t m l 成为新的数据显示标准的趋势， 主要因为它和h t m l 相比有如下特点口引：( 1 ) 使用有意义的标记。( 2 ) 数据的语义 与显示方式分丌。( 3 ) 可自定义标记。( 4 ) 严格的语法控制，更加有利于用计算机自 动处理。其它如引用，x p o i n t 等也都体现了x m l 的强大的功能。 2 1 2 x m l 的结构 x m l 把标记的定义、内容和显示分开。因此，x m l 主要包括三要素：文档定义 ( d t d 、x m l s c h e m a 、r e l a x 等) 、定义x m l 显示的样式单( x s l ) 和可扩展链 接语言( x l i n k ) 。文档定义说明了x m l 文档的逻辑结构、元素、元素属性以及它们 问的关系。x l i n k 进步扩展了h t m l 上的简单链接。图2 1 是x m l 的技术及功能 结构图，它不但包含了x m l 的三要素，还包括许多基于x m l 扩展的技术。 图2 1x m l 的技术及功能结构图 在w 3 c 的规定中，x m l 必须满足一定的约束条件，它要求x m l 文档是结构良 好的。其有效性则是可选的，也就是说一个x m l 文档可以没有相应的文档模式定义。 结构良好的是指：如果一个x m l 文档包含一个或多个元素，那么各个元素都有 正确的嵌套，并且j 下确地使用属性和实体参考，符合x m l 的基本语法规范。 有效的x m l 文档是指：x m l 文档与一个文档定义相关联，并且该x m l 文档符 合对应文档定义的各种规则，那么就称这个x m l 文档是有效的。 2 1 3x m l 文档简介 本节介绍x m l 标准p ，5 ，6 j 的核心部分，对应用的扩充部分则不详述。 j 堕坚塑坐型盟型堂墨 1 厄索 元鬃足x m l 文档的麟本成分，由对应的起始标记和结束标记分隔，如 t h e s 8 m p e o f t a g t i t l e 。每个元素有一个用名字标0 的标记，称为通f j 标识符，如t i t l e 。 兀豢内部可以有其它元素、文本以及两者的混合。 如f 面一个x m l 文档片断： 例2 1 19 9 9 m a y 2 0 尖括号中的标记如d a t e 、y e a r 等称为标记。 元素包含了子元素， 其它如 1 9 9 9 则包含了文本信息。 2 属性 x m l 允许每一个元素后跟属性列表，用来表示元素的属性。如例2 2 ： 例2 2 p e r s o ni d = ”s h a h n a m e f i r s t n a m e = ”k s h i t i j ”l a s t n a m e = ，s h a h ”b n a m e 元素有两个属性，分别用来表示n a m e 元素的f i r s t n 锄e 和l a s t n 锄e 属性。 同元素标记一样，属性名也是由用户自定义的，但是它在一个元素中最多出现一次。 3 x m l 的引用 和数据库中的主码一样，x m l 的每个元素都可以定义i d 属性，用来唯一标识 该元素，其它元素可以通过这个i d 来引用该元素，而不用把整个元素重新拷贝一遍。 如例2 3 ： 例2 3 n a m e f i r s m a m e = ”j u d i t h ”l a s t n a m e = k l a v a n s ，b l d a v a n s c o l u m b i a e d u 这个例子中e d i t o r 元素引用了两个元素，它们的i d 分别是：s h e t h 和b o s s v 。这两 个元素的具体定义可以参考属性中出现的例子2 2 。 例2 4 是一个x m l 文档的片断( 7 】，该x m l 文档片断包含了x m l 的一些基本元 素、属性、引用等。 例2 4 x l l 教据蕾理系统f i ：j 训，o j 吱j 见 i n t lc o n f e r e n c eo n c o n c e p t u a lm o d e l i n g ( e r ) 19 9 9 m a y 2 0 n a m ef n = ”j u d i t h ”1 n = ”k l a v a n s ” k l a v a n s c o l u m b i a e d u i n d e x i n gm o d e l f o rs t r u c t u r e d 2 2 x m l - q l 查询语言 x m l q l 是专门针对x m l 数据设计的，它包含了基本数据库查询语言所应具备 的功能：数据选择、数据集成、数据传送和数据转换等。同时x m l 。e l 还参考了s q l 、 o q l 和其它的x m l 数据查询语言，所以它有一定的独到之处： 1 ) 用类似于s q l o q l 中的s e l e c w h e r e 类型的基本查询结构，容易被人 们理解和接受。由于引入了c o n s t r u c t 操作，使用户无须关心数据来源是真实数 据源还是奄询结果。可以同时对多个数据源进行查询，产生一致的数据视图。 2 ) x m l q l 提供无序和有序两种数据处理方法，给用户更大的选择权。 3 ) 支持正规路径表达式和元素名变量，有利于查询的重用。 本文选用x m l e l 作为查询语言的蓝本，同时也对其功能作了一定修改。 2 2 1x m l 语言成分 本节参考了x m l q l 的标准f 3 0 1 ，使用的数据源是b i bx m l ，其对应的文档结构定 义用d t d 表示如下： 例2 5 坐! ! 堕! 塾盔叁：! ：丝l 兰竺堕兰 使用模式( p a t t e r n ) 匹配数据 x m l q l 使用元素模式匹配x m l 文档中的数据，如要获得出版社 a d d i s o n - w e s l e y 所出版书籍的作者名，则可以用x m l q l 查询语言表达如下( 其中 元素结束标记可以简写为 ，它和最近的一个丌始元素标记相匹配) 。 例2 6 w h e r e a d d i s o n w e s l e y s t s a i n ”w w w a b c b i b x m l c o n s t r u c t $ a 这个查询得到b o o k 元素的作者名，这本书的出版社为a d d i s o n w e s l e y ，并且要 求这本书的基本信息至少含有一个t i t l e 元素和个a u t h o f 元素。 构造l 数据 上例中查询返回的结果是( ， ) 对，为了使查询结果更加直 观和容易理解，可以在c o n s t r u c t 子句中加入适当的元素标记，按照定的格式 构造结果数据，如例2 7 ： 例2 7 w h e r e a d d i s o n -