（计算机应用技术专业论文）基于双路索引的xml查询优化研究.pdf

摘要 基于双路索引的x m l 查询优化研究 摘要 x m l 是一种可扩展的标记语言，由于其丰富的表达能力和自描 述性、灵活性等特点，被广泛应用于w e b 环境下数据的表示和共享。 随着大量数据以x m l 格式保存，如何高效、系统、科学地管理x m l 文档己成为数据库研究领域中的一个重要挑战。 本文首先研究了从x m l 模式到关系模式之间的映射，然后给出 了一个基于s c h e m a 的x m l 存储模型，在这个存储模型基础上研究 了x m l 查询语言和索引查询技术；结合多种索引方法，提出了双路 索引模型，最后是它的查询处理算法，“大体上包含以下内容： ( 1 ) 由于采用传统的模型来存储x m l 文档虽然模型简单，但 是它仅适合于传统的以从上到下或从下到上顺序遍历x m l 文档，查 询效率较低，本文在改进的基础上提出了一个基于s c h e m a 的x m l 存储优化模型。利用在实际应用中经常存在的x m l 数据的模式信息 x m ls c h e m a ，根据相应的转换规则，生成基于关系数据库的存储模 型。与传统方法相比，其优点在于：将传统的大表集中存储分散成相 互关联的小表存储，适合从任意层次遍历x m l 文档。当文档比较大、 ； 节点数比较多时，利用该存储模型进行查询，程序不必一层一层逐个 节点遍历文档，提高了查询效率。此外，它还为索引的建立提供一个 相对持久和稳定的参考。 北京化t 大学硕。f ：学位论文 ( 2 ) 在基于s c h e m a 的x m l 存储模型上，提出了一种新的x m l 文件索引方法d i 索引。目前的路径索引多倾向于解决绝对路径表达 式的查询，而对于相对路径表达式的处理，得到满足路径表达式的结 果可能需要遍历整个索引，付出较高的查询代价。d i 索引方法采用 倒排文件索引机制及中文分词技术，建立了绝对索引模型和相对索引 模型，能有效支持各种形式的路径表达式，又不会占用过大的空间。 绝对索引模型将查询路径表达式缩短，减少了比较次数，相对索引模 型建立父子索引表补全路径，用较小的索引结构替代原始查询。利用 这种索引方法克服了元素查找总是从树的根部开始进行的缺陷，节约 了索引存储空间，提高了查询速度。 ( 3 ) 基于d i 索引，本文还研究给出了相关查询处理的算法。采 用f a b r i c 索引和d i 索引，对3 种不同的查询语句进行了测试，给出 了模型仿真试验结果。实验结果表明，该方法可以有效地提高查询处 理的性能。 关键词：双路索引，倒排索引，查询优化 a b s t r a c t d o u b l ei n d e x b a s e dx m ld a t aq u e r y o p t i m i z a t i o n 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 ) i saf l e x i b l ed a t af o r m a ta n di s f a s te m e r g i n ga st h ed o m i n a n ts t a n d a r df o rr e p r e s e n t i n ga n de x c h a n g i n g i n f o r m a t i o no nt h ei n t e r n e tb e c a u s eo fi t sa b u n d a n te x p r e s s i o na n d s e l f - d e s c r i p t i o n ，f l e x i b i l i t y , e t c w i t ht h el a r g ea m o u n to fd a t ai nx m l f o r m a t ，h o wt om a n a g et h ex m l d o c u m e n ti na ne f f i c i e n t ，s y s t e m a t i ca n d s c i e n t i f i cw a yh a sb e c o m eag r e a tc h a l l e n g ei nt h ef i e l do fd a t a b a s es t u d y i nt h ep a p e r ，w ef i r s ta n a l y z et h em a p p i n gb e t w e e nx m ls c h e m a a n dr e l a t i o n a ls c h e m a ，a n dt h e np r o p o s ea nx m ls t o r a g em o d e lb a s e do n s c h e m a a f t e rt h a t ，w ed i s c u s san u m b e ro fk e yt e c h n i q u e so ft h ex m l i n d e x i n ga n dq u e r y b a s e do nt h er e s e a r c h ，w ep r o p o s e dad o u b l ei n d e x ( d i ) m e t h o d a tl a s t ，aq u e r ya l g o r i t h mi sp r e s e n t e d i tm a i n l yc o n t a i n s ： ( 1 ) a l t h o u g hi ti ss i m p l et ou s et r a d i t i o n a lm o d e lt os t o r a g ex m l d o c u m e n t s ，i ti so n l ys u i t a b l et ot h et r a d i t i o n a lm e t h o dt r a v e r s i n gx m l d o c u m e n t si n t o p t ob o t t o mo rb o t t o mt o t o po r d e r a n dt h eq u e r y i i l 北京化t 大学硕+ 学位论文 e f f i c i e n c yi sl o w i nt h i sp a p e r w ep r o p o s ea nx m ls t o r a g em o d e lb a s e d o ns c h e m a a c c o r d i n gt ot h er u l e so fc o n v e r s i o n ，u s i n gx m ls c h e m a w h i c ho f t e ne x i s t si np r a c t i c a la p p l i c a t i o n s ，w ec a ng e n e r a t eas t o r a g e m o d e lb a s e do nr e l a t i o n a ld a t a b a s e b yc o m p a r i n gw i t ht h ec o n v e n t i o n a l m e t h o d ，t h em o d e lh a ss o m em e r i t sa sf o l l o w s ：d i s p e r s et h et r a d i t i o n a l l a r g et a b l e i n t oi n t e r c o n n e c t e ds m a l l e ro n e s ，a n di ti ss u i t a b l et o t r a v e r s i n gx m l d o c u m e n t sf r o ma n yl a y e r w h e nt h ed o c u m e n ti sl a r g e a n dh a sm a n yn o d e s ，q u e r y i n gw i t ht h es t o r a g em o d e ld o n th a v et o t r a v e r s et h ed o c u m e n tn o d e - b y n o d et h u si tc a ni n c r e a s et h ee f f i c i e n c y i n a d d i t i o n ，t h em o d e lc a np r o v i d ea d u r a b l ec o n f e r e n c ef o ri n d e x ( 2 ) b a s e do nt h es t o r a g em o d e l ，t h i sp a p e rp r o p o s e san e wi n d e x e d s t r u c t u r e d is t r u c t u r a li n d e x t h ec u r r e n tp a t hi n d e xt e n d st or e s o l v et h e q u e r i e so na b s o l u t ep a t he x p r e s s i o n t or e l a t i v ep a t he x p r e s s i o n ，i no r d e r t og e tt h er e s u l t sm e e t i n gt h ee x p r e s s i o n ，i tm a yh a v et ot r a v e r s et h e w h o l ei n d e x t h ec o s ti sh i g h a p p l y i n gi n v e r t e df i l ei n d e x i n gt e c h n i q u e a n dc h i n e s ew o r ds e g m e n t a t i o nt e c h n i q u e ，d im e t h o db u i l d sa na b s o l u t e i n d e xm o d e la n dar e l a t i v eo n e t h em e t h o dc a ne f f i c i e n t l ys u p p o r t d i v e r s e q u e r i e s t h e a b s o l u t ei n d e xm o d e lr e d u c e st h en u m b e ro f c o m p a r i s o nb ys h o r t e n i n g t h e p a t he x p r e s s i o n s t h e r e l a t i v eo n e c o m p l e t e st h ep a t he x p r e s s i o n sb ys e t t i n gu pp a r e n t c h i l di n d e xt a b l ea n d r e p l a c e so r i g i n a lq u e r i e sw i t hs m a l li n d e x s t r u c t u r e t h i sm e t h o dc a n a v o i dt h ed e f e c to fa l w a y st r a v e r s i n gt h et r e ef r o mt h eb o o ta n ds a v e i v a b s t r a c t s t o r a g es p a c e a l s o ，i ti m p r o v e st h eq u e r ye f f i c i e n c y ( 3 ) b a s e do nd i ，t h i sp a p e ra l s op r o p o s e saq u e r ya l g o r i t h mr e l a t e d t ot h em e t h o d a i d e rt h et e s to nt h r e ed i f f e r e n tq u e r i e sb e t w e e nf a b r i c i n d e xw i t hd ii n d e x ，m o d e ls i m u l a t i o nr e s u l t sa r eg i v e n e x p e r i m e n t a l r e s u l t ss h o wt h a tt h em e t h o dw o r k sw e l l k e yw o r d s ：d o u b l ei n d e x ，i n v e a e di n d e x ，q u e r yo p t i m i z a t i o n v 北京化工大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声 明的法律结果由本人承担。 作者签名：鏊日期： 关于论文使用授权的说明 i o 、6 、) 学位论文作者完全了解北京化工大学有关保留和使用学位论文的规 定，即：研究生在校攻读学位期间论文工作的知识产权单位属北京化工大 学。学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可 以允许采用影印、缩印或其它复制手段保存、汇编学位论文。 保密论文注释：本学位论文属于保密范围，在土年解密后适用本授 权书。非保密论文注释：本学位论文不属于保密范围，适用本授权书。 v “ 作者签名：量整日期：! 里：墨：2 导师签名： 醐：盟字一 第一章绪论 1 1 研究的背景和意义 第一章绪论 随着i n t e m e t 的迅速发展，互联网己经成为新经济时代的标志，它极大地改 变了人们发布、获取、使用信息的方式，i n t e r n e t 成为了一个拥有巨大信息资源 的开放的、分布的信息空间，人们从信息缺乏进入到信息极大丰富的年代。 w e b 上的数据激增，面对庞大的信息海洋，从众多的资源中快速提取所需要 的信息通常极为困难。其中虽然有硬件方面的原因，但是主要是由h t m l 的性 质引起的。 尽管h t m l 自发明以来，已成为最成功的电子发布语言，但是它仅注重数 据的显示格式，它的标记仅仅反映了信息应该如何在页面上表现，并没有对信息 本身进行描述，并且它的标记是固定的，不能够根据需要进行扩展。随着w e b 应用的日益广泛，它的局限性越来越明显，不适于作为i n t e m e t 上信息交换和标 识的工具。 1 9 9 8 年2 月，w 3 c ( w b r l dw i d ew e bc o n s o r t i u m ，互联网联合组织) 推出了 一种新型的w e b 语言- x m l1 0 t ，以此来取代已跟不上网络需求的h t m l ( h y p e rt e x tm a r k u pl a n g u a g e ，超文本标记语言) 语言，并正式推荐x m l 成为 下一代互联网标准。x m l1 0 是s g m l ( s t a n d a r dg e n e r a l i z e dm a r k u pl a n g u a g e ， 标准通用标记语言) 的一个简化子集，它将s g m l 的丰富功能与h t m l 的易用性 结合到w e b 应用中，以一种开放的、自描述方式定义数据结构，在描述数据内容 的同时能突出对结构的描述。x m l 的嵌套结构可以表示现实世界中各种复杂的 对象，各种格式的数据都可以比较容易地转化为x m l 数据，这使得x l 日 常适 于w 曲信息的发布和集成。 和h t m l 相比，x m l 具有以下几个优点： ( 1 ) 自描述性：x m l 简单，具有自描述性且易于解析。这个特性使计算机 可以在没有人为干涉的情况下，理解数据的含义。各种应用都可以按照各种方式 解析、过滤和重构x m l 文档。 ( 2 ) 可扩展性：h t m l 中的标记是固定的，不允许用户自行定义他们自己 的标识或属性，而在x m l 中，标记由用户定义，可以任意地扩展，使其它信息 系统自动了解文档的内容自行定义新的标识及属性名，以便更好地从语义上修饰 数据。 ( 3 ) 结构性：h t m l 不支持深层的结构描述，x m l 的文件结构嵌套可以复 北京化工大学硕：卜学位论文 杂到任意程度，能表示面向对象的等级层次。 ( 4 ) 细粒度的数据处理：h t m l 中的标记表示的是数据的显示格式，没有 任何语义，而x m l 的标记则明确指出了数据的含义，使细粒度x m l 数据的处理 成为可能。 ( 5 ) 可检验性：h t m l 没有提供规范文件以支持应用软件对h t m l 文件进 行结构检验。而x m l 文件可以包括一个语法描述，使应用程序可以对此文件进 行结构检验。 近年来，随着w e b 技术的飞速发展，x m l 逐渐成为i n t e m e t 上数据表示和 数据交换的一个新标准。由于它具有灵活性、自描述性、可扩展性等特点，越来 越多的领域开始使用x m l 作为主要的存储格式和传输媒介，因此产生了大量的 x m l 数据。随着x m l 应用规模和复杂性的快速增长，以x m l 格式表示和存储 的数据得到了i n t e m e t 领域和数据库领域研究人员的广泛重视，i n t e m e t 上的应用 对x m l 数据的查询、定位和获取的需求不断增加，如何从众多的x m l 资源中 快速提取信息，对x m l 数据进行合理存储和快速查询，成为一个需要迫切解决 的问题，这也正是本课题的意义所在。 1 2 国内外研究现状 随着越来越多的结构化或半结构化的数据采用x m l 的标准进行存储和交 换。从数据库的角度来看，在这些大量的x m l 文档中所包含的数据应该可以进 行抽取和分析。如何对x m l 文档内容进行高效率的查询变得越来越重要。 为了实现结构化数据查询，将x m l 数据映射到某种数据模型，如关系模型、 关系对象模型、面向对象的半结构化数据模型以及o o d 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 数据l z j 。 用文件系统存储和管理x m l 数据，是最简单最方便的一种方式，但查询的 效率非常低。因此这种方式只适合于较小规模的使用，在比较正式、复杂和大型 的x m l 应用场合上并不多见。 原生x m l 数据库是专门设计用于存储和管理x m l 文档的数据库，目前已有 2 第一章绪论 很多研究机构开发了原生x m l 数据库，国外有l o r e u l 、t a m i n o l 4 j 、t i m b e r t m 等， 国内主要是人民大学的o r i e n t x 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 l 数据库只能按顺序进行扫描，一直到文档的末尾。而关 系数据库和面向对象数据库则可以将文档分成小块同时进行搜索，速度比原生 x m l 数据库当然要快得多。由于目前它是一种全新的数据库，有很多技术还不 够成熟，因此，使用原生x m l 数据库存储和管理x m l 数据还有待进一步的研究 和发展。 使能x m l 数据库，即在现有的关系数据库系统或面向对象数据库系统【7j 基础 上扩展相应功能，使其能够胜任x m l 数据的处理。由于当前的面向对象数据库 系统的性能仍不足以支持对大规模数据的复杂查询，因此基于关系数据库的存储 查询是一种较有前景的方式。关系数据库方法是将x m l 半结构数据转换为结构 化数据后存储在二维表中，利用关系数据库来实现对x m l 数据的存储和管理。 对x m l 数据的查询操作转化为一系列关系查询操作，利用关系查询代数、查询 处理和优化机制来响应查询。同面向对象数据库和原生x m l 数据库相比，关系 数据库是当今主流的数据库，这就意味着人们在关系数据库中投入很多。目前， 企业大多把很多重要的数据存放在关系数据库中，如果要部署另一种数据库，则 要把这些数据倒出来，这就需要花费大量的人力物力同时还存在数据丢失的风 险。另外还要培训大量的工作技术人员。因此，利用关系数据库方法，能够将现 有的大量存储在关系数据库中的商用数据集成到系统中来。 此外，关系模型有着坚实的代数理论基础。它能表示太多的实际问题。关系 数据库具有数据结构化、程序与数据间较高的独立性、最低冗余度、易于扩充、 易于编制应用程序等优点。它在存储管理，查询优化等许多方面都较其他系统远 为成熟和稳定。使用关系数据库存储x m l 数据，可以充分利用已有的非常成熟 的关系数据库技术，如存储管理、并发控制、恢复、版本机制等有效地管理数据。 目前主流的数据库厂商j t l m i c r o s o t 、o r a c l e 、i b m 等都在其原来的数据库系统的 基础上进行功能扩充，开发出了支持x m l 的数据库产品，女i s q l s e r v e r2 0 0 0 ， 3 北京化下大学硕士学位论文 o r a c l e9 i ，d b 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 研究中的一个热 点和难点。国内有复旦大学的v x m l r t 8 】系统，i _ _ _ 1 外有c o n t e n t x m l t 9 】系统、 m a r k g r a v e s 1 0 j 系统等。 v x m l r 的主要思想是：先把) ( i 骥式映射为关系模式，然后把x m l 文档存 入关系数据库中。查询时，先把x m l 查询语言重写为s q l 语句，然后把查询结果 重构为x m l 文档。v x m l r 采用的是朴素的映射算法，用表外键表示元素的父子 关系。由于v x m l r 系统存储的表结构太多，查询重写复杂，因此查询效率较低。 c o n t e n t x m l 是麻省r e a d i n g 的x y v i s i o n 企业研制的一套内容管理系统，它可以 在任何一种流行的关系数据库中存储x m l 文件。其优点是可以开展基于内容的 协同工作，进行多通道内容输出。m a r k g r a v e s 系统f l q m a r k g r a v e s 提出，采用独立 于文档的关系存储模式把l 存储到关系表中。独立于文档的关系存储的最基 本思想是文档中每种结构类型都有自己的关系表( 元素，属性和字符数据区域) ， 还有一个文档表和元素与它们的组成部分( 子元素或字符数据) 之间的父亲孩 子关系表。m a r k g r a v e s 系统的缺点是所有内容、属性混合存储，存储结构不够直 观。 由以上的分析可知，由于关系数据库拥有强大的功能、良好的结构特征支持 x m l ，所以x m l 与关系数据库的结合将是一种必然趋势。 为了查询x m l 数据，学术界已经提出了多种查询语言，如l o r d 【l ， x m l _ q l l l 2 1 ，x m l - g l f l3 1 ，x p a t h t l 4 】，q u i r t l 5 】，x i 涮1 6 】等等。这些查询语言的 一个显著的特点就是使用路径表达式，路径表达式是一种对x m l 文档的内容进 行定位、检索的表达式。在关系数据库中，x m l 数据被分散到各个关系表中， 所以要进行路径信息的查询，就要涉及到一连串的关系表，严重影响了查询效率。 为了解决这个问题，利用索引技术来优化x m l 的查询得到了广泛研究，目前， 提出了多种索引方法支持x m l 数据的查询，第1 类是基于节点的x m l 索引，其基 本思想是将x m l 数据分解为数据单元的记录集合，同时在记录中保存该单元在 x m l 数据中有助于确定节点间结构关系的位置信息，如x i s s 0 7 1 ，x r - t r e e t 堪j ， m p m g j n t l 9 】等；第2 类是基于路径的x m l 索引，其基本思想是对x m l 树结构中 节点的路径信息进行归纳，采用某种约简方式，使得约简后的树结构只维护不同 的路径信息，而不会存在具有相同路径的两个节点，如d a t a g u i d e l 2 0 1 ，1 - i n d e x t 2 1 】， 4 第一章绪论 a ( k ) i n d e x l 2 2 1 ，d ( k ) 2 3 1 ，m ( k ) 【2 4 】，c t r e e 2 5 1 ，a p e x t 2 6 1 ，f a b r i c 2 7 】索引等。 d a t a g u i d e 减少了遍历路径查询时所需的部分节点，对从根部遍历x m l 文档 是有效的，但对于某些路径查询要进行多次的连接操作，查询效率较低。1 - i n d e x 引入了双似等价关系的概念，能够很好地满足简单路径查询的要求，但在实现性 能上稍显不足。a ( k ) i n d e x 中主要利用了b i s i m i l a r i t y 的概念，保证索引中的每 个节点拥有相同的k 阶的b i s i m i l a r i t y ，其缺点是要求索引中所有的节点拥有相同 的k 阶b i s i m i l a r i t y ，而没有考虑实际的查询需求和源数据的结构特点，当源数据 变化时不易更改索引结构。因此，a ( k ) i n d e x 能准确查询长度不大于k 的路径，但 当路径长度大于k 时，一般需要遍历整个数据图以进行验证，运算代价很高。c t r e e 基于组的概念建立的编码方式能有效处理带有分支的查询表达式，但在c t r e e 中 组节点很多的情况下效率不高。a p e x 对频繁使用的路径创建索引，能够有效地 处理某些相对路径查询，但对非频繁使用路径和从根节点开始的路径查询效率较 低。f a b r i c 索引能处理较复杂、含有谓词修饰的路径表达式，它将半结构化数据 之间的关系表示成路径，将路径编码成字符串，然后在字符串上面建立索引，它 存储了x m l 数据的层次结构信息，使对x m l 数据的查询和更新所需要的时间与 层次相关而不是与索引关键字的长度相关，但丢失了元素节点问的结构关系，因 为它只保留了有文本值的元素节点的信息。 作为互联网的新技术，x m l 的应用非常广泛，可以说x m l 己经渗透到了互 联网的各个角落。x m l 在各领域的应用可以简单地分为以下几类【2 8 】： ( 1 ) 设计置标语言 x m l 为用户提供了定义本行业、本领域置标语言的优秀工具。目前化学领 域的c m l ，数学领域的m a t h m l ，移动通信领域的w m l 等都使用x m l 定义本行 业的置标语言。 ( 2 ) 异构系统间的信息集成 由于各个企业或行业之间使用各不相同的系统，给企业之间、部门之间的数 据交换，信息共享造成了极大的不便。因为这些系统的结构各不不同，往往需要 开发专门的软件，才能把他们的数据统一到一起，这显然是一项耗时耗力的工作。 x m l 的出现，为信息的标准化提供了有力的工具。使用x m l 做数据交换可以使 应用程序更具有弹性。x m l 为各行业带来了新的机遇和活力。 ( 3 ) 文件保值 x m l 良好的保值性和自描述性使其成为保存历史档案的最佳选择，很多如 政府文件、公文、科学研究报告等都使用x m l 格式来保存。 ( 4 ) 灵活的w 曲应用 由于x m l 是由s g m l 特别为w e b 简化的，因此x m l 文档将成为w e b 资源的重 北京化t 大学硕十学位论文 要组成部分，x m l 使得搜索引擎更为智能和准确。x m l 还可以用于建立多层w e b 应用。 1 3 课题的难点 ( 1 ) x m l 数据存储模型 对x m l 数据的查询、检索、更新等操作都建立在一定的存储模式基础上， 它的存储方式在很大程度上影响了查询处理的效率。但x m l 文档数据是一种半 结构化数据，利用现有的技术无法有效地存储和管理它，因此如何更有效的存储 x m l 数据，将是本文研究的重点。 ( 2 ) x m l 索引结构的构建 除了存储方案之外，索引技术也是影响x m l 查询效率一个非常重要的因素。 如何针对x m l 数据建立有效的索引结构，提高查询效率，降低查询所需成本。 1 4 课题的主要创新点 ( 1 ) 探索改进了基于s c h e m a 的x m l 存储优化模型。利用在实际应用中经 常存在的x m l 数据的模式信息x m ls c h e m a ，根据相应的转换规则，生成基于 关系数据库的存储模型，建立了从x m ls c h e m a 到关系数据库的映射规则，将 x m l 文档数据的查询问题最终转化为关系数据库中数据的查询操作。与传统方 法相比，其优点在于：将传统的大表集中存储分散成相互关联的小表存储，它不 仅适合传统的从上到下或从下到上顺序遍历x m l 文档，还适合从任意层次遍历 x m l 文档。当文档比较大、节点数比较多时，如果利用该存储模型进行查询， 程序不必一层一层逐个节点遍历文档，提高了查询效率。 ( 2 ) 在基于s c h e m a 的x m l 存储模型上，提出了一种新的x m l 文件索引 方法一d i 索引。研究了x m l 的数据模型，采用倒排文件索引技术和中文分词技 术，建立了双路索引模型，作为有效实现x m l 查询的基础。主要内容包括t 针 对查询需求，设计了完整的索引结构，包括路径索引表( p i ) 和文本索引表( t i ) ， 父子索引表( p c i ) 。给出了从模式信息出发的索引构建方法。设计了支持多种索 引查询方式，包括绝对路径查询，父子关系和祖先后代关系的基本结构关系， 相对路径等，可以有效地支持路径表达式的计算，其结果线索路径集可以进一步 用于目标路径集的计算。基于以目标节点为导向的原则，给出了路径查询的选择 策略。 与目前的路径索引方法相比，其优点在于：建立了绝对索引模型和相对索引 模型，能有效支持各种形式的路径表达式，又不会占用过大的空间。绝对索引模 6 第一章绪论 型将查询路径表达式缩短，减少了比较次数，相对索引模型建立父子索引表补全 路径，用较小的索引结构替代原始查询。利用这种索引方法克服了元素查找总是 从树的根部开始进行的缺陷，节约了索引存储空间，提高了查询速度。 ( 3 ) 目前的x m l 查询处理研究工作主要关注单个技术问题，如侧重x m l 存储研究却没有考虑在这种存储方式下查询处理的效率问题，很少考虑多个技术 在x m l 查询处理中的综合应用情况，本文从整体的计算框架出发，给予了更多 的考虑。 1 5 论文的研究内容和组织结构 1 5 1 论文的主要研究内容 本文对x m l 查询中所涉及到的存储、查询算法和查询语言等进行了研究。 主要研究内容包括： ( 1 ) 结合x m l 数据查询研究背景，对x m l 数据查询算法研究现状、发展 以及应用进行分析和总结。 ( 2 ) 全面分析当前主流x m l 数据库的技术特点和应用，包括传统关系数 据库的x m l 扩展和原生x m l 数据库。 ( 3 ) 探索改进了基于s c h e m a 的x m l 存储模型。 ( 4 ) 研究x m l 数据库索引技术和x m l 查询处理技术。 ( 5 ) 提出了一种双路索引模型以及相关查询处理的算法。 ( 6 ) 搭建实验环境，实现算法，并进行性能分析。 1 5 2 论文的组织 本文对x m l 查询处理中的关键技术进行了深入的研究和阐述，全文的组织 结构如下： 第一章介绍了x m l 查询处理的研究背景和意义，国内外的研究历史和现 状，以及课题的难点和创新点，本文的主要研究工作和组织安排。 第二章研究了x m l 的存储技术，对x m l 数据的存储和典型的x m l r d b 映射方法进行了深入分析，并提出了基于s c h e m a 的x m l 存储优化模型及相关 映射方法，与现有的存储模型进行了对比。为后续章节的基于双路索引的x m l 查询研究与实现奠定了理论基础。 第三章研究了x m l 索引查询技术，对常用的索引策略、查询处理技术进 行了深入探讨，并分析了存在的问题。然后提出了一种双路索引模型，作为有效 7 北京化t 大学硕+ 学位论文 实现x m l 查询的基础。针对查询需求，设计了完整的索引结构，给出了从模式 信息出发的索引构建方法，指出了其中的关键技术问题，设计了支持多种索引查 询方式，并提出了相关查询处理的算法。 第四章通过实验将f a b r i c 索引与本文提出的d i 索引在执行同样的查询语句 时所需要的时间进行了对比，给出了实验结果。 第五章对本文的主要工作进行了总结，同时也提出了进一步的研究和工作。 8 第二章x m l 存储模型的研究o j 改进 第二章x m 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 文 档到关系表的映射。目前提出的映射方法主要分为两类：结构映射方法 ( s t r u c t u r e - m a p p i n ga p p r o a c h ) 和模式映射方法( m o d e l m a p p i n ga p p r o a c h ) 。对于结构 映射方法，它把x m l 文档结构( d t d 或x m ls c h e m a ) 直接映射到数据库关系模式， 将x m l 文档数据存放到这些模式对应的关系表中，不同d t d 的x m l 文档生成不 同的关系模式，它是x m l 模式( 或d t d ) 相关的。对于模式映射方法，它将x m l 文档模型( 即文档树结构) 映射为关系模式，即将x m l 文档树中的节点和边映 射为关系模式，得到的存储模式与x m l 文档结构无关，因此可以使用一种固定 的关系模式存储所有的x m l 文档结构，它是x m l 模式( 或d t d ) 无关的。 2 1 基于模式映射的存储模型研究 2 1 1x m l 模式及映射 l 包含三要素：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 模 式( s c h e m a ) 、可扩展的样式语言( e x t e n s i b l es t y l el a n g u a g e ：x s l ) 以及可扩展链接 语( e x t e n s i b l e “i l l ( l a n g u a g e ：x l l ) 。其中，x s l 用于规定x m l 文档呈现样式的语 言，它使数据与其表现形式相互独立；而x l l 用于扩展目前w e b 上已有的简单链 接。传统数据库中，数据的定义、查询表达、查询处理与优化等都依赖于模式。 下面是一个我们都非常熟悉的地址联系信息的x m l 文档片段： 9 北京化t 大学硕十学位论文 x m l 2 010 = l t 京 朝阳区 张- - - 化工大学 10 0 0 2 9 6 6 6 6 8 8 8 8 李四 三元桥 10 0 0 2 8 6 7 8 9 012 3 文档类型定义( d t d ) 【冽是描述l 数据模式的模式定义语言，它描述了文档 中元素的内容和结构，主要包括元素类型声明、属性类型声明、记法声明和实体 声明。d t d 规定可以在文档中使用哪些标符，应该按什么次序出现，哪些标记符 可以出现于其他标记符中，哪些标记符有属性，等等。由于x m l 本身并不是一 种语言，而是定义语言的一个系统，因此，想要使用x m l 进行数据交换的工业 或组织可以定义各自的d t d 。 d t d 存在以下缺陷： ( 1 ) d t d 采用一种和x m l 完全不同的语法，为了分析d t d 必须使用另外一 套软件。 l o 第二章x m l 存储模型的研究0 改进 ( 2 ) d t d 的数据类型非常有限，除了支持字符串类型外，对其它基本类型 i n t ，d a t e ，f l o a t 都不支持。 ( 3 ) 由于x m l 灵活、强大的表达能力，普遍用于数据集成和交换，为了方 便与数据库之间进行数据转换，需要一套和数据库数据类型兼容的数据类型表 示。 ( 4 ) d t d 对元素间施加了顺序，但在很多情况下，兄弟元素之间是没有顺 序关系的。 x m ls c h e m a 3 0 1 是d t d 之后第二代用来描述x m l 文档结构的标准，拥有许多 类似d t d 的准则，但又要比d t d 更为强大一些。与d t d 相比，x m l s c h e m a 的明 显好处在于x m ls c h e m a 文档本身也是x m l 文档，而不是像d t d 一样使用特殊格 式。这就大大方便了用户和开发者，因为他们可以使用相同的工具来处理x m l s c h e m a 和其他x m l 信息，而不必专门为s c h e m a 使用特殊工具。另外，s c h e m a 支 持数据类型的定义。由于x m ls c h e m a 的种种优点，现在s c h e m a 取代d t d 已成大 势所趋，成为x m l 体系中正式的类型语言。目前，国际上一些知名企业和组织 纷纷提供对x m ls c h e m a 的支持。 x m ls c h e m a 定义了x m l 文档的结构，包括x m l 文档的元素节点名称、元素 节点类型( 简单元素节点或复杂元素节点) 、元素节点值的类型( 整型、浮点型、 字符型、时问日期型等) 、属性节点名称、属性节点值的类型( 与元素节点值的 类型相似) 、节点的其它约束( 如最大出现次数、最小出现次数、节点顺序等) 。 通过x m ls c h e m a 我们可以了解x m l 文档的详细的结构信息。下面是用x m l s c h e m a 定义x m l 文档的片断： 钒s d ：s e q u c e 北京化丁大学硕十学位论文 从x m ls c h e m a 对x m l 的定义可以看出，一个x m l 主要含有3 类节点信息： 简单元素节点、复杂元素节点和属性节点。 简单元素节点是指只含有文本信息的节点，复杂元素节点是指含有属性节点 或子节点的节点。复杂元素节点本身可以含有文本信息，也可以不含有。简单元 素节点和属性节点类似，都是 的数对。 模式映射方法是一种最早被研究的用于存储x m l 数据的技术，也是实现关 系数据库存储x m l 数据的重要部分。 模式映射方法将任何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 存储模犁的研究0 改进 一个模板，x m l 在关系数据库中的存储按照数据库提供的模板来组织数据。模 式映射