（计算机软件与理论专业论文）对于利用dtd模式优化基于路径的xml查询的研究.pdf

山东大学硕士学位论文 对于利用d t d 模式优化基于路径 的x m l 查询的研究 研究生 指导教师 许丰娟 洪晓光教授 摘要 x n i l 作为一种数据的表示形式，正在数据库及网络中的数据传输领域被广泛 使用。关于存储方面的研究很多，并且对于x m l 的存储数据方面现在基本上都已 经能实现了。但用x m l 存储了数据之后，对它进行查询就成了一个不可避免的事 实，关于这方面的研究也成为我们研究的一个热点，提高查询的速度成为一个我 们必须研究的方向，现在有很多查询的方法，但仍然在时间和空间上的效率不是 很理想。仍有待于投入更多的研究，进一步对查询进行优化。 随着x m l 不断的被广泛应用，用它来表示数据也有了一系列的规范，每个 x m l 文档都有一个对应的d t d 来规范制约它的结构。基于这一思想，为了更高 效的利用d t d ，这篇文章提出了一种更高效利用d t d 对x m l 数据进行查询的方 法。 本文以软件开发为背景，提出了一种对d t d 快速扫描的方法，并提出了对扫 描d t d 树的结果，即真路径的存储方法；然后，介绍了我们扫描d t d 树的基本 思想和算法，然后又基于d t d 扫描的结果，即得到的真路径，提出了对x m l 文 档树进行查询的思想及算法。文章最后给出了例子，详细分析了对于x m l 基于路 径的查询，我们提高它的效率的原理。 本文所做的具体工作是具有实际意义的，现在虽然对x m l 查询的研究很多， 但很多都是基于理论的，或只研究了查询中的一小部分，以现在对x m l 的利用情 况是无法实现的，本文不只提出了基本思想，而且还提出了算法，能在x m l 现有 的情况下去实现，所以是有实际意义的。 山东大学硕士学位论文 关键词：有效的x m l 文档，d t d 树，真路径 i i 山东大学硕士学位论文 t h es t u d yo fu s i n gd t dt oo p t i m i z e x m l q u e r yb a s e dp a t h p o s t g r a d u a t e ：x uf e n g j u a n t u t o r ：p r o f h o n gx i a o g u a n g a b s t r a c t x m li ss u i t a b l ef o rd a t ar e p r e s e n t a t i o n ，a n di ti sb e i n gu s e dw i d e l yi nt h ea r e ao f d a t a b a s ea n do fe x c h a n g i n gd a t ao v e rt h ew e b t h e r ea r es o m ei n v e s t i g a t i o no ns t o r a g e ， a n dm a n ys t o r a g em e t h o d sf o rx m lh a v eb e e na c h i e v e d b u ti ti si n e v i t a b l et oq u e r yo n x m ld a t aa f t e rt h ea p p l i c a t i o no fx m lb e c o m e st r u e s oi t i se s s e n t i a lt of i n da l l e f f e c t i v ex m lq u e r yl a n g u a g e m a n yp e o p l ep r o p o s em a n yk i n d so fx m lq u e r y l a n g u a g e ，b u tt h e i re f f i c i e n c yo nt i m ea n ds p a c ei sn o tp e r f e c ty e t a n di ti sc r u c i a lt o h a v em o r es t u d i e so no p t i m i z i n gx m lq u e r yl a n g u a g e se x i s t i n gn o wa n dp r o p o s i n g m o r et a c t i c so nx m l q u e r y w i t ht h eg r o w i n gp o p u l a r i t yo fx m l ，t h e r ea r em a n yc r i t e r i o n st or e s t r i c tt h e s t r u c t u r eo f x m ld o c u m e n t f o re v e r yx m ld o c u m e n t ，t h e r ei sad t dc o r r e s p o n d i n gi t t or e s t r i c ti t ss t r u c t u r e o nt h eb a s eo ft h i s ，f o ra p p l y i n gt h ed t dt ox m lq u e r y e f f i c i e n t l y , am e t h o df o ru s i n gt h ed t d t oi m p r o v ex m l q u e r yi si m p o s e di nt h i s a r t i c l e am e t h o df o rs c a n n i n gd t dt r e ef l e e t l ya n dam e t h o df o rs a v i n gt h es c a n n i n g r e s u l t sa r ep u tf o r w a r d ，a n dt h es c a n n i n gr e s u l t sa r en a m e dt r u ep a t h s t h eb a c k g r o u n d o ft h i sa r t i c l ei sm a k i n gs o f t w a r e a n dt h e n ，i tp r o v i d e st h eb a s i ci d e aa n da l g o r i t h mo f s c a n n i n gd t d t r e e a n do nt h eb a s i so ft h er e s u l t so fs c a n n i n gd t d t r e e ，n a m e l y , t r u e p a t h s ，i tp r o d u c e st h eb a s ei d e aa n da l g o r i t h mo fs c a n n i n gx m ld o c u m e n tt r e e t h e r e a r ei l l u s t r a t i o n sa tt h ee n do ft h i sa r t i c l ea n di te x p l a i n sd e t a i l e d l yt h et h e o r yt h a tt h e m e t h o d sp r o v i d e di nt h i sa r t i c l ei m p r o v ex m _ lq u e r yb a s e dp a t h t h es i g n i f i c a n c ef o rt h ei d e a sa n da l g o r i t h m sp r o p o s e di nt h i sa r t i c l em e a l l s p r a c t i c a l i t y t h o u g ht h e r ea r em a n ys t u d i e so nx m lq u e r y , m a n yo ft h e ma r eb a s i so n t h e o r e t i c s a n dm a n yo ft h e ma r eo n l yo n ep a r to fo n em e t h o do ft h ex m lq u e r y , a n di t i sn o ti m p l e m e n t e da tp r e s e n t i nt h i sa r t i c l e ，n o to n l yt h eb a s i ci d e a sa r ep r o v i d e d ，b u t a l s ot h e a l g o r i t h m s a r e p r o d u c e d a n dt h e ya r ei m p l e m e n t e dw i t h t h e p r e s e n t i i i 山东大学硕士学位论文 t e c h n o l o g i e s s oi ti se n f o r c e a b l e k e y w o r d s ：v a l i dx m ld o c u m e n t ，d t d ，t r u ep a t h s 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究作出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名： 盗圭鱼瓷 日 期：驴r o f 、啦r 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅：本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：盗圭! 鱼导师签名：心多e 丸 日期：k 町。蟛f 山东大学硕士学位论文 1 1 引言 第一章绪论 世界不断发展，人们需要交流的东西也越来越多，随着信息时代的到来，一切 需要交流的东西转换成了数据。i n t e r n e t 作为一个全世界信息发布和交流的中心， 正在改变人们对信息处理的传统观念。i n t e m e t 中的数据浩浩荡荡，千变万化，也 越来越需要有一种统一规范的描述方法，来保证信息传输的流畅。 第一种标记语言g m l 发明于1 9 6 9 年，主要用于支持文档处理应用。五年后 出现了标准通用标记语言( 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 ，s g m l ) ，并且 从1 9 7 8 年到1 9 8 0 年它不断被国际标准化组织修改和发展，以满足系统的独立性 和国际交换的要求，这些要求使得用于处理那时已有的相异系统的广泛选择成为 必要。将来在文档化处理复杂系统时，s g m l 是一个优秀的、强有力的工具，但 不幸的是，s g m l 对现在因特网的需求过于复杂。 h t m l 是s g m l 的为了简单设备独立再现和超链接的一个应用。h t m l 在因 特网的诞生时期非常适合它的发展，但是随着因特网成为商业中心、信息中心、 商业运作中心，h t m l 的应用出现了一系列的问题，比如确认h t m l 文件很困难， 链接系统不灵活，以及缺少国际化的支持等，h t m l 不再能够满足因特网的需求。 与h t m l 相反，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 ) 是s g m l 的一个配置，设 计于9 0 年代后期，它给s g m l 提供在w o r l dw e b 环境中的可扩展能力。x m l 不 完全象s g m l ，它不允许选择自由，它只支持为w e b 作出的选择，对下代的因 特网应用程序、电子贸易和公司的d n s 而言，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 应用通常通过创建文档类型定义( d o c u m e n tt y p ed e f i n i t i o n ，d t d ) 来定义，d t d 是x m l 文档的可选组件。d t d 类似一个数据库概要信息：它定义 和命名了可以在文档中使用的元素、元素显示的顺序、可用的元素属性以及其他 文档特性。要使用一个特定的x m l 应用，通常需要在x m l 文档中包括其d t d ： 在文档中包含d t d 限制了可以使用的元素和结构，这样文档就被强制符合该应用 程序的标准。x m l 不仅是一种用于定义文档的立即可用的工具，而且还可以当作 建立需要随i n t e m e t 发展的应用程序和x m l 增强功能的框架。 x m l 具有自描述特点，支持用户自定义标记标明数据的语义，具有很强的灵 活性，由于它的很多优点，逐渐成为i n t e m e t 中信息描述和信息传输交换的新的标 准，被认为是最有发展潜力的一种半结构化数据组织方式。 1 2x m l 的可用性 x m l 作为s g m l 的一个配置，最初被设计通过分离内容和格式来面对大规模 的电子出版业的挑战。把一个文档的内容和它怎样被格式化分离开来，简化了开 发和维护。具有不同专门技术的不同的人员( 或团队) 可以独立的操作从文档中 抽取的关于格式、样式和美化的信息。 x m l 在数据交换中也是有用的，x m l 可以用来在w e b 上的应用之间或应用 与用户之间交换数据。x m l 本身并不给终端用户提供表示，但是当与样式表( 提 供样式) 一起使用时，就容易浏览x m l 文档了。x m l 文档提供一种方法来获取 数据、样式表( 例如，可扩展的样式表语言，x s l ) 或层叠样式表( 提供把x m l 转化为h t m l 或其他表示的机制，c s s ) ，x s l 和c s s 控制x m l 在w e b 浏览器 中的表示。 x m l 另一个关键的优势就是集成数据和文档的能力。大多数语言或者在表示 严格的、绝对的内容和数据结构上设计得好一点，或者在表示灵活的、自由形式 山东大学硕士学位论文 的文档文本上设计得好一些，但是x m l 在两方面都做的很好。它能格式化通过 e m a i ! 发送的情书，或者用来发表一首诗。x m l 能表示数据和自由格式的文本， 也能在同一个文档上做到这两方面。详细的评论或完整的科学论文能够以一种广 泛的、复杂的数据集来解释一块简单的数据，科学论文可以在文档中嵌套大量复 杂的层次数据集。 x m l 用一种灵活的可扩展的表示来实现内容通信。因此，数据的描述可以反 复的被优化为基础域的变化，这使得x m l 对具有一个复杂的，频繁遭受修订的组 织的领域是特别有用的。一些早期的x m l 技术的采纳者包括一些科学领域，例如 生物、化学和数学。存在于这些领域的基于x m l 的科学标准分别是b i o m l 、g m l 和m a t h m l 。这样，非常复杂的领域可以使用x m l 很好的合理的表示出来。 与其他数据交换语言相比，x m l 的两个关键特性就是它具有相当的表现力和 可扩展性。实际上，你可以在你选择的主题上表述任何你想表述的。它具有一致 的语法，这使它很容易的被解析。因此，x m l 可以获取在应用之间交换的信息的 类型；x m l 文档也可以被剪裁以适合特殊的需求。 x m l 可以使用用于定义处理的样式表来表示w e b 页面上的内容。w e b 页面可 以是静态的或动态的，例如在线目录。静态的w e b 页面中，内容和表示的分离可 以简化开发，也可以减少页面的大小。动态的w e b 页面非常容易表示，因为内容 可以随着需求改变，而样式表保持不变。当内容上具有同样的条件时，使用同样 的样式表，可能会有非常不同的表示。 x m l 文档可以用多种形式发布：h t m l 、p d f 、p o s t s c r i p t 等等。 x m l 另外的一个优点是，它可用于数据库中，数据库可以把数据存储为x m l ， 并且使用x m l 与其他应用进行交互。 正因为x m l 语言具有以上的实用性，所以我们有必要对它进行各方面的研究， 尽快的在很多领域灵活的运用它，加快它的发展。 1 3 对于x m l 文档查询的研究现状和面临的问题 尽管x m l 可以描述非常复杂的结构，其本质仍然是树状的数据。针对x m l 的查询，学者们已经提出了多种x m l 查询语言，例如x p a t h ，x q u e r y 等。这些 查询语言都将路径表达式作为核心内容。针对路径查询的处理问题，人们已经进 山东大学硕士学位论文 行了大量的研究工作。目前还有一种分解连接查询执行的策略，它的基本思想是， 首先定位路径查询树中每个结点的候选元素节点集合，然后通过结构连接操作组 合这些中间结果来生成最后的结果。采用这种策略会产生大量的结构连接操作。 在树状的x m l 数据中匹配路径查询的基本方式是对数据进行导航式的遍历，它简 单直接，但执行效率不能得到保证，尤其是在大数据量的情况下。目前这一方面 主要的工作集中在怎样提高扫描文档树的效率。本文则利用了限制x m l 文档结 构的d t d ，来提高遍历文档树的速度。 1 4 本文的组织结构 本文的组织结构如下：第二部分中说明了文章的背景和我们用到的一些关于 x m l 的基本理论，并介绍了几个与我们文章相关的概念：第三部分和第四部分是 文章的主要内容，第三部分描述了怎样存储扫描d t d 得到的路径及扫描d t d 的 算法；第四部分描述了怎样利用由第三部分得到的结果来层次遍历x m l 文档树及 其用到的队列的数据结构，在最后一部分中，对全文做了总结，对我们的方法的 优点做了叙述，并讨论了它的应用情况。 山东大学硕士学位论文 2 1 引言 第二章对于x m l 文档的基于路径的查询问题 随着x m l 作为一种网络语言的广泛使用，产生一种高效的x m l 查询语言是 很重要的，也引起了我们的关注。尽管x m l 表达数据时经常以文本的格式出现， 但它却能很清晰的表示出数据之间的层次关系，其本质仍是层次关系，所以每个 x m l 文档都对应着一棵树状结构。x m l 文档只是一种正文文件，因此能够使用 普通的文件i 0 方式进行读写，但采用这种方式进行读写就失去了x m l 文档的意 义了。 有效的x m l 文档都具有大量的结构信息，我们要以某种能够检查其有效性的 方式读取它们，而且要保留它们都具有什么字段以及结构如何等信息。我们需要 有一个能够读取x m l 文件，并在内存中生成一种树形数据结构，其中包含x m l 文件中的所有信息的扫描器。d o m 扫描器是一种非常通用的程序，它根本不知道 用户定制的x m l 文件标记符的确切含义就能按我们的希望完成读取x m l 文件的 工作，并最终返回一个完整地描述x m l 文件内容的树形数据结构。所以，我们现 在要由一个x m l 文档得到与它对应的x m l 文档树已经不成问题了，它是实现我 们算法的前提条件。 2 1 1 查询条件的模式 基于它的树形结构的查询也有很多，比如关于利用x m l 文档结构对x m l 文 档的查询 1 4 5 6 7 8 ，他们都讨论了基于结构的递归的查询。我们所用的很多查询， 大多都是以路径的方式输入的查询条件，但路径中的元素只是父子关系或子孙关 系，并不是文档中找到该元素的详细路径，这种查询叫做结构递归查询，一般有 一个符号“”，如l i b e r a r y t i t l e ，l i b e r a r y 只是t i t l e 的祖先，所以，只要是l i b e r a r y 的子孙中的t i t l e ，都要输出的；再如，t i t l e ，无论t i t l e 的路径是怎样的，无论它 的位置在哪里，只要从根结点开始，在其子孙结点( 包括它自己) 中找t i t l e 结点。 基于此，很多研究都利用了分解路径的方法来优化查询。 山东大学硕士学位论文 2 1 2 问题背景 关于对x m l 文档查询的研究很多，如现在正在发展的查询语言x p a t h 2 和 x q u e r y 4 1 1 】等。x q u e r y 的一些实例证明结构递归查询是非常有用的，但在结构 递归查询中也遇到了一系列的问题，比如怎样将输入的结构转化，生成新的有用 的结构，怎样保存输入的结构及相关的层次等。x q u e r y 核心【3 5 是x q u e r y 语言 核心的一部分，x q u e r y 核心支持映射 9 ，在x q u e r y 核心中，每个x q u e r y 输入 式被映射到一个表达式，此表达式表示了原来输入式的语义。x q u e r y 核心中有很 多定义表达式类型的原则和一些等价原则，然后再根据那些原则定义映射的表达 式的类型并且简化表达式。这样，x q u e r y 核心就为x q u e r y 提供一些算法，并且， 对于x q u e r y 核心来说，映射表达式，定义表达式类型及优化表达式是非常重要的。 然而，x q u e r y 核心并不完全是关于结构递归查询的。由x q u e r y 核心推断出的结 构递归查询的类型往往是不精确的，因为查询调用了一些复杂的函数，这些函数 声明的返回类型通常是一个一般类型：x s ：a n y t y p e 。 x q u e r y 核心包括两部分，一个是映射，一个是定义类型。 映射：一个结构递归查询调用一个或多个递归函数。对于由符号“，”后面加 查询目标，只有这两部分构成的查询，一般被映射成调用一个递归函数的函数和 一个映射关系，调用的这个递归函数为d e s c e n d a n to rs e l f o ；比如，t i t l e 被最终 映射为：d e s c e n d a n to rs e l f ( $ r o o t s ) t i l t e 。变量$ r o o t s 是唯一的一个变量。从映射的 表达式，我们有以下复式表达式： f o r $ v li nd e s c e n d a n to rs e l f ( $ r o o t s ) r e t u r n t y p e s w i t c h ( $ v 1 ) a s $ v 2 c a s ee l e m e n tt i t l e ( x s ：a n y t y p e ) r e t u r n $ v 2 d e f a u l tr e t u m0 t y p e w i t e h 和a s 是关键字，s v l 是操作数，$ v 2 是操作数变量。无论操作数 为什么类型，总满足其中的一种c a s e 情况，因为c a s e 语句中包含了所有可能的情 况。第一个符合的c a s e 语句叫做有效情况。操作数表达式或许可能有好几种类型， 但操作数变量只有一种类型，动态的随着情况的变化而不同。表达式能很快的决 定, q 4 , $ v l 的当前类型。以上复式表达式的意思是：对于r o o t 结点的每个子孙结点( 包 山东大学硕士学位论文 括r o o t 自身) ，如果子孙结点的类型为e l e m e n t t i t l e ( x s ：a n y t y p e ) ，则返回此结 点，否则返回空值。 ( a ) d t d 定义 d b l i p i n g s o n g s 5 0 c o ) d t d 定义的x m l 文档 图2 1 定义类型：定义的函数的类型，必须包括函数实际的类型，但这样有可能定义 的函数的类型是没有意义的，比如x s ：a n y t y p e 。接收x m l 数据的语义递归函 数的类型通常都声明为：x s ：a n y r y p e ，因为这种结构递归查询调用的函数结果 的类型定义的不是很精确。 一个a dh o c 方法 5 是用一个定义类型的函数r e c f a c t o r 0 来给不同的结构递归查 询来定义类型的，因) b t i t l e 可映射到d e s c e n d a n to rs e l f ( $ r o o t s ) t i t l e ，我们有必要 给函数d e s c e n d a n to rs e l f ( $ r o o t s ) t i t l e 定义类型。当前的a dh o c 方法调用函数时， 用根结点的类型r o o t 作为函数的变量，然后r e c f a c t o r 0 收集在遍历以r o o t s 为根结 点的整棵x m l 文档树的过程中遇到的所有类型。对于图2 1 的x m l 文档树，给 出以下类型： t y p eb i b = 山东大学硕士学位论文 e l e m e n tb i b ( b o o k + ，c d + ) t y p eb o o k 2 e l e m e n tb o o k ( e l e m e n tt i t l e ( x s ：s t r i n g ) ， e l e m e n ta u t h o r ( e l e m e n tf i r s t ( x s ：s t r i n g ) ， e l e m e n tl a s t ( x s ：s t r i n g ) ) + ) t y p e c d 2 e l e m e n tc d ( e l e m e n tt l t l e ( x s ：s t r i n g ) ， e l e m e n tp r i c e ( x s ：s t r i n g ) ) 1 21 3 只是优化了规则路径的查询，即非结构递归查询。s t r u c t u r a lf u n c t i o n i n l i n i n g 1 采用了一种著名的技术嵌入式函数 1 0 来定义和优化结构递归查 询，它的理论基础是：在定义一个结构递归查询的类型及优化它时，最大的障碍 就是它调用的表达语义的递归函数，【1 将映射的函数表达式转化成了函数体，并 将x m l 文档的结构嵌入函数中。如在图2 1 的文档中，有查询t i t l e ，则初始嵌 入式函数为图2 2 ( a ) ；将x m l 数据的结构代入后的结构嵌入式函数为图2 2 ( b ) 。 它的算法的基本思想就是以上描述的，然后一层层递归，直到最后到e l e m e n t t i t l e 。 如以上查询t i t l e ，算法思想为图2 3 所示，然后再根据x m l 数据结构执行它调用 的函数g e t t i t l e ( c h i l d r e n ( $ x ) ) ，最后产生化简后的结果。 g e t t i t l e ( $ b i b ) f o rs ni n $ b i br e t u r n b y p e s w i t c h ( s n ) a ss x c a s ee l e m e n tt i t l e ( x s ：a n y t y p e ) r e t u r ns x d e f a u l tr e t u r n0 ( a ) 初始的嵌入式函数 g e t t i t l e ( $ b i b ) f o rs ni ns b i br e t u r n b y p e s w i t c h ( $ n ) a ss x c a s ee l e m e n tt i t l e ( x s ：a n y t y p e ) r e t u r ns x d e f a u l tr e t u r n0 山东大学硕士学位论文 ( b ) 结构嵌入式函数 图2 2 为了规范x m l 文档，通常都用d t d 模式来限制x m l 文档的结构，d t d 是 一棵树状结构。本文利用d t d 查出可能得到目标结点的路径，然后再利用这些路 径对结构递归函数优化。这篇文章中提出了一种高效利用d t d 的方法，提出了一 种对d t d 扫描的方法及怎样存储其扫描结果，并提出了一种利用d t d 扫描的结 果扫描x m l 文档树的方法。 g e t t i t l e ( $ b i b ) f o r $ ni n $ b i br e t u r n b y p e s w i t c h ( $ n ) a ss x c a s eb i br e t u r ng e t t i f l e ( c h i l d r e n ( $ x ) ) d e f a u l tr e t u r n0 图2 3 2 2 基本理论 2 2 1x l v i l 文档的基本结构 一个x m l 文档一般主要有两个主要组成部分：序言和文档元素。文档元素也 就是根元素。如下面的一个x m l 文档。 t h ea d v e n t u r e so fh u c k l e b e r r y 2 9 8 t h et u r no f t h es c r e w 2 9 8 山东大学硕士学位论文 前三行是序言部分，第一行是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 文档中的文本是由标记和字符数据混合成的。标记是用来描述文档结构 的定界文本即元素的起始标签、元素的结束标签、空元素标签、注释、文档 类型声明、处理指令、c d a t a 节定界符、实体引用和字符引用。所有其他的文本 是字符数据真正的文档信息内容。 在示例文档中，文档元素是小v e n t o r y 。其起始标签是 ，其 结束标签是 ，其内容是两个嵌套的b o o k 元素。 2 2 2 基本的x m l 规则 理。 一个格式正确的文档是符合最小规则集的文档，它可以被浏览器或其他程序处 文档必须正好有一个顶层元素( 文档元素或根元素) 所有其他元素必须嵌 山东大学硕士学位论文 入到其中。 元素必须被正确地嵌套。也就是说，如果一个元素在另一个元素中开始， 那么它必须在同一个元素中结束。 每个元素必须同时拥有起始标签和结束标签。与h t m l 不同，x m l 不 允许忽略结束标签一一即使浏览器能够推测出元素在何处结束时也是如 此。 起始标签中的元素类型名必须与相应结束标签中的名称完全匹配。 元素类型名是大小写敏感的。实际上，x m l 标记中的所有文本都是大小 写敏感的。例如，下列元素是非法的，因为起始标签的类型名与结束标签 的类型名不匹配： l e a v e so fg r a s s 2 2 3 基本概念 以下我们给出几个与我们的文章及其背景相关的基本概念。 x m l 文档是表示数据的，数据多了，就会没有了秩序，这时要有一个规 范他们结构的机制是很有必要的，可以文档类型定义( d t d ) 的方式定 义x m l 文档，如果一个x m l 文档符合d t d 定义的规则，则被称为有效 的x m l 文档，研究有效的x m l 文档将更有意义，更有价值，可以对有 效的x m l 文档内容的有效性进行检查。 x m l 文档一般是以文本的形式展现在我们面前的，若将其转换成树状结 构后，他的层次结构将能更清晰的表现出来，我们在上面所做的操作也将 会更容易，x m l 文档所对应的树状结构，我们称之为文档树。 为了利用d t d ，我们有必要将其文本格式转换成一棵树状结构，我们在下 面对其扫描时，只要遍历这棵树就可以了，d t d 所对应的树状结构，我们 称其为d t d 树。 文档树或d t d 树中的一结点，它所对应的内容是我们所要查询的最终结 果，我们称之为目标结点。 在d t d 树中，从根结点到目标结点所经过的所有结点及其顺序构成的路 山东大学硕士学位论文 径，我们称为真路径，在文档树中若要找到目标结点，其路径也必为某条 真路径。真路径上的每个结点就象一个个站点一样，它们的顺序对我们也 是非常重要的，所以我们要记的是真路径，而不是一大堆的结点。 b i b 。 。i t l e m 。，。m 。阳。 f i r s tl a s t 图2 4 图2 1 ( a ) 对应的d t d 树 对于图2 4 ，若查询n t i t l e ，目标结点为t i t l e ，真路径有两条 ( b i b ，b o o k ，t i t l e ) ( b i b ，c d ，t i t l e ) 并且每条真路径中结点的次序是不能变的。 2 3 本章小结 本章首先阐述了问题产生的背景以及问题提出的方式，说明需要解决的问题是 优化以路径方式给出的查询，查询前已经给出文本文档和对应的文档树，并且也 己知道x m l 文档所对应的d t d 树；然后介绍了与本文章相关的几个概念，并举 例说明了概念的含义。 山东大学硕士学位论文 第三章遍历d t d 树 我们在本章中将详细描述怎样遍历d t d 树，找到我们所需要的真路径。 3 1 真路径的存储结构 对于怎样利用我们得到的真路径查询文档树，真路径的存储结构也是非常重要 的，真路径存储结构如图31 。 1 2 n 图3 1 叫王 叫王 总的是以数组存储的，数组的每个元素是可能找到目标结点a 的一条真路径； 每条真路径是用链表存储的，链表中每个结点的结构分为两部分( d a t a ，n e x t ) ，链 表中的元素) j n i 链表中元素的顺序就成为一条真路径( 如图3 1 ) ，链表中每个元 素的d a t a 为d t d 树中查到目标结点a 所经过的结点，n e x t 是指针类型。 3 2 扫描d t d 的基本思想 我们用栈来深度扫描整棵d t d 树，若结点不是目标结点，则将结点压栈，直 到遇到目标结点a ，将a 放入真路径中；按照先进后出的原则，然后用同样的方 法处理栈顶元素其他的子树，直到它没有子结点了，让它出栈，根据它的子结点 是否为真路径经过的结点来判断它是否加入到真路径中，如果有真路径经过它的 山东大学硕士学位论文 一个或多个孩子结点，则就应该将其加入到真路径中，找一下已出栈的真路径部 分中哪些以自己的孩子结点为开头，把它加在这些真路径的开头部分：每个栈顶 元素都要以同样的方法来处理。直到栈为空；我们要在栈中保存的是压栈的结点， 当前正在处理它的第几个孩子结点，还有到现在为止，真路径是否通过它的一个 或多个孩子结点，共三个参数。不妨，我们用n o d e 来表示该结点，v i 来表示正在 处理n o d e 的第v i 个孩子结点，用p u t i n 等于1 或0 来表示到目前为止，是否有真 路径经过它的孩子结点，即它是否该加入到真路径中。栈中元素形式为( n o d e ， v i ，p u t i n ) ，例如我们的目标结点为图2 4 中的t i t l e ，栈中的情况变化如图3 2 所示， 扫描从d t d 树的根结点b i b 开始，因为b i b 不是目标结点t i t l e ，开始处理它的第一 个孩子结点，将b i b 压栈，到目前为止，没有任何路径经过它的任何孩子结点，所 以栈中情况如图3 2 ( a ) ：它的第一个孩子结点b o o k 也不是目标结点，开始处理 结点b o o k 的第一个孩子结点，并将b o o k 压栈，同样到目前为止，也没有任何真 路径经过结点b o o k 的任何子结点，所以栈中情况如图3 2 ( b ) 所示，b o o k 的第一 个孩子结点t i t l e ( 1 ) 与目标结点一致，将t i t l e ( 1 ) 放入r o a d 中，r o a d 为存储真路径的 数组，其结构如图3 1 ，这样结点t i t l e ( 1 ) 就处理完了，然后处理栈顶元素b o o k ，因 为栈顶元素中v i = 1 ，所以这时知道b o o k 的第一个孩子结点处理完了，因为真路 径经过它的第一个孩子结点t i t l e ，所以b o o k 的p u t i n 值改为1 ，再找b o o k 的下一 个孩子结点发现它还有第二个孩子结点，所以开始处理它的第二个孩子结点 a u t h o r ，并将栈顶元素中、，i 的值改为2 ，栈中情况如图3 2 ( c ) ，同样，发现a u t h o r 也不是目标结点，所以开始处理它的第一个子结点f i r s t ，并将a u t h o r 结点压栈；栈 中情况如图3 2 ( d ) ；开始处理f i r s t ，它不是目标结点，并且没有子结点，所以将 其舍掉：栈顶元素a u t h o r 还有第二个子结点，所以开始处理它的第二个子结点， 栈中情况如图3 2 ( e ) ；同它的第一个子结点一样，将它的第二个子结点l a s t 舍掉； 栈顶元素没有第三个子结点，所以出栈，这时，因为它的p u t i n 值仍为0 ，即没有 任何真路径经过它的孩子结点，它又不是目标结点，所以将其出栈后舍掉，栈中 情况如图3 2 ( f ) 。继续处理栈顶元素b o o k ，看到b o o k 的“值为2 ，所以，它的 第二个孩子结点已经处理完了，找它的下一个子结点，结果，它没有孩子结点了， 所以b o o k 结点也处理完了，因为这时它的p u t i n 变量的值为1 ，所以在真路径中找 以它的孩子结点为开头元素的真路径，：然后将其加在真路径的前面，真路径的情 山东大学硕士学位论文 况如图3 3 ( b ) 所示；然后继续处理栈顶元素b i b ，这时栈中的情况如图3 2 ( g ) ， 因为它的第一个子结点b o o k 加入到了真路径中，所以它的p u t i n 值也改为1 ，并开 始处理它的第二个子结点，栈中情况改为图3 2 ( h ) ；它的第二个子结点为c d ，不 是目标结点，并且有孩子结点，所以压栈，栈中情况如图3 2 ( i ) 所示；它的第 个孩子结点t i t l e ( 2 ) 为目标结点，所以加入到r o a d 中，成为另一条找到e l 标结点 的真路径，r o a d 的情况如图3 3 ( c ) 所示，然后处理栈顶元素c d ，因为它的第一 个子结点为目标结点，所以它的p u t i n 值改为l ，并且开始处理它的第二个子结点， 栈中情况如图3 2 ( j ) ；它的第二个子结点p r i c e 既不是目标结点，也没有子结点， 所以舍掉，这时栈顶元素c d 处理完了，将其加入到以它的孩子结点t i t l e ( 2 ) 开头 的第二条真路径中，这时栈中情况如图3 2 ( k ) ；处理完c d 结点后，继续处理栈 顶元素b i b ，因为它没有第三个子结点了，所以出栈，并加入到两条真路径中。此 时栈为空，结束扫描过程。 ( a )( c ) ( h )( i )0 ) 图3 2 ( d ) ( e ) 图3 3 山东大学硕士学位论文 往真路径中加b o o k 和c d 时，是不会加错位置的，因为当b o o k 出栈时，只有 一条真路径以t i t l e 开头，这就是我们标的t i t l e ( 1 ) ，所以b o o k 肯定是加在t i t l e ( 1 ) 的 前面，当c d 出栈时，只有第二条真路径是以c d 的孩子结点t i t l e 开头，因为t i t t l e ( 1 ) 的前面已经有b o o k 元素了，所以，c d 不可能加在t i t l e ( 1 ) 的前面，所以b o o k 和c d 加入时，是不会搞混的。扫描过程中，r o a d 的变化如图3 3 ，( a ) 是扫描完t i t l e ( 1 ) 后的情况，( b ) 是扫描完b o o k 子树后的情况，( c ) 是扫描完t i t l e ( 2 ) 后的情况，( d ) 是扫 描完c d 子