（计算机软件与理论专业论文）规则路径表示下xml数据的优化查询.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本人完 全意识到本声明的法律责任由本人承担。 论文作者签名：! ：煎 目 期： 瑚弓。c ? 孑 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：! i ! 函导师签名：日期： 山东大学硕士学位论文 摘要 随着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 ) 的出现，它已成为i n t e r n e t 上信 息表示和交换的新标准 1 ，因为x m l 数据具有自描述性，被认为是定义半结构化 数据最有前景的方法。为了检索x m l 和半结构化数据，已经出现了几种x m l 查询 语言，例如l o r e l 2 ，x m l q l 3 ，x m i g l 4 ，x q u e r y 5 等，它们的共同特征 是用规则路径的表示去查询x m l 数据。以往的研究表明 8 ，运用当前关系数据库 的技术还不能满足x m l 数据的高效存储和查询，并且在处理有规则路径表示的查 询时，采用的一些基于传统遍历树的方法，在查询路径很长或未知的情况下效率 很低。在一些改进的查询处理方法中，提出了一些新的编码方案和索引结构，对 查询的处理也进行了优化，提高了查询效率。对现有索引结构和查询处理算法从 理论上进行剖析研究，并加以改进优化是很有意义的。 本文从x b l l 的基本知识开始，对x m l 的基本概念、语法等方面，配合实例代 码作了介绍，对x m l 解析器和文档对象模型d o m 作了描述。随后，文章重点对x m l 数据的查询语言、索引结构、查询处理算法以及优化问题展开了详细讨论，查询 语言主要介绍了x q u e r y 5 典型的“f o r - l e t - w h e r e r e t u r n ”的语法结构，它是 x q u e r y 所具有的最接近于s q l 的语句。索引结构主要讨论了l o r e 系统 9 的四 种索引和一个称作“i n d e xf a b r i c ” 1 0 的索引结构，对它们基于的理论基础、 框架结构、实现算法进行了描述。在对查询处理的算法中，文章首先简单介绍了 传统的基于遍历树的方法 8 ，重点讨论了基于路径分解 6 的查询处理算法，对 其编码方案、索引结构、查询表达式的分解与中间结果集合并算法进行了分析。 本文的主要工作体现在第五章，一是针对在“路径分解”查询处理算法中， 当查询路径很长时，需合并的中间结果集很多，计算量非常大，而合并次序不同 导致计算量也不同的实际情况，基于“动态规划”的思想，设计出具体算法，先 确定出中间结果集的最优合并次序，再进行合并，大大降低了合并的计算量，提 高了处理效率；二是针对原算法在合并中问结果集时要进行大量树节点“祖先后 代”关系的判断，本文基于关系运算设计出新的处理算法，可减少“祖先后代” 关系的判断问题，进步优化了奁询的处理。 论文的主要内容组织如一f ：第一、二章介绍了x l 基本概念、解析器和文档 山东大学硕士学位论文 对象模型等内容：第三章的内容为x m l 数据的查询语言和索引结构；x m l 数据的 查询处理方法在第四章进行了详细讨论：在第五章，文章提出了用动态规划算法 和关系分解法对处理x m l 数据的查询进行优化；最后在第六章对全文内容进行了 总结。 关键字：) ( m l ，路径分解，合并连接，动态规划 山东大学硕士学位论文 a b s t r a c t t h ee x t e n s i b l em a r k u pl a n g u a g ex m lh a sr e c e n t l ye m e r g e da san e ws t a n d a r df o r i n f o r m a t i o nr e p r e s e n t a t i o na n de x c h a n g eo nt h ei n t e r n e t 1 s i n c ex m ld a t ai s s e l f - d e s c r i b i n g , x m li s c o n s i d e r e do n eo ft h em o s tp r o m i s i n gm e a n st od e f i n e s e m i s t r u c t u r ed a t a t or e t r i e v ex m la n ds e m i - s t r u c t u r ed a t a ，s e v e r a lq u e r yl a n g u a g e s h a v eb e e n p r o p o s e d e x a m p l e s a r el o r e l 2 ，x m i _ q 1 1 3 ，x m l _ g i 4 ，a n d x q u e r y 5 t h ec o m n l o nf e a t u r e s o ft h e s el a n g u a g e sa r et h eu s eo fr e g u l a rp a t h e x p r e s s i o na n dt h ea b i l i t yt o e x t r a c ti n f o r m a t i o na b o u tt h es c h e m af r o mt h e d a t a d e s p i t et h ep a s tr e s e a r c he f f o r t s 8 ，i ti sw i d e l yb e l i e v e dt h a tt h ec u r r e n ts t a t eo f t h e a r to ft h er e l a t i o n a ld a t a b a s et e c h n o l o g yf a i l st od e l i v e ra l ln e c e s s a r yf u n c t i o n a l i t i e st o e f f i c i e n t l ys t o r eo rq u e r yx m ld a t a f u r t h e r m o r e ，w h e ni tc o m e st op r o c e s s i n gr e g u l a r p a t he x p r e s s i o nq u e r i e s ，t h ea p p r o a c h e sb a s e do nc o n v e n t i o n a lt r e et r a v e r s a l sc a nb e f a i r l yi n e f f i c e n t ，e v e nf o rt h ep a t hl e n g t h sa r ev e r yl o n go ru n k n o w n i nt h ei m p r o v e d m e t h o d s ，n e wn u m b e r i n gs c h e m e sa r ep r o p o s e d ，n e wi n d e x e sa r ee s t a b l i s h e d ，a n dn e w a l g o r i t h m si sp r o p o s e dt oo p t i m i z et h eq u e r y i n gx m ld a t a ，t h ee f f i c i e n c yo ft h eq u e r y i si n c r e a s e d t os t u d yt h ec u r r e n ti n d e x e sa n dt h ea l g o r i t h m so fp r o c e s s i n gq u e r y t h e o r e t i c a l l y ，a n dt oi m p r o v et h e mi sv e r ym e a n i n g f u l i nt h i sp a p e r ，w eb e g i nf i o mt h eb a s i ck n o w l e d g eo fx m l ，a n dw i t ht h ee x a m p l e s o fx m lc o d em a k ea ni n t r o d u c t i o no fi t sb a s i cc o n c e p t s ，p h r a s i n g ，e t c e s p e c i a l l y d e s c r i b et h ep a r s e ro fx m la n dt h ed o c u m e n to b j e c tm o d e l l a t e r l y ，t h ex m l q u e r y l a n g u a g e 、t h ec o n s t r u c t i o no fi n d e xa n dt h ea l g o r i t h m so fp r o c e s s i n gq u e r ya r e d i s c u s s e di nd e t a i l t h eq u e r yl a n g u a g en a m e dx q u e r yi sp r e s e n t e d ，t h eu s eo f f o r l e t w h e r e r e t u r ns t a t e m e n t so fx q u e r yi se x p l a i n e d ，w h i c ha r eu s e di na m a m l e rs i m i l a rt os q l a sf o rt h ei n d e xc o n s t r u c t i o n ，t h ep a p e rp r e s e n t st h ef o u rk i n d s o fi n d e x e si nt h el o r es y s t e ma n da n o t h e ri n d e xn a m e d “i n d e xf a b r i c ”，t h et h e o r i e sa n d t h ea l g o r i t h m st h e yb a s e do na r ed i s c u s s e dw i t hs o m ee x a m p l e s w h e nt h ea l g o r i t h m s o fx m lq u e r yp r o c e s s i n ga r ed i s c u s s e d ，t h ec o n v e n t i o n a lm e t h o d sb a s e do nt r e e 1 山东大学硕士学位论文 t r a v e r s a l s 8 a r ei n t r o d u c e df i r s t l y t h e n ，w ep u te m p h a s i so ut h ea l g o r i t h mb a s e do n d e c o m p o s i t i o n o fp a t h e x p r e s s i o n 6 i n t h e a l g o r i t h m ，t h e a n c e s t o r d e s c e n d a n t r e l a t i o n s h i pf o rap a i ro fn o d e sc a nb ed e t e r m i n e db yt h e i ro r d e ra n ds i z ev a l u e s ，w h i c h c a na v o i dt r a v e r s i n gx m lt r e e s m o r e o v e r , t h es p e e do ft h eq u e r yp r o c e s s i n gi s i m p r o v e db yd e c o m p o s i n gt h el o n gp a t he x p r e s s i o ni n t os h o r to n e s t h ep a p e rs t u d i e s t h en u m b e r i n gs c h e m e 、t h ei n d e xs t r u c t u r ea n dt h ea l g o r i t h m so fd e c o m p o s i n ga n d m e r g i n g t h em a i nw o r ko ft h ep a p e rc a r lb es e ei nt h ec h a p t e rf i f t h f i r s t l y , i nt h ea l g o r i t h m d i s c u s s e da b o v e ，t h en u m b e ro ft h er e s u l ts e t sc a ni n c r e a s er a p i d l yw h e nt h eq u e r yp a t h b e c o m ev e r yl o n g d i f f e r e n to r d e ro ft h em e r g i n gl e a d st od i f f e r e n tc a l c u l a t i o n s oa n e wa l g o r i t h mi s p r o p o s e dt oo p t i m i z et h eq u e r y i n gx m ld a t af o rr e g u l a rp a t h e x p r e s s i o n s , w h i c hi sb a s e d o nd y n a m i cp r o g r a m m i n g ，i nt h en e wa l g o r i t h m ，t h eo r d e ro f t h em i d d l er e s u l ts e t s m e r g i n gi sd e t e r m i n e db e f o r et h em e r g i n gi sp r o c e s s d ，t h e c a l c u l a t i o nc o n s u m e sal i u l ea n dt h ee f f i c i e n c yi si m p r o v e d s e c o n d l y ，an e wq u e r y p r o c e s s i n ga l g o r i t h mb a s e do n “r e l a t i o n s h i pa l g e b r ad e c o m p o s i t i o n ”i sp r e s e n t e di nt h e p a p e r , t h ea l g o r i t h mc a ns p e e du pt h er e s u l ts e t s m e r g i n gw i t h o u td e t e r m i n i n gt h e a n c e s t o r d e s c e n d a n tr e l a t i o n s h i pa m o n gt h en o d e so f x m lt r e e t h ec o n t e n to ft h ep a p e ri so r g a n i z e da sf o l l o w s ：t h ef i r s ta n ds e c o n dc h a p t e r s i n t r o d u c et h eb a s i ck n o w l e d g eo f x m l 、p a r s e ra n dd o m ，e t c t h ec o n t e n to f t h et h i r d c h a p t e ri s x m lq u e r y l a n g u a g e a n dt h ec o n s t r u c t i o no fi n d e x i nt h ef o u r t h c h a p t e r ，s o m ea l g o r i t h m sa r e d i s c u s s e di nd e t a i l t w on e wa l g o r i t h m sw h i c hc a n o p t i m i z et h eq u e r y i n gp r o c e s so fx m l d a t aa r ep r e s e n t e di nt h ef i f t hc h a p t e r t h el a s t o n es u l y n n a f t z e sa n dv i e w st h i sp a p e r k e yw o r d s ：e x t e n s i b l em a r k u pl a n g u a g e ，d e c o m p o s i t i o no fp a t he x p r e s s i o n s ， p a t hj o i n ，d y n a m i cp r o g r a m m i n g d 山东大学硕士学位论文 简称 x m l s g m l w 3 c p d a d t d w m l d o m s a x o e m f l w r 符号说明 英文全称中文翻译 e x t e n s i b l em a r k u pl a n g u a g e扩展标记语言 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 标准通用标记语言 w b r l dw i d ew e bc o n s o r t i u m万维网联盟 p e r s o n a ld i g i t a la s s i s t a n t个人数字助理 d o c u m e n tt y p ed e f i n i t i o n文档类型定义 w i r e l e s sm a r k u pl a n g u a g e无线标记语言 d o c u m e n to b j e c tm o d e l s i m p l ea p if o rx m l o b j e c te x c h a n g em o d e l 文档对象模型 l 的简单应用接口 对象交换模型 f o r - l e t w h e r e r e t u r n x q u e r y 的典型句型 5 山东大学硕士学位论文 第一章绪论 1 1 研究背景 ) ( m l 是由万维网联盟( w 3 c ) 开发的，主要目的是为了克服h t m l 的缺点。因 随着h t m l 应用的普及，人们对h t m l 进行了扩展，引入了很多新的标记，h t m l 由 最初的1 2 种标记发展到现在的将近1 0 0 种标记，并且引入了很多种支持技术，如 j a v a s c r i p t 、j a v a 、c g i 、a s p 、j s p 等等，h t m l 已变成一种复杂的语言，但一些 应用程序并不能支持如此复杂的语言，如p d a ( 个人数字助理) 上的一些应用； 另外，格式化一个页面需要很多标记，经常可以看到有些w e b 页面的标记比正文 内容还多，下载和显示比较缓慢。再者，随着i n t e r n e t 高速发展，信息量迅速膨 胀，用户关心的w e b 信息并不是存放在数据库系统中，而是在h t m l 页面中，h t m l 是一种显示描述语言，缺乏结构和元数据信息。通过浏览器，人可以非常直观地 获取自己关心的知识和信息，但是计算机却难以理解这些h t m l 文档。这给w e b 信 息的集成、交换造成了很大不便。x m l 的开发就是为了克服h t m l 的这些缺点，建 立种灵活的机制，它在以下几个领域正改变着w e b ： l 、简化了数据交换。因为不同组织很少就单一工具集形成标准，所以要使应 用程序相互交流需要进行大量工作。使用x m l ，每个实体可以创建单一的实用程 序，该实用程序将该实体的内部数据格式转换成x m l ，反之亦然。 2 、x m l 支持智能代码。因为可以使x m l 文档结构化以标识每个非常重要的 信息片段以及这些片段之间的关系，所以可以编写无需人工干预就能处理这些 x m l 文档的代码。 3 、x m l 支持智能搜索。尽管搜索引擎这些年在稳步改进，但从搜索中得到错 误的结果仍很常见。如果搜索包含名叫“c h i p ”的人的h t m l 页面，可能还会找 到有关功克力片、计算机芯片、木片以及许多其它无用但匹配的页面。搜索x m l 文 档查找包含文本c h i p 的 元素会给一个好得多的结果集。 随着x m i 数据的增多，如何对其进行高效地存储、索引和查询是非常重要的， 因此，出现了许多对x m l 数据的查询语言、索引结构、处理算法或专用系统。本 山东大学硕士学位论文 文从x m l 的基本概念入手，着重对当前x m l 数据查询的索引结构和处理方法进行 分析研究，并加以改进和优化，来进一步提高查询处理效率。 1 。2x m l 的基本语法 1 1 x m l ，称为可扩展标记语言，用户可以用来创建自己的标记，它是半结构化的， 即无规则或组织结构时常变化。h t m l 是为人设计的，即使不用浏览器查看如代码 卜1 的h t m l 文档，人也会知道那是某个人的邮政地址，但是机器不能做到。 t o m 14 0 1m a i ns t r e e t a n y t o w n ，n cl l1 2 9 ( 代码卜1 ) 尽管这个文档中的标记告诉浏览器如何显示该信息，但标记没有告诉浏览器 信息是什么，要显示h t m l ，浏览器只需遵循h t m l 文档中的指令将文档格式化， 但机器不知道这是地址。如考虑从该h t m l 文档中抽取邮政编码，有一个简易算 法：如果找到有两个 标记的段落，那么邮政编码就是第二个换行标记下面 第一个逗号之后的第二个词。尽管该算法对于这个示例起作用，但对于许多完全 有效的地址，该算法根本不起作用。即使可以编写算法来找出任何用h t m l 编写 的地址的邮政编码，但许多具有两个换行标记的段落根本不包含地址，即便有可 能编写算法来查看任意h t m l 段落并找出其中的任意邮政编码，也是极其困难的。 如用x m l 来实现上述例子，如代码卜2 所示。可以给文档中的标记赋予某种 含意。更重要的是，机器也容易处理这样的信息，只需通过找到 和 标记之间的内容，就可以从该文档中抽取邮政编码。 m r s m a r y 山东大学硕士学位论文 m c g o o n 1 4 0 1m a i ns t r e e t a n y t o w n n c 1 1 1 2 9 ( 代码卜2 ) 有三个通用术语用来描述x m l 文档的组成部分：标记、元素和属性。下面的 样本文档说明了这些术语：标记是左尖括号( ) 之间的文本。 有开始标记( 例如 ) 和结束标记( 例如 ) ；元素是开始标记、结 束标记以及位于二者之间的所有内容。如代码i - 2 中， 和 之间的部 分。 ) ( m l 文档必须包含在一个单一元素中。这个单一元素称为根元素，它包含文 档中所有文本和所有其它元素。在下面的代码卜3 中，x m l 文档包含在一个单一 元素 中。 h e l l o ，w o r l d ! ( 代码卜3 ) 在x m l 中，元素是区分大小写的。如果您试图用 标记结束 元 素，将会出错。x m l 文档中的属性必须有值，那些值必须用引号括起。如： 山东大学硕士学位论文 大多数x m l 文档以x m l 声明作为开始，它向解析器提供了关于文档的基本 信息，但它不是必需的，如果有，它一定在文档的开头。声明最多可以包含三个 名称一值对：v e r s i o n 是使用的x m l 版本，目前该值必须是1 o ；e n c o d i n g 是该 文档所使用的字符集；s t a n d a l o n e ( 可以是y e s 或n o ) 定义了是否可以在不读 取任何其它文件的隋况下处理该文档。例： r a d ia 1 0 0 0 0 ( 表l i 关系数据库中的产品列表) 嚣团 山东大学硕士学位论文 t v 2 0 0 0 0 0 c a r 3 0 0 0 0 0 0 ( 代码卜4 用x m l 表示的产品列表) ) ( m l 用于在公司之间交换信息，x m lw e b 是可供应用程序使用的一个大型数据 库，软件可以自动访问价格列表，提取价格数据，更新数据库中的信息。 1 4x m l 的伙伴标准 x m l 的价值在于它是一种标准标记语言，是一种可以在自己的环境中使用的 工具，w 3 c 已开发出一系列的标准来完善x m l ，这些标准通常被称为x m l 的伙伴标 准。 1 、x m l 的名称空间。x m l 的能力来自它的灵活性，数百万人可以定义自己的 标记来描述数据，利用名字空问可在一个全局命名系统中对元素进行定位。如表 示个人姓名的x m l 文档中包括表示个人尊称的 元素：一家网上书店， 创建了一个表示书名的 元素。这些都是合理的选择，但都用了相同的名 称创建元素，可以使用名称空间来分辨某个特定的 元素指的是人还是 书。首先要定义一个名称空间前缀，然后将它映射至一个特殊字符串。下面代码 i - 5 介绍如何定义这两个 元素的名称空间前缀： 山东大学硕士学位论文 m r s l o r do ft h er i n g s 在该例中，两个名称空间前缀是a d d r 和b o o k s 。为特定元素定义名称空间意 味着该元素的所有子元素都属于同一名称空间。第一个 元素属于a d d r 名称空间，因为其父元素 属于该名称空间。名称空间定义中的字符 串仅仅是字符串，它必须是唯一的，所以大多数名称空间定义成u r l 的形式。 2 、x m l 编程接口。这些接口为开发人员使用x m l 文档提供了一致的接口。 使用最广泛的a p i 有两种：文档对象模型( d o c u m e n to b j e c tm o d e l ) 和用于x m l 的简单a p i ( s i m p l ea p if o r ) ( m l ( s a x ) ) 。 ( 1 ) 文档对象模型d o m 为x m l 文档的已解析版本定义了一组接口。解析器 读入整个文档，然后构建一个驻留内存的树结构，程序代码就可以使用d o m 接口 来操作这个树结构，可以遍历树以了解原始文档包含了什么，可以删除树的几个 部分，还可以重新排列树和添加新的分支，等等。d o m 提供了一组丰富的功能， 可以用这些功能来解释和操作x m l 文档。 但d o m 存在一些不足之处。如：在构建整个文档驻留内存的树时，如果文档 很大，就会要求有极大的内存：d o m 创建表示原始文档中每个东西的对象，包括 元素、文本、属性和空格，如果只需关注原始文档的一小部分，那么创建那些永 远不被使用的对象是极其浪费的；d o m 解析器必须在代码取得控制权之前读取整 个文档。对于非常大的文档，这会引起显著的延迟。这些仅仅是由文档对象模型 的设计引起的问题，撇开这些问题，d o ma p i 是解析x m l 文档非常有用的方法。 ( 2 ) 用于x m l 的简单a p i ( s a x ) 的如下特征解决了d o m 的问题：s a x 解 析器向您的代码发送事件，当解析器发现元素开始、元素结束、文本、文档的开 始或结束等时，它会通知，帮助决定要创建什么类型的数据结构以保存来自这些 事件的数据，如果没有显式地保存来自某个事件的数据，它就被丢弃。s a x 解析 器根本不创建任何对象，它只是将事件传递给应用程序。当解析器发现文档开始、 元素开始和文本等时，代码会收到一个事件，应用程序可以立即开始生成结果而 不必一直等到整个文档被解析完毕。如果只查找文档中某些内容，代码一旦找到 所要找的东西就可以抛出一个异常，该异常会停止s a x 解析器，然后代码用它找 山东大学硕士学位论文 到的数据做它需要做的事情。 s a x 解析器也有些问题：s a x 事件是无状态的，当s a x 解析器在x m l 文档 中发现文本时，它就向代码发送一个事件，该事件仅仅给出发现的文本，它不告 诉什么元素包含那个文本；s a x 事件不是持久的，如果应用程序需要一个数据结 构来对x m l 文档建模，则必须自己编写那样的代码，如果需要从s a x 事件访问 数据，并且没有把那个数据存储在代码中，那么不得不再次解析该文档。 1 5 本文的主要工作 本文的主要工作体现在以下两个方面：一是在本文第四章介绍的“路径分解” 查询处理算法中，当查询路径很长时，需合并的中间结果集很多，计算量很大， 而不同的合并次序会导致不同的计算量，为此本文第五章基于动态规划的思想， 设计出具体算法，在进行中间结果集合并之前，算法可先求出该合并问题的最优 值，进而求出最优解，确定出最优合并次序，大大降低了结果集合并的计算量， 提高了查询处理效率。二是针对原算法在合并中间结果集时要进行大量“祖先后 代”关系的判断，文章基于关系运算提出了新的查询分解处理算法，主要思想是 将用规则路径表示的x m l 数据查询表达式进行分解，分解成为若干二元关系和一 个一元关系，使它们拥有一个共同的属性：对每个关系按先根顺序遍历x m l 文档 树，求出每个关系所拥有的元组，然后对这些关系按它们的共同属性进行自然连 接，在得到的最终关系中，据查询表达式中要求的内容，在相应的属性上作投影， 得到最终结果，此方法可避免“祖先后代”关系的大量判断，进一步优化了查询 处理。 第二章解析器和d o m 2 1 解析器 1 1 解析器是最基本也是最重要的x m l 工具，它是处于应用程序和x m l 文档之间 的软件组件其目标是把错综复杂的x m l 语法对开发人员屏蔽起来，每个x m l 应 用程序都包含解析器。x m l 文档可以是结构完整的或是合法的，结构完整的文档 要遵循语法规则，而合法的文档不仅要遵循语法规则，还要与相应的d t o 或模式 描述的结构保持一致。同样，解析器分为验证解析器和非验证解析器，它们都对 文档执行语法规则检查，但只有验证解析器会通过矾d 或模式对文档进行合法性 检查。 x 札程序由两个部分组成：解析器( 用于处理x m l 文件) 和应用程序( 通过 解析器对文件内容进行操作) 。如图2 1 ，虚线部分表示解析器和应用程序间的应 用程序编程接口或通信途径。 ( 图2 一l 删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 一l 的x m l 文档， 表示一个产品列表。 x b e ：p r o d u c tp r i c e = ” 2 3 ，0 0 ”) x h le d i t o r j 4 山东大学硕士学位论文 d t de d i t o r ( 代码2 - 1 ) ( 图2 - 2 建立对象树) 解析器读入x m l 文档，并逐渐建立与文档相匹配的对象树。如图2 2 所示， 当代码2 一l 被读入时，会识别出文档的顶层元素叫做p r o d u c t s ，将构造一个对象 来表示元素p r o d u c t s ；下面是一个p r o d u c t 元素，解析器生成另一个对象表示此 p r o d u c t 元素，并且将这两个对象连接起来，构建树型结构。下一步要识别p r i c e 属性，解析器为p r i e e 生成一个对象，把它加入正在构建的树中；在p r o d u c t 中 有一些文本，解析器会将文本转换为另一个对象，作为树中的一个文本节点。随 后解析器会转向处理另一个p r o d u c t 元素，此元素的读入会使树中增加更多的对 象，解析器的处理过程会一直持续，直至整个文档被读入后才结束。当解析器阅 读到文档的结尾时，它已在内存中建立了一个与文档的树结构相匹配的对象树。 2 。2 文档对象模型( d o m ) d o m 是x m l 的基础，x m l 文档具有称为节点的信息单元的层次结构，d o m 是描 述那些节点和节点间关系的方式，是一个定义对象的a p i ，这些对象出现在x m l 文档中以及用于访问和操纵这些对象的方法和特性中。 d o md o c u m e n t 是以层次结构组织起来的节点，或信息片段的集合。这种层 次结构允许开发者通过浏览树来查找特定信息。通常，分析结构需要在完成任何 工作之前装入整个文档并且装入层次结构。由于d o m 是基于信息的层次结构，因 此它被称为是基于树的。对于极其大的文档，装入整个文档并对该文档进行解析 山东大学硕士学位论文 会很慢且占用大量资源，可以用一些基于事件的模型，如s a x ，它是工作在数据 流之上，在数据流经过时对其进行处理。基于事件的a p i 消除了在内存中构建数 据树的需要，但它不允许开发者实际更改原始文档中的数据。另一方面，d o m 还 提供了一个a p i ，该a p i 允许开发者为创建应用程序而在树的任何地方添加、编 辑、移动或除去节点。d o m 路线图如下： ( 图2 - 3d o m 路线图) 解析器是设计用来分析文档并对信息做一些特定事情的软件应用程序。在 d o m 这种基于树的a p i 中，解析器在内存中构建数据树。d o ma p i 包含一些接口， 这些接口表示所有可以在x m l 文档中找到的不同类型的信息( 譬如，元素和文 本) 。如代码2 - 2 是表示商业系统定单的l 文件。包含以下几个基本部分： ( 1 ) x m l 声明：定义了该文件为x m l 文档，并指定编码，只要解析器理解 那个特定的编码，就能正确地读取该文档。 ( 2 ) d 0 c t y p e 声明：k m l 是人类与机器之间交换信息的一种便利方式，但对 于x m l ，要使其工作顺畅，还需要一些公共的词汇。这个可选的d o c t y p e 声明可 以用来指定一个文档o r d e r s d t d ，可用来与x m l 文档相比较以确保不会偏离或 丢失信息，用这种方式处理过的文档称为有效文档。 ( 3 ) 数据本身：x m l 文档中的数据必须包含在单一根元素中，如o r d e r s 元 素。 1 6 山东大学硕士学位论文 p r e m i u mc i n c h 4 9 0 0 1 2 5 1 2 2 2 p e n d i n g w i n t e rb l a n k e t ( 7 8i n c h ) 2 0 i o ( 代码2 2 ) 在d o m 中，使用x m l 信息意味着首先要将它分成多个节点。d o m 是一些节 点的集合，由于文档中可能包含有不同类型的信息，所以定义了几种不同类型的 节点。在创建x m l 文件的层次结构时，自然要产生概念上类似于下面结构的东西。 它是所包含数据的精确描述，而不是由d o m 所表示的数据的精确描述。这是因为 它表示元素，而不表示节点。如图2 - 4 。 ( 幽2 - 4 ) 山东大学硕士学位论文 事实上，元素只是一种类型的节点，节点是信息的容器。信息可以是其它元 素节点、文本节点、属性节点或其它类型的信息。下面图2 - 5 是代码2 - 2 更精确 的图形。 口：表示元素节点o ：表示文本节点：表示父母孩子关系 ( 图2 - 5 ) 矩形框表示元素节点，椭圆形表示文本节点。当一个节点包含另一个节点时， 那个节点被认为是这个节点的子节点。请注意，o r d e r s 元素不是只有两个子节点， 而是有五个子节点：两个o r d e r 元素以及这两个元素之问和周围的文本节点。即 使o r d e r 元素之问没有内容，这之间的空白组成一个文本节点。类似的，i t e m 有 七个子节点：n a m e 、p r i c e 、q t y 和这三个节点周围的四个文本节点。还要注意， 可能要考虑元素的内容，譬如，“p r e m i u mc i n c h ”实际是文本节点的内容，它是 n a m e 元素的子节点( 本图表省略了属性节