（计算机软件与理论专业论文）patriciatries结构的xml数据索引技术的研究.pdf

p a t r l c i a t r i e s 结构的x m l 数据索引技术的研究 r e s e a r c ho nt h ex m l i n d e x i n gt e c h n o l o g yb a s e do n t h ep a t r i c i a t r i e ss t r u c t u r e 专业：计算机软件与理论 作者：龚成清 导师：叶小平副教授 论文答辩委员会委员： 2 0 0 7 年l o 月2 9 日 霉苣聋回衫 讳i 鹏移友杪 批彬 论文题目：p a t r i c i a t r i e s 结构的x m l 数据索引技 术的研究 专业：计算机软件与理论 硕( 博) 士生：龚成清 指导教师：叶小平 摘要 当前，高校图书馆数据管理系统各自为政。随着网络技术的发展，x m l 的 应用越来越广泛，它已经成为i n t e r n e t 上数据表示和交换的新标准，同时也被认 为是用来定义半结构化数据最有效的手段。利用x m l 技术来处理图书数据信息 将会使数据规范统一，便于数据的交流和共享。大量的书籍信息以x m l 数据文 件保存后，对信息的查询提出了新的要求。为了提高x m l 数据的查询效率，为 ) o v i l 数据的建立索引是一种有效的方法。 研究了当前x m l 数据索引的常用方法，分析比较各种方法的优缺点。在压 缩存储的思想下提出了基于t r i e 树结构的p a t r i c i a - t r i e s 索引结构。具体介 绍了p a t i u c i a - n u e s 索引结构的建立的四个步骤：编码元素标签、编码元素值、 建立索引树、设立头结点：分析了p a t r i c i a - t r l e s 索引结构的时间复杂度和空 间复杂度同时也指出了该索引的不足。该索引具有容量小，速度快的优点。 实践证明，该方法是行之有效的。 关键词：x m l ，数据，索引。p p 3 t d c i a - t r i e s t i t l e ：r e s e a r c ho nt h ex m li n d e x i n gt e c h n o l o g y b a s e do nt h ep a t r i c i a - t r i e ss t r u c t u r e m a jo r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：g o n gc h e n g q i n g s u p e r v i s o r ：y ex i a o p i n g a b s t r a e t n o wt h el i b r a r yd a t a b a s em a n a g e rs y s t e me a c hd o e st h i n g si nh i so w nw a yi n c o l l e g e t h ea p p l i c a t i o no fx m li sw i d e l yu s e d w i t ht h ed e v e l o p m e n to ft h e n e t w o r k i th a sb e e nan e ws t a n d a r do fd a t as h o wa n dd a t ae x c h a n g eo ft h e i n t e r a c ta n di th a sb e e nt h em o s te f f c c t i v em e a n st od e f t n et h es e m i s t r u c t u r e d a t a w i t ht h eh e l po fx m lt e c h n o l o g yt op r o c e s s i n gb o o k sd a t a , i tw i l lm a k et h ed a t a s t a n d a r d i z a t i o na n de a s yt ob es h a r e da n de a s yt ob ee x c h a n g e dw h e nt h em a s sd a t ai s s t o r e di nt h ex m lf i l e i tb r i n g sf o r w a r dan e wr e q u e s tt os e a r c ht h ei n f o r m a t i o n s ot o s e t u pt h ei n d e xo ft h ed a t a i sv e r yi m p o r t a n ti t i sag o o dw a yt oe n h a n c et h e e f f i c i e n c yo f t h eq u e r y i n g t h ec l a s s i c a lm e t h o d so fx m ld a t ai n d e x i n ga r es t u d i e di nt h i sp a p e r l t a n a l y s e s t h ec l a s s i c a lm e t h o d sa n d p o i n t s o u t t h e i r a d v a n t a g e s a n d d i s a d v a n t a g e sb a s e d o nt h ei d e ao fc o m p r e s s i n g s t o r a g e ，i tb r i n g sf o r w a r d a p a t r i c i a - t r i e si n d e x i n gs t r u c t u r eb a s e do nt h et r i e - t r e es t r u c t u r e i ti n t r o d u c e s f o u rs t e p st os e tu pt h ep a t r i c i a - t r i e si n d e x i n gs t r u c t u r ei nd e t a i l ：c o d i n gt h e e l e m e n tl a b e l ，c o d i n gt h ee l e m e n tv a l u e ，s e tu pt h ei n d e x - t r e ea n ds e tt h eh e a d i n g n o d e s i ta l s oa n a l y s e st h et i m ea n ds p a c ec o m p l e x i t yo ft h ep a t r i c i a - t r i e s i n d e x i n gs t r u c t u r ea n di t ss h o r t a g ei sa l s ob e e np o i n t e do u t t h ep a t r i c i a - t r i e s i n d e x i n gs t r u c t u r ei ss m a l ls t o r a g ea n df a s tp r o c e s s i n gs p e e d p r o v e di np r a c t i c e , i ti sa ne f f e c t i v em o t h o d k e yw o r d s ：x m l ，d a t a , i n d e x i n g ，p a t r i c i a - t r i e s 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研 究作出重要贡献的个人和集体，均己在文中以明确方式标明。本人完 全意识到本声明的法律结果由本人承担。 学位论文作者签名：安城有 日期：啡1 1 月弦日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文并向国家主管部门或其指定机构送交论文的电子版 和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论文进 入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入有关 数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。保 密的学位论文在解密后使用本规定。 学位论文作者签名：壤戏有 导师签名：叶j ，尹 日期：卅年1 1 月记日日期：碲7f 月棚 引言 随着网络技术的发展，x m l 在i n t e r n e t 上占据越来越重要的地位，它已经 成为i n t e r a c t 上数据表示和交换的新标准，同时也被认为是用来定义半结构化数 据最有效的手段。目前，在各个高校的图书馆中，都建立了图书馆数据库管理系 统来对馆藏的书籍进行管理。这些系统大多数都是采用传统的数据库技术结合动 态网页技术来实现的。由于没有统一的技术标准，各高校的图书馆数据库管理系 统自成体系，无法很好地实现数据的共享和交流。x m l 技术的出现为高校图书 馆数据库管理系统的建设提供了一种新的标准，可以有效地解决数据共享和交流 的问题。 利用x m l 技术来建设高校的图书馆数据库管理系统，大量的数据将会存放 在x m l 的数据文件中，如下面的b o o k s x m l 文件： t o m x m l 入f 2 3 0 0 7 - 0 3 ，0 1 4 2 5 6 9 2 0 0 s m a r y k 时，在a ( k ) 索引中无论采用自底向上或自顶向下 的查询策略所得到的查询结果都有可能包含错误的查询结果。所以在这种情况下 还要将所得到的查询结果在x m l 数据图上进行验征，以确保所得到的查询结果是 正确的。 4 d ( k ) 索引 h ( k ) 索引中每个索引结点的相似度都为k ；d ( k ) 索引是对频繁使用的路径进 行索引，而频繁使用的路径长度往往是不相同的，因此d ( k ) 索引中的每个结点的 相似度k 也不相同。”1d ( k ) 索引有如下两个性质； ( 1 ) 每个索引结点与一个相似度k 有关。 ( 2 ) 给定一个索引结点的相似度k ，它的父结点的相似度至少为k - i 。 d ( k ) 索引主要由两个算法组成： ( 1 ) 索引创建算法；首先根据频繁使用的路径决定每个索引结点所需的最 大相似度k 。然后由a ( 0 ) 索引开始迭代，分裂每个索引结点，直到它们的相似度 达到最大相似度k ， ( 2 ) 更新算法：对频繁使用的路径进行更新后，现有索引中的结点的最大相 似度也要进行相应的更新。 5 m ( k ) 索引 d ( k ) 索引主要存在以下两个问题： ( 1 ) 在更新算法中，对不相关结点的扩展集也进行分裂操作。分裂后的索引 大小比满足查询需要的最小索引的大小要大得多； ( 2 ) 若结点v 的相似度为k ，v 的父结点的相似度满足 k l ，d ( k ) 索引更新算法 对结点v 的扩展集进行分裂操作，而实际上对于满足这类条件的结点v ，不要对其 结点的扩展集进行再分裂操作。哳1 引起上述两个问题的原因是d ( k ) 索引的k 值只 能取个值。 醅( k ) 索引的特点； ( 1 ) 每个索引结点的相似度k 不相同： ( 2 ) 为了避免对不相关结点集进行分裂，m ( k ) 索引的更新算法除了使用路径 表达式之外还使用了频繁使用路径的查询结果， 1 4 m ( k ) 索引是多个类似m ( k ) 索引的集合，表示为i 。，i ，一，i 。分别存储结点 相似度从0 分裂到k 的索引。 m ( k ) 索引中各个索引之间结点分裂前后的结点由 指针连接。m ( k ) 索引有如下性质： ( 1 ) 每个索引i ；具有m ( k ) 索引的性质； ( 2 ) 索引i m 是由索引i 。的分裂得到。由i 索引结点分裂得到i 。的索引结点， i i 1 索引结点的相似度至多增加l ： ( 3 ) 若i t 索引分裂得到i m 索引，结点的相似度不增加，则结点相似度在以后 的索引分裂中也不会增加。 m ( k ) 索引优点：由于k 有不同取值，因此它可以高效查询路径长度不同的频 繁使用路径，并且避免了d ( k ) 索引的两个缺陷。 6 a p e x 索引 d a t a g u i d e 索引和卜i n d e x 索引保存从根结点开始的所有简单路径。若用户给 定的查询路径不是从根结点开始，则使用上述两个路径索引需要对索引进行遍历 式导航，查询效率降低。 a p e x 索引是d a t a g u i d e 索引的一种近似，能够有效地处理某些相对路径查询， 它创建的索引是基于查询频度，对频繁使用路径创建索引。当查询频度有变 化时，a p e x 索引可以进行有效的更新以适应查询频度的变化。a p e x 索引的优点： ( 1 ) 索引可以随着查询频度的改变而更新： ( 2 ) 能够有效处理查询语句的开始标签不是从根结点开始的简单路径查询。 a p e x 索引的缺点： ( 1 ) 频繁使用路径如何判定： ( 2 ) 对非频繁使用路径的查询效率较低： ( 3 ) 查询从根结点开始的路径效率较低。 7 f a b r i c 索引 f a b r i c 索引的基本思想是将半结构化数据之间的关系表示成路径。眇1 将路 径编码成字符串，然后在字符串上面建立索引。f a b r i c 索引的优点： ( 1 ) 能够管理大量长而复杂的字符串： ( 2 ) 其结构是平衡的，因而不同的访问所需的查询代价几乎相同： ( 3 ) 既可以作为路径索引，也可以作为值索引。 f a b r i c 索引是从p a t r i ct r i e ( p t ) 树结构发展而来的，p a t r i ct r i e 是一种字 符串的编码方式，是一种多路树，采用树形结构将字符串之间的差异表示出来。 正是因为p t 树只描述串之问的差别，所以它增长得很慢，同时索引项的长度对索 引大小影响很小。f a b r i c 索引支持文档的更新操作。 利用f a b r i c 索引管理x l l 路径文档路径分为两类：简单路径和精确路径简单 路径将) ( m l 文档从根节点到叶子结点的路径按照顺序编成字符串。精确路径不仅 可以实现简单路径的编码功能也可以实现对其他信息进行编码，从而可以支持复 杂查询。 2 2 基于编码的x m l 索引查询技术 基于路径索引的删l 查询技术能够有效地解决单路径查询问题，但是不能很 好地解决分支路径查询；编码索引查询技术不仅可以有效地查询单路径，也解决 了分支路径查询问题。基于编码的x m l 索引查询技术主要有：x r + x r s t a c k 算法、 a n c - d e s c r b + 算法等。1 们 1 ) 叫数据的编码方案 目前常用的x m l 数据的编码方案主要有：位向量编码、区间编码等。 位向量编码；树t 中的每个结点被编码为一个1 1 位向量，n 是树t 中的结点数量， 在某个位置i 上的一个“1 ”惟一标识第i 个结点；并且在一个自顶向下( 或自底向 上) 的编码方案中，每一个结点继承它祖先( 或后裔) 结点的所有位上的“l ”，如 图2 - 4 所示。 1 6 圉2 - 4 位向量编码 区间编码：树t 中的每一个结点被赋予一个区间编码 b e g i n ，e n d ，并且满 足：一个结点的区间编码包含它的后裔结点的区间编码，即树t 中的结点u 是结点v 的祖先，当且仅当b e g i n ( u ) ( b e g i n ( v ) a e n d ( v ) 。 对树t 的所有结点进行先序遍历，每一个结点在遍历树时分别被访问两次并产生 两个序号。一次是在遍历该结点的所有后裔结点之前访问该结点，并产生该结点 的序号b e g i n ，另一次是在遍历完该结点的所有后裔结点后再一次访问该结点， 并产生该结点的另一个序号e n d ，如图2 5 所示。 圈2 - 5l h u 编码 1 7 2 “e o e s e b + 算法 一般而言，基于编码的查询算法都是基于结构连接算法的。所谓结构连接 算法是指利用结点的编码来判定结点之间是否具有祖先后裔关系。a n c _ d e s c _ b + 算法的基本思想是：对于给定的查询语句，首先要生成它的祖先列表和后裔列表， 然后利用b 十树索引跳过不参加连接的祖先列表中的结点和后裔列表中的结点，避 免对祖先列表和后裔列表中的所有结点进行扫描。n 例如，对于图2 5 中的x 札数据图，假设某个查询语句所对应的祖先列表中 的结点为姐，2 ，3 ，4 ，7 ，8 ，9 ，t o ，后裔列表中的结点为( 5 。6 ，1 1 。现要 查找结点1 0 ，则通过扫描祖先列表和后裔列表来判断结点之间的关系，在判定完 结点5 ，6 的父结点为结点4 之后，判断结点儿，由于结点l l 的父结点是l o ，且结 点l o 是祖先列表中满足b e g i n ) e n d ( 2 ) 的结点，因此跳过祖先列表中结点( 7 ，8 。 9 ) ，而直接定位到结点1 0 。 在图2 _ 6 所示的x m l 文档中，假设某个查询语句所对应的祖先列表中的结点 为( 1 ，2 ，8 ，后裔列表中的结点为 3 ，4 。5 ，6 ，7 ，g ) 。在判定出结点2 ，3 具 有祖先后裔关系后，利用树索引直接定位到结点9 ，结点9 是后裔列表中满足 b e g i n b e g i n ( 2 ) 条件的第一个结点，避免了后裔列表中结点( 4 ，5 ，6 ，7 ) 的扫描。 圈2 - 6 晓过后膏结点的售况 3 x r 树+ x r - s t a o k 算法 在a n c _ d e s c _ b + 算法中，利用b + 树索引能够有效地跳过后裔列表中所有不参 加连接的结点，但是对于祖先列表中所有不参加的结点，并不能利用b + 树索引来 有效地跳过，这是因为；在祖先列表中无法利用b + 树索引直接定位结点的第一个 1 8 可能的祖先结点，需要多次定位才能跳到结点的第一个可能的祖先结点。为了解 决这个问题，x r 树索引被提出，基于x r 树索引不仅能够有效地跳过后裔列表中所 有不参加连接的结点，而且能够跳过祖先列表中所有不参加连接的结点。例如， 图2 - 6 中若要找到后裔结点9 的父结点8 ，在a n c _ d e s c + 算法中不能够一次定位到 结点9 的父结点。需要多次在祖先列表中迸行定位才麓够找到结点9 的父结点8 ， 而x r 树+ x r - s t a c k 算法能够在祖先列表中一次定位到结点9 的父结点8 。 4 x l s s 系统 x i s s 系统的主要思想是：将一个正则路径表达式分解成子路径表达式，将子 路径表达式产生的中间结果进行结构连接操作得到最终的查询结果，并且该系统 支持文档更新操作。 x l s s 系统主要由五个索引组成：元素索引、属性索引、结构索引、名称索引、 值索引。1 2 1 这五个索引采用b + 树作为索引结构。 x i s s 系统将正则路径表达式分解成五个基本的子表达式： ( 1 ) 单元素单属性子表达式：通过查找元素索引、属性索引得到查找结果。 ( 2 ) 一个元素和一个属性子表达式：e a j o i n 。 ( 3 ) 具有两个元素的子表达式：e e j o i n ( 4 ) k l e e n ec l o u r e ( + ， ) ：k c j o i n 。 ( 5 ) 子表达式之问的联合操作。将分解的子表达式所得的中间结果进行连接 得到最终酌正则路径表达式的查询结果。 x i s s 缺点：只能解决单路径查询，对于分支路径查询效率较低。 1 9 第3 章基于p a t r i c i a - t r i e s 的x m l 路径索引设计 上述的各种x m l 数据索引的方法各有其优缺点。但大多数索引技术的压缩 率都不高，本文提出了一种基于p 舢c i a - t r 皿s 的x m l 路径索引设计方法， 该方法具有简单高效，压缩率高等特点。 3 1p a t r i c i a - t r i e s 结构 基于关键空间分解的任何数据结构称为个t r i e 结构。象b + 树一样，基于关 键空间分解的树结构只在叶结点存储数据记录，内部结点作为占位符引导检索过 程。1 3 1 字符a a a b b a 、a b a b a 、a b a b b 、b a 用t r i e 结构进行区分。如图3 1 所示。 3 - 1t r i e 结构 t r i e 结构要对字符串进行逐一的比较，效率很低。d m o r r i s o n 在1 9 6 8 年对 t r i e 结构进行了改进，发明了有关t r i e 结构的一种变体称为p a t r i c i a - t r i e s 。 p a t r i c i a - t r i e s 改进了t r i e 结构