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

摘要 具有优良特性的x m l 逐渐成为了网络信息交换的载体，越来越多的数据采用x c t l 格 式存储和交换，而传统的查询技术不再适应新的应用，x m l 索引及查询方法的研究就显 得更加迫切。 论文对与索引查询技术相关的编码、查询、索引等技术进行了深入研究和分析，指 出了现有编码、索引技术的优缺点，同时给出了优秀索引、编码模式的标准。由于现有 的索引多数都是通过路径表达式来表达和实现x m l 的结构查询，而这种方法最核心的技 术之一就是：利用索引编码方法有效地判断x m l 文档中的元素或属性间的祖先后代关 系、父子关系、左右兄弟等位置关系，只有有效判断出任意节点间的结构关系，才能避 免对整棵文档树的遍历，从而提高结构连接效率。本文提出了两种新的编码模式，其中 一种是通过引入了虚拟节点建立的区间编码模式，该模式首先给树的叶子节点处添加 编好序号的虚拟逻辑叶子节点，然后利用这些编号给该虚拟叶子节点的祖先节点赋予区 间编码。分析证明这种编码模式可通过节点间的区间包含关系有效地判断出祖先后裔 关系、父子关系，并提高了编码更新效率。 为了能够提供更多有效判断节点间的位置关系的结构信息，我们又提出了p s b 一- 基 于素数和序列串的编码模式，它充分利用素数的整除特性和序列串匹配技术，只需要对 文档树进行一次前序遍历就可以完成所有编码并且可以在常数复杂度的时间内实现节 点之间祖先后裔、父子、层次、兄弟关系的判断；该编码较好地支持文档的各种更新。 采用标准的s h a r k s 数据对编码更新有效性进行性能评估，与以d i e t z 编码机制为代表的 区间编码机制编码更新率进行了对比。当x m l 文档树中插入或者删除节点时，p s b 编 码机制需要重新编码的节点数目相对较小。因此，p s b 编码是支持更新的动态编码。 编码模式反映了元素在树结构中的位置关系，而路径索引描述了源数据的路径结构 信息。我们传统的x m l 路径表达式查询处理方法中：一种实现方法是建立x m l 文档的路 径索引，通过路径索引来加速x m l 路径表达式查询的计算；另一种方法是对x m l 文档树 中的节点进行编码，将x m l 路径表达式的计算转化为结构连接的计算。本文提出将路径 索引与编码模式相结合的索引查询方法，具体方法原理就是利用已有文档模式信息或者 从现有文档中抽取d t d 模式信息的方法，然后对获取的模式信息再利用简化d t d 的规则 进行简化，获取较小的模式结构充当文档的路径索引。之后，我们利用新提出的虚拟节 点建立的区间编码模式对简化模式和x m l 文档树进行编码。在对x m l 文档索引结构进行 查询时，首先在此简化d t d 模式上进行查询路径表达式合法性验证，对合法的查询才继 续到x m l 索引中进行查询，否则及时给出查询非法的提示并终止查询。由于这种索引查 询方案既能够将非法查询控制在规模较小的简化d t d 查询阶段，又把路径索引与编码模 式相结合，能够取得较高的效率。通过实验与s p i n x 索引进行查询效率比较，虽然我们 的索引在建立简化d t d 、编码、索引时花费的代价略高，但在索引规模的不断增大非法 查询表达式随之增加的情况下具有较高的查询效率。 关键词：x m l ，编码模式，索引，查询 ar e s e a r c ho nx m l q u e r y i n gb a s e do ni n d e x z o n gd e j 吼( c o m p u t e ra p p l i c a t i o nt 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 ep r o f w e id o n g p i n g a b s t r a c t a sat o o lo fo n l i n ed a t ae x c h a n g e ，x m lh a sm a n ye x c e l l e n tc h a r a c t e r i s t i c s m o r ea n d m o r ed a t ai ss t o r e da n de x c h a n g e di nt h ef o r mo fx m l o nt h eo t h e rh a n d ，t r a d i t i o n a ld a t a b a s e t e c h n o l o g i e sc a r l tw o r ke f f i c i e n t l yo w i n g t ot h en e wa p p l i c a t i o n s o ，n e wi n d e x i n ga n dq u e r y t e c h n o l o g i e ss p e c i a l l yd e s i g n e df o rx m l d a t aa r en e e d e dt oc a u s eo u ra t t e n t i o n o nt h eb a s i so ft h ed e 印s t u d ya n dc o m p a r i s o no ft h ex m lc o d i n gs c h e m a , q u e r y t e c h n o l o g i e s ，i n d e x i n gt e c h n o l o g i e s ，w ep r o p o s e dt h ea d v a n t a g e sa n dd i s a d v a n t a g e so fe x i s t i n g t e c h n o l o g i e sa b o u tq u e r i n ga n di n d e x i n g ，a n da tt h es a m et i m ew ea l s og i v eas t a n d a r da b o u t g o o di n d e xa n dc o d i n gs c h e m a m o s te x i s t i n gi n d e x sc a ne x p r e s sa n dr e a l i z et h ex m l s t r u c t u r e - q u e r i n gt h r o u g ht h ep a t h e x p r e s s i o n o n eo ft h ec o r et e c h n o l o g i e si s ：m a k ef u l lu s e o ft h ec o d i n gs c h e m at oe f f e c t i v e l y j u d g e t h e r e l a t i o n s h i p b e t w e e nt w o a r b i t r a r y n o d e so fx m ld o c u m e n t s ，s u c ha s a n c e s t o r d e s c e n d a n t 、f a t h e r s o n 、p r e c e d i n g - s i b l i n g f o l l o w i n g s i b l i n g 、l e v e lr e l a t i o n s h i p s ，e t c o n l yd e t e r m i n i n gt h es t r u c t u r eo fi n t e r - r e l a t i o n se f f e c t i v e l y ，c a l lw ea v o i dt h et r a v e r s a lo fa l l t r e ea n di m p r o v et h ee f f i c i e n c yo ft h es t r u c t u r a lj o i na l g o r i t h m s i nt h i sp a p e rw ep r e s e n t e d t w on e wc o d i n gs c h e m a s ，t h ef i r s ti sak i n do fr e g i o n a lc o d i n gs c h e m ab yi n t r o d u c i n gv i r t u a l n o d e sa tt h el o c a t i o no nt h et r e el e a v e s b ya d d i n gt h ei dn u m b e ro nt h ev i r t u a ll o g i c a ll e a f n o d e s ，w eg e ta n c e s t o rn o d e s r e g i o n a lc o d e s a n a l y s i ss h o w e dt h a tt h i sc o d i n gs c h e m ac a n d e t e r m i n et h ea n c e s t o r d e s c e n d a n t 、f a t h e r s o n 、l e v e ll o c a t i o n r e l a t i o n s h i p se f f e c t i v e l y b e t w e e nt w oa r b i t r a r yn o d e so fx m ld o c u m e n t s ，a n da v o i dc o d i n gu p d a t ee f f e c t i v e l y i no r d e rt ob ea b l et op r o v i d em o r ee f f e c t i v es t r u c t u r a li n f o r m a t i o nt od e t e r m i n e r e l a t i o n s h i p sb e t w e e na n yt w on o d e s ， w ep r o p o s e da n o t h e rc o d i n gs c h e m aw h i c hi sb a s e do n p r i m en u m b e r sa n dt h es e q u e n c ee n c o d i n gs t r i n gm o d e t h en e wc o d i n gs c h e m am a k ef u l lu s e o ft h ed i v i s i b l ef e a t u r e so fp r i m en u m b e r sa n dm a t c h i n gt e c h n i q u e so fs e q u e n c es t r i n g i tc a n f i n i s ha l lt h e c o d i n g w o r k sa tc o n s t a n tt i m e ，w h i c hc a l ld e t e r m i n ea l lk i n d s l o c a t i o n - r e l a t i o n s h i p st h r o u g ho n et r i pp r e - o r d e rt r a v e r s a lo nt h ex m l d o c u m e n tt r e e t h e l a s tb u tn o tt h el e a s t ，t h i sc o d i n gs c h e m as u p p o r ta l lk i n d so fc o d i n gu p d a t e s ，a n dt h en u m b e ro f a f f e c t e dn o d e si sv e r ys m a l la f t e ri n s e r t i n go rd e l e t i n gn o d e s w eu s et h es t a n d a r ds h a r k sd a t a t oe v a l u a tt h ee f f i c i e n c yo fc o d i n gu p d a t eb yc o m p a r i n gp s be n c o d i n gs c h e m aa n dd i e t z s c h e m aw h i c hr e p r e s e n tr e g i o n a le n c o d i n gs c h e m a s t h ea f f e c t e dn o d e so fp s bs c h e m ai s l e s st h a nt h a to fd i e t zs c h e m aa f t e ri n s e r t i n go rd e l e t i n gn o d e s t h e r e f o r e ，p s bc o d i n gs c h e m a i sa d y n a m i cc o d i n gs c h e m aw h i c hs u p p o r t t i n gd o c u m e n t s c o d i n gu p d a t i n g c o d i n gs c h e m ar e f l e c t sa l lo b j e c t s l o c a t i o n - r e l a t i o n s h i p si nt h ex m lt r e es t r u c t u r e ，b u t t h ep a t hi n d e xd e s c r i b e st h ep a t hs t r u c t u r ei n f o r m a t i o no fs o u r c ed a t a t h et r a d i t i o n a lx m l q u e r ym e t h o do fp a t he x p r e s s i o np r o c e s s i n gi s ：t h ef h s ti m p l e m e n t a t i o nm e t h o di st os p e e du p t h ee f f i c i e n c yo fx m l p a t he x p r e s s i o nq u e r yc a l c u l a t i o nb ys e t t i n gu pt h ep a t hi n d e xo fx m l d o c u m e n t s ；a n o t h e rm e t h o di st oe n c o d et h ex m ld o c u m e n tt r e en o d e ，a n dc o n v e r tt h e c a l c u l a t i o no fx m l p a t he x p r e s s i o ni n t ot h es t r u c t u r e - c o n n e c t e dc o m p u t i n g i no r d e rt o i m p r o v et h ee f f i c i e n c yo fq u e f i n ga n du p d a t i n g ，w ec o m b i n et h et w om e t h o d s ：p a t hi n d e xa n d c o d i n gs c h e m a t h es p e c i f i ci m p l e m e n t a t i o np l a ni st h a tw ed on o tu s et r a d i t i o n a lm e t h o dt o e x t r a c tp a t hi n d e xi n f o r m a t i o nf r o mx m l d o c u m e n t s ，b u to n l yt a k ea d v a n t a g eo fa v a i l a b l e d t di n f o r m a t i o n so rs i m p l em e t h o dt oe x t r a c tc h i e fp a t hi n f o r m a t i o n 、析t hd t d s i m p l i f i e d r u l e s i nt h i sw a y ，w eg e tas m a l l e ri n d e xs t r u c t u r ew h i c hc a nb et a k ea st h ep a t hi n d e xo ft h e d o c u m e n t t h en e x ts t e p ，w ee n c o d ex m ld o c u m e n tt r e ea n dt h es i m p l ed t di n d e xs t r u c t u r e 、析t 1 1t h en e wc o d i n gs c h e m a - - - v i r t u a ln o d e sr e g i o n a lc o d i n gs c h e m a b e f o r ew eq u e f i n gi n d e x s t r u c t u r eo fx m l d o c u m e n t s ，w ee x e c u t et h eq u e r yi ns i m p l i f i e dd t ds c h e m a t h r o u g ht h i s s t e p ，w ec a l ld e t e r m i n et h el e g a l i t yo ft h ep a t he x p r e s s i o nq u e r y t h e n ，o n l yt h el e g i t i m a t e i n q u i r i e sc a nc o n t i n u et oe x e c u t en e x tx m li n d e xq u e r y ，o t h e r w i s e ，w et e r m i n a t et h ei n q u i r y i nat i m e l ya n dg i v ei l l e g a lq u e r yt i p s b e c a u s et h i si n d e xp r o g r a mc a nc o n t r o li l l e g a li n q u i r i e s a tas m a l l e rs c a l e s i m p l i f yt h ed t d i n q u i r ys t a g e ，a n dt a k ea d v a n t a g eo ft h em e r i t so ft w o m e t h o d s ：t h ep a t h i n d e x i n ga n dc o d i n gs c h e m a , s ot h i sp r o g r a mc a na c h i e v eah i g h e r e f f i c i e n c y w ec o m p a r et h eq u e r ye f f i c i e n c yb e t w e e ns p i n xa n do u rs c h e m a t h r o u g h e x p e r i m e n t s ，w ec a ns e et h a to u rp r o g r a m sc o s ti ss l i g h t l yh i g h e rt h a ns p i n xi ne n c o d i n g ， i n d e x i n gs t a g e ，b u tw ec a ng e tai d e a le f f i c i e n c ya c c o m p a n i e db yt h ei n c r e a s ei nt h es i z eo f q u e r yd a t a k e yw o r d s ：x m l ，c o d i n gs c h e m a ，i n d e x ，q u e r y 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：基暨瞳透日期：卫a 7 年5 月2 0 日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印 刷版和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机 构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、 借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、 缩印或其他复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：盛噩日期：m 年s 肋日 指导教师签名： 日期：砌年占月z o h 中国石油大学( 华东) 硕士学位论文 第一章绪论弟一早三；百下匕 1 1 研究背景和意义 随着i n t e m e t 的迅速发展，互联网作为信息传播的媒体，极大地方便和更新着人类 的生活、生产方式，并且必将继续对人类社会的进步起到不可替代的推动作用。但是面 对w e b 不断蔓延所带来的庞大信息数据海洋，虽然我们能够非常方便地获得各种各样 丰富的信息，但是想要找到真正所需要的信息变得越来越困难。这是因为随着x m l 数 据的大量涌现，这种具有可扩展性和自描述性的高效信息载体，正在逐渐进入人们的视 野，它在电子商务、网站管理、个性化出版、电子文档交换等各个领域得到了广泛地应 用，而我们以往用来索引、查询、处理这些数据的技术相对落后，所以研究针对x m l 数据库的高效查询技术就变得日趋紧迫。 x m l i l 】( e x t e n d e dm a r k u pl a n g u a g e ) 是19 9 8 年w 3 c 组织制定的一项网上数据交 换国际标准。它是通用标记语言s g m l ( i s o8 8 7 9 ) 的一个优化、核心子集，作为一种元 标记语言，用户可以定义自己的标记，用于描述文档的结构。与最普遍的数据表现形式 h t m l 相比，x m l 具有一些显著的特性 4 2 1 ： ( 1 ) 能够存储结构和语义信息。x m l 侧重于对文档内容的描述，而不单单是对文 档结构的描述。用户自定义的标记描述了数据的语义，便于对数据的理解和机器的自动 处理，这正是x m l 易用性的重要表现。 ( 2 ) 可扩展性。x m l 中的标记不像h t m l 那样是事先定义好的、不容更改的， x m l 允许用户定义自己独有的个性标记和属性，可以有各种定制的数据格式，这样各 个行业就可以自定义灵活多变的行业内标准。 ( 3 ) 简单易用。与通用标记语言s g m l 相比，x m l 简单易用，它是s g m l 最最 常用的核心功能集合，所以相比较而言x m l 更加便于理解、学习和掌握，这也是它能 够得以推广和应用的重要原因之一。 ( 4 ) 自描述性。x m l 将对数据语义和数据内容本身的描述都包含在x m l 文档中， 使数据具有很大的灵活性。x m l 表示数据的方式真正做到了独立于应用系统，并且数 据能够重用，x m l 文档被看作是文档的数据库化和数据的文档化。 ( 5 ) 数据内容与显示格式分离。x m l 所关心的是数据本身的语义，而不再是数据 的显示方式。将数据与显示分离后，用户可以在同样的x m l 数据上定义多种独立的显 示方式，可以让一份数据对应多种自定义格式。 x m l 的这些优点不但使得它迅速成为了网络数据交换的事实标准，而且正在逐渐 第一章绪论 成为数据的表示标准。随着x m l 的流行，一系列相关的标准( 如x m ls c h e m a t 2 1 ， x q u e r y 3 1 ，x m ld a t am o d e l 【4 】【5 1 等) 也不断出现，越来越多的w ，e b 应用，如电子商务网 站，信息服务等都采用了x m l 作为其数据表现形式，甚至很多的网站采用x m l 作为 信息发布的形式，各个大型传统数据库也增加了对x m l 的支持，可以预见x m l 必将 会获得更大的应用和普及。随着大量x m l 文档的出现，w e b 上的各类信息必将通过x m l 文档进行存储、交换。因此，如何高效、准确地查询这些x m l 数据，就成为一个值得 研究的重要课题，而如何充分利用索引查询来是提高查询效率自然成为了重中之重。 1 2 国内外研究现状 由于越来越多的结构化或半结构化w e b 数据采用x m l 格式进行存储和表示，x m l 数据的查询变得日益重要和迫切。w 3 c 为此专门成立了x m l 查询工作组( x m lq u e r y w o r k i n gc r o u p ) ，专门负责制定有关x m l 查询的数据模型、查询语言等方面的规范。 可以说x m l 数据格式、x m l 数据库等各个与x m l 相关的各个方面正在受到更大的重 视。 从传统数据库角度来看，一个x m l 文档就相当于一个简单的概念数据库，而它对 应的d t d t l 】或者x m ls c h e m a 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 数据库尤其是纯x m l 数据库来说，如何设计相 应的索引结构来提高查询的效率和检索信息的准确率意义重大而又非常迫切。 近些年，基于x m l 半结构数据的索引的研究主要集中于文档的数据结构表示、索 引数据结构和检索算法的改良、索引存储空间的压缩、索引编码方案、结构连接算法以 及索引结构和索引编码的更新。其中值得注意的是文档数据的表示和索引的结构不同， 对检索的算法影响也较大。常见的索引的结构主要有倒排文件( i n v e r tf i l e ) 6 1 1 7 1 、t r i e ( 带标 记的树状索引) 、p a t f i c i at r i e ( 带字符串压缩的t i l e ) 引、后缀树( s u f f i xt r e e ) 1 9 1 。对关键码 范围进行均分的结构，这种数据结构，叫做t r i e 结构，t i l e 结构主要基于两个部分：有 2 中国石油大学( 华东) 硕士学位论文 一个固定的关键码集合和对于节点的分层标记。其内部节点仅作为占位符引导检索过 程，数据记录只存储在叶节点中。 图1 - 1t r i e 结构图 f i g l - 1 t r i ec h a r t p a t r i e i at r i e 是一种比较好的中文字典组织方式，它不是对关键码大小范围的划分， 而是根据关键码每一个二进制的编码来划分，因为每一位要么是0 ，要么是l ，所以分 支因子是2 ，每个内部节点都代表一个位的比较，必然产生两个子节点，所以他是一棵 满二叉树。 图1 - 2p a t r i c i at r i e 结构图 f i g l - 2 p a t r i c i at r i ec h a r t 早期x m l 数据库的数据查询多数是通过路径遍历来实现的。在半结构化数据查询 系统中，建立路径索引是提高查询效率的一种重要手段。其中，d a t a g u i d e s 1 0 】是一种有 效的全面描述文档结构的路径索引，在很多情况下可以提高数据访问效率。为了减少建 立和维护路径索引的代价，更有效地利用路径索引的功能，分步建立和更新路径索引的 办法【l l 】采取了分步骤建立路径索引的方法，当建立路径索引的复杂度较大时，仅根据需 要为源数据中部分关键路径建立索引。针对结构化文档索引的一般模式，可以以词为单 位建立基于位置的索引算法和基于路径的索引算法f 1 2 】。基于元素编码的索引1 3 1 ，使用 b + 树跳过了部分无关元素提高了查询效率，并且通过进一步引入新的内容树结构提高查 询速度。x i s s 1 4 索引兼备路径记录和结构索引、树节点编码两个特点。另外，它还对调 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 查询的具体分类【”】包括： ( 1 ) 对元素值( 内容) 的查询，即通过限定元素内容或属性的值来进行查询，称 为值查询。 ( 2 ) 通过表达的文档中元素之间的结构关系的路径表达式进行查询，称为结构查 询。元素之间的结构关系包括：祖先后裔( a n c e s t o r d e s c e n d e n t ) 关系、双亲孩子 ( p a r e n t c h i l d ) 关系、之前之后( p r e c e d i n g f o l l o w i n g ) 关系、左兄弟右兄弟( p r e c e d i n g - s i b l i n g f o l l o w i n g s i b l i n g ) 关系等。其中，祖先后裔、双亲孩子关系统称为包含关系，之前之后 关系、左兄弟右兄弟关系统称为文档位置关系。利用路径表达式，用户能够导航x m l 文档树中的任意长度的路径。但是，一个单一路径的查询，如b o o k a u t h o r 或 s e c t i o n f i g u r e ，将被分解为查找b o o k 元素的孩子a u t h o r 元素或s e c t i o n 元素的后裔f i g u r e 元素。因此，这种x m l 文档的结构查询将导致大量的结构连接( s t r u c t u r a l j o i n ) 操作。 为了有效地实现结构查询，我们需要重点实现以下两点： ( 1 ) 快速准确地确定出x m l 文档树中任意两个节点之间的结构关系种类； ( 2 ) 高效地确定某元素在给定的结构关系下在x m l 文档中发生的所有情况。 比如：我们需要能够找出x m l 文档中满足双亲孩子关系的所有满足父子或祖先 后裔关系的所有t e a c h e r s t u d e n t 元素对。对于t e a c h e r 元素中包含的所有孩子元素s t u d e n t 的查询，一个传统但效率不高的方法就是导航式遍历x m l 文档树，找到t e a c h e r 元素节 点的所有子树中含有s t u d e n t 元素的分支，这是一种代价很高的自顶向下导航方法。当 x m l 文档比较大，或者查询的路径表达式根本不合法时，对表达式的查询就类似于对 整棵树进行遍历，效率可想而知，可是如果我们将一种编码方案嵌入到x m l 文档树中， 4 中国石油大学( 华东) 硕士学位论文 则x m l 文档树中任意两个节点对之间的结构关系就能够被快速地判断出来。正是出于 这种考虑，很多研究者有提出了许多x m l 数据索引和编码方案。 有代表性的x m l 文档索引技术中，d a t a g u i d e s 1 0 】是将n f a 转换为d f a 的形式，对 x m l 文档书中的相同路径进行约简，由x m l 文档树根节点开始的简化路径的一种结构 性摘要。所以，它不再需要具备d t d 或者s c h e m a ，而是直接从文档中提取结构信息。 但是如果x m l 数据图是图结构或者说是树结构中带有回路的话，那么建立d a t a g u i d e 所需要的时间和空间就有可能是x m l 数据大小的指数倍，建立索引时间长，索引占空 间大，特别当x m l 文档复杂时尤其如此；另外，d a t a g u i d e 中各个节点的扩展集可能 存在相交的情况。文档树的边的标签组成的串表示字符路径，字符路径在d a t a g u i d e s 中 只需要被描述和存储一次。d a t a g u i d e s 减少了查询时遍历路径所需要的许多节点，但是 它的缺点是只对从根节点开始的遍历是有效的，不能使用于一般的从任意节点为开始的 查询，查询效率不是很高，查询方式也比较单一。例如，图1 3 中x m l 数据图它所对 应的d a t a g u i d e 索引如图l - 4 所示。 图1 - 3x m l 数据图 f i g l - 3 x m ld a t ac h a r t 图1 - 4d a t a g u i d e 图 f i g l - 4d a t a g u i d ec h a r t 1 - i n d e x 1 6 1 引入了双模拟性呖s i m u l a t i o r l ) 原理，减少了索引空间的大小，提高了查询 效率，其弱点在于通用性不是很强。它为了弥补d a t a g u i d e 的不足，提出两节点“相似 的概念，其含义是：若节点u ，v 具有相同的标签且节点u 是u 的父节点，节点v 是 5 第一章绪论 v 的父节点，则节点u 与v 相似。这种索引，索引的大小和x m l 数据图大小成线性 关系；索引的扩展集之间不相交，所有扩展集的节点总数和x m l 数据图中节点总数相 等。不能提供任意两个节点的父子关系的判断，也不能从任意节点开始进行向下的路径 查询，仅支持简单路径查询，不适于几个正则表达式的组合路径查询和分支路径查询。 1 - i n d e x 索引中将“相似”的节点存放在一个扩展集中，例如，图1 5 就是前面x m l 数 据图对应的1 - i n d e x 索引图。 图1 - 51 - i n d e x 图 f i g l - 5 1 - i n d e xc h a r t l o r e 1 7 1 索引是基于一种对象交换模型o e m ( o b j e c te x c h a n g em o d e l ) 的图状模型。 l o r e 索引由四个部分组成：值索引、链接索引、文本索引、路径索引。值索引用于查找 满足查询条件的所有原子对象；链接索引用于查找已知节点的双亲节点，因为l o r e 本 身没有提供访问双亲节点的机制；文本索引用于支持复杂的文本查询，找到包含特定词 的对象以及该词在文本中的位置；路径索引返回通过路径能到达的所有对象，它是和 d a t a g u i d e s 配合使用的。 i n d e xf a b r i c 索引【1 8 1 是基于p a t r i c i at r i e 树的一种半结构化数据索引结构，其基本思 想是将半结构化数据之间的关系表示成路径，然后将路径编码成字符串，最后在字符串 上面建立索引。并根据用户经常涉及到的查询，提供对常用简化路径的快速路径查询： 但在处理带“的路径查询时，例如s c h o o l s t u d e n t 表示查找所有具有祖先s c h o o l 的 s t u d e n t ，i n d e xf a b r i c 显得效率不高，这一问题的根源就在于i n d e xf a b r i c 的编码方法的 缺陷。 d ( k ) 在1 - i n d e x 1 6 1 和a ( k ) 【2 0 1 的基础上，d ( k ) 吸收了a p e x 中动态反映查询分布的 优点，a ( k ) 索引中每个索引节点的相似度都为k ；d ( k ) 索引是对频繁使用的路径进行索 引，而频繁使用的路径长度往往是不相同的，因此d ( k ) 索引中的每个节点的局部相似度 k 也不相同。d ( k ) 索引每个索引节点与一个局部相似度k 有关，给定一个索引节点的局 部相似度k ，它的父节点的局部相似度至少为k - 1 。 6 中国石油大学( 华东) 硕士学位论文 a p e x 索引【2 1 1 是一种基于工作流的索引结构，运用数据挖掘的方法利用常用的查询 数据来建立索引，将经常出现的x m l 查询语句对应的标签节点预先保存在一个哈希结构 中。首先在哈希表中搜索是否有满足的节点。它实质上是d a t a g u i d e 索引的一种近似， 该算法并不保存所有路径索引，而是利用频繁使用的路径建立索引来提高查询效率。它 能够有效地处理某些相对路径查询，它创建的索引是基于查询频度，对频繁使用路径创 建索引。当查询频度有变化时，a p e x 索引可以进行有效地更新以适应查询频度的变化， 具备了索引的动态性，但它对于带有元素值或属性值的查询表达式的处理效率较低。 x i s s 1 4 】把元素、属性作为查询的基本单元，其主要索引结构有结构索引、元素索引 和属性索引，其主要思想是将复杂路径分解为简单路径，然后对各个简单路径的处理结果 进行连接，它分别对x m l 文档树以前、后序遍历进行编码。将复杂的路径查询分解为 单独的简单路径，然后对各个简单的单独路径查询处理结果进行连接操作。x i s s 对路 径查询处理时，无需遍历x m l 文档树。但是，首先，如果查询路径由n 个元素属性组 成，x i s s 需要从索引中检索出n 组节点；其次，对于由n 个元素属性组成的查询路径， 处理每个x m l 文档至少需要( n 1 ) 次结构连接算法的调用：这样就不可避免的会有许多 不相关结构中的节点，参与简单路径处理过程中双亲孩子关系或祖先后裔关系的判断， 比如：路径s c h o o f n a m e 中没有s d u d e n t 元素，但是该路径中n a m e 节点会参与s d u d e n t n a m 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 索引查询方法能够有效的 解决分支路径查询。那么我们能否将两种x ，查询方法中的优点结合起来，有效提高 对x m l 文档的查询效率呢? 1 3 论文的主要工作和创新 论文对y d v i l 存储、索引编码方案、查询技术、索引技术等进行了深入研究和分析， 指出了现有的常用编码方案、索引方法的优缺点，提出了两种新的编码模式，一种是引 7 第一章绪论 入了虚拟节点的区间编码模式，该模式首先给树的叶子节点处添加新的虚拟叶子节点， 并给该虚拟节点编号，然后利用这些编号给每个文档树节点赋予新的区间编码。另一种 是基于素数和序列的编码模式，它是我们利用素数的整除特性和序列串匹配技术，提出 的一种新编码模式。该编码模式可以在常数复杂度的时间内实现节点之间祖先后裔关 系、层次关系、兄弟关系的判断，并且很好的支持文档的各种更新。 在利用简化d t d 的基础上，使用虚拟节点的区间编码模式，我们提出了一种新的 索引方法，该索引方案充分利用了简化d t d 提供的路径有效性信息，所有路径查询表 达式首先要先在规模较小的简化d t d 的索引上进行有效性判断，只有合法的路径表达 式才可以在x m l 文档树中作进一步查询，有效地提高了查询反应效率。 1 4 论文组织 论文共分五章。第一章介绍了x m l 数据的特点、x m l 查询的具体分类、索引查询 研究的国内外现状、研究背景和意义，最后提出了论文的主要工作和创新点。 第二章x m l 索引技术的相关研究，对x m l 数据库的存储分类、路径查询处理技 术、x m l 编码方案、常