（计算机应用技术专业论文）xml更新流的xquery查询处理技术研究.pdf

内蒙古科技大学硕士学位论文 论文题目：茎丛生夏堑速塑圣q 旦皇型查迦丝堡堇查婴究 作者： 路皓 指导教师：登堕壁壑茎 协助指导教师： 单位：鬯茎壹型垫查兰 论文提交日期：2 0 1 0 年0 6 月1 2 日 学位授予单位：内蒙古科技大学 单位： 单位： ，l i 【 x m l 更新流的x q u e r y 查询处理技术研究 r e s e a r c ho nx q u e r yq u e r yo v e rx m l u p d a t es t r e a m s 研究生姓名：路皓 指导教师姓名：张晓琳 内蒙古科技大学信息工程学院 包头0 1 4 0 1 0 ，中国 c a n d i d a t e ：l uh a o s u p e r v i s o r z h a n gx i a o l i n s c h o o lo fi n f o r m a t i o ne n g i n e e r i n g i n n e rm o n g o l i au n i v e r s i t yo fs c i e n c ea n dt e c h n o l o g y b a o t o u0 1 4 0 1 0 ，p 1 l c h d i a 。0一 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 内蒙古科技大学或其他教育机构的学位或证书所使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均己在论文中做了明确的说明并 表示了谢意。 关于论文使用授权的说明 本人完全了解内蒙古科技大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保 存论文。 签名： ( 保密的论文在解密后应遵循此规定) 导师签名：擞畦 橡 日期：21 ：五! ! 圣 内蒙古科技大学硕士学位论文 摘要 随着科学技术的迅猛发展，网络与人们的日常工作学习已经密不可分，人们对 网络的普遍使用促使了很多新生技术的发展。比如w e b 日志、金融分析、网络监控 和安全、传感器网络、电信数据管理、生产制造、图书订阅、位置搜寻、在线拍 卖、股票信息查询等这类密集型的数据的广泛应用，也引起了很多学者的关注，促 使了数据流的查询处理技术的快速发展，同时也引起了研究界的浓厚兴趣。这类数 据的特点是：数据量大，而且流过服务器的速度非常快、数据流是在线到达的、达 到的顺序也是不可控制的，由于其数据量很大，所以无法实现数据的存储，但是相 对数据的不确定性，查询却是持久存储的。显然，可以看出如果利用传统的管理方 式，像管理传统的数据库管理系统一样，对这样类型的数据进行存储，想根据某一 时刻稳定的查询计划得到精确的查询结果，不符合实际需求。这类数据类型并不支 持连续反复的查询，然后连续查询恰恰是数据流的典型特性。x m l 数据流的查询和 管理技术成为目前数据流领域专家们研究的热点问题，这类数据的特点决定了它们 不能用持久稳定关系建模，同时如何高效的为数据流建模也是专家们要解决的关 键。 在i n t e m e t 环境中运行着x m l 数据流得处理系统，在该环境下存在着海量用 户，这些用户利用x q u e r y 语句描述其需求，x q u e r y 语句的核心是x p a t h 式，x m l 流的查询问题主要归结到x p a t h 查询，如何在x q u e r y 中提取x p a t h 式，如何利用 x p a t h 表达式高效的查询x m l 数据流是数据流查询中需要解决的关键问题。将 x m l 更新流的概念引入到x p a t h 查询领域，解决无法进行连续精确查询的问题，这 是课题的主要研究内容。 针对在x m l 流上执行x q u e r y 查询处理，获取精确输出查询结果的问题，结合 了x m l 更新流和x q u e r y 处理技术特点，给出了一种基于x m l 更新流的解决方 案。在x m l 流中动态地插入更新事件，得到x m l 更新流，以达到获取连续精确的 结果。x q u e r y 查询语言在x p a t h 路径查询的基础上使用f l w o r 表达式实现x m l 数据流的复杂查询。将主x p a t h 式进行提取，分出绝对路径和相对路径，把有依赖关 系的路径进行合并，重写f l w o r 表达式，结合自动机技术提高x q u e r y 的查询效 率。实验结果表明，提出的方法能够提高执行效率，得到精确的查询结果。 关键词：x m l 更新流；x o u e r y 查询：x p a t h ； 【卜l、 内蒙古科技大学硕士学位论文 a b s t r a c t w i t ht h ew i d e s p r e a du s eo ft h ei n t e m e t ，s o m en e wd a t a - i n t e n s i v ea p p l i c a t i o n sh a sb e e n w i d e l yr e c o g n i z e d , m a d e dt h e s t r e a md a t ap r o c e s s i n gt e c h n o l o g ya r o u s e dw i d e s p r e a d i n t e r e s t i nt h er e s e a r c hc o m m u n i t y s u c ha sw e db l o g 、f i n a n c i a la n a l y s i s 、n e t w o r k m o n i t o r i n g a n ds e c u r i t y ，s e n s o rn e t w o r k s ，t e l e c o m m u n i c a t i o n sd a t am a n a g e m e n t ， m a n u f a c t u r i n g ，l o c a t i o ns e a r c h ，l o c a t i o ns e a r c h ，s o c ki n f o r m a t i o ni n q u i r ye t c ，w h o s e f e a t u r ei st h a td a t ai sr e a c h i n gq u i c k l yi nt h ef o r mo fac o n t i n u o u sd a t as t r e a mi n u n c o n t r o l l a b l eo r d e ro nl i n ea n dc a nn o tb es t o r e d ，b u tq u e r i e sa r es t o r e dl a s t i n g l y t h i s t y p eo fd a t as t r e a ma p p l i c a t i o nh a sp r o d u c e ds o m en e wp r o b l e m s s ot h et h e o r ya n d t e c h n o l o g ya b o u tt h ex m ld a t as t r e a mm a n a g e m e n ta n dq u e r yh a v eb e c o m et h eh o t r e s e a r c hi nt h ef i e l do fd a t as t r e a mc u r r e n t l y x m ld a t as t r e a mp r o c e s s i n gs y s t e mi sr u n n i n go nt h ei n t e m e t t h eu s e r sa r em a s s i v e i nt h i se n v i r o n m e n t t h e yu s ex q u e r ye x p r e s s i o nt od e s c r i b et h e i rq u e r i e sn e e d s t h ec o r e o ft h ex q u e r ys t a t e m e n ti s a m x m ls t r e a mq u e r yp r o b l e m sm a i n l ya t t r i b u t e dt ot h e x p a t hq u e r y ，h o wt oe x t r a c tt h ex p a t hf o r mt h ex q u e r y , h o wt ou s ex p a t he x p r e s s i o n s e f f i c i e n tq u e r yx m ls t r e a mi st h ek e yi s s u e sf o rt h e x m ls t r e a l t lp r o c e s s i n g i n t r o d u c e dt h e c o n c e p to fx m lu p d a t es t r e a mi n t ot h ex p a t hq u e r yf i e l d , t or e s o l v e dt h ei s s u eo fr e c e i v e c o n t i n u o u sp r e c i s eq u e r ya n s w e r t h i si st h ee m p h a s i so ft h i sp a p e r i nt h i sp a p e r ，a i m e da tr e c e i v ec o n t i n u o u sp r e c i s eq u e r ya n s w e ro v e rt h ex m l s t r e a mx q u e r yq r o c e s s i n g ，c o m b i n a t i o nt h ea t t r i b u t i n so fx m l u p d a t es t r e a ma n dx q u e r y p r o c e s s i n gt e c h n o l o g y ，p r o p o s e das o l u t i o nb a s e do nt h ex m lu p d a t es t r e a m d y n a m i c a l l y i n s e r tt h eu p d a t ee v e n ti n t ot h ex m ls t r e a m , t of o r mx m l u p d a t es t r e a m , s ot h a tw ec a n r e c e i v ec o n t i n u o u sp r e c i s ea n s w e r s x q u e r yb a s e do nx p a t hq u e r i e su s ef l w o r e x p r e s s i o n st oa c h i e v ec o m p l e xq u e r i e so nx m ld a t as t r e a m e x t r a c tm a i np a t hf r o mt h e e x p r e s s i o n s ，s e p a r a t et h ea b s o l u t ep a t ha n dr e l a t i v ep a t h , m e r g et h ep a t hw h i c hh a v e d e p e n d e n c yr e l a t i o n s h i p ，r e w r i t ef l w o re x p r e s s i o n s ，i m p r o v et h ee f f i c i e n c yo fx q u e r y q u e r i e s e x p e r i m e n t a lr e s u l t ss h o wt h a t , o u rm e t h o dc a ni m p r o v et h ee f f i c i e n c yo fx q u e r y q u e r i e s ，g e tt h ep r e c i s er e s u l t s k e yw o r d s ：x m lu p d a t es t r e a m ；x o u e r yq u e r y ；x p a t h ； l。、 内蒙古科技大学硕士学位论文 目录 摘要兽i a b s t r a c t i i 1 绪论1 1 1 背景知识1 1 1 1x m l 发展1 1 1 2x m l 的特点2 1 1 3x m l 语言的研究领域。3 1 1 4x m l 与相关技术【7 引。4 1 1 5x m l 数据流应用5 1 2x m l 数据流的国内外研究现状6 1 3 课题的研究意义及主要研究内容7 2 基础理论1o 2 1 数据流管理系统与数据库管理系统区别lo 2 2x m l 文档及文档树1 1 2 3 m 。数据流1 3 2 3 1x m l 数据流定义1 3 2 3 2x m l 数据流的处理特点1 4 2 4 皿查询规范14 2 4 1x q u e r y 查询语言。1 4 2 4 2x p a t h 查询语言l6 2 5 、，几解析17 2 5 1d o m ( d o c u m e n to b j e c tm o d e l ) 解析l7 2 5 2s a x 解析18 2 5 3s a x 与d o m 的对比。21 3x m l 更新流2 2 3 1x m l 更新流的提出2 4 3 1 1 简单的x m l 数据流2 4 3 1 2 x m l 更新流的定义及结构2 4 3 1 3 x m l 更新流更新过程2 5 3 2 基于x m l 更新流的x q u e r y 的重写2 6 3 2 1 x q u e r y 相关知识介绍2 6 3 2 2 基于x m l 更新流重写x q u e r y 算法步骤2 7 4x 0 u e r y 的查询实现2 9 4 1 上下文无关文法( c o n t e n t f r e eg r a m m a r c f g ) 2 9 4 2 自动机技术理论的概述。2 9 l i 1 | 卜 _ 内蒙古科技大学硕士学位论文 4 2 1n f a ( 非确定的有穷自动机) 3 0 4 2 2d f a ( 确定的有穷自动机) 3 1 4 2 3 非确定有穷自动机n f a 转化成与之等价的确定的有穷自动机d f a 3 2 4 3 基于非确定自动机n f a 的x p a t h 查询处理3 4 4 3 1 问题查询过程的描述。3 4 4 3 2 非确定的有穷自动机n f a 的构造3 4 4 3 3 n f a 的数据结构3 7 4 3 4n f a 的运行4 0 4 4 基于d f a 的x p a t h 查询处理4 0 4 4 1d f a 的数据结构。4 1 4 4 2d f a 的运行4 3 5 实验测试及结果分析4 4 5 1 试验环境4 4 5 2 测试结果及分析4 5 结论4 7 参考文献。4 8 在学研究成果5 2 致谢5 3 内蒙古科技大学硕士学位论文 1 绪论 1 1 背景知识 1 1 1x m l 发展 随着网络技术的迅猛发展，尤其是从上个世纪9 0 年代以来，网络技术的出现，在 极大的程度上改变了当今人发布、获取、使用信息的方式，从以往的看书，读报来获取 信息的方式转变到通过网络方式来获取信息。互联网来为人们提供了一个资源共享以及 信息发布的信息空间的平台，人们逐渐的从信息匮乏的时代跨入到了信息资源非常丰富 的新时代。从另一个角度上看，互联网也面临新的挑战，如何在互联网环境下进行数据 交换和信息共享这些具有分布性、异构性、动态性等特点的海量的信息，值得人们去研 究学习。 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 语言的特点大家也是很熟知的，它不受任何表现形式的约束限 制，平台无关性、可扩展性和简单易用以及自描述等特点，可以由用户自己定义所需要 的标签，能以可读的格式表示数据。用x m l 来定义语言的目的是能够定义计算机和人 都能够识别的数据类型，为程序开发人员和用户提供了便利。x m l 是一种提供描述结 构化数据的格式，提供了一种通用的标准来表示数据，并且也提供了一种独立于应用程 序的方法来实现数据共享，是一种用来描述数据的语言，也是一种新的用来自动描述信 息的标准语它增强了语言信息和结构信息，实现了使计算机可以即时处理多种形式的信 息。然而x m l 是一种元语言( m e t a - l a n g u a g e ) ，本身并不是一个单独的标记语言，是 一种能够创建标记语言的语言。与h r m l 具有固定的格式不同，x m l 可以运行在任何 操作系统中和任何平台之上，具有很强的可扩展性。 在互联网络的快速发展和数据量密集型数据应用的广泛使用，x m l 已成为网络数 据表示和交换的新标准，如今越来越多的信息处理系统都采用x m l 文档作为信息存 储、交换和发布的载体。我们可以看出x m l 类型的数据已成为当前存储和表示数据形 式的主要方式l l 3 j x m l 提供描述结构化数据的格式，是一种用来描述数据的语言。x m l 提供了一种 独立于应用程序的方法来共享数据，它是一种新的用来自动描述信息的标准语言。 x 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 d m a r k u pl a n g u a g e ) ，是用来描述电子文件结构与内容的标记语言，是一种国际标准。它 i 内蒙古科技火学硕士学位论文 能够对各种类型的数据进行描述。s g m l 出现在i n t e m e t 之前。随着i n t e m e t 的出现，人 们开始把s g m l 的运用转移到w e b 上来。但s g m l 是卜卜分复杂的语言格式，用这 种格式描述的数据不利于在网上传输问。 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 最著名的应用，是一种专为网页显示 及浏览而设计的简易标识语言。由于其简单、易学、通用，目前是制作网页的标准语言 格式。但随着网络的发展，在互联网上不仅是为了显示信息，还有很多商务应用。由于 h t m l 有很多限制，如结构上的限制( 标准集是固定的，这些标准的都是定义显示格式 的，h t m l 只能适用于固定而简单的文件结构) 、数据交换的限制、难以扩展、单向的 链接等等，使其在电子数据交换、数据库与搜索引擎等领域的应用存在着障碍。为了解 决这一问题，w 3 c 协会制定了一种新的语言，即可扩展标记语言x m l 。 x m l l 5 】本身并不是一个单独的标记语言，它是一种元语。- 言( m e t a - l a n g u a g e ) ，是一 种能够创建标记语言的语言。标记语言将标记直接插入到文本中来描述文档的各部分。 x 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 是一种元标记语言，x m l 是s g m l 的一个缩减版， 使用x m l 能更容易地定义自己的文件类型，也使程序员能更容易地编写处理这类文件 的程序。它省略了s g m l 中过于复杂的和很少使用的部分，变得更容易使用和理解， 也更适合在网上传递和操作。可以说x m l 提供了一种比s g m l 简单，比h t m l 更广 泛的方法来描述文档内容，使得网上信息的利用达到更高的水平。 1 1 2x m l 的特点 作为一个文档结构化标记语言的x m l 语言，由于其具有良好的数据格式来存储 数据、高度化的结构、强大的可扩展性、在网络传输很便捷等优势，为软件开发人 员开发网页信息和内容创作者在网页上组织信息提供了便利，确保了信息在通过网 络进行交互合作时，使其具有良好的可靠性与互操作性，同时也不断满足增长的网 络应用需求。详细地说，x m l 语言作为一个文档结构化标记语言具有以下主要特 点： 首先，具有易于扩展的语言特点。x m l 语言是摒弃了s g m l 中一些复杂性， 开发人员将其考虑到适合w e b 特性的一个子集，用户可以使用x m l 语言来定义其 它语言，其数据类型类型的数量可以是无限的，用户可以通过自己的需求随意定义 数据的类型。 内蒙古科技入学硕士学位论文 其次，结构性强。强大的结构性主要体现在，x m l 的文件结构嵌套可以复杂到 任意程度，能表示面向对象的等级层次。h t m l 不支持深层的结构描述。 第三，交互性好。用户与应用程序进行交互时，使用x m l 可以非常方便地在 本地进行排序、过滤等其它的数据操作，不需要与服务器进行交互，减轻了服务器 的负担。 第四，语义性强。h t m l 文档是只包括格式和结构的标记。而x m l 可以自己 任意设计有意义的标记，便于异构系统之间的数据交换和信息检索，实现机器问的 信息交换。 第五，自描述性。x m l 文档具有自描述性，具有很强的语义性的特点。x m l 可以自己根据需要任意设计有意义的标记，而不像h t m l 文档是只包括固定格式和 结构的标记。这样x m l 使数据交换和信息检索在异构系统之间的实现提供了便利 条件，同时也实现了不同的机器之间的信息交换。 1 1 3x m l 语言的研究领域 当今随着数据库和网络技术的兴起与广泛使用，x m l 语言在很多领域都得到了 广泛的应用。主要体现在异构系统之间信息的共享与交换、信息检索、w e b 自动 化、x m l 安全的标准、x m l 的应用研究、x m l 文档的数据管理等很多领域，下面 就逐个说明这些领域的应用特点： 1 、异构系统之间信息的共享与交换 在异构系统之间进行交换数据的方法是采用一种统一的信息交换格式。不同的 操作系统平台和不同的数据库系统，应用在相同的企业之间、部门之间，致使共享 信息流通困难。广大用户面临着如何解决异构系统之间的数据交换的问题。程序开 发人员发现x m l 具有自定义性及其可扩展性等优势，便用x m l 来表示各种数据类 型，作为异构数据库之间的中间件，将数据的接口进行了统一，便于信息交换和共 享，在不同的平台之间或者不同的数据库当中。 2 、具有便于信息检索的特点 在网络上都使用过搜索引擎，都会体会到，若是搜索返回的结果很多，就必须 在这些返回的结果中检查自己所需要的适当结果，这样会很浪费时间与经历。x m l 标记弥补了这个缺陷，能够通过用户自己定义的标签很明确地表达了涵义，相同的 关键词和类似的内容可以准确的都能够为，很清楚的知道用户想要表达的意思，和 用户的需要，从而会根据搜索返回适当的用户需要的精确的结果。 3 、w e b 自动化 内蒙古科技大学硕士学位论文 随着w e b 上的内容及应用快速增加，实现w e b 交互操作自动化已经非常必要。当通 过h t m l 形式来进行用户交互操作时，往往由于服务提供者改变了网站布局、向表单中 增加了新的内容或改变了u r l ，使得自动浏览软件出错，更改它们需要花费大量的时 间，) ( m l 则可以解决以上这些问题。 4 、x m l 安全的标准 随着x m l 在电子商务中的广泛应用，如何确保在业务合作者、客户以及供应商之间 传递数据的安全性和可靠性，解决授权和认证机制，将成为重要研究问题。 5 、x m l 的应用研究 在远程医疗、远程教学和电子图书馆等应用中大量的图片、声音、视频等多媒体信 息需要在网络上传输、再现，因此有关基于x m l 的多媒体标准和应用研究需得到深入研 究。 6 、x m l 文档的数据管理 可以把整个x m l 文档看成是一个数据库系统，x m l 文档本身可以看成是数据库中的 数据区，d t d 或者s c h e m a 可以看成是数据库模式设计，s a x 或d o m 可以看成是数据库处 理工具。但是它还是缺少数据库所必须的一些东西，比如有效的存储组织、索引结构、 安全性、事务处理、数据完整性、触发器、多用户处理机制等等。这就需要研究x m l 文 档如何存储、建立索引、查询等相关内容1 6 】。 1 1 4x m l 与相关技术1 7 别 1 、x m l 与面向对象技术 x m l 的a s c i i 对象编码与现有的面向对象方法的结合，使x m l 成为供软件开 发商首选的语言，使得过去在商务过程中长期存在的问题得到解决，主要体现在：1 ) 可以用x m l 解决各种应用之间的数据传送的问题，并且比较容易学习和使用；2 ) 有 助于集成和补充e d i ，能够无需特殊的e d i 翻译程序，在商业e d i 应用之间进行传 送数据；3 ) x m l 和e d i 的组合x m l e d i 为在各种应用之间以一种标准格式定义数 据提供一种方法。 2 、x m l 与j a v a 技术 j a v a 9 】由于具有众所周知的简单、跨平台、安全性和便于网络传输、即时编译引 擎等优点，而成为网络应用软件开发人员的首选开发语言。j a v a 和x m l 技术的结 合促进了新一代w e b 应用的产生，比如电子商务和企业应用程序的集成。目前很多 x m l 解析器和处理工具都是用j a v a 编写的。j a v a 提供了字符串处理、哈希表支 持、u r l 支持等特性，从而成为开发x m l 应用工具的理想语言，而x m l 以其数 据的灵活性和高度可移植性使j a v a 应用中的数据更容易在网络中传输。凡是需要在 少- 内蒙古科技大学硕士学位论文 网络系统中交换数据，如e d i 、电子商务、企业资源管理和供应链管理，x m l 和 j a v a 的结合是最好的选择。 3 、) ( 1 l 与数据库技术 x m l 文档分为两种不同的文档类型：以数据为中心和以文档为中心的文档类 型。以数据为中心的x m l 文档被用来进行数据转换，它们的物理结构往往并不重 要，只作为实体的属性值。要存储和检索这样类型的文档，只需要用关系型或面向 对象数据库来对数据进行存储，同时需要某些数据转换软件，甚至可能还需要w e b 发布能力。在以数据为中心的应用中，在数据库和x m l 文档之间来转换数据需要 使用中间件，中间件可以采用各种语言编写，如采用o d b c 、j d b c 或o l e d b 接 口。而以文档为中心的x m l 文档则包括用户手册、静态w e b 网页、市场宣传资 料，它们的物理结构很重要，且结构不规则，内容复杂。要存储和检索这类x m l 文档，不仅需要数据库外，还需要内容管理的功能。如果要存储内容片段，系统中 还要包括编辑器、版本控制以及从已有的文档片段上构造新文档的能力。目前很多 现有的数据库都增加了对x m l 的支州1 0 】。 1 1 5x m l 数据流应用 在当今的社会中，科学技术的空前发展，随着网络技术的发展和普遍的应用，使得 数据流得到广泛的应用和学者们的大力研究，数据流的是如何产生的、怎样传输及怎么 样才能达到高效的处理，成为近年来社会各界研究的热点问趔1 1 , 1 2 。 1 股票行情自动收录 典型的查询，如股票价格，在线分析涉及到发现相关性，识别趋势，套汇时机和未 来价格预测，最近成交量振荡的最高变更犁1 3 15 1 。 2 传感器网络 传感器网络的应用很广泛，如核电厂异常事件监测，战场士兵方位传感器监控【1 6 1 ， 根据最近电力消耗统计调整发电的速率，化工厂环境温度监控，空气水环境温度监控， 空气水环境质量监控，g p s 定位系统等不同的监控应用系统中。 3 事务日志分析 为了发现某些客户行为模式，鉴别可以消费预示欺诈的行为和预测未来的数据值， w e b 使用同志在线挖掘，电话呼叫记录，自动取款机处理事务等也符合数据流处理模式 特征。实时检查w e b 服务器同志，当主动服务器负载过大时，为用户重新路由至备份 服务器。 4 网络流量分析 内蒙古科技人学硕+ 学位论文 在实时情况下，i n t e m e t 通信l l7 j 量的a d - h o c 分析系统已经应用在流量统计和关键条 件的检测等方面【l8 】，在i n t e r n e t 中，信息源和目的地址的流量模式遵守能量分配规律， 即少量通信量巨大的用户将大多数带宽消耗，查询包括：通信量基数，确定每一个源目 的所使用的带宽数量的总和，并且按协议类型或子网掩码将其分组。在t c p 三次握手 过程中，后来两步逻辑流的组成上对不同的源目的的数量进行比较，如果数量上存在巨 大的差异，则可能会发生服务拒绝攻击。 在很多应用于数据集成当中，包含w e b 服务、个性化内容传送或实时信息的持续 查询等分布式环境中，x m l 语言已经成为了主流的数据交换的标准。用数据流的形式 来表示他的数据。x m l 数据流处理系统的特点是m l 文档的节点一次性地按照某种 遍历的顺序流过，数据到达的顺序是不可能控制的，当接收方接收到x m l 数据流后， 需要对它们即时地解析，并按设定的条件有选择地路由、过滤或转换。面对数据流的是 如何产生的、怎样传输及怎么样才能达到高效的处理，成为近年来社会各界研究的热点 1 9 - 2 2 1 。 1 2 帆数据流的国内夕 研究现状 目前国内外对x m l 数据流查询处理的研究方法有多种，所采用的主要方法是基 于自动机1 2 3 2 5 】的处理方法，其他的有基于索引的方法、基于b l o o m f i l t e r 的方法、 f i s t 方法等。 x f i l t d 冽将有限状态机模型( f i n i t es t a t em a c h i n e ，简称f s m ) 引入x m l 流的过滤 处理。x f i l t e r 对每一个x p a t h 路径查询使用一个单独的f s m ，并在文档处理的过程 中，同时运行所有的f s m 。x f i l t e r 没有考虑相似查询的冗余处理。 y f i l t e r 2 7 】系统是x f i l t e r 的扩展，将所有的x p a t h 表达式合并成为一个单独的 非确定有限状态机( n o n d e t e r m i n i s t i cf i n i t ea u t o m a t o n ，简称n f a ) 并共享所有查询 的公共前缀，实现多个x p a t h 的高效查询处理。y f i l t e r 将t w i n gp a r e r 视为嵌套路 径表达式，并使用查询分解进行处理，在该方法中，当一个查询包含嵌套路径时， 就被分为主路径和一组扩展路径，每一个扩展路径都用一个相对独立的n f a 进行处 理，对它的处理分两步：路径匹配和路径匹配结果的后置处理。针对嵌套路径， y f i l t e r 主要考虑的是具有a n d 谓词的查询，并且这种后置处理的方式可能会产生大 量的中间结果，从而影响系统性能。 x t r i e t 2 8 】是对基于n f a 自动机查询处理的扩展，n f a 自动机每接受一个元素事 件，都查找相关的转换，但x t r i e 在接受元素事件序列之后，才选择相关的处理器进 行响应，减少了接受元素输入序列时可能响应的查询处理器的数量，从而提高了运 行时的处理效率。 内蒙古科技大学硕士学位论文 x p u s h 2 9 】将所有的x p a t h 表达式构造为单个定制的确定下推自动机( x p u s h 机) 。 它主要利用了支持表达路径之间a n d o r 关系的a f a ( a l t e r a t i n gf i n i t ea u t o m a t i o n ) 自动 机。与其他基于自动机的方法一样，随着x p a t h 的增加，状态数目会呈指数级增长。 t o o dj 骶e i l 【3 0 】为保证以持续的高吞吐量处理x m l 数据流上的大量x p a t h 表达 式，提出了在运行阶段建立l a z y d f a ，大大减少了自动机中与查询无关的节点，降低了 自动机的复杂程度，l a z y d f a 是一种有效的处理x m l 数据流上大量x p a t h 表达式的有 效方法，但是对于复杂的x m l 数据这种方法是无效的。 x e b t 3 l 】利用树自动机技术构造查询处理器，它的空间代价要比a f a 自动机要 小，而且还利用d t d 对查询处理器进行了优化，是一种有效的儿数据流上海量 x p a t h 查询的处理方法。 x s i e q t 3 2 】是一种立即计算谓词并即时输出的x m l 流查询处理系统。它利用f j 缀共 享【3 3 j 的方法由多个x p a t h 式构造一个n f a ，并对n f a 状态进行分类和添加索引，使得 在运行时能快速确定谓词计算和数据缓存等的时机，x s i e q 还提供在运行时隋性地构造 d f a 3 4 进行查询，不过多重匹配的发生将极大地降低x s i e q 的查询效率流查询。 其他处理x m l 数据流的方法主要基于索引的方法、基于b l o o mf i l t e r 的方法以及 f i s t 方法。i n d e x - f i l t e r 3 5 】采用基于索引的技术处理x m l 数据流，它利用x m l 文档流 的文档标记动态地建立x m l 文档的索引，从而避免处理一部分x m l 文档。与y f i l t e r 相比，通过实验表明：当查询数量相对较小、x m l 文档相对较大时，i n d e x - f i l t e r 更有 效；当查询数量相对较大、x m l 文档相对较小时，y f i l t e r 更有效。基于b l o o mf i l t i e 一3 6 j 的x m l 包过滤器是一种近似查询方法，利用b l o o mf i l t e r 将x p a t h 表达式作为字符 串，将x p a t h 与x m l 包之间的匹配转换为字符串之间的匹配，从而提高查询性能，它 只是用来处理简单的x p a t h 表达式，并且有一定的失误率。f i s t 3 7 1 针对t w i n gp a t t e r n 提出一种有别于y f i l t e r 的方法，将一组t w i n gp a t t e m 转换为p r u f e r 序列，并对一组 t w i n gp a t t e r n 与x m l 数据流进行整体匹配。f i s t 考虑的是具有a n d 谓词的t w i n g p a t t e m ，而没有考虑如何处理o r 谓哥弼圳j 。 这些方法在处理简单的x p a t h 时有很好的效果，但是只能获得近似精确的查询结 果，本文在总结以上方法的基础上，在x m l 数据流的基础上构造了x m l 更新流，对 x q u e r y 表达式进行重写，提取出主x p a t h ，结合自动机的技术，完成了对数据流的查 询处理工作，解决了不能得到连续查询，精确结果的问题。 1 3 课题的研究意义及主要研究内容 x m l 是一种标识语言，它允许用户自定义标签并且具有的数据结构特性是半结构 化的。对数据进行数据描述利用元素或标签，能够在不同的系统平台上运行，具有很强 内蒙古科技大学硕士学位论文 大的可扩充性与自我表述能力。它的出现很好地解决了系统不兼容的问题。因此当今业 界最重要的数据储存与交换的文件标准格式非x m l 莫属。x m l 也自然地成为了一种 标准。 i n t e m e t 环境中海量用户利用x q u e r y 语句和x p a t h 语句描述需求，保存到系统 中，这一阶段称为订购；当x m l 数据以网络速度流入时，系统判断x m l 数据流是 否满足某个用户需求，如果满足，则触发应用程序采取某种动作，如向用户返回相 应文档，这个阶段称为发布。如何在x m l 数据流上高效地执行大量的x p a t h 查询 成为主动服务实现的关键问题之一。 数据流的实际数据量大小无法事前得知，数据是不断产生的，因此用户无法预 知要来到的数据将会有多大，而且只能进行单遍地处理。也无法重新处理己流过去 的数据，只能进行单边扫描，要求极高的实时处理操作，存储很小很小的一部分的 数据，所以对传统的数据库系统的操作方式已经无法满足这种数据流的处理方式 4 1 1 0 解决x m l 数据流上海量查询问题，目前所采用主要的方法是基于自动机的方 法、基于索引的方法、基于b l o o m f i l t e r 的方法、f i s t 方法等。这些方法在处理简单 的x p a t h 时有很好的效果，但是只能获得近似精确的查询结果，本文在总结以上方 法的基础上，在x m l 数据流的基础上构造了x m l 更新流，对x q u e r y 表达式进行 重写，提取出主x p a t h ，结合自动机的技术，完成了对数据流的查询处理工作，解 决了不能得到连续查询，精确结果的问题。 论文的主要工作为： 1 对x m l 文档进行解析，形成x m l 事件流。 2 在x m l 事件流中添加标签，构造成x m l 更新流。 3 对x o u e r y 表达式进行重写，提取出主x p a t h 式和谓词。 4 根据提取出的x p a t h 式，利用自动机技术建立相应的处理模块。 5 建立n f a 和d f a 的数据结构。 6 x m l 更新事件作为自动机的输入驱动自动机n f a 和d f a 的运行。 7 通过试验对系统性能进行测试，并在时间和内存的消耗上进行比较。 论文的组织结构 第一章背景知识。介绍了与x m l 语言相关的理论背景知识，x m l 数据 流处理技术研究的必要性和当前国内外研究现状。 第二章基础理论。概述了x m l 数据管理技术的特点，介绍了x m l 数 据流的相关