（计算机软件与理论专业论文）基于bloom+filter的路径表达式查询处理.pdf

中文摘要 近年来，x m l 语言已经成为了互联网上数据表示和交换事实上的标准。随着 w e b 服务和个性化信息订阅等应用的蓬勃发展，越来越多的信息以x m l 的格式 通过网络被发布和交换。在这些应用中，x m l 数据以数据流的形式不断地快速到 达，而针对x m l 数据的查询是大量的路径表达式，传统的查询处理技术在性能 上已经不能够满足应用的需求。在x m l 数据流上对大量的路径表达式进行查询 处理是科研技术人员所面临的一个新的挑战。 本文围绕x m l 数据流的查询处理问题展开研究工作，分别探讨了针对简单 路径表达式和复杂路径表达式的查询处理技术，提出了新的处理方法，并通过实 验验证了所提出方法的有效性和高效性。同时，本文就x m l 数据流处理引擎 的设计进行了探讨，并实现了一个原型系统。论文的主要贡献可以总结为如下几 点： 本文首先提出了将b l o o mf i l t e r 结构应用于解决x m l 数据流过滤问题的方 法，该方法可以有效地支持对简单路径表达式中的通配符”号和后代轴 “”的处理。同时本文设计了前缀过滤的方法，用于减少解析过程中所生 成候选路径的数量，提高过滤处理的性能。详尽的对比实验表明，本文提 出的方法在创建路由表时的性能和所创建路由表的大小两个方面明显优于 已有的处理方法。同时，在查询集很大并且x m l 文档深度相对较小的情况 下，本文提出的方法在过滤性能上也要优于已有的方法。 本文提出了将包含有分支结构的复杂路径表达式分解成一组简单路径表达 式，在对简单路径表达式进行过滤处理的基础上，实现对复杂路径表达式进 行查询处理的方法。与已有的方法不同，本文所提出的方法以简单路径过滤 引擎输出的查询字符串流作为输入，可以支持对元素内容约束的处理，同时 可以以连续查询( c o n t i n u o u sq u e r i e s ) 的方式实现对复杂路径表达式的查询处 理。本文通过实验将所提出的处理方法与已有方法进行了对比，证明该方法 在对复杂路径表达式的查询处理上具有较好的性能。 本文在简单路径表达式和复杂路径表达式查询处理技术的研究基础之 上，设计和实现了一个x m l 数据流处理引擎一一x s t rf x m ls t r e a m p r o c e s s i n ge n g i n e ) 原型系统，并对该系统的实现进行了介绍。x s t r 系统 可以被作为中间件应用于针对x m l 数据流进行处理的应用系统中。 综上所述，本文就x m l 数据流的查询处理技术进行了深入的探讨和研究， 提出了不同于已有方法的新的技术和方法，并通过实验对所提方法的有效性进行 了验证。本文的研究工作，促进了x m l 查询处理技术的发展，具有现实的应用 价值。 关键词：x m l 数据流、路径表达式、查询处理、连续查询 分类号：t p 3 1 1 1 1 a b s t r a c t i nt h ep a s ts e v e r a ly e a r s ，x m lh a sb e e nt h ed e 如c t os t a n d a r df o rd a t ar e p r e - s e n t a t i o na n de x c h a n g eo i lt h ew e b i ti sw i d e l ya p p l i e di nt h ee m e r g i n ga p p l i c a t i o n s y s t e m s s u c h 柏w e bs e r v i c e sa n dp e r s o n a l i z e dc o n t e n td e l i v e r y i nt h e s ea p p l i c a ，- t i o n s ，p l e n t yo fp a t he x p r e s s i o n sa r ep r o c e s s e da g a i n s tx m ld o c u m e n t st h a ta r r i v e r a p i d l yi ns t r e a mf o r m e f f i c i e n tq u e r yp r o c e s s i n go nx m l s t r e a mh a sb e e nav e r y i m p o r t a n tr e s e a r c hc h a l l e n g e i nt h i sd i s s e r t a t i o n w ef o c u so nt h er e s e a r c hr e l a t e dt oq u e r yp r o c e s s i n go n x m ls t r e a m s o m en o v e lm e t h o d sa r ep r o p o s e df o rt h ep r o c e s s i n go fs i m p l ep a t h e x p r e s s i o n sa n db r a n c h e dp a t he x p r e s s i o n sr e s p e c t i v e l y t h ep e r f o r m a n c eo ft h e s e m e t h o d sa r ee v a l u a t e da c c o r d i n gt oe x p e r i m e n t s i np a r t i c u l a r ，w ei m p l e m e n ta x m ls t r e a mp r o c e s s i n gp r o t o t y p es y s t e m t h en o v e l t ya n dc o n t r i b u t i o n so ft h i s d i s s e r t a t i o nc a l lb es u m m a r i z e da sf o l l o w i n g ： w e p r o p o s ean o v e lm e t h o df o rx m l s t r e a mf i l t e r i n g w h i c hu s e 2b l o o mf i l t e r s r e p r e s e n t i n gs i m p l ep a t he x p r e s s i o n s t h i sm e t h o ds u p p o r t st h ee f f i c i e n tp r o - c e s s i n go fw i l d c a r dc h a r a c t e ra n dd e s c e n d a n ta x i so fs i m p l ep a t he x p r e s s i o n s t oi m p r o v et h ef i l t e r i n gp e r f o r m a n c e ，w ei n t r o d u c ean e wd a t as t r u c t u r e ，p r e - f i xf i l t e r s ，t od e c r e a s et h en u m b e ro fc a n d i d a t ep a t h s e x p e r i m e n t ss h o wt h a t o u rb l o o mf i l t e r b a s e dm e t h o dt a k e sl e s st i m et ob u i l dr o u t i n gt a b l et h a ne x i s t - i n ga u t o m a t o n - b a s em e t h o d a n do u rb l o o mf i l t e r - b a s e dm e t h o dh a sag o o d p e r f o r m a n c ew i t ha c c e p t a b l ef a l s ep o s i t i v ew h e nf i l t e r i n gx m ld o c u m e n t so f r e l a t i v e l ys m a l ld e p t hw i t hm i l l i o n so fp a t hq u e r i e s m w ep r o p o s ean o v e lm e t h o df o rb r a n c h e dp a t he x p r e s s i o n sp r o c e s s i n go nx m l s t r e a m ，w h i c hd e c o m p o s e sa l lb r a n c h e dp a t he x p r e s s i o n si n t os i m p l ep a t he x - p r e s s i o n sa n de v a l u a t e st h eb r a n c h e dq u e r i e sb a s e do nt h eo u t p u to fs i r e - p l ep a t he x p r e s s i o n sf i l t e r i n g t h i sm e t h o ds u p p o r t st h ee v a l u a t i o no fv a l u e p r e d i c a t e sa n dp r o c e s s e sb r a n c h e dp a t he x p r e s s i o n si nas t r e a mf a s h i o n e x - p e r i m e n t a lr e s u l t sc l e a r i yc o n f i r mt h a tt h i ss t r e a m - b a s e dm e t h o dh a sb e t t e r p e r f o r m a n c et h a ne x i s t i n gs t o r e b a s e da p p r o a c h w ep r e s e n tt h ed e s i g na n di m p l e m e n t a t i o no fx s t r ap r o t o t y p es y s t e mf o r x m ls t r e a mp r o c e s s i n g ad e t m l e da r c h i t e c t u r a ld e s c r i p t i o no ft h es y s t e m i sp r o v i d e d ，a n dav a r i e t yo fi s s u e si ni m p l e m e n t a t i o na r ed i s c u s s e d ，x s t r s y s t e mc o u l dw o r k 鹪m i d d l e w a r ec o m p o n e n ti nx m ls t r e a ma p p l i c a t i o n s i nc o n c l u s i o n ，w es t u d yt h ep r o b l e mo fp a t he x p r e s s i o nq u e r yp r o c e s s i n go n x m ls t r e a n l ，a n dp r e s e n tn e wm e t h o d sd i f f e r e n tw i t he x i s t i n ga p p r o a c h e s t h e p e r f o r m a n c eo fp r o p o s e dm e t h o d si se v a l u a t e db ye x p e r i m e n t s t h ew o r k si n t h i s d i s s e r t a t i o nc o n t r i b u t et ot h eq u e r yp r o c e s s i n go fx m ls t r e a ma n dt h ed e v e l o p m e n t o fp r a c t i c a lt e c h n o l o g i e s k e y w o r d s ：x m ls t r e a m ，p a t he x p r e s s i o n ，q u e r yp r o c e s s i n g ，c o n t i n u o u sq u e r i e s 图目录 1 1x m l 数据流处理引擎应用场景 1 2 简单路径表达式的过滤问题 1 3 复杂路径表达式的查询处理 2 1 一个x m l 文档示例 2 2x m l 文档树示例 2 3s a x 解析器产生的事件 2 4x m l 查询语言相互之间的关系， 2 5 本文所处理路径表达式的语法 2 6 简单路径表达式的语法 2 7 路径表达式所对应的查询树 2 8 查询树的匹配， 2 9 查询树多个匹配的简单例子 2 1 0x m l 文档数据库查询应用模型 2 1 1x m l 数据流查询应用模型 2 1 2x m l t k ：基于确定有限自动机的路径表达式查询处理 2 1 3y f i l t e r ：基于非确定有限自动机的路径表达式查询处理 2 1 4 非确定有限自动机的执行示例 3 1 一个使用4 个哈希函数的b l o o mf i l t e r 示例 3 2x m l 文档过滤问题的应用场景 3 3 创建路由表表项的示例 3 4 产生候选路径过程的示例 3 4 4 9 u m巧坞均牡沈船拍勰； 雅 图目录 3 5 对候选路径进行路由的示例 3 6 创建前缀过滤器 3 7 使用前缀过滤器 3 8 前缀过滤性能实验：候选路径的数量 3 9 前缀过滤性能实验：过滤时间， 3 1 0 创建前缀过滤器的时间 3 1 l 路由表创建时间对比 3 1 2 路由表大小对比 3 1 3 不同用户数量情况下过滤时间对比 3 1 4 不同深度x m l 文档的过滤时间对比 4 1 简单路径表达式中等值约束的处理， 4 2 查询树的分解， 4 3 复杂路径表达式的处理模型， 4 4 逻辑表达式树 4 5x m l 文档树和复杂路径表达式， 4 6 输出的匹配路径流， 4 7 复杂路径表达式的计算过程示例( 1 ) 4 8 复杂路径表达式的计算过程示例( 2 ) 4 9 基于路径存储的方法示例， 4 1 0 对不同数量通配符和后代轴的处理性能对比 4 1 l 对不同大d 、x m l 文档的处理性能对比 4 1 2 对不同大小查询集的处理性能对比， 5 1x m l 数据流处理引擎的应用 5 2 x s t r 系统架构， 8 0 8 2 蛆必驵勰的n弛孔 阻铝铀礼他2丌蔼 ， 1 绪论 1 1 研究工作的背景 在进入信息化时代的今天，人们每天会面对大量的各种形式的信息，对信息 的处理变得与我们的生活密切相关。互联网技术的发展为我们提供了丰富的信息 来源，同时也对信息处理技术提出了更高的要求。在数据库研究领域，研究人员 不再仅仅面对传统意义上的结构化数据，对各种形式的非结构化、半结构化数据 的处理逐渐成为研究的热点。x m l 8 4 i 吾言作为一种数据表示和交换的格式，具 有可扩展和自描述等特点，被广泛地应用于各种互联网应用中。对x m l 数据处 理技术的研究是近年来学术界和工业界关注的热点之一，一大批x m l 处理技术 和工具集被研发出来，进一步推动了基于x m l 的应用的发展。 面对互联网上海量的信息，个性化的定制服务【1 9 ，8 6 1 逐渐成为人们获取信 息的一个重要手段。越来越多的信息提供者开始在互联网上以x m l 格式发布 信息。n i t f ( n e w si n d u s t r yt e x tf o r m a t ) 2 4 ：是被世界各地的新闻机构广泛使用 的，用于发布新闻信息的x m l 格式标准，n e wy o r kt i m e s 、a g e n c ef r a n c ep r e s s 和a n s ai t a l y 都在使用这一标准。当新闻信息被以n i t f 格式发布时，个性化 的新闻定制服务便可以提供给用户更丰富的表达兴趣的手段，例如用户可以定制 关于“有关禽流感的新闻”、“伊拉克局势的最新报道”以及“昨天发生在上海 的交通事故”等等。同时这种个性化的服务还可以让用户指定，仅发送给他们新 闻信息的特定部分，如标题、摘要等r s s ( 融a l l ys i m p l es y n d i c a t i o n ) 7 9 是另 外一种基于x m l 的信息发布方式，它允许信息的发布者以x m l 格式来发布信 息，用户可以根据信息发布者的u r l 或使用关键字来订阅感兴趣的信息内容。 目前国内的很多新闻网站都已经开始提供基于r s s 的新闻定制服务。 对于个性化的信息定制服务来讲，其核心技术是如何对大量的用x m l 格式 表示的数据进行有效的处理。用户通过图形化界面或其它方式将他们的订阅请 l 1 绪论 求发送给服务器，这些订阅请求被当作对x m l 数据的查询保存在服务器上。当 系统中产生或从其它信息发布者处获得新的x m l 数据时，需要判断每一条新的 x m l 数据与哪些用户查询相匹配。这种查询匹配处理的难点在于： 1 对于信息定制服务来说，其用户的数量往往是巨大的，因此用户所提交查询 的数量也是巨大的。显然，以传统的方式对每条查询进行匹配处理，是不能 够满足系统服务性能的要求。如何同时对大量的用户查询进行处理是所面临 的一个挑战。 2 在信息定制服务系统中，往往每时每刻都会有新的x m l 数据产生，这些 新的数据就像数据流一样源源不断地到达，系统必须快速及时地对到达的 x m l 数据进行处理和分发。传统的将数据保存后建立索引，然后进行查询 的处理方式，很难对快速的数据流进行及时的处理。 除了上文所提到的信息发布与订阅应用之外，x m l 还被很多其它类型的应用 系统采用为数据表示的格式。例如，在w e b 服务以及应用集成领域，不同系统 之间相互传递的消息部开始采用x m l 格式表示大量的以x m l 格式表示的消 息在网络上被发送和接收，对于应用系统或消息路由服务来说，这些消息形成了 一个源源不断的x m l 数据流。对x m l 数据流处理技术的研究不但被学术界所 关注，越来越多的企业也开始关注相关技术和产品的研发，例如m i c r o s o f t 2 3 1 和 b e as y s t e m s 1 0 1 公司都已经开始致力于开发下一代基于x m l 的消息处理中间 件。目前，在现有的相关软件产品中，还仅针对于已知格式的x m l 数据流进行 处理，对于大量的不同格式或格式未知的x m l 数据流进行处理是一个有待于进 一步研究的领域。 1 2 本文的研究内容 本文对x m l 数据流的处理技术进行研究，主要关注x m l 数据的过滤及查询 处理的相关技术。如图1 1 所示，在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 1 绪论 者会向x m l 数据流处理引擎注册它们的查询，并不断地接收从x m l 数据流返回 的查询结果。 图1 1 ：x m l 数据流处理引擎应用场景 在这样的应用场景中，对x m l 处理技术的挑战主要来自几个方面： 数据量：所需处理的数据量一方面指x m l 数据到达的速率，另一方面也包 括所到达的每个x m l 文档的大小。通常通过网络传递的x m l 数据在单个 文档上不会很大，一般不超过几m b ，但数据到达的速率往往会很快，可以 达到每秒上万条数据。例如，n a s d a q 6 2 股票交易市场在开盘期间每秒钟 可以产生将近6 0 ，0 0 0 条消息。 查询：对x m l 数据的查询通常是以路径表达式的形式体现，如x p a t h 2 0 1 查询表达式。路径表达式中涉及通配符“* 号、后代轴“”、分支路径以 及元素内容约束的处理一直是查询处理中的难点。此外，在x m l 数据流应 用环境中，用户的数量往往会很大，因此用户所提交路径表达式的总量会很 多，如何同时对大量的路径表达式进行查询处理是需要解决的问题之一 结构信息：由于x m l 数据的来源很多，在很多情况下所接收到的x m l 文 档并没有一致的模式，因此基于x m l 数据模式的查询处理技术在数据流环 境下往往是不适用的。 3 1 绪论 图1 2 ：简单路径表达式的过滤问题 针对x m l 数据流上路径表达式的查询处理，本文首先从不具有分支路径和 元素内容约束的简单路径表达式的处理入手，研究了针对简单路径表达式的x m l 数据流过滤处理技术。如图1 2 所示，在这个应用场景中，用户的查询全部是简 单路径表达式，每个用户可以提交一组查询。x m l 过滤引擎根据输入的x m l 文 档在每个用户查询集中的匹配情况，对x m l 文档进行路由分发处理。在处理过 程中，并不是针对每一个单独的用户查询来对x m l 文档进行匹配。对于用户来 说，只要x m l 文档可以和其所提交的一组查询中的任何一个匹配，就可以将这 个x m l 文档发送给用户。 图1 3 ：复杂路径表达式的查询处理 在针对简单路径表达式的过滤处理技术相关研究工作的基础上，本文对包含 有分支路径和元素内容约束的复杂路径表达式在x m l 数据流上的查询处理进行 了研究。由于存在着分支路径，在x m l 数据流上很难直接对复杂路径表达式和 x m l 文档进行匹配，因此本文采用将复杂路径表达式分解为一组简单路径表达式 4 1 绪论 的方法，利用x m l 数据流上针对简单路径表达式的过滤处理技术来对复杂路径 表达式进行查询处理。如图1 3 中所示，所有的复杂路径表达式首先被分解成简 单路径表达式，利用简单路径过滤引擎可以得到与简单路径表达式匹配的文档片 断，复杂路径表达式处理器可以利用这些文档片断来实现对复杂路径表达式的查 询处理。 为了能够将研究工作的成果转化为现实的应用技术，本文对x m l 数据流引 擎的应用需求进行了深入的分析，提出了一个x m l 数据流处理引擎的架构设 计；并在已有工作的基础上，实现了一个对x m l 数据流进行处理的原型系统。 1 3 论文的主要贡献 本篇论文主要对x m l 数据流上路径表达式的查询处理技术展开研究工作， 论文的主要贡献可以总结为如下几点： 本文在对x m l 数据流应用的特点进行深入分析后，首先提出了将b l o o m f i l t e r 结构应用于解决x m l 数据流过滤问题的方法，这是一个完全不同于 已有方法的新的解决思路。在x m l 数据流过滤问题的研究中，对路径表达 式中通配符“”号和后代轴“”的处理是研究的难点。本文所提出的基于 b l o o mf i l t e r 结构进行x m l 数据流过滤处理的方法可以有效支持对简单路 径表达式中的通配符”号和后代轴“”的处理，同时可以方便地支持用 户对查询集的修改。 在基于b l o o mf i l t e r 结构进行x m l 数据流过滤处理的方法中，候选路径的 生成是其中的关键步骤。在对x m l 数据流中的文档进行解析的过程中， 当x m l 文档的深度增加时，所生成候选路径的数量会快速增长，这是制约 过滤性能的主要因素。本文设计了前缀过滤的方法，用于减少解析过程中所 生成候选路径的数量。前缀过滤结构是根据用户的查询集进行构造的，在生 成候选路径的过程中，使用前缀过滤可以有效地将无用的候选路径前缀摒 除，极大地减少了所生成候选路径的数量。 为了验证本文所提t r i g 基于b l o o mf i l t e r 结构的x m l 数据流过滤方法的性 能，我们选取了已有技术中具有代表性的基于非确定有限自动机的方法作 为对比，进行了详尽的比较实验。实验结果表明，本文提出的基于b l o o m 5 1 绪论 f i l t e r 的方法在创建路由表时的性能和所创建路由表的大小两个方面明显优 于基于自动机的方法。对x m l 数据流进行过滤处理时，在用户的查询集很 大( 如l ，0 0 0 ，0 0 0 个互不相同的简单路径表达式) 并且输入的x m l 文档的深度 不超过5 的情况下，基于b l o o mf i l t e r 的方法在过滤性能上要优于基于自 动机的方法。 在针对x m l 数据的路径表达式查询处理中，分支结构和对元素内容的约束 是另外两个处理的难点。针对x m l 数据流上路径表达式的查询处理问题， 本文提出了将包含有分支结构的复杂路径表达式分解成一组简单路径表达 式，在对简单路径表达式进行过滤处理的基础上，实现对复杂路径表达式进 行查询处理的方法。与已有的方法不同，本文所提出的方法以简单路径过滤 引擎输出的查询字符串流作为输入，可以支持对元素内容约束的处理，同时 可以以连续查询( c o n t i n u o u sq u e r i e s ) 的方式实现对复杂路径表达式的查询处 理。本文通过实验将所提出的处理方法与已有方法进行了对比，证明该方法 在对复杂路径表达式的查询处理上具有较好的性能。 本文在简单路径表达式和复杂路径表达式查询处理技术的研究基础之 上，设计和实现了一个x m l 数据流处理引擎一一x s t rf x m ls t r e a m p r o c e s s i n ge n g i n e ) 原型系统，并对该系统的实现进行了介绍。x s t r 系统 可以被作为中间件应用于针对x m l 数据流进行处理的应用系统中。 1 4 章节安排 本论文共分为六章第1 章主要对论文研究工作的动机、应用场景和主要内 容进行概要性介绍，给读者以整体的印象第2 章到第5 章是本文的核心内容， 对本文研究工作的背景知识、主要技术、和性能实验进行了详尽的介绍。为了方 便读者理解本文的研究工作，在第2 章中首先介绍了x m l 语言以及对x m l 数 据的建模和相关解析技术，然后对路径表达式和x m l 查询语言进行了介绍，并 给出了在x m l 数据上进行路径表达式计算的模型；针对本文所研究的x m l 数 据流处理，第2 章中还对当前x m l 查询处理技术发展的现状进行了综述，并介 绍了两个x m l 数据流处理原型系统。论文的第3 章研究了针对简单路径表达式 查询对x m l 数据流进行过滤处理的技术。在对b l o o mf i l t e r 结构进行介绍的基 础上，提出了基于b l o o mf i l t e r 结构进行x m l 数据流过滤处理的方法，以及利 6 1 绪论 用前缀过滤对该方法的改进。最后，通过实验对基于b l o o mf i l t e r 的方法进行了 性能分析。在x m l 数据流上对复杂路径表达式进行查询处理是本文另外一个重 要的研究工作，第4 章对这部分内容进行了详尽的介绍。首先，本文讨论了对路 径表达式中所包含的节点内容约束的处理，然后介绍了如何将复杂路径表达式分 解成一组简单路径表达式的方法；在此基础上介绍了本文提出的在x m l 数据流 上进行复杂路径表达式连续查询处理的技术，并分别通过示例和实验对该技术的 处理过程及性能进行了分析。在第5 章当中，本文对x m l 数据流应用的需求进 行了分析，提出了一个x m l 数据流处理引擎的系统架构设计，并以第3 章和第 4 章中的实验代码为基础，实现了原型系统x s t r 中的核心模块。最后，在第6 辛中对论文的研究工作进行了总结，并就技术的改进和将来的研究方向进行了讨 论。 7 2 背景知识和相关工作 本文在第1 章绪论中，对研究工作的应用背景、内容和主要贡献进行了阐 述。本章主要介绍与论文研究工作相关的背景知识，以及在相关领域中已有的 研究工作和成果。首先，我们通过一个x m l 文档的示例对x m l 语言进行了介 绍，并讨论了x m l 语言的解析技术；其次，介绍了用于对x m l 数据进行查询 的x p a t h 语言，在对x p a t h 语言的表达能力进行分析的基础上，我们对本文研 究工作所涉及的路径表达式进行了定义；最后，我们对x m l 查询处理领域中已 有的研究工作，特别是对x m l 数据流处理技术进行了综述，并对相关的原型系 统进行了介绍。 2 1 可扩展标记语言( 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 ) 8 4 】，简称x m l 语言，是由 w 3 c 2 1 】组织提出的一种简单灵活的文本数据格式。x m l 语言是从s g m l 3 8 】 语言派生出来的，是s g m l 语言的一个子集。定义x m l 语言的目的在于弥补 h t m l 2 5 】语言在对数据语义和结构上表达能力的不足。目前，x m l 越来越广泛 地被应用于各个领域，已经成为互联网上数据表示和数据交换事实上的标准。 2 1 1x m l 文档基本结构 一个x m l 文档通过标记( t a g ) 来表示一组数据对象，其中每个数据对象被 称为一个元素( e l e m e n t ) 。x m l 文档中的每个元素通过一个开始标记和一个结束 标记指定了该元素所包含数据的范围，标记名描述了该元素所包含数据的语义。 元素与元素之间存在着层次关系，即一个元素可以被包含在另一个元素的范围 之内。一个元素的内容可以是嵌套的子元素，也可以是属性或字符串值。每个 8 2 背景知识和相关i 作 c o l o m b i ae a r t h q u a k e 1 4 3d e a di nc o l o m b i ae a r t h q u a k e b yj a r e dk o t l e r ，a s s o c i a t e dp r e s sw r i t e r b o g o m ，c o l o m b i a m o n d a yj a n u a r y2 51 9 9 97 ：2 8e t 图2 1 ：一个x m l 文档示例 x m l 文档都有一个唯一的根元素，包含了该文档的所有内容。图2 1 给出了一 个用于描述新闻信息的x m l 文档示例。图中粗体字表示的是元素的标记名，如 t i t l e 和b o d y 是两个元素的标记名，表示这两个元素分别是新闻信息的标题和内 容。 和 是新闻标题元素的开始标记和结束标记。两者之间的数 据是新闻标题元素的内容，即字符串“c o l o m b i ae a r t h q u a k e 。该文档的根元素 是n i t f , 包含了文档中所有的其它元素。文档的第一行是x m l 的声明语句，用 来定义所使用x m l 语言的版本和文档中的字符编码，如图2 ，1 所示，表明该文 档符合x m l1 0 规范的语法，并且使用i s 0 8 8 5 9 - 1f l a t i n - i w e s te u r o p e a n ) 字 符集。这里需要特别指出的是，x m l 文档中所有元素都应有一个开始标记和一个 结束标记，缺少结束标记的元素定义是非法的；此外，在同一个x m l 文档中的元 素之间必须保持正确的嵌套关系，交叉嵌套的元素会造成x m l 文档语义上的混 乱，如例2 1 中元素 和 。元素在开始标记中可以包含属性，属性值应 当被引号所标明，如图2 1 中的元素n i t f 具有属性i d 和b a s e l a n g ，属性值分别为 “n 0 1 ”和“e n g l i s h ”。 例2 ，1 i m p r o p e rn e s t i n go ft a g sm a k e sn os e i i s et ox m l 9 2 背景知识和相关i 作 x m l 文档的语法规范除上述的的特征外，还包括注释( c o m m e n t s ) 、处理指令 ( p r o c e s s i n gi n s t r u c t i o n s ) 等其它特征，因这些特征不影响对x m l 文档的处理， 本文中不再一一赘述。符合x m l 语法规范的x m l 文档被称为良构( w e l l - f o r m e d ) 的文档，本文研究工作所处理的目标数据均为良构的x m l 文档。对于非良构的 x m l 文档，可以在对文档结构分析的基础上，通过修改文档的内容使其成为良构 的文档。因此，在后文中所提到的x m l 文档均指良构的x m l 文档，不再另加 说明。 x m l 文档的结构可以通过d t d ( d o c u m e n tt y p ed e f i n i t i o n ) 8 4 和x m l s c h e m a 4 7 1 进行描述。一个d t d 或者x m ls c h e m a 定义了一类x m l 文档应当 满足的规则，包括文档中元素的结构、属性的值域等。通过为x m l 文档定义标 准的d t d 或x m ls c h e m a ，人们可以更容易理解x m l 文档的内容，通过x m l 来进行数据交换更加方便。在存在d t d 或x m ls c h e m a 的情况下，对x m l 文 档的处理也将会更加容易。但在现实的应用中，特别是在基于互联网的应用中， 很多情况下需要处理的x m l 文档并没有相关的结构信息，或者说不存在一个统 一的d t d 或者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 语言作为数据的表现格式，具有自描述性、灵活性和可扩展性等 优点。x m l 的自描述性是指在x m l 文档中，可以通过指定元素的标记名来对元 素所包含的内容进行描述。与保存在数据库中的结构化数据相比，使用x m l 对 数据进行播述具有很大的灵活性。除了用户可以任意定义元素的标记名外，即使 对于那些受d t d 或x m ls c h e m a 约束的x m l 文档，在其内容和结构上仍然有 很灵活的变化空间。例如，在x m l 文档中，一个元素的子元素、属性以及文本 内容都可以是可选的，同一个子元素可以出现多次等等。x m l 语言的可扩展性 体现在结构和标记的定义上，任何人都可以为自己发都的x m l 文档定义d t d 或x m ls h c e m a ，也可以对已有的d t d 和x m ls c l l e m a 进行修改。在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 ) 2 5 l 语言中，所有的标记都是预先定义好的；而在 x m l 语言中用户可以任意定义元素的标记 2 1 2x ml 文档的树模型 在x m l 文档中，元素与元素之间存在着嵌套关系，并且存在着唯一的根元 素，因此一个x m l 文档可以被看成是一棵由元素构成的文档树。在图2 2 中， 1 0 2 背景知识和相关i 作 图2 2 ：x m l 文档树示例 我们将图2 1 中的x m l 文档表示成一棵文档树的形式。在x m l 文档树中的每 个节点对应于文档中的一个元素、属性或文本内容，每个节点的标签是对应的元 素名、属性名或字符串值，节点之间的层次关系对应于文档元素之间的嵌套关 系。如果在x m l 文档中两个元素是直接嵌套在一起的，那么处于嵌套外层的元 素对应于文档树上的一个父节点，处于嵌套内层的元素所对应的结点是外层元素 所对应节点的子节点。例如，在图2 1 所示的x m l 文档中，元素t i t l e 直接嵌套 在元素h e a d 中，因此在图2 2 所示的x m l 文档树中，节点t i t l e 是节点h e a d 的子节点。一个节点的父节点，以及其父节点的父节点，以此类推的所有节点被 称为该节点的祖先节点。例如，图2 2 中节点0 、5 、8 都是节点9 的祖先节点。 一个节点的的子节点，以及其子节点的子节点，以此类推的所有节点被称为该节 点的后代节点。例如，图2 2 中以节点5 为根的子树上的所有节点( 不包含节点 5 ) ，即节点6 至1 2 ，都是节点5 的后代节点。所有具有相同父节点的节点，相 互称为兄弟节点。例如，图2 ，2 中节点6 、8 、1 0 是兄弟节点；节点1 l 和1 2 也 是兄弟节点。 从x m l 文档树模型的角度看，元素的属性和元素直接包含的子元素，都对 应于元素节点的子节点，因此在处理上可以将属性和子元素同等对待，不进行更 详细的区分。x m l 文档中的文本内容可以像元素一样被映射到文档树上的一个 1 1 2 背景知识和相关i 作 节点，也可以仅将其看成是所属元素的内容，作为一个特殊的节点看待。在部分 x m l 文档中，允许子元素和字符串值同时出现在一个元素的内容中，即，一个 x m l 文档树上的节点可以同时拥有子节点和文本内容。在本文中，为了讨论的方 便，不再区分元素节点和属性节点，也不允许一个元素节点同时拥有子节点和文 本内容。对于字符串值，本文中不将其映射为一个独立的节点，而足作为所属节 点的文本内容来处理。 由于在x m l 文档中，一个元素可以重复出现多次，在处理的过程中，为了 区分同名的不同元素，通常的做法是为每个元素分配一个唯一的编号。对文档中 元素进行编号的一种方法是，在每个元素中包含一个i d 属性，通过属性值的不同 来区分不同的元素。这种方法要求在生成x m l 文档的时候为每个元素分配一个 编号：但对于处理x m l 文档的应用来说，这个编号往往很难满足应用的需求。 因此，大多数的x m l 处理方法中，都会根据自身的特点在处理过程中为每个元 素另外分配一个编号。如，图22 中的每个元素节点都有唯一的一个编号，这个 编号是根据对x m l 文档树进行前序遍历顺序生成的，也是本文中将要使用的编 号方法。 2 1 3x m l 文档的解析 x m l 是一种文本数据格式，为了能够有效地从文本格式中解析出x m l 数据 的结构和内容，专用的x m l 解析器是处理x m l 文档所必须的。目前，对x m l 文档的解析技术主要可以分为以下几类： 基于推模型( p u s hm o d e l ) 的技术：应用程序通过解析器对x m l 文档进 行处理，解析器在顺序处理x m l 文档的过程中不断产生一系列事件，并且 将这些事件推送给应用程序。在这种处理方式中，解析器产生的事件控制应 用程序的处理节奏。基于推模型的技术的主要优势在于只需要将正在处理的 相关元素装入内存，不必将整个x m l 文档全部装入内存，因此可以处理很 大的x m l 文档。此类技术的典型代表是s a x ( s i m p l ea p if o rx m l ) 6 4 解 析器。 基于拉模型( p u l lm o d e l ) 的技术：与基于推模型的技术不同，当使用基 于拉模型技术的解析器时，应用程序主动请求解析器产生的事件，而不是被 动地等待和处理解析器的事件。与基于推模型的技术相同的是，在这种处理 1 2 2 背景知议和相关i 作 方式中，应用程序只能够向前( f o r w a r d o n l y ) 对x m l 文档解析，而不能够 对已经处理过的元素进行回溯。x m lp u l lp a r s i n g 4 6 】是此类技术的一个代 表。 基于树模型( t r e em o d e l ) 的技术：将一个x m l 文档表示成一个节点 树的形式，x m l 文档中的元素和属性