（计算机应用技术专业论文）native+xml数据库并发控制技术研究.pdf

摘要 随着互联网技术的发展，x m l 已经成为数据描述和数据交换的新标准。各行各业 都积极采用x m l 格式表示其数据和信息，借助于x m l ，w e b 正逐步转化为一个巨大的 数据库。基于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 原生 数据库领域，事务和并发控制机制方面的研究才刚刚开始。目前，虽然很多x m l 原生 数据库都声称支持事务处理，但是，锁的粒度通常比较大，是针对整个文档而不是针对 文档片断，所以多用户并发性的支持相对较低。 本文结合x m l 文档的特点，通过简化x p a t h 数据模型，定义了一个x m l 事务模 型，并在此基础上设计了一种基于x p a t h 的并发控制加锁协议，对该协议的具体操作流 程和算法以及死锁的检测和处理、事务撤销或中止时的处理等进行了深入地研究，给出 了支持x m l 事务模型的可扩展编码方案，论证了在此协议下的调度是可串行化调度。 最后，结合目前x m l 应用的特点，基于这一协议，将传统关系数据库中基于版本化的 并发控制思想应用到x m l 原生数据库中，设计实现了只读x m l 多版本协议，通过利 用只读事务与更新事务互不阻塞以及只读事务不需要加锁的优势，提高了事务的并发 度，并给出了事务调度的可串行化证明。 为验证所提协议和算法的有效性，本文还进行了大量实验，结果表明本文所提出的 并发控制协议能够非常有效地降低事务回滚率和提高系统吞吐量，从而改善系统性能， 对今后进一步的研究和实际应用具有重要意义。 关键词：x m l ，事务，并发控制 r e s e a r c ho nc o n c u r r e n c yc o n t r o lt e c h n o l o g yo f n a t i v ex m l d a t a b a s e s u nh u a g u o ( c o m p u t e ra p p l i c a t i o nt 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 w i t ht h ed e v e l o p m e n to fi n t e r n e t ，x m lh a sg a i n e dg r e a tp o p u l a r i t yi nr e c e n ty e a r sa n d e m e r g e da san e ws t a n d a r df o rd a t ar e p r e s e n t a t i o na n de x c h a n g e x m li sb e i n g u s e di nm o r e a n dm o r ea r e a s w i t ht h er a p i da d o p t i o no fx m l ，t h ei n t e r n e th a sb e e nt u r n e di n t oag i g a n t i c d a t a b a s eg r a d u a l l y t h eo c c u r r e n c eo ft h ex m ld o c u m e n t st h a ta r cb a s e do nt h ea p p l i c a t i o n o fi n t e r n e to rw e b ，e s p e c i a l l y , t h ea d v e n to fn a t i v ex m ld a t a b a s e s ( n x d ) ，a r i s e sa n u n p r e c e d e n t e dc h a l l e n g et ot r a d i t i o n a ld a t a b a s ef i e l d c o n c u r r e n c yc o n t r o li st h em o s ti m p o r t a n tm e c h a n i s mo fi m p r o v i n gt h et r a n s a c t i o n c a p a b i l i t yo fd a t a b a s es y s t e m a n d i ti sa l s oad i f f i c u l t yi nt h ef i e l do f n x d t h er e s e a r c h e so f x m lt r a n s a c t i o np r o c e s s i n gt o d a ya r ef a rf r o mp e r f e c t o nt h ep r o b l e mo fh o wt os o l v e c o n c u r r e n c yc o n t r o lo fx m ld a t a , au n i v e r s a lp e r s p e c t i v es u g g e s t st h a tt h ex m ld o c u m e n t c a nb ep r o j e c t e di n t ot r a d i t i o n a ld a t a b a s e ss ot h a tt h ep e r f e c tt r a n s a c t i o nm e c h a n i s mo f t r a d i t i o n a ld a t a b a s e sc a l lb eu s e dt oe n s u r et h em u l t i u s e r sc o n c u r r e n c yo fx m l b u ti nf a c t , b e c a u s eo ft h ec o n f l i c tb e t w e e nt h ei n b o r nc o m p l a n a t i o no ft r a d i t i o n a ld a t a b a s e sa n dt h e h i e r a r c h yo ft h ex m ld o c u m e n td a t a , t h ec o n c u r r e n c ym e c h a n i s mb a s e do nt h ep e r s p e c t i v e h e r e i n b e f o r ec a n tc o n t r o lt h ec o n c u r r e n c ya c c e s so fm u l t i - u s e r st os i n g l ed o c u m e n th i g h e f f e c t i v e l y o nt h eo t h e rh a n d ，i nt h ef i e l do f n x d t h er e s e a r c hc o n c e r n i n gt h et r a n s a c t i o na n d t h ec o n c u r r e n c yc o n t r o lm e c h a n i s mi si n i t i a t e dn o tl o n ga g o c u r r e n t l y , a l t h o u g hm a n yo f n x dc l a i mt o s u p p o r tt h et r a n s a c t i o nm a n a g e m e n t ，t h e yc a n te f f e c t i v e l ys u p p o r tt h e c o n c u r r e n c yo fm u l t i - u s e r ss i n c et h eg r a n u l a r i t yo ft h el o c ki sg e n e r a l l yb i g ，t h a ti s ，i tf i t st h e w h o l ed o c u m e n t ，n o tt h ef r a g m e n td o c u m e n t i nt h i sp a p e r , w ed e f i n e da nx m lt r a n s a c t i o nm o d e lb yc o m b i n i n gt h ec h a r a c t e r i s t i co f x m ld o c u m e n ta n ds i m p l i f y i n gt h es t a n d a r dx p a t hd a t am o d e l o nt h eb a s eo ft h a t ，w e d e s i g n e dan e wx p a t h - b a s e dl o c k i n gp r o t o c o la n dd i s c u s s e di t so p e r a t i o n a lp r o c e s sa n d a l g o r i t h m s ，d e t e c t i n ga n dh a n d l i n gm e t h o d so fd e a dl o c ka n dw a y so fr o l l b a c ko ra b o r to fa t r a n s a c t i o ni nd e t a i l t h e nw ep u tf o r w a r da ne x t e n s i b l ee n c o d i n gs c h e m aw h i c hc a ns u p p o r t x m lt r a n s a c t i o nm o d e l ，b e s i d e s ，w ea l s om a d ead e m o n s t r a t i o no ft h e p r o t o c o l s s e r i a l i z a b i l i t y a tl a s t ，w ep r o p o s e dar e a d o n l yx m l m u l t i - v e r s i o np r o t o c o lb yi n t e g r a t i n gt h e c h a r a c t e r i s t i co fx m l a p p l i c a t i o n s i ta p p l i e sm u l t i - v e r s i o nc o n c u r r e n c y c o n t r o lo ft r a d i t i o n a l r e l a t i o nd a t a b a s et on x d b e c a u s eo ft h er e a d o n l yt r a n s a c t i o nn e v e rb l o c k sw i t ht h e u p d a t i n gt r a n s a c t i o ne a c ho t h e ra n dd o e s n ta l s on e e da n yl o c k s ，i tc a n i n c r e a s ec o n c u r r e n c y o ft r a n s a c t i o n s m o r e o v e r , w em a d ead e m o n s t r a t i o no fi t ss e d a l i z a b i l i t yi nt h ee n d i no r d e rt ov a l i d a t et h ee f f e c t i v i t yo ft h ep r o t o c o l sa n da l g o r i t h m sw ep r o p o s e di nt h i s p a p e r , w ec o n d u c t e dp l e n t yo fe x p e r i m e n t s t h er e s u l ts h o w st h a tt h ep r o t o c o l sw ep r o p o s e d c a l lr e d u c et r a n s a c t i o nr o l l b a c k s ，i n c r e a s es y s t e mt h r o u g h p u ta n di m p r o v ep e r f o r m a n c e e f f e c t i v e l y t h e ya l s oh a v ei m p o r t a n ts i g n i f i c a n c ef o rf u t u r es t u d i e sa 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 ，t r a n s a c t i o n , c o n c u r r e n c yc o n t r o l 1 1 1 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：醐 冁干印月易日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印 刷版和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机 构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、 借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、 缩印或其他复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签 指导教师签名： 隰1 年彩月莎日 日期：叩年印月易e l 中国石油大学( 华东) 硕士学位论文 第一章绪论 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 ) 【1 1 是从标准通用标记语言 s g m l ( s t a n d a r dg e n e r a l i z e dm a r k u pl a n g u a g e ) 【2 j 发展而来的一种新的描述型标记语言， 也是用于i n t e m e t 数据描述与交换的一种新标准，它由国际标准化组织一万维网联盟 w 3 c ( w r o d dw i d ew e bc o n s o r t i u m ) 于1 9 9 8 年2 月推出。虽然x m l 的出发点相当简单， 将数据加上表示其含义的标签，但却带来了异常深远的影响，被誉为构成未来w | e b 的 新工具。 x m l 与先前的h t m l 虽然同为s g m l 的一种应用，然而由于x m l 突出的优点， 人们开始研究用x m l 文档来存储、组织和管理i n t e m e t 上庞大的信息资源。x m l 有着 许多独特的特性f 3 】： ( 1 ) 可扩展性。和现在i n t e m e t 上流行的h t m l 标记语言不同，x m l 没有固定的 标签集合，它只提供了一种通用的、灵活的语法机制，用户能够根据需要自己定义新的 标志和属性名，以便更好地从语义上修饰数据，便于人们理解，并通过命名空间的机制 保证各个x m l 文档之间不会出现名字冲突。 ( 2 ) 自描述性。x m l 基本上使用的是非常简单的数据格式，可以用1 0 0 的纯a s c i i 文本来书写，也可以用其它集中定义好的格式来书写。由于a s c i i 文本是几乎不会“磨 损 的，因此一个x m l 文档丢失一些字节甚至大部分字节，剩下的数据仍然可以读取。 ( 3 ) 简单性。由于x m l 格式以文本为基础，这使得它更容易阅读文档，有时也更 容易测试。 ( 4 ) 结构化数据。x m l 的数据是以树状层次结构保存数据的，这样构造出来的 x m l 文档具有良好的结构性，又具有很强的表达能力，因而对于大型和复杂的文档是 很理想的，它的文件结构嵌套可以复杂到任意程度，能表示面向对象的等级层次，将数 据组织成规则的层次结构。 ( 5 ) 语法和表现形式分离。x m l 文档中表达的是基本的数据，而x m l 数据的表 现形式是在一个单独的文档一样式表中定义的，样式表使用的是可扩展样式语言 ( e x t e n s i b l es t y l e s h e e tl a n g u a g e ，x s l ) 。一个样式表可以为多个x m l 文档提供统一的 表现形式。反之，一个单独的x m l 文档可以通过多个样式表以多种形式来表示。 ( 6 ) 开放性。x m l 规范是由w 3 c 制定的，其数据结构是完全开放的：可以是层 第一章绪论 次型的，也可以是关系型的，或者任何自定义的结构，甚至可以是完全松散的。因此 x m l 数据不依赖于某个特定的平台，使得用x m l 表达的数据更具有通用性。 ( 7 ) 国际化。x m l 支持国际语言编码u n i e o d e ，取名方面也摆脱了原来以英语为 中心的a s c i i 字符的限制而允许使用大多数的世界语，并且x m l 元数据还可以用本地 语言来描述。x m l 样式是真正的i n t e m e t 国际化的基础，全世界的人都可以使用自己的 语言来发挥x m l 的作用。 鉴于x m l 的上述优势，使得x m l 已经成为i n t e r n e t 上数据交换和数据表示的事实 标准。l 正逐步将w 曲转化为一个巨大的数据库。但将数据表示为舭只是对w 曲 这一巨大数据库进行有效处理的第一步，如何对大量的x m l 数据进行有效管理和检索， 对传统的数据管理技术提出了巨大挑战，也为数据库研究提供了良好的机遇。 数据库厂商对这一新的需求迅速做出了响应。目前大多数商业化的关系、面向对象 和对象关系数据库系统都提供了各种x m l 数据的扩展和插件，与此同时，为x m l 数 据管理量身打造的x m l 原生数据库系统也不断涌现。构建于传统数据库之上的x m l 数据管理系统( 即x m l 使能数据库x 】巳d ) 与x m l 原生数据库n x 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 数据库的研究大部分都集中在数据库的索 引构建、查询及其优化、x m l 文档与关系数据库之间的转换机制等方面，在事务及并 发控制方面的研究尚不系统。这主要表现在对事务的处理技术方面大部分所采用的仍是 原有的传统技术，对于x m l 文档等非结构化信息的处理性能方面相对较弱。现有的 x m l 原生数据库产品还远非完善，对数据更新的支持不足一直是现有x m l 原生数据库 系统最大的弱项之一，大部分系统只支持文档级的更新，只有少数系统提供专有的更新 语言或接口支持。随着大量x m l 文档处理需求的不断扩大，必然需要对事务处理技术 进行深化，针对x m l 原生数据库本身的结构特点，在封锁机制以及粒度方面结合x m l 的特性加以改进，从而加快处理非结构化信息的速度，提高事务处理的效率以及存储系 2 中国石油大学( 华东) 硕士学位论文 统的性能。 现在x m l 原生数据库系统缺少对事务的支持固然与x m l 缺乏一种标准的数据更 新语言有很大关系，但同样重要的是更新必然导致并发问题，而目前并没有一种成熟的 x m l 并发控制技术存在。虽然近两年来一些研究人员已经对此展开了研究，并提出了 一些x m l 并发控制技术，但总体来说，对x m l 事务处理技术的研究还处于初级阶段， 在x m l 产品中的应用更是处于萌芽状态，因此，本课题正是针对这一问题进行比较深 入地研究和探讨。 1 2x m l 并发控制研究现状 1 2 1 传统并发控制 数据库系统是面向多用户的系统，事务并发可以提高系统的吞吐量，所以并发控制 在保证系统正确性的同时，并发机制的好坏也直接影响系统的性能，是d b m s 的关键 技术。传统的并发控制理论经过约三十年的发展，已经形成一套非常完善的理论体系【4 】。 并发控制机制是多个事务同时到来时，数据库系统控制事务之间的相互影响，防止 它们破坏数据库一致性的应用机制。传统的并发控制协议可分为两大类，即单版本并发 控制协议和多版本并发控制协议。 单版本并发控制协议总体上可概括为两类：悲观类和乐观类。悲观类协议是当检测 到一个冲突时，就强迫事务等待或者回滚，即使该调度有可能是冲突可串行化的，主要 代表有基于锁的协议、基于时间戳的协议和串行化图检测三种。基于锁的协议可分为两 阶段封锁协议和非两阶段封锁协议。其中最常用的是两阶段封锁协议( t w o - p h a s el o c k i n g p r o t o c o l ，简称2 p l ) ，非两阶段封锁协议中最主要的是树协议。基于时间戳的协议主要 是指时间戳排序协议( t i m e s t a m p o r d e r i n gp r o t o c o l ，简称t o ) 。串行化图检测协议 ( s e r i a l i z a t i o ng r a p h t e s t i n g ，简称s o t ) 维护事务之间的冲突图，并保证图中无环。乐 观类协议中常见的有b a c k w a r d o r i e n t e do p t i m i s t i cc c ( b o c c ) 协议和f o r w a r d - o r i e n t e d o p t i m i s t i cc c ( f o c c ) 协议，主要是有效性确认的方法不同，b o c c 协议中进行有效 性确认的事务执行与所有已提交事务的冲突检测，f o c c 协议中进行有效性确认的事务 执行与所有处于读阶段的事务进行冲突检测。 多版本并发控$ 1 j ( m u l t i _ v e r s i o nc o n c u r r e n c yc o n t r 0 1 ) 技术假设数据项存在多个版本， 每个写操作产生一个新版本。当事务发出一个读操作时，并发控制管理器根据一定的规 则选择一个版本读取其内容。由于读操作有了更多的选择，多版本并发控制协议通常能 获得更好的并发度。常用的多版本并发控制协议主要有多版本时间戳排序协议、多版本 3 第一章绪论 两阶段封锁协议、多版本串行化图检测协议和多版本只读协议。 关系数据库产品中使用的并发控制协议主要有两阶段封锁协议和多版本协议。商业 数据库中s q ls e r v e r 与d b 2 使用基于两阶段封锁的协议。s q ls e r v e r 支持多种锁粒度， 包含数据库级、表级、页级以及记录级的锁。为减少加锁的开销，系统根据隔离级别、 扫描方式、选择率等条件在操作执行前确定合适的加锁粒度，同时也支持锁升格。d b 2 支持表级锁和记录级锁。 基于多版本的并发控制技术在关系数据库系统中也得到了广泛应用。商业数据库中 使用此类协议的有o r a c l e 和s q ls e r v e r2 0 0 5 。o r a c l e 中的协议类似于r o m v ，其中时 间戳被称为s c n ( s y s t e mc h a n g en u m b e r ) 。s q ls e r v e r2 0 0 5 中的多版本并发控制技术 实现了快照隔离。开源数据库中使用多版本技术的也有不少，包括p o s t g r e s q l - - 1 5 、m y s q l ( 特指i n n o d b 存储引擎) 【6 】、f i r e b i r d t 7 1 ，可以说，基于多版本的并发控制技术在关系 数据库中的应用是相当成功的。 1 2 2x m l 并发控制 并发控制是改善数据库系统事务性能最重要的机制，它允许多个事务并发执行并保 证事务的隔离性( i s o l a t i o n ) 和可串行性( s e r i a l i z a b i l i t y ) 。在传统的数据库管理系统领 域，己经广泛地研究了多种并发控制机制以确保并发调度的可串行性，其中，两阶段锁 协议( 2 p 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 数据转化为关系数据库 中的表来实现并发控制时，如文献【8 】中提出的边表机制，锁的粒度比较大，并发度相对 较低；同时谓词锁机制本身就是一个n p 问题，另一方面使用关系数据库系统中的谓词 锁对半结构化数据太严格，因而降低了访问的并发度。另一种思想是利用x m l 数据自 身的特点而提出的并发控制机制，但在x m l 原生数据库领域，并发控制机制的研究才 刚刚开始。目前关于x m l 的并发控制机制主要分为以下几种： ( 1 ) 基于实例加锁的x m l 并发控制机制 4 中国石油大学( 华东) 硕士学位论文 对x m l 文档中的数据实例进行加锁是现有x m l 并发控制协议中最广泛采用的技 术，目前研究者已经提出了十多种不同的协议，可统称为基于实例加锁的x m l 并发控 制技术。这一类协议根据其面向的应用不同又可分为两个子类：一类是基于d o m 接口 提出的加锁协议，一般使用共享锁、排它锁等简单的锁类型。其中包括：s h e h n 一9 ， 1 0 】等提出的基于d o m 树的d o c 2 p l 、n o d e 2 p l 、n 0 2 p l 和0 0 2 p l 四种协议，除了d o c 2 p l 协议是文档级加锁，其它三种加锁协议都是对结点加锁，锁粒度比较小，但是忽略了 x m l 数据的特点以及对x m l 数据进行的操作所具有的特点，因此并发度并不理想。 由m p h a u s t e i n 1 1 ，1 2 , 1 3 】等提出的t a d o m 系列加锁协议，该协议提出的加锁数量比较多， 有加在结点上的锁，也有加在虚拟边上的锁，虽然锁粒度比较小，但是维护锁的代价比 较大，而且主要是面向通过d o m 接口访问x m l 数据的应用。另一类则在锁对象中包 含复杂的路径和谓词条件，面向x p a t h 访问进行优化。关于这方面的研究，s t i j n d e k e y s e r 1 4 ，1 5 】等人提出了两种协议：一种称为路径锁传播协议( p a t hl o e kp r o p a g a t i o n s c h e m e ) ，采用这一协议时要求读锁从上而下传播，对所有查询涉及的非叶结点都需要 加锁；另一种称为路径锁满足协议( p a t hl o c ks a t i s f i a b i l i t ys c h e m e ) ，采用这一协议时 所有锁只加于根结点，其相容性判断主要由路径是否冲突决定，因此复杂度很高。这两 种协议是等价的，只是实现策略不同。基于这两种协议，分别提出了c o m m i ts e h e d u l e r 和c o n f l i c ts c h e d u l e r 两个调度器，c o m m i ts c h e d u l e r 运行两阶段锁技术，在锁冲突时等 待，c o n f l i c ts c h e d u l e r 运行冲突图检测技术，只保证冲突图无环，两个调度器都可以保 证可串行化。s t i j nd e k e y s e r 等人的工作主要贡献在于为x m l 提供了一个精确的事务模 型，但其方法对x p a t h 表达式要求过于严格，只支持“”和“两个操作。类似的工 作还有 1 6 】和【1 7 】。文献【1 6 】中提出使用五种锁机制，p a s s b y 锁表示在执行过程中访问到 某结点但不读取其内容( 可读取其名称) ，其它为r e a d 、w r i t e 、i n s e r t 、d e l e t e 锁。通过 区分p a s s b y 和r e a d 两种读模式可获得更高的并发度( p a s s b y 锁与w r i t e 和i n s e r t 锁不 冲突) 。同时不满足谓词条件的结点的p a s s b y 锁可以提前释放，但该协议不能防止幻象。 刘波等人提出的x p l 协议【3 】与 1 6 】中提出的协议是类似的。文献 1 7 】中的协议能够处理 更复杂的路径表达式，但锁相容性的判断也更为复杂。 ( 2 ) 基于路径索引的x m l 并发控制机制 这类协议是通过对路径索引中的结点加锁来实现x m l 事务的隔离性。这方面最早 的工作是g r a b s 等人提出的d g l o c k 协议i s 。d g l o c k 对事务访问的结点本身并不加 锁，而是对相应的d a t a g u i d e 中的结点加锁，d g l o c k 没有处理d a t a g u i d e 结构发生变 5 第一章绪论 化时的情况，不能保证无幻象及可串行化。p e t e rp l e s h a c h o v 等人提出的x d g l 系列协 议【1 8 1 9 , 2 0 l 对d g l o c k 协议进行了改进，增加了对“操作的支持。 基于路径索引的x m l 并发控制策略的优点是能够大量减少加锁的数量，因为路径 索引的规模通常比x m l 数据本身要小的多。但这类协议也存在很明显的缺点：为保证 并发度，这类协议都必须使用谓词锁，而谓词的判定问题是一个经典的n p 问题，另一 方面，仅仅依靠谓词可能导致产生不必要的伪冲突；与结点路径锁协议簇类似，单独借 助于对路径索引加锁无法有效处理i d r e f 跳转问题，而且对非根据x p a t h 表达式自上 而下进行的查询执行模式的支持也是个问题。 ( 3 ) 其它x m l 并发控制机制 作为在s e d n ax m l 数据库并发控制方面的早期工作，p e t e rp l e s h a c h k o v z 在【2 l 】中提 出了结点编码段封锁的方法，两个事务是否冲突取决于它们封锁的编码段是否有交集， 且锁模式不相容。由于事务获取的锁对象不依附于结点而只是一个编码段集合，而判断 两个集合是否有交集的代价很高，这一工作最终没有在s e d n a 数据库中使用。比较早期 的工作还有庞引明等人提出的x m l 动态树协议x d t p 2 2 1 ，该协议对传统的树形协议进 行了扩展，使之能够处理动态树结点的插入、删除。该协议能够保证冲突可串行化且可 避免死锁，但文中只考虑了排它型锁，锁的类型比较单一，不能满足x m l 数据操作。 此外，k h i n - m y ow i n 等人提出的x s t a m p s 协议【2 3 1 首次将版本化的思想应用到x m l 数 据库的并发控制中，x s t a m p s 是传统多版本时间戳调度协议在x m l 数据库中的应用， 它区分只读事务和更新事务，基于版本化的优点，x s t a m p s 保证读操作不会被阻塞。 x s t a m p s 还引入了数据项的安全系数和事务的安全阈值概念，通过降低对事务可串行性 的需求来提高并发度。 由于x m l 原生数据库正处于发展初期，大多数x m l 原生数据库产品都不提供完 整的事务支持，采用何种并发控制技术也没有公开的文献报道。目前并发控制技术主要 还是应用在一些研究型或实验性系统中，其中l o r e 系统使用页级的两阶段封锁协议【2 4 】， n a t i x 系统【2 5 1 使用的是n o d e 2 p l 系列协议，x d g l 系列协议被应用于作者开发的原型数 据库系统s e d n a 【2 6 】中，x s t m a p s 协议应用在实验性系统n e x t d b l 2 3 1 中。 1 3x m l 相关标准与特征 x m l 是w 3 c 提出的标准，主要特点是支持任意嵌套的层次结构及允许用户自定义 标签。由于其强大的数据表示能力及易于处理的优点，短短几年的时间就在各个领域得 到了广泛的应用。x m l 并不仅仅是一种语言，广义的x m l 是一系列标准的集合，x m l 6 中国石油大学( 华东) 硕士学位论文 作为核心，其它x m l 相关标准都是用它制定并为其服务的。图1 1 表明了与x m l 相关 的主要规范。 x m l 一多夕t 太 文档结构标准文档格式标准文档查询标准文档链接标准文档解析标准 1 l上 上 上1 l d t dc s s x q u e r y x l i n kd o m 上上上上1 l s c h e m ax s l l - i x p a t h l l x p 。i n t e rs a x 图1 - 1x m l 的主要规范 f i g l - it h em a i ns t a n d a r do fx m l ( 1 ) x m l 文档类型定义d t d 与模式定义s c h e m a 。d t d 代表文档类型定义鲫。 一项文档类型定义应规定元素清单、属性、标记、文档中的实体及其相互关系。d t d 可以包含在它所描述的文档的文件中，或者与外部的u r l 相链接。d t d 为应用程序、 组织和兴趣组提供了共同遵循的方法，同时也以文档形式阐述了标记标准并强制遵守此 标准。d t d 的出现赋予了x m l 文档可扩展性、结构性以及可验证性，正因为如此，x m l 才具备了类似于数据库的一些性质。d t d 并不是x m l 文档必须的成份，具有d t d 的 x m l 文档称作v a l i d ，否则就是w e l l f o r m e d 。x m ls c h e m a 为一类文档建立了一个模式， 规范了文档中的标签和文本可能的组合形式。它不仅包括了d t d 能实现的所有功能， 而且它本身就是规范的x m l 文档。x m ls c h e m a 的出现弥补了d t d 的不足【2 踟，并且提 供了一系列丰富的数据类型。 ( 2 ) 可扩展样式语言x s l 。x s l 是用于规定x m l 文档样式的语言 2 9 1 。x s l 凭借 其可扩展性能够控制无穷无尽的标记，而控制每个标记的方式也是多样化的，这就给 w e b 提供了高级的布局特性，例如旋转的文本、多列和独立区域等。x s l 能使w e b 浏 览器改变文档表示法，通过变换样式表，同一个文档可以显示得更大。它支持国际书写 格式，可以在一页上混合使用从左至右、从右至左和从上至下的书写格式。 ( 3 ) 处理x m l 文档的接口d o m 和s a x 。d o m 及s a x 推荐标准由w 3 c 维护， 它们是两个用于x m l 文档，且受到广泛支持的a p i 。d o m 是d o c u m e n to b j e c tm o d e l ( 文档对象模型) 的简称，是对w e b 文档进行应用开发、编程的应用程序接口。作为 w 3 c 公布的一种跨平台、与语言无关的接口规范，d o m 提供了在不同环境和应用中的 标准程序接口，可以用任何语言实现。d o m 通过在内存中构造一个对象树，提供了文 7 第一章绪论 档的一个视图，文档的主要组件结构是对象树中的结点。d o m 采用对象模型和一系列 的接1 3 来描述x m l 文档的内容和结构，即利用对象把文档模型化。利用d o m ，开发 人员可以动态地创建x m l 文档，遍历结构，添加、修改、删除内容等。s a x ( s i m p l e a p i f o rx m l ) 是一种基于流的、以事件处理方式工作的接i ：1 p 0 1 ，它并非一个标准组织的产 品。它是早期x m l 开发过程中，许多开发者为了寻求一种有效的a p i 而制造出来的产 品。s a x 并不把应用程序的注意力集中在整个文档的树状图上，而是在解析时提供事件 驱动的内容。s a x 虽然对系统资源要求低、速度快，但对文档的操作是只读的。相对于 s a x ，d o m 的处理能力更强大，尽管要求大量的系统资源，尤其是对于大型的x m l 文档。 ( 4 ) x m l 文档查询语言x p a t h 和x q u e r y 。x p a t h 是另一种w 3 c 标准【3 l 】，在x s l t 样式表中使用x p a t h 表达式来使得源x m l 文档中的模板与对象( 比如元素、属性、处 理指令、注释和文本串) 相关联。当源树中的对象与特定的x p a t h 表达式匹配的时候， 与这个对象相关联的模板将被实例化，并填入源文档中的数据，然后编写输出文档。 x p a t h 表达式也可以表示数值和布尔运算符等数据类型。所以，x p a t h 也可以用来执行 简单的计算，x p a t h 的目的是在匹配x m l 文档结构树时能够准确地找到某一个结点元 素，完成x q u e r y 的基本功能。x q u e r y 建立在x p a t h 规范之上，其核心是能够通过x p a t h 表达式从文档中选择特殊的结点序列【3 2 1 。x q u e r y 是一种将查询表示成表达式的功能语 言，通过它所支持的多种表达式，它的查询可以有多种不同的形式。x q u e r y 使得x m l 查询变得简洁、易于理解，而且能够非常灵活的查询大量x m l 信息源，包括数据库和 文档。 1 4x m l 数据库 1 4 1x m l 数据库分类 按照x m l ：d bi n i t i a t i v e 提出的分类【3 3 】，可以把现有的x m l 数据库分成三类：支 持x m l 的数据库系统( x m l e n a b l e dd a t a b a s e ，x e d ) 、x m l 原生数据库( n a t i v ex m l d a t a b a s e ，n x d ) 、混合x m l 数据库( h y b r i dx m l d a t a b a s e ，h x d ) 。 ( 1 ) 支持x m l 的数据库系统( d ) x e d 是在原有传统数据库基础上扩展了x m l 支持模块，完成x m l 数据和数据库 之间的格式转换和传输f 3 3 1 。这种格式转换主要是通过增加一个映射层来完成，它是x m l 文档数据与数据库之间转换的桥梁。从存储粒度上，可以把整个x m l 文档作为i b m s 表中一行，或把x m l 文档进行解析后，存储到相应的表格中。为了支持w 3 c 的一些 8 中国石油大学( 华东) 硕士学位论文 x m l 操作标准，如x p a t h 等，x e d 提供一些新的原语( 如o r a c l e 9 i r 2 增加了一些数据 包来操作x m l 数据等) ，并优化了x m l 处理模块。 为了把x m l 文档存储到x e d 中，必须将x m l 文档的模式( d t d 或x m ls c h e m a ) 映射到数据库模式。同样，将数据从x e d 取出来重新组合成x m l 文档，完成相反的操 作。这种转化发生在元素( e l e m e n t ) 、属性( a t t r i b u t e ) 和文本( t e x t ) 上。由于x e d 注重的是数据而非格式，所以在这个过程中，x m l 文档的大部分物理结构( c d a r a 、 实体等) 和一部分逻辑结构( 处理指令、注释等) 都被忽略，而数据被保存。这种转换 可能会丢失信息，一个x m l 文档存储到x e d 后再取出来，可能会变成另外一种