（计算机软件与理论专业论文）xpath查询模型研究.pdf

摘要 目前，随着x m l 技术的不断发展及其应用领域的不断扩展，越 来越多的数据开始用x m l 进行描述、存储和交换，x m l 数据流查 u 研究成为x m l 技术研究领域的热点。而用户垒询通常是用x p a t h 语言表乃。当x m l 流数据剑达时，查询处理系统根据用户输入的 x p a t h 查询表达式与x m l 数据流匹配，实时的返l 叫匹配结果。通常 情况下，系统需要处理大量来自用户x p a t h 查询，如何及时、高效的 将奄询结果返回给用户是x m l 查询研究的关键。 本文通过对x p a t h 查询表达式的分析，注意剑这样一个事实：多 个x p a t h 查询表达式具有一定程度上的相似性，它们可能具有相同的 谓词表达式项，如果能够减少这些相同的渭词表达式项的计算，就能 有效的提高查询效率。基于此，并结合x m l 流索引、路径查询等技 术，本文提出了一种基于流索引的x p a t h 查询渭词处理的新方法，并 设计和实现了利用该谓词处理方法来处理谓词的x p a t h 查询模型。 本文主要的工作和贡献如下： 1 、首先介绍了x m l 数据流台询在国内外的研究现状和x m l 的 相关技术，深入研究了h 寸下流行的几种x p a t h 查询模型，重点对基于 自动机的x p a t h 查询模型进行了剖析。 2 、通过对一种比较常用的谓词处理方法基于共享路径的谓 词处理力法的分析，提出了一种基于流索引的谓词处理方法。并给出 了该方法的基本思想，模型结构和渭词处理算法，介绍了谓词处理器 的处理机制，并提小了该谓词处理方法的优化措施。 3 、设计并实现了利 j 基于流索引的i 胃词处理办法来处理i 肖词表 达式的x p a t h 台询模型，分析了模犁的设计思路和模型框架。 4 、通过实验证明：基于流索引的x p a t h 查询模型能够有效的提 高奁询效率，适合于处理大文档和复另鼍的x p a t h 查询。 关键宇：x m l 数据流，x p a t h 查询，流索引，谓词表达式 a b s t r a c t a tp r e s e n t ，m o r ea n dm o r ed a t ah a v eb e e nd e s c r ib e d ，s t o r e d a n de x c h a n g e db yx m lw i t ht h ec o n s t a n td e v e l o p m e n to fx m l t e c h n o l o g ya n dt h ec o n t i n u o u se x t e n s i o no fi t sa p p l i c a t i o n s t h es t u d yo fx m ld a t af l o wq u e r yh a sb e c o m et h ef o c u so ft h e f i e l do i x m l t e c h n o l o g i c a ls t u d y m e a n w h il e ，t h e u s e r s q u e r i e sa r eu s u a ll ye x p r e s s e db yx p a t hl a n g u a g e w h e nt h ex m l d a t as t r e a ma r r i v e s ，t h eq u e r yp r o c e s s i n gs y s t e m ，a c c o r d i n gt o u s e r s in p u to fx p a t hq u e r ye x p r e s s i o nm a t c h i n gw i t ht h ex m l d a t as t r e a m ，r e t u r n st h em a t c hr e s u l t si nt i m e u n d e rn o r m a l ci r c u m s t a n c e s ，t h es y s t e mn e e d st oh a n d leal a r g en u m b e ro f x p a t hq u e r ie sf r o mu s e r s ：t h e r e f o r e ，h o wt og i v eb a c kt h eu s e r s t i m e l ya n de f f i c i e n tq u e r yr e s u l t si sac r i t i c a ls t u d yo fx m l q u e r le s t h i sp a p e r ，b yt h ea n a l y s i so ft h ex p a t hq u e r ye x p r e s s i o n ， n o t e st h isf a c tt h a tl o t so fx p a t hq u e r ye x p r e s si o n sh a v ea c e r t a i nd e g r e eo fs i m il a r it ya n d t h e ym a yh a v et h es a m e p r e d i c a t ee x p r e s s i o ni t e m s i fw ec a nr e d u c et h ec a l c u l a t i o n o ft h es a m ep r e d i c a t ee x p r e s s i o ni t e m s ，t h eq u e r ye f f i c i e n c y c a nb ee f f e c t i v e l yi m p r o v e d b a s e do nt h i sa n dc o m b i n e dw i t h x m ls t r e a mi n d e x ，p a t hq u e r yt e c h n i q u ea n ds oo n ，t h isp a p e r p r e s e n t sn e wm e t h o d sb a s e do nas t r e a mi n d e x b a s e dx p a t hq u e r y p r e d i c a r e s ：a n dd e s i g n sa n di m p l e m e n t s x p a t hq u e r ym o d e lt o d e a lw i t hp r e d i c a t eb yu s i n gt h ea p p r o a c ht od e a lw i t ht h e p r e d i c a t e t h em a i nc o n t r i b u t i o n sa sf o l l o w s ： i t h ep a p e rd e s c r ib e st h er e s e a r c hs t a t u so fx m ld a t as t r e a m q u e r y a t h o m ea n d a b r o a d ， a n di n t r o d u c e st h er e l a t e d t e c h n o l o g i e so fx m l ，a sw e lla si n d e p t hs t u d yo fs e v e r a l 川 p o p u l a rx p a t hq u e r ym o d e l a n dt h e p a p e re m p h a s iz e s o n a n a l y z i n gt h ea u t o m a t i cm a c h i n e b a s e dx p a t hq u e r ym o d e l 2 t h ep a p e rg i v e st h ea n a l y s i so fac o m m o na p p r o a c ht o p r e d i c a t ew h i c hi ss h a r e dp a t h b a s e d ，a n dp r o p o s e sas t r e a m i n d e x b a s e do ft h ep r e d i c a t ea p p r o a c h b e s i d e s ，i tg i v e sb a s i c i d e ao ft h ei n i t i a t i v ec o m p u t a t i o nm o d e l ，t h em o d e ls t r u c t u r e a n dt h e p r o c e s s i n ga l g o r i t h ma n di n t r o d u c e sp r e d i c a t e p r o c e s s o rh a n d li n gm e c h a n i s ma n dm e t h o do fo p t i m i z a t i o n 3 t h ep a p e rd e s i g n sa n di m p l e m e n t sx p a t hq u e r ym o d e lu s i n g s t r e a mi n d e x b a s e do ft h ep r e d i c a t ep r o c e s s i n ga p p r o a c ht od e a l w i t hp r e d i c a t ee x p r e s s i o n sa n da n a l y z e st h ed e s i g n i n gi d e a so f t h em o d ela n dm o d e1f r a m e w o r k 4 t h a tt h es t r e a mi n d e x b a s e dx p a t h q u e r ym o d e lc a n e f f e c t i v e l yi m p r o v et h eq u e r ye f f i c i e n c yh a sb e e np r o v e d t h r o u g he x p e r i m e n t s ，s u i t a b l et oh a n d l el a r g ed o c u m e n t sa n d c o m p l e xx p a t hq u e r i e s k e yw o r d s ：x m ld a t as t r e a m ，x p a t hq u e r y ，s t r e a mi n d e x ，p r e d i c a t e e x p r e s s l o n ： i v 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 黍丘九 驯口年s 月狮日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 研究生在校攻读学位期间论文工作的知识产权单位属湖南师范大学。 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密留。 ( 请在以上相应方框内打“”) 作者签名：琴笠叉 刷醛备纠别事 日期：幻p 年工月z 中日 e l 期：洌口年岁月z 写日“ x p a t h 查询模砸研究 1 绪论 1 1 背景介绍 近年米，随着i n t e r n e t 的迅速发展和w e b 的广泛应h ，社会正逐 步迈向信息化。在互联网上，各种信息大量 f i j 现，海最信息呈现爆炸 式的增长。这螳信息形式各异，从其数据载体的结构特征角度分析， 基本分为二三类：无结构化数据信息；半结构化数据信息；结构化数据信 息。其中，半结构化数据具有不规则、多变的结构特征，在互联网存 在最为广泛。可扩展标记语言x m l 是半结构化数据常用的一种表现 形式。随着半结构化数据信息目益膨胀，x m l 己逐渐成为网上数据 表达和数据交换的标准。 x m l l l l ，或称为可扩展标记语言( e x t e n s i b l em a r k u pl a n g u a g e ) ， 是一种叫以用来创建自己的标记的标记语言。它由万维网协会( w 3 c ) 创建，用米克服h t m l ( 即超文本标记语言( h y p e r t e x tm a r k u p l a n g u a g e ) ，它是所有网贞的基础) 的局限。和h t m l 一样，x m l 基于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 p l a n g u a g e ) ，它是s g m l 的一个精简子集，是一种简单、灵活的文 本格式。相比其他标记语言，x m l 具有自描述性、可扩展性、易用 性和异构的特点。由于x m l 具备这些特点，使得它成为口前互联网 上通用数据的表示和交换格式。 近廿鼍年来，一类数据密集的应用得剑广泛的认同，这些应用的数 据以实时的，快速的数据流形式持续剑达，适。南：刚数据流【2 l 建模。这 些应刖的实例包括金融服务、网络豁控、电信数据管理、4 - # ：5 检测等。 随着x m l 成为网_ ：数据表达和交换的标准，j 泛的j 近j 目予各种j 衄胴 和信息源之问的数据交换，所以，x m l 数据流成为了这种流数据的 主要形式。这些实时到达的x m l 流中包含大量的信息，并需要根据 硕+ 学位论文 不同用户的需求从这些信息中过滤、抽取出各个用户关注的信息。因 此x m l 数据流的高效查询成了目前业界研究的热点。 由于x m l 流数据具有在线实时的、持久的到达和不能改变数据 到达j l l 页i - y 的特点，所以在x m l 数据流处理系统中，不呵能将所有到 达的流数据存储剑本地后进行查询。因此对于x m l 数据流查询算法 的设计必须满足流数据单遍处理的特点。 1 9 9 9 年1 1 月，制定x m l 技术规范标准的w 3 c 发布了x p a t h l 0 t 3 】 推荐标准，它提供了关于路径导航( p a t hn a v i g a t i o n ) ，节点定位( n o d e l o c a t i o n ) ，渭词选择等方面精确的规范，它最主要的目的是为了在 x m l l 0 或x m l l 1 文档节点树中定位节点。x p a t h 采用类似于计算 机文件系统文件路径的方式来定位x m l 文档中的x m l 元素。路径 使用强调节点之间的层次关系的符号来表达节点模式。为了更加精确 的查找用户所需要的数据，我们给x p a t h 查询语句增加了许多限定条 件，我们把这些限定条件称为谓词，谓词的引入使得包含谓词的x p a t h 查询不再足单枝查询，大大增加了查询处理的难度，如何高效的处理 谓词是提高金询效率的关键因素。 x m l 流数据处理系统通常运行在w e b 上，其上的用户会迅速增 加到十万、百万级的数量。用户查询通常用x p a t h 语言表示。由于一 个用户可以提交若干查询，查询的数量十分巨大。x m l 流数据处理 研究的一个关键挑战足如何同时有效处理大量来自用户的查询并及 时的将结果返匝i 给用户。 1 2 国内外研究现状 口前，x m l 数据流的x p a t h 查询处理技术在国内外已经取得了 许多研究成果：如x f i l t e r i4 1 、y f i l t e r l 5 1 、x t r i e 7 1 、x p u s h 9 】等。 对于x m l 流的x p a t h 查询处理，使j f j 最酱遍的足基于自动机f 6 】 的方法，x f i l t e r 、y f i l t e r 、x t r i e 、x p u s h 等都足基于自动机的典型代 表。 ， x p a t h 奔询模型研究 m e h m e ta l t l n e l 提出了x f i l t e r 处理方法，首次将基于有限状态自 动机( f i n i t es t a t em a c h i n e ，简称f s m ) 的方法引入x m l 数据流的过滤处 理，对于每一个x p a t h 查询表达式，x f i l t e r 建立一个有限状态机，实 现简单x p a t h 路径表达式的处理。由于x f i l t e r 对每一个路径查询使 用一个单独的有限状态自动机，并在文档处理的过程中，同时运行所有 的有限状念自动机，所以，x f i l t e r 没有考虑相似查询的冗余情况并没 有减少冗余查询的处理。 y f i l t e r 在x f i l t e r 基础上进行了改进，具有强大的x p a t h 盒询能 力，它将所有的x p a t h 金询表达式合并成一个单独的非确定有限自动 机( n f a ) ，并共享所有查询的公共前缀。并将t w i g p a t t e r n l 8 】视作嵌套 路径表达式，并使用查询分解进行处理。y f i l t e r 能够减少不同查询处 理中的重复计算，但它不能单遍处理所有查询，处理人文档时性能明 显下降。 x t r i e 是对基于n f a 自动机的查询处理的一种扩展，引入了索引 机制，用来提取多个x p a t h 查询表达式中公共路径。x t r i e 支持有序 的和无序的x m l 文档的匹配，适应于处理复杂的x p a t h 查询表达式。 上述方法本质上是基于n f a ，即在查询处理系统运行过程中， 处理机内部同时运行了多个状态，随着x p a t h 查询数目的增加，执行 效率会降低。为了解决这个问题，提出了另外一类x m l 数据流的查 询处理方法，即用基于确定自动机( d f a ) 来构造的。l a z yd f a n 】， x p u s h 9 】和目前o n i z u k a 1 0 】( 一种l a z yd f a 改进的方法) 进行的研究 鄢足基于确定自动机的。 l a z yd f a 力法中的状念是在运行时才产生的，即只有在接受j ， ；与i ，j - 输入后需要进行一次转移进入新的状态的时候才7 e 成。l a z y d f a 人人减少了状念数目凶而提高了效率。 x p u s h 是对l a z yd f a 方法的扩展，解决了l a z yd f a 处理包含 嵌套路径的复杂x p a t h 查询时处理效率f 、= 高的问题。理论上，x p u s h 硕+ 学位论文 在处理x p a t h 查询表达式时具有恒定的处理时间，提高了系统的查询 效率，但是需要消耗大量的存储空间。 其他处理x m l 流的方法主要有基于索引的方法1 2 2 1 、基于b l o o m f i l t e r 2 3 1 的方法以及f i s t 2 5 】方法。基于自动机的x p a t h 查询处理方法 的一个缺点是：构造自动机的过程中会增加状态的数e j ，尤其在x p a t h 查询表达式中包含谓词或者x p a t h 查询数目非常大的。情况下。基于索 引机制的x p a t h 查询处理方法通过对x m l 数据流建立索引，能够在 匹配过程中忽略掉那些不符合条件的数据，从而能够提高查询效率。 但是对x m l 数据流建立索引机制会需要额外的存储空间丌销。 1 3 本文所做的工作 本文在大量前人研究的基础上，针对x m l 数据流的特点，提出 了一种基于流索引的x p a t h 查询谓词处理方法，并设计和实现了利用 该谓词处理方法的x p a t h 查询模型，主要工作如下： 1 、通过对x m l 特性的研究，给出了x m l 数据流的解析模型。 介绍了x m l 数据流的两种查询规范：x p a t h ，x q u e r y 。 2 、深入研究了时下流行的j - l 静t , x p a t h 台询模型，分析了各模型 的优势和缺点。 3 、提出了一种基于流索引的x p a t h 查询谓词处理方法，并给出 了该种谓词处理方法的基本思想，模型结构和模型算法，介绍了渭词 处理器的处理机制和该方法的优化措施。 4 、设计并实现了应用基于流索引的渭涮处理疗法的x p a t h 奁询 模型，分析j ，模型的设计思路和模型框架，重点介绍了流索引的构造 和对x p a t h 定位步的处理。 5 、实验表明该x p a t h 查询模型能够有效的提高查询效率，尤其 适合于处理大的x m l 文档和复杂的x p a t h 鱼询。 x p a t h 夯询模型研究 1 4 本文的组织框架 本文共分为六章 第，一章绪论介绍了研究的背景、国内外研究现状、本文所作 工作和本文的t l t g t 框架。 第二章x m l 数据流及其查询规范介绍x m l 及x m l 数据流 的相关知识以及x p a t h 奄询规范，分析了x p a t h 表达式中谓词处理对 查询效率的影响。 第三章x p a t h 查询处理模型介绍了x m l 数据流x p a t h 查询处 理的常见方法及其存在的问题，主要讨沦了基于自动机的x p a t h 查询 处理模型。 第四章x p a t h 查询渭词处理本章和下一章是本文的重点。本 章介绍了一科- 现有的渭词处理方法，分析的该方法的优点和缺点。提 出了一种基于流索引的谓词处理方法，并详细介绍了该方法的基本思 赤目 j o 笫五章基于流索引的x p a t h 查询模型的 殳计与实现本章和上 一章是今文的重点。本章设计并实现了种x p a t h 查询模型，并给出 了该模型的模型结构和设计思路。并通过实验证明了该x p a t h 查询模 型能有效的提高x p a t h 查询效率。 第六章总结与展望，总结全文，指全文研究成果及后续工 作。 最后是参考文献和致谢。 x p a t h 布询模砸研究 2 1x m l 2 x m l 数据流及查询规范 x m l 是一利t 较新的标记语言，但它基于一种成熟的标记语言， 叫做标准通h j 标记语言( s g m l ) ，并且是它的子集。w w w 的h t m l ( h y p e r t e x tm a r k u pl a n g u a g e ，超文本标记语言) 语言也是基于s g m l 的，实际上它是s g m l 语言的一种应用。所有的这些标记i 旨言都是 表达元数据的，但s g m l 和x m l 可以被进一步看做是元语言，因为 它们可以被用来产生新的元数据语言。正如h t m l 是用s g m l 来表 示的，x h t m l 和其他的语言会用x m l 来表示。但x m l 更加优于 s g m l ，因为x m l 掌握了s g m l 的扩展性、文件自我描述特性以及 强大的文件结构化功能，但摒除了s g m l 过于庞大复杂以及不易普 及化的缺点。这正是x m l 正在被越来越广泛的使用的主要原因。 x m l 数据足一种树形结构，它可以被看作是一个带有根结点的 有序标签树。在x m l 树中，每一个结点对应了一个文档结构元素( 包 括元素、属性、文本，注释和处理指令) 或者元素值。结点与结点的 边对应了元素之间的父子，祖孙关系。在文档中，这种层次嵌套关系 可以由元素起始标签( s t a r t t a g e n d t a g ) 的包含关系来确定。 例如，以下一个b o o k x m l 文档的例子，它的x m l 树形结构对应 于图2 1 。在该x m l 树中，根结点r o o t 有两个标签值为b o o k 的子元 素，该子元素分别具有n a m e ，t i t l e ，v e r s i o n s ，a d d r e s s 子元素。其中， r o o t b o o k 是父子关系，r o o t n a m e ，r o o t t i t l e ，r o o t v e r s i o n s ，r o o t a d d r e s s 是祖孙关系结点。 x m l x m l 可扩展语言 硕十学位论文 1 o 中国广东 j a v a t h i n ki nj a v a 3 o 中国湖南 n a m e x m l 图2 - 1x m l 文档树 、- a d d r e s s 一 u 中国湖南 x m l 技术体系并不仪仪只是x m l 标记语言，它还包括了许多 相关的技术规范，下而讲述最常刖的几个技术规范： 1 、x m l 路径语言( x m l p a t hl a n g u a g e ，x p a t h ) ：x p a t h 是一种合 询语言，刚于对x m l 数据对象的特定部分进行编址。这一语言把 x m l 数据作为书点内部的抽象层次树结构的路径和q ，l 前的l 卜文节 点米处理，而不足使j j 肤浅的标记和属性语法。x p a t h 的编址能力也 意味着它在x m l 数据中的模式匹配能力，这就提供了一种查询数据 的简单方法。这是本文研究的主要技术。 8 x p a t h 查询模型研究 2 、文档类型定义( d t d ) ：d t d 用于验证x m l 数据的有效性， 它规定了x m l 文档。| j 的元素、属性、文本之问的关系。 3 、x m l 模j = 定义( x m ls c h e m a ) ：x m ls c h e m a 规范定义了描述 x m l 文档所要j j 到的x m l 词汇表。与d t d 不l 司的是，基于x m l s c h e m a 的定义主要基于类掣，而非基于标签名称。这就使得x m l s c h e m a 对编程语言和数据库等现存系统有更高的适应性。与d t d 的 另一个不i j 的是：x m ls c h e m a 支持名称空间，而且可以说是以名称 空间为中心。与d t d 的第三个不同点是：x m ls c h e m a 本身也是x m l 文档，可以刚与解析和生成它所描述的x m l 文档相l i 寸的技术来解析 和生成。 4 、x s l t ( x s l t r a n s f o r m a t i o n ，x s l 转换) ：x s l t 规范定义了一种 基于x m l 的语言，用于表达从一类x m l 文档剑另一类x m l 文档 的转换规则。x s l t 文档可作为一种通用语言，用于表达从一种 s c h e m a 类型到另一个s c h e m a 类型的转换。实际上，可以将使用x s l t 文档相像为任意x m i 。转换引擎的一种输入形式。x s l t 的优势在于 将一种基于x m l 的表示映射到另一种基于x m l 的表示。 2 2 x m l 数据流 设i 为任意时刻，a i 表示在i 时刻数据流中的元素，则数据流可 以表示为：d a t a s t r e a m = a i , a ，。数据流与传统的数据类型 不同，传统的数据可以随机读取所需要的任意数据，而w e b 上的流 数扔：的剑达州i 、司足不可预测的，数据的次序是相对独市的，我们不可 能把所有的数据都存储剑本地，然后进行处理。 而x m l 数据止是以这种数据流的形j = 弋在w e b 卜f 簟输的，基于数 据流的特点，对x m l 流数据的处理需要满足以卜要求【1 2 】： ( 1 ) 凶为x m l 数据流的到达顺序是独立于系统的，所以对x m l 的每一个文档元素节点只能被访问一次，臣r l ，r _ 1 访问x m l 文档一次就 必须完成对x m l 的解析和查询处理工作； q 硕十学位论文 ( 2 ) 通常w e b 上传输的x m l 数据是非常庞大的，我们不可能将 所有的数据暂存到本地内存窄问后才进行处理，所以对x m l 畲询处 理的算法必须具有尽可能少的空间复杂度。 ( 3 ) x m l 数据流的剑达是快速的、实时的，所以对每个x m l 元 素节点的处理要有很高的效率。 当x m l 以流的形式进行处理时，在逻辑上实际是以先序遍历的 形式对x m l 树中的结点进行访问，即x m l 流可以看作一系列连续 且有序的结点x o x l x n 组成的序列。x m l 流的处理过程就是对这些 序列结点的分析。 定义2 1 给定x m l 树r ，对丁中结点进行先序遍历所得剑的结 点序列为x m l 树的流表达【12 1 。记作s t - - ( x o x l x n ) ，x i t ，基中， 序列x 0 确x n 实际上就是x m l 流元素的访问顺序。 例如，对于x m l 文档b o o k x m l ，与其对应的x m l 树如上图2 - 1 所示，根据流表达的定义2 1 ，可得b o o k x m l 的流表达为： s t =( x o x l x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 1 1 x 1 2 x 1 3 x 1 4 x 1 5 x 1 6 x 1 7 x 1 8 ) 其中x o = e l e m e n t ( r o o t ) ，x l = e l e m e n t ( b o o k ) ，x 2 = e l e m e n t ( n a m e ) ， x 3 = t e x t ( x m l ) ，x 4 = e l e m e n t ( t i t l e ) ，x 5 = t e x t ( x m l 可扩展语言) ， x 6 = e l e m e n t ( v e r s i o n ) ，x 7 = t e x t ( 1 o ) ，x 8 = e l e m e n t ( a d d r e s s ) ，x 9 = t e x t ( r 辛 国广东) ，x l o = e l e m e n t ( b o o k ) ，x 1 l = e l e m e n t ( n a m e ) ，x 1 2 = t e x t ( j a v a ) ， x 1 3 = e l e m e n t ( t i t l e ) ，x 1 4 = t e x t ( t h i n k i n j a v a ) ，x 1 5 = e l e m e n t ( v e r s i o n ) ， x 1 6 = t e x t ( 3 o ) ，x 1 7 = e l e m e n t ( a d d r e s s ) ，x 1 8 = t e x t ( 中国湖南) 。 2 3 x m l 解析模型 x m l 解析模型的作用足提取x m l 文档数据集的抽象信息并且 将抽象信息投影剑个对象模型l ，该对象模型允许程序员根据扣i 象 信息项工作，而不足根据x m l 串行化格式的尖括号和字符引刚来工 作。常用的x m l 解析模型有两种，分别为s a x ( s i m p l ea p if o rx m l ， 用于x m l 的简单a p i ) 和d o m ( d o c u m e n to b j e c tm o d e l ，文档对象 1 0 x p a t h 查询模型研究 模型) 。 d o m 是一种与平台和语言无关的界面，它定义了一组对象类型 及其性质，并提供操作这些对象构成的树的方法。程序和脚本可以利 用此界面访问和更新x m l 文档。d o m 在解析x m l 文档之前会先将 整个x m l 文档载入剑内存中构建x m l 树，然后才能进行金询处理， 因而它支持抽象x m l 文档的内存内遍历、导航和修改。但是由于要 载入整个x m l 文档到内存中，所以对于大x m l 文档不适合采用 d o m 解析模型。 d o m 是基于树的力法，与此相反，s a x 是基于事件的模哩。就 是说，如果你挑选了一些x m l 数据并用一个基于s a x 的解析器解 析它，该解析器将在遇剑文档的各部分及其值时生成事件。对这止嗨事 件的分析通常足以达到应用程序搜索x m l 文档，寻找所需值或作为 适配器取出x m l 文档的内容并与数据库记录一致的目标。 s a x 处理一般包括以下几步【1 3 】： ，1 ) 创建事件处理程序。 ( 2 ) 创建s a x 解析器。 ( 3 ) 将事件处理程序分配给解析器。 ( 4 ) 对文档进行解析，将每个事件发送给处理程序。 回到2 1 节所示的x m l 文档b o o k x m l 的例子，运行一个s a x 兼容的解析器将产生如下事件流： s t a r td o c u m e n t s t a r ie l e m e n t ：r o o t s t a r te l e m e n t ：b o o k s t a r te l e m e n t ： n a m e c h a r a c t e r s ：x m l e n de l e m e n t ：n a m e s t a r te l e m e n t ：t i t l e 硕一 ：学何论文 c h a r a c t e r s ：x m l 可扩展语言 e n de l e m e n t ：t i t l e s t a r te l e m e n t ：v e r s i o n s c h a r a c t e r s ：1 0 e n de l e m e n t ：v e r s i o n s s t a r te l e m e n t ：a d d r e s s c h a r a c t e r s ：中国广东 e n de l e m e n t ：a d d r e s s e n de l e m e n t ：b o o k e n dd o c u m e n t 其中，s t a r td o c u m e n t ，s t a r te l e m e n t ，c h a r a c t e r ，e n de l e m e n t ， e n dd o c u m e n t 都是s a x 解析模型常用的事件。 从上分析可看出，d o m 和s a x 是两种完全不同的x m l 数据流 解析方法，我们可以从以下几点来分析两种方法的区别： ( 1 ) d o m 将整个x m l 文档存入内存中构造x m l 树，l 大l 此处理 系统可以随机的访问x m l 文档中的任意元素节点，而s a x 是基于 事件的，对每一个元素节点只做一次处理，不会在内存中保留整个 x m l 文档的信息。 ( 2 ) 对于大的x m l 文档的处理，如果采用d o m 解析，把整个 x m l 文档载入到内存中会消耗大量的内存资源，降低系统处理效率， i f i j 采用s a x 解析时不需要将整个x m l 文档载入到内存窄问一 i ，而 是按照事件流的线性序列处理数据。甚至当处理条件得到满足时， s a x 小需要解析整个文档就口j 停止解析。所以，当x m l 文档很人时， 采用s a x 解析更加合理和高效。 在本文中，因为处理的是人量的x m l 数据流，凶而我们选择s a x 作为x m l 文档的解析模型。 x p a t h 奇啕模型研究 2 4 x m l 查询规范 x m l 数据流的查询在x m l 流处理中具有非常重要的地位，目 前常见的x m l 奁询规范- 仃x s l t l l 4 、x m l q l l l 5 1 、x o u e r y j 6 】、x q l l l 7 】 及x p a t h 等，所有贪询语法皆以路径表示法为基础，在奉节中，我们 将介绍最常用的两种x m l 查询规范：x p a t h ，x o u e r y 。 x p a t h 足w 3 c 批准的对x m l 文档子集寻址的语言，它支持用于 标识单个文档内子集的文档内表达式。x p a t h 语法非常类似于用于遍 历文件系统或其他层次结构的语法。通过文件系统定义的语法，可以 找到我们所需要的文件；同样，通过x p a t h 定义的语法，可以定位我 们所需要查找的元素1 了点。x p a t h 基于x m i 。的树状结构，提供在数 据结构树中找寻节，l 、i i 的能力。 x p a t h 定义了7 种1 ，点类型，分别是：根节点、元素肖点、属性 节点、文本节点、处理指令节点、注释节点、名称空问节点。它们都 可以成为x p a t h 树的一部分。 以下面p l a y x m l 文档为例： s t r a t t e l e l e sp a u l 1 硕 ：学何论文 该文档包括了x p a t h 定义的7 中节点类型。其中，g u i t a r s 为根节 点，t y p e = e l e c t r i c 为属性一h i j - 烈。，g u i t a r 为元素节点。 最常见的x p a t h 表达式是路径表达式( x p a t h 这一名称的来源) 。 路径表达式是从一个x m l 节点( 当前的上下文节点) 到另一个节点、 或一组节点的书而步骤顺序。这些步骤称为定位步，每一个定位步有 三个构成成分： ( 1 ) 轴描述：朋来表示节点之间的关系； ( 2 ) 节点测试：用以指定节点类型和定位步所选择的节点的扩展 名； ( 3 ) 零个或多个谓词：可以用来对任意的x p a t h 表达式进一步提炼 定位步所选定的节点的集合。 定位步的第一部分是轴捕述，x p a t h 定义了几种相对于上下文节 点的节点关系，这种关系引用的节点集称为节点轴，其中最常用的节 点轴为：“”，表示选耳) ( 根一1 了点；“”，表示选取文档中所有符合条件 的节点；“”，表示选取当i 仃节点；“，表示选取当前节点的父节点； “ “，表示选取当前节点的属忖：节点。 在如下表格2 - 1 中，是针对p l a y x m l 文档的一些典型的x p a t h 表 达式及其表示的结果： 表2 2x p a t h 路径表达式示例 表达式结果 i t y p e选取所彳j t y p e 属性 m o d e l选取文档t - 的所有m o d e l 元素 g u i t a r m o d e l选取g u i t a rl l l 的所有m o d e l 子元素 g u i t a r选取g u i t a r 元素的根节点 g u i t a r m o d e l选取文档r f l 所有处g u i t a r 节点下的m o d e l 元素 g u i t a r 选取g u i t a r 元素的所有子节点 x p a t h 杏啕模弛研究 定位步的第二部分是节点测试，是定位步中唯一必选的部分，它 由x p a t h 查询前进中要选择得到的一系列节点组成，包括特定节点名 或者更一般的表达式。 定位步的第三部分是谓词，谓词是一个x p a t h 表达式，用于进 一步筛选定位轴和1 了点溯0 试所标识的常点集，一般出现在：箝点溯0 试后 的方括号中。谓词表达式计算结果为数值、布尔值或节点集，当所有 计算完成之后，谓词表达式的结果最终会转化成一个布尔表达式。非 布尔值形式的结果按如下方式进行转化： ( 1 ) 数字与上下文节点列表中的节点位置进行比较。如果匹配， 则结果为t r u e ，否则结果为f l a s e 。 ( 2 ) 空节点集合为f l a s e ，所有其他节点集合为t r u e 。 ( 3 ) 0 长度的字符串为f a l s e ，所有其他字符串为t r u e 。 对于上下文节点列表中的每个节点，将计算谓词表达式。把表达 式最终求值为f l a s e 的每个节点从节点集中去掉。因此，只有那些 满足谓词表达式的1 了点得以保留在节点集中。 如下表2 2 中，是针对p l a y x m l 文档的一些典型的含有i 胃词的 x p a t h 表达式及其表示的结果： 谓词出现使路径表达式在选择节点或者节点集的时候加上了限 制条件，更加有效的精确了盒询条件。虽然谓词并不是一个x p a t h 表 达式必需的内容，f 咀是随着现在x m l 数据的巨型化以及用户对金询 的精确化要求，大部分x p a t h 表达式都会包含渭词。 在x p a t h 标准f 3 l 【| l ，i 胃词操作的实质是对查询的 _ f l 问结果进行过 滤，包含谓训的x p a t h 表达j = 不再足线性的，由于渭词操作在每次对 当前节点集进行过滤时都要执行，【大i 此如何处理表达式中的诮训足影 响查询时间空问复杂皮的一个关键l 大i 素1 1 8 1 。x p a t h ，l ，i 肖刊通常订三种 形式：元素位置，属性比较和分支选择，而分支选择r - 每个分支由前 两种形式组成。 硕十学位论文 表2 2x p a t h 表达式中使用谓词示例 表达式结果 选取g u i t a r s 节点下的所有包 含属性t y p e 等于e l e c t r i c 的 g u i t a r s g u i t a r t y