（计算机科学与技术专业论文）基于二次索引技术的xml查询研究.pdf

摘要 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 数据树；压缩树；哈希编码；层次索引 r e s e a r c ho ns e c o n d ei n d e xt e c h n o l o g yf o rx m ld a t a w e ic h a n g f a n g ( c o m p u t e rs c i e n c ea n dt e c h n o l o g y ) d i r e c t e db ya s s o c i a t e p r o f e s s o rw e id o n g p i n g a b s t r a c t x m la st h en e w g e n e r a t i o n sd a t ae x c h a n g es t a n d a r d ，a r eg e t t i n gm o r ea n dm o r eu s ei n t h en e t w o r ka p p l i c a t i o n t h e r ea r et h em a s s i v ex m ld a t a h o wt oc a r r yo nt h ee f f e c i t i v e i n q u i r yt ot h ex m ld a t at op r o c e s st h eh o ts p o tw h i c hi n t ot h ep r e s e n ts t u d i e s ，h o w e v e r , x m ld a t ai sas e m i s t u c t u r i z e dd a t a i th a st h ec h a r a c t e r i s t i c so fd e f i n i t i o na n de x p a n d t h e s e c h a r a c t e r i s t i c sh a v ec a u s e dc e r t a i nd i f f i c u l t yt ot h ex m ld a t aq u e r yw o r k t h ei n d e xa c h i e v e m e n ta c c e l e r a t e st oi n q u i r et h ep r o c e s s i n ga l li m p o r t a n tm e a n st h a ti s p l a y i n gt h ec r u c i a lr o l ei nm a n yd o m a i n s t h e r e f o r e ，e n h a n c et h ed a t au s i n gt h ei n d e xi sa n f e a s i b l em e a n s t h i sa r t i c l ei nc a r r i e so nt h eg e n e r a l i z e da n a l y s i st ot h ed o m e s t i ca n df o r e i g n r e s e a r c hp r e s e n ts i t u a t i o ni nt h ef o u n d a t i o n , h a sf u r t h e rc o n d u c t e dt h et h o r o u g hr e s e a r c ht o t h ex m li n d e xt e c h n o l o g y p a p e rt h ei n d e xm e t h o dw h i c hp r o p o s e dt ot h er e c e n ty e a r sh a sc o n d u c t e dt h es t u d y r e s e a r c h , h a sa n a l y z e dt h ee x i s t i n gi n d e xc h a r a c t e r i s t i ca n dt h eg o o da n db a dp o i n t s b a s e do n t h i sp r o p o s e do n ek i n du s e st h ed i f f e r e n ti n d e xs t r u c t u r ea c c o r d i n gt ot h ew a yt oc a r r yo nt h e i n q u i r yt h em e t h o d t h i sm e t h o dh a sd i v i s i o no fs i m p l ep a t ha n dt h eb r a n c hp a t h , u s e st h e c o m p r e s s i o nt r e ei n d e xa n dt h eh a s hc o d i n gi n d e xs e p a r a t e l yc a r r i e so r lp r o c e s s i n g t h ec o m p r e s s i o nt r e ei n d e xu s e dt op r o c e s s i n gt h es i m p l ep a t ht oi n q u i r e si nt h ep r o c e s s t h i sm e t h o dn o to n l yh a sp r o v i d e dt h es u c c i n c tw a yo u t l i n ei nt h eg r o u pl e v e l ，a n dh a s s u p p l i e dt h ef a t h e r sa n ds o n si nt h ee l e m e n tl e v e lt h er e l a t i o n a ld e t a i l e dl i n ki n f o r m a n t i o n w h e nt h ee l e m e n tl e v e lm a p p i n gm a yaf a s tv i s te l e m e n tf a t h e rn o d e ，t h eg r o u pl e v e lm a y r e d u c et h er e s e a r c hs p a c ee f f e c t i v e l y t h i si n d e xu s er e p l a c e db a s e do ng r o u p se l e m e n t q u o m t i o nh a sc a r r i e do nt h ec o d et ot h ee l e m e n t , r e d u c e dt h es p a c ew h i c ht h ei n d e xn e e d e d t h ei n t r o d u c t i o ni m p r o v e m e n t sp l a t o o ni n d e xa n dt h er e v e r s ei n d e xs p e e du pt ot h ee l e m e n t j u d g m e n t ，m o r eh i g h l ye f f e c t i v eo b t a i n si n t h ei n d e xg r o u pt h ei n f o r m a t i o n t a k e st h e r e f e r e n c eb a s e do nt h eg r o u pl e v e l se l e m e n t ，n o to n l ym a yc a u s et h ec o m p r e s s i o nt r e et o b e c o m ea c c o r d i n gt ot h eg r o u pc l u s t e ra r r a n g e si ni n v e r t e do r d e rt h et a b l e ，t h u sf o ra r r a n g e s i ni n v e r t e do r d e rt h et a b l ea n dt h eg r o u ps c o p ei ng r o u pl e v e l t h e s t r u c t u r ei n d e xp r o v i d e sa b e t t e rc o n n e c t i o n ，b u tm a ya l s oe a s yt oc a r r yt h ec l a s s i f i c a t i o na c c o r d i n gt ot h eg r o u pl e v e l t h ec l o s ee l e m e n tw i l lp u ti nt h es a m ep l a c ei na d v a n t a g e o u sf o rt h ei n d e x t h em a i ni d e ao ft h eh a s hc o d i n gi n d e xi sm a k ee a c hn o d ec o r r e s p o n d e n c eai n d e xt r e e n o d e i nt h ei n d e xt r e en o n - l e a fn o d e si sd e p o s i t i n gt h i sn o d ei nt h ex m ld o c u m e n t s p o s i t i o n w h a tt h ei n d e xt r e es a v e si si nt h ex m ld o c u m e n t st h ef a t h e rn o d et oi t ss u b n o d e s p a t hh a s hc o d i n g i nt h ei n d e xt r e e ，l e a fn o d ei ss t o r i n gt h ex m l d a t a t h eh a s hc o d i n gp a t h i n d e xh a st h eq u i t eg o o de x t e n s i o n , t h i si n d e xr e p l a c e si nt h eb e f o r e h a n di n d e xt h r o u g ht h e m e m o r y n o d e sh a s hc o d i n gt os a v et h en o d e t h u s ，i tc a nr e d u c e dt h es t o r a g es p a c ew h i c ht h e i n d e xf i l en e e d s t h r o u g ht h en o d ec a r r i e so nt h ec o d et ot h ed o c u m e n t st r e e ，t r a d e st h es t r i n g o fc h a r a c t e ra t t i r ef o rt h ei n t e g e r , r a i s e st h e 岫u i r ys p e e d i nt h ei n d e xi n t r o d u c t i o nt r a d i t i o n d a t a b a s et h el e v e li n d e x sc o n c e p t ，h a sr e a l i z e dt ot h ef r e q u e n tu s ep a t hd i r e c ta c c e s s t h i sa r t i c l ep r o p o s e dal e v e li n d e x i tc a nu s et h ed i f f e r e n ti n d e x e dm o d ea c c o r d i n gt ot h e p a t he x p r e s s i o n ss p e c i a ld e t a i l s i ti sg o o da ti m p r o v et h ee f f i c i e n c yo f r e t r i e v a l k e yw o r d s ：x m ld a t at r e e ，c o m p a c tt r e e ，h a s hc o d i n g ，l a y e ri n d e x 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名；二蚴日期：2 p 加年s 月冲日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印 刷版和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门 ( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被 查阅、借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用 影印、缩印或其他复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：塾遮茎 指导教师签名： 弛1 车 日期：”妒年箩月2 9 日 日期：优归年于月勿日 中国石油大学( 华东) 硕士学位论文 1 1 研究的背景及意义 第一章绪论 随着因特网技术的发展，网络成为人们重要的消息来源和信息媒介，并在平时 的工作生活中扮演着越来越重要的角色。而作为新一代网络数据形式的x m l ( e x t e n s i b l e m a r k u pl a n g u a g e ，可扩展标记语言) i l l , 也受到了大家的关注。x m l 数据具有自描述 性、可扩展性等特点，使其在网络管理、电子文档交换、电子商务等众多领域得到广泛 使用，但也因此产生了大量的x m l 数据。如何对这些数据进行有效地管理和查询，成为 当今关注的研究热点。 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 e p 可扩展标记语言的缩写，是w 3 c 组织制定的新 一代用于网上数据交换的标准。它与h t m l 师出同门，都是从通用标记语言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 的一个子 集，但也是一种元语言。它同样允许用户定义自己的标记，来描述文档的结构。 为了对x m l 数据进行查询，一些查询语言被提了出来，例如：x p a t h t 3 9 1 ，x q u e r y ， l o r e l l 4 0 ，q u i l t 。现有的这些语言都采用正则路径表达式的方式对x m l 数据进行查询。 例如对路径q 的查询处理： q ：b o o k a r t i c l e a u t h o r = t o m 】 传统的处理方式是采用自顶向下或自底向上畔】的方式对整个x m l 数据进行遍历。假如 采用自项向下的方式处理q ：首先从b o o k 节点遍历其所有的后裔节点，检查这些后裔节 点是否有a r t i c l e 节点，若能找到再从查出的节点中找出具有属性a u t h o r = t o m ”的a r t i c l e 节 点。这种处理方式通常需要遍历整佃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 数据查询的索引技术相继提出。例如d a t a g u i d e s 【2 】，1 - i n d e x e s 3 1 ， t i n d e x e s 4 1 ，i n d e xf e b r i c t 5 】，x i s s l 6 1 。 d a t a g u i d e s 是对源数据从根节点开始进行约简，获得源数据的路径摘要。边标记连 接在起形成字符串路径，该路径在d a t a g u i d e s 中只描述一次。因为d a t a g u i d e s 为源数 据的就该快，索引减少了遍历过程中需要访问的节点。它可以在与查询路径长度成比例 的时间内求出通过该路径到达的所有节点的集合。该索引对从根节点开始的查询是非常 有效的。 t - i n d e x 是一种图结构的索引，它将源数据中的节点按照边的等价关系分组，再定义 模板来建立节点之间的对应关系，以此来提高路径连接的效率。利用该索引处理与定义 的模板相匹配的路径是简单有效的，但是将查询路径表达式按照模板重新构建是其要进 一步解决的问题。而1 - i n d e x 和2 i n d e x 其实是t - i n d e x 的特定情况。 i n d e xf a b r i c 索引是在p a t r i c i at r e e l 4 2 】基础上建立的索引。它采用关键字压缩的方法 为数据中的字符串建立索引。i n d e xf a b d e 索引的索引树是一种平衡树，对索引进行访 问所需的i 幻操作都是相同。 t o x i n 索引完整记录了x m l 数据图的全部路径结构信息，它适用于从任一节点开 始的查询匹配处理。t o x i n 主要包含两种不同的索引结构：v a l u ei n d e x 和p a t hi n d e x 。 p a t hi n d e x 由i n d e xt r e e 和实例函数集组成，i n d e xt r e e 是d a t a g u i d e s 索引的简化形式， 实例函数集与索引树中的边相对应，主要用来记录节点对之间的结构关系。 x i s s 索引将数据中的元素和属性作为查询的基本单，对于复杂路径，该索引首先 将其分解成简单路径，然后对拆分得到的简单路径进行查询，再将得到的查询结果进行 连接。其主要索引结构有父子关系索引、祖先关系索引、元素索引和值索引。x i s s 索 引在对路经表达式进行查询处理时，无并不需要遍历整个x m l 文档树。如果查询路径 是由n 个元素或者属性组成，x i s s 将先从索引中查找出这n 个节点，在处理过程中对 获得的节点进行至少( n 1 ) 次的结构连接。这种连接方式将使得一些不相关的节点也 被加入到连接操作的序列里从而影响简单路径处理过程中对双亲孩子关系或祖先后裔 关系的判断。 a p e x 索引是一种基于工作流的索引结构，该索引利用数据挖掘的方法结合常用的 2 中国石油大学( 华东) 硕士学位论文 查询数据来建立索引，将经常使用的查询路径对应的节点标签预先保存在一个哈希表 中。这样在查询时首先在哈希表中检索是否有满足的节点集合。该索引与d a t a g u i d e s 索引在结构上有些相似。x i s s 并不需要保存所有查询使用的路径索引，而是将频繁使 用的路径表达式建立成索引，这样即减小了索引所需的空间，又提高了查询效率。同时 该索引又是一个动态的索引，它可以根据查询路径使用频率的变化进行动态的更新。 x i s s 索引能够对某些相对路径进行有效的查询处理，但它对于带有元素值或属性值的 查询表达式的处理效率较低。 尽管研究人员在x m l 数据索引上取得了一定的成就，相续提出了一些很好的索引 结构和连接算法，但是现有的这些索引技术和连接算法还有那一项成为学术界公认的经 典的技术和算法，它们还都存在着这样或那样的问题。 d a t a g u i d e s 通过对源数据路径进行精简，减少了遍历过程中所需要查询访问的节点 数目，该索引对从根节点开始的遍历是有效的。然而，该索引没有利用x m l 数据的结 构信息，从索引中不能获得节点之间的位置关系，对节点的父子关系或祖先后裔关系的 判断需要遍历后确定，因此该索引在处理从任意节点开始的路经查询效率不高。 l o r e 索引是现在使用的索引中较为成熟和完善的索引技术。然而该索引与 d a t a g u i d e s 索引有着同样的确定：都没有充分利用x m l 数据所包含的结构信息。尽管 该索引在处理过程中减少了匹配和指针的操作，但是因为没有利用数据的结构信息使得 索引在向上和向下搜索时需要先对节点间关系进行判断，在确定父子或祖先后裔关系后 进行大量的连接操作，使得查询的代价较大。例如查询路径a r t i c l e i s s u e t i t l e ，在索引过 程中即要处理由标记t i t l e 与i s s u e 连接构成的父子节点对，还要检索由t i t l e 与a r t i c l e 连 接起来构成的祖先后裔节点对，而对祖先后裔节点对的处理是不需要的。 i n d e xf a b r i c 索引适用于以文档的根为起点的路径查询，而对于其它的路径查询则要 求首先进行多个索引的查询或对路径进行一个预处理。为了解决这一问题，研究人员提 出使用约简的摘要路径。但是因为在约简的过程中有可能丢失部分数据，索引在使用之 前要对摘要路径进行多次预选择。 x i s s 索引对每一个节点都有一个 的编码对，其中o r d e r 为先序遍历数据 得到的编码，s i z e 为其子孙编码的范围。该索引能够快速地对数据中元素之间的关系进 行判断。但是，该索引的 编码对中o r d e r 和s i z e 的取值是任意整数，当有新 的元素插入或删除元素时，需要重新对元素进行编码。此外，x i s s 会在n a m ei n d e x 和 d e m e n ti n d e x 以及a t t r i b u t ei n d e x 中为重复出现的标记重复建立索引，这即占用大量的 3 第一章绪论 存储空间，也增加了检索所需的时间，降低了查询的效率。 1 3 研究的主要研究内容和创新 在对x m l 数据进行查询的时候都只使用一种索引方法来处理，而这种“以不变应 万变 的思路对于数据形式不规则、表现形式灵活多样的x m l 数据并不合适。对x m l 数据查询通常使用的是路径表达式的方法。路径表达式可分为简单路径和分支路径，本 文在对现有索引方法进行研究的基础上，提出了一种根据不同的路径表达式采用不同的 索引方法的索引模式。该模式针对简单的路径表达式使用改进的压缩树索引方法进行查 询处理，而对复杂的分支路径表达式使用哈希编码的方式进行处理。 在本文中针对路径表达式的分类，采用了两种索引方法来对x m l 数据进行索引。 第一种是针对简单路径的压缩树索引。在压缩树索引中通过引入结构摘要的概念，过滤 掉不必要的节点，减少了遍历节点的数目。通过引入正排索引和倒排索引技术，对节点 之间的结构关系进行快速判断，减少了传统方法进行判断需要的遍历匹配操作。第二种 是针对分支路径的哈希编码索引。在哈希编码索引中引入关系数据库中层次索引的概 念，通过记录以前的查询信息，确定查询中的频繁使用路径，实现对频繁路径的直接存 取。通过对分支节点的检索提前对分支路径进行判断，减少了不必要的连接操作。 1 4 论文的组织结构 论文共分为五章，组织结构如下： 第一章绪论 主要介绍本课题研究的背景、目的及意义，总结了现阶段国内外关于x m l 数据索 引的研究现状，简单介绍了主要的研究内容和创新，并提出论文的研究目标以及实现的 具体内容与思路。 第二章x m l 索引技术的相关研究 主要介绍了路径查询处理技术、x m l 编码方案、常见的索引的分类，并对现有索引 中存在的问题进行了说明。最后介绍了一下二次索引的基本结构和使用到的相关知识和 概念。 第三章压缩树索引 主要介绍了压缩树索引的基本结构，及引入正排索引和倒排索引技术对其进行改进 的过程。然后以具体的示例介绍了索引的应用过程，并对索引处理查询的性能进行了评 4 中国石油大学( 华东) 硕士学位论文 价。 第四章哈希编码索引 主要介绍了哈希编码索引的基本结构、编码的过程、索引的构建过程，并利用示例 对索引的查询过程进行了说明。 第五章算法实现 用初步的实验来验证了所提索引策略的可行性。通过与其它索引的对比，表明该索 引在简单路径和频繁使用路径的处理上具有较好的效率。 第六章总结与展望 总结所作工作，列出了研究所取得的成果及创新，对索引技术研究工作进行了展望， 并明确了下一步研究的内容。 5 第二章x m l 索引技术的相关研究 2 1 前言 第二章x m l 索引技术的相关研究 为了能更好的利用x m l 这种数据结构，w 3 c 带i 定了一系列的标准，并针对x m l 数 据地查询工作成立了讧l 查询工作组( x m lq u e r yw o r k i n gg r o u p ) ，专门负责制定x m l 数据查询的数据模型和查询语言方面的规范。当前对x m l 数据查询的研究在许多方面学 习借鉴了关系数据库的研究成果。研究的领域主要有：数据模型、数据模式的建立与维 护、查询语言的设计、查询的处理过程、x m l 数据存储技术等。 1 、数据模型 对x m l 数据模型的研究现状有以下几种思路，一种是借鉴已经相对成熟的关系模 型，使用关系模型作为x m l 的数据模型。文献【1 4 】【1 5 】f 1 6 1 就介绍了这种方法；另一种是采 用半结构化的数据库模型，将x m l 数据映射到半结构化的数据库模式中。文献【1 刀对该 方法进行了研究。 2 、模式建立与维护 国际标准组织制定了关于x m l 模式定义的各种不同标准，其中典型的包括d t d 和 x m ls c h e m a 1 9 】【4 3 1 等。d t d 和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 解析器就可以根据给定的模式判断这个文档是否合法，即是否符合模式所规定的结 构和其他限制的要求。在数据交换的应用过程中，因为d t d 与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 数据的模式映射为传统数据库模式即 ( 关系的或面向对象的数据库模式) ；对于不带d t d 和模式的x m l 文档，从x m l 文档 中提取元素、结构信息并根据这些信息建立模式，再分别讨论与x m l 数据映射的关系模 式、半结构化的数据库模式的更新问题。 3 、查询语言的设计 由于x m l 文档时一种半结构化数据，传统数据库中的查询语言s q l 等不能直接应用 到这种数据结构上，因此在对半结构化数据的查询语言进行研究的基础上，针对x m l 6 中国石油大学( 华东) 硕士学位论文 数据的特点，先后推出了许多查询语言方案：l o r e l 2 0 1 2 1 】圈、x m l q l 2 3 1 1 2 4 、x m l g l 2 5 1 、 x s l t 2 6 1 1 2 7 1 等。同时，x m l 查询工作组也提出了一种查询语言：x q u e r y 。该语言借鉴了 关系数据库和半结构化数据查询语言的部分特点，作为一种用于描述对x m l 数据源的 查询的语言，具有精确、强大和易用的特点查询的处理过程。 4 、查询的处理过程 x m l 数据的查询处理研究包含方面几个方面：索引技术的研究、路径表达式的处理 与优化等。 在对x m l 数据进行查询处理的过程中，一个重要的步骤就是对路径表达式的处理与 优化，而对路径表达式的处理和优化时建立在前面介绍的数据模型、数据模式以及索引 技术的基础上。其中优化正则路径表达式( r e g u l a rp a t he x p r e s s i o n ，r p e ) 的一个常用 方法是：根据x m l 数据的模式信息或提取出的模式信息将r p e 拆分成成若干个简单路径 表达式( s i m p l ep a t he x p r e s s i o n ，s p e ) 的集合，通过对s p e 的处理间接获得所需的结果。 现有查询系统中对简单路径表达式通常采用的有三种查询策略：自顶向下查询 ( t o p d o w n ) 、自底向上查询( b o t t o m - u p ) 和混合策略查询。q l i 和c h u n gc 等在查询x m l 数 据过程中，根据各自研究的索引结构采用路径连接算法对简单路径表达式进行处理 【2 8 1 【2 9 1 。d i e s t e rs c h e f f n e r 提出了两种针对路径表达式的优化策略：路径精简和外延路径策 略，借此提高x m l 路径处理效率【3 0 1 。 5 、x m l 数据存储技术 x m l 数据的存储方式主要有三种：文件系统存储、关系数据库存储和n a t i v ex m l 数据库存储。x m l 数据的存储方式对查询系统的实现、索引的性能和检索的快慢等都 有着直接的影响。文件存储是将x m l 文档整个文件进行存储的方式，单纯的文件系统 缺少并发性，也没有安全机制，系统的性能较差，因此一般不采用这种存储方式。而用 关系数据库存储x m l 数据就需要先将x m l 文档映射到关系数据库中，这主要是进行 模型映射( m o d e lm a p p i n g ) 和结构映射( s t r u c t u r em a p p i n g ) 。使用关系数据库存储可 以利用现有的关系数据库的成熟技术对数据进行存储和管理，但是因为x m l 数据是半 结构化数据，在转换过程中会导致一些数据的丢失而且x m l 文档结构的多变形也不利 于关系数据库的存储。n a t i v e x m l 数据库( 简称n x d ) 是专门针对x m l 数据的存储， 因n x d 技术发展时间相对传统数据库来说还很短，技术基础还不是很牢固。但是n x d 在对x m l 数据的存储管理，索引管理，查询更新方面也有自己的优点。n a t i v e x m l 数 据库的研究也越来越受到研究人员的重视。 7 第二章x m l 索引技术的相关研究 2 2x m l 简介 x m l ( e x t e n d e d m a r k u pl a n g u a g e ，可扩展标记语言) 是w 3 c ( w o r l dw i d ew e b c o n s o r t i u m ) 在1 9 9 8 年发布的的一项用于网上数据交换的标准【3 l 】。可以说x m l 和h t m l “师出同门，都是从通用标记语言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 ，通 用标记语言) 【3 2 1 延伸出的标记语言。x m l 是s g m l 的- - 个子集，也是一种元语言，它定 义了自己的语义标记规则，用户利用这些规则可以定义自己的标记来描述文档的结构。 与同门所处的h t m l 相比，x m l 具备其所不具备的数据描述的性质。x m l 所既有的具有 的特点如下： l 、语言自描述性。通过定义自己的标签，x m l 将对数据包含的语义和数据内容都 隐含到删l 文档的结构中，使文档的结构可以为用户提供一定的语义信息。 2 、x m l 数据的可扩展性。x m l 的第一个特点就是“x ，即可扩展性( e x t e n s i b l e ) 。 h t m l 中的标记都是固定的，是用该语言必须遵循其所规定的限制，而x m l 没有规定具 体格式，允许自定义标记和属性，并根据需要制定各种数据格式。x m l 所具有的嵌套结 构不仅可以描述各种复杂的对象，还可以根据不同领域的需要将格式不同的数据容易地 转化为x m l 数据，而且这些数据可以拥有不同的格式。x m l 这种开放性、可扩展性的 特点非常适于w e b 信息的发布。 3 、自定义的文档结构和语义。x m l 作为元语言可以对文档的结构进行定义，使文 档结构包含一些信息，这些信息可以是对文档内容的描述。通过分析这些用户白定义的 标记可以帮助用户了解数据的语义，以便更好的理解并处理数据。 4 、简单方便易于使用。x m l 与s g m l 相比，具有简单方便，便于用户掌握的特点。 其自我描述的性质使得对x m l 文档的解析更容易。对于一个x m l 文档可以有多种解析、 过滤、重构的方法。 5 、数据与显示方式分离。x m l 相对于h t m l 的一个不同是：h t m l 注重的是数据 的显示方式，而x m l 更关心的是数据本身所具有的语义。它实现了内容结构和表现形式 二者的分离。结构通过文档类型定义( d t d ) 来定义。d t d 描述了文档中元素和子元素间 的嵌套结构，决定了一个x m l 文档可以包含什么元素，元素之间的结构是怎样的等等。 数据的现实通过x s l 实现，不同的用户即使使用相同的数据也可以通过x s l 按不同的显 示方式显示全部或部分的数据内容，因此在相同的的x m l 数据上可以定义多种显示形 式，实现数据与显示的分离。 8 中国石油大学( 华东) 硕士学位论文 以上x m l 的这些特性使得它在很短的时间内成为了现在网上数据进行转换的通用 标准。随着x m l 的广泛使用，其正慢慢的成为一种数据表示的。正式基于这种趋势，与 x m l 相关的一些标准也逐渐的被提出。自1 9 9 8 年推出x m l 的基本标准版本1 0 以来，又 陆续推出了一些相关的标准。这些标准包括x l i n k ：主要作用是描述在x m l 数据文档 中引入超级链接的标准；x p o i n t e r ：可以实现对x m l 数据中指定部分进行确定的标准； x s l ( e x t e n s i b l es t y l e s h e e tl a n g u a g e 扩展样式表语言) ：对x m l 数据显示样式进行定义的 标准；d o m ( d o c u m e n to b j e c tm o d u l e 文档对象模型) ：提供应用程序对x m l 文档进行处 理所需的对象和相应借口的定义标准；x m ln a m e s p a c e s ：提供一种统一命名x m l 文档 中的元素和属性的机制，避免来自不同标记词汇表的元素和属性之间冲突；x m l s c h e m a s ：用于定义和描述x m l 文档结构和内容模式，定义元素和元素之间的关系，定 义元素和属性的数据类型；x q u e r y ：用于描述对x m l 数据源查询的语言等等，其中如 x q u e r y 还在定义过程中。 由此也反映了工业界对x m l 的巨大支持。越来越多的w e b 应用，如电子商务，数字 图书馆，信息服务等采用x m l 作为数据表现形式，也有很多的网站采用x m l 作为信息 发布的形式，可以预见到将有越来越多的x m l 数据出现在i n t e m e t 上。 x m l 语言所具有的优秀特性使得其具有广泛的应用。自订l 1 0 推出以来，x m l 在 各个领域得到应用，特别是在电子商务领域更是得到充分应用。x m l 的实际应用有数据 交换，w e bs e r v i c e ，电子商务，配置文件。 2 3x m l 索引的分类 在传统数据库中，索引的使用可以提高数据的检索速度，优化系统性能。面对日益 庞大的x m l 数据，如何更好的对其进行管理和查询成为人们研究的重点。在借鉴传统数 据库的基础上，研究人员想到了利用索引的方法对x m l 数据进行处理。通过几年的努力， 一些索引的方法被提了出来，这些索引技术主要可分为值索引、字符串索引、路径索引 和节点索引。 然而传统的索引技术经过长期的研究积累已经相对成熟，这类索引技术针对的主要 是关键字和值的索引，它并不考虑元素之间的结构和逻辑关系。这种索引技术并不适用 于半结构化的x m l 数据，x m l 数据中各元素之间的结构关系本身包含一定的语义信息， 使用传统的索引技术将忽略这些信息，使得x m l 数据所表达的信息不完整。因此传统的 索引技术可以借鉴，但不宜直接应用到订l 数据上。经过研究人员的努力，一些适用于 9 第二章x m l 索引技术的相关研究 x m l 数据的索引技术被提了出来。例如：d a t a g u i d e s 、t i n d e x e s 、r e v e r s e dd a t a g u i d e s 、 l o r e 索引、i n d e xf a b r i c 、t o x i n 和x i s s 等等。 而现有的这些索引方法主要分为两类，即基于路径的索引和基于节点的索引。 2 3 1 基于路径的l 索引 基于路径的索引主要使用节点聚类的方法，以x m l 数据的树形结构为基础，对树结 构中等价的节点和等价的路径进行简化，得到比原始文档小的多的摘要树的方法，使得 获得的摘要树结构只保存原树中不同路径的信息。由此使得摘要树中不存在具有完全相 同路径的两个节点。摘要树仍然是树形结构，因此使用该技术处理查询是，仍需对整个 索引树进行遍历才能获得所需的结果。该索引技术可以很好的支持简单路径表达式的查 询，但对于复杂路径效果不佳。利用该方法的索引有：d a t a g u i d e s 索引、i n d e xf a b r i c 索 引、x m l 数据的自适应路径索弓i ( a d a p t i v ep a t hi n d e xf o rx m ld a t a ，a p e x1 【7 j 。 d a t a g u i d e s 索引是通过对原树结构进行简约路径获得的一种结构摘要。通过简约使 得获得的结构摘要中的标记在d a t a g u i d e s d p 只描述一次。d a t a g u i d e s 对原数据进行简约的 方法是通过将非确定有限自动机( n 1 1 a ) 转