（计算机应用技术专业论文）基于区域编码模式的xml更新系统的设计与实现.pdf

华东师范大学硕上学位论文基于区域编码模式的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 p a t h 和x q u e r y 的处理效率。然而，由于区域编码模式 在更新时，需要修改平均一半节点的p r e 值( 文档树自 f 序遍历时节点访问顺序) ， 故其更新操作效率不高。因此，设计并实现一个基于区域编码模式的x m l 高效 更新系统是一件十分有意义的工作。 本文基于区域编码模式设计并实现x m l 数据原型更新系统x u n a t e 2 s q l 。 本原型系统主要由两个部分组成： 第一部分基于区域编码模式设计了x u p d a t e 语言到s q l 语言的翻译规则， 并采用循环消除法将x u p d a t e 语言中的循环转换为s q l 语言中的连接，解决了 x u p d a t e 语言和s q l 语言的差异性问题；然后根据此翻译规则通过b u r g 工具 将x u p d a t e 语法树转换成s q l 语法树，完成整个编译过程，实现了x m l 数据 的更新功能。本原型系统内部编译器的目标语言为s q l 语言，遵循s q l 9 2 规则， 支持当前流行的r d b m s ，具有良好的通用性。 第二部分设计并实现批量更新策略，通过引入增量b t r e e ，不仅减少了需要 更新的节点数目，而且节省了重建索引所耗时间。试验表明，批量更新策略大大 提高了x m l 数据更新操作的效率。由于批量更新策略保持了原数据库内部结构 的完整性，因此不依赖于某个特定的数据库系统，具有良好的可移植性。 此外，为了方便不熟悉x u p d a t e 语言的普通用户使用，x u p d a t e 2 s q l 原型系 统给出了图形化操作界面，并提供快捷菜单供用户自动生成x u p d a t e 语句，增强 了本系统的易用性。 通过测试验证，x u p d a t e 2 s q l 原型系统在保持高效的查询性能的同时，提高 华东师范大学硕上学位论文 摹于区域编码模式的x m l 更新系统的设计与实现 了x m l 文档更新操作的性能，使系统的整体性能得到提高。x u p d a t e 2 s q l 原型 系统的通用性、高效性、可移植性和易用性构成了本文的最大的特色和创新之处。 最后，本文综合评估了x u p d a t e 2 s q l 原型系统的优点和有待进一步完善之 处，提出了今后需要深一步开展的研究工作。 关键词：x m lx u p d a t e 关系数据库管理系统s q lb 树 华东师范大学硕士学位论文 摹于区域编码模式的x m l 更新系统的设计与实现 a b s t r a c t a san e wm a r k u pl a n g u a g e ，x m lh a sb e c o m et h es t a n d a r df o r r e p r e s e n t i n ga n d e x c h a n g i n gd a t av i an e t w o r k s i n c ei t su n i q u ea d v a n t a g e ss u c ha ss e l f - d e s c r i p t i o n , a n dp l a t f o r m - i n d e p e n d e n c e , m o r ea n dm o r ea p p l i c a t i o n su s ex m l t os t o r e ，e x c h a n g e a n dp u b l i s hi n f o r m a t i o n , w h i c hb r i n g sag r e a tc h a l l e n g et ox m l s t o r a g es o l u t i o n w i t h p o w e r f u la n dr e l i a b l ed a t am a n a g e m e n tc a p a b i l i t i e sr e l a t i o n a ld a t a b a s ei si n c r e a s i n g l y w i d e l yu s e dt os t o r ex m ld a t a c u r r e n t l yt h ep e r f o r m a n c ei s s u eo fq u e r ya n du p d a t e x m ld a t ab a s e do nr d b m sh a sb e c o m ear e s e a r c hh o t p o i n t i no r d e rt ot i s ee x i s t i n gr d b m s i t 托q 1 1 j 硝璎t oo f l i e i m f l ym a px m ld a t ai n t o r e l a t i o n a lt a b l e h o w e v e r , w i t hn oa w a r eo f u n d e r l y i n gt r e e - s h a p e dd a t ar d b m sc a n t m a k ef u l lu s eo fe n c o d i n gi n f o r m a t i o n ，w h i c ha f f e c t si t s q u e r ya n du p d a t e p e r f o r m a n c e r e g i o n - b a s e de n c o d i n gm a p sx m ld a t ai n t o i n d e xs t r u c t u r et h a t f a c i l i t a t e st h em a n a g e m e n t m o r ei m p o r t a n t l y , s t a i r c a s ej o i na r ea w a r eo ft r e e - s h a p e d d a t aa n dc a ne f f e c t i v e l yr e d u c er e d u n d a n to p e r a t i o nf o rl o o p e x p e r i m e n t ss h o w c o m p a r e dw i t ho t h e ra p p r o a c h e st h eu s eo fr e g i o n - b a s e de n c o d i n gc a ns i g n i f i c a n t l y i m p r o v et h ep e r f o r m a n c eo f x p a t ha n dx q u e r y h o w e v e r , b e c a u s eo f s t r u c t u r a lu p d a t e p r o b l e mi nr e g i o n - b a s e de n c o d i n gn e a r l yh a l fo ft h et o t a ln o d e sn e e dt ob ec h a n g e d f o ru p d a t eo p e r a t i o n t h e r e f o r e ，i ti s v e r ym e a n i n g f u lt od e s i g na n di m p l e m e n ta h i g h - e f f i c i e n tr e g i o n - b a s e dx m lu p d a t es y s t e m t h i sp a p e rd e s i g n sa n di m p l e m e n t sap r o t o t y p es y s t e mc a l l e dx u p d a t e 2 s q l i t c o n s i s t so f t w om a j o rc o m p o n e n t s ： t h ef i r s tp a r td e s i g n st h er u l e st om a px u p d a t et os q la n du s e s l o o p l i t t e d a p p r o a c ht oc o n v e r tl o o pi nx u p d a t et oj o i ni ns q lt os o l v et h ed i f f e r e n c e sb e t w e e n x u p d a t ea n ds q l t h e na c c o r d i n gt ot h o s er u l e si tt r a n s f o r m sx u p d a t ea s t ( a b s t m as y n t a xt r e e ) t os q la s t w i t hb u r gt o o lt oc o m p l e t ec o m p i l a t i o np r o c e s s t h e t a r g e tl a n g u a g eo fi n t e r n a lc o m p i l e ri ss q lw h i c hf o l l o w ss q l 9 2s t a n d a r da n d s u p p o r t e db yp o p u l a rr d b m s s oi th a sg o o dv e r s a t i l i t y t h es e c o n dp a r td e s i g n sb u s ( b a t c hu p d a t es t r a t e g y ) b yi n t r o d u c i n gi n c r e m e n t a l b t r e e ，n o to n l yr e d u c et h en u m b e ro ft h en o d e sn e e d e dt ob eu p d a t e db u ta l s os a v e t h et i m es p e n to nr e c o n s t r u c t i o ni n d e x t e s t ss h o wb u sh a sg r e a t l ye n h a n c e dx m l u p d a t ep e r f o r m a n c e b u sm a i n t a i n st h ei n t e g r i t yo ft h ei n t e r n a ls t r u c t u r eo ft h e d a t a b a s es oi ti s i n d e p e n d e n t o f s p e c i f i cr d b m s a n dh a sg o o dp o r t a b i l i t y i i i 些查墅蔓查兰堡主兰垡丝兰 苎主垦苎堕堕蔓壅箜! 型! 里堑墨丝堕堡盐兰壅墨 i na d d i t i o n , f o ro l d i n a r yu s 郇w h oa l eu n f a m i l i a rw i t hx o # a t el a n g u a g et h i s s y s t e mp r o v i d e sg u i a n df a s tm e l l ut oa u t o m a t i c a l l yg e n e r a t ex u p d a t es t a t e m e n ta n d e n h a n c e se a s eo f u s eo ft h es y s t e m t e s t sv e r i f yx t 3 p d a t e 2 s q lp r o t o t y p es y s t e m m a i n t a i n se f f i c i e n tq u e r y p e r f o r m a n c e ，w h i l ei m p r o v i n g t h ex m lu p d a t ep e r f o r m a n c e , s y s t e m so v e r a l l p e r f o r m a n c ei si m p r o v e d v e r s a t i l i t y , e f f i c i e n c y , p o r t a b i l i t ya n d e a s eo f u s ec o n s t i t u t e t h eb i g g e s tc h a r a c t e r i s t i e sa n di n n o v a t i o no f t h i sp a p e r f i n a l l y , w og i v eac o n c l u s i o no ft h ea d v a n t a g e s a sw e l la sd r a w b a c k so f x u p d a t e 2 9 q lp r o t o t y p es y s t e m ，w h i c hw i l lg u i d e o b fr e s e a r c hw o r k i nt h ef u t u r e k e yw o r d s ：x m lx u l x l a t er d b m ss q l b t r e e i v - 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究 成果。据我所知，除文中已经注明引用的内容外，本论文不包含其他个人已经 发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在 文中作了晚确说明并表示谢意。 作者签名：墨笾日期：团：! ：二 学位论文使用授权声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有权保 留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权 将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅有 权将学位论文的内容编入有关数据库进行检索。有权将学位论文的标题和摘要 汇编出版保密的学位论文在解密后适用本规定。 学位论文作者签名：鱼弛 导师签名：塑 日期：逆l ! 壁日期：趁：2 ：! 兰：! o r i g i n a l i t yn o t i c e i np r e s e n t i n gt h i st h e s i si np a r t i a lf u l f i l l m e n to f t h er e q u i r e m e n t sf o r t h em a s t e r s d e g r e ea te a s tc h i n an o r m a lu n i v e r s i t y ，1w a r r a n tt h a tt h i st h e s i si so r i g i n a la n da n y o ft h et e c h n i q u e sp r e s e n t e di nt h et h e s i sh a v eb e e nf i g u r e do u tb ym e a n yo ft h e r e f e r e n c e st ot h ec o p y n g h t ，t r a d e m a r k ，p a t e n t ， s t a t u t o r yr i g h t ， o rp r o p r i e t yr i g h t o fo t h e r sh a v eb e e ne x p l i c i t l ya c k n o w l e d g e da n di n c l u d e di nt h er e f e r e n c e ss e c t i o na t t h ee n do f t h i st h e s i s s 驷枷掀专劾。d 咖：卿， c o p y r i g h tn o t i c e ih e r e i na g r e et h a tt h el i b r a r yo fe c n us h a l lm a k ei t sc o p i e sf r e e l ya v a i l a b l ef o r i n s p e c t i o n if u r t h e ra g r e et h a te x t e n s i v ec o p y i n go ft h et h e s i si sa l l o w a b l eo n l yf o r s c h o l a r l yp u r p o s e s ，i np a r t i c u l a r ，s t o r i n gt h ec o n t e n to ft h i st h e s i si n t or e l e v a n t d a t a b a s e s ，a sw e l la sc o m p i l i n ga n d p u b l i s h i n gt h er i f l ea n da b s t r a c to f t h i st h e s i s ， c o n s i s t e n tw i t h ”f a i ru s e ”a sp r e s c r i b e di nt h ec o p 埘g h tl a wo ft h ep e o p l e s r e p u b l i co f c h i n a s i g n a t u r e ：亏筋d a t e ：卿， 华东师范人学硕上学位论文 基于区域编码模式的x m l 更新系统的设计与实现 1 1x m l 简介 第一章引言 x m l t l 】的全称是“可扩展标记语言”( e x t e n s i a b l em a r k u pl a n g u a g e ) ，它是 w 3 c ( 万维网联盟) 认可的文档标记标准。它定义了利用简单的、人类可读的标签 对数据进行标记所采用的一般语法，提供了计算机文档的一种标准格式。这种格 式很灵活，可以进行定制以应用于各种领域，如网站、电子数据交换、矢量图形、 家谱、房地产清单、对象串行化、远程过程调用和声音邮件系统等。 与h t m l 一样，x m l 也是源于标准通用标记语言s g m l l 2 1 。s g m l 于1 9 8 6 年被i s o 定为标准，它是一种语义的和结构化的文本文档标记语言。s g m l 非 常强大，在美国军事和政府、航天部及其它需要有效地处理大规模技术文档的多 个重要领域获得成功。但由于s g m l 语法过于复杂、庞大，无法在计算机上实 现其全部功能，因此，w c b 的发明者根据当时计算机技术的能力，提出了h t m l 语言。然而，h t m l 语言仅仅是s g m l 的一种成功应用，它没有s g m l 那样强 大的功能。h t m l 采用固定的标签集，这些标签主要用于w 曲页面的显示，很 难在其他应用程序中起到作用。例如，无法使用h t m l 在两个不兼容的数据库 之问交换数据，或者向零售站点发送更新的产品目录等。 随着互联网的迅猛发展，用于简单显示网页的h t m l 语言已无法满足人们日 益增长的网络应用需求，于是开发一种新的w e b 语言势在必行。1 9 9 6 年，j o n b o s a k 、t i mb r a y 、c m s p e r b e r g - m c q u e e n 、j a m e sc l a r k 等开始着手编写s g m l 的“精简”版本。该版本保留了s g m l 的大部分功能，删除了一些冗余、复杂 且难实现的特性，就此诞生了x m l1 0 ，并且很快获得了成功。 x m l 是一种文本文档的元标记语言。x m l 文档中包含的数据是文本字符串， 描述这些数据的文本标记围绕在数据周围。数据和标签有一个称为元素的特别单 位。x m l 规范确切定义了标记必须遵循的语法：标签如何界定元素，可以接受 什么样的元素名称，属性放在什么位置等等。x m l 也是一种元标记语言。它没 有一套能够适用于各个领域中所有用户的固定的标签和元素。x m l 允许开发者 和编写者根据自己的需要定义元素，体现了该语言良好的可扩展性。 x p a t h 3 】是一种在x m l 文档中查找信息的语言。x p a t h 被用来在x m l 文档 中对元素和属性进行遍历。x p a t h 是w 3 cx s l t 标准的主要元素，并且x q l l e 钏 和x p o i n t e r l 5 】同时被构建于x p a t h 表达之上。 x q u e r y 语言【4 1 ( x m l q u e r y ，x m l 查询语言) 是一个用于从x m l 格式的文 华东师范大学硕士学位论文基于区域编码模式的x m l 更新系统的设计与实现 档中获取数据项的查询语言，它可以广泛应用于各种类型的x m l 数据源中， x q u e r y 对x m l 的作用类似s q l 对数据库的作用。目前x q u e r y 已经成为w 3 c 的推荐标准。 x u p d a t e 语言f 6 1 ( x m lu p d a t el a n g u a g e ，x m l 更新语言) 为x q u e r y 语言的 扩展，利用该语言可以方便地修改x m l 文档。x u p d a t e 语言定义了用于修改 x m l 文档数据的更新工具，旨在使用常规x m l 文档和数据库集合中的x m l ， 甚至可以使用虚拟x m l 数据模型。 1 2x m l 文档在数据库中的存储方式 作为一种全新的标记语言，x m l 以其扩展性、结构性、平台独立性和自描 述性等诸多特性逐渐成为网络上数据表示和交换的事实标准，越来越多的应用使 用x m l 来存储、交换和发布信息，大量x m l 数据的出现给x m l 的存储和管 理带来了巨大的挑战。 1 2 1x m l 在面向对象数据库中的存储方法 面向对象数据库是一种以对象形式表示信息的数据库，面向对象数据库的 管理系统被称为o d b m s ( o b j e c t d a t a b a s em a n a g e m e n ts y s t e m ，面向对象数据库 管理系统) 或o o d b m s ( o b j e c t - o r i e n t e dd a t a b a s em a n a g e m e n ts y s t e m ，面向 对象数据库管理系统) 。 在面向对象的数据库中，数据以对象的形式进行存储，这些对象只能由其 所属类中定义的方法来操作。对象被组成一种类型层次，子类继承其超类的特 性。对象中可以引用其它对象，提供了一种导航式访问数据的方法。 x m l 文档元素具有层次嵌套特性，因此很容易将x m l 文档数据转化为面 向对象数据库中的对象进行存储。面向对象数据库的结构不仅给x m l 的存储 带来方便，而且在访问时，由于不需要作表问的连接，加快了数据访问的速度。 然而，面向对象的数据库由于缺乏形式化的数学基础，在一般目的的大规 模查询支持上处于弱势，再加上它没有统一可行的标准，以致产品间的兼容性 和可移植性比较差，所以应用范围较窄，通用性差。 1 2 2x 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 p a t h 查询句法不支持组、排列和摘要数据等功能， 比x p a t h 更丰富的x q u e r y 查询语言仍然仅仅是一个设计表格，更有甚的是 x q u o r y 正式化的时候，它仍然不支持数据更新、插入和删除等功能。上述种 种问题使得原生数据库的数据管理能力大打折扣，也给x m l 文档存储后的数 据管理带来了新的问题。 随着x m l 文档数量的不断上升，文档规模的不断增大，原生数据库在面 临大数据量时，就显得相形见绌。而以处理和管理海量数据为特点的关系数据 库，在这方面显示出了强大的生命力。如何将x m l 形式的数据存储到现有的 关系数据库中，利用成熟的关系数据库管理技术和最低的改造成本，解决x m l 的存储管理问题，如今越来越受到关注。 1 2 3x m l 在关系数据库中的存储方法 r d b m s ( r e l a t i o n a ld a t a b a s em a n a g e m e n ts y s t e m ，关系数据库管理系统) 是建立在集合代数基础上，运用数学方法来处理数据库中的数据。现实世界中 的各种实体之间的各种联系均用关系模型来表示。关系模型由关系数据结构、 关系操作集合、关系完整性约束三部分组成。 关系型数据库的数据模型最早是在1 9 世纪7 0 年代由e e c o d d 博士提出 的。当初并没有受到太多的重视，但是后来人们逐渐发现了它的生命力。关系 型数据库从理论研究走向商业应用，占据数据库市场的主流地位，反过来又对 数据处理和计算机整体的理论研究起到了很大的推动作用。 由于关系数据库强大的数据管理能力和广泛的市场占有率，使得如何将 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 数据存储提供 了一定的支持，例如i b m 的d b 2x m le x t e n d e r t “，s q l s e r v c r 的o p e n x m l 8 1 ， o r a c l ex m ld b 9 】等。 由于x m l 逐渐成为网络上数据表示和交换的事实标准，越来越多的应用 使用x m l 来存储、交换和发布信息。大量x m l 数据的出现给x m l 的存储和 管理带来了巨大的挑战。随着x m l 文档不断增大，面向对象数据库和原生数 据库在数据的管理上显得力不从心，关系数据库因其强大可靠的数据管理能 力，被越来越广泛地用于存储x m l 数据。 1 3 国内外研究现状及存在问题 虽然采用成熟的关系数据库系统存储x m l 数据具有许多优势，但是将x m l 数据存储于关系数据库中需要解决两个关键问题： 1 模式映射 模式映射即如何根据x m l 文档结构( d t d e l o 】或x m ls c h e m a “1 ) 生成关 系数据库模式。x m l 数据基于x m l 模式，采用半结构化存储，而关系数据 库采用的是关系模式，将数据存储于表和列中。因此，需要进行x m l 模式 到关系模式的转换，也就是将x m l 文档结构映射到关系表定义( 即关系模 式) 。 目前，模式映射领域己存在多种技术，基本上可以分为两大樊1 2 i ：基于 x m l 模式信息( s c h e m a o b v i o u s ) 的技术，如基本内联法、共享内联法、混合 内联法【1 3 】等；不基于x m l 模式信息( s c h e m a - c o n s c i o u s ) 的技术，如边存储法 1 4 l 、二元法1 1 5 】、s t o r e d t l 棚、x r e l 1 7 】等。 2 查询转换 查询转换u p o n 何将x m l 查询语句翻译为关系数据库上的s q l 查询语 句。针对x m l 数据的查询语言有w 3 c 提出的x p a t h 、x q i l e r y 等，而关系 数据库中的查询语句是s q l 语言。x q u e r y 是基于路径的，在结构上具有嵌 套的特性，而s q l 在结构上是扁平的，语义没有x q u a r y 复杂。因此，如要 将x m l 文档存储于关系数据库中，为了能够使用x m l 查询语言透明地操 作存储在关系数据库中的x m l 数据，需要将x m l 查询语句翻译成s q l 语 句。 华东师范大学硕士学位论文基于区域编码模式的x m l 更新系统的设计与实现 但是，在对x m l 文档进行查询更薪操作时，由于x m l 文档采用树状体 系结构而r d b m s 中数据存储器采用表格式模型，两者难以匹配。因此，这些 模式映射技术在x m l 文档查询和更新的效率上不如原生数据库，这问题在 查询更新海量x m l 数据时显得更加突出。 为了提高x m l 文档查询和更新性能，c o p p e r t l 剐，l i 和m o o n 【1 9 】，s u c i u 和m i l o l 2 0 1 分别提出了一系列基于x m l 文档的索引策略。然而，这些索引策略 主要应用于x p a t h 语言中c h i l d 和d e s c e n d a n t o r - s e l f 轴，并没有支持整个x p a t h 语言。p o n o i l 等提出的o r d p a t h 标签【2 l j 在x m l 文档更新方面具有较高的 性能，但是这种性能的提升是以大容量的存储为代价，而且这种方法是针对 x m l 文档更新操作设计，其查询效率较低，难以满足海量x m l 数据查询的要 求。 t o r s t e n g n l s t 提出了区域编码模式 2 2 , 2 3 , 2 4 1 。通过该编码模式可将) 0 帆文档 转换为五元索引结构映射到关系数据库中，方便了x m l 数据的管理，而x m l 查询语言则可以转换为s q l 语句实现【2 5 0 6 刀1 。更为重要的是，基于该索引结构 所提出的阶梯连接( s t a i r c a s ej o i n ) 1 2 舢3 2 】可充分利用编码模式的特性，有效地减少 计算a n c e s t o r 、d c s c e i l d a n t 、p r o c e e d i n g 和f o l l o w i n g 轴时的冗余操作。实验表明， 区域编码模式可以显著地提高x m l 查询的处理效率1 3 3 , 3 4 ，而且与现在基于原 生数据库的主流x q u e r y 引擎g a l a x 3 5 】相比，基于关系数据库的区域编码模式的 查询效率更高【3 6 1 ，这使其在处理海量x m l 数据的查询方面具有广泛的应用前 景。 但是，基于关系数据库的区域编码模式在x m l 数据的更新上存在不足， 使x m l 文档更新操作的效率较低【3 7 1 。文献【3 8 】提出了支持x m l 数据更新操作 的系统m o n e t d b x q u e r y ，该系统通过修改m o n e t d b l 3 9 1 数据库逻辑页面( 1 0 # e m p a g e ) 的方式来实现x m l 文档的更新。然而，这种方式利用了虚拟列( v i r t u a l c o l u m n ) 这一m o n e t d b 独有的特性，难以扩展到其他数据库。并且该系统内部 编译器的目标语言为m o n e t d b 虚拟机语言：m i “m o n e t d bi n t e r p r e t e r l a n g u a g e ，m o n e t d b 解释语言) ，不能直接应用于其他关系数据库中。 因此，设计并实现一个基于区域编码模式的通用而高效的x m l 更新系统 将是一项十分有意义的工作。 1 4 本文的主要研究工作 本文对基于关系数据库的x m l 文档的更新问题进行了研究，设计并实现 了以x u p d a t e 语言为核心的x m l 文档原型更新系统x u p d a t e 2 s q l 。该系统主 要由两个部分组成： 华东师范人学硕上学位论文基于区域编码模式的x m l 更新系统的设计与实现 第一部分基于区域编码模式设计了x u l x l a t e 语言到s q l 语言的翻译规员f j ， 并根据此规则通过b u r g i 删工具完成整个编译过程，实现x m l 数据的更新功 能。 第二部分设计批量更新策略，并且以开源数据库s q l i t e 为实例，通过引 入增量b t r e e 不仅减少了需要更新节点数目而且节省了重建索引所耗时间，试 验表明批量更新策略大大提高了x m l 数据更新操作的效率。 此外，为了方便不熟悉x u p d a t e 语言的普通用户使用，x u p d a t e 2 s q l 原 型系统给出了图形化操作界面，并提供快捷菜单供用户自动生成x u p d a t e 语 句，这使本系统具有良好的易用性。 本文所做的主要研究工作如下： 1 基于区域编码模式，提出并设计了x u p d m 语言到s q l 语言的翻译 规则。 2 采用l e x y a c c ，自行设计并实现了原型系统所需的x u p d a t e 词法语法 分析器。 3 基于本文提出并设计的翻译规则采用b u r g 工具实现了x u p d a t e 语 法树到s q l 语法树的转换。转换后的s q l 语法树经过s q l 语句生成 子系统，自顶向下地递归生成s q l 语句，完成整个编译过程。 4 设计并实现了x m l 文档载入和重构子系统，使得x m l 数据能够在 原始x m l 文档和关系数据库这两种数据载体之间进行灵活的双向转 换。 5 针对区域编码模式在x m l 数据更新上的不足，提出了x m l 数据批 量更新优化策略，并以开源数据库s q l i t e 为实例，通过修改其内部 b t r e e 结构，实现了批量更新策略。 6 本原型系统设计并实现了一套图形化用户界面，以方便不熟悉 x u p d a t e 语言的普通用户使用，从而增强了系统的易用性。 本文所设计的x u p d a t e 2 s q l 原型系统的优点是： ( 1 ) 在整个系统的开发过程中，x u p d a t e 语言将被编译成s q l 语言，遵循 s q l 9 2 规则，支持当前流行的r d b m s ，这使本系统可以方便地在目 前各个关系数据库中移植，提高了本系统的通用性。 ( 2 ) 本文在对x m l 数据更新操作的特点进行分析后，提出了批量更新优 化策略，该策略通过对关系数据库底层b t r e e 进行了适当修改，提高 了x m l 数据的更新效率。 华东师范人学顾十学位论文基于区域编码模式的x m l 更新系统的设计与实现 1 5 本文的组织结构 本文按照如下方式组织： 第一章对x m l 作概念性介绍，简单阐述了x m l 与各个数据库系统的关 系。总结了国内外研究现状和不足，阐明了本文的研究意义，并对本文的研究 内容和组织结构作了总体介绍。 第二章介绍了x m l 查询语言x p a t h 和x q u e r y ，以及x m l 更新语言 x u p d a t e 。讨论了区域编码模式的结构，以及如何基于区域编码模式将x m l 文档的查询语言x p a t h 转换成关系数据库的查询语言s q l ，并详细讨论了基于 区域编码模式的x m l 文档的查询优化策略，对基于区域编码模式x m l 文档 的更新问题进行了分析，从而阐明了实现一个基于区域编码模式的高效的 x m l 更新系统的意义。 第三章分析了x m l 更新表达式以及x u p d a t e 语言和s q l 语言的特点， 并提出了x u p d a t e 语言核心表达式的翻译规则，将x m l 更新语言x u p d a t e 编 译成关系数据库语言s q l 。 第四章阐述x u p d a t e 2 s q l 原型系统的框架，包括各个子系统的数据传输 过程以及其主要功能。 第五章阐述x u p d a t e 2 s q l 原型系统中语法词法分析子系统、语法树转换 子系统、s q l 语句生成子系统、x m l 文档载入和重构子系统等四个子系统的 实现过程。 第六章针对区域编码模式在x m l 数据更新上的不足，提出x m l 数据的 批量更新优化策略。以开源数据库s q l i t e 为实例，通过修改其内部b t r e e 结 构，实现批量更新策略。 第七章给出x u p d a t e 2 s q l 系统图形化用户界面并对本系统进行性能测 试。 第八章结束语，对本文的研究进行总结和展望。 华东师范大学硕士学位论文基于区域编码模的x m l 更新系统的设计与实现 第二章x m l 查询更新语言和区域编码模式 x p a t h l 3 】语言是一种能在x m l 文档中查找定位信息的表达式语言；x q u c r y 语言是一种用于从x m l 格式的文档中获取数据项的查询语言；x u p d a t e 为 x q u e r y 语言的扩展，利用该语言可以方便地修改x m l 文档。区域编码模式 2 2 “r e g i o n b a s e de n c o d i n g ) 将x m l 文档按照前序和后序遍历的顺序进行编码， 映射到特定的关系数据库表结构中，r d b m s 通过区域编码模式中的阶梯连接【3 0 】 ( s t a i r c a s e j o i n ) 能够认识到x m l 文档的底层树状结构，从而大大地提高了x m l 文档的查询效率。此外，本章对基于区域编码模式的x m l 文档更新时存在的性 能问题进行了分析。 2 1x m l 的查询与更新 2 1 1x m l 查询语言：x p a t h 和x q u e r y ( 1 ) x p a t h 语言 x p a t h 语言【3 1 ( x m l p a t h ，路径表达式) 是一种能在x m l 文档中查找定位信 息的表达式语言，它可以从交换或显示的x m l 源数据或文档中选择或过滤信息， 在计算机或计算机应用程序之间的信息交换中起着重要的作用。 x p a t h 定义了用来求值的树状模型，该树状模型将x m l 文档的逻辑结构进 行编码。大多数的x p a t h 表达式确定了该树状模型上的一个结点集合，称该类表 达式为定位路径。如i n v o i c e i t e m p r i c e ，就定位了根元素i n v o i c e 下的子元素i t e m 下的子元素p r i c e 。 默认情况下，x p a t h 以文档次序遍历这个树状模型。x p a t h 通过定位路径表 达式来获取特定的结点或结点集。定位路径由一个或多个定位步骤构成，每个定 位步骤之间用“”隔开。路径表达式分为绝对路径表达式和相对路径表达式。 如：i n v o i c e i t e m 是绝对路径表达式，确定i n v o i c e 根元素的i t e m 子元素；i t e m s k u 是相对路径表达式，确定上下文结点i t e m 子元素的s k u 子元素。 通过x p a t h 轴可定义某个相对于当前节点的节点集，主要的x p a t h 轴如表 2 1 所示： 表2 - 1x p a t h 轴 华东师