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

中文摘要 中文摘要 w e b 技术的飞速发展使得全球信息的传递和共享日益增多，而x m l 技术的出现则丁f 是为了有效应对上述问题。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 s q l ， 该语言支持x m l 文档中的路径表达式查询、支持x m l 文档的数据更新 操作以及查询结果的语义描述，同时该语言具有良好的易用性。在x s q l 的基础之上，本文提出了基于路径缩短规则的路径表达式优化算法，有 效地减少了路径表达式查询的长度；同时考虑到数据索引的影响，有效 地降低了路径表达式的查询执行时间。本文提出了基于查询依赖树的查 询处理方法并给出了查询处理各部分的算法，利用该x m l 数据上的查 询处理方法，结合路径表达式的翻译规则，可以将用户下发的针对x m l 数据的x s q l 查询转化为对应的s q l 执行序列并执行得到x s q l 的查 询结果。最后，利用上述方法建立了x m l 数据库系统，并给出x m l 数 据库系统的性能评测。 关键词：x m lx m l 数据库路径表达式优化查询处理 英文摘要 a b s t r a c t w i t ht h er a p i da d v a n c e m e n to ft h ew e bt e c h n o l o g y , t h ed e l i v e r i n ga n d s h a r i n go ft h e i n f o r m a t i o ni n c r e a s e s i n c r e a s i n g l y a l lo v e rt h ew o r l dt h e e m e r g e n c e o fx m lt e c h n i q u e e x a c t l y d e a l sw i t ht h ea b o v e p r o b l e m e f f e c t i v e l y x m lh a sb e c o m eas t a n d a r df o rd a t ae x p r e s s i n ga n dat o o lf o r i n f o r m a t i o n e x c h a n g i n gg r a d u a l l y ，i t w i l l d e v e l o p an e wr e a l mf o rt h e a p p l i c a t i o no fd a t a b a s e h o w e v e r ，t h es e m i - s t r u c t u r ec h a r a c t e r i s t i co fx m l d a t a ，t 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 lp a t he x p r e s s i o na n d t 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 er e l a t i o n a l d a t a b a s em a g n a g e m e n tf u c u t i o nd e a l i n gw i t t lx m ld a t al i m i t e d t h i sp a p e rf o c u s e so nt h eq u e r yl a n g u a g eo fx m l d a t a ，t h et e c h n o l o g i e s o fp a t he x p r e s s i o no p t i m i z i n ga n dt h eq u e r yp r o c e s s i n go fx m ld a t a t h i s p a p e rp r e s e n t s an e w q u e r yl a n g u a g e ，x s q l ，f o r x m ld a t a b a s e ，w h i c h s u p p o r t st h eq u e r yo fp a t he x p r e s s i o nf o rx m ld a t a ，t h eo p e r t a t i o no fx m l d a t a u p d a t i n g ，t h e s e m a n t i cd e s c r i b i n go fq u e r yr e s u l ta n di s e a s yt o u s e b a s e do nx - s q l q u e r yl a n g u a g e w ep r e s e n tap a t he x p r e s s i o no p t i m i z a t i o n a l g o r i t h m ，w h i c h r e d u c e st h e l e n g t h o fp a t h e x p r e s s i o ne f f i c i e n t l y a n d i m p r o v e st h eq u e r ye f f i c e n c y t h e nw ep r e s e n tt h eq u e r yp r o c e s sa l g o r i t h m b a s e do nq u e r yd e p e n d e n tt r e e ，w h i c hm a k e su s eo ft h et r a n s l a t i o nr u l e s ， t r a n s l a t e st h eu s e r s x - s q lq u e r yi n t oc o r r e s p o n d i n ge x e c u t i o ns e q u e n c eo f s t r u c t u r e dq u e r yl a n g u a g ea n do b t a i nt h ef i n a lq u e r y r e s u l t m a k i n gu s eo f t h e a b o v e m e t h o d s ，w ee s t a b l i s h ax m ld a t a b a s e m a n a g e m e n ts y s t e m a n d e v a l u a t et h ep e r f o r m a n c eo ft h ed a 培b a s e k e y w o r d s ：x m l x m ld a t a b a s ep a t h e x p r e s s i o no p t i m i z a t i o n q u e r yp r o c e s s i n g 第1 章引言 1 1 研究背景 第1 章引言 w e b 技术的飞速发展使其成为全球信息传递与共享的重要工具和最 具潜力的资源，它作为一种新的环境资源，为新技术的产生开辟了新的 领域，同时也为数据管理技术的研究提出了新的问题。w e b 技术与生产 生活的紧密联系，使得信息量与日俱增，信息形式多种多样。如何从海 量w e b 数据中获取有用信息，已经成为用户最关注的问题。因此有效地 组织和管理分布于世界各地海量数据，提高信息获得速度逐渐成为数据 管理领域的重要研究问题。 信息集成已被视为w e b 信息管理的最主要的发展方向。信息集成指 将异构的、不相容的、不同模式的分布式信息源的数据进行有效的集成。 用户可通过统一的访问模式透明地对分布式信息源进行访问以完成信息 搜索的目的，而无需了解具体的分布式信息源的信息结构和访问接口。 1 9 9 4 年s t a n f o r d 大学提出集成和共享i n t e r n e t w e b 上分布式异构 信息源的m e d i a t o r w r a p p e r 架构，以此为开端，研究者在分布式异构 信息集成技术方面开展了大量研究工作，取得了许多研究成果。目前建 立分布式异构信息集成系统主要有两种方法： 数据仓库方法”“1 。该方法将各信息源中的数据利用抽取器全部抽取 出来，利用包装器、合成器将抽取的数据合成为一个全局模式，集中存 储到数据仓库中，系统针对数据仓库进行数据维护和处理。该方法优点 是对异构数据源可以采用统一的管理，管理方式简单方便；缺点是数据 仓库不允许更新，只能定期重建，并且存在例如数据类型不支持、数据 结构无法映射、转换接口工作量大、系统网络传输和处理瓶颈问题。 黑龙江大学硕士学位论文 虚拟方法又称m e d i a t i o n 方法”“1 。该方法构建出虚拟数据库系统， 系统不存储任何数据，采用支持虚拟视图方式进行数据源维护。当用户 发出查询请求时，m e d i a t o r 将查询请求翻译成一个或多个对数据源的查 询，发送给数据源的包装器w r a p p e r ，且将各个数据源包装器的查询结 果进行综合处理，返回给用户。其中包装器完成特定数据源的本地查询 转换处理。这种方法的优点在于简化了异构数据之问的统一存储，实现 各种数据源的高度自治，便于扩展集成系统，同时也可以利用异构系统 中现有的先进方法进行数据处理，优化了系统的性能；其存在的主要问 题在于中间模式的统一标准，即中间模式的查询和数据发布标准。 上述方法各具优势，数据仓库方法对于命中的查询效率要比虚拟方 法更高，而虚拟方法更适应于数据源数目多、各局部数据源的自治性很 高且局部数据经常变化的w e b 环境。目前已有的分布式异构信息服务原型 系统如下：d a t a f o u n d r y 系统1 7 j 是一种基于o n t 0 1 0 9 y 的动态建立的数据仓 库模式的信息集成系统，其利用o n t o l o g y 减少数据仓库的维护操作，该系 统中o n t o l o g y 也被用于信息源的m e d i a t i o n 的自动生成以及信息源到数 据仓库的转化数据的方法。t s i m m i s 系统“1 是i b m 阿尔马登研究中心与 斯坦福大学共同研究开发的信息集成系统。系统利用约束管理机制”和 信息模式分类提取机制，进行结构化和非结构化数据的异构信息源的快 速集成，利用翻译器。“将结构化或非结构化数据对象转换为统一的自描 述对象模型：系统的m e d i a t i o n 基于该对象模型进行多个数据源的信息 提取，并将信息转化为统一的对象模式，同时根据数据源的调用统计作 为查询评估的依据，进行查询优化处理。7 ”1 ：系统采用维护模块包装器“” 的方式为包装器提供操作函数库，包装器从系统应用接口接收查询，并 针对具体数据源根据操作函数进行查询处理转化，将查询结果进行数据 模型转化，返回给应用接口；系统为w e b 数据源提供提取规则及映射接口， 第1 章引言 利用w 4 f 。作为w r a p p e r 生成工具。m i x 系统”1 是基于x m l 的数据交换集成 系统，其模式信息采用x m l d t d 进行描述。g a r l i c 系统。“是集成数据库系 统、文本、视图、影像等数据系统的多媒体信息系统，m e d i a t o r 向用户 提供统一的数据视图应用接口。3 ，包装器“”采用面向对象的统一数据模 型，并提供统一的查询处理接口。当用户提出查询请求时，利用对象查 询策略将全局查询语言转化为相应的局部查询策略，且创建各个局部数 掘服务器的可执行查询计划并发送给每个数据服务器，并将查询结果返 回给应用系统，该系统支持多媒体信息处理“，优化采用针对各种数据 服务器集合的优化策略“。 各种异构数据源之间的数据类型、数据取值差异以及数据丢失等问 题对异构信息集成系统提出挑战。基于x m l 的信息集成系统”2 1 4 1 的出现 为处理异构数据源间的数据丢失和模式异构的差异提供了可行的方法。 在基于x m l 的信息集成系统中，如何有效地组织、管理x m l 数据，并且 通过查询获取x m l 数据十分重要，因此信息集成系统中的x m l 数据的组 织和管理方面的研究具有重要的理论价值和实际意义。 1 2 x m l 数据库系统的研究现状 x m l 技术允许工业界制定平台无关协议来交换数据，越来越多的人 采用x m l 作为i n t e r n e t 上数据的表示标准和交换工具，i n t e r n e t 上的 x m l 数据飞速增长，x m l 的数据源也是多种多样，如纯文本文件和各种 数据库数据等。有效的解决管理维护x m l 数据、选择适当的查询语言对 x m l 数据进行查询、以及x m l 数据之上的查询优化、查询处理以及x m l 数据的索引等方面的问题已经成为近几年来的研究焦点，研究人员针对 x m l 存储管理。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 。的形式发布到w e b 上。目前x m l 数据采用数据库技术进行维护主要有以下三种方法：( 1 ) 采用关系数据库 对x m l 数据进行存储维护“1 ；( 2 ) 采用面向对象数据库对x m l 进行存储 维护【”；( 3 ) 采用n a t i v e x m l 数据库，即以x m l 格式存储和进行查询的 数据库6 i ”3 。 文 4 1 采用分解x m l 文档的方式利用关系数据库进行x m l 数据的查 询。该系统的特点是：模式的分解与d t d 说明无关，而是根据文件的结 构进行分解。文 4 2 提出了种有效的支持x m l 查洵的关系数据库存储 方法，利用关系数据库完成x m l 查询到关系查询的转换后得到s o l 的执 行，最后返回x m l 查询的结果。o r a c l e 、i b m 和s y b a s e 等数据库系统公 司都将支持x m l 数据作为其数据库的一个新功能。i b m 提供了x m l e x t e n d e rf o rd b 2 ，使得用户可在d b 2 中存储x m l 文档，并提供一些支 持x m l 的新功能协助用户处理；m i c r o s o f t 的s q ls e r v e r6 5 和7 0 也 进行了x m l 扩充；o r a c l e 也拥有功能强大的x m l 索引引擎。 x m l 数据自身具有的对象特点，引发许多研究人员采用面向对象的 数据库方法研究x m l 数据管理。x m l 文档本身是一种由若干结点构成的 结构，而对象数据库允许用户自定义数据类型和各种操作方法，这种特 点使得数据适合采用面向对象格式来存储，同时可以利用面向对象语言 调用x m l 接口访问x m l 结点。当今许多大型面向对象数据库厂商如 第1 罩引言 o b j e c t s t o r e ”等都提供了处理x m l 的工具。 随着x m l 数据的大量出现，x m l 数据库市场已经初具规模。目前， n a t i v e x m l 数据库已经出现，所谓n a t i v e x l i l 数据库，就是专门为x m l 文档设计存储保存x m l 信息的数据库。n a t i v e - - x m l 数据库同样需要索 引信息，索引信息与x m l 文档一起按照特定的存储方式存储到资源库 中，以支持快速检索x m l 内容，得到满足查询条件的x m l 文档或x m l 文 档的某一部分。第一个商用n a t i v e x m l 数据库t a m i n o 。1 系统诞生于美 国加州的s o f t w a r ea g 公司，该系统采用数据分析器对x m l 数据进行分 析，获取数据分析树，通过处理该树进行数值存储、索引存储和数据元 存储，并且依据分析树采用一些运算进行查询优化。它彳i 仅可以存储和 访问x m l ，还具备多项功能，包括o p e nd a t a b a s ec o n n e c t i v i t y 、符合 u n i c o d e 要求、h ，l 、t p 通信及处理非x m l 数据的能力，而且t a m i n o 拥有直 接x m l 检索和特殊检索的能力，其查询语言强大而简短，可进入任意深 度，使s q l 相形见绌。e x i s t ”1 也是一个n a t v i e - - x m l 数据库系统，该系 统具有存储、索引、查询处理功能，索引模式主要采用快速i d 和结构结 点关系建立，在索引模式的基础上实现路径的连接算法和关键字的查询。 其他的n a t i v e x m l 数据库包括美国d b x m lg r o u pl l c 公司d b x m l 、e x c e l o n 公司e x c e l o n 和荷兰t h ec o n n e c t i o nf a c t o r y 公司的x h i v e d b ，l o t u s 公司的d o m ir l o 数据库也可以处理x m l ，而且其x m lt o o l k i t 工具与 n a t i v e x m l 数据库一样，允许用户创建和处理x m l 的内容。 目前x m l 数据库系统的研究工作结合了信息集成系统的研究。t s i m m i s 最先提出对象交换模型( o e m ) 并用其表示和交换从数据源中提取出来 的信息。在半结构化数据的查询处理的研究工作中，美国s t a n f o r d 大学 的l o r e 系统【6 0 l 比较成熟。在l o r e 系统中，s t a n f o r d 以t s i m m i s 系统中 提出的对象交换模型( o e m ) 为基础，研究用于处理半结构化数据的数据 黑龙江大学硕士学位论文 库管理系统，后来l o r e 扩展了对x m l 数据的处理的能力。它重写设计了 数据库管理系统的各个部分，定义了半结构化数据上的查询语言l o r e l 和 代数操作，设计了半结构化数据的存储方法，提出了在半结构化数据上 建立索引的方法以及基于代价的查询优化方法。 文 6 0 】是对半结构化数掘库管理系统l o r e 的概述，简要的介绍了 l o r e 的数据模型、查询语言、查询处理、查询优化的方法以及l o r e 的索 引。文【6 l 】介绍了l o r e 的基于代价的查询优化的实现，定义了逻辑查询 计划和物理查询计划，数据库的统计量阻及代价模型，用启发式的方法 减小搜索空间大小的查询计划选择方法。文 6 2 】介绍了l o r e 系统的四种 类型的索引以及四种索引在查询处理中的使用方法。文【6 3 介绍了 d a t a g u i d e s 的理论基础以及创建算法，通过在l o r e 数据库系统中使用 d a t a g u i d e s 做为数据库系统的动态模式，有利于浏览数据库的结构、表 示查询、存储统计信息以及查询优化。文 6 4 介绍了使l o r e 从处理半结 构化数据到处理x m l 数据的转化方法，提出了l o r e 的适合x m l 数据 的数据模型以及查询语言l o r e l 针对于x m l 数据的改变的方法。文【6 5 】 提出了一种基于模式数字编码对x m l 数据建立索引并且存储x m l 数据 的方法，同时提出了e e - j o i n 、e a - j o i n 、k c - j o i n 三种连接操作的算法。 文 6 6 1 利用d y n a m i ci n t e r v a l 的方法对x m l 文档进行编码并且将编码结 果存成关系，然后将x q u e r y 上的查询转化为等价的s q l 查询。文 6 7 1 利用e d g e b a s e d 的方法对x m l 文档进行编码，将全局模式下的x q u e r y 查询转化为s q l 查询。文 6 8 - 7 1 利用关系数据库对x m l 数据进行存 储发布。文 7 2 1 详细介绍了w e b 数据的数据模型、查询语言以及查询处 理等方面的处理方法和主要问题。针对于x m l 和半结构化数据，已经 出现了一些查询语言。如l o r e l 7 3 1 、x m l q l 7 4 1 、x m l g l 7 5 1 、q u i l t 7 6 1 、 x p a t h t 7 7 1 和x q u e r y 7 引。其中，l o r e l 是l o r e 原型系统中所使用的查询语 第1 章引言 言。x q u e r y 是w 3 c 提出的关于x m l 查询语言的第一个工作草案。它 是为了适应各种各样从x m l 文档到x m l 数据库上的应用而设计的。这 些查询语言的共性是使用路径表达式提取信息，因此路径表达式的优化 方法是一个重要的问题。文 7 9 1 币1 j 用数据图的局部信息来处理路径表达式 的查询评估。文【8 0 提出了两种查询优化的方法，将指定的路径表达式重 写成另一个查询来减少搜索空问的范围。 1 3 本文主要工作 本文主要研究x b l l 数据的查询优化与查询处理技术。x m l 作为新的 信息交换的标准和数据的表示方法已经广泛的被业界接受。但x b l l 数据 的查询语言标准众多，很难被熟悉s q l 的数据库开发人员掌握；因此， 鉴于目前的众多x m i 数据的查询语言的特点，本文提出种类似标准s q l 的查询语言x - - s q l ，该查询语言借鉴了众多x v l l 数据查询语占的特点以及 关系数据库查询语言s q l 的通用性，为用户提供了简单、易记的查询x m l 数据的查询接口，同时支持众多x m l 数据查询语言所不支持的x m l 数据 的更新操作，扩充了原有x m l 查询语言的更新功能，兼顾了s q l 的易用 性，为用户提供了极大的方便。 同传统的关系数据库一样，x m l 数据的查询优化是x m l 数据管理的 核心问题，然而由于关系模型和x m l 数据本身的模型之间的差异，导致 了关系数据库查询优化问题和x m l 数据的查询优化问题的不同解决方 法。由于在x m l 数据的查询中，涉及到的都是路径表达式查询，而路径 表达式查询和关系数据库中的s q l 查询截然不同。如何有效减少路径表 达式的长度是x m l 数据查询优化关注的核心问题。本文提出了基于x m l 数据模式信息的路径表达式优化方法，有效的缩短了路径表达式的查询 时间，提高了查询的效率。 黑龙江大学硕士学位论文 在x m l 数据的查询处理中，本文提出了基于查询依赖树的查询处理 方法，该方法根据x - s q lx m l 数据查询语言的语法分析结果，即x - s q l 的语法分析树，建立支持查询处理功能的查询依赖树，并通过结果变量 的依赖树绑定、条件合取范式转化、条件合取范式下推、单条件下推、 路径表达式优化、优化后路径表达式翻译等阶段的操作，将查询依赖树 的信息转化为最终查询计划，向底层数据库下发查询计划来完成对x m l 数据的查询处理。 综合文中提出的各种方法以及算法，本文实现了一个x m l 数据查询 系统，该系统由x m l 文档加载器、查询处理器、查询结果构造器三个部 分构成，其中查询处理器是该系统的核心，它由语法语义分析器、查询 优化器、查询变换器和查询执行器构成。该系统支持x - s q l 语言的针对 于x m l 数据的查询。 1 4 各章内容安排 本文共分六个部分。 第一章引言。分别介绍了本文的研究背景、x m l 数据库系统的研究 现状、本文的主要工作以及各章节内容安排。 第二章预备知识。主要介绍了可扩展标记语言x m l 的基本知识、本 文建立的x m l 数据库的系统结构以及x m l 数据库的底层存储，包括x m l 数掘的关系存储和x m l 数据的元数据存储。 第三章x m l 数据库查询语言x - s q l 。主要介绍了现有的数据库查询 语言以及本文综合现有x m l 数据查询语言所提出的功能完善的查询语言 x s q l 。 第四章x m l 数据库的查询优化。介绍了x m l 数据的模式信息提取以 及基于模式信息的路径表达式优化方法。 第1 章引言 第五章基于依赖树的查询处理策略。主要介绍了x - s q l 语法分析树 的结构、基于依赖树的查询处理方法、路径表达式的关系转换方法以及 查询处理事务生成的过程。 第六章x m l 数据库性能分析。主要包括索引对x m l 数据库的影响以 及x m l 数据库的对比试验结果。 最后给出了本文的结论。 黑龙江大学硕士学位论文 2 1x m l 简介 第2 章预备知识 近年来，i n t e r n e t 已经成为人们获取信息的主要工具，它提供世界 范围内的网络互联和通信，而w e b 则成为环球信息资源库。由于传统的 h t m l ( 超文本标记语言) 只适合数据的浏览，而不适合数据问的交换， 因此需要一种新的语言能够适应数据的组织和交换，x m l 的出现为上述 问题的提供了良好的解决方案。 2 1 1 可扩展标记语言概述 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 的缩写，意为可扩展的标记语 言。x m l 是由万维网协会( w 3 c ) 设计的用来自动描述数据信息的一种新的 标准语言。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 文件头说明部分、文档类型定义部分、x m l 文件中的元素、 x m l 文件中的属性以及元素和属性的取值。元素和属性是x m l 数据文件 第2 章预备知识 的核心部分。x m i 利用文档类型定义对元素进行描述，每个元素数据项 都具有自已的类型描述和结构描述。x m l 允许定义新标记，并且其结构 允许随意嵌套。每个元素可具有一个或多个属性，也可不具备任何属性， 用户可为元素自定义属性，但每个属性仅能在元素中出现一次。图 2 1 1 _ l 为在i e 浏览器显示的x m l 数据文档。 图2 1 1 1x m l 数据文档 x m l 并不是在真空中操作的。如果将x m l 用于多种数据格式显示， 就需要与多种的技术相互作用。这些技术包括h t m l 、c s s ( c a s c a d i n g s t y l es h e e t ，层叠样式表) 和x s l ( e x t e n s i b l es t y l el a n g u a g e s ，可 扩展的样式语言) 、u r l 和u r i 、x l l ( e x t e n s i b l el i n k i n gl a n g u a g e ， 可扩展的链接语言) 和u n i c o d e 字符集。利用c s s 规则定义x m l 文档显 示的样式标准，利用x s l 定义格式化的词汇表，便于用户文档问的数据 转换，利用x m ls c h e m a 规定一些公共特征、方法等等。 黑龙江大学硕士学位论文 2 1 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 文档是自描述的。 不仅人能读懂x m l 文档，计算机也能处理。x m l 表示数据的方式真正 做到了独立于应用系统，并且数据能够重用。x m l 文档被看作是文档的 数据库化和数据的文档化。 可扩展性 x m l 允许使用者创建和使用他们自己的标记而不是h t m l 的有限 词汇表。这一点至关重要，企业可以用x m l 为电子商务和供应链集成 等应用定义自己的标记语言，甚至特定行业一起来定义该领域的特殊标 记语言，作为该领域信息共享与数据交换的基础。 灵活性 h t m l 很难进一步发展，就是因为它是格式、超文本和图形用户界 面语义的混合，要同时发展这些混合在一起的功能是很困难的。而x m l 提供了一种结构化的数据表示方式，使得用户界面分离于结构化数据。 所以，w e b 用户所追求的许多先进功能在x m l 环境下更容易实现。 第2 章预备知识 2 2 x m l 数据库系统体系结构 本系统采用客户服务器结构。客户端使用w i n d o w s 2 0 0 0 操作系统， 主要为用户提供一个友好、直观、便捷并具有人性化、智能化的人机交 互界面，便于用户输入以x s q l 表示的查询指令并获得查询结果，客户 端同时具有支持用户加载x m l 文档的功能。 服务器端主要包含四个部分：x m l 文档加载器、查询处理器、查询 结果构造器以及底层关系数据库。 x m l 数据库系统体系结构如图2 2 1 所示。 x m l 文档加载器：x m l 文档加载器主要任务是加载x m l 文档。 主要由四个功能模块组成：x m l 文档分析器、d t d 提取器、x m l 到关 系数据的转换模块、关系数据的加载模块。 查询处理器：查询处理器主要任务是处理用户输入的x s q l 查 询，并将查询的结果返回给用户。其主要包含两个模块：词法一语法分析 及语义检查模块和查询处理模块。其中词法语法分析及语义检查模块主 要负责) ( _ s q l 查询的词法分析、语法分析以及语义检查工作，最终的目 标是产生语法分析树，为下一阶段的查询优化和查询处理奠定基础。查 询处理模块主要负责对用户输入的查询、更新语句进行处理的任务。其 工作依赖于第一阶段产生的语法分析树。查询处理模块由两部分组成： 查询语句处理模块和更新语句处理模块。查询语句处理模块又可分为查 询优化器、查询变换器、查询执行器三部分。更新语句处理模块通过调 用查询处理模块找到需进行更新操作的纪录，进行相应的更新操作。因 此查询处理模块实质上是x m l 数据库系统的核心模块。 查询结果构造器：查询结果构造器主要负责对查询产生结果的重 新构造，将其重构为x m l 格式的文档。 黑龙江大学硕士学位论文 图2 _ 2 1x m l 数据厍系统结构 底层关系数据库：底层关系数据库的主要任务是储存数据。x m l 数据库系统中的底层关系数据库采用的是p o s t g r e s q l 7 3 - 3 。p o s t g r e s q l 的对象一关系型数据库管理系统( 有一段时间被称为p o s t g r e s 9 5 ) 是从伯 克利写的p o s t g r e s 软件包发展而来的。经过十几年的发展，p o s t g r e s q l 是世界上可以获得的最先进的开放源码的数据库系统，它提供了多版本 第2 章预备知识 并行控制，支持几乎所有s q l 构件，包括予查询，事务和用户定义类 型和函数，并且可以获得非常广范的开发语言支持包括c ，c + + ，j a v a ， p e r l ，t e l ，和p y t h o n 。p o s t g r e s q l 主要的改进有： 表级锁被多版本并行控制取代，这样就允许读操作在写操作活跃 时继续读取一致的数据，并且令数据库等待执行查询时用 p g _ d u m p 进行热备份成为可能。 实现了许多重要的后端特性，包括子查询，缺省值，约束和触发 器等。 增加了附加的s q l 9 2 一兼容的语言特性，包括主键， 引号标识 符，文本字串类型转换，类型转换，以及二进制和卜六进制整 数的输入。 改进了内建的数据类型，包括新的大范围日期时间类型和附加 几何数据类型的支持。 总体上，后端代码的速度提高了大约2 0 4 0 ，而且自v 6 0 起 后端的启动时间缩短了8 0 正是由于p o s t g r e s q i 的上述特点以及它的开放源码的特性，使得该 数据库可以做为x m l 数据库系统中用于存储数据的底层数据库。 2 3x m l 数据的存储 目前，有关x m l 的存储技术主要有以下几种：文本存储、建立专门 的x m l 数据存储系统、数据库存储。 文本存储方式是一种最简单、直接地存储x m l 数据的方式。以文本 形式存储整个文档( 比如在关系数据库中用b l o b 类型，在操作系统的文 件系统中用文件类型) 与数据被理解的方式是一致的，自然地反映t x m l 黑龙江大学硕士学位论文 文档中对象之间的嵌套关系，x m l 数据以自然合理的方式聚集在一起， 数据所占用的空间较小。主要缺点是存储粒度大，当数据量很大时不利 于实现网络间通信和数据共享；并目由于修改操作涉及到对文件的修 改，所以当前很少能够支持修改操作；要求采用特殊的查询处理器来完 成在x m l 数据文档中的查询；每次存取或浏览时都需要进行分析，且分 析后的文件比原x m l 文档大得多，在处理的过程中处理文件需要驻留内 存；建立索引很困难。 专有的x m l 存储系统，如斯坦福大学开发的l o r e 系统，它利用自己 的对象管理器管理物理磁盘上的半结构化数据或x m l 数据对象。还有美 国s o f t w a r e a g 公司推出的t o m i n o 服务器，它是一个纯x m l 数据库服务器， 它把一篇x m l 文档作为存储的基本单位，使用d t d 或x m ls c h e m a s 作为其 “数据定义语言”。 利用数据库存储主要采用两种方式：采用面向对象数据库系统存 储和采用关系数据库系统存储。 面向对象数据库存储方式利用d t d 对应的文档类型定义给出信息构 造类的层次结构，正则表达式的符号可以由基于对象数据模型的类型来 表达，也可以通过创建新的类实现。该方式的数据模型更接近半结构化 数据模型，并能很好地处理嵌套的集合，因此，其数据存储和查询处理 可以用来提高x m l 数据处理的效率。其主要问题在于数据加载时对未知 的数据类型需要建立新类的埘应，这样影响了加载效率：当d t d 改变时， 数据模式的变动代价也很昂贵；x m l 文档中的元素通常较小，将每一个 元素都做一个对象来存储会浪费系统的存储空问。 关系数据库存储方式可以利用现有的大型商品化的关系数据库系统 来存储x m l 数据，并且可以利用现有数据库的存储管理、并发控制、恢 复、版本机制等成熟技术有效地管理数据，但应用前提是需要将x m l 第2 章预备知识 数据转换成关系数据。通常利用关系数据库对x v i l 文档进行查询处理 的过程如下： 映射d t d 为关系模式 将满足d t d 模式的文档转化为关系元组，利用关系数据库加载 将原x m l 上的查询转换为关系数据上的s q l 查询 将s q l 查询结果转化为x m l 数据 该方法的主要缺点存储前后的转换工作很繁杂；为了清除半结构化 数据与二维数据之间的差别，其转换工作使原有的半结构化数据的部分 信息丢失；当将x m l 元素以及属性映射为关系时，极简单的元素或属性 可能映射为多个表，这直接导致简单的路径查询可能需要多个表的j o i n 操作才能实现，严重影响查询的效率，因此该方法需要选择适当的方法 实现查询的优化技术，减少多表之问的连接次数。另外出于x m l 数据缺 乏模式和数据类型，也使得关系数据库的一些优化存储策略无法应用。 尽管关系数据库系统在处理x m l 数据时具有如上所述缺点，但世界各国 数据库科学家二十多年关于关系数据库的研究使得关系数据库已经具有 一套成型的理论基础和实践平台，利用这些经验，选择好的存储方式、 优化方法、利用关系数据库的特性搭建基于关系的x m l 数据库仍旧是一 种好方法。 目前，x m l 文档主要有两种逻辑结构：有向连通图结构和树结构。 斯坦福大学在开发l o r e 时采用的o e m ( o b j e c te x c h a n g em o d e l ) 模型实质就是有向连通图。图2 3 1 所示的x m l 文档的0 e m 对象实例如 图2 3 1 所示。在浚模型中，结点表示对象，有向边上加有标识，实体 由对象表示，每个对象有唯一的对象标识，没有出边的结点表示原子对 象，原子对象具有具体值，这些值是一些原子类型，如i n t e g e r ，r e a l ， s t r i n g ，g i f 等。其他结点是复杂结点，它们的值是对象引用集，记为 黑龙江大学硕士学位论文 二元组( 1 a b l e ，o i d ) 的集合。l a h l e 是从原子类型s t r i n g 得来，o i d 则是对象标识，用o i d 来区分不同对象实例，该值在数据库中是全局唯 一的。通过o l d 可以快速查找到所需的对象并且在对象之间导航。该数 据模型有一个根，它可以到达图中的任何一个结点，该模型的缺点是在 进行路径表达式查询时需要建立大量的索引。 图2 3 10 e m 模型 d o m 树实质是x m l 文档的一种树结构模型。d o m ( d o c u m e n to b j e c t m o d e l ，文档对象模型) 是w 3 c 组织推荐的一组应用于结构完整的x m l 文 档和合法的h t m l 文档的编程接口，整个x m l 文档的逻辑结构是一种由 d o m 生成的结点对象所组成的树形结构，每个结点对象同时包含了方法 和属性，对应于x 札文档中的元素。结点之间遵从x m l 规范，存在着父 子和兄弟关系。而且父子、兄弟关系反映了文档中各元素之问的顺序关 第2 章预备知识 系。因此作为x m l 文档的存储模型，d o m 是胜任的，但是d o m 在表示元 素白j 的引用语义时，却显得无能为力。 图2 ，3 3d o m 模型 2 3 1x m l 数据的关系存储 综合o e m 模型和d o m 树模型的特点，并且结合了关系数据库的特性， 我们设计了x m l 数据库的关系存储模型，该模型利用关系的特性表示o e m 模型中元素之间的引用，利用树的特性表示d o b l 模型中父子兄弟之间的 关系。并且关系的映射不是利用d t d 产生，而是根据x m l 文档直接拆分 成固定的关系模式信息。在该模型中任何x m l 文档均被看成是一棵有序 的、有结点编号的树，结点编号是按前序和后序遍历x m l 文档中结点产 黑龙江大学硕士学位论文 生的序号，前序编号、后序编号都可以作为主键确定x m 。文档中的唯一 非叶子结点。用n o d e p r e 表示结点的前序编号，n o d e p o s t 表示结点的后 序编号，用p a r 表示结点的父结点的前序编号，则三元组( n o d e p r e ， n o d e p o s t ，p a r ) 也可以唯一地确定该模型中的一个结点，利用该三元组 可以表示路径查询中结点与结点之间的复杂关系，例如子孙关系，兄弟 关系、位置关系、父子关系等等。由于x m l 数据库允许存储多个x m l 文 档，因此采用x m l 文档编号d o c i d 表示不同的文档，根掘x m l 数据的特 点和对于有效路径表达式查询功能的支持，可以将x m l 文档拆分为六个 关系，由x m l 文档所拆分的六个关系的存储的模式如表2 3 1 卜2 3 1 6 所示。 名称数据类型说明 t a g n a m ec h a r a c t e r ( 8 0 )标签名称 t a g n oi n t e g e r标签编号 表2 3 1 1 标签名称表( x m l t a g 表) 标签名称表专门用于保存x m l 文档的标签名称和标签编号信息，其 中标签名称t a g n a m e 既可以是元素的名称也可是元素属性的名称，多个 x m l 文档的标签名或属性名称都存储在x m l t a g 表中，标签编号t a g n o 是 用来唯一标识标签名称的整型数字。 名称数据类型说