（计算机科学与技术专业论文）支持数据更新的xml结构连接的编码方案研究.pdf

r e s e a r c ho nl a b e l i n gs c h e m eo fx m lc o n t a i n m e n tj o i n f o ru p d a t e - - s u p p o r t i n g at h e s i ss u b m i t t e df o rt h ed e g r e eo fm a s t e r c a n d i d a t e ：j i an a n s u p e r v i s o r ：a s s o c i a t ep r o f w e id o n g p i n g c o l l e g eo fc o m p u t e r & c o m m u n i c a t i o ne n g i n e e r i n g c h i n au n i v e r s i t yo f p e t r o l e u m ( e a s t c h i n a ) 、 黍警t，fj-， 墨k 、 节、 丫 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名 曼御 日期：f1 年妨弓。日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版 和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和 复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他 复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签 指导教师签名： 日期：刀fj 阵珀, j o b 日期：加f | 年广月弓口日 譬、 冀 摘要 随着x m l 已成为互联网上数据存储和信息交换领域事实上的标准，人们已经开始 习惯使用x m l 文档来存储、管理i n t e m e t 上的海量信息资源，因而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 数据更新的前缀编码方案i d s u ( i m p r o v e dd e w e y - l a b e l i n g s c h e m ef o r u p d a t e s u p p o r t i n g ) 。通过扩展d e w e y 编码，它将x m l 文档树中的每一个节点赋予一个 二元组 ，其中i d s u i d 表示节点的编码，其初始形式与d e w e y 编码相 同；d e p t h 表示节点在文档树中所处的层数，用来加速结构连接操作。该编码方案不仅 高效地支持结构查询，能够快速准确的判断x m l 文档结构树中任意两个节点之间的父 子、祖先子孙以及兄弟关系，并且针对x m l 文档树频繁更新后重新编码的情况，设计 了一种“编码相加”的更新规则，避免了更新操作带来的编码调整问题，可以更有效地支 持x m l 文档数据更新。 为验证i d s u 编码方案的有效性，我们做了一些对比性实验。将i d s u 编码方案和其 他编码方案，在编码的时间、空间、查询、更新性能方面进行了全面、细致的比较分析。 实验结果表明，i d s u 编码在应对x m l 数据更新方面具备良好的优势，能有效的支持数 据更新，完全避免重新编码，另外在结构查询方面，也有上佳的表现。 本文的i d s u 编码方案是在解决x m l 编码方案应对数据更新问题的有效尝试，对今 后进一步的研究和实际应用都具有重要的参照意义。 关键词：x m l ，编码方案，数据更新 、 t ” r e s e a r c ho nl a b e l i n gs c h e m eo fx m l c o n t a i nm e n tj o i nf o r u p d a t e - s u p p o r t i n g j i an a n ( 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 ep r o f w e id o n g p i n g a b s t r a c t a sx m lh a sb e c o m et h ed ef a c t os t a n d a r do fd a t as t o r a g ea n di n f o r m a t i o ne x c h a n g eo n i n t e r a c t ，p e o p l eh a v eg o tu s e dt oa p p l y i n gt h ex m l d o c u m e n tt os t o r e ，m a n a g ev a s ta m o u n t s o fi n f o r m a t i o no ni n t e m e t c o n s e q u e n t l yw e bi sg r a d u a l l yt r a n s f o r m e di n t oal a r g ex m l d o c u m e n td a t a b a s e h o we f f e c t i v e l ys t o r ea n dq u e r yx m ld o c u m e n th a sb e c o m eah o t r e s e a r c hf i e l di nx m ld a t a b a s e i no r d e rt oe f f e c t i v e l ys u p p o r tt h ex m lq u e r y , e s p e c i a l l yt h es t r u c t u r a lq u e r y , an u m b e r o fl a b e l i n gs c h e m eo fx m ld o c u m e n t si sp r o p o s e da tp r e s e n t b u ti na c t u a la p p l i c a t i o nx m l d o c u m e n td a t ai sf r e q u e n t l yu p d a t e d ，w h i c ht a k e sal o to ft i m ec o s to fr e e n c o d i n g ，s e r i o u s l y a f f e c t i n gt h ee f f i c i e n c yo fx m lq u e r y i nt h i sp a p e r , a ni m p r o v e dd e w e y - l a b e l i n gs c h e m ef o ru p d a t e s u p p o r t i n g ( i d s u ) i s p r o p o s e dt ob a l a n c et h eq u e r ye f f i c i e n c yw i t hu p d a t ee f f i c i e n c yi nx m l d o c u m e n t s ，b a s e do n t h o r o u g ha n a l y s i so ft h ee x i s t i n gx m l d o c u m e n tl a b e l i n gs c h e m e b ye x t e n d i n gd e w e y c o d i n gs c h e m e ，i tg i v e se a c hn o d eo fx m l d o c u m e n tt r e eau n i td o u b l e t ， i d s ui dm e a n st h ee n c o d i n gn o d e s ，t h ei n i t i a lf o r mi ss a m ea sd e w e ye n c o d i n g ；d e p t h i n d i c a t e st h en o d et h en u m b e ro fl a y e r si nt h ed o c u m e n tt r e e ，w h i c hi su s e dt os p e e du pt h e s t r u c t u r a lj o i no p e r a t i o n t h el a b e l i n gs c h e m ec a l ln o to n l ys u p p o r ts t r u c t u r eq u e r i e se f f i c i e n t l y , b u ta l s oq u i c k l ya n da c c u r a t e l yd e t e r m i n et h er e l a t i o n s h i po fa n yt w on o d e si nt h ex m l d o c u m e n tt r e ea m o n gf a t h e r s o n , a n c e s t o r s d e s c e n d a n t sa n db r o t h e r s ，m e a n w h i l e ，f o rt h e s i t u a t i o no ff r e q u e n tu p d a t ea n dr e - e n c o d i n g ，a p p l ya n e w u p d a t er u l e sc a l l d c o d ea d d i t i o n ”t o a v o i dc o d ea d j u s t m e n ta f t e ru p d a t eo p e r a t i o n ，e f f e c t i v e l ys u p p o r t i n gu p d a t eo fx m l d o c u m e n td a t a t ov a l i d a t et h ee f f e c t i v e n e s so ft h ep r o p o s e di d s ul a b e l i n gs c h e m e ，w ea r r a n g e dal a r g e n u m b e ro fc o m p a r a t i v ee x p e r i m e n t sf r o mt h ee n c o d i n gt i m e ，e n c o d i n gs p a c et oq u e r ya n d u p d a t ep e r f o r m a n c e ，t h ec o m p r e h e n s i v e l ya n dc o m p a r a t i v e l ya n a l y s i sb e t w e e nt h e s el a b e l i n g s c h e m ea n de x i s t i n gl a b e l i n gs c h e m e s t h ee x p e r i m e n tr e s u l t ss h o wt h a t ，i d s uh a sg o o d a d v a n t a g e si nt h ex m ld a t au p d a t i n g ，m e a n w h i l e ，e f f e c t i v e l ys u p p o r td a t au p d a t e sa n d c o m p l e t e l ya v o i dr e e n c o d i n g ，f u r t h e r , t h e r ei sa l s oag o o dp e r f o r m a n c ei ns t r u c t u r a lq u e r y t h ep r o p o s e di d s ul a b e l i n gs c h e m ei sa ne f f e c t i v ea t t e m p ti ns o l v i n gt h ep r o b l e mo f d a t au p d a t eo ft h ex m l l a b e l i n gs c h e m e ，a n dg i v ea ni m p o r t a n tr e f e r e n c es i g n i f i c a n c eo f f u r t h e rr e s e a r c ha n dp r a c t i c a la p p l i c a t i o n s 、 心， k e yw o r d s ：x m l ，l a b e l i n gs c h e m e ，d a t au p d a t e - p _ 目录 第一章绪论j 1 1 1 研究背景及意义一l 1 2 国内外研究现状。2 1 3 论文的主要研究内容和创新4 1 4 论文的组织结构4 第二章x m l 文档编码机制的相关研究。6 2 1x m l 文档基础理论6 2 1 1x m l 文档及其数据模型6 2 1 2x m l 文档的查询9 2 1 3x m l 文档的解析1 2 2 2x m l 文档编码机制一l3 2 2 1 基于区间的编码机制1 4 2 2 2 基于路径的编码机制1 5 2 2 3 编码机制的衡量标准18 2 3 数据更新问题的研究分析1 9 2 3 1 问题的提出19 2 3 2 解决数据更新的方法1 9 2 4 小结2 1 第三章i d s u 编码方案的研究与设计2 2 3 1 问题的提出2 2 3 2 基本定义及定理2 4 3 3i d s u 编码2 6 3 3 1 编码的定义2 6 3 3 2 编码的存储代价分析2 8 3 4 编码对数据更新的支持2 8 3 4 1 更新规则2 9 3 4 2 更新算法描述一3 0 3 5 编码对结构查询的支持31 3 5 1 祖先子孙关系的判断3 l 3 5 2 父子关系的判断3 2 3 5 3 兄弟关系的判断3 3 3 6 爿、结3 3 第四章实验分析及性能测试3 4 4 1 实验环境及配置3 4 4 2 实验系统流程3 5 4 3 性能分析比较3 7 4 3 1 时间性能分析3 8 4 3 2 空间性能分析。：3 8 4 3 3 查询性能分析3 9 4 3 4 更新性能分析一4 0 4 4d 、 结4 1 结论4 2 参考文献4 4 攻读硕士学位期间取得的学术成果4 8 致谢4 9 中国石油大学( 华东) 硕士学位论文 1 1 研究背景及意义 第一章绪论 目前，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 ，可扩展标记语言) 【l 】已成为互联网上数 据存储和信息交换领域事实上的标准。x m l 由于自身的可扩展性、自描述性、简单性 和开放性等突出优点，使得人们习惯应用x m l 文档来存储、管理i n t e r a c t 上的海量信 息资源，因而w e b 也正逐步转化为一个庞大的x m l 文档数据库。 查询是数据库使用最为频繁的操作，即如何对x m l 文档进行有效的存储、检索， 正成为当前n a t i v ex m l 数据库领域研究的热点1 2 1 。但x m l 文档本身的半结构化、有序、 嵌套等特点，却对传统数据管理技术提出了前所未有的挑战。 针对x m l 文档这种采用树状数据模型的查询( 如图1 1 所示) ，国内外研究学者提 出了多种查询语言，如：x p a t h 3 1 ，x q u e r y 4 1 ，l o r e l t 5 1 ，q u i l t t 6 1 等。虽说这些语言形式各 不相同，但在实现x m l 结构查询时，都采用了正则路径表达式的核心技术进行x m l 文档的定位，而这一技术实现的基础是x m l 文档中元素或属性节点的祖先后代关系或 父子关系的快速判断。 j i m j a c kt o ml i l y x ul i ul i l u c yl i l y m i k e 图1 - 1x m l 文档的数据模型 f i g l - i d a t am o d e lo fx m ld o c u m e n t 例如以下对路径q 的查询： q ：s c h o o l 木s t u d e n t n a m e = j a c k 传统的处理方式是采用导航的方式对x m l 文档树遍历。例如上述查询处理q ：从 s c h o o l 首节点开始依次遍历所有的子孙节点，从中查找s t u d e n t 节点，若找到则再从查 出的节点中找出属性n a m e = ! j a c k ”的子节点。显而易见，这种基于导航的查询效率是很 r 第一章绪论 低的。而解决这个问题的一个重要思路是对节点进行有效的编码。 编码作为加速x m l 查询处理的一种重要手段，通过对x m l 文档树中的元素、属 性和相关语义实体进行编码，从而直接判断两个节点之间的祖先子孙、父子、兄弟关系， 而不是对原x m l 文档树进行遍历。这种方法较为直观，而且编码比较计算速度快，完 全适应x m l 路径查询分解计算的基本要求，倍受研究学者的青睐。而这种为x m l 文 档树节点分配唯一编码的具体策略也称之为编码方案( 机制) | 2 2 1 。因此，x m l 文档编 码方案是实现n a t i v ex m l 数据库【2 0 】高效查询的重要条件，对它的研究具有非常重要的 理论意义和实践意义。 1 2 国内外研究现状 在x m l 数据存储和查询中使用编码对x m l 文档进行查询优化，在近几年取得了 很大的理论成果，一些针对x m l 文档树的编码方案相继提出，这些编码方案都是使用 特定的编码策略对x m l 文档树中的元素、属性和相关语义实体进行编码，利用编码唯 一标识实体，从而直接判断出x m l 文档树节点间的基本结构关系【2 1 1 。目前已经提出的 编码方案有d i e t z 编码【