（计算机软件与理论专业论文）在xml数据流上的模式树匹配查询.pdf

复、学删l 学位论文 在x m i 。数据流i ：的模式树匹配查渤 在x m l 数据流上的模式树匹配查询 摘要 x m l 以其强大的数据表达能力，事实上已经成为i n t e r n e t 上数据表示和交换 的标准。有些x m l 数据只能以数据流的形式访问。所以，如何设计x m l 数据 流杏询算法，如何利用x m l 的文档结构来提高数据流查询的时间空间效率已成 为一个重要的课题。 木文就此研究和分析在x m l 数据流上的模式树查询匹配，并提出一个x m l 数摒流的模式树查询系统。该系统中有三个关键算法：x m l 数据流编码算法、 s t r e a m i n gt w i gj o i n 算法和d e l t a p a t hj o i n 算法。 x m l 数据流编码算法改进了原有的x m l 元素的三元组编码方案，并提出了 基于s a x 事件回调机制的编码算法。 s t r e a m i n g t w i gj o i n 算法是对h o l i s t i e t w i gj o i n 算法在数据流处理下的改进， 井能，卜成以路径为单位的查询匹配结果。 d e l t ap a t hj o i n 算法能以递增的方式生成最终的模式树查询匹配结果。 实验证明本文所提出的x m l 数据流查询系统有较高的查询效率。 关键字x m l ，数据流，模式树匹配 第1 页共5 4 页 复。人学坝j 学似沦文 在x m l 数据流j ：的模式树匹配盎询 t r e ep a t t e r n m a t c h i n g o nx m ls t r e a m s a b s t r a c t i nf a c t ，x m lh a sb e c o m et h es t a n d a r do fd 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 l i n t e r a c tb e c a u s eo fi t s p o w e r f u la b i l i t y o fe x p r e s s i o n s o m ex m ld a t ac a nb e a c c e s s e do n l yb yt h ew a yo f s t r e a m s t h u s ，i th a sb e c o m e a l li m p o r t a n ti s s u et h a th o w t o d e s i g n t h e a l g o r i t h m o fx m l s t r e a m i n gq u e r i e sa n dh o wt o m a k eu s eo ft h e s t r u c t u r eo fx m ld o c u m e n tt o i m p r o v es p a c e a n dt i m e e f f i c i e n c y o fs t r e a m i n g q u e r i e s i nt h i sp a p e r , w es t u d ya n d a n a l y s i st r e ep a t t e r nq u e r i e s o nx m ls t r e a m s w ea l s o d e s i g na t r e ep a t t e r nq u e r i e ss y s t e mo nx m ls t r e a m s t h e r ea r et h r e ek e ya l g o r i t h m s i nt h es y s t e m ：x m i s t r e a m i n g n u m b e r i n ga l g o r i t h m ，s t r e a m i n gt w i g j o i na l g o r i t h m a n dd e l t ap a t hj o i n a l g o r i t h m x m ls t r e a mn u m b e r i n ga l g o r i t h mi san u m b e r i n ga l g o r i t h mb a s e do ns a x e v e n t sc a l l b a c km e c h a n i s m t h en u m b e r i n gs c h e m ai nt h ea l g o r i t h mi m p r o v e so n o r i g i n3 - t u p l em u n b e r i n g s c h e m ao nx m le l e m e n t s s t r e a m i n gt w i g j o i na l g o r i t h mi m p r o v e so r lt h eh o l i s t i ct w i gj o i na l g o r i t h mo n t h ex m l s t r e a m i n g p r o c e s s i tc a l lg e n e r a t ep a t t e r nq u e r yr e s u l t si nt h eu n i to f p a t h s d e l t ap a t hj o i n a l g o r i t h m c a n g e n e r a t e f i n a l q u e r y r e s u l t so ft r e e p a t t e r n m a t c h i n g e x p e r i m e n t sh a v ep r o v e dt h a tx m ls t r e a m i n gq u e r ys y s t e mh a sh i g hq u e r y e f f i c i e n c y k e y w o r d x m l , s t r c a m s t r e ep a t t e r nm a t c h i n g 第2 页麸5 4 页 复口大学砸i j 学位论文 在x m i 数据流上的模式树世配书询 第一章绪论 今i - j l 年来，随着i n t e r n e t w e b 信息技术的迅速发展，i n t e r n e t w e b 已经成为 人类社会信息共享与交换、信息发布与传递的平台。同时，当今的i n t e r n e t 又面 临信息格式松散、缺乏必要标准和元数据的问题，各内容提供者和服务提供者大 多以自治的方式存在。 w 3 c 存1 9 9 8 年制定了x m l 的标准，启动了整个i n t e m e t 信息标准化的进程。 x m l 以其自描述性、可扩展性以及计算机易处理性迅速取得了学术界和企业界 的广泛认同，它日益超出其作为标注语言的初衷而成为i n t e m e t 上数据表示和交 换的标准。 x m l 最大的优点是它强大的数据表达能力，以x m l 表达的数据在i n t e r n e t 卜迅速地增长。大量x m l 数据的存在，使得如何管理，如何查询这些数据成为 迫切的问题。由于x m l 是典型的半结构化数据( s e m i s t r u c t r u e dd a t a ) ，同前应 用最广泛的关系数据库管理系统并不适合管理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 p m h 、x m l 解析器、x m l 与半结构化数据之间 的关系，然后对当前x m l 数据流查询相关领域的研究作概括和总结。 1 1x 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 ) 【x m l l 9 9 8 ，即可扩展标记语言，是由 w 3 c ( w o r l dw i d ew e bc o n s o r t i u m ) 组织的x m l 工作小组定义的。这个： 作小 组是这样描述该语占的：“扩展标记语言( x m l ) 是s g m l 的子集，其目标是允 许普通的s g m l 在w e b 上以目前h t m l 的方式被服务、接收和处理。x m l 被 i 5 乏计成易于实现，且可在s g m l 和h t m l 之间互相操作。”这段话是从正式的 x m i 。规范1 0 版本中引述的，该规范是x m l 工作组在1 9 9 8 年2 月完成的。正 如所看到的，x m l 设计的初衷是让它成为一种专门在w e b 上传递信息的语言， 第5 页共5 4 页 复人学坝i ：q ：4 , i l k 文 和x m l 数据流1 的模式树匹配盘咖 一_ _ _ 一 就像h t m l ( 超文本标记语言) 群( 自从w e b 出现以来，h t m l 已经成为了 创建w e b 页的标准语言) 。 。，h t m l 不同，x m l 具有如下一些特征：x m l 具有自描述性( 元素的标记 描述了信息) ；x m l 具有可扩展性( 用户可以通过d t d 或s c h e m a 来定义新的 元索) ；x m l 提供了更为灵活的机制来表达更为复杂的链接关系，x l i n k ( x m i 。 l i n k i n gl a n g u a g e ) 【x l l 2 0 0 1 【ix p o i n t e r ( x m lp o i n t e rl a n g u a g e ) x p l 2 0 0 2 j 允许定义灵活的链接目标；把信息的结构、内容和显示分离开来，x m l 主要表 示信息的内容和结构，而把显示方法交给x s l ( e x t e n s i b l es t y l e s h e e tl a n g u a g e ) x s l 2 0 0 2 或c s s 处理。 t c p 1 pi l l u s t r a t e d s t e v e n s w p u b l i s h e r a d d i s o n w e s l e y 6 5 9 5 a d v a n c e dp r o g r a m m i n gi nt h eu n i xe n v i r o n m e n t s t e v e n s w q f i r s t a d d i s o n - w e s l e y 6 5 9 5 x m l a b i t e b o u l s e r g e s u c i u 叫l a s t d a n m o r g a n k a u f m a r m p u b l i s h e r s 3 9 9 5 图1 1 一个描述书籍信息的x m l 文档 x m l 文档是一种树状的结构，包含了从根元索开始的嵌套元素结构，所以 经常把x m l 文档称作“x m l 文档树”。x m l 文档的每个元素有一个标签( t a g ) 第6 页共5 4 页 拒x m l 数据流 。的模式树匹自d 盘咖 与之对应。除了字符串数据，元素还可以包含属性值对和嵌套子元素。图1 1 给 出_ r 一个描述书籍信息的x m l 文档。根元素b i b 包含多个b o o k 子元素，b o o k 儿素义包含y e a r 属性以及t i t l e 、a u t h o r 、p u b l i s h e r 、p r i c e 等子元素，其中a u t h o r 子元素可以有多个，a u t h o r 元素又包含l a s t 和f i r s t 子元素。 x m l 文档：如果一个数据对象满足x m l 规范中的格式良好( w e l l f o r m e d ) 的要求时，它就是个x m l 文档( 例如图i 1 显示的x m l 文档) 。x m i 。数据： 以x m l 格式表示的数据。本文中，对于x m l 文档和x m l 数据这两个概念并 不严格区分，认为它们是同义的。 1 。2x m l 和x p a t h x p a t h ( x m l p a t h l a n g u a g e ) x p l l 9 9 9 是一种对x m l 文档的内容进行定位、 查询的语占，是后续更强大x m l 查询语言如x q u e r y 【x q l 2 0 0 3 的基础，x p a t h 因使用路径标记在x m l 文档的层次结构中进行导航而得名。其工作方式与语法 有些类似于操作系统中用于文件定位得路径以及互联网中用于资源定位的u r l 。 当然，x p a t h 比后两者复杂得多。x p a t h 不独立使用，主要嵌入在x s l t ，x p o i n t e r ， d o m d o m 2 0 0 4 等宿主语言中应用，比如在x s l t 的应用中，x p a t h 用在模板 ( t e m p l a t e ) 中来查询数据以及定位匹配模式( p a t t e m ) 。 x p a t h 将x m l 文档视为一个节点树，节点有七类，包括根节点、元素节点、 槿性节点、文本节点、命名空间节点、处理指令节点、注释节点。x p a t h 对每个 节点都定义了计算其字符串值的方法，不同的节点计算方法可能不同。 文档顺序( d o c m n e n to r d e r ) 定义了每个节点在x m l 文档中出现的顺序。x p a t h 认为的文档顺序与x m l 文档中节点的物理顺序( 起始标签) 一致。例如，根节 点为文档的第一个节点，每个元素节点出现在其子节点之前。 x p a t h 使用路径表达式去确定x m l 文档中的节点。我们将利用图1 1 的x m l 文档拙述x p a t h 语法。x m l 文挡可以表示为树结构节点形式，而x p a t h 使用模 式表达式识别x m l 文档的节点。一个x p a t h 的模式是使用反斜杠“”分开子元 紊名称描述路径。下面的x p a t h 表达式选择元素b i b 下元素b o o k 中的所有p r i c e 元素。 b i b b o o k p r i c e 注意，j _ f = j “”路径开始代表元素的绝对路径，不用“”路径开始代表元素的相 对路径，而用“”路径开始代表整个文档满足条件的所有元素。如果表达式中 间用“，路径代表元素下面满足条件的所有子孙元素。下面的x p a t h 表达式选 择文档中所有的b o o k 元素下的l a s t 子孙元素。 b o o m l a s t 第7 页共5 4 页 复 人学坝i 学位论文 托x m l 数据流i 瑚模式树匹酣查啕 使用力括号 o j 以指定特定的元素，下面的x p m h 表达式选取所有y e a r 属性为 2 0 0 0 并且有p r i c e 了元素的b o o k 元素。 b o o k y e a r = 2 0 0 0a n dp r i c e l 1 3x m l 解析器 现今有两种流行的x m l 文档解析器：d o m ( d o c u m e m o b j e c t m o d e l ) d o m 2 0 0 4 芹 is a x ( s i m p l e a p if o rx m l ) 。d o m 和s a x 作为一套a p i 已经在 多种语言中实现，包括j a v a 、c + + 、p e r l 、p ) r t h o n 等等。下面简要介绍一fd o m 和s a x 。 1 3 1d o m d o m 乃由w 3 c 定义，和d o m 有关的主要有d o m 规范和基于d o m 的 x m lp a r s e r 。d o m 规范文档根据“基于树”的思想中定义了一种对象模型，这 k 十x , l 象模型将一份结构化文档用对象树的形式表达出来。按照d o m 规范提供- 次丌发接口的x m lp a r s e r 软件包称为基于d o m 的x m lp a r s e r ，区别于基于s a x 的x m lp a r s e r 。d o m 的思想也称为“基于树的( t r e e b a s e d ) ”，因为其主要想 法是一次性将一篇结构化文档全部解析，然后生成一个对象树( o b j e c tt r e e ) 用 以描述该文档。之后对于该文档的所有操作( 如修改、查询等) ，均在该对象树 i ：进行。 d o m 的规范现有两层。l e v e lo n e 的草案于1 9 9 7 年1 0 月公布，f 式文档于 1 9 9 8 年】0 月发布。l e v e lt w o 于1 9 9 8 年1 2 月提出草案，2 0 0 0 年5 月发布正式 文档。l e v e lt h r e e 已于2 0 0 0 年9 月1 日发布第一份草案( d r a f t ) 。d o m 新发布 的每一层都对以前d o m 进行了内容上的扩充和更新。d o m l e v e lo n e 在结构上 分为两段，其中d o m ( c o r e ) 定义了用于描述x m l 的d o m 接口，d o m h t m l 描述了用于h t m l 的d o m 。d o m l e v e lo n e 主要描述了三部分内容，它们分别 是：1 ) 定义了用于表达和操作一份结构化文档的接口和对象。2 ) 这些接口和对 象的语法，包括其行为和属性。3 ) 这些接口和对象之间的关系与协同关系。 d o ml e v e lt w o 在l e v e lo n e 的基础上增加的内容包括：文档的抽象视、对象树 的遍历、文档中的块( r a n g e ) 、风格页、层叠式风格页等内容。另外，更重要的 是，l e v e l t w o 增加了对事件机制的支持。事件机制在l e v e l o n e 中完全没有被 定义。需要注意的是，d o ml e v e lt w o 中所说的事件( e v e n t ) 和s a x 的事件驱 动( e v e n td r i v e n ) 中的事件，虽然名称相同，但涵义完全不同。d o m 2 中的事件， 指的是结构化文档内部所定义的事件，比如页面被加载时的o n l o a d 事件等，和 p a r s e r 无关。而s a x 中的事件，指的是x m l p a r s e r 在解析x m l 文档时产生的 第8 页共5 4 页 皇兰尘兰竺兰兰竺兰兰一一 生兰竺! 垫塑塑：! 竺堡苎塑坚望兰塑 _ _ 一 回啕( c a l l b a c k ) 事件，和文档本身无关。l e v e l t h r e e 还处于草稿中，从w 3 c 公 布的草案来看，第三层的主要目标是进一步加强和扩充。 遵循d o m 规范开发的x m l p a r s e r 的使用足自然的：首先初始化一个p a r s e r ， 然后将一篇文档提交处理，p a r s e r 处理后返回一颗对象树。然后所有剐文档的操 作均对这颗树进行。在这个过程中，对象树和其操作等，均遵循d o m 规范的规 定。凼此，遵循标准d o m 接口的x m l p a r s e r 是具有良好的重用特性的。由于 含有对象的概念，d o m 天生就是为面向对象的程序语言指定的。其规范中也以 j a v a 语言作为示例语言。需要指出的是，d o m 并不是一个二进制的规范，所以， 只有对于特定的编程语占才有意义。例如，对于c + + 程序员来说，用j a v a 写的 x m lp a r s e r 只有参考价值。 d o m 的最大问题在于性能，无论是在运行的速度上，还是运行所需要的内 存上，都对资源提出了很高的要求。在运行速度方面，d o m 程序在解析整个文 档时下少需要扫描整个文档两遍，而s a x 只需扫描一遍在运行所需要的内存方 面，山于d o m 程序一次性将整个文档都成生一颗树存放于内存中，故对于一些 大型的文档，可能会在内存上遇到麻烦。另外，即使是处理一些不那么大的文档 时，d o m 程序也会建立一大堆小对象。频繁的建立对象可能会导致很大的丌销。 例如，在j a v a 中，用n e w 建立的每一个对象最终都必须由j v m 的垃圾收集器负 责释放，大量的n e w 操作可能会导致j v m 的崩溃。 1 3 2s a x s a x 即是指一种接口，也是指一个软件包。作为接口，s a x 是事件驱动型 x m l 解析的一个标准接口，已被o a s i s ( o r g a n i z a t i o n f o r t h e a d v a n c e m e n to f s t r u c t u r e di n f o r m a t i o ns t a n d a r d s ) 所采纳。作为软件包，s a x 最 甲的丌发始r1 9 9 7 年1 2 月，由一些互联网分散的程序员合作进行。后来，参与 丌发的程序员越来越多，组成了互联网l 的x m l d e v 社区。五个月以后，1 9 9 8 年5 月，s a x l o 版由x m l d e v 正式发布。2 0 0 0 年5 月，x m l d e v 社区又发 布了最新的s a x 2 0 。2 0 版本在多处与1 0 版本不兼容，包括。+ 一些类和方法的名 字。 s a x 的工作原理是：p a r s e r 顺序扫描文档，扫描到文档( d o c u m e n t ) 开始与 结束、元素( e l e m e n t ) 开始与结束等地方时通知事件处理函数( h a n d l e r ) ，由事 件处理函数做相应动作，然后继续同样的扫描，直至文档结束。很明显，这种思 路利d o m 截然不同。使用s a x 时，只需将精力集中在事件处理函数的编写上 即可。如果使用的是非面向对象语言，如c ，则需要将程序员自行丌发的事件处 理函数作为参数传递给s a xp a r s e r 。如果使用的是面向的语言，则需要重载s a x 包巾原有的事件响应函数。 第9 页共5 4 页 复口 学坝 琦位论史 在x m l 数据流上的模式树呱配番询 由于s a x 在原理以及提供的接口等方面均比d o m 简单，i nh 寸s a x 的概念 0 i 是面向对象的，所以，虽然s a x 在速度、对资源的要求等方i 酊性能比d o m 好，但s a x 比d o m 难用、难懂。当使用s a x 的x m l p a r s e r 的程序规模增大 时，程序的可读性和可维护性迅速变坏。另。方面，使用s a x ，二次丌发的程 序员需要自行建立中间对象用于存储文档的信息，而这项工作在d o m 罩是由 p a r s e r 程序完成的。 1 4x m l 和半结构化数据 现实世界中，一些数据是完全没有结构的，如图像，音频，视频数据流；而 另外很多数据并非完全没有结构，但也不具有固定的结构。如h t m l 构成的w e b 页、电了二邮件、l a t e x 文档、生物数据库( 如a c e d b ) 等等。我们把它们称为 半结构化数据( s e m i s t r u c t u r e dd a t a ) 【b u n l 9 9 7 ，s u c l 9 9 8 】。与传统的数据化结构 ( 如关系数据库、对象数据库中的数据) 相比，它的主要特征是自描述性( 即内 容与结构都包含在数据中) ，它的结构是不固定、不规则、隐含的，并且是易变 化的。f | 于w e b 数据表示、数据集成、数据交换都需要利用半结构化数据，因 此从数据库角度研究半结构化数据的数据模型、模式、查询、查询优化、视图成 为近年来的热点问题，并且取得了很多可喜成果。 x m l 数据模型与半结构化数据之问的对应是非常明显的。可以说x m l 就是 半结构化数据的一个特例 w i d l 9 9 9 。x m l 文档代表了一4 个重要的并且在不断增 长的半结构化数掘源，它同半结构化数据有许多共同的性质，如自描述性、结构 不固定的、易变的。半结构化数据中的标注( 或称为属性) 、对象、原予值( s t r i n g ， i n t ，f l o a t ，v i d e o 等等) 分别对应于x m l 中的标记、元素、p c d a t a 。应此半结 构化数据已有的理论，如数据模型和查询，以及已有的原型系统可以作为x m l 研究的基础。但是x m l 与经典的半结构化数据之间也有区别。x m l 的元素可 以含有属性。x m l 文档的数组元素( e l e m e n t ) 具有顺序，元素之间通过i d 和 i d r e f 岗性进行引用，文档具有可选的d t d 等。x m l 文档的这些特征将其区 别于经典的半结构化数据，使其成为一种独特的半结构化数据类型。大量x m l 文档的高效组织管理、文档类型推导、分布式计算等问题为我们带来了新的研究 课题。x m l 具有可扩展性、更强的链接方法等优良特性，使得它可以作为一种 半结构化数据的通用逻辑表示，程序可以很容易地把任何数据源的数据转换为 x m l 格式的数据。因此，x m l 是半结构化数据家族中的代表，对于它的研究具 有重要的价值。 1 5x m l 数据流查询现状 x m l 是一种独特的半结构化数据类型，因此半结构化数据和x m l 之间具有 第1 0 页共5 4 页 复口人学埘l 学位论文 在x m l 数据流 二的模式树匹配备哟 罹著的相似性，半结构化数据己有的理论和原型系统r ，j 以作为x m l 研究的基础。 同时，x m l 特别是x m l 数掘流所具有的独特特性又为我们带来了新的研究课 题。 x m l 数据流处理中，大多数系统均使用基于自动机( a u t o m a t i o n b a s e d ) 的 力法来处理数据流。自动机 h u l 9 7 9 1 吸引人的地方在于它的效率以及设计的简 洁。建造这些x p a t h 查询系统的难点在于如何用把一个或一组x p m h 表达式产生 自动机。 早期大量的x m l 数据流处理工作 a f 2 0 0 0 ，d f f 2 0 0 2 ，c f g + 2 0 0 2 ，g m o + 2 0 0 3 p c 2 0 0 3 ，g s 2 0 0 3 1 主要集中于用x p a t h 表达式过滤一组x m l 文档。这些x p m h 过滤系统可应用于基于内容的x m l 路由( c o n t e n t - b a s e dx m lm u t i n g ) s c g 2 0 0 1 、信息的选择性分发( s e l e c t i v ed i s s e m i n a t i o no fi n f o r m a t i o n ，o rs d i ) i a f 2 0 0 0 ，d f f 2 0 0 2 ，c f g + 2 0 0 2 1 、存储于大型x m l 文件的科学数据的连续查询和 处s $ c d t + 2 0 0 0 ，h f s + 1 9 9 2 ，t d l 9 9 2 】。 没有谓词的x p a t h 表达式本质上是一种正则表达式，这些表达式可以转化为 有限状态自动机( f i n i t es t a t ea u t o m a t a ，o rf s a ) 来接受满足表达式的x m l 文档。 如果f s a 接受了文档，则该过滤系统把文档标识符返回给用户。这些系统不必 缓存文档中的元素。然而，流处理系统如果缺乏缓存能力，就不能查询一般的带 有谓词的x p a t h 表达式。 文献 p c 2 0 0 3 使用懒惰的确定自动机( 1 a z yd e t e m f i n i s t i ca u t o m a t a ) ，使得处 理大量( 1 0 ，0 0 0 - - 1 ，0 0 0 ，0 0 0 ) 的x p a t h 表达式时，自动机的状态数不会爆炸性的 增长。x p u s h 系统 g s 2 0 0 3 使用懒惰的下推自动机( 1 a z yp u s h d o w na u t o m a t a ) ， 使得它即可以控制自动机的状态数目，也可以处理x p a t h 表达式中的谓词。 令两年来，基于自动机的x p a t h 查询系统相继出现。x m l t k 系统 a r g + 2 0 0 2 支持x p a t h 表达式查询，返回x m l 文档的一部分作为结果。所以，它一旦遇到 个元素与查询中的x p a t h 表达式匹配，就把元素输出。然而，如果x p a t h 表达 式包括谰词，则一般情况下，不能立刻确定一个元素是否满足查询条件。x s m 系统 l m p 2 0 0 2 可以处理x p a t h 表达式中的谓词，但是它不能处理“”轴( c l o s u r e a x i s ) 和聚合函数。x s q 系统p c 2 0 0 3 1 使用下推自动机，可以处理包含“”轴、 聚合函数和多个谓词的x p a t h 表达式查询。 1 。6 本文剩余部分内容安排 【第- _ 二章背景和相关工作】对本文所用到的前人所作的成果以及相关领域 的知谚l 背景作概括性的介绍，其中有x m l 的模型和编码方案、模式树匹配、结 构化连接算法。 【第三章x m l 数据流查询系统概述】首先分析面对x m l 数据流查询时呵 第1 1 页共5 4 贞 复u 入学坝卜学位论文 札x m l ，数据流上的模式树匹配查询 能涉及到的关键技术，然后提出x m l 数据流查询系统框架，最后描述查询系统 框架的四个关键数据结构。接下来的三章再讲述查询系统中关键的三个算法。 【第四章x m l 数据流编码方案】首先提出了x m l 数据流模型与编码方案， 然后给出了实现编码的算法。 【第五章s t r e a m i n g t w i gj o i n 算法】针对x m l 数据流查询改进了t w i g j o i n 算法，使之能应用到本查询系统中。 【第六章d e l t ap a t hj o i n 算法】把s t r e a m i n gt w i gj o i n 算法生成的中间结果 连接成最终结果，仔细地分析了相关数据结构和算法过程。 【第七章实现与理论评估】首先讲述实现查询系统的各个算法之问的调度 规则，然后对本文提出的系统与先前的x m l 数据流处理系统进行理论上的比较。 【第八章实验结果与分析】给出了针对本文提出的查询系统和相应的查询 算法的实验结果与分析。从实验可以看出由于利旯 | 了x m l 的结构特征，本文提 出的禽询系统和算法有较好的时间与空间性能。 第1 2 页共鲋页 复口人学坝i 学位论文在x m l 数据流i 的模式树匹配也啕 第二章背景和相关工作 在本章，我们介绍与文本工作密切相关的背景与知识。首先定义模式树匹配 问题，然后讨论x m l 数据模型和编码方案，最后介绍结构化联接算法和加快算法 而引入的些常用索引技术。 2 1 模式树匹配 x m l 查询语言( 例如x q u e r y 、q u i l t 、x m l q l ) 的查询使用( 带标签节点 的) 模式树来匹配x m l 数据库中相关部分的数据。模式树节点标签包含元素的 和j 、签t a g ，属性值对或字符串值。模式树匹配边是父一子边( 用单线表示) 或者 足 h 先一后代边( 用双线表示) 。 例如，如下的两个x p a t h 路径表达式： ( a ) b o o k 【t i t l e = x m l a n d y e a r = 2 0 0 0 】 ( b ) b o o k t i t t l e = 。x m l 1 a u t h o r f l r s t = j a n e a n dl a s t = d o e 】 x p a t h 查询( a ) 的b o o k 元素满足如下要求：1 ) 有一个文本内容为x m l 的t i t l e 子 元素：2 ) 有一个值为2 0 0 0 的属性y e a r 。x p a t h 查询( a ) 可表示为图2 1 ( a ) 中的 模式树，在该模式树中只有父一予边。 b o o k d t l e y e a r i 1 x m l 2 0 0 0 ( a ) b o o k t i t l e l x m l ( b ) j 图2 1 模式树匹配 r a n c l a s t i d o e n x p a t h 垒询( b ) 的b o o k 元素满足如下条件：1 ) a u t h o r 元素有一个子元素f i r s t ，f i r s t 的内容为j a n e 字符串；并且有一+ t ；元素l a s t ，i a s t 的内容为d o e 字符串。2 ) a u t h o r 元素是b o o k 元素的子孙元素；并且b o o k 元素还有一个子元素t i t i e ，t i t l e 的 内容为一x m l ，字符串。x p a t h 查询( b ) 可表示为图2 1 ( b ) 中的模式树。注意，b o o k 第1 3 贝共5 4 页 复【1 人学倾 学位论文 在x m l 数据流上的模式树匹自e 查向 元素! j a u t h o r 元；素之间使用了祖先后代边。 根据f i ；j - 向的例子我们可以说，模式树是在x m l 文档的多个元素卜的谓词选 择。模式树可以表示为一个带有标签的由多个节点组成的树。模式捌与x m l 文 档匹配就是在x m l 文档中找出所有与模式树匹配的模式。下面给出模式树匹配 的形式化定义。 定义2 1 ( 模式树匹配) 当2 5 9 - 一个模式树查询q 和一个x m l 文档d ，q 在d 中的一个匹配就是扶 q 中的查询节点翻d 中的帛点的一个映射并且满憩： i ) 元素节点满足对应的查询节点的谓谪条件： i i ) 元素节点之阃的关系满足对应的查询节点2 闻的结构关系( 父子关系 或褪先一茜代荚系) ， 如果模式树查询q 带有1 1 个查询节点，q 的查询结果可以表示为一个1 3 元数组 ( d 1 d 2 ，d n ) ，数组中的元素由x m l 文档中的满足q 在d 中匹配条件的节 点组成。 例如，图2 1 ( a ) 所示的模式树和图1 1 所示的x m l 文档。该模式树查询在 x m l 文档中有一个匹配，模式树中的查询节点分别映射为x m l 文档的第三个 b o o k 元素、其y e a r 属性- 值对和第一个t i t l e 为根的子树。 2 2x m l 数据模型和编码方案 x m l 数据一般模型化为树结构，树中的节点代表元素、属性或文本，树中 的父予节点对代表x m l 元素之间的嵌套关系。 x m l 奄询算法依赖于x m l 元素的编码方案。x m l 编码方案必须要能反映 x m l 文档树的结构，并且能快速的判断任意两个元素之间的结构关系。 有一种编码方案是对文档中每一个节点赋一个三元组的值( p r e o r d e r ， p o s t o r d e r ，l e v e l n u m ) 【l m 2 0 0 1 ，z n d + 2 0 0 1 ，a j k + 2 0 0 2 】，这三个值这分别是节 点在义档树中的前序编号、后序编号和深度。我们知道按照树的结构特点，只要 知道其前序遍历利后序遍历，就可以还原整棵文档树。 但是为了能支持x m l 文档树的更新，文献 l m 2 0 0 1 提出了可持久的 ( d u r a b l e ) 编码方案，在这个方案里面文档中的每个节点赋一个三元组值 ( s t a r t p o s ，e n d p o s ，l e v e l n u m ) ，其中要求s t a r t p o s e n d p o s ，但s t a r t p o s 和e n d t l o s 同样按照前序遍历和后序遍历排列。s t a r t p o s 值和e n d p o s 值由元素节点在文档树 中的位置决定。这种编码方案称为“区域编码”。 第1 4 页菇5 4 页 复i i 凡学颂卜学位论文 n - x m l 数据流l 的模武树匹配盘询 在区域编码方案中，对于x m l 文档中任意两个不同的元素节点u 、v ： i ) 如果u e n d p o s v s t a r t p o s ，则u 在v 之前； i i ) 如果u s t a r t p o s v s t a r t p o s u e l l d p o s ，则u 是v 的祖先节点； i i i ) 如果v s t a r t p o s u s t a i r t p o s v e n d p o s ，则u 是v 的子孙节点； i v ) 如果v e n d p o s u s t a r t p o s ，则u 在v 之后。 注意，如果h 是v 的祖先节点，并且u 1 e v e l n u m = v 1 e v e l 一1 ，则可以进一步确 定u 是v 的父节点。 陶2 2 举例了一棵经过编码后x m l 文档树，树的根节点a i ( 1 ，1 0 0 ) 处在第1 层，从位置i 跨越到1 0 0 ；它的第一个元素b 1 处在第2 层，位置从2 跨越到1 5 ； 而a 1 的第二个子元素b 4 处在第2 层，从位置2 0 跨越到7 5 。 b 3 ：0 0 ，1 l ，4 ) llb 6 ：( 2 5 ，3 0 ，d ) iic 2 ( 4 1 、4 2 ，4 ) l1 b 8 ：( 4 5 6 0 4 ) b 9 ：( 4 6 4 7 ，5 ji lb i o 。( s 0 ，5 5 ，5 图2 2 ：x m l 文档树编码示意图 注意，任意两个元素之间的区域不可能交叉，但可以覆盖。例如元素a l 的 区域覆盖它的子元素b 1 和b 4 。 2 3 结构化连接算法 如图21 ( b ) ，这么复杂的模式树查询通常是被分解成一组父一子或祖先一后代 第1 5 页共5 4 页 复1 1 人学坝t 。学位论文 在x m l 数据流i ：的模式树匹酣在湖 关系结点对，即：祖先一后代关系( b o o k ，a u t h o r ) 和父一子关系( b o o k ，t i t t l e ) ， ( t i t t l e ，x m l ) ，( a u t h o r ，f i r s t ) ，( f i r s t ，j a n e ) ，( a u t h o r ，l a s t ) ，( 1 a s t ，d o e ) 。 r 是，该查询模式口j 以这样柬完成： 1 ) 在x m l 数据库中匹配卜述分解的二元结构关系； 2 ) 将垒找到的二元结构匹配结果组装( s t i t c h i n g ) 成最终的符合t - 述查询表 达式的完整树结构。 结构化联接算法( s t r u c t u a lj o i n ) 【a j k + 2 0 0 2 c v z + 2 0 0 2 】就是要找到两个 元素序列之间的匹配对序列，这些匹配对满足祖先后代关系或父一子关系。更准 确的说：给定两个输入序列a 1 i s t ( 作为候选前代的序列) 和d l i s t ( 作为候选后 代的序列) ，序列中的每个元素都格式化成( s t a f l p o s ，e n d p o s ，l e v e l ) 的形式， 并且两个序列都按s t a r i p o s 从小到大排序，结构化联接算法的目的是找到所有这 样的匹配对( a i ，d i ) ，满足： 1 ) a i e a l i s t ，d j d l i s t ； 2 ) a i s t a r t p o s ( d j s t a r t p o s a i e n d ，也就是d j 是a j 的后代； 3 ) 如果要求查询父子关系的节点对，则还要满足a i 1 e v e l = d j 1 e v e l 一1 。 如上所述的结构化联接算法，就是文献 a j k + 2 0 0 2 中提出的s t a c k - t r e e 联接算 法。它虽然比文献 z n d + 2 0 0 1 中的多谓词归