（计算机软件与理论专业论文）native+xml数据库编码方案研究.pdf

摘要 摘要 随着网络技术和网络服务的飞速发展，) 0 v 儿( c x “e 地i b l em 捌( i l pl 吼g l l a g e ) 越来越多地活跃在数据交换和存储领域。大量礼数据的出现，要求数据库具 有更有效的儿数据管理能力和更快、更精确的) 0 v 皿数据查询能力。n a t i v e 沮，数据库由此应运而生，它以一种自然的方式来存储和管理儿数据。存 储和查询) 。m ，数据是n a t i 、，e v 几数据库的主要功能，因此，相关的底层技术 如编码方案、存储方案和索引方案都对数据库的性能起着关键的作用。 本文在分析总结国内外已有的n 撕v e v 几数据库研究成果的基础上，对 n 撕v e 儿数据库的编码方案进行了深入的研究，提出了一种新的编码方案 ) a ) n ，这种编码方案具有前缀性和字典有序性，能够有效地支持各种咀，查询， 并且具有很好的动态性和较短的编码长度，在更新操作之后不需要重新编码； 在n 编码方案的基础上，给出了一种采用分页存储策略的细粒度存储方案， 它使用b + 树结构来实现快速确定咀。结点的存储位置，具有较好的咀。文档 存取性能；根据) n 编码方案和相应的存储方案，给出了一种包含值索引和结 点索引的索引方案，它使用b + 树结构的变体来建立索引，大大减少了访问磁盘 加的次数；最后还探讨了基于这些底层技术的查询处理方案，给出了各种结构 连接算法。 关键字：n a t i v c 仉数据库编码方案存储方案索引方案 a b s t 阻c t a b s t r a c t w i 也t l l e 船p i dd v e l o p i n e n to fn e t w o r kt e c h n o l o g i 髓趾dm 帆m r ks e r v i c e s ， ) ( m l ( c x c c 璐i b l em a r k u pl 粕g l l a g e ) e n l i v e 璐i n 口s i i l 百yi nt l 他d c 衄a i 璐o fd a l a e x 曲哪百n ga i l ds t l ) 血g t h e 锄c r g e n c eo fv a s tx mld a ：c ar e q u e g t sl h ed a 例b a t 0 m 姐a g cx m ld a t am o r ee 饪t i 、，e l y ，锄dt oq l 旧叮x m ld a l t am o r eq l l i d d ya n d p r c c i s c l y n a t i v e 也d a 乜b a ，砒d c hs t 咐s 缸dn 瑚i a g e s 见d a t ai nan a 缸a l w 觋t h 璐黜i n t o b e i n g s 劬ga n dq 1 1 e r y i n g t h e x m 吐d a 土aa r e t h e m a i n 如似觚 o fn a l i v ex m ld 眦i b a f o r e ，r e l a n v e u n d 盯l y i n gt e c h n i q i l e s 跚c h 龉 如m 1 ) e r i n gs c h 黜，s t o r i i l gs c h 锄e 如di n d e x i n gs c h e m ea l lp l a yak e yr o l ei nt h e p e r f o 】c m a n c eo f n a t i v e ) m 几d a t a b a s e o n 血cb 嬲i so f 删d 归n ga n ds l l r 衄a r i z 啦n a t i v e ) 0 甩d a t a b a s cr e 黜h i n g r c s l l l t sb o t ha th 伽a n da ：b m a d t h i st h c s i sh 勰ad e e pr c a r c ho nt h en 哪b e r i n g h 础o f n a t i v cx m ld a t a b a a n db r i n g sf 0 】啊a r dan e w 册m b e r i n g h e m e ，w h i c h i sn 锄e d 嬲x d n t h en e ws c h c m eu sap r e f i x - 舶ee i l c o d i n g 锄d 锄彻g e st h e c o d c so f ) 。“l d e s i n d i r 。c t o r y 耐c r ，“c 缸s u p p o n q u e r ) ，i n g v a r i o 璐煳l d a t a e 虢c t i v e l y f u t h e 册o r e ，) ni sd y n 锄i c ，w h i c h l a k e si ts u p p o nu p d 鲥n gw i 也o u t r e l a _ b e l i l l g 面s t i i l gn o d e s ，锄dh a ss h 咖l c n g t l lo f d ec o d c s t h i st h e s i st h 百v e s a 痂舱l yg r a n u l a rs t i 试n gs c h e m ek 幽耐o nx d n nu sp a g i n gs t o r i n g 蛐f a t e g y 觚d b + 懈s 拓u c t i 鹏t o h i e 、，er a p i di d e n t i f i c 撕o no f 以ln o d e ss 吣l o c a t i o n ， t h a ti th 舔ab e t l 髓p e r f o 珊a n c e0 nv i s i 伽g 咀。d o c u m e n t s b 雒c do n ) n 锄d c o r s p o n d i 唱s 蕾o r i i 培s c h e m e ，姐i n d e x i n gs c h e m ei s 百v e ni tw e sa v a r i a n t 蛐彻：t u r e o f b + 仃e et ob m l dv a l u e 砌e x 锄dn o d ei n d e x ht h i sw a y 。i tr e d u c e st h em 蚰b e ro f v i s i t 堍d i s k 删e l y f i n a l l y 1 h i s 也e s i sd i s 哪s 血e 蝴g h c m e b a s e do n t h e 础l y i n gt c c h n i q u e sa n dp r o v i d e st h ev 鼍i r i o 惜曲m c t u f a ll i i l ka 1 9 0 r i t h 脚 k e ，rw o r d s ：n 砒i v e v 儿血劬a ，n u m b 痂gs c h e m e ，咖r i n gs c h 锄e ，i n d e x i n g s c h 锄e 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制沧文的部分或全部内容用于学术活动。 学位论文作者签名：到殿鑫 z d d 占年歹月；d 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月 日 各密级的最长保密年限及书写格式规定如下 内部5 年( 最长5 年，可少于5 年) 秘密1 0 年( 最长1 0 年，可少于1 0 年) 机密2 0 年( 最长2 0 年，可少于2 0 年) 。j _ 一= ； 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均己在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名：刘殿鑫 z p 护莎年歹月3 d 日 第一章引言 第一章引言 第一节n a 蜥ex m l 数据库研究的意义 网络技术的飞速发展使得网络信息不断扩充膨胀，海量的结构化和半结构 化的数据使得人们在检索网络信息时往往陷入困境，需要一种可以简单通用的 表示这些数据的方法。在这种背景下，) 0 沮应运而生。 v 几( e x t e 璐i b l em a r k u pl a n g l l a g c ，可扩展标记语言) 【l j 是一种自描述的、 半结构化的和可扩展的标记语言。它以其通用、可延伸的特征逐渐成为数据描 述和交换的标准，并在许多领域内得到广泛的支持和应用。如在电子商务( e c ) 和 企业应用集成( e a i ) 应用领域，) ( m l 已成为通用信息交换标准格式。电子商务全 球化标准e b ) 函儿圆，具有我国自主知识产权的电子商务交易规范语言伽m ， 中国国情的电子政务语言规范c n g ) m 几【4 】等，都采用。格式。 随着v m 技术应用的深入，将会有大量的) m 几文档出现。同时，m 。也 作为异构数据集成的中间格式出现，这意味着存储在各种不同格式的数据库中 的数据都会被转化为儿。因此，如何有效地存储和管理大规模) 几文档、 如何实现更快、更精确的查询札数据已经成为迫切需要解决的研究课题。 对儿数据库的研究主要有两种方法：一种是) 。咀，e n a b l c d 数据库垆j ，它 是在已有的关系数据库系统或面向对象数据库系统的基础上扩充相应的功能， 使其能够胜任沮。数据的处理。m ，e n a b l e d 数据库的优点是可以充分利用已 有的非常成熟的数据库技术；但其缺点是不能利用，几数据自身的特点，如结 构化、自描述性等特征，使得在处理) m 几数据的时候要经过多级复杂的转换， 这必将带来效率的降低。另一种则是n a t i v e 订l 数据库【6 j ，它是专门设计用于 存储和管理) 函几文档的数据库，将) 。v 儿文档和元素作为基本结构。n 撕v e ) 0 沮。数据库充分考虑到) 函几数据的特点，以一种自然的方式来处理v 几数据， 能够从各方面很好地支持) q m ，的存储和查询。 综上所述，n 撕v e 皿，数据库在处理) 。舡，数据时拥有其他数据库所不能 比拟的天生优势，在面临大量的) m 也数据管理与查询需求时，n a t i v e ) m 几数 据库是最好的选择。目前我国的电子商务、电子政务正在全面开展，其数据普 第一章引言 遍采用沮。格式进行表示、交换和存储，对咀。数据库的需求也与日俱增。 因此，n a t i v e ) m 几数据库的研究与实现具有十分重要的理论意义和应用价值。 第二节本文的主要研究工作和创新之处 本篇论文在分析总结国内外已有的n 破v e m 。数据库研究成果的基础上， 对n a l i v e 儿数据库的编码方案进行了深入的研究，提出了一种新的) m 也动 态编码方案，并且给出了相应的数据库存储方案和索引方案，最后还探讨了基 于这些n a t i v e ) m m 数据库底层技术的查询处理方案。主要的研究工作和创新之 处如下： 1 对国内外已有的各种n a t i v e 儿数据库结点编码方案进行了研究和分析， 总结出三种类型并比较了各自的优缺点。 2 提出了一种新的，匝动态编码方案) a ) n ，它不同于传统的结点编码方案， 这种编码方案能够从本质上支持结点的更新操作，既提高了执行效率，又节 省了存储空间。 3 在) n 编码方案的基础上，给出了一种采用分页存储策略的细粒度存储方 案，它使用b + 树结构来实现快速确定沮。结点的存储位置，具有较好的 d l 文档存取性能。 4 根据) n 编码方案和相应的存储方案，给出了一种包含值索引和结点索引 的索引方案，它使用b + 树结构的变体来建立索引，大大减少了访问磁盘 的次数 5 根据) n 编码方案和相应的存储方案、索引方案，探讨了基于这些底层技 术的查询处理方案，给出了各种结构连接算法。 第三节论文的组织结构 本文围绕n 础e v m 数据库的编码方案，对相关的技术进行了研究和论述， 文章的整体结构如下： 第一章引言。简单介绍了v 匝技术的发展现状和m 。数据库的研究背景， 阐述了研究na ：i j _ v e ) m 也数据库的重要意义。 第二章n a l i v e 咀，数据库分析。介绍了沮。及相关的技术，给出了n a t i 、忙 2 第一章引言 见数据库的定义，分析了n a t i v e ) 。v 儿数据库的特性，研究了n a t i v e 沮。数 据库的系统结构及各个模块的功能，总结了n a t i v e 沮。数据库的研究现状。 第三章编码方案研究。在分析总结了国内外已有的各种na c i _ v e 沮。数据 库结点编码方案的基础上，提出了一种新的) 函几动态编码方案) n 。 第四章存储方案及索引方案研究。在第三章提出的) 口) n 编码方案的基础 上，进一步给出了其相应的数据库存储方案和索引方案。 第五章查询处理方案研究。基于第三章和第四章提出的n a t i v e 沮。数据 库底层设计方案，探讨了其相应的查询处理方案。 第六章总结与展望。总结了全文，并对进一步的研究工作提出了建设性意 见。 3 第二章n 撕v ex h 礼数据库分析 2 1 1 舳综述 第二章n a 晰ex m l 数据库分析 第一节毗及相关技术介绍 。( e x t e n s i b l e m a f k u p i 加毋】a g e ，可扩展标记语言) 是由w o f l d w i d c w c b c 咖r t i 啪( w 3 c ) 的沮。工作组定义的一种自描述的、半结构化的和可扩展 的标记语言。这个工作组是这样描述该语言的【刀：“) 0 v 几是s g m l ( s t a n d a r d g 锄e r a i i z c dm a r k u pl a 矗g i l a g e ，标准通用标记语言) 的子集，其目标是允许普通 的s g m l 在w e b 上以目前h n 仉( h 卿e 斌m m 唧l 趾9 1 1 a g e 。超文本标记语 言) 的方式被服务、接收和处理。) m 几被设计成易于实现，且可在s g m l 和 h n 沮，之间互相操作。” ) 。沮。是一套定义语义标记的规则，这些标记将文档分成许多部件并对这些 部件加以标识。它是一种元标记语言，用户可以定义自己需要的标记。这些标 记必须根据某些通用的原理来创建，但是在标记的意义上具有相当的灵活性。 ) 0 ，几标记描述的是文档的结构和意义，它不描述页面元素的格式化。可用样式 单为文档增加格式化信息。文档本身只说明文档包括什么标记，而不是说明文 档看起来是什么样的。 ) m 也作为s g m l 的一个简化子集，将s g m l 的丰富功能与 r r m l 的易用 性结合到一起。它具有以下的特点： 1 自描述性。咀。允许根据各种不同的规则来制定标记，实现了用定义它 们自己的标记集来说明文档内容的功能。 2 半结构化。) 0 儿文档的结构可以通过模式来描述。有了模式，就可以方 便地验证文档的有效性。 3 可扩展性。沮，是一种元标记语言，用户可以定义自己需要的标记。因 此，) m 几允许开发各种不同专业的特定领域的标记语言。 4 可移植性。由于血是以文本形式描述的，所以适合于各种平台环境 的数据交换，在一种平台上编写的) m 也文档无须任何更改即可移植到其它平台 4 第二章n 砒i v ex m l 数据库分析 上。 5 内容和表现形式分离。沮。文档只描述数据本身，而数据的表现形式则 由另外的处理程序来完成，具有内容和表现形式相分离的特点。 ) m 儿的这些特点使其逐渐成为数据描述和交换的标准，并在许多领域内得 到广泛的支持和应用。 2 1 2 ) m 几文档的类型 ) m 几文档可以划分为两种类型：以数据为中心的文档和以文档为中心的文 档。 ( 1 ) 以数据为中心的文档 以数据为中心的文档就是将沮。用作数据的传输载体，提供给机器使用的 文档，如公司的销售订单、航班时刻表、科研数据、股市汇率等。这种文档的 特点是：结构相当规整，数据粒度精细( 即最小的独立数据单位只存在与 p c d a l 隗元素或属性这一级别) ，很少或没有混合内容。除非在对文档进行验 证的时候，否则同级元素或p c d a l a 的出现次序一般来说并不重要。 ( 2 ) 以文档为中心的文档 以文档为中心的文档通常是供人使用的，如书籍信息、e - m a i l 、广告等。这 种文档的特点是：结构松散，数据粒度大，混合内容多。同级元素或p c d u a 的出现次序非常重要。 在实际的使用中，以数据为中心的文档和以文档为中心的文档之间的差别 不一定很明显。例如，一种以数据为中心的文档比如发票，可能含有结构不规 则的、大粒度的数据比如零件说明；一种以文档为中心的文档比如用户手册， 可能包含结构规则的、细粒度的数据比如修订日期。 2 1 3 d ) 和帆s c h e i n a 为了使舭文档能够被帆解析器正确地解析出来，) m 几文档必须遵循 一组特定的规则，遵守这组规则的咀文档被称为良构的( w e l l f o n n e d ) ，良 构是沮。文档必要的最起码的标准。在大多数应用中，为了得到有效的皿 文档，还需要明确文档中的信息必须遵守哪些结构，即需要一种用来描述儿 文档中信息结构的模式 5 第二章n 砒i v ex ，数据库分析 d 1 d 【研( d o c i l m e n t t y p e d e f i n m ，文档类型定义) 是目前使用最广泛的一 种沮j 模式，它列出了可用在文档中的元素、属性，实体和符号表示法，以及 这些内容之间可能的相互关系，指定了文档结构的一系列规则。 d t d 是皿从s g m l 继承而来的，使用d t d 的好处是可以利用大量的在 s g m l 世界中现有的d 1 d 工具。然而，d t d 有如下缺陷： ( 1 ) d t d 的定义不符合) m 亿语法； ( 2 ) d t d 几乎完全没有数据类型的定义； ( 3 ) d t d 的约束定义能力不足，无法对儿实例文档作出更细致的语义限 制； “) d t d 的扩展性比较差； ( 5 ) d t d 不够结构化，重用的代价相对较高。 由于d t d 并不能完全满足) 0 帆自动化处理的要求，所以w 3 c 于2 0 0 1 年 5 月正式推荐咀。s c h 锄a 阻l l 】为) 0 咀，的标准模式。w 3 c 希望以咀，s c h e m a 来作为咀，模式描述语言的主流，并逐渐代替d 1 巾。 咀。s c h e m a 是一种基于m 。语法的模式，用来定义沮。文档中的元素 和属性的具体类型。它提供丰富的数据类型( 如整型、布尔型、日期类型等) ，而 且一个元素中的数据类型可以进行规定，甚至可以根据需要自定义数据类型。 儿s c h 锄提供了一套完整的机制以约束儿文档中标记的使用，而且作为 咀，的一种应用，它具有很好的可扩展性和可重用性。 2 1 4 a m 和x q l l 叫 随着存储在v 几文档中的信息量的增长，能有效并且高效的存取) m 也的 信息相应的也变得越来越重要。要做到这一点，必须要有一个让你能够准确的 获得所需信息、更新咀，数据源中数据的可表达的查询语言。 ，a 也删即为v f i ，路径语言( 儿p a t hl 锄g u a g e ) ，它是一种用来确定咀， 文档中某部分位置的语言，是一种虹文档的寻址语言。，a 也是由w 3 c 创 建的，它使用一种紧凑的、非) m 也的语法，在) m 几文档的一个抽象、逻辑结 构上进行操作。，a i h 使用类似于i j i 也的路径表示法，在一个咀。文档的层次 结构中进行导航。除了用来寻址外，a m 也被设计为包含一个能够用于匹配( 测 试一个结点是否与一个样式匹配) 的自然子集。 6 第二章n 砒i v e 咀。数据库分析 x q r y l ”j 是一种从咀。格式的数据源中获取数据的查询语言，它起源于 沮，数据查询语言q u m 。x q u e f y l 0 与) a 血2 o 【1 4 】有公共的数据模型、公共的 正式语义、公共的函数和操作符以及公共的全文规范。事实上，a m 2 0 是 x q u e r y l o 的一个严格的句法子集。2 0 0 5 年1 1 月，w 3 c 发布) 口，a ：i l l 2 o 和 x q u e r y l 0 为候选推荐标准。 x ( u e r y 具有强大的查询和检索功能，它通过各种由关键字、符号、操作数 构成的表达式完成查询，其表达式的操作对象可以又是另一个表达式。作为一 种函数语言，它还允许各种表达式进行相互嵌套以实现各种查询。 2 1 4x u p d a t e x 1 2 u e r y 能够从旺数据库中检索信息，但是它不能向数据库中添加文 档、从数据库中删除文档、修改已有的文档或者其他操作。目前对于此数据 的更新操作，无论在语言，还是在操作方法上都没有一个统一的标准，最有可 能成为标准的是x u p d a 惦。 枇t e 【1 5 】是由咀，：d b 工作组定义的一种描述对咀，文档所进行更改 的规范，它使用) a 也定义的表达式语言来定位被更新的元素和属性，且支持 有序和无序数据的更新操作。 第= 节n a 伽e 【l 数据库的定义 “n a 矗v e 订l 数据库”这个术语首先在s o 丘w a a g 为t a m i 所做的 营销宣传中露面。也许由于它的成功，后来这个术语在同类产品的开发商那里 成了通用叫法。r 0 n a l d b o u 力吼在其“。锄d d a t a b 船e s ”一文中，对n a t i v e 沮。 数据库有如下定义1 16 】： 1 它为) m 几文档( 而不是文档中的数据) 定义了一个( 逻辑) 模型，并根据 该模型存取文档。这个模型至少应包括元素、属性、p c d a t a 和文档顺序。这 种模型的例子有a 也数据模型、沮。h l f b s e t 以及d o m 所用的模型和s a x 1 o 的事件。 2 它以儿文档作为其基本( 逻辑) 存储单位，正如关系数据库以表中 的行作为基本( 逻辑) 存储单位。 3 它对底层的物理存储模型没有特殊要求。例如，它可以建在关系型、层 7 第二章n 鲥v ex m l 数据库分析 次型或面向对象的数据库之上，或者使用专用的存储格式，比如索引或压缩文 件。 该定义的第一部分与其他类型数据库的定义相似，都是关于数据库所用的 模型的。不过，n a t i v c 沮。数据库所能存储的信息比模型中定义的要多。例如， 它可以支持基于，a 也数据模型的查询，但所用的存储格式是纯文本。在这种 情况下，c d a t a 段和实体用法也存储在数据库中，但是模型中没有包括。 该定义的第二部分指出，n a l i v e 咀，数据库的基本存储单位是) 0 咀。文档。 虽然似乎也可以用讧l 文档片断作为基本存储单位，但几乎所有的n a l i v c 咀数据库都是以文档方式存储的。基本存储单位就是可以容纳一份数据的最 低级的上下文( c o n t e 煳，相当于关系数据库中的行。它的存在并不妨碍以更小 的数据单位来读取数据，比如文档片断或个别元素，同样也不影响将不同文档 中的片断进行组合。从关系数据库的术语来讲，相当于数据虽然以行的形式存 放，并不意味着无法读取某个字段的值，或从现有的数据行创建新一行数据。 该定义的第三部分讲的是底层的数据存储格式并不重要，正如关系数据库 所使用的物理存储格式与数据库是不是关系型之间毫无关系。有一些n 撕v e m 。数据库就是采用传统的数据库作为底层存储引擎的，当然也有很多n a t i v e 沮。数据库是使用专有存储格式的。 第三节n a 伽e 【l 数据库的特性 一般认为，n 撕v c ) m m 数据库应该具有以下几个特性：文档集合( d o c 啪e n t c o l l e c t i o n ) ，查询，更新，事务、锁和并发控制、二次开发接口等。 ( 1 ) 文档集合 很多n a t i v e ) 。沮，数据库产品都支持“文档集合”的概念，就像文件系统中 的一个目录或关系数据库中的张表，一个“文档集合”把一类文档聚集在一 起，方便用户操作。集合级别上的查询、修改操作都会反映到集合内的每个文 档。 一般说来，一个“文档集合”关联一种模式。将文档加入到有模式的“文 档集合”时，会对要加入的文档进行模式检查。只有符合。文档集合”模式的 文档才可以加入。 与关系数据库中的表必须具有模式不同，n 鲥v e 咀，数据库还提供。无模 8 第二章n 鲥v e 沮。数据库分析 式”的文档集合，即将一个文档放入该集合中时，不必检查该文档的模式。“无 模式”的文档集合大大方便了用户存储格式很难统一、半结构化的儿文档， 但同时也降低了皿，文档的完整性并加大了管理这些文档的难度。 ( 2 ) 查询 a m 和x q u e r ) r 是w 3 c 推荐的针对沮，文档的查询语言。目前大部分 n a t i v e 沮。数据库产品都支持x p a m ，另外还有一些n 砸v e 讧l 数据库提供专 有的查询语言。 ) 口，a m 是基于) m 几文档树形模型，给出从某个结点起的查询路径，搜索文 档。目前，a m 作为数据库查询语言还有不少缺陷：不能分组、排序、连接等。 而x c 岫碍更像一神编程语言，支持循环等逻辑，支持分组、排序、连接等。 相对于传统数据库的标准s q l 语句，x q u e r y 在对沮。数据的查询方面，是一 种功能更强大、更易于编程的方法。 为了提高查询的性能，n a t i v e ) 洲l 数据库支持在集合中存储的) m 也数据 上使用编码方案和索引技术。这些编码方案和索引技术可以显著地提高查询执 行的速度。 ( 3 ) 更新 大多数n a l i v e ) m 几数据库对v 几文档的更新是通过调用其提供的a p i 完 成的，或者通过简单的替换整个文档来实现。一些n a l i v e m ，数据库提供专用 的更新语言以允许执行更新，同时还有不少开放源码的n a t i v e v i l 数据库支持 ，p d a ：c e 。 ( 4 ) 事务、锁和并发控制 几乎所有的n a 虹v e ) m 几数据库都支持事务处理。但是，锁的粒度通常比较 大，对整个文档的而不是对文档片断的，所以多用户并发性的支持相对较低。 具体的并发程度取决于应用程序以及文档的构成。 ( 5 ) 二次开发接口 几乎所有的n m i v e 讧l 数据库都提供编程接口：提供数据库连接、浏览元 数据、执行查询和返回结果的方法。返回结果通常是皿。字符串、d o m 树、 返回文档的s a x 解析器。如果查询返回结果是多个文档或文档片断的话，通常 都会提供枚举这些结果的方法。虽然大多数n a t i v e ) 洲l 数据库都提供自己的 a p i ，但是沮。：d b o 曙已经开发出种与供应商无关的) 。以l 数据库a p i ，许 多n a l i v e m 。数据库已经支持它。对于以c l i e 甜s e r v e r 模式运行的数据库产品， 9 第二章n a t i v e ) a l 数据库分析 还可以将结果通过网络协议( 如h 兀p ) 回传给客户端。 ( 6 ) 往返存取( r 舢n d 一p m n g ) n a t i v c 沮，数据库的一个重要特性是它为) m 几文档提供了“往返存取”： 可以将) m 几文档存放在n a t i v e 儿数据库中，而且再取回“同样的”文档。 对于以“文档为中心”的应用程序来说非常重要，因为易被忽略的c d u a 部分、 实体应用、注释和处理指令是这些文档不可缺少的组成部分，特别是对于法律 和医学领域中格式不允许随意窜改的数据文档。 所有的n 砒i 、吧咀，数据库都能够在元素( d 锄e n t ) 、属性( a 晒b u t e ) 、c d a l - a 和文档顺序的级别上为文档提供“往返存取”，能达到的具体程度取决于数据 库产品。 第四节n a 晰e 咀。数据库的系统结构 不同的n 砸v e ) 0 以l 数据库的系统结构是不同的，但至少应该包含存储管理、 索引管理、查询处理以及数据导入等模块；而一个完备的n a t i v e 咀。数据库还 应该包含事务管理、并发控制、恢复技术等，并且应该提供良好的更新机制， 还应该有相应的应用程序编程接口和友好的用户使用界面。一个典型的n a t i v e ) m 几数据库的系统结构如图2 1 所示。 1 0 第二章n 鲥v cx h 也数据库分析 图2 1n 鲥v e 沮。数据库的系统结构 存储管理模块主要负责完成叽数据的物理存储，管理数据库物理存储空 间的分配与回收。为了提高读写效率，通常在存储管理模块之上建立缓冲区管 理模块，通过使用内存缓冲区来减少访问磁盘的次数。 元数据管理模块用于管理数据库的元数据，包括文档集合的模式信息、数 据库的配置信息等。 数据管理模块用于管理) m 几文档的数据信息，包括沮，文档的结构和内 容等。为了能够快速得到) m 几文档的结构信息，通常使用编码方案为) m 几文 档中的结点编码以记录其在文档中的位鼍。 索引管理模块用于创建和维护数据库中各种类型的索引，通常包括：文档 集合索引、元素索引、属性索引、值索引等。如果数据库没有使用编码方案， 索引管理模块还要提供路径索引。 第二章n a t i v ex m l 数据库分析 查询处理模块是n a l i v e v 匝数据库的主要功能模块，它解析仉查询表 达式，对查询语句进行优化处理，并利用编码方案和索引来提高查询性能，返 回查询结果。 数据导入模块负责将沮，文档解析后导入到数据库中，同时更新相应的元 数据、结点编码和索引等。 事务管理模块负责保持事务的四个特性，即原子性、一致性、隔离性和持 久性。它提供提交和回滚的操作，以及锁机制、并发控制和恢复技术等。 数据库管理模块提供数据库的用户管理和访问权限控制等功能。 第五节n a t i 、，e m 。数据库的研究现状 最近几年以来，在学术界和工业界的共同推动下，产生了大量n a l i v e ) 。咀。 数据库的原型系统和商用产品，大致上可分为三大类型： ( 1 ) 商业类：如i p e d o 【1 7 】，t a m i 舯【1 8 】，n a t i 】【嘲，x y l e m e 【2 0 】等。 ( 2 ) 研究类：如s 伽l f o r d 大学开发的l o r e 【2 1 】等。 ( 3 ) 开放源码类：如b c r k e i e yd b ) m 几阎，d b ) a 田】，) ( i n d i c c 洲，e ) ( i s t 【2 5 1 等。 在文献 2 6 】中列出了目前国际上比较有名的各个n a t i v e v 儿数据库系统及 其开发组织。 综合学术界和工业界的研究现状可以看出，有效地存储和查询沮。数据是 n 撕v e 沮，数据库的主要功能，也是当前n 撕v e ) a 帆数据库研究的热点。但 由于n a t i v e m 。数据库的研究发展时间较短，所以在数据更新和事务处理等方 面还存在很多需要解决的问题，n a l i v e v 几数据库距离成熟还有很长的路要走。 第三章编码方案研究 第三章编码方案研究 第一节) 酬【l 编码方案分析 3 1 1 v 几编码方案的引入 如何在n a l i v e 咀。数据库中有效地存储和查询) m m 数据是当前研究的一 个热点。) m 乱查询通常应包括： ( 1 ) 在元素内容上的选择，即通过限定在元素内容或属性值上的取值而进行的选 择查询，称为值查询。 ( 2 ) 通过路径表达式，对文档中标记的元素之间的结构关系进行查询，称为结构 查询。 为了有效地实现订l 的结构查询，近年来研究者们提出了很多种v 几编 码方案。) q 沮。编码方案是对) & 也文档树中的结点( 或边) 进行编码，即给r 也 文档树中的每一个结点( 或边) 赋予一个唯一的编码，以便能够通过编码直接 判断结点之间的结构关系，而不是对原) 仉文档树进行遍历，也就是说，通过 编码将m 。结构查询的计算转化为结构连接的计算。编码方案作为) m m 文档 的结构信息的管理方案，直接影响着存储方案和索引方案的设计。 。编码方案通常至少要满足以下两点： ( 1 ) 快速确定儿文档树中任意两个结点对之间的结构关系。 ( 2 ) 有效查找某个特定结构关系在) m 几文档中发生的所有情况。 将一种好的编码方案嵌入到沮。文档树中之后，通过编码提供的信息来进 行结构查询，能够有效地提高查询的效率。 3 1 2 咀。编码方案的分类 沮。编码方案按照其设计思想和编码特点可以分为三大类：基于路径的编 码方案、基于次序的编码方案和混合的编码方案。 ， ( 1 ) 基于路径的编码方案 1 3 第三章编码方案研究 基于路径( pa _ m b a s l ；d ) 的编码方案利用) m 几文档的嵌套特点，根据儿 文档的嵌套结构为从文档根节点开始所能到达的每个路径和元素结点赋予一个 编码。对于结点u 与它的后裔结点v ，满足u 的编码是v 的编码的前缀。文献【2 7 ，2 8 】 中对基于路径的编码方案进行了深入的研究。 基于路径的编码方案能够有效的支持包含关系( 祖先后裔关系、双亲孩子 关系) 的计算，而且编码的动态性使得它能够很好地支持) m 几文档的更新操作， 在插入新结点后通常不需对任何原结点进行重新编码。但是，很多基于路径的 编码方案没有( 直接) 记录结点的文档顺序信息，对文档位置关系的计算很复 杂或无法实现。而且在) 。吡文档树深度较大时，结点的编码长度太大。 ( 2 ) 基于次序的编码方案 基于次序( o r d 昏b 船e d ) 的编码方案利用v f i 。文档的有序特点，根据每一 个元素结点的文档顺序位置为其赋予一个编码。基于次序的编码方案又可分为 两类：基于区间的编码方案和完全树编码方案。 基于区间的编码方案 在基于区间的编码方案中，编码通常是一个二元组陋，口删或其变型 【d 以盯，妇】( 后者可以理解为s 州= n 陆，；p 耐= d 眺r 怕妇) ，并且对于结点甜 与它的后裔结点v ，满足f 柏 础删俐 p 耐m e 删n 驴。另外，为了能够有效 地支持结点之间的双亲，孩子关系的计算，大多树基于区间的编码方案还为每个 结点赋予一个表示该结点在文档树中的层数的值z p 僧l 文献【2 9 3 3 】中提出的都 是基于区间的编码方案。 完全树编码方案 完全树编码方案的核心设计思想是：先构造一棵完全k 叉树，然后将) m 也 文档树转换为k 叉树后嵌入到这颗完全k 叉树中，以结点在完全k 叉树中的前 序( 后续) 遍历序号作为其编码。文献【3 4 3 6 】中提出的都是完全树编码方案及 其变型。 基于次序的编码方案不仅能够有效地支持包含关系的计算，而且能够有效 地支持文档位置关系的计算；而且编码的长度通常较小；在结构查询时，比较 计算花费的时间也很少。但是，基于次序的编码方案一直无法实现编码的动态 性，在插入的新结点数量超过预留空间后，重新编码的代价很大。 ( 3 ) 混合型的编码方案 混合型( b 蛳d ) 的编码方案结合了基于路径的编码方案和基于区间的编码 1 4 第三章编码方案研究 方案的优点，它既具有基于路径的编码方案的前缀特点，又像基于区间的编码 方案一样记录了结点的文档位置信息，例如d e w e y 编码方案1 3 1 ”。o m ) p 御编 码方案娜l 和d l n 编码方案p 9 l 在d 鲫e y 编码方案的基础上改进了编码的动态性， 使得编码方案在更新操作后具有很小的重新编码代价、甚至不需重新编码。但 是，已提出的混合型的编码方案在编码的最大长度或平均长度等方面还有待优 化( 尤其是在遇到一些特殊情况时有些编码方案会使得编码长度迅速增加) 。 综上所述，因为n a t i v e 沮，数据库是刚刚兴起的研究热点，皿，查询是 当前最主要的研究课题，所以已经提出的大多数几编码方案主要考虑的是其 支持沮。结构查询的性能，而更新操作导致的其重新编码的代价则普遍很大， 只有少数几种) m 儿编码方案在这方面解决的较好，但其在编码的最大长度或平 均长度等方面还有待优化。因此，本文将提出一种新的v 儿动态编码方案，它 不但能有效的支持) 0 v 匝结构查询，而且在更新操作时能够具有很小的重新编码 代价、甚至不重新编码，并且具有较小的编码长度。 第二节一种新的编码方案洄n 3 2 1 ) n 的设计思想 设计编码方案要考虑的主要包括以下几点： ( 1 ) 被编码数据的结构； ( 2 ) 支持各种结构关系的查询； ( 3 ) 编码生成算法的时间复杂度； ( 4 ) 编码的最大长度和平均长度； ( 5 ) 编码后的查询性能； ( 6 ) 更新操作导致的重新编码代价。 本文接下来将根据这些特点设计一种新的v 几编码方案。 3 2 1 1 被编码数据的结构 几文档是树型结构，文档中的元素( 或属性) 对应于树中的结点。m 。 结点之间的结构关系包括：祖先后裔( 锄c c s t o r d e d a m ) 关系、双亲，孩子 ( p a m 肌h n d ) 关系、之前之后( p 船潮i n g f o u o w i n g ) 关系、左兄弟，右兄弟 1 5 第三章编码方案研究 ( p r c c e d i n 哥s i b l i l l g ，f o l l o ，i 1 1 争s i b l i i l g ) 关系等。其中，祖先，后裔、双亲胲子等关 系统称为包含关系，之前之后、左兄弟右兄弟等关系统称为文档位置关系。以 图3 1 中的舭结点树为例，结点4 是结点p 的祖先，结点p 是结点口的后裔； 结点口是结点6 的双亲，结点6 是结点口的孩子；结点6 在结点d 之前，结点d 在结点6 之后；结点6 是结点c 的左兄弟，结点c 是结点6 的右兄弟。 图3 1 一棵x m l 结点树 编码可以看作是一个比特串，为方便描述，在本文中将比特串用英文双引 号”标记，而将固定长度的一段比特串用与其相等的、不带英文双引号标记的 十进制数表示。例如，若比特串长度设为4 ，则编码l 表示的实际编码比特串 为”0 0 0 l ”。 3 2 1 2 支持包含关系查询 为了使编码能够确定结点之间的包含关系，使用前缀编码是一种有效的方 法。前缀编码的规则是： 一 直接将一个结点的双亲结点的编码作为该结点编码的前缀。 为了记录层次结构信息，在结点编码的双亲编码前缀之后、新增编码之前 添加一个用于标记分层的符号。在本文以后的内容中将一个结点的编码除去其 双亲编码前缀和分层符号之后剩余的新增编码部分称为该结点的“本层编码”。 以图3 1 中的) m 几结点树为例，设结点口的编码为c 例，则其子结点6 的编码 c 例= f 砂栉，“”是分层符号，“疗”是6 的本层编码。 前缀编码是一种粗粒度的编码方案，即满足其编码规则对沮。文档树按照 结点的一定次序进行编码的结果不唯一。按照前缀编码的规则，一个结点1 ，是另 一个结点“的后裔当且仅当“的编码c 俐是v 的编码c 例的前缀；一个结点1 ，是 1 6 第三章编码方案研究 另一个结点甜的孩子当且仅当”的编码c 驴是v 的编码c 似的前缀、且c 俐中的 分层符号数止w e f c d 俐比c 仰中的分层符号数如卯切蜊少1 个。 3 2 1 3 支持文档位置关系查询 为了使编码能够确定结点之间的文档位置关系，需要使编码具有字典有序 的性质：一个) 函也文档树中结点的编码按照此文档树的先序遍历顺序从小到大 有序。编码比较的规则是：从前向后依次比较两个编码比特串同一位置的一对 比特，若它们的值相同，则继续比较下一对比特。若它们的值不同，则值较大 ( 即值为1 ) 的比特所在的编码较大；若所有比特均相同，则两个编码相等；若 一个编码全部k 个比特与另一个编码的前k 个比特相同，则比特串较长的编码 较大。例如： 编码比特串“1 0 l ”与”l o l “，它们相等； 编码比特串”1 0 l o ”与”1 0 lr f i ， ”1 0 1 0 ”小于”1 0 1 1 ”； 编码比特串”l o ”与”1 0 1 ”， ”1 0 ”小于”1 0 1 ”。 根据前缀编码已有的前缀性可知，双亲结点的编码大于其孩子结点的编码， 因此，可以将字典有序的条件简化为：对于) m 见文档树中的任意一个结点，其 编码大于它的左兄弟子树中所有结点的编码、且小于它的右兄弟子树中所有结 点的编码。这样，使前缀编码具有字典有序性的一种最简单的方法是为前缀编 码增加以下规则： 使用一个结点在其双亲结点的所有孩子结点中从左到右的序号作为该结点 的本层编码，所有结点的同层编码比特串长度相等。， 增加了字典有序性的前缀编码和d c w e y 编码【3 7 】的规则相似，它是一种最小 粒度的编码方案，即以此编码方案对沮。文档树按照结点的一定次序进行编码 的结果具有唯一性