（计算机软件与理论专业论文）基于特征向量的时态xml索引研究.pdf

枣 e 原 本人郑重 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的科研成果。对本 文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：鏊e 圣竺生 日论文作者签名： 叠( 二! ：了 日期：竺! ! ：! ：f 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意 学校保留或向国家有关部门或机构送交论文的复印件和电子版，允 许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他 复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) ：蚪新弛靴一r 一 l ，i 0，f， 1 3 本文的主要工作7 1 4 本文的组织结构8 第二章t f i x 索引模型9 2 1 理论背景9 2 1 1 双似、双拟”9 2 1 2 小枝查询( t w i g ) 1 2 2 1 3 对称矩阵的特征值性质l3 2 1 4 时态x m l 结点时间区间的包含性1 6 2 2 索引构建1 6 2 2 1 特征向量的选择1 6 2 2 2 索引分类1 8 2 2 3 索引构建算法1 9 2 2 4 索引的完备性2 4 第三章t f i x 索引查询处理2 6 3 1 索引查询算法”2 6 3 2 时态查询举例”3 0 第四章t f i x 索引维护与实验3 4 4 1 索引的维护一3 4 4 1 1 增加数据的索引维护3 4 山东大学硕士学位论文 4 1 2 删除数据的索引维护3 7 4 1 3 更新数据的索引维护3 8 4 2 实验3 8 4 2 1 索引筛选效率实验3 9 4 2 2 索引查询性能实验4 0 第五章总结与展望4 3 5 1 论文工作总结4 3 5 2 进一步的工作一4 3 参考文献4 5 致谢5 0 攻读学位期间发表的学术论文目录5 l 攻读学位期间参与的项目5 2 f ， 一l 山东大学硕士学位论文 t a b l eo fc o n t e n t s a b s t r a c ti nc h i n e s e “i - a b s t r a c ti ne n g l i s h 皿 c h a p t e r1 i n t r o d u c t i o n 。1 1 1b a c k g r o u n d 1 1 1 1x m ld o c u m e n ta n dx p a t h 1 1 1 2t e m p o r a lx m ld o c u m e n ta n dt x p a t h 2 1 2c u r r e n tr e s e a r c h 4 1 2 1n o n t e m p o r a lx m lr e s e a r c h 5 1 2 2t e m p o r a lx m lr e s e a r c h 6 1 3m a i nw o r k 7 1 4o r g a n i z a t i o n 8 c h a p t e r2t f i xi n d e xm o d e lt f i x 9 1th21b a c k g r o u n dt h e o r i e s 9 p 2 1 1b i s i m u l a t i o n 9 2 1 2t w i gq u e r yp a t t e r n 1 2 2 1 3 t h e p r o p e r t y f o r e i g e n v a l u e o f m a t r i x 1 3 2 1 4c o n t a i n m e n tp r o p e r t yf o rv a l i dt i m eo f t e m p o r a lx m l n o d e s 1 6 2 2i n d e xc o n s t r u c t i o n 1 6 2 2 1c h o i c e o f f e a t u r e v e c t o r 1 6 2 2 2i n d e xt y p e s 18 2 2 3i n d e xc o n s t r u c t i o na l g o r i t h m 1 9 2 2 4c o m p l e t e n e s so f t f i xi n d e x 2 4 c h a p t e r3c o m p l e t e n e s so f t f i x i n d e x 2 6 3 1q u e r yp r o c e s s i n ga l g o r i t h mo f i n d e x 2 6 3 2t e m p o r a lq u e r ye x a m p l e 3 0 c h a p t e r4m a i n t e n a n c eo f t f i x i n d e xa n de x p e r i m e n t 3 4 4 1m a i n t e n a n c eo f i n d e x 3 4 4 1 1m a i n t e n a n c ef o ra d d i n gd a t a 3 4 山东大学硕士学位论文 4 1 2m a i n t e n a n c ef o rd e l e t i n gd a t a 3 7 4 1 3m a i n t e n a n c ef o ru p d a t i n gd a t a 3 8 4 2e x p e r i m e n t 一3 8 4 2 1f e a t u r ev e c t o r ss e l e c t i v i t y 3 9 4 2 2q u e r yp e r f o r m a n c e 4 0 c h a p t e r5s u m m a r ya n df u t u r ew o r k 4 3 5 1s u m m a r y 。4 3 5 2f u t u r ew o r k 4 3 r e f e r e n c e s 4 5 a c k n o w l e d g e m e n t s 5 0 a c a d e m i cp a p e r s 5 l a c a d e m i cr e s e a r c hw o r k 5 2 产l川叫jlili- ， 由于网络技术的不断发展，w e 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 数据库一样，如何建立高效的索引成为时态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 索引技术t f i x 。它的基本思想是在处理查询时，只在 文档中可能包含查询结果的部分进行搜索，避免遍历整个文档。对于大的时态 x m l 文档，本文首先枚举出所有深度为k 的子文档片，k 是索引的参数且为整 数，以特征向量来表征每一个文档片，计算出各个文档片的特征向量并作为键值 插入到b + 树中建立索引。索引在处理查询时，同样将小枝查询看作是一棵查询 树，计算出特征向量，以此在b + 树进行匹配，查找出所有可能包含查询结果的 子文档片集，最后只在这个中间结果集中进行简单遍历即可得到最终结果集。本 文所使用的特征向量包含如下几个分量：文档片根结点名称、文档图对应矩阵的 最大最小特征值和根结点有效时间。它是基于图论中的基本结论和时态x m l 文 山东大学硕士学位论文 档自身的性质提出来的。本文详细讨论了t f i x 索引的构造、查询和维护的算法 过程，并通过实验对比，验证索引的性能。 本文的创新之处在于，提出一个特征向量并利用它的筛选作用，减少查询时 需要遍历的范围，提高索引的查询处理性能。这种思路与结点记录类和结构摘要 类索引的构造思想有所区别，但在t f i x 索引构造过程中也借鉴了计算结构摘要 ， 的理论，提出适合本索引的双拟概念。实验结果表明t f i x 索引具有较突出的查 询性能。 关键词：时态x m l 索引：t f i x 索引：查询；索引维护 r e p r e s e n t i n gd a t a ，a n dc a nb eu s e da sa ni n t e r m e d i a t ef o r m a tf o ra l lp l a t f o r m s x m l d a t a b a s et e c h n o l o g yh a sb e e nd e v e l o p m e n tw e l lw i t l lal a r g en u m b e ro fo u t s t a n d i n g a c h i e v e m e n t s i ti sp r a c t i c a ls i g n i f i c a n tt oi n t r o d u c et i m ei n f o r m a t i o ni n t ox m ld a t a b e c a u s et i m ei sa ni m p o r t a n te l e m e n to fc o m m e r c i a la p p l i c a t i o n sa n dc a l lb eu s e dt o r e p r e s e n tv a l i dt i m eo fd a t a t e m p o r a lx m l d a t a b a s ei st h ee x t e n s i o no ft h ex m l d a t a b a s eb yi n c r e a s i n gt h es u p p o r to ft e m p o r a lp r o p e r t i e s i tc a l lt r a c kh i s t o r i c a ld a t a , o rr e s t o r et h ed a t at os t a t eo fa n yt i m eb e f o r e r e s e a r c h e r sa r em o r ea n dm o r e c o n c e m e da b o u tt h et e m p o r a lx m ld a t a b a s e sb o t hh o m ea n da b r o a d t h ed e m a n do fq u e r yp r o c e s s i n ga b i l i t yi si n c r e a s i n ga st h ea m o u n to fd a t a b e c o m e sl a r g e ra n dl a r g e ro v e rt i m e h o wt ob u i l de f f i c i e n ti n d e x e sb e c o m e sa n i m p o r t a n ti s s u ef o rt e m p o r a lx m ld a t at e c h n o l o g ya s f o rn o n t e m p o r a lo n e s i n t e m p o r a lx m li n d e xa r e a s ，m o s to ft h e mg e n e r a t ean e wv e r s i o nw h e nu p d a t i n g t e m p o r a lx m l d o c u m e n ta n dn e e dt ot r a v e r s ed i f f e r e n tv e r s i o n st oc o m p l e t eq u e r y p r o c e s s i n g w h i l eo t h e r s f o c u so nd r a w i n go nt h en o n - t e m p o r a lx m ld a t a b a s e i n d e x i n gt e c h n o l o g yt oe x t e n dt h e mt ob u i l dt e m p o r a li n d e xb ya d d i n gt e m p o r a l s u p p o r tt oq u e r yp r o c e s s i n ga n di n d e xm a i n t e n a n c er e s p e c t i v e l y t h en o n - t e m p o r a l x m li n d e x e sc a nb ec l a s s i f i e di n t ot w oc a t e g o r i e s ，n o d e - r e c o r d - s t y l ei n d e xa n d s t r u c t u r a l s u m m a r y - s t y l e i n d e x t h e s ei d e a so fc o n s t r u c t i n gi n d e xa r eg o o d e n l i g h t e n i n gf o rt h et e m p o r a lx m 儿i n d e x i n gt e c h n o l o g ya tt h ei n i t i a ls t a g e i nt h et e m p o r a lx m lm o d e lu s e di nt h i sp a p e r ，w es t o r ed a t aw i t hd i f f e r e n tv a l i d t i m ei nt h es a m ed o c u m e n t ，r a t h e rt h a nt i m e d i v i s i o nv e r s i o no fd a t ai sk e p ts e p a r a t e t h i sp a p e rp r e s e n t san e wt e m p o r a lx m li n d e x i n gt f i xm a k i n gg o o du s eo ft h e t e m p o r a lc h a r a c t e r i s t i c so fx m ld o c u m e n t s i t sb a s i ci d e ai st h a t i nd e a l i n gw i t h i i i q u e r i e s ，i to n l ys e a r c h e st h ep a r t sm a yc o n t a i nq u e r yr e s u l t sr a t h e rt h a nt r a v e r s et h e e n n r ed o c u m e n t f o rl a r g e t e m p o r a lx m ld o c u m e n t s ，w ef i r s te n u m e r a t ea l l s u b - d o c u m e n tc h i p sw h o s ed e p t hi skt h ep a r a m e t e rt f i xi n d e x , a n du s ef e a t u r e v e c t o rt oc h a r a c t e r i z ee a c hc h i p w ec a l c u l a t ef e a t u r ev e c t o rf o r e v e r yd o c u m e n tc h i p a n di n s e r t e di n t ob + t r e ea sa k e yt ob u i l di n d e x w h e nd e a l i n gw i t hq u e r i e s ，w ea l s o c o n s i d e rt h et w i gq u e r ya sq u e r yt r e et oc a l c u l a t et h ef e a t u r ev e c t o r , a n dd ot h e m a t c h i n gi nb + t r e et of i n do u td o c u m e n tc h i ps e te a c ho fw h i c hm a yc o n t a i nq u e r y r e s u l t a tl a s tw e j u s tn e e dt ot r a v e r s ee a c hc h i pi nt h i si n t e r m e d i a t er e s u l ts e ts i m p l v t oo b t a i nt h ef i n a lr e s u l t s t h ef e a t u r ev e c t o rf o r w a r d e di n t h i s p a p e rc o n t a i n s f o l l o w i n gs e v e r a lc o m p o n e n t s ：t h en a m eo fd o c u m e n tr o o tn o d e ，t h em a ) 【i m u m 锄d m i n i m u me i g e n v a l u eo ft h ec o r r e s p o n d i n gm a t r i xo fd o c u m e n tg r a p ha n dv a l i dt i m e o fr o o tn o d e t f i sb a s e do nb a s i cg r a p ht h e o r ya n dt h en a t u r eo f t e m p o r a lx m l d o c u m e n t t h i sp a p e rd i s c u s s e st h et f i xi n d e xc o n s t r u c t i o n ，q u e r yp r o c e s s i n ga n d i n d e xm a i n t e n a n c e a l g o r i t h m s a n d v e r i f y t h e p e r f o r m a n c eo ft h ei n d e xv i a e x p e r i m e n t t h ei n n o v a t i o no ft h i sp a p e ri sp r o p o s i n ga f e a t u r ev e c t o rw i t hp r u n i n ge f f e c tt o r e d u c es c o p eo ft r a v e r s ea n di m p r o v eq u e r yp r o c e s s i n gp e r f o r m a n c e t h ei d e ah e r ei s d e f e r e n tf r o mt h a to fs t r u c t u r a l s u m m a r y s t y l ei n d e x ，b u tw ea l s op u tf o r w a r d b i s i m u l a t i o nc o n c e p tf o rc e r t a i np u r p o s e e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ei n d e xh a s p r o m i n e n tq u e r yp e r f o r m a n c e k e y w o r d s ：t e m p o r a lx m li n d e x ；t f i xi n d e x ；q u e r y ；i n d e xm a i n t e n a n c e i v _ 在x m l 数据库发展初期主要是通过扩展关系数据库来实现对x m l 数据的支持。 在众多的商业应用中，时间作为一种备受关注的属性，被引入到数据库中具有现 实的意义。这类数据库称为时态舭数据库，它可以跟踪历史信息和恢复文档 在以前任意时刻的状态。随着时间推移，数据量越来越大，如何迅速有效地管理 数据成为重要课题。为此，人们提出了各种各样的索引方案，来提高数据处理效 率。如何建立高效的索引已得到越来越多的关注。国内外在时态x m l 索引领域 的研究时间还不长，但已取得一些不错的成果。 1 1 1x m l 文档和x p a t h x ，数据包含在儿文档中，x m l 规范规定了文档的基本格式。x m l 文档基本组成元素有：声明、元素、注释、字符引用和处理指令，这些不同类型 的元素本文统称为数据单元。图1 1 为一个简单的x m l 文档片断，从中可以直 观地得到如下数据信息。文档中的数据单元之间存在包含和被包含的关系，呈现 层次和依赖关系。可以用一棵树来表示文档中的数据单元之间的关系，因为x m l 规范规定的结构恰好是一种树形结构，树中的每个结点对应文档中的一个数据单 元。图1 2 是图1 1 对应的x m l 文档树。 为获取x m l 文档中的数据，已提出多种查询语言，其中包x 池q l ， g l ，q u i l t ，x p a t h ，x q u r e y 等。它们主要是基于正则【2 ，3 ，4 】表达式的形式， 支持各种复杂的查询操作。这里本文主要讨论较为流行的x p a t h ，它是x q u e r y 的基础。它定义了一系列的操作，可满足对x m l 数据进行操作的基本需求。以 图1 2 为例，可以有如下简单的线性查询操作：c o m p a n y m a n a g e r n a m e ，目标是 山东大学硕士学位论文 查找出公司所有经理的名字，从图中可以方便地得到查询结果： p e t e r , w a d e ，l i n d a 。更为通常的查询模式则是大多数学者关心的小枝查询( t 、) v i g ) ， 它本身也可以看作是一棵树，这也是本文所关心的。 p e t e r m a l e w a d e m a l e l i n d a f e m a l 4 3 图1 1x m l 文档举例 p e t e r 1 1 2 时态x m l 文档和t x p a t h m a l e w a d ef e m a l l i n d a 4 3 图1 2x m l 文档树 时态x m l 文档是在x l v i l 文档基础上加入时态信息，使其数据单元具有时 间属性。文献【4 】给出了时态x m l 的数据模型，在半结构化数据中有效地表示了 一 2 乞 山东大学硕士学位论文 时间信息。时态x m l 是x m l 的子集，因此它也可以用一棵树来对应一个文档， 而且只是比x m l 文档对应的树多了一些时间标记。为了能更直观地说明时态 x m l 文档的格式，这里构造了一个时态x i v l l 文档，图1 3 为文档图。此文档表 示一个公司下面有三个分公司，每个公司里面又有相应的员工，图中的一些边上 带的方框用与表示时间，时间区间即为对应结点的有效时间，即在该信息数据在 此时间段内存在。如员工c a t e r 在0 0 和0 4 年期间为分公司b r a n c h a 效力，而0 4 到0 8 年间又转为分公司b r a n c h c 服务。又如t r e a t y 在0 0 到0 5 年和0 5 至今和 平均薪水分别为5 0 0 0 和7 0 0 0 ，名字为t r a c y 的w o r k e r 结点有两个s a l a r y 子结点， 但它们并不同时存在。不带时间约束的边，默认表示为从创建至今，即该结点一 直存在。 c a t e r4 0 0 05 5 0 0t r a c y5 0 0 07 0 0 0f e m a lt i m2 5s e l i n a 4 5 0 0 5 5 0 0 图1 3 时态舭举例 文【5 】中提出了四种将文档图映射到x m l 文档的方法，这里采用第一种自上 而下无重复方法( t o p - d o w nn o n r e p l i c a t e d ) ，可得图1 3 对应的x m l 文档如下图 ( 部分) ： c a t e r 3 山东大学硕士学位论文 4 0 0 0 5 5 0 0 图1 4 时态x m l 文档 对于时态x m l 来说同样需要对应的查询语言来满足查询要求，要从时态 x m l 文档中获取数据，就要有符合它特性的查询模式。t ) a m 查询语言是研究 者普遍认可的一种，它是从x m l 查询语言x p a t h ( 2 0 版本) 扩展而来，针对时 态x m l 的特征和需求，在x p a t h 中引入时间操作符。t x p a 1 下的查询表达式是 由一系列的( n o d e ，i n t e r v a l ) 结点对标签序列组成，相对于x p a t h 中的结点标签 序列多了一个时间区间属性，用于表达时间查询约束。文献【6 】中出了最大连续 路径的概念来定义t x p 础中的查询表达式。此定义中强调了时间区间( i n t e r v a l ) 在对查询结果的制约。以图1 3 所给的时态x m l 文档为数据源，下面举例说明 t ，a t h 查询语言。有以下查询表达式： e o m p a n y b r a n c h b w o r k e r n a m e = ”t r a c y ” s a l a r y f r o m ；， 2 0 0 0a n d t o 一 2 0 0 5 】 这个查询表达式是要找出在b r a n c h b 分公司效力的员工t r a c y 有0 0 年到0 5 年间的平均薪水。从图中可以直观地找到沿结点c o m p a n y 经过结点b r a n c h b 和 w o r k e r 最终到结点s a l a r y ，这一条最大连续路径，再由查询条件 n a m e = ”t r a c y ”】确 定唯一的可能的两个s a l a r y 结点，最后查询表达式中的时间区间约束条件为0 0 年到0 5 年，则只剩唯一结点，即值为5 0 0 0 的s a l a r y 结点。 1 2 国内外研究现状 当前，x m l 数据库无可厚非地成为学者们的研究热点，不断地有新成果被 提出，x m l 索引的性能也不断的在提升，很多优秀的索引方案问世。而在时态 x m l 领域，虽然还没得到长足的发展，但也得到越来越多的关注。时态x m l 索引方面的成果很多与非时态x m l 索引有直接的联系，非时态x m l 领域的成 果对其有很好的借鉴作用，因此本节先讨论非时态x m l 领域的成果，再对时态 4 历，当文档中存在大量的路径相同的结点时，不能够一次性定位出来所有结点。 结点记录类索引的大致思想是设计某种遍历策略，得到由结点组成的序列，节 点的标签在序列中就具有唯一的次序，将序列与某指标集建立一一映射的关系，对 应序列中某个标签就有唯一的序号；对任意两个具有节点序号信息的节点，可以构 建某种运算，该运算的结果可以表征节点间的结构关系。不同的索引往往使用不 同的序列，即不同的编码，但目的是相似的，研究者在如何建立一种高效的编码 方式上提出了很多不同方案。文献【8 ，9 ，1 0 采用区间编码的形式对x m l 树的 各结点进行编码，以先序遍历序列和后序遍历序列中的序号对组成的区间 ( p r e ，p o s t ) 进行编码，可以确定两个结点之间的祖先后裔关系。文献【4 】提出了 d e w e y 编码；文献【1 1 1 的o r d p a t h 编码都采用的是局部编码形式。文献【1 2 】则 给出了称为结构持久编码的方法，采用二进制形式编码，而不是自然数。以上几 种可以细归类为结点序号类索引，还有一类则像文献 1 3 ，1 4 ，1 5 提出的索引结 构，称为结点路径类索引，它基于路径信息来获取节点的结构关系。这类索引的 核心技术是字符串的模式匹配。因而，这类索引记录数据的管理方法，有许多是来 自于信息获取领域的。一些高效的字符串模式匹配算法被用到索引搜索中去。例 如t i l e 、p a t r i c i at r i e 、s u f f i xt r e e 、 s u f f i xa r r a y 等结构。 结构摘要类索引的大致思想是：以x m l 树结构中节点的路径信息为基础， 采取某种约简方式，使得约简后的树结构只维护一套不同的路径信息，对于路径相 同的结点都映射到约简后的树中的同一个结点。文献 1 6 】是s t a n f o r d 大学的l o r e 项目中的d a t a g u i d e ，它是结构摘要的最初形式，其基本思想是基于将n f a 转换 为d f a 的形式对x m l 数据中的相同路径进行约简。【1 7 提出的1 - i n d e x ，引入 了双似等价关系的概念，从而对结构摘要找到了形式化描述的理论基础。为了增 5 山东大学硕士学位论文 加对结构摘要树遍历的灵活性，文献【1 8 】进一步提出了f & b 索引，可以满足全部 分支路径查询的要求，但在实现上必须依赖内存。文献【1 9 】在其基础上提出基于 磁盘存储的f & b 索引。文献 2 0 1 提出了用特征向量来表征x m l 文档，再利用 b + 树建立索引，同样利用了双拟的概念，对结构复杂的x m l 文档效率优越性比 较明显。文【1 7 】中还提出了k 阶相似的概念，基于此概念建立的索引有 a ( k ) - i n d e x 21 、d ( k ) - i n d e x 2 2 、m ( k ) - i n d e x 2 3 等。 1 2 2 时态x m l 领域 时态x m l 索引领域的研究已得到越来越多的关注，学者已提出许多索引方 案和查询语言。时态x m l 的索引重点在于解决对时态信息的支持，方便实现带 有时间约束的查询。在时态x m l 索引领域，多数模型是在时态x m l 文档更新 时产生一个新版本，查询时需要遍历不同的版本，降低了查询处理的性能。一个 版本保存了一个有效时间断的数据，分离了不同阶段的数据，增加了查询代价。 文献 2 4 】中的索引方案就属这种类型，它提出一种版本索引( v e r s i o ni n d e x ) 来管理 不同版本的x m l 文档。这样，一个时态x m l 数据库中存在很多的版本，而且 随时间的推移，将会越来越大。 另一类模型则是采用把不同时间断的数据存放于同一个文档中，利用时间区 间元素来标识不同时间的数据，本文称之为结点有效时间。这样历史数据可以集 中存放，查询时不用去遍历分散在各个文档中的不同时间的数据。近来，大多数 学者主要关注这类模型下的索引研究。在这种模型基础上建立索引，目前的研究 成果主要是通过借鉴非时态x m l 数据库的索引，在原有的索引方案中引入时间 元素，来支持时态x m l 索引的时态查询。近几年国内外发表了很多这类作品， 有些已得到不错的实验结果。与非时态x m l 索引类型相对应，时态x m l 索引 也有两大类，一种是借鉴前者中的结点记录类型索引，另一种则是借鉴前者中的 结构摘要类型索引。 文献 2 5 1 通过讨论时态x m l 查询数据模型t x q d m ，提出了基于结点有效 ， 时间的前缀编码方案，并引人t x q d m 结点间的基于时态连通的等价关系和基 一 于时态包含的拟序关系，建立了时态x m l 索引数据模型t x i d m 。显然它属于 结点记录类时态x m l 索引，这种类型的还有文献【2 6 】利用区间树( i n t e r v a l t r e e ) 6 建立的时态 据库上的有 还有一些成果可归类为结构摘要类时态x i v l l 索引。文献 2 7 1 采用了文献 2 8 】 提到的文档模型，提出t e m p i n d e x 时态x m l 索引。对于x m l 文档的更新，不 保存一个新的版本，而是直接在文档上采用不同的边去连接不同的上一级节点， x m l 文档树中的边上保存着该关联成立的有效时间，它借鉴1 - i n d e x 索引，对文 档中的节点划分等价类，简化文档树结构中的路径信息。文献 2 9 1 提出了一种基 于扩展时态x m l 模型的索引技术。它同样是将时态x m l 文档分成多个等价类， 只是它是基于一种扩展的等价关系。在文献 3 0 1 中，利用基于磁盘的f & b 索引 的优点，对它进行扩展，加入时间的处理，并提出索引t f & b 。而在文章【3 l 】中 将时态x m l 文档转换到1 1 维空间的节点和直线，使用u b t r e e ( u n i v e r s a lb t r e e ) 对这些n 维空间的节点和直线进行索引，用空间中一个专门的维度表示文档的 时态信息，u b t r e e 是在多维空间中快速定位结点的索引技术 1 3 本文的主要工作 本文致力于时态x m l 索引方面的研究，提出一种新的索引方案：t f i x ，基 于特征向量的时态x m l 索引。本索引的目的在于对查询深度不大于k 且查询表 达式中不包含“”的查询子集( 在2 1 2 小节中定义) 提供高效解决方案。在时 态x m l 数据库中，t f i x 索引可以作为一种辅助索引，致力于解决此类查询。 本文详细介绍了t f i x 索引构造的理论依据、构造算法过程、查询处理算法，以 及索引的维护工作，最后通过实验说明索引具有较为突出的性能表现。 t f i x 索引的基本思想是在查询时，很快定位到时态x m l 文档中可能包含 查询结果的部位进行搜索，避免遍历整个文档。为了能迅速定位到这些地方，本 文将大的时态x m l 文档分解开来，枚举出来所有深度为k 的子文档片，以特征 向量来表征每个文档片，并以它为键插入b + 树构造索引。索引构建思路有别于 结构摘要类和结点记录类索引的构造思想。处理查询时，同样计算出来查询树的 特征向量在b + 树中找出所有可能包含查询结果的文档片集合，最后只对这个中 间结果集进行搜索即可得到最终的结果集。本文的特征向量是基于图论中的基本 结论和时态x m l 文档本身的性质提出的，格式为( r o o t ，九畎，九加，i m w v a l ) ，r o o t 7 山东大学硕士学位论文 代表子文档根结点名称，中间两个分量是子文档片转化为所对称矩阵后得到的最 大最小特征值，i n t e r v a l 则是根结点的有效时间区间。本文将详细阐述特征向量 的理论依据。 1 4 本文的组织结构 本文的组织结构如下： 第一章绪论，主要介绍本课题的研究背景和研究现状，并简要说明了本文的 主要工作。 第二章详细讨论了t f i x 索引的理论基础，主要是索引所采用特征向量的理 论依据，并给出完整的索引构造算法。 第三章讨论利用t f i x 索引进行处理小枝查询的算法过程，并以典型的时态 查询的例子来说明算法步骤。 第四章主要是介绍数据库中数据更新后的索引维护算法，针对数据增加，数 据删除和数据更新三方面分别讨论索引的更新策略。 第五章为本文最后一章，主要是对论文的工作进行总结，并对未来工作的一 个展望。 8 一 在时态 的成果。索 文也将提出 程和更新维 本文提 引做法有点 来化简文档 枚举出所有满足要求的小文档片，以一个特征向量来表征每一个小文档片，并以 此向量作为一个键值，利用b + 树建立索引。同时也由于对大文档进行了分解， 查询处理的对象变成这些子文档，造成索引可处理的查询对象的范围也有所限 制。本文的工作重点在于力争提出一种高效解决一个较大的查询子集的方案。 要建立t f i x 索引，首先要解决以下两个问题： ( 1 ) 如何选择一个合适的向量作为特征向量来表征小文档片： ( 2 ) 如何避免子文档片中可能存在的