（计算机应用技术专业论文）一种基于文本节点的xml文档索引和查询方法.pdf

承诺书 本人郑重声明：所呈交的学位论文， 是在导师指导下独立完成的，学位论文的 知识产权属于山西大学。如果今后以其他 单位名义发表与在读期间学位论文相关的 内容，将承担法律责任。除文中已经注明 引用的文献资料外，本学位论文不包括任 何其他个人或集体已经发表或撰写过的成 果。 学位论文作者r 签章j ：饼 2 0 0 5 年月韶日 、 摘要 x m l 作为一种扩展标记语言以其独有的特点及优势，使得开展 i n t e m e t 上的深层应用成为町能，它将逐步取代h t m l ，并成为i n t e m e t e 数据表示及数据交换格式的新标准。如今，越来越多的数据被存储在 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 m l 文档，包 括没有d t d ( 文档类型定义) 文件的x m l 文档。 本文的主要工作如下： 1 ) 阐述厂x m l 的基本概念及其特性，并说明了对x m l 文档进行 奁询的理论基础。 2 ) 对国内外x m l 查渤技术进行研究，分析现有查询技术的优缺点， 找到其中影响查询效率的因素，并吸取其中的先进思想。 3 ) 引入唯一元素标识u i d 的思想，两：且说明如何利用该思想为x m l 文档建立索引。 4 ) 根据、 结构化数据的不规则、不完整的特，气，构造产一种增强的 基丁文本节点的x m l 文档索引。该索引结构仔储_ j ，i _ i i jd o m 技术【i 成的 x m l 文档树中对查询有利的关键信息，有效地得州，x m l ：r 结构化的 特于 f ：，r ，以加快x m l 奁询的速度。这利l 索引结构的特点足索引文件规 模较小，而且川以进行局部奁找。根据此索，j 技术设计了一种合适的蛮 湘算法，并划关键算法进行了形式化描述。 5 ) 设计并实现了一个x m l 赍询实验系统，描述丁系统备1 婪模块 的功能。并对增强的基j 文本节，i 囊的索r f 进行验证，给f i 7 以二测试、卜台 l 的实验结果。 6 ) 总结奉义的x m l 索引技术的优缺点，并指出今斤彳的对此x m i 索 引技术的改进方向。 关键词x m l ；文档树；文本节点索引：词频累加；倒排文什；查询处 理器 a b s t r a c t x m l ，a sae x t e n s i b l em a r k u p1 a n g u a g ew j t hp a r t i c u l a rc h a r a c t e r i s t i c s a n da d v a n t a g e s ，m a k e si tp o s s jb l et oc a n yo u td e e pa p p l i c a c i o no ni n t e m e t x m lw i l lb e c o m et h en e ws t a n d a r df b 珊a to fd a t a e x d r e s sa n dd a t a 打a n s p o t a t j o n o ni n t e n e t 主n s 把a do fh t m ls e p b ys t e pj n t h ef h t u r e n o w a d a y s ，m o r ea n dm o r ed a t aa r es t o r e di nx m l6 l e ，a n dt h e r eh a sa l r e a d v a1 a r g en u m b e ro fd a t ac 0 1 1 e c t i o n sb a s e do nx m l d o c u m e n t so ni n t e m e t t h e d a t a b a s et e c h n 0 1 0 9 yh o wt os t o r ea n dq u e r yx m ld a f ai sa n i n l p o r t a n t s u b je c tf o rr e s e a r c h b e c a u s ed a t ai nx m ld o c u m e n t sh a sc h a r a c t e r i s t i c so f n e s t e ds t r u c t u r ea n di n c o m p l e t ei n f o r m a t i o nm o d e ，w h j c hm a k e si t ss 廿u c t u r e v e r yc o m p i e x ，i ti ss od i m c u l tt od e a lw i t hx m l q u e r y t r a d i t i o n a lt r a v e r s e t e c h n o l o g i e sb a s e do nt r e es t m c t u r ec a nn o tm e e tt h ed e m a n dt od e a lw i m c o n l p l e xx m ld o c u m e n f s s oh o wt oq u e r yt h ed a t ai nx m ld o c u m e n t s q u i c k l ya n da c c u r a t e l yh a sa l r e a d yb e c o m eae x i g e n tp r o b l e mt ob es 0 1 v e d i m m i n e r 】t l y ， i nt h i sp a p e r ，w er e s e a r c ht h eq u e r ya l g o n t h m sf o rx m l d o c u m e n t s ，a n d c o n s n u c tas p e c i a li n d e xb a s e do nt e x m o d ea n da q u e r ys t r a t e g yf b r s e n l i s t l c t u r e dd o c u m e l l tl i k ex m ld o c u n l e n t w ec o n s n _ u c t t h e c o n e s p o n d i n gi n d e xs t r u c t u r ea n dr e a l i z et oq u e r yd a t ai nx m ld o c u m e n t s h j g h e 瓶c i e t l f l y t 】1 j sm e t h o dh a st h e 士0 1 1 0 w i n ga d v a n t a g e s i f si n d e x6 1 ei s s n l a i l ，c a nq u e r yx i v u d o c u m e n t sq u i c k l y ，i se a s yt or e a l i z e ，a n di ss u i t a b l e f o l a 1 1x m ld o c u r n e n t sj n c l l i d i n gx m ld o c u m e n t sw i t h o u td t dn l e s t h en l a i nw o r ko fc h i sp a p e ri sa s 内1 1 0 w s ： 1 ) x m lb a s i cc o n c e p t i o n sa n dc 1 1 a r a c t e r i s t i c sa r ee x p a t j a t e d ，a n db a s e s o fx m l q u e r yi se x p l a i n e d 2 ) d o m e s t i ca n di n t e n l a c i 0 1 1 a 1 t e c h n 0 1 0 9 i e s f 0 1 x m lq l l e r ya r e r e s e a r c h e d ，t 1 1 ed js a d v a n t a g e sa 1 1 da d v a n t a g e so fe x js t j n gq u e r yt c c h n o l o g y a r ea n a l y z e d ，t h e 妇c t o i sw 1 1 i c ha f i e c tt h eq u e r ye f t y c j e n c ya r ef o l l l l d ，a n df h e a d v a n c e di d e a sa n o n gt h e ma i ed r e w 31t h ei d e ao fl 】n i q u ee l e m e n t 】d e n f i n c ri sl m p o r t e d a n dh o wl o1 1 s ec h i s i d e at os e tu di n d e xf l o rx m l d o c l l m e n t si se x p l a l n e d 4 1a c c o r d in 2t ot 1 1 ec h a r a c t e r i s t i ct h a ts e m i s t 九j c t u r e dd a t a i s i n c g u l a r a n di n c o m d i e t e ，ae f f e c t i v ei n d e xs t 九i c t u r e ae n h a n c e di n d e x f o rx m l d o c u m e n t sb a s e do nt e x t n o d ei sc o n s t r u c t e d 。 t h i si n d e xs t 九l c t u r e1 1 a ss t o r e d t h ef a v o r a b l ck e vi n f b m l a t i o ni nt h ex m l ，d o c u m e l l tt r e ew h l c h 】sm a d eb y d o mt e c h n 0 1 0 9 y ，a n de f 受c t i v e l yu s et h ec h a r a c t e r i s t i co fs e m i s t r u c t l l r ci n x m ld o c u n l e n tt oe x p e d i t et h es p e e do fx m lq u e r y t h ec h a r a c t e r i s t i c so f i n d e xs t n l c t u r ea r et h a ti n d e x 行1 ei ss m a l l ，a n dj tc a nb eu s e dt oq u e r yx m l d o c u n l e n t sp a r t i a l l y a c c o r d i n gt ot h i si n d e xt e c l m 0 1 0 9 y as u i t a b l eq u e r y a l g o r i t h mi sd e s i g n e d ，a n dt h ek e ya l g o “t h m si s d e s c r i b e df b n l a 1 1 y 5 ) ae x p e r i m e n t a lx m lq u e r ys y s t e n li sd e s i g n e da n dr e a l i z e d ，a n dt h e f u n c t i o n so ft h em a j nn l o d u l e sj nt h i ss y s t e ma r ei n t r o d u c e d t 1 1 ee n h a n c e d i n d e xb a s e d0 1 c e xt n o d ei sp r o v e d ，a n dt h ee x p e r i m e n t a lr c s u i t so nt 1 1 et e s t p l a t f 0 1 a r ep r o v l d e d 6 ) t h ea d v a n t a g e sa n dd i s a d v a n t a g e s ( ) fx m li 1 1 d e xt e c h l l 0 1 【) g yi 1 1t 1 1 i s p a p e r a r e s u m m a r i z e d ， a 1 1 dt h ed i r e c t i 0 1 1c o i m p r o v e t h j sx m lj n d e x t e c l l n 0 1 0 9 vi 1 1t h ef l “l 【r ei si n d i c a t e d + k e y w o r d s ：x m l ：d o c u l l l e n ti r e e ：f e x t n o d e jt 1 d e x ：c u l l l 1 1 a t ew o r d 仔e q u e n c y ：i 1 1 v e 】。t e d 扣1 e ；q l l e i | y e n g m e 第一章引言 1 1 x m l 简介 x m l ( e x f e n s i b l em a r k u pl a n g u a g e 可扩展的标记语晶) 是w 3c 绢织于1 9 9 8 年 2 月发狮j 的一种“推荐标准”，它足由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 ) 所简化演变而来的种标也语言。x m l 和h t m l 一样都是s g m l 的了集，它是专 为i n t e m e c 应用而设计的s g m l 的一个优化子集，以一种丌放的自我描述方式定义 数据结构，在描述数据内容的同时能突出对结构的描述，从而体现出数据之问的关 系。 x m i 。具有半结构化的特点：方面，与数据存储在起的标识描述了数据的结 构，还可以声明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 文档中的元素结构； 另一方面，数据又往往是很不规则的。因此，x m l 数据和传统数据库( 关系数据库 或面向对象数据库) 中的数据有较大的差别，不能简单采用处理结构化数据的方法 处理半结构化的x m l 数据。 x m l 是一种定义语言，使用者可自由定义标签，并通过元素之间的嵌套包含来 体现层次关系。它主要有二个要素：s c h e m a ( 模式) ，x s l ( e x t e n s i b l es t v l e s h e e t l a n g u a g ei q 扩展样式语言) 和x l l ( x m ll i n kl | d 1 1 9 u a g e 可扩展链接语言) 。s c h e n l a 定义了x m l 文件的逻辑结构，定义文件的元素、元素的属性及元素和元素属性间的 关系，可以用x m l 解析器来分析校验x m l 文件的合法性，s c l l e j m 允许把内容类型 ；皇义为整型、浮点型、布尔型或其它简单数据类型。x s l 是规定x m l 文档样式的浯 。j ，能存客户端使w c b 浏览器改变移示方法，从而不需再与服务器交互。x l l 可以 迸一步扩展目前w e b 上已有的简单连接。山此可见，x m l 迁档足山元素、子元素、 属性、p c d a t a 以及元素与后三肴的连接构成。 1 2x m l 文档实例 f 两我们列d ；_ 一个简单的x m l 文档及其d t d 文什的实例，未加显尔控制的 x m l 文档在浏览器中的艟可i 孙c 源文件桐同，通过这个x m l 文档实例，我们呵以 行钊x m l 的半结构化特征和树型存储及显示 、确已 1 ) x m l 文档：e x a m p l ex m l ? x m iv e r s l o n = ”10 ”e n c o d 1 苎= ”( _ i b l 312 ”净 1 1 1t h ew e es n l a 】j ol 1 r s ( m t l e i a c k s r a o k f i lih ew o os n a ljh ( ) l j 鼯c ：，f r a c k 10 e ta i o n gw 油o u fy u i 垤叮w e l j t 1 1 eo 凰p n n g a m e i l c a n a j t lc l e w c l c o m e h a v ey o ue v e f s t a r l n ga tt h es l l l l ( ，l r a c k ) t r a c k ) p r e t t yf l y ( f o raw 胁e 吼1 y ) ( ，c o m p a c t d l s c 2 ) d t d 丈档：e x a m p l e d t d ! e l m e n tc o n l p a c t d l s c ( a 九l s t ，i 】l 】e ，【j a c k s ，p l l c e p f e l e m e n ta n j s tf 萍p c da r i a ) f a 丁丁f ，i s ran i s cr y p e ( 1 y p e ，) 靠r 卜q r e d ) ! h l e m e n tt j t l ef 萍p ( 1 d a r a ) ：- 。 f l h m e n tt r a c k sn r a c k 8 p 一e l e m e n td n c e ( 牟p c d a la p i 3x m i 。特性 x m l 它采明了内。存，格式分离彬j 山，l5 i j 数据的仔储i j 艟小分j 1 ，t 所洲迎的 艾梢结构 i 仃良f j | 的j 玖利约求，l ，j _ 以f 骨州系统精确的u j 侍息所【= 似 ，幼j 表达殳档数州u 扑i 啦适合北i 占构史孙0 仑之处删，尤其足l t j 以利l jx m i 爻巾jn 0 机、i 己求确定钥艾档l t 的哪部分卣找，m 小址像nh t m l 义梢i p a 嚷个让托t 【倚j k 。 x m lh 仃以! 、h t m l 和咫箭的特性，这“姊计h 史刘x m l 迁档迎玎捎舰愀i 尘玲成 山口 能：1 ) j 护悖m ! ) 结船r i ：3 一“生性：4j 圳肼r l 、川托 引川j 性；5 ) 独立性；6 ) 灵活性；7 ) 健壮性：8 ) 平台无关性。 1 4 x m l 的意义及主要研究方向 目前1 1 1 t e n l e t 上的许多文档是用h 丁m l 格式存储及表示的。但是h t m l 在扩展 性、结构化和n j 验证性等方面的不足限制了它的应用能力及范围。随着x m l 文档的 大量涌现，对类似传统h t m i 。文档检索一样的x m l 文档的榆索功能的需求越来越 迫切。虽然h t m l 搜索引擎也可以应用到x m l 文档h 但是x m l 语言是比h t m l 语言功能更加强火的一种语言，所以如果直接把目前的h t m l 搜索引擎不加修改就 应用，x m l 特有的长处就不能得到完全发挥。x m l 语言提出以后，计算机界均认 为它可以比h t m l 更好地解决搜索问题。这是因为x m l 搜索引擎可以缩小检索范 围，利用x m l 文档中的标签束确定在文档中的哪部分查找，而不是象在h t m l 文档中一样在整个文档中查找。本文构造了一种针对x m l 这种半结构化文档的基于 文本节点的索引及查询策略，并建立了相应的索引结构及算法，实现了对x m l 文档 的高效查询，使i n t e m e t 中的海量数据可以更为方便地被人们利用。 x m l 研究方向主要分为3 个分支：1 ) x m l 文档向关系数据库的转化，主要解 决如何将x m l 的元素映射为关系数据库中的关系表；2 ) x m l 文档的查询，主要解 决将x m l 查询语言转化为s o l ，并利用关系数据库建立索引以实现对x m l 信息的 查询优化；3 ) 关系数掘库中数据的x m l 表示，主要解决将用s q l 浯旬查询到的关 系表结构的数据集转化为x m l 的表示彤式。 1 5x m l 查询的依据 传统的w e b 查咖技术把整篇h t m l 文档作为。一个原j 二单位，并且把整个文档当 作一个查咖结果返回给刖户。但是存许多情况下，文档中只有很少的一部分内容1 j 用户需求的信息有关。这样，用，。就必须在很长的个文档罩，弭去查找所需的相 关内容，以致降低了查洵效率，浪费了查询用户的宝贵时间。 x m l 本身具有半结构化的特点，它虽然没有关系数掘库巾数据的完整结构4 m 但是x m l 中元素耵1 属性都足相对独立的。通过x m l 解析器，j 以构造x m l 文档 的d o m 树，在d o m 捌1 ，每个结止i 都能单独进行处理。利用这个特性，我们可 以把d o m 树中符合月j 户查询条件的元素和膳h ：结点抽取h j 束，返m 给川户。这样， x m l 文档的结构化就完全叫以实现只返吲用广1 所火心的信息，从而满足用，。的精确 瓤咖要求。 第二章x m l 查询技术及算法 色基f 半结构化数据的基础上，已经j r 髅丁很多关于x m l 文档的存储、索引、 查询的研究。莉h t m l 不一样，由fx m l i 要是描述数抓：本身r 可不是拙述数掘的 冠示格式，所以x m l 文档已绎将数据和艾档的界限缩小厂，有耐可以将x m l ，文档 看作数据或将数据看作x m l 文档。一砦x m l 史档很适台于表示存储：数掘库l 1 1 的 数据，而一膨非结构化文档用x m l 文档存储后，常常能提供更太挥度上的信息共享。 随着x m l 的广泛应用，h t e r n e t 上大量的信息副将通过x m l 文档来进行俘储、交换， 或者通过各种应用接 | 用x m l 来表现。在x m l 数掘源中对大量的信息进行有效地 务询对用户而言就显得很重要r ，它能帮助用户更方便地浏览信息，正有效地获取 信息。另一方面，许多应用需要能对x m l 数掘源进行查询，例如删来解析x m l 数 据的j a v aa p p l e t ，使用x m l 数据来作数据采集和知识发现的智能代胖等、另外当具 有不同权限的用户存取同一文档时，通常需要让不同用户有不同的视图时，用奇询 语言来定义视图也是一种较好的方法。人量的x m l 数据，各种x m l f 、v 崩的出现， 以及x m li ：逐渐成为通用的数据交换格式，都要求有引肘x m l 文档的鸯洵i 开高求 查询相关数据。 2 1x m l 查询语言分类 到目时为l l ：，处婵x m l 数据的途径主要铂三种，关系数据庠处瑚乃浊、 f i 阳对 象数扼；库处理力法和原始处珲方法。在关系数捌处理方法t p5 1 ，x m i ，史十、引的数 据被映射为关系数据阵中的衰，埘x m l 数捌n 勺商c 自j 被转换为s q l l 身。二i 的彤c 。 s t o r e d “、a g o r a 吲、m o n e t 叫和v x m l r 川系统就是采用的这种处删，j 浊。限胁向 对象处珲方法中俐。】，x m i 文档r 、l 的数据根螂其s c 1 c l m 和d 丁d 文件亿i l 以类的 形式被存储在0 0 d bl 。h 刊x m l 数捌的咖破转换为0 q l 奄旧 “；的形。、l o r e 系统足采用的这种处聊方法的觌，弘代表。，l 原始处州方法t hx m l 史梢仍以蟓始形 式存j i * ，f l 二 足需要建洲哿殊的数撕构和索，) j 列x m l 数掰进行内仃疗淅 j 索j ，夯 咖时适需要有针对圳心数据结构和索r j qa 咖优化。采圳此押d 浊的系绵、仃 r l m 】s l 、s r 】1 1 d e 引、仉l n l 1 0 j 。 当今的x m l 套询语言堪水可以分为眄炎：1 ) 数执：雎领城：枷l o r e x m l q lj 1 、t a 丁l 、q “i 川1 “、x a 4 l g f ：2 ) 义p f 翎! 域：拟fx s l 、x q f ，j j 、x c ) l i c i y j 、 x p a t 毗；。 9 跫水i 免，f ! l 更4 7 1 j i i j i e 肖捉f n ，r i 匍i n 。，j j i 兜较0 9 ，蚰 x s l 和x q l 均不支持正规路径表达式匹配等。而由数据库研究者提出的查询语音功 能相对强大， 般都支持复杂的路径表达式、连接、嵌套查询等数据库查询语言。的 典型特性，但在对些高级特性的支持程度上也存侄着一定的差别。如l o r e 和o u i l t 支持全称量词，而x m l q l 和x m l g lm 0 不支持；在语法形式上也有所筹别，l o r e 利q u i l f 类似于s q l 和0 q l ；x m l q l 的主体部分为标准的x m l 挤式；x m l g l 则是一种图示化的查询语占。这些查询语言的共同点是都使用了基于汇则路径表达 式r p e ( r e g u l a r p a t he x p r e s s i o n ) 来查询x m l 数据，可以根据r p e 在x m l 数据中 搜索任意长的路径。 2 2x m l 查询语言特征 一般来说，x m l 查询语言应该具有如下特征： 1 ) 可进行精确的语义查询；2 ) 可进行查洵转换：3 ) 应具有潜在的代数基础； 4 ) 支持各种简单的数据类型，并提供一种可扩充数据类型的机制；5 ) 应支持选择、 重构、连接、析取等基本操作，还应支持复杂选择条件和布尔操作；6 ) 应易于被优 化：7 ) 应简单，通用，易于被解析器进行解析；8 ) 应具有封闭性，即查询的对象 为x m l 文档，查询返回的结果也应为x _ m l 文档；9 ) 查询范围应该能够覆盖单。 的x ml - 文档和一系列的x m l 文档：1 0 ) 查询过程应该是说明性的，而非过程性的。 即用户只需说明想得到什么，而不必说明如何得到。1 1 ) 无需s c h e m a 或d t d 支持； 1 2 ) 保持元素的顺序和关联；1 3 ) 易于由程序生成。 2 3x m l 查询方法 x m l 查询方法的选择是x m l 查询效率高低的重要影响因素，高效的惫询方法 和索引结构将为x m l 查询系统带来最佳的性能发挥。x m l 查询研究领域中已经出 现i r 许多查渤方法，如糕于扩展的o e m 模型的查嘲方法【1 ，基于树模型的查询 方法俐，基j 币则路径表达式的查泊j 方法旧，基于b 树存储的的查询方法2 3 】，暴 。而向划象的半 槲勾化数据模型的查询方法吲，基于模式蕴含韵查询方法吲，基于 k e vf 。查询方法吲，基于模式匹配的查询方法，堪1 ：部分匹配的食询方法川， 这些务咖方法根掘其利用的数据模型种类各不相同，各有优势及不足。j 、面我们分 析儿种重要的常用x m l 查询方法： 1 ) 基于1 1 = 则路径表达式的x m l 查向：文献f 2 l h 时茁述，x m l 文档司以被抽琢成 符二二路径。峡例晌集合，每个数训常点都相应地对应于个路径实例。路径表达式 查嘲h 术匹刚x m l 文档n 路径。其协，从而得至i j = 合条件的冗素实例。文献 2 2 ”6 j 述 了利用d a t a g u i d e 将f 则路径表态式查询重q 为简单路径表达式查询的思想。矿则路 径表达式以字符串的形式表示从根结t 起至同标 ；点的路径l 的所育- 信，皂、。 _ = 【 是路径表达式并未利用x m l 文档的有序性，因此它不能够表示同胞结点、和丸绵点 的一j 胞结点以砹这些同胞结点的子孙结点上的条件。 2 ) 基于b 树存储的x m l 数据库查询：文献 2 3 中描述了币个x m l 义档本身 具有树；扶结构，这种查询思想是将系统l + 小同的x m l 文档仃储在同 棵b 树中， 关继问题在于如何给不同的x m l 文档以及其中的元素、埔性等赋j 相臆的关键字， 并进行适当的调整，使之达剑半衡，构成b 树。b 树是一种平衡的多路杏找倒，杏 询过程是一个递归过程，查询返川一个u 录。这种方法查啕的过程较简单， = _ i 是在 每次查询时都建立b 树，并t 其进行节点位置调整，徂：处理大型x m l 文档时速度 会很慢，而且对内存和c p u 性能要求较高。 3 ) 基于模式蕴含的x m l 数掘库查洵；文献f 2 5 中描述了模式垃含的思想。似设 s c m 2 s c m l ，可以得m ：( 1 ) s c m 2 的匹配仪能在s c m l 中找到，丑聚已知蕴岔模式 s c m l 的匹配，需要查询与被蕴含的模式s c m 2 匹配的信息，则搜索空倒闭被减小； f 2 ) 所有s c l n 2 的匹配也足s c n l i 的匹配，所以，如果己知被蕴含模，s c m 2 ，需要 奁洵蕴含模式s c m l 的匹配信息，则无需搜索即0 得到s c l l l l 的荇于匹配，、_ 然，s c m l t ，能还商其它的匹配。这种方法已经存根火程度 提高了查询效率，似足列预存模 式的提取、选择和匹配又带术了模式库空间的扩大、系统处理时m 的增加等不利因 素。 2 4 索引在x m l 查询优化中的重要性 何种数据查询语南都f 应地对j 咄荷种数据模州，如结构化逝嘲 等j ( s 0 l ，) 剥 鹿0 i 关系数据卡夔刑；面向划象查问语j ( o q i ，) 剥应着利象模型：x m 卜 _ i 1 = 咖l f z 、j 、v 的数j ：【 模叫既不同。= 卜关系模型，也个删7 。对象模骂，f 盯魁和近二求数据库7 班究久 艮进行了人量研究的卜i 槲，j 化数据模j 皑 h 千h 似。良半结构化数折 模，眇h 人躺陌* 结构化数据表现为某种蚓或树的结构= n 阱目似，x m l 文档也ij j 表现柴聊罔或捌的 结构。f i ：进行x m l 查询时。通常将) ：m l 文梢解析为d o m 树采进行处州。 x m la 【1 _ i i 最简r 讧的方浊是，揪掘路径条件深度优先遍历所钧讧i 、j 硝i i 嘲涧条件的啄j 7 刈象，这利t 方竣称为顺阳j 、的赶嘞方池。，j个，j 浊越，丸。t 拽 所，f = 1 j 钧龠删涧绦件的脓了扩c i ，然后| j ：找它们的父节，r i ，l p i ；吐的i _ 纾枷、抟为 给定阳眦，这种方法j 阳肢向f ：的盎耐m 第种0 法为i ) = _ 哲的溉i 7 先i t 顺 二型兰生二= 兰型! ! 兰竺! 兰! ：= ! 墨! j 塑】垒塑立竺 向下的方法爿找符合路径条件的对象，然后再用自底向上的方法寻找符合谓词条件 的原子对象，两者的结合即为最后的查询结果。根据实际情况的不同，这种方法各 有其优势。 这种基于d o m 查询的实现方法一般就是对d o m 树进行遍历，但是对于由大型 的x m l 组成的海量x m i 。数据库，这种方法将会占用超大内存并且查询响应叫问非 常长，令查询用户无法接受。d o m 遍历方法的查询时间随着测试数据量的增= 人呈现 类指数增长，而使用索引后的查询方法基本上是呈线性增艇。因此，x m l 数据库的 索引技术对x m l 数据查询处理起着至关重要的作用，如果没有索引的支持将会还柬 巨大的i o 代价和语义方面的限制。 在关系型数据库中，数据表中的所有数据都是结构化的，为了加快查询速度，司 以为表中的属性建立索引，这种索引是针对属性值而建立的。而在x m l 文档数据库 中，x m l 文档中的数据是半结构化的，在进行x m l 查询时，d o m 树中路径的信息 与元素及属性的值具有同样的重要性。因此只有值索引是远远不够的，还要为路径 信息建立索引，这样才能加快x m l 查询的速度。 2 5x m l 索引类型 应用特殊的索引来检索结构比文档中的数据的研究已经进行了好多年，并且涉及 很多领域如信息检索、数据库、x m l 。s h a n mu g a s u n d a r a mj 等提m 对于不同的路 径表示法进行不同的s q i 。转换，z h a n gc h u n 等提山建立i u v e r t e d1 i s t 来支持内容 检索川。并且已经产生了好多种可行的索引技术，如树匹配( t r e em a t c h i n g ) 吲 3 3 】 路径索引( p a t hi n d e x ) ”4 心，串索引( s t r i n gr n d e x ) ，本体索引( o n t o i o g yi n d e x ) 川等。其中s t 如f b r d 大学的l o r e ( l i 曲t w e i 曲to b j e c tr e p o s j t o r y ) 3 7 脚1 就是个著名 的x m l 数据系统，他们在对半结构化数掘进行多年研究的基础l ，史现了用火系数 据库存储、查询和表示x m l 数据的整套解决方法，该系统中的d a t a g u i d e s 刚是章 门为半结构化数据殴计的索引技术，其中包括v a l u ei n d e x ，l a b l e1 n d e x ，e d z ei n d e x 和p a t h i n d e x 等4 种刁i 同的索引结构。这些索引技术大部分都使用 j ，基于矿则路径表 达式的食询语言，适用范闱较小，而日实现复杂，索引文件量非常大。 z i ：团内外近年来出现的儿类索引中，比较常用的索引纠合有以下几种，这u b 索引 组合已经被应f h 到许多较成熟的系统上： 】) l o r e 系统针列臼身的o e m 结构和d a t a 璺i i d e 结构建0 了4 科- 不州的索弓f ， 咀加快对x m l 的查嘞速度：v 1 1 1 d e x ( v a l u c1 1 1 d e x ) 支持查找仃给定边并满足某个州洲 山开i 人学2 ( ) 0 5 扁例“先生学位论文 的所有原子对象：l i n d e x ( l a b e l1 1 1 d e x ) 支持查找所有给定边的父对象；e 抽d e x 征d g e t 1 1 d e x ) 支持杏找所有山给定标签连接的父子对象对：p m d e x ( p a i ht n d e x 支持食找通过 给定的路径所能找到的所有利象。这类索引在使用时更多的依靠x m ls c l l c m a ，限制 条什较复杂。 2 ) 元素索引( e 1 e m e n t i n d e x ) 、属性索引( an _ t i b u t e i u d e x ) 、结构索弓| ( s tr l l c t i n d e x ) 【”l ：这i 种索引分别用来支持3 种必须的功能。通过元素索引可以找剑所有恩有相 同元素名字的元素实例，通过属。陀索引可以找到具有相同属性名字的属性实例，结 构索弓! 用柬查找某一给定元素的父元素和子元素。在这种设训中存在着如下不足之 处，皋r 这种设计提出的快速确定x m l 数据层次结构中的祖先一了孙关系的编号机 制，可以很容易从父亲一孩了：关系表中演化出祖先一子孙关系，但是很难从般的 祖先一子孙关系表中区分m 父亲一孩子关系，因此很难建市结构索引。这种方法无 法支持路径中父子关系的元素一元素的连接操作，同样也无法支持元素属性阃的 连接操作。 3 ) 父子别索引( p n a m ei n d e x ) 、属性值索引( a t t r i b u t e 、州u ei n d e x ) 、引用祭0 r r e l c r e i l c ei n d e x ) 、全文索引( e i e n l e n t t e x l1 1 1 d e x ) 。查询的时候通过这些索引而不足直 接遍历d o m 树本身。每个索引结构都是基于b + 树的，能够理解结构化詈标树，提 供伞文索引，以用对元素和属性进行索引，对结构和内容进行索引，并提供按照元 素和属性定化并检索几素的功能。这种索引技术为x m l 文档的信启、建妒j 全血索 引，但是也大大增加了索引库的体_ | ，向目在每次奇询时都要重建d o m 拊，增加r 杏泊j 时日l 。 第三章文本节点索引技术 从数据库的观点m 发已经提出了很多来描述x m l 数据的模型，这些模型可以简 化半结构化数据的查洵过程。基于这类模型的数据库把不一j 的x m l 元素从不同的数 据源合并到一个学一的层次结构巾，然后用种统一内部的描述去查询x m l 数据。 这种方法刁i 是把x m l 文档看成一个整体文本，而把x m l 文档看成了不同的x m l 元素的集合。实现结构检索的关键是对文档的结构信息进行标识，建立结构索引。 其中文档结构的表示以及索引结构的设计是主要应解决的问题。 本文利用文本节点索引技术t n i n d e x ( t e x t n o d e i n d e x ) ，可以大大减少x m l 文档的索引量而且可以加快查询的响应时间。其基本思想是：在建立索引时，对x m l 文档的所有文本节点( 最底层节点) 进行关键词索引，并记录各文本节点中关键词 的词频：在对x m l 文档进行查询时，要得到的是非文本节点( 本文中指元素节点和 属性节点) 的关键词出现的频率，由于待查询的非文本节点属于高层节点，我们可 以通过对其子元素的中非文本节点的相应关键词的词频进行自底向上的累加而得 到。 3 1 唯一元素标识 首先我们引入l e e ，y k 提出的唯一元素标识u i d ( u n i q u ee l e m e n ti d e n t m e r ) 的 思想，这种标识方法可以快速计算出任意一个给定元素的父元素，并且可以根据一 个元素的u i d 来确定它所有子元素可能的u i d 范围。在文献【4 1 中，x m l 文档被描 述为一个完全k 叉树，k 为x m l 文档的树型结构中一个元素可能包含的最火子元 素的个数。如果我们把待查询的x m l 文档与一棵完全k 义树进行对照，那么在这 棵完全k 叉树的所有节点中一定会存在勺x m l 文档肖点不匹配的节点，阿日这些 节点是我刷对完全k 叉树各节点进行u i d 标识时所小可缺少的节j j j 。因此，在进行 节点标_ i = 的时候仍然要让这些与x m l 文档节点不匹配的书耐节点占位绵号，但是在内 存中并不真正剐它们进行存储，我们把这类节点称作虚节。t 气。把完仝k 叉树r j 能与 x m l 文档节点匹配的树节点进行编号存储，这类节t i 被称作实节点。存编号时，我 们采用层次遍历的方法进行完全k 义树的遍历。 这样，在这棵完全k 又树中，如果我们知道一个节点的u i d ，就司以依抛表达 式f1 ) 直接计算山它的父节点的u i d ，其中p a r e n t ( i ) 表示当前节t i 的父节点u 1 d 编号，i 表示当污节点的u t d 编号： 些! ! 生兰! ! ! ! 墅竺1 竺垒竺兰竺堡! _ _ + _ _ _ - _ _ _ 降e n t = l 竿“i 司以依掘表达式( 2 ) 和表达式( 3 ) 计算出它的最小了节点的u i d 和最大f 节点的 ij i d ，其巾c h i l dm i n ( i ) 是当前