（计算机软件与理论专业论文）基于temporal+xml文档的索引研究.pdf

山东大学硕士学位论文 摘要 近年来，随着计算机技术的迅猛发展和网络技术的不断进步，人们通过网 络来传输各种数据也越来越频繁。但是在不同环境下，人们使用不同的数据表达 方式，这就给数据的传输造成了极大的不便。而) m 几作为一种数据的表现形式， 正在成为事实上的数据标准。x m l 的应用普及，也使得对x m l 的各种研究已 经成为当前数据库研究领域的一个热点。 对于儿的研究大多集中在两个方面：存储和查询。目前针对这两个方面 的研究工作已经有很多，但是针对特殊类别的沮，文档的研究却不是很多。本 文中主要提到的脚r a l 沮，文档就是其中的一个例子。当前针对这种特殊的 帆文档的研究大多还是停留在对于普通) m 几文档研究的基础之上，即对于 t e n l p o r a i 蛆。文档的各种操作仍然使用普通皿，文档的操作模式进行操作， 这就大大的影响了对于t e m p o r a lx m l 文档各种操作的执行效率。 本文提出了一种关于沮。文档的存储模型，这种模型是一种典型的m 囝 ( n a l i v e 诅。d b m s ) 的存储模式，它采用了元素和字符数据进行分离的思想， 构造的元素架构是以数据块为单位结点的一种树结构，字符数据则以聚簇方式存 放。在这种存储结构上，可以更好的对x m l 文档数据进行各种操作。 针对t e 删) o r a l 皿。文档这种特殊的沮。文档，本文提出了一种新的 t e m p o r a l ) 口l 的数据模型。x p a ：吐i 数据模型是传统) m 几文档的一种数据模型， 在这种数据模型的基础上，我们加入了时序的概念，从而得到了可以适用于 t e m p o r a l 诅。文档的数据模型。 本文在上面提出的数据模型的基础上，针对t e n 中o r a lx m l 文档这一特殊 的咀。文档，提出了一种特殊的索引结构。这种索引结构将文档中的元素结点 抽出，并组成一个有向无环图( d a g ) 的结构。其他的元素数据放到各个索引 表中，并存储与二级存储器内。在整个索引结构中，本文还考虑到t e n l p o r a l ) m 几 文档与普通仉文档的不同之处，即在t e m p o r a l 沮。文档中的时间片属性。 我们在索引表中放入时间片的属性，使我们在操作这种特殊的x m l 文档时，摆 脱利用传统的咀。文档操作模式来操作t e m p o r a lx m l 文档的方法，提出了专 山东大学硕士学位论文 门针对t e r n p o r a ix m l 文档的索引结构，大大的提高了效率。在提出这种索引结 构的基础上，本文还进步给出了利用该索引结构对数据进行查询、插入和删除 等操作的算法。 关键宇：t e m p o r a l 儿文档；存储模型：索引结构 山东大学硕士学位论文 a b s t r a c t r e c e 川k 诵也也ed e v e l o p i n e n t o fc o m p m e rt e e i m o l o g y 锄d 球卿r k a p p l i c a l i o n ，d a l a 仃趾s r n i s s i o nt l l r o u g hn e t w o r kb e c o m 舒m o r ea n dm o r e 丹e q 唧t b u td i f f e r e i l tp e o p l eu s ed i f f e r e n tm e t l l o 出t od e n o t et l l ed a = t a ，砌c hm a l 【ei td i 伍c i l l t 幻t r 觚s r n i tt i l ed a t 乱a sal 【i n do fd a t ap r 嚣锄枷o nm e d l o d ，：j ( m li g 钺：t i l a l l y b e c o t l l i n gn l es t a i i d a r dt h e 诵d eu s a g eo fx m l m a l 【e si t sr e s e a r c hi i l l p o n a n ti nm e f i e l do fd a _ t a b 私e 皿e f e s e a r c h 龉o f ) 0 儿f o c u s o n 咖f i e l 出：蜘r a g e 锄d q u 吖n o w m e r ea r ea l o to fr e s e a r c h e sa b o u tt | l e t 、 ，of i d d s ，b u t1 l i er e s e 盯c h e s s p e c i a lx m l d o c 啪e n t sa r ev e f yf e wt h et e m p o r a lx 一d o c 砌e n ti ss u c h 锄e x 锄p l e w t l l er e s e a r c ho nm i sd o c 啪锄ti ss t i l lt i l es 锄ea st i l e 仃a d i d o n a lx 1 儿d o c 啪e 1 1 t ， 枷c hm e a n st l l ei l s a g eo f 仃a d i 矗o n a lm e t h o d st 0s o l v et l l ep r o b l e n l so nt i l et e m p o r a l 皿d o c 啪即t s ；h e n c el i r n i t sm ep e r f b n n a n c ee m c i e n c yo ft l l et e m p o r a lx m l d o c u m e n t h 吐l i s p a p e r w e p u t f b r w 甜das t o r a g e m o d do f t h e x m ld o c u m e 咄w h i c h i s a 锣p i c a ln x d ( n a t i v e ) 几d b m s ) s t o r a g en l o d e l t h eb 嬲i ci d e ai st os e p a r a t em e e l e m 朗协a n dm ec h a r a c t e rd a a t h ee l e m e n ts c h e m ai sa 仃e es 仃u c t u r eb a s e do nt h e d a t ab l o c k ，a 1 1 dt l l ec h a r 舵t e rd a t aa r es t o r e db yc l u s t e ru s i n gt h i ss t l l l c t u r e ，w ec m m a n i p u i a t et l l ed o c 啪e n tr n o r ee 衔c i e n t l y h lv i e wo f t h es p e c i a lf e a t u r eo f 血et e m p o r a l 咀。d o c 啪即t ，w ep r o p o s ea n e wd a t am o d e lo ni tx p a t hd a _ t al l 】b d e li sac o 姗0 nc l a t am o d e lo nt r a d i t i o n a l ) 几d o c l 】m 栅t b a s e do nt h i sd a t an l o d e l ，w ea d dt h ei d e ao ft i i l l i n g ；h e n c ea d a p ti t t o t l l et e r n p o r a l ) m 皿d o c 啪e n t b 舾e do n “ss t o r a g en l o d e l ，w ep u tf o 脚，a 】r das p e c i a li n d e xs 仃1 l c t u r ea i m e da l 也et b m d o r a lx l 讧ld o c u n l e n tw 色e x 仃a c tt h ee l e m tn o d e sf 如mt 量l ed o c u m e n ta i l d 百v er i s et oad i r e c t e da c y c l i c 黟a p h ( d a g ) s n l l c 岫a l l dt i l ec h a r a c t e rd a t aa r ep u t i l lt l l ei n d e xt a b i ea n ds t o r e di nt l es e c o n d a i ys t o r a g e h it i l ew h o l ei n d e xs 仉l c t i l r e ， w ea l s ot a k en o d c eo f 血ed i f f e r e n c eb e t 、v 咖m et e r n p o r a lx m ld o c 啪锄ta i l dm e i i i 山东大学硕士学位论文 仃a d i 矗o n a lx m ld o c 岫e i l i e m e 缸m es l i c ep r o p e r i y w 吾p u tt h e6 m es l i c 嚣私a p r o p e r l yi n t o 山em d e xt a b l e ，觚d 讪e nw em 柚i p u j a t e “s 印e d a 】x m ld o c 啪即乞 w ec a ng e tr i do fm e 仃a d i d o n a lm e 幽o d s t h j ss p e c i a li 1 1 d e xs 们l c t i l r ea i m e d 砒 t e m p o r a l ：n 仉d o c 岫e 1 1 tc 锄i m p r o v el 量l ee 衔d c yg r e a yb a do f i “ss 饥i c t i l r e ， w ea l s op r o p o s ea l g o r i m 蟠o nd a t ai n s e n i o i l ，d e l e t i o n 舭dq u e 哆 k 巧w o r d s ：t e m p o r 蚰讧ld o c u m e n t ；s t o r a g em o d e i ；i i i d e xs t m c t i i 啦 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：塞血日期：堡渔塑塑 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：塑导师签名：1 翌亟鱼z 名期：2 竺2 兰塑 山东大学硕士学位论文 1 1x 札基础 1 1 1 什么是x 址 第一章绪论 x m l 代表可扩展标记语言。它是一种把数据表示为一个文本字符串的语 言，这个文本字符串还包括用于描述数据的散布的“标记”。使用标记允许把文 本和与它的内容或形式相关的信息散布在一起。 标记( t a g ) 用角括号“ ”包含字符( 例如，“l l i i s ”) 来区别字 符数据( 非标记文本) 。因此一个字符串、一个文档由标记和字符数据组成，这 些结合起来就形成了元素。一个元素( ) 以一个开始标记开始，以一个结束标记 结束。结束标记用角括号和一个用来区分开始标记的正斜杠“”来表示，像 “啪i s ”。 是标记，在标记里面的内容是文本， 而从一个开始标记到它的结束标记的文本区域是一个元素，像 “ i n t e r s p e r s e d ”就是一个元素。 尤其是，标记提供一种机制来给文档添加元内容和结构信息。标记为注释 元素中的字符数据提供了一种机制。元素是咀。的基本的组成部分。元素可以 包含嵌套在其中的其他元素，叫做子元素( 鲫b e l e m e m ) 。一个文档由一个单一的 最外面的( 或最高级的) 元素组成，它包含其他元素和或字符数据，并且每个 子元素可以包含其他带字符的“子元素的子元素”( s u b s u b e l e m t ) ，等等。下面 给出一个汽车经销商的x m l 文档的示例。 c o n t a c 伊 1 3a u t o m o b i l ew 匆 8 0 0 - 5 5 5 1 2 3 4 山东大学硕士学位论文 1 2 4 0 0 b l a c k b o l o l am ，f m ，c d4s p e a j c e r s 3 一d o o rh a l c h b a c k t a n t c o l o r m ，f m c d4s p e a l 【e r s 1 1 2 l 的起源 s g m l s g m l ( s t 肌d a r dg e r a l i z e dm a r k l l pl 锄g i l a g e ) ，即标准通用标记语言，是 1 9 8 6 年出版发布的一个信息管理方面的国际标准( i s o8 8 7 9 1 。该标准定义独立于 平台和应用的文本文档的格式、索引和链接信息，为用户提供一种类似于语法的 机制，用来定义文档的结构和指示文档结构的标签。其中咄印的含义是指插 入到文档中的标记。标记分为两种：一种称为p r o c e e d e dm a r k u p ，用来描述文档 显示的样式：另一种称为d e s c r i p h v em a r k u p ，用来描述文档中的文字的用途。制 定s g m l 的基本思想是把文档的内容与样式分开。 s g m l 规定了在文档中嵌入描述标记的标准格式，指定了描述文档结构的 标准方法，目前在w e b 上使用的m m l 格式便是使用固定标签集的一种s g m l 文档。用于s g m l 可以支持无数的文档结构类型，并且可以创建与特定的软硬 件无关的文档，因此很容易与使用不同计算机系统的用户交换文档。 使用s g m l 对多媒体的创作将带来许多好处。首先，由于其规范性，它可 以使创作人员更集中于内容的创作，可提高作品的重复使用性能、可移植性能以 2 山东大学硕士学位论文 及共享性能。其次，由于s g m l 的独立性，使得它在许多场合都有用武之地。 同) 皿相比，定义的功能很强大，缺点是它不适用于w 曲数据描述，而且s g m l 软件价格非常价格昂贵。 h n ， 1 9 8 9 年，在cern 工作的蒂姆伯纳斯李和罗伯特咔利奥分别独立地发 明了超文本标记语言( html ) ，这是一种文档生成语言，它包括一套定义文 档结构和类型的标记。这套编码描述了文档内文本元素之间的关系。这个术语中 的“超文本”这个词起源于6o 年代，文字机器一书的作者特德尼尔森首次使 用了这个词。尼尔森设想出一种页面链接系统来连接相关的页面，不论这些页面 分别存储在什么地方。“标记语言”这个词则来源于传统的印刷业。 h t m l 的基础是s g m l 。h t m l 是一种特殊的s g m l 文档类型一文 档类型定义( d t d ) ，它比s g m l 更容易学习和使用。例如，m m l d t d 用于w w w 上的所有文档。在h t m l 的早期应用时期( 即9o 年代初) ，当时 流行的h tml 版本非常适合于创建带有标题、标题栏、布告、行和项目列表的 文本文档。但用户要求更好的w w w 页面元素的标题栏，以及更精确的图形定 位、表格和框架，w w w 的设计者每周都在要求新的特征。此外，软件开发商 也不断要求增加h t m l 的功能。 但是，目前的h r m l 还不稳定，不同的浏览器会产生不同的显示效果。此 外，由于h r m 巴对超级链接支持不足，并缺乏空间立体描述，处理图形、图像、 音频、视频等多媒体能力较弱，图文混排功能简单，不能表示多种媒体的同步关 系等缺点，也影响h r m l 的大规模应用以及用于复杂的多媒体数据处理。 x 几 和h t m l 一样，扩展标记语言( x m l ) 也是从sg m l 发展而来的。 x m l 是种相对较新的语言，它定义了w w w 页面显示哪些数据，而h t m l 确定页面如何显示。xml 使设计者很容易地以标准化的、连续的方式来描述 并传输来自任意应用程序的结构化数据。 很多w w w 设计者都相信x m l 将很快成为w w w 上优先使用的编程语 言。尽管h t m l 可以提供大量描述页面格式的标记，但它不能描述页面的具体 内容，即不能解释页面上数据的含义。与之相反，xml 可以掐述页面的内容。 山东大学硕士学位论文 此外，xml 还有数据跟踪能力，这将改变数据共享的方式以及检索数据库和 文件的方式。 1 1 3x 札的特点 使用有意义的标记 咀。标记具有语义，描述性强。 数据的语义与显示方式分开 ) m 几只描述数据的内容，并不决定数据如何显示，数据的显示由级联样式 单( c s s ) 或可扩展样式单语言( x s l ) 决定。咀。和它有关的标准鼓励内容 ( 作为抽象数据类型) 、表示( 作为格式对象，即一组特定的元素) 和处理( 作 为样式单) 相分离，每部分都可以独立的发展，不需要在一个统一的框架中折衷。 可自定义的标记 x m l 可由用户按需要自由设计、定制标记及标记之间的关系，如数学标记 语言m 舡卸诅、财经标记语言f p 舳l 、电子商务标记语言髓儿等等。所以 说沮，是一种“定义语言的语言”，即一种元语言，具有很好的可扩展性。 严格的语法控制 儿对语法有严格的要求，所有咀。的文件都必须经过严格的“验证” 过程才算完成，文件格式容易转换。 1 1 4x 札的优势 皿最大的优势在于对各种数据的管理。任何系统都可以通过几的解析 器来读取帆数据，因此它的数据可以通行各处，而不用担心系统不支持的问 题1 2 】。 数据的检索 i n t e r l l e t 上主要的数据检索方式：分类检索和全文检索。检索效率低，或找 不到。) 。咀。以语义标记作为搜索索引，在文件中截取关键部分。所有标记内的 数据都可视为个元素，而每一个元素都可以作为数据的索引。 数据的显示 ) ( 1 诅。将数据保存的格式与数据显示的方式分开。使得x m l 文件可以轻易 4 山东大学硕士学位论文 地更换数据显示的方式，仅需改变x s l 的设置，用户就可以将同一数据制作成 m 蛐。、p d f 、w 池( 晰r e l 嚣sm a r k u pl 卸g i l a g e ) 、壬d 地( h 越d _ h e l 晰c e m a r k 印l 锄g u a g e ) 等不同格式，供不同的硬件显示。 数据的交换 ) m 也语法简单，可以被所有的机器解读，又可以在各种平台上使用，使得 x m l 有潜力成为一个通行四海皆准的标记语言。 1 2x m l 数据库 1 2 1 什么是x 札数据库 儿数据库是一个) 0 儿文档的集合，这些文档是持久的并且是可以操作 的。它是一个能够在应用中管理咀激据和文档的数据库系统，一个沮。数据 库是x m l 文档及其部件的集合，并通过一个具有能力管理和控制这个文档集合 本身及其所表示的信息的系统来维护。儿数据库不仅是结构化数据和半结构 化数据的存储库，像管理其他数据一样，持久的沮。数据管理包括数据的独立 性、集成性、访问权限、视图、完备性、冗余性、一致性以及数据恢复等等。 x m l 数据本身的树形结构不同于关系模型中的二维表结构，这种差别反映 在数据库产品处理) m 几数据的技术上，总体而言，主要有以下三种： 平面文件 平面文件是最简单的存储方案，就是在一个文件上存储整个x m l 文档，以 多种不同的文本编辑器和几个x m l 工具作为数据操纵工具来实现沮。数据的 操纵。它可以首先通过文件系统的目录结构，然后通过咀。文档的元素结构来 提供对数据的层次访问。 平面文件数据库的优点是实现方便，容易构建和维护，并且容易被其他工 具访问。从任何程序设计语言中访问数据是很容易的，并且从所有沮。解析器 中访问数据也是很容易的。 但是咀。平面文件数据库也存在一定的缺陷，它的数据没有被很好的保 护，不方便，而且平面文件数据库通常不提供并发控制、数据锁或恢复工具。 x e d ( x ，e n a 瑚e dd b m s ) 山东大学硕士学位论文 x e d 是在原有数据库基础上扩展了) 函几支持模块，完成x m l 数据和数 据库之间的格式转换和传输。从存储粒度上，可以把整个咀。文档作为r d b m s 表中一行，或把咀。文档进行解析后，存储到相应的表格中。为了支持w 3 c 的一些咀。操作标准，如，a t h ，d 提供一些新的原语( 如o r a c l e 9 i r 2 增加 了一些数据包来操作儿数据等) ，并优化了x m l 处理模块。 x e d 中的) 见接口提供对健壮的数据库技术的访问，同时可以进行札 传输，在r d b m s 中，复杂的查询可以由s q l 来实现，查询的结果进而被格式 化为咀。，为一些基础数据提供视图。另外，它还具有也其他关系型数据库之 间的互操作能力、精确的事务管理和恢复机制以及大量工具对它的支持。在数据 库必须被与其他关系型数据库进行互操作应用程序的访问时，使用到d 的 咀，接口比较合适。 但是，在这种种方便的背后也存在着一些缺点：将树状结构的帆数据转 换成关系数据库的二维关系表形式时面l 临语义信息丢失的问题；x m l 查询( 如 ，a l h 和x q u e r y ) 等不能直接在关系数据库上执行，需要转换成s q l 查询：而 且其关系表形式的查询结果还必须得还原成为树状形式的) 函几数据：查询执行 和数据存储的代价会受x m l 数据的映射方案的影响可能会变的较大。 x m l 文档模式和d 模式的映射为了把) 函儿文档存到d 中，我们必 须将v 几文档的模式( d 1 巾或v 儿s c h e n l a ) 映射到数据库模式。同样，将数 据从m 取出来重新组合成皿文档，要完成相反的操作。这种转化发生在 元素( e l e m t ) ，属性( a t t 曲m e ) 和文本( t e ) 【t ) 上。由于x e d 注重的是数据而非格式， 所以在这个过程中，x m l 文档的大部分物理结构( c d a l a 、实体等) 和一部分 逻辑结构( 处理指令、注释等) 都被忽略，而数据被保存。这种转换可能会丢失 信息，一个咀，文档存到j d 里后再取出来，可能会变成另外一种格式。 n x d ( n “v e m 。d b m s ) m j ( d 为) m 几文档( 而不是文档中的数据) 定义了一个逻辑模型，并根据 模型存取文件。这个模型至少应包括元素、属性、p c d 舶a 和文件顺序。它出现 在v 匝数据处理领域内，一般采用层次数据存储模型，保持v 几文档的树形 结构，省掉了。文档和传统数据库的数据转换过程。它对底层的物理存储模 型没有特殊要求。例如，它可以建在关系型、层次型活面向对象的数据库之上， 山东大学硕士学位论文 或者使用专用的存储格式，比如索引或压缩文件。 m 囝是专门为存储) m i i j 文档设计，也兼有一般数据库的特性，例如支持 事务，并发控制，查询语言，安全机制，二次开发接口等。唯一的不同之处在于 其内部存储模型是基于) a 咀。文档树形结构，而非关系模型。 n x d 在存储时保留数据的树型模式：根据一个结点可以直接找到其孩子结 点、左右兄弟结点或父亲结点等。以n 撕v e 方式存储的，几数据，支持，甜1 和x q u e 珂等v 皿查询以读取数据。存取) 几数据，就无需进行数据模式的 转换，也不需要进行查询语言的转换。 1 2 2 两种文档类型 ( 1 ) 以数据为中心( d a t a - c 埘c ) 【4 】 ”以数据为中心”的江文档着重于文档中的数据，而非文档格式，如航 班信息、销售定单、科学计算结果等。这种文档的数据一般由机器产生，来源于 传统数据库中的数据。主要应用在电子商务、e r p 、e 越等领域，集成不同数据 源的数据，交换信息。”以数据为中心”的皿文档具有以下特点： 结构化的数据 数据粒度大小适中 很少或没有混和内容( m i x e dc o n t t ) 文档顺序( d o c u r n e l l t o r d 盯) 不重要 ( 2 ) 以文档为中心( d o c 岫e n t c e n 缸c ) ”以文档为中心”的x m l 文档主要是用来表示人类自然语言描述的数据，如 电子邮件、书和用户手册。这种文档具有更复杂的结构，一般不是机器自动产生 的。目前，w 曲上的大部分数据都可以表示成这种文档。”以文档为中心”的文档 具有以下特点： 半结构化或非结构化的数据 较多的混和内容( m i x e dc o n t e n t ) 文档顺序( d o c u m e i l t o r d e r ) 重要 对于”以数据为中心”的儿文档，x e d 可以方便地将其中的数据抽取， 存储在传统数据库中，但对于”以文档为中心”的儿文档则显得力不从心了。 m 囝由于无需在两种模型之间转换数据，因此在处理”以文档为中心”的) ( 1 帆文 山东大学硕士学位论文 档就很有优势。 1 2 3 x 印与n x d 的比较 l 、x e d 优势 ( 1 ) 用户不需要将传统数据库中原有数据重新移植到新系统中，只是稍加 改变，就可以支持儿应用。 ( 2 ) 传统数据库技术，例如并发控制、事务等，已经很成熟。 ( 3 ) 传统数据库知识和经验依然有效，用户不需要为了应用沮。而再去 学习一套新的数据库技术。 劣势 ( 1 ) ) 几文档存入到数据库时需要将其吁r 碎”，取出时需要”组合”，不仅 耗时，而且文档的格式可能会不同 ( 2 ) ) m 几文档和数据库之间的模式转换复杂，在前期开发阶段需要投入很 大 ( 3 ) 对”以文档为中心”、格式复杂的沮。文档处理性能较差 ( 4 ) 在采纳咀。技术标准方面较落后 2 、n x d 优势 ( 1 ) 咀。文档存取无需模式转换，存取速度快。 ( 2 ) 对格式复杂的x m 臣文档支持比! d 要好。 ( 3 ) 支持大部分的最新的帆技术标准。 劣势 ( 1 ) 在传统数据库技术方面比较薄弱，没有经过时间的考验。 ( 2 ) 知识比较新，相应的支持人员和文档资源都比较少。 ( 3 ) 应用范围仅局限在儿应用领域中。 事实上，两者的优劣并没有统一的答案，而是和具体的应用相关。在开发 格式较简单、数据内容比格式更重要的应用时，d 是不错的选择，特别是在 已有的传统数据库上要提供x m l 的访问接口的情况下。相反，如果皿。文档 格式复杂，数据本身就有层次性关系，或是只有咀。数据的时候，就可以考虑 山东大学硕士学位论文 n x d ，因为它提供更好的性能，对x m l 标准有更完备的支持。另外，由于n ) ( d 在事务、数据恢复等传统数据库技术方面还未得到时间的检验，因此对数据安全 要求较高的一些应用，如银行、金融系统的数据库，建立在传统数据库上的d 相对来说更有优势。 1 3x 札查询技术 1 3 1x p a t h 1 、 a m 数据模型断】 抽是对儿文档各部分内容进行定位的语言，主要用在x s l t 、 o i n t 盯中。它为x s u 和o i n t e r 提供了一个共同整合的定位语法用来定位 咀，。文档中的各个部分除了提供一套定位语法x p a l l l 还包括一些函数，这些 函数提供基本的数字运算布尔运算和字符串处理功能。 a 山使用一种紧凑的非沮，的语法，它基于沮。文档的逻辑结构， 在该结构中进行导航定位。，a n l 基于沮。的树形结构建立数据模型，将沮。 文档看成由结点集构成的树结点，它的类型可以有多种，包括元素结点、属性结 点和文本结点等等。，a i l l 的基本语法由表达式构成，在计算表达式的值之后产 生一个对象，对象类型包括结点集合、布尔型、数字型和字符串型等等。 x p a m 模型将x m l 文档描述为包含根元素属性文本命名空间处理，指令 注释七种结点类型的有序树。对每种结点类型都有一个方法来确定该类型的每个 结点的值。对于某些类型的结点，值是结点内容的一部分。对于其它类型的结点， 结点的值由该结点子孙结点的值决定，对于部分类型的结点还可以为该类型的每 个结点确定一个名字为叙述简化起见这里重点描述四种结点类型。 根结点表示整个x m l 文档，是最高级元素r o o t 的父结点。根结点的后代 中，所有文本结点的字符串值按照文档顺序相连接形成根的值。根结点没有名字， ) m 几文档中每个) 0 v 儿元素均对应一个元素结点，元素结点的名字由其标记， 所标识与根结点类似元素结点的后代中所有文本结点的字符串值按照文档顺序 相连接形成该元素结点的值。元素结点可以有零个或多个子结点，子结点可以是 元素结点或文本结点。每个元素结点拥有与该元素结点相关联的属性结点集，属 9 山东大学硕士学位论文 性结点具有属性名和属性值。属性结点没有子结点，属性结点的名字和值分别为 其属性名和属性值。值得注意的是元素结点是其属性结点的父结点，但是属性结 点并不是元素结点的子结点，与属性结点相同文本结点没有子结点所有的文本结 点都没有名字，但都有一个字符串值。 在x p 抽模型中除根结点以外每个结点只能有一个父结点，没有一个结点 的孩子与另一结点的任何一个孩子会是同一结点。 x p a ：l l l 模型完整的保持了x m l 文档的信息，包括文档的结构和数据。可 以直接在这个模型的基础上对v 儿文档进行操作而无须进行转换包括沮，查 询语言。 2 、x m l 路径表达式 路径表达式是x p a 血核心，它选择与上下文结点相关的一个结点集作为其 计算结果。x p a t i 有两种定位路径：相对路径和绝对路径。在相对路径中，每一 个定位步骤都选择与上下文相关的一个结点集，然后这个结点集中的每一个结点 都作为后续定位步骤的上下文结点选择，如此从左到右进行选择，最后将选择的 所有结点组合在一起得到按照文档顺序排列的不重复的结点集。 一个路径表达式按照砒h 语法可以定义为p a m ：= ( s t 印) ，也就是说一 个路径表达式是由个或多个定位步骤组成的，并且每个s t e p 都可以定义为 s t e p ：= a 妇s ：d e t e s t 口r e d i c a 叫，每一个定位步骤包括三个部分：轴( a ) d s ) 、 结点测试( n o 螂e 哟、零个或多个谓词( p 陀d i c a t e ) 。轴指明定位步骤选择的结点 与上下文结点的关系，结点测试指明定位步骤选择的结点类型和扩展名称，谓词 则使用表达式进一步精简选择的结点集。，a ：l l l 中的定位步骤是按照从左到右的 顺序，进行计算同时每个定位步骤的结点集按照文档顺序进行排序，并删除重复 的结点。整个，劬表达式的查询结果是最后一个定位步骤的结点集。 轴是 a 吐1 中的重要组成部分，a m 支持1 1 种定位轴，可分为两类前 向轴和反向轴。前向轴( f o n 一d a ) 【i s ) 仅包含当前结点和文档顺序排在当前结 点之后的结点，包括c 1 1 i l dd e s c e n d 锄ts e l fd e s c d a n 伽r - s e l ff o l l o w i n 哥s i b l i n g f o l i o 撕n g ：反向轴仅包含当前结点和文档顺序排在当前结点之前的结点，包括 p a r e n t 越c e s t o rp r e c e d i n g s i b l i n gp r e c e d i n ga i l c e s t o r - o r - s e l f 。此外 a 廿l 也支持一 种缩写语法，例如轴的名字可以省略默认为c h i l d ， 轴是 山东大学硕士学位论文 d 髂c 锄d 锄t o r s e l f ：n o d e 0 自q 缩写，默认为d e s c e n d 锄t o r s e l f d轴础的一个 定位步骤所产生的结点集里，其结点的上下文位置从某种意义上说取决于轴的选 取。如果轴是前向轴那么上下文位置按文档顺序来指定，如果轴是反向轴那么上 下文位置按逆文档序来指定。不论是哪种轴结点集的第一个上下文位置均被指定 为l 。对于，础的查询结果，甜1 2 o 中特别指出，a l l l 的查询结果必须保 持文档顺序并且查询过程的各个s t e d 也必须保持文档顺序。 1 3 2x q u e r y x q u e 叮是w 3 c 制定的) m 正查询语言n 即。它是以q l l i l t 语言为基础发展而 来的，极有可能成为儿的标准查询语言。x q u e f y 借鉴和吸收了x q l 、 皿一q l 、l 0 r e l 、等多种查询语言的优点，如x q l 的路径表达式、x m l q l 的 变量绑定机制、o q l 的函数概念等。 一个x q u e r y 查询包括三个部分： l 、名字空间和模式声明可选。 2 、函数定义可选。 3 、查询表达式。 其中前两个部分合在一起称为查询序( q u e r yp r o l o g ) 。查询表达式是x q u e r y 的核心，x q u e r y 提供七种类型的查询表达式：路径表达式、元素构造表达式、 n w r 表达式、包含运算符和函数的表达式、条件表达式、限制表达式、测试 及修改数据类型的表达式。 l 、路径表达式 x q u e r y 的路径表达式基于，a d l 的语法规则并在此基础上作了扩充，有 关路径表达式的说明此处不再赘述。 2 、元素构造表达式 除了在咀。文档中查找元素，x q u e f y 经常需要产生新的元素。产生新元 素的方法是使用m 。标记直接嵌入到查询语句中，这种表达式就是元素构造表 达式。 3 、f i ：w r 表达式 一个f 1 w r 表达式通过f o r 、l e t 、w 脏r e 和r e l l 瓜n 语句来构造的， 山东大学硕士学位论文 这些语句必须以正确的顺序出现。一个h 腓表达式绑定值到一个或更多变量 上，然后使用这些变量来构造一个结果。f o r 语句用在需要重复的地方它引入 一个或更多变量，将每个变量和表达式对应起来；l e t 语句也可将一个或多个 变量绑定到一个或多个表达式，与f o r 语句不同的是，u 玎语句仅仅将每个变 量无重复地绑定到各表达式的值上，使每个变量对应一个绑定f 1 w r 表达式可 以包含几个f o r 和l e t 语句：w 玎j r e 语句代表x q u e r y 查询的条件；而 砌! nj l c n 语句则代表构建返回的结果。 4 、包含操作符和函数的表达式 与大多数查询语言一样，x q u e 巧提供了一系列可以用在表达式中的操作 符，并允许将操作数加上括号。x q u e f y 所提供的操作符种类有算术操作符、比 较操作符、逻辑操作符、序列操作符、结点操作符以及其他操作符。 5 、条件表达式 一个条件表达式计算一个测试表达式，然后返回两个结果表达式中的一个。 若测试表达式的值是真的，第一个结果表达式的值返回，否则第二个结果表达式 的值返回。 6 、限制表达式 有时需要测试某个元素是否满足某个条件，或决定是否某个集合下所有元 素满足一个条件。x q u e r y 提供了某个表达式和每一个表达式这两种表达式方 式，表达式的这两种形式也就是量化表达式，某个表达式使用一个现存的量词， 每个表达式使用一个通用的量词。某个表达式的值总是真或假，就像f o r 语 句，一个某个表达式使用矾语句里由表达式所返回的值产生对一个变量的多次 绑定，对于每一个绑定要执行s a s f 正d s 表达式，如果至少有一个 s a ：n s 砸d s 表达式的执行返回布尔值为真，那么某个表达式是真，否则为假， 当然如果玳语句中的表达式不返回任何结点则不计算s 棚s f 正d s 表达式并且 某个表达式的结果为假 7 、测试和修改数据类型的表达式 x q u e r y 有一个基于皿s c h e m 的类型系统可以在查询中使用定义在名 字空间h t t p ：，v m ( w 3o f g 2 0 0 1 ) ( m l s c h e m a 的数据类型名。x q u e f y 类型名出现 在可以指定函数参数类型和结果类型的函数声明中，类型名字也可以使用在 山东大学硕士学位论文 c a s t 和n 汪 t 表达式中并作为矾s t a n c e o f 操作符的操作数。 除了上述表达式x q u e f y 还提供了一个内置函数的核心库一一x q u e r y 核 心函数库，包括x p 甜l 核心函数库的所有函数：集合函数以及其他函数集合函 数如a v g 、s 砌、c o 岫t 、m a ) ( 、r n i n 、d i s t i n c t 、e m p 锣等。 1 4 论文的组织 本论文共分五章，其中第一章为绪论，主要针对咀。的有关概念进行介绍， 并对其中关键的技术沮。的查询技术和“l 的存储方法进行了详细的介绍， 确立课题的研究内容。然后在第二章中系统阐述了由本实验室自主设计研发的， 用来存储儿文档的n x d 数据存储模型，并介绍了该模型的实现方式以及查 询、修改、插入和删除等操作的实现方式。在第三章中介绍了一种由) a t h 模型 扩展而来的，专门针对t e m p o r a l ) 。文档的数据模型。在第四章中介绍了在 t e m p o r a l 皿。这种特殊的帆文档中实现的一种特殊的索引结构，介绍了该 索引的构成方式，并详细给出了生成该索引的算法以及在t e 啪r a l x m l 文档上 进行查询、插入和删除等操作时对该索引的使用方法。第五章对以上内容进行了 总结，并对今后的工作提出一些设想。 山东大学硕士学位论文 2 1 基本概念 第二章札存储模型 在当今的数据库领域中，关系型数据库系统已经发展为相关技术的主流。 在一般的关系型数据库中，数据通常存储在第二级存储器当中，一般情况下就是 计算机中的磁盘。各种数据通过存储管理器建立起数据元素与数据块之间的关联 关系，将数据元素存储在磁盘中。然而，只有数据在主存储器中时，才能对其进 行有意义的操作。因此，数据库管理系统中都有一个成为缓冲区管理器的成分， 它负责将可使用的主存空间分割成为缓冲区。计算机通过页面调用的方式，在缓 冲区和磁盘之间进行数据的传输。每一次的页面传输称之为一次磁盘i o 。这样， 所有需要从磁盘得到的信息的数据库管理系统成分都与缓冲区以及缓冲区管理 器之间进行交互。不同的数据库成分所需要的数据类型包括： ( 1 ) 数据：数据库自身的内容，构成数据库的实质性信息。 ( 2 ) 元数据：数据的数据，描述数据库的结构和对数据库的约束的数据 库模式。 ( 3 ) 统计信息：数据库信息系统收集和存储的关于数据库的各个关系或 其他成分的大小、取值等的信息。 ( 4 ) 索引：支持对数据进行高效存取的数据结构，是一个数据库系统付 诸使用的重要工具。 在图2 1 中给出了一般的数据库的构成成分。 1 4 山东大学硕士学位论文 图2 1 数据库的构成 山东大学硕士学位论文 对于皿文档来讲，一个) a 儿文档一般是由元素( 元素名) ，属性( 属性名， 取值) 和被元素包住的字符数据( 可以有超级链接) 组成它是一种近似于层次的逻 辑结构所谓近似是因为在字符数据中仍然有超级链接整个文档由一个大的元素 组成，内部允许嵌套多层元素。结构上类似于广义表。很显然它的结构比关系数 据库中关系更有表现力，一个x m l 元素可以包含其他元素、变化顺序和属性的 数量，并且可以包含具有相同元素类型的多个元素，这使得它更容易表示复杂的 数据。还有一些类似于面向对象的编程语言中对象的特性。例如，元素类 型、命名属性和表示层次的能力。但也有本质的不同，对象设计例如方法，继承 等，v 儿就不具备，就封装来说，对象隐藏所有的内部结构，而l 则显式 地暴露所有的内部结构，因此对象成为更好的编程基础，而皿成为更好的数 据表示的基础因此皿。比对象更容易与数据交换一起使用。 从存储角度上来说，由于它是文档的形式，因此存储一个文档有多种粒度 可以选择，可以存储完整的文档，也可以被分割为更小的部分保存为片段，或被 分解为独立的元素，这里存储平台像其他n x d 一样只考虑整个儿文档的存 储，也就是说是一种大粒度的存储。当然这种方式对并发支持的力度将有所下降 下面本文首先给出数据块的定义。 数据块( b i o c k ) ：数据在二级存储( 一般为磁盘) 和一级存储( 缓存) 之间一次i ，o 的单位，在内存中它也称为页面( p a g e ) 。大小在4 k 5 6 k 之间，这里以4 k 为单位。 在磁盘上它一般由多个扇区( 5 1 2 字节) 组成。对于关系存储由于