（计算机应用技术专业论文）支持高效动态更新的xml数据编码方法研究.pdf

t h e s i sf o rm a s t e rd e g r e e ，2 011 s c h o o lc o d e ：1 0 2 6 9 s t u d e n tn 0 ：5 1 0 8 1 2 1 1 0 0 2 e a s tc h i n an o r m a l u n i v e r s i t y r e s e a r c ho nh i g he f f i c i e n c y u p d a t e - s u p p o r t i n g x m ld a t a e n c o d i n gm e t h o d s d e p a r t m e n t ： q 望望坠! 曼! g 星旦! 曼! q s i s g m a j o r ： r e s e a r c ha r e a ：w e ba p p l i c a t i o nt e c h n o l o g y s u p e r v i s o r ： c a n d i d a t e ： e a s tc h i n an o r m a lu n i v e r s i t y c o m p l e t e d i nn o v 2 010 华东师范大学学位论文原创性声明 郑重声明：本人呈交的学位论文支持高效动态更新的x m l 数据编码方法 研究，是在华东师范大学攻读硕博士( 请勾选) 学位期间，在导师的指导下 进行的研究工作及取得的研究成果。除文中已经注明引用的内容外，本论文不包 含其他个人已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和 集体，均已在文中作了明确说明并表示谢意。 作者签名： 日期：矽矿年fj 月计日 华东师范大学学位论文著作权使用声明 支持高效动态更新的x m l 数据编码方法研究系本人在华东师范大学攻 读学位期间在导师指导下完成的谤，士博士( 请勾选) 学位论文，本论文的研究 成果归华东师范大学所有。本人同意华东师范大学根据相关规定保留和使用此学 位论文，并向主管部门和相关机构如国家图书馆、中信所和“知网 送交学位论 文的印刷版和电子版；允许学位论文进入华东师范大学图书馆及数据库被查阅、 借阅；同意学校将学位论文加入全国博士、硕士学位论文共建单位数据库进行检 索，将学位论文的标题和摘要汇编出版，采用影印、缩印或者其它方式合理复制 学位论文。 本学位论文属于( 请勾选) ( ) 1 经华东师范大学相关部门审查核定的“内部”或“涉密”学位论文宰， 于年月日解密，解密后适用上述授权。 2 不保密，适用上述授权。 导师签名5 盘本人签名茎簋本人签名立2 芰 印p 年f 月矸日 宰“涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定 过的学位论文( 需附获批的华东师范大学研究生申请学位论文“涉密”审批表方 为有效) ，未经上述部门审定的学位论文均为公开学位论文。此声明栏不填写的，默认 为公开学位论文，均适用上述授权) 。 黄俊硕士学位论文答辩委员会成员名单 姓名职称单位备注 杨宗源教授华东师范大学信息学院主席 朱敏高级工程师华东师范人学信息学院 陈志云副教授华东师范犬学信息学院 华东师范大学2 0 11 届研究生硕士学位论文论文摘要 论文摘要 随着计算机和网络技术的不断发展，x m l 技术的应用得到了不断的扩展，它 事实上已经成为数据交换的标准和s o a 架构的基石。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 数据 编码方法对这一点都不能提供很好的支持，本文就此进行了相关方面的研究。 本文分析比较了当前几种比较流行的数据编码方法，提出了一种新的高效的 支持动态更新的) ( m l 数据编码方法。该编码方法不仅能够快速准确判断x m l 文档 结构树中任意两个结点之间的关系、计算结点所在的层次，而且在插入结点时的 二次编码率为零。 本文的主要工作如下： ( 1 ) 对现有的编码方法进行深入的比较分析，指出这些编码方法的不足和在 支持) ( m l 文档树动态更新上的缺陷。 ( 2 ) 提出了一种新的支持动态更新的高效编码方法，该方法是前缀编码和奇 偶编码的一种扩展和变形，该方法采用的编码方案中的结点编码包含以下三个部 分：前缀码、奇偶码和顺序码。把当前结点的父亲结点的编码去除结点码间连接 符“ 后的字符串当作当前结点的前缀码，同一父结点下的所有子结点的前缀 码都相同，前缀码在判断父子关系、兄弟关系和祖先后裔关系有重要作用，具 有前缀编码的优点；奇偶码的初始值为“l 。当在x m l 文档中插入结点时，奇偶 码的编码规则根据实际需要分为高频率更新和大幅度更新，为了区别高频率更新 和大幅度更新，引入插入结点间隔因子o t ，根据间隔因子来高效支持x m l 文档的 动态更新；顺序码是由字母字符串组成的编码，静态编码算法中顺序码表示x m l 文档中兄弟结点的顺序，动态编码算法中顺序码表示兄弟结点顺序的同时又用于 区分前缀码和奇偶码相同的结点。 ( 3 ) 详细阐述了论文提出的编码方案的相关定义及其实现算法；对编码的特 性进行了详细介绍，给出了编码更新算法，并结合实例分类讨论了插入结点后编 华东师范大学2 0 11 届研究生硕士学位论文 论文摘要 码的更新情况。 ( 4 ) 结合提出的编码方案提出了一种效率较高的x m l 数据存储策略，并结合 提出的编码方法阐述了在这种存储模式下具体的x m l 数据查询过程。 ( 5 ) 通过实验，将本文编码方法与已有编码方法进行了时间性能、空间性能、 二次编码率及查询性能等方面的比较分析。 关键词：x m l 存储，x m l 查询，x m l 编码，动态更新，二次编码率 a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e ra n dn e t w o r kt e c h n o l o g y , x m lt e c h n o l o g y h a sb e e ne x t e n d e dc o n t i n u o u s l ya n di th a sb e c o m et h ed a t ae x c h a n g es t a n d a r d sa n d t h ef o u n d a t i o no fs o a a r c h i t e c t u r ei nf a c t a sas p e c i a ls e m i - s t r u c t u r e dd a t a ，x m l i s d i f f e r e n tf r o mt h ed a t ai nr e l a t i o n a ld a t am o d e l x m ld a t a b a s ei sac o l l e c t i o no fx m l d a t ai nw h i c ht h ed a t ai sp e r s i s t e n ta n do p e r a b l e h o wt os t o r ea n dq u e r yx m l d a t a e f f e c t i v e l yi sa ni m p o r t a n ta s p e c to fx m l d a t a b a s e ，w h i c hw i l la f f e c tt h ee f f i c i e n c yo f t h es y s t e m t h es t o r a g ea n dq u e r yb a s e do ns o m es p e c i a le n c o d i n gm e t h o dh a s b e c o m eo n eo ft h eh o ti s s u e si nt h ed a t ar e s e a r c hf i e l db e c a u s eo fi t sw i d ea p p l i c a t i o n s i n t e r - z o n e b a s e de n c o d i n gm e t h o da n dp a t h - b a s e de n c o d i n gm e t h o da r et h et w o t y p e se n c o d i n gm e t h o d sf o rt h ex m l d o c u m e n tt r e e x m ld o c u m e n tt r e en e e d st ob e u p d a t e dd y n a m i c a l l ya c c o r d i n gt ot h ea p p l i c a t i o nr e q u i r e m e n t sa n dt h ec u r r e n tx m l d a t ae n c o d i n gm e t h o d sc a nn o ts u p p o r ti tw e l l t h i sp a p e rc a r r i e do u tr e l e v a n t r e s e a r c h a f t e rc o m p a r i n gs e v e r a lp o p u l a rc u r r e n td a t ac o d i n gm e t h o d s ，t h i sp a p e r p r o p o s e d an e we f f i c i e n tx m ld a t ae n c o d i n gm e t h o dw h i c hs u p p o r t e dd y n a m i c u p d a t i n g t h ee n c o d i n gm e t h o dc a nd e t e r m i n et h er e l a t i o n s h i pb e t w e e na n yt w o n o d e sa n dc o m p u t et h el e v e lo fan o d ei nt h ex m ld o c u m e n tt r e eq u i c k l ya n d a c c u r a t e l y , a n dk e e pt h er e e n c o d i n gr a t et oz e r ow h e ni n s e r t i n gn o d e st ot h ex m l d o c u m e n tt r e e t h em a i nw o r ki sa sf o l l o w s ： ( 1 ) b yc o m p a r i n gs e v e r a lp o p u l a re n c o d i n gm e t h o d ，t h i sp a p e rp o i n t e do u tt h e d e f i c i e n c i e sa n dt h el i m i t a t i o no ft h o s em e t h o d si ns u p p o r t i n gd y n a m i cu p d a t eo f x m ld o c u m e n tt r e e ( 2 ) t h i sp a p e rp r o p o s e dan e we f f i c i e n te n c o d i n gm e t h o dw h i c hs u p p o r t e d d y n a m i cu p d a t i n g t h en e wm e t h o dw a s a ne x t e n s i o na n dd e f o r m a t i o no ft h ep r e f i x e n c o d i n gm e t h o da n dp a r i t ye n c o d i n gm e t h o d t h en o d e sc o d eo ft h ee n c o d i n g s c h e m eu s e di nt h en e wm e t h o dw a sc o n s i s t e do ft h ef o l l o w i n gt h r e ep a r t s ： p r e f i x c o d e ，p a r i t y - c o d ea n do r d e r - c o d e t h e c u r r e n tn o d e sp r e f i x - c o d ew a st h es t r i n g o fi t sf a t h e r sc o d ew i t h ”b e i n gr e m o v e d t h en o d e s c o d e sw e r et h es a m ei ft h e y i u h a dt h es a m ef a t h e rn o d e t h ep r e f i x c o d ep l a y e da l li m p o r t a n tr o l ei nd e t e r m i n i n g p a t e r n i t y , b r o t h e r h o o da n da n c e s t o r d e s c e n d a n tr e l a t i o nb e t w e e nn o d e s i th a dt h e a d v a n t a g e so ft h ep r e f i xc o d e ；p a r i t y - c o d eh a dt h ei n i t i a lv a l u eo f ”1 ”t h ee n c o d i n g r u l eo fp a r i t y - c o d ew a sd i v i d e di n t oh i g h f r e q u e n c yu p d a t i n ga n dv a s t n u m b e r u p d a t i n gw h e ni n s e r t i n gn o d e si n t ot h ex m l d o c u m e n tt r e e i no r d e rt od i s t i n g u i s h t h e m t h ei n t e r v a lf a c t o r 口w a si n t r o d u c e d t h ei n t e r v a lf a c t o rw a su s e dt os u p p o r t t h ee f f i c i e n td y n a m i cu p d a t i n go fx m ld o c u m e n t s t h eo r d c r - c o d cw a sc o m p o s e do f l e t t e r s t h eo r d e r - c o d ei n s t a t i ce n c o d i n ga l g o r i t h mi n d i c a t e dt h eo r d e ro fs i b l i n g n o d e si nt h ex m ld o c u m e n t t h eo r d c r - c o d ci nd y n a m i ce n c o d i n ga l g o r i t h mw a s u s e dt od i s t i n g u i s ht h en o d e sw h e nt h e yh a dt h es a m ep r e f i x c o d ea n dp a r i t y - c o d e ，a s w e l lt oi n d i c a t et h eo r d e ro fs i b l i n gn o d e s ( 3 ) t h er e l a t e dd e f i n i t i o n sa n da l g o r i t h m sf o rt h ep r o p o s e de n c o d i n gs c h e m ea r e e x p l a i n e d i nd e t a i l t h ec h a r a c t e r i s t i c so ft h ee n c o d i n gm e t h o dw e r ed i s c u s s e d t h o r o u g h l y t h ee n c o d i n gu p d a t i n ga l g o r i t h mw a sp r o p o s e d ，a n dt h ee n c o d i n gu p d a t e d e t a i l sa f t e ri n s e r t i n gn o d e sa r ee x p l a i n e db ye x a m p l e s ( 4 ) c o m b i n e dw i t ht h ep r o p o s e de n c o d i n gs c h e m e ，am o r ee f f i c i e n tx m l d a t a s t o r a g es t r a t e g yw a sp r o p o s e d t h es p e c i f i cx m l d a t aq u e r yp r o c e s sf o rt h es t o r a g e m o d ew a se x p l a i n e db a s e do nt h ep r o p o s e d e n c o d i n gm e t h o d ( 5 ) t h r o u g he x p e r i m e n t s ，t h ee n c o d i n gm e t h o dp r o p o s e di n t h i s p a p e rw a s c o m p a r e dw i t h t h e e x i s t e n te n c o d i n gm e t h o d si n t h ef o l l o w i n ga s p e c t s ：t i m e p e r f o r m a n c e ，s p a c ep e r f o r m a n c e ，t h er e e n c o d i n g r a t ea n dq u e r yp e r f o r m a n c e k e y w o rds ：x m ls t o r a g e ，x m lq u e r y , x m le n c o d i n g ，d y n a m i cu p d a t i n g ，t h e r e e n c o d i n gr a t e i v 华东师范大学2 0 l 届研究生硕士学位论文目录 目录 论文摘要i a b s t r a c t i i l 目录v 第一章绪论1 1 1 背景概述1 1 2 国内外研究现状2 1 3 本文的丁作3 1 4 本文的组织结构4 第二章x m l 相关理论6 2 1 x m l 介绍6 2 2 x m l 相关理论基础7 2 3x m l 查询语言和查询树模式9 2 4 x m l 文档解析接口一1 2 2 5基于关系的x m l 数据存储策略1 4 2 6本章小结1 7 第三章x m l 编码方法分析与研究。1 8 3 1 编码标准和分类1 8 3 2区域编码l8 3 3 前缀编码2 l 3 4 k 分树编码。2 2 3 5 支持动态更新的编码方法2 4 3 。6 各种编码方法的比较分析2 6 3 7 本章小结2 6 第四章p p c s u 编码方法分析与研究2 7 4 1 x m l 文档结构树2 7 4 2 新的编码方法p p c s u 及算法2 8 4 3 新编码结点关系的判断4 2 4 4 新编码方法的优点4 3 4 5 实验结果和性能分析4 4 4 6 本章小结4 6 第五章p p c s u 编码存储策略4 7 5 1 编码存储结构设计4 7 5 2 存储实例分析4 8 第六章总结与展望5 0 6 1 总结5 0 6 2 展望和进一步的工作5 0 附录51 攻读学位期间参加的工作5 2 参考文献5 3 致 射5 8 v 华东师范大学2 0 1 1 届研究生硕士学位论文第一章绪论 1 1 背景概述 第一章绪论 随着网络的迅速发展，人们迫切需要实现信息的共享和高效利用。网络上的 信息大部分是半结构或者无结构的，而传统的数据模式大多用来解决结构化的数 据，所以就需要一种数据交换格式或者标准来表示这些信息。x m l ( e x t e n s i b l e m a r k u pl a n g u a g e ，可扩展标记语言) 作为一种新的网上数据交换标准的出现， 正在引起人们的极大关注，其目的是能够定义人和计算机都能方便识别的数据类 型。x m l 是面向内容的，适用于w e b 上的数据交换。x m l 数据模型相似于半结构 化数据模型，它既为半结构化数据晗3 的研究提供了广阔的应用前景，同时也推动 了半结构化数据研究的发展。x m l 还是一种很灵活的数据格式标准。如何存储口1 和查询h 3 x m l 数据已经逐渐成为业界的研究热点。 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 ) ，是由w 3 c 组织于 1 9 9 8 年2 月发布的一种标准。) 眦是一种元标记语言，用户可以定义自己需要的 标记，只要这些标记是满足某些最低准则。x m l 的特点使得它不仅成为网络数据 交换的标准，而且正逐渐成为数据表示的标准。相关的技术和标准，如x m ld a t a m o d e l 、x m ls c h e m a 、x m lq u e r y 、x m lp a t h 等也不断出现，这些都是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 数据这一研究领域，目前大致有两种方法：一种称为使能 数据库嵋1 ( x m le n a b l e dd a t a b a s e ，x e d b ) 。使能数据库支持x m l ，其特点是在不 变动关系型数据库内核层的基础上，将x m l 的树形结构数据拆散、重组转换成关 系型表格数据存入数据库哺1 。另一种是纯x m l 数据库h 1 ( n a t i v ex m ld a t a b a s e s ) 其特点是以自然的方式处理x m l 数据。在中间时间尽可能少的前提下，将x m l 数据转化成关系数据，利用成熟的关系数据库技术，通过相应的存储和结点编码 华东师范人学2 0 1l 届研究生硕上学位论文 第一章绪论 技术来实现对x m l 文档树结点的高效存储和访问旧儿钔n 0 1 是x m l 数据领域的一个热 点，其中编码技术也可以用于纯x m l 数据库中的存储和查询n ，本文正是基于这 个出发点所进行的研究。 1 2国内外研究现状 x m l 数据库主要解决x m l 数据的存储管理、查询处理、数据更新、访问控制 等。x m l 数据库的存储管理技术包括存储、编码、索引n 2 m 3 等方法。在x m l 的众 多问题中，实现对x m l 数据的有效存储和查询是非常重要的一个方面。 近年来，国外许多著名的大学和研究机构都在从事x m l 数据处理领域的研究 工作，如s t a n r o r d 大学、w i s e o n s i n 大学、b e l l 实验室、法国的i n r i a 研究所 等。国内的中国人民大学、东北大学、复旦大学等也在该领域进行了大量的工作。 在各种大型的国际学术会议( 如i c d e 、v l d b 、s i g m o d 等) 上，该领域相关的论文 占了相当比重，有关的学术交流也非常活跃。此外，许多面向该领域的国际会议 也逐渐发展，如w e b d b 、w l s e 、w a i m 等。 对于x m l 数据的查询，学术界已经提出了多种查询语言n 引，如x p a t h 、x q u e r y 等，这些语言都是将路径表达式作为核心内容，即t w i g 查询n 习n6 l 。t w i g 查询处 理的优劣在很大程度上决定了整个x m l 查询的处理效率。导航的方式简单、直接， 但在大数据量的情况下，执行效率难以保证。大量后续工作针对这一问题进行了 深入研究，由此提出了两种“一次一集合的t w i g 查询处理方法。为了提高路 径查询匹配的执行效率，人们提出了多种导航的遍历方式。文献 1 7 对路径查询 匹配的优化进行了研究，提出了借助文档的模式信息以及在文档结构树中引入索 引的优化方法。虽然这些方法可以在一定情况下改进路径匹配的效率，但由于导 航方式的本质缺陷，查询效率不能得到根本保障。 根据x m l 查询处理所采用的技术的特点及要求，目前已提出的查询处理方法 可以分为3 类：( 1 ) - - 元结构连接，该方法的基本思想是将t w i g 查询分解成两两 结构连接的方式，最后将两两结构连接的结果进行合并得到最终的查询结果；( 2 ) 整体匹配，该方法是为了避免两两结构连接方法输出过多的无用中间结果而提出 来的，它将t w i g 查询进行整体处理，减少只满足局部结构的中间结果；( 3 ) 基于 序列匹配的处理方法。由于一个x q u e r y 表达式中包含多个t w i g 查询，因此，如 果将其转化为一个等价的、但执行效率更高的代数表达式，从而以整体的方式处 理x q u e r y 表达式是x m l 数据库查询引擎是否能够在面对实际应用时，取得高效 2 华东师范大学2 0 11 届研究生硕士学位论文 第一章绪论 率的关键。为了得到高效的查询效率，需要研究的问题很多，包括查询片段的有 效计算，中间结果的高效组合操作，路径查询的分解策略等。解决这些关键技术 问题，实现路径查询的高效处理，是实现大规模x m l 数据查询的关键。目前，随 着研究的不断深入，对于x m l 路径查询处理已经取得了许多的研究成果。由于使 用结构索引可以加快查询处理的速度，因此，开发高效的结构索引并将其纳入查 询计划，从而得到更优的物理执行计划是一个重要的研究问题。 在x m l 数据编码方面，唯一和包含特定关系的有效编码可以迅速确定各个结 点的关系，而不用遍历x m l 文档树，这正符合x m l 路径查询分解计算的基本要求， 为此学者们在这方面做了大量的研究。这些方法都是对x m l 文档树中的元素、属 性和其他语义实体进行编码，并且这种编码具有唯一性，每个实体的编码都不相 同，从而可以方便的对文档树中结点的基本结构关系进行判断。典型的编码方法 有四种：区域编码、前缀编码、k 分树编码以及支持动态更新的编码方法。 区域编码方法的基本思想是为每一个结点分配一对数字，这对数字隐含了该 结点包含的区域。前缀编码方法又称为基于路径的编码方法，父结点的编码是孩 子结点编码的前缀。k 分树编码方法的基本思想是构造一颗k 分完全树作为原来 的x m l 树的容器，这种方法的优点是需要更少的存储空间。 支持动态更新的编码方法满足了x m l 文档需要不断更新的要求。随着x m l 文档应用的不断推广，x m l 文档的插入和删除操作变的越来越频繁，而对于绝 大多数编码方法来说，在执行x m l 文档更新之后需要对x m l 文档树进行重新 编码，需要耗费大量的时间，为此，学者们提出了多种支持动态更新的编码方法， 以降低更新代价n 引，如b i t p a t h 编码、浮点数编码( q u a r t e r i n g - r e g i o n s ) 、奇偶编 码( o r d p a t h ) 、素数编码( p r i m es c h e m e ) 、位字符串编码( c o m p a c td y n a m i cb i n a r y s t r i n g ) 和向量编码( v e c t o re n c o d i n g ) 等。这些编码方法在支持x m l 文档树动 态更新方面都有一定的局限性。 以上编码方法在本文的第三章将做出具体介绍。因此，高效的x m l 数据编 码，解决x m l 文档的更新问题及提高查询效率在x m l 数据库领域具有十分重 要的作用和意义。 1 3本文的工作 本文工作重点侧重于x m l 数据编码方案的研究，针对目前x m l 数据编码 面临的主要问题进行了分析，在比较现有的编码方法的基础上提出了一种新的高 萎 华东师范大学2 0 11 届研究生硕士学位论文第一章绪论 效的支持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 文档更新为大幅度更新时，结点间隔因子口取1 。同时当在奇偶码间隔为l 的两个结点间插入结点时，把左右结点的奇偶码用字符“一 连接作为当前结点 的奇偶码，通过以上方法来避免同一层结点的编码重复问题，同时又考虑了文档 的更新状况，能在保证编码长度较短的情况下使更新后的二次编码率为零。前缀 码、奇偶码和顺序码唯一标识x m l 文档中的结点。本文详细介绍了编码的过程并 给出了该编码方法的实现算法，同时给出了编码更新算法，并给出了实例分析讨 论结点的编码和插入结点的编码。提出了对应本文编码的基于关系模式的x m l 数据存储策略， 最后利用数据库的典型评测数据集，在相应的实验平台上对提出的编码方案 和其他典型的编码方案在各方面进行对比，结果表明，本文提出的编码方案在编 码时间、编码长度、二次编码率方面具有更佳的性能，适用于基于关系数据库n 钔陷们 的x m l 数据的存储和查询。 1 4 本文的组织结构 本文的组织结构如下： 第一章主要介绍本文的研究背景、国内外研究现状及存在的主要问题并简单 说明本文的工作。 第二章讨论了x m l 的基础理论知识、x m l 查询语言和x m l 数据存储策略， 为后面的进一步研究打下基础。 4 华东师范人学2 0 1l 届研究生硕士学位论文第一章绪论 第三章详细介绍和分析了典型的编码方法，并进行了优缺点比较。 第四章提出了一种新的支持动态更新的高效x m l 数据编码方法，详细介绍 编码过程、编码算法和特性，结合实例进行分析，并通过实验对编码方法的相关 性能进行测试和分析。 第五章提出了基于新的编码方法的存储策略，并进行了存储实例分析。 第六章对全文进行了总结，分析了本文研究成果的意义，并指出了今后需要 进一步做的工作。 5 叫簪 甥艮 华东师范大学2 0 1 l 届研究生硕上学位论文第二章x m l 相关理论 2 1x m l 介绍 第二章x m l 相关理论 随着i n t e r a c t 的迅速发展，信息传递与共享在现实生活中已经变的越来越重 要。在数据传递和共享的过程中，网络数据格式的多样性对传统的计算机科学技 术提出了新的挑战。w e b 数据的灵活多变与高效的w e b 数据管理之间似乎着不 可逾越的鸿沟，x m l 的出现为问题的解决带来了新的契机。 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 ，可扩展的标记语言) 是一套定义语义标 记的规则，这些标记将文档分为许多部件并对这些部件加以标识。它也是元标记 语言，可以定义其他与特定领域有关的、语义的、结构化的标记。x m l 是i n t e m e t 环境中跨平台的、依赖于内容的技术，是当前处理分布式结构信息的选择工具。 它可以简化通过i n t e m e t 的文件信息传输。x m l 由x m l 工作组开发，此工作组 由w o 订dw i d ew 曲c o n s o r t i u m ( w 3 c ) 在1 9 9 6 年主持成立。x m l 的设计目标 是：x m l 应该可以直接用于i n t e m e t ；x m l 应该支持大量不同的应用；x m l 应 该与s g m l 兼容；处理x m l 文件的程序应该容易编写；x m l 中的可选项应无 条件地保持最少，理想状况下应该为0 个；x m l 文件应该是人可以直接阅读的， 应该是条理清楚的；x m l 的设计应快速完成；x m l 的设计应该是形式化的、简 洁的；x m l 文件应易于创建；x m l 标记的简洁性是最后考虑的目标。图2 1 是 一个x m l 文档瞳妇样例。 cl a n g u a g e 19 9 5 k a t h e r i n e d a t a b a s e s s t a n f o r d k j e l l p r o g r a m s c a l i f o r n i a 图2 - 1x m l 文档样例 与w e b 上己有的最普遍的数据表现形式h t m l 相比，x m l 的优越性表现 6 华东师范大学2 0 11 届研究生硕上学位论文第二章x m l 相关理论 在以下各方面： ( 1 ) 更有意义的搜索。数据可以被x m l 唯一地标识。 ( 2 ) 不同来源数据的集成。 ( 3 ) 多种应用得到的数据。 ( 4 ) 本地计算和处理。 ( 5 ) 数据的多样显示。由于数据显示与内容分开，x m l 定义的数据允许指 定不同的显示方式，使数据更合理地表现出来。 ( 6 ) 粒状的更新。 ( 7 ) 在w e b 上发布数据。 ( 8 ) 升级性和压缩性。 2 2x m l 相关理论基础 x m l 文档伫2 1 包含x m l 声明、元素、属性、处理指令、注释和命名空间， 其中元素典型的组成了x m l 文档中的大部分内容。x m l 有多项标准规范，包 括x m ld t d ( x m l 文档类型声明) ，x m ls c h e m a ( x m l 模式) 等1 。下面主要介 绍x m l 文档类型声明：d t d 和s c h e m a 。 2 2 1d t d 文档类型声明 d t d 心4 1 包含或指向一组能够提供文档类型语法的标记声明，这种语法称作文 档类型声明或者d t d 。d t d 规定了对于一个x m l 文档来说，什么样的规则定 义是合法的，它的基本格式是 ，其中规则声明又 包括了元素规则的声明、属性规则的声明、实体的声明和注释的声明。 ( 1 ) 元素规则的声明 元素规则的声明就是对一个元素的合法内容进行定义，它的表示方法如下： 在元素的描述内容中可以规定一个元素是否可为空元素，是否可以包含任意 内容，包含哪些子元素，是否可以包含文本内容。 ( 2 ) 属性规则的声明 属性规则的声明就是对一个元素属性的合法内容进行定义，它的表示方法如 下： 7 华东师范人学2 0 11 届研究生硕一l ：学位论文 第二章x m l 相关理论 属性类型有c d a t a ( 值为字符数据) 、i d ( 值为唯一的i d ) 、i d r e f ( 值为另外 一个元素的i d ) 、e n t i t y ( 值是一个实体) 等多种，默认值则有# d e f a u l tv a l u e ( 属性的默认值) 、# r e q u i r e d ( 属性值是必需的) 、# i m p l i e d ( 属性不是必需的) 、 # f i x e dv a l u e ( 属性值是固定的) 4 种。 ( 3 ) 实体的声明 实体的声明就是将一组普通文本或特殊字符定义成为一个实体，以便于重 用，它的表示方法如下： 。 ( 4 ) 注释的声明 注释的声明用于定义注释，注释使x m l 文档可以将通知信息传递给外部应 用程序，它的表示方法如下： 。 2 2 2s c h e m ax m l 模式 s c h e m a 是一类x m l 文档的描述，通常被表示为这类文档在x m l 文档本身 的语法约束之外的，在结构和内容上的约束。一个x m ls c h e m a 在高层次上为文 档提供一个抽象视图。 x m l s c h e m a 心朝本身就是一个结构良好的x m l 文档，表示方法如下： 样子元素的定义 定义子元素时，可以使用简单类型元素和复杂类型元素。 ( 1 ) 简单类型元素 只使用基本数据类型，不包括任何子元素和属性的元素称为简单类型元素。 它的基本语法是： x s ：e l e m e n tn a m e = “元素名称”t y p e = “元素的基本数据类型 今 ( 2 ) 复杂类型元素 复杂类型元素是指包含子元素或属性的元素，它包括4 种类型，分别是空元 素、只包含子元素的元素、只包含文本的元素、同时包含子元素和文本的元素。 复杂类型元素声明的表示方法有两种。一种是对此元素直接进行声明，具体表示 方法如下： 华东师范大学2 0 11 届研究生硕士学位论文 第一二章x m l 相关理论 x s ：e l e m e n tn a m e = “子元素名2 t y p e = “基本数据类型”