（计算机应用技术专业论文）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 原型数据库( n x r ) ) g 统领 域，事务和并发控制机制方面的研究刚刚起步。目前，很多n x d 都称可以支持事务处理， 但锁的粒度一般比较大，大都是对整个文档的，所以对多个用户并发访问的支持相对较低， 并发度也相对比较低。 本文给出了一种基于x p a t h 路径查询语言的x m l 数据库并发控制机制，主要研究成果 为： 1 给出了x m l 文档定义以及x m l 事务模型的定义，并讨论了在此事务模型下的四种 x m l 数据库操作，包括查询、插入，更新和删除操作。 2 定义了x p l o c k 锁协议模型以及锁协议规则，讨论了并发控制操作流程和锁的申请、 锁的释放等算法，并验证了在此锁协议机制下的并发调度是可串行化调度。 3 给出了死锁的检测与处理方案和事务撤销与中止的处理方法。 4 根据多用户事务并发和x m l 文档结构的特点，利用了支持事务管理的扩展前序编 码来实现对x m l 文档的更新操作。从而实现了x m l 事务的并发控制。 最后围绕这种并发控制机制进行了仿真实验，结果表明本文提出的x p l o c k 锁协议在 并发度，锁粒度等方面是一种有效的x m l 并发控制机制。 关键词：x m l ，事务，并发控制机制。x p l o c k 锁协议 a b s t r a c t t h er e s e a r c ho fx m lf f a n s a c t i o up 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 w h i l es o m e r e s e a r c h e r sh a v ep r o p o s e ds o m ec o n c u r r e n c yc o n t r o lp r o t o c o l s t h ed o n c u r r e n c yt r a n s a c t i o no f m u l t i u s e r s a c c e s s i n gx m l d a t a b a s e sa n dh o wt oa d v a n c ei t se f f i c i e n c yh a sb e c o m e i m p o r t a n t r e s e a r c hs u h j e c t 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 tc a nb ep r o j e c t e di n t o t 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 d t oe n s u r et h em u f 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 e i n b o mc 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 s l dt h eh 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 e c 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 eh e r e i n b e f o r ec 卸、s u p p o r tt h ec o n c u r r e n c y a g c e s so f m u l t i - u s e r st oas i n g l ex m ld o c u m e n th i g he 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 a t i v ex m ld a t a b a s e s ( 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 dt h ec o n c u r r e n c y c 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 fn x dc l a i mt os u p p o r t t 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 e f f e c t i v e l ys u p p o r tt h ec o n c u r r e n c yo fm u f t i u s e r ss i n c e t h eg r a n u l a r i t yo f t 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 ew h o l ed o c u m e n t , n o tt h ef r a g m e n to f t h ed o c u m e n t , s ot h ed e g r e eo f c o n c u r r e n c yi sr e l a t i v e l ys l o w i nt h i sp a p e r , w ep r o p o s eac o n c u r r e n c yc o n t r o lm e c h a n i s mo fx m ld a t a b a s e ，w h i c hb a s e d o nx p a t hl a n g u a g e t h ec o n t r i b u t i o mo f t h i sp a p e ra r ea sf o l l o w s ： i t h ed e f i n i t i o no f x m ld o c u m e n ta n dt h ed e f i n i t i o no f x m l t r a n s a c t i o nm o d e la r eg i v e n , a n dt h i sp a p e rd i s c u s s e sf o u rm a n i p u l a t i o n ss u c ha sq u e r y i n g 、i n s e r t i n g ，u p d a t i n ga n dd e l e t i n g u n d e rt h i sm o d e l ； 2 x p l n c kp r o t o c o la n dr u l e sa r ed e f i n e d w ed i s c u s st h ef l o wo fc o n c u r r e n c yc o n t r o la n d a l g o r i t h m so fa p p l y i n gl o c ka n dr e l e a s i n gl o c k t h ec o n c u r r e n c ys c h e d u l e i n t h i sp r o t o c o l m e c h a n i s mi sp r o v e dt ob eas e r i a l i z a b l es c h e d u l e 3 t h ed e t e c t i n ga n dp r o p o s i n gw a y sf o rd e a dl o c ka r eg i v e n ，b e s i d e s , w ep r e s e n tt h ew a y so f r o l l b a c ko ra b o r to f a t r a n s a c t i o n 4 w ei n t e g r a t et h em u l t i o s e r s t r a n s a c t i o nc o n c u f f a n c ya n dt h es t r u c t u r eo fx m ld o c u m e n t a n di l s ee x t e n d e dp r e o r d e rn u m b e r i n gs c h e m aw h i c hs u p p o r t st r a n s a c t i o nm a n a g e m e n tt or e a l i z e t h eu p d a t i n go f x m ld o c u m e n t , a n da c h i e v et h ec o n c u r r a n c yc o n t r o lo f x m l a tl a s ts o m er e l a t e de x p e d m e n t sa r ed o n e ，w h i c hf o c u s e so nt h i sc o n c u r r e n c yc o n t r o l - i i - m e c h a n i s m t h er e s u l t sh a v ep r o v e dt h a tt h ex p l o c ki se f f i c i e n tf o rx m lc o n c u r r e n c yc o n t r o li n d e g r e eo f c o n c u r r e n c ya n dl o c kg r a n u l a r i t y 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 lm e c h a n i s m , x p l o c k i i i - 学位论文独创性声明 本人郑重声明： 1 、坚持以。求实、刨新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究 成果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外。不包含其他人或其它机构 已经发表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示 了谢意。 作者签名： 日期： 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版：有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅；有权将学位论文的内容编入有关数据库进 行检索；有权将学位论文的标题和摘要汇编出版。保密的学位论文在 解密后适用本规定。 作者签名： 日 期： x m 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 , 2 1 由w 3 c 于1 9 9 8 年提出，是从标 准通用标记语言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 ) t 3 , 4 1 发展而来的一种新的描述 型标记语言，也是用于i n t e m e t 数据描述与交换的一种新标准。它由国际标准化组织万维隔 联盟w 3 c ( w o r l d w i d e w e b c o n s o n i u m ) 于1 9 9 8 年2 月推出。目前已经成为i n t e r n e t 上数据交 换和数据表示的事实标准。虽然x m l 的出发点相当简单，将数据加上表示其含义的标签， 但却带来了异常深远的影响。 众所周知，h t m l ( h y p e rt e x tm a r k u pl a n g u a g e ) 简单与普通性原则使得w e b 的推广受益 非浅，但当人们认识了互联网的价值，准备将w e b 进一步应用到电子商务、e d i 等全新领 域时，却发现在w e b 上大量使用的h t m l 方法，其标志是描述数据如何显示，而不是描述 数据内容的，因而无法反映数据的性质，不利于数据的传输、检索、分类和挖掘。直到可扩 展标记语言x m l 的出现，才从根本上解决了这一问题。 图卜lx m l 是非常理想的网络语言 x m l 与先前的h t m l 虽然同为s g m l 的一种应用，然而由于x m l 突出的优点，人们 开始研究应用x m l 文档来存储、组织和管理i n t e r n e t 上庞大的信息资源。x m l 有许多独特 的特性i ，】： ( 1 ) 可扩展性：和现在i n t c m c n 上流行的h t m l 标记语言不同，x 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 e s 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 r a c t 国际化的基础全世界的人都可以使用自己的语言来发挥x m l 的作用。 正因为x m l 有着上述众多的特点，使得x m l 已经成为互联网事实上的数据交换标准。 x m l 并非h t m l 的直接替代品，h t m l 是注重数据及其表达方式，而x m l 只关心数据本 身。几乎所有大型的商业应用系统都是和数据库相关联的，其实x m l 本身并不是数据库， 从严格的意义上来说，x m l 仅仅意味着x m l 文档。只有当x m l 被用于数据存储时，x m l 以及与之相关的技术结合就组成一个数据库管理系统。该系统应主要由以下五个部分组成 f 6 1 ： ( 1 ) x m l 数据库的逻辑模型的描述语言：d t d 或者s c h e m a 。该模型可以对x m l 数据 库的数据进行存储和访问； ( 2 ) x m l 数据库的数据区x m l 文档，一个x m l 文档就是一个基本的存储单元，相当 于关系数据库中的一个表格； ( 3 ) x m l 数据库中的查询语言：x q u e r y 、x p a t h 、x q l 、x m l q l 、q u i u ； ( 4 ) x m l 转换语言：x s l t ； ( 5 ) x m l 数据库的编辑、管理以及与其它语言的编辑接口：s a x 、d o m ，相当于数据 库管理工具。 - 2 - x m l 并发控制机制的研究 第一章绪论 1 2 研究x m l 数据库多事务并发的必要性 由于x m l 盼广泛应用，x m l 正逐步将w e b 转化为一个巨大的数据库。但将数据表示 为x m l 只是对w e b 这一巨大数据库进行有效处理的第一步。如何对大量的x m l 数据进行 有效地管理和检索，对传统的数据管理技术提出了巨大挑战。也为x m l 数据库研究提供了 良好的机遇。 。 对于数据库而言，信息资源是非常宝贵的，只允许单用户独占数据库的应用适用范围非 常的小。对于在金融、通讯、运输、制造、政府及军事等领域中的数据库应用应该是多用户 共享数据库。用户共享数据库资源会涉及到对数据的读写问题。如果每个用户都只读取数据 库中的数据，则不会有什么问题，但是有的用户可能要更新数据库中的数据，这时就必须有 一个机制来保证这种更新操作不会影响数据库本身的完整性和一致性，不影响其它用户对数 据库的访问。为了满足这一需求，事务和并发控制机制随之出现。简单的说，事务处理的任 务就是在数据库系统的资源共享条件下，确保多个用户能够正确地共享数据库资源，使每个 用户都不受其它用户的影响。 事务作为数据库发展过程中最基本的概念之一。已在各种电子商务平台、企业信息化平 台中获得了目益广泛的应用。然雨，在全球网络化普遍流行的今天，h n t e m e t 已经逐渐替代 以个人计算机为计算中心的单机运行环境而成为新的计算平台标准，这使得数据库应用环境 发生了巨大的变化，基于i n t e r n e t w e b 的应用以及x m l 格式的文档大量涌现，特别是n a t i v e x m l 数据库的出现，使得x m l 并发控制的研究日益重要。 1 3x m l 并发控制的研究现状 在解决如何并发访问x m l 数据库的问题上，一种普遍的思想是将x m l 文档映射到传 统的数据库：关系数据库，利用传统数据库完善的事务机制保证x m l 的多用户并发。握是 这种方法都需要先把x m l 数据转化为关系数据库中的表结构。在转化过程中，不仅要考虑 x m l 数据的存储、更新和检索，而且要考虑其转换语义，其中的约束问题，信息是否丢失 等方面。这本身就付出了很大的代价，同时x m l 数据转化为关系数据库中的表来实现并发 控制时，如文献 1 4 】中提出的边表机制，锁的粒度比较大，并发度相对较低；同时谓词锁机 制本身就是n p 难闫题，另一方面使用关系数据库系统中的谓词锁对半结构化数据太严格， 因而降低了访问并发度。 另一种思想是利用x m l 数据自身的特点而提出的并发控制机制，可以分为以下几种： ( 1 ) 基于实例加锁的x m l 并发控制机制； 这种并发控制方法包括两种：一种是基于d o m 接口提出的加锁协议。其中包括： s h e l m e r l 7 , s 】等提出的基于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 四种协议。除 - 3 x m l 并发控制机制的研究第一章绪论 了d o c 2 p l 协议是文档级加锁，其它三种加锁协议都是对节点加锁，锁粒度比较小，但是忽 略了x m l 数据特点和对x m l 数据进行的操作所具有的特点，因此并发度不不理想。由 m p h a u s t e i n | 9 , t o , u ! 等提出的t a d o m 系列加锁协议，该协议提出的锁数量比较多，有加在节 点上的锁，也有加在虚拟边上的锁，虽然锁粒度比较小，但是维护锁的代价比较大，而且主 要是面向通过d o m 接口访问x m l 数据的应用。另一种是基于x p a t h 提出的加锁协议，文 献【1 7 】描述了一种基于x p a t h 的锁机制，并提出读锁和写锁的冲突检测算法，能够处理更复 杂的路径表达式，但锁相容性的判断也更为复杂 ( 2 ) 基于路径索引的x m l 并发控制：是通过对路径索引中的节点加锁来实现x m l 事务 的隔离性。这方面最早的工作是g r a b s 等人在文献 1 4 1 中提出的d g l o c k 协议。d g l o c k 对事务访问的节点本身不加锁，而是对对应的d a t a g u i d e 中的节点加锁i x l o c k 没有处 理d a t a ( u i d e 结构发生变化对的情况，不保证无幻象及可串行化。 ( 3 ) s i l b e x s c h a t z 和k e d e m 提出的树加锁协议( t r e ep r o t o c 0 1 ) ”是基于静态树结构数据而定 义的。但是，文中的树加锁协议是静态树协议，因为它是基于一个前提：所操作的树型数据 是静态的，不考虑x m l 数据的插入、删除等操作。而我们知道，x m l 数据是动态变化的 树型结构，插入、删除等操作是不可避免的。所以，这种树协议是不能适应实际需求的。 为了改进静态加锁协议，使其适合x m l 数据库，文献【1 6 】提出了一种x m l 动态树加 锁协议x d t p ( x m ld y n a m i ct r e ep r o t o c 0 1 ) 该协议能继续保持静态树协议的特性：可串行 化和无死锁，但是它只考虑了排它型锁，锁类型比较单一，不能满足x m l 数据操作。 1 4x m l 相关标准与特征 x m l 是w 3 c 提出的标准【，主要特点是支持任意嵌套的层次结构及允许用户自定义 标签。由于其强大的数据表示能力及易于处理的优点，在短短几年就在各领域得到广泛的应 用。 1 4 1x m l 的相关标准 x m l 并不仅仅只是一种语言，广义的x m l 是一系列标准的集合，x m l 作为核心，其 他x m l 相关标准都是用它制定的成为服务的。图1 - 2 表明了x m l 相关的主要规范。 - 4 图卜2 x m l 相关规范构成图 1 4 2 处理x m l 文档的接口( d o m 、s a x ) d o m 及s a x 推荐标准由w 3 c 维护。它们是两个用于x l v l l 文档，且受到广泛支持的 a p i 。换句话说，d o m 和s a x 是处理x m l 文档的两种方式。 d o m 是d o c u m e n to b j e c tm o d e l ( 文档对象模型) 的简称，是对w e b 文档进行应用开 发、编程的应用程序接口( a p i ) 。作为w 3 c 公布的一种跨平台、与语言无关的接口规范， d o m 提供了在不同环境和应用中的标准程序接口。可以用任何语言实现。 d o m ( d o c u m e n to b j e c tm o d e l ) 是一种独立于平台和语言的接口，它对x m l 文档进行 分析后，d o m 通过在内存中构造一个对象树，提供了文档的一个视图。文档的主要组件结 构是对象树中的节点。d o m 采用对象模型和一系列的接口来描述x m l 文档的内容和结构， 即利用对象把文档模型化。这种对象模型实现的基本功能包括： 描述文档表示和操作的接口； 接口的行为和属性； 接口之间的关系以及互操作。 d o m 可对结构化的x m l 文档进行解析，文档中的指令、元素、实体、属性等所有内 容个体都用对象模型表示，整个文档被看成是一个有结构的信息树，而不是衙单的文本流， 生成的对象模型就是树的节点。对象同时包含了方法和属性。因此，对文档的所有操作都是 在对象树上的进行在d o m 中，树中的一切都是对象，不管是根节点还是实体的属性。 在d o m 中主要有以下三个对象： x m l 文档对象x m l 文档既是一种对象，同时又代表整个x m l 文档。它由根元素 和子元素组成。 x m l 节点对象x m l 节点对象代表的是x m l 文档内部的节点，如元素、注释。名 字空间等。 x m l 节点列表x m l 文档模块列表代表了节点的集合。 利用d o m ，开发人员可以动态地创建x m l 文档，遍历结构，添加、修改、删除内容 等。其面向对象的特性，使人们在处理x m l 解析相关的事务时节省大量的精力，是一种符 合代码重用思想的强有力编程工具。 s a x ( s i m p i ea p if o rx m l ) 是一种基于流的、以事件处理方式工作的接口l “，它并非一 个标准组织的产品。它是早期x m l 开发过程中，许多开发者为了寻求一种有效的a p i 而制 造出来的产品。s a x ，并不把应用程序的注意力集中在整个文档的树状图上，而是在解析时 提供事件驱动事件的内容。 s a x 虽然对系统资源要求低、速度快，但对文档的操作是只读的。相对于s a x ，d o m 的处理能力更强大，尽管要求大量的系统资源，尤其是对于大的x m l 文档。 一5 - x m l 并发控制机制的研究第一章绪论 1 4 3 文档类型定义( d t d ) 与x m l 文档模式定义( s c h e m a ) d t d 代表文档类型定义【2 i 】。一项文档类型定义应规定元素清单、属性、标记、文档中 的实体及其相互关系d t d 为文档结构制定了一套规则。例如，一项d i d 指定一个b o o k 元素有一个i s b n 子元素，一个1 1 t l e 子元素、一个或多个a u t h o r 子元素。d t d 以元素、 实体，属性和记号的标记声明来做到这一点。d t d 可以包括在包含它描述的文档的文件中， 或者与外部的u r l 相链接。d t d 为应用程序、组织和兴趣组提供了麸同遵循的方法，同时 也以文档形式阐述了标记标准并强制遵守此标准。 d t d 具有以下特点：它是易于学习的，并且具有同一个标准：它是成熟的，并可以在 多个应用程序中应用 它有一大批专门的开发者，这些开发者从s g m l 的全盛期就开始使 用；有很多关于使用d i 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 c d ， x m ls c h e m a 为一类文档建立了一个模式，规范了文档中的标签和文本可能的组合形 式。它不仅包括了d t d 能实现的所有功能，而且它本身就是规范的x m l 文档。x m l s c h e m a 弥补了d t d 的不足【2 2 1 ，提供了系列丰富的数据类型：包括数字型、布尔型、整型、日期 时间、u r i 、十进制数等，而且它还支持由这些简单的类型生成更复杂的类型；可以由用户 自定义数据类型；支持属性分组。属性的应用范围是多种多样的，有的是针对所有元素。有 的则专门针对图形元素。 d t d 定义的内容模式是封闭的，而x m ls c h e m a 定义的内容模式是开放的，可以随时 更新，支持域名。 1 4 4 可扩展语言( x s l ) x s l 是用于规定x m l 文档样式的语言( 2 3 1 。x s l 的处理流程如图1 3 所示。x s l 能使 w e b 浏览器改变文档表示法。例如数据的显示顺序改变，就不需要再与服务器进行交互通信。 通过变换样式表，同一个文档可以显示得更大，或者经过折叠只显示外面的一层，或者变为 打印格式。可以设想一个适合用户学习特点的技术手册，它为初学者和更高一级的用户提供 不同的样式。而且所有的样式都是根据同样的文本产生的。 x s l 凭借其可扩展性能够控制无穷无尽的标记，而控制每个标记的方式也是无穷尽的。 这就给w e b 提供了高级的布局特性。例如旋转的文本、多列和独立区域。它支持国际书写 格式，可以在一页上混合使用从左至右、从右至左和扶上至下的书写格式。 6 x m l 并发控制机制的研究 第一章辫 论 圃固 f + 寒毫lo_ - 亘至囊 ；亳习一 图1 - 3 x s l 处理流程 1 4 5x m l 文档查询语言( x p a t h 、x q u e r y ) ( 1 ) x p a m x p a t h l 2 4 】是另一种w 3 c 标准，在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 p a t h 中的基本要素是和x m l 文档中的组成要素相对应的，具体包括： ( 1 ) 根节点。根节点是一棵树的开始，根节点是唯一的。树中的其它所有元素节点都是 它的子节点或后代节点。对根节点的处理机制与其它节点相同。在x p a t h 中对树的匹配总是 从根节点开始。 ( 2 ) 元素节点。元素节点对应于文档中的每一个元素，一个元素节点的子节点可以是元 素节点、注释节点、处理指令节点和文本节点。可以为元素：宵点定义一个唯一的标识i d 。元 素节点可以有扩展名，包括命名空间u r l 和本地命名。 ( 3 ) 文本节点。文本节点包含了一组字符数据，即c d a t a 中包含的字符，文本节点没有 扩展名。 ( 4 ) 属性：肯点。每一个元素节点由一个相关联的属性节点集合，元素是每个属性节点的 父节点，但属性节点却不是其父元素的子节点，也就是说通过元素可以查到属性节点，面反 之不成立，原因在于x p a t h 规定元素的属性节点是单向的。此外，元素的属性节点不能被共 享，不同的元素节点不能同享一个属性节点。 ( 5 ) 命名空间节点。每一个元素节点都有一个相关的命名空间节点集。在x i v i l 文档中， 命名空间是通过保留属性声明的，因此，在x p a t h 中该类节点与属性节点很相似，它们与父 元素之间的关系是单向的，并且不具有共享性 ( 6 ) 处理指令节点。处理指令节点对应以x m l 文档中的每一条处理指令。它也有扩展名， 扩展名的本地命名指向处理对象，而命名空间部分为空。 ( 7 ) 注释节点。注释节点对应英语文档中的注释。 ， x m l 并发拧制机制的研究 第一章绪论 x p a t h 查询路径表达式： 在x p a t h 语法中，是通过一系列的路径匹配规则来实现的。 ( 1 ) 路径匹配。路径匹配与文件路径的表示相仿，主要有以下几种路径操作： 用，表示节点之间的父子关系，如a b c d 表示节点“a ”的子节点为“b 竹，并且” 的子节点为“d ”，这里“，a ”表示根节点。 用锄”表示节点之问的祖先一后代关系，如 d ”表示所有在x m l 文件中出现的d 元 素。再比如“a e 表示所有的以a ”为祖先节点的e 元素。 用“”表示通配符，如“a b c * ”，表示a 元素一b 元素一c 元素下的所有子元素。 ( 2 ) 位置匹配。对于每个元素，它的各个子元素是有序的。如 “a 8 c 1 】”，表示a 元素一b 元素一c 元素的第一个子元素； “，a 愿，c 【l 酬”表示表示a 元素一b 元素一c 元素f l 勺最后一个子元素： a b c p o s i t i o n 0 1 ”表示表示a 元素一b 元素一c 元素之下的位置号大于l 的元素。 ( 3 ) 属性及属性值。在x p a t h 中，可以利用属性及属性值来匹配元素，要注意的是元素 的属性名前要有“ 前缀。例如，b 【 i d ”表示所有具有属性i d 的b 元素。再如 1 3 【 i d - 。- m r 表示i d 值为m ”的b 元素。 ( 4 ) 亲属关系匹配。x m l 文件是树型结构，任何一个节点都不是孤立的，它们之间具有 亲属关系，如父子关系、祖先后代关系、兄弟关系等。 在对元素进行匹配时，可以利用上述关系进行匹配。在x m l 查询中，x p a t h 路径表达 式如果是以叩开头的，就表明该路径表示的是一个绝对路径；以“，开头则表示在文档中的 任意位置查找。x p a t h 路径表达式包括以下几种形式： ，p l p 2 饥 p l l 彬p , p l p 2 ，p b 固悔札n 瓢 ( 2 ) x q h e r y x q u e r y 是由w 3 c 组织制定的标准口q 。该标准使锝x m l 查询变得简洁、易于理解，而 且能够非常灵活的查询大量的x m l 信息源，包括数据库和文档。这使得x q u e r y 可以查询 异构的数据源，通过将这些数据源的数据翻译成x m l 文档。 x q u e r y 建立在x p a t h 规范之上，其核心是能够通过x p a t h 表达式从文档中选择特殊的 节点序列。x q u e r y 是一种将查询表示成表达式的功能语言，通过它所支持的多种表达式， 它的查询可以有多种不同的形式，x q u e r y 还允许通过嵌套类s q l 的子句来创建复杂查询， 以及通过将x m l 构造器直接包括在输出中来创建复杂结果。x q u e r y 模块包括三个部分： 名字空间和模式声明、函数定义、查询表达式，其中模式声明和函数定义不是必须的。x q u e r y 的特性之一是利用功能强大的f l w r 表达式进行查询。f l w r 表达式是一种典型的能够完 - 8 x m l 并发控制机制的研究第一章绪论 成具有菜种实际意义豹查询的表达式。f l w r 表达式包含模式匹配、过滤选择和结果构造三 种操作。f l w r 语句是x q u e r y 所具有的最接近于s q l 的语句。此外，x q u e r y 还提供了函 数调用和用户自定义函数等功能。 1 5 x m l 数据管理 由于x m l 的流行，与x m l 相关的数据管理产品不计其数，著名的x m l 数据库研究者 及顾问r o n a l db o u r r e t 在【2 6 】中将x m l 数据管理产品分为中间件、i d e 和编辑器、x m l 使 能数据库( ) ( m l - e n a b l e dd a t a b a s e ，简称x e d ) 、x m l 原生数据库( x m l - n a t i v e dd a t a b a s e ， 简称n x d ) ，x m l 服务器、包装器，内容管理系统、x m l 查询处理引擎、x m l 数据绑定 等9 大类，其中与数据库技术密切相关的是x e d ，n x d 和x m l 查询处理引擎。 x e d 为以扩展形式提供x m l 支持的传统数据管理产品，一般构建于关系数据库之上， 为现有系统提供了支持x m l 数据的快速便捷的方式，因此引起了研究者的大量关注和主流 数据库厂商的青睐。x e d 的核心是x m l 毅据关系存储映射技术。研究者提出了众多x m l 数据到关系数据的映射策略，可分为模式不敏感映射和模式敏感映射两大类。模式不敏感映 射使用关系表示节点间的父子关系i ”- 3 0 l ：模式敏感映射根据x m l 模式定义、人工指定的映 射配置文件或某种数据挖掘方法确定映射方式p ”。由于模式敏感映射利用了部分x m l 语 义信息，效率一般比较高，因此o r a c l e ，d b 2 ，s q ls e r v e r 等商业化数据库中都采用这一方 式。由于x e d 系统对外提供x m l 操作界面，底层却以关系模型等实现，因此还需要进行 x m l 查询到s q l 查询的转换。而这一转换就可能导致一部分语义信息的丢失，使得对部分 查询难以进行有效的优化】。 n x d 是为存储与杏询x m l 数据而特殊设计的数据库管理系统。目前这样的系统有很 多，可以在【2 6 】中获得它们的列表，其中产品主要有b e r k e l e yd bx m l ，i p e d o ，x i n d i c e 等， 研究性系统主要有l o r e i “，t i m b e r l 3 6 。t a m i n o p 7 j 坞， 各种n x d 系统的具体实现技术大不相同，但总体来说，存储系统、x m l 查询处理技 术和事务管理是目前n x d 研究的重点。存储系统是x m l 原生数据库的基础，要解决的主 要问题是如何将x m l 文档中的节点组合成物理记录。组合方式主要可分为三大类。第一类 是基于文档的组合，如a p a c h e 的开源x m l 原生数据库管理系统x i n d i e e t ”1 就采用这种方法， 即一个文档就对应条物理记录，采用相同模式的文档被组合在起。第二类是基于元素的 组合，即将同类元素组合，采用这种方式的系统有l o r e 和t i m b e r 等。第三类是基于子树 的组合，即尽量将属于同一子树的节点组合存储在一条物理记录中，中国人民大学开发的 x m l 原生数据库o r i e n t x 中使用的l p b c 方法就是一种基于子树的组合方法1 3 9 1 为提高空闯 效率，数据压缩技术也在n x d 存储的研究热点之一“o t 4 1 l 。 查询处理是数据库的核心。因此对x m l 查询求解技术的研究也非常多，包括查询代数、 执行算子、代价估计、索引设计、等价变换和代数优化等多个方面。索引是提高查询效率的 9 x m l 并发控制机制的研究 第一章绪论 主要途径，目前n x d 系统中采用主要有值索引，边索引和路径索引等，其中路径索引最为 重要，也摄为复杂，是x m l 索引技术研究中的热点。路径索引首先是在面向对象数据库中 提出的h 2 i ，但在x m l 数据库中应用更为普遍。路径索引是原x m l 文档的简化表示，典型 的有d a t a g u i d e t 4 ”，卜i n d e x , f & b i n d e x 【删等，文献【4 4 】中的半相似性概念为路径索引研究 提供了主要理论工具。x m l 索引方法主要包括： ( 1 ) 基于图的遍历方法即基于路径的索弓 方法，主要是t - i n d e x 索引，主要包括d a t a g u i d e 索引和a p e x 索引。 ( 2 ) 基于字符串搜索的索引方法，主要有f a b r i c 索引。 ( 3 ) 基于编码方案的索引方法，主要包括h i e r a r c h y 索引、先序后序( p r e n o g ) ( 区间编 码) 索引和相对区间坐标( r r c ) 索引。具体索引分类见图l - 4 所示。 执行算子研究中最突出的是结构化联接技术h 5 问，该技术主要优化两个节点集之间祖先 ，后裔关系的匹配，是x m l 查询处理技术的特点之一。 但以数据库的角度审视现有的n x d 系统及其研究，可以发现n x d 技术要达到成熟， 还有很长段路要走，其中的一个障碍是事务管理。虽然当前研究者们已经提出了一些x m l 的并发控制方式，但现有x m l 产品中的并发控制技术并不是很成熟，或者只是依赖于关系 数据库中的并发控制技术，因此并发度并不高。 x m l n d c 岫 m e t h o e a f a b r i c h i 盯a r c 畸 1 - 4x m l 索引分类图 1 6 本文研究内容及论文结构 1 6 1 本文研究内容 由于n a t i v ex m l 数据库的出现，面向x m l 文档的信息检索能力变得日益重要。如何 使信息共享，而且在并行访问时相互不受影响，这是本文要讨论的内容，即x m l 数据并发 1 0 - 耐 蝴嘶m j 尺 x m l 并发控制机制的研究 第一章绪论 控制机制研究的主要内容。 研究x m l 并发控制机制我们需要考虑以下几方面的内容： x m l 并发