（计算机应用技术专业论文）基于结构索引的xml数据流的xpath查询技术研究.pdf

j 。 、7 内蒙古科技大学硕士学位论文 舢1 l | l i l l | l l l i i l l 1 1 1 1 1 1 1 1 1 | l y 17 8 9 5 3 8 论文题目：基于结构索引的龇数据流的舭查询技术研究 作者：陈向阳 指导教师：鲞堕堡垫壑 协助指导教师= _ 单位：哮古科技大学 论文提交日期：2 0 1 0 年弓月，五日 学位授予单位：内蒙古科技大学 单位： 单位： 基于结构索引的x m l 数据流的x p a t h 查询技术研究 x p a t h q u e r y i n gt e c h n o l o g yr e s e a r c hb a s e ds t r u c t u r e i n d e xo fx m ld a t as t r e a m 研究生姓名：陈向阳 指导教师姓名：张晓琳 内蒙古科技大学信息工程学院 包头0 1 4 0 1 0 ，中国 c a n d i d a t e ：c h e n x i a n g - y a n g 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 d t e c h n o l o g y b a o t o u0 1 4 0 l o ，p r c h i n a 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 内蒙古科技大学或其他教育机构的学位或证书所使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并 表示了谢意。 签名：氆：鱼2 叠日期：坦! ! ：! 兰 关于论文使用授权的说明 本人完全了解内蒙古科技大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保 存论文。 ( 保密的论文在解密后应遵循此规定) 签名：血：鱼壁垒导师签名：型建盘 日期：缈参1 2 - 内蒙占科技人学硕十一学位论文 摘要 近年来，随着w w w 的迅猛发展，x m l 成为数据交换事实上的标准，x m i 数据的 应用也越来越广泛。例如：会融服务，网络监控，安全，电信数据管理，w e b 应用， 牛产制造，传感，t 一, 。：h 、p 。l 等。基于x l 的半结构化数据管理的研究已成为越来越热门的 研究课题。查询优化足研究的重要内容，而建立合适的x m l 索引技术义成为研究的 关键。为x m l 。建立较小的索引是提高x m l 查询的有效手段。它们的特征是：数据以 大量、快速、实时的数据流形式持续在线到达，数据到达的顺序不可控制、无法存 储、而查询持久存储。在这些应用。 | ，如果利用传统数据库管理系统的方式管理， 把数据存储，在某- n 执行稳定的奁询计划给出精确的回答，显然是不可能的，不 切合实际的，因为它并不支持连续查询，而连续查洵币是数据流的典型特征。因 此，这类数据不宜用持久稳定关系建模，适宜用数据流建模，由此产生了一些新的 研究问题，因此，x m l 数掘流查洵和管理技术成为目自于数据流领域研究的热点。 x m l 数据流处理系统运行在i n t e r n e t 环境中，该环境下存在海量用户，这些用 户利用x p a t h 语句描述其需求，因此，x m l 数据流的查询问题主要归结到x p a t h 查 询，如何利用x p a t h 表达式高效的查询x m l 数据流是数据流查询中需要解决的关键 问题。本文根据x m i 。文档的s c h e m a 获取它的文档结构建立较小的结构索引，把带谓 词的x p a t h 查询分成两步完成，第一步利用结构索引预处理完成x p a t h 的路径匹 配，第二步当x l 数据流流过时利用路径匹配的结构索引处理谓词，完成查询。这 是本文的主要研究内容。 本文结合结构索引和预处理技术，实现了对带谓词的x p a t h 表达式的查询处 理。从理论上分析，结构索引和预处理技术能够提高x m l 数据流的查询效率。实验 结果表明，该算法可以有效地提高带谓词的x p a t h 的查询效率。 关键词：x m l 数据流；结构索引：x p a t h 毋 内蒙古科技大学硕士学位论文 目录 摘要i a b s t r a c t i i 1 绪论1 1 1x m l 的发展及特点1 1 2x m l 的相关技术3 1 3x m l 数据流的应用4 1 4 研究的现实意义。4 1 5 国内外研究现状5 1 6 课题的主要工作。8 2 背景知识：1 0 2 1 数据库管理系统与数据流管理系统1 0 2 1 1 数据流管理系统与数据库管理系统的区别1 0 2 1 2 数据流管理系统必须具备的功能1 1 2 2x m l 流1l 2 2 1x m l 文档及文档树1 1 2 2 2x m l 数据流的定义1 3 2 2 3x m l 数据流处理的特点1 3 2 3x m l 解析器1 4 2 3 1d o m 1 4 2 3 2s a x 15 2 3 3s a x 与d o m 的对比15 2 4x m l 查询规范1 5 2 4 1x p a t h 16 2 4 2x q u e r y 17 3 基于x m l 的结构索引1 9 3 1 结构索引的方法及特点1 9 3 2 结构索引的潜在优势1 9 3 3 基于x m l 文档的索引机制的改良1 9 内蒙古科技大学硕士学位论文 3 4 基于x m l 文档s c h e m a 的结构索引2 0 3 4 1x m l 文档s c h e m a 的定义。2 0 3 4 2x m ls c h e m a 规范及其组成部分2 0 3 4 3x m ls c h e m a 的特点2 2 3 4 4x m ls c h e m a 应用及前景。2 3 3 4 5x m ls c h e m a 实例和符合) a 也s c h e m a 的文档2 3 3 4 6x m ls c h e m a 得到的结构索引2 5 3 5 本章小结2 5 4 带谓词的x p a t h 查询处理。2 6 4 1 数据流处理模型2 6 4 2 解决问题的基本思想2 7 4 3 预处理x p a t h 查询的路径匹配2 7 4 4s a x 事件流2 9 4 4 1s a x 解析2 9 4 4 2s a x 解析器的特点和优点。3 2 4 4 3s a x 事件流类型3 2 4 5 用结构索引处理x m l 数据流3 6 。 4 5 1 用结构索引处理礼数据流的的过程。3 6 4 5 2 用结构索引处理x 札数据流的实例3 9 4 6 本章小结4 0 5 试验测试和结果分析。4 1 5 1 实验环境4 1 5 2 测试结果及分析4 2 5 3 本章小结4 2 6 结论z 1 3 参考文献4 4 在学研究成果4 8 霉| 【谢。4 9 2 内蒙古科技大学硕士学位论文 1 绪论 1 1 。的发展及特点 x m l j ( 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 具有自描述性、平台无关性、可扩展性和简单易用等的特点，能以可读的格 式表示数据而不受表现形式的限制。 随着i n t e r n e t 的快速发展，尤其是电子商务、w e b 服务等应用的广泛使用，x m l 已 成为w e b 数据表示和交换的新标准，越来越多的信息处理系统采用x m l 文档作为信息存 储、交换和发布的载体，x m l 类型的数据已成为当前主流的数据形式。与此同时，x m l 应用领域也出现了一些值得关注的新情况，x m l 数据查询技术成为了当前的研究热点， 这些情况给x m l 索引与查询优化技术提出了严峻的挑战。 自从上世纪9 0 年代以来，w w w 技术的出现极大地改变了人们发布、获取、使用信 息的方式，i n t e r n e t 成为了一个拥有巨大信息资源的、开放的、分布的信息空间，人 们从信息缺乏进入到信息极大丰富的年代。而从另一角度，i n t e r n e t 所固有的海量数 据的分布性、异构性、动态性等特点也对互联网环境下的数据交换和信息共享提出了新 的挑战。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 儿提供描述结构化数据的格式，是一种用来描述数据的语言。x m l 提供了一 种独立于应用程序的方法来共享数据，它是一种新的用来自动描述信息的标准语言。 x 札提供了一种通用的标准来表现数据，能增加结构和语义信息，使得计算机可以即时 处理多种形式的信息。 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 pl a n g u a g e ) ，它是一种用来描述数据的标记语 言，出现在x m l 语言之前，它是用来描述电子文件结构与内容的标记语言，是一种国际 标准。它能够对各种各样的类型的数据进行描述。s g m l 在i n t e r n e t 出现以前就已经有 了。随着i n t e r n e t 的出现，人们开始把s g m l 的运用转移到w e b 上来。但是s g m l 是个 僦大而且复杂的语言格式，用这种格式描述的数据不利于在网上传输。 s g m l 最著名的应用是h i 3 i l ( h y p e r t e x tm a r k u pl a n g u a g e ) ，它是一种专为网页显示 及浏览而设计的简易标识语言。由于其简单、易学、通用，目前是制作网页的标准语言 格式。但随着网络的发展，在互联网上不仅仅为了显示信息，还需要逐渐转向商务应 用。但由于h t 儿有很多的限制，例如，结构上的限制( 标准集是固定的，这些标准的都 是定义显示格式的，因此，h t m l 只能适用于固定而简单的文件结构、数据交换的限 制、难以扩展、单向的链接等等，使其在电子数据交换、数据库与搜索引擎等领域的应 内蒙古科技大学硕士学位论文 用存在着障碍) 。为了解决这一问题，w 3 c 协会制定了一种新的语言，即可扩展标记语 言x m l 。 确切地讲，x m l 本身并不是一个单独的标记语言，它是一种元语言( 艇t a _ l a n g u a g e ) ，是一种能够创建标记语言的语言。标记语言将标记直接插入到文本中来描 述文档的各部分。x m l 能够运行在任何平台和操作系统上。它的可扩展性表现在它并不 像h t 儿那样有固定的格式。 由于m 札有固定的格式，使它缺少了灵活性，极大的限制了能够描述的数据类 型。m 札的优势是连接文本和显示内容，用h t m l 来处理信息就有些力不从心。h t m l 是 一种特殊化的标记语言，x m l 是一种元标记语言，x m l 是s g m l 的一个缩减版，使用x m l 能更容易地定义自己的文件类型，同时也使程序员能更容易地编写处理这类文件的程 序。它省略了s g 儿中过于复杂的和很少使用的部分，变得更容易使用和理解，也更适 合在网上传递和操作。可以说x m l 提供了一种比s g m l 简单，比h t m l 更广泛的方法来描 述文档内容，使得网上信息的利用达到更高的水平。 由于x m l 是一个文档结构化标记语言，所以它强调元素顺序的作用，而大多数据模 型都不考虑顺序。为了把x d l 应用到数据集成和交换，目前已经有许多数据库研究人员 参与x b t l 相关标准的制定和修改。 ) 强也具有以下主要特点【2 】： 第一，易于扩展。h t m l 是符合s g m l 语法的一种固定格式的超文本标记语言，因其 格式固定，标记有限，故难以扩展。而) 强也摒弃了s c 4 i l 中的一些复杂性并考虑到适合 w e b 特性的一个子集，可以用来定义其它语言，同时x m l 的标记是用户定义的，从理论 上讲，其类型的数量可以是无限的。 第二，结构性强。h t m l 不支持深层的结构描述，而x m l 的文件结构嵌套可以复杂 到任意程度，能表示面向对象的等级层次。 第三，交互性好。用户与应用进行交互时，使用x i d l 可以非常方便地在本地排序、 过滤和进行其它的数据操作，不需要与服务器进行交互，减轻了服务器的负担。 第四，语义性强。f i t m l 文档只是包括格式和结构的标记。而x d 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 已经成为新一代网络数据表示、传递和交换的标准，i n t e r n e t 内蒙古科技大学硕士学位论文 环境中跨平台的、依赖于内容的技术，其应用已经渗透到与网络数据处理相关的各个领 域。通过对信息加上标记，不同种类的数据都可以用x m l 格式来表示，不论数据是结 构化的关系表，还是半结构化的文档，或者是来自某数据源的数据流，i n t e r n e t 上越 来越多的信息将以x m l 的形式存储、交换和表示。从存储在不同介质上的数据自动生 成x 虬文档的能力，以及在不同的存储形式之间以x 地格式交换信息的能力，将成为 未来i n t e r n e t 应用的关键。 1 2x m l 的相关技术 1 、) ( m l 与面向对象技术 x 地的a s c ii 对象编码与现有的对象方法的结合，将使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 虬e d i 为在各种应用之间以一种标准格式定义数据提供一种方法。 2 、x m l 与j a v a 技术 j a v a 由于众所周知的简单、跨平台、安全性和便于网络传输、即时编译引擎等优 点，而成为网络应用软件开发的首选。j a v a 和x 儿技术的结合促进了新一代w e b 应用 的诞生，比如电子商务和企业应用程序的集成。目前很多x m l 分析器和处理工具都是用 j a v a 编写的。j a v a 提供了字符串处理、哈希表支持、u r l 支持等特性，从而成为开发 ，x m l 应用工具的理想语言，。而x 札以其数据的灵活性和高度可移植性使j a v a 应用中的 数据更容易在网络中传输。只要是需要在网络系统中交换的数据，例如e d i 、电子商 务、企业资源管理和供应链管理，瑚l 和j a v a 的结合就是最好的选择。 3 、x m 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 接口。而以文档为中心的) 眦文档则包括用户手册、静态w e b 网页、市 场宣传资料，它们的物理结构很重要，且结构不规则，内容复杂。要存储和检索这类 瑚l 文档，除了需要数据库外，还需要内容管理功能。如果要存储内容片段，系统中还 要包括编辑器、版本控制以及在已有的文档片段上构造新文档的能力。目前很多现有的 数据库都加了对x m l 的支持网。 内蒙古科技人学硕士学位论文 1 3n i v i l 数据流的应用 在包含w e b 服务、应用与数据集成、个性化内容传送或实时信息的持续查询等分布 式环境中，x m l 作为主流的数据交换标准，它的数据是以流的形式存在的。x m l 数据流 处理系统的特点是不可能控制数据到达的顺序，即x m l 文档的节点一次性地按照某种遍 历的顺序流过，当接收方接收到x m l 数据流后，需要对它们即时地解析，并按设定的条 件有选择地路由、过滤或者是转换。面对x m l 数据流高速地产生、传输，如何高效、安 全地处理这些数据成为近年来的研究热点【4 2 1 1 。 1 4 研究的现实意义 随着i n t e r n e t 以及密集型数据应用的发展，产生了大量待处理的实时数据，例 如：传感器数据位置跟踪，网络监测数据，工厂装配线管理，金融数据，w e b 使用日志 及点击流和电话呼叫记录等。这些实时数据具有连续性、数据量极大、生成速度快和生 成速率随时间变换等特点，这些应用背景中信息按照数据值序列的形式自然产生，而对 这些数据的处理又要求能够做到连续不间断的、实时的连续查询。在有限的内存和处理 器资源的情况下，保证这些实时数据能够快速、有效的处理变的越来越重要。传统的关 系数据库管理系统在处理有限的存储数据方面是高效的，但是，处理此类数据则显得效 率低下，甚至无法处理。因此，一些实时处理大规模数据的新方法，成为目前数据库领 域研究的新热点。 可扩展标记语言x m l 作为s g 儿的精简子集，是一种简单、灵活的的文本格式，x m l 继承了s g m l 可扩展、自描述和简明性的特性，能轻松地表示表格式数据( 如数据库中 的关系数据或电子表格) 和半结构化数据( 如w e b 页面或业务文档) 。它不依赖于任何 编程语言、操作系统或软件供应商，可以提供对各种数据处理、构建、转换和查询技术 的访问。经过多年的发展和应用，x m l 强大的数据表达能力及其内容与表示分离的特 性，使得它成为目前互联网上通用的数据表示和交换格式。制定x m l 技术规范标准的 1 3 c 在1 9 9 9 年推出了x m l 文档寻址语言x p a t h l 0 。 ( p a t h 使用路径表达式来选择x l v i l 文档中的n o d e s ( 节点) 或是n o d e - s e t ( 节点集) 。x p a t h 的出现给x m l 文档的查询提 出了规范，也使得x l v i l 流查询的重点转移到对x a d a t h 表达式的处理上。 以主动服务为例来说明x m l 数据流上海量查询处理的应用背景，主动服务系统 是近几年来提出的建立在w e b 服务技术规范之上的新的服务模型。主动服务能够根 据用户的个性化要求和特点，对服务进行定制和帮助，从而实现根据用户需要而动 态变化、主动适应用户的要求。主动服务的一个典型应用是目前被广泛应用的订购 和发布系统，海量x m l 数据的x p a t h 查询问题是它其中的关键技术之一。在订购阶 段，用户利用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 查询越来越引起人们的重视。本文针对x m l 数据流上带谓词的 x p a t h 查询处理以及查询优化问题，给出先预处理完成x p a t h 查询的路径匹配部分，然 后再完成谓词匹配的解决方案。为了提高查询处理效率，本文提出了利用x m l 文档的结 构信息建立结构索引，用结构索引预处理) ( p a t h 查询的结构向导部分，得到路径匹配的 结构索引，然后用路径匹配的结构索引处理x m l 数据流，完成x p a t h 查询谓词的匹配。 1 5 国内外研究现状 利用索引技术来优化x m l 的查询，这几年得到了一定的发展，一些索引技术相继被 提出，例如d a t e g u i d e s ，卜i n d e x e s ，2 - i n d e x e s 和t i n d e x e s ，r e v e r s e d d a t e g u i d e s ， l o r e 索引，i n d e xf a b r c ，t o x i n ，x i s s 。 文献印的d a t a g u l d e s 是从根节点为起始的精练路径的一种结构摘要。边标签串联 在一起形成的字符串路径在d a t a g u l d e s 中只描述一次。d a t a g u i d e s 减少了遍历路径查 询时所需的部分节点，它对从根部遍历) a 札文档是有效的。然而，由于它不能提供关于 结点之间父子或者祖先后代关系的任何结构信息，因此它不使用于一般的从任意结点为 开始的查询，构建索引的时间和空间开销都较大。 文献四】中的t - i n d e x 是特定的路径索引，它不是对所有的路径建立索引，而仅仅对 有限的路径抽取结构摘要信息来建立索引。卜i n d e x 和2 - i n d e x 是t - i n d e x 的特定情 况。 文献即中的l o r e 索引通过采用两个附加的索引结构b i n d e x 和l i n d e x 向前向后遍 历来解决d a t a g u l d e s 中的一些问题。l o r e 索引由四个索引结构组成，它们是值索引 ( v i n d e x ) 一用于查找具有入边并且满足查询条件的所有原子对象；标签索引( l i n d e x ) 一 用于查找己知节点的父亲节点；边索引( b i n d e x ) 一用于查找由一标签连接起来的父子节 点对；路径索引( p i n d e x ) 。 l o r e 索引相对来说是一种比较成熟和比较完善的索引系统。但是，这些索引和 d a t a g u i d e s 一样没有采用数据树结构信息。尽管这些索引结构减少了指针转移操作的 次数，但是路径信息的缺乏在向前和向后搜索时产生了大量的冗余数据，从而造成查询 代价较大。 文献圈中的i n d e xf a b r i e 索引是在p a t r i e i at r e e 基础上采用关键字压缩机制 来为大量的字符串建立索引，它通过前缀编码的方式将r a w p a t h 和r e f i n e d p a t h 编码 成字符串，然后插入到索引中。i n d e x f a b r i c 索引树是一种平衡树，对索引的所有访 内蒙古科技大学硕士学位论文 问都只需要同样小的i 0 资源。在检索i n d e x f a b r i c 索引时，从最左边的水平层的根 节点开始，在一个块内部，沿着这些边将所要查找的字符串与边标签进行比较，如果带 标签的边是远程连接，搜索处理就向右在下一层的某一个不同块中进行查找，如果没有 带标签的边与所要查询的关键字字符串相匹配，搜索处理就沿着非标签边到下一层中一 个新的块中进行查找。查询处理就这样一层一层地进行查询，直到最底层即o 层。在0 层中进行搜索期间，如果没有标签边与所要查找的字符串相匹配，则该关键字的索引就 不存在。否则，顺着路径就能够找到该关键字字符串。 i n d e xf a b r i c 索引结构适合于以文档根结点为起点的路径查询，而其它路径查询 则要求查询多个索引或要经过一个预处理。为了弥补这个不足，它提出了精确路径的概 念。然而在利用索引进行查询之前，这种精确路径要经过多次预选择。 文献闭中的t o x i n 索引完全采用了数据图的全部路径结构信息，它适用于从任何节 点开始的向前和向后搜索。t o x i n 由两种不同的索引结构组成，v a l u e i n d e x 和 p a t h i n d e x ，p a t h i n d e x 由i n d e xt r e e 和实例函数集组成， i n d e xt r e e 是一种最小化 的d a t a g u l d e s ，实例函数集是与索引树中的边一一对应的，它用来记录节点对之间的 父子关系。 为了快速确定元素之间的关系，文献f 7 】提出了n u m b e r i n gs c h e m a 的概念，并在此 基础上提出了一个新的索引和存储x m l 数据的系统，叫做x i s s 系统。n u m b e r i n g s c h e m a 能够快速地确定元素和( 或) 属性之间的祖先后代关系，x i s s 系统能够有效地 找到同名字符串的元素和属性，x i s s 系统的索引结构主要由三部分组成，即e l e m e n t i n d e x ，a t t r i b u t ei n d e x 和s t r u c t u r ei n d e x 。 ， x i s s z s 系统，虽然利用了n u m b e r i n gs c h e m a 的能够快速地确定元素和( 或) 属性 之间的祖先后代关系，但是该索引系统所采用的n u m b e r i n gs c h e m a 的 对 中的o r d e r 和s i z e 值都是任意的整数，这样不便于为以后插入的元素分配 值。另外，一些重复出现的元素会在n a m ei n d e x 和e l e m e n ti n d e x 以及 a t t r i b u t ei n d e x 中重复建立索引、重复存储，这样会浪费存储空间、增加检索时间的 同时，降低了检索的效率。 随着索引技术以及n u m b e r i n gs c h e m a 的发展，人们在这些技术基础上相继提出了 一些) 。元素之间的连接算法。 文酬驯研究了如何处理树结点匹配的各种问题，但是这种算法的时间复杂度太高， 因为它假设整个树总是驻留在内存中。 文献【3 0 中j a c o b s o n 等人提出计算一个列表中的元素是否是另一个列表中一些元素 的后代或祖先的一种合并算法，但这种合并算法主要用于w e b 上或u n ix 类型的文件系 统上的基于关键字的搜索。 内蒙古科技大学硕士学位论文 文酬3 i 】中j a g a d i s h 等人提出一种基于栈的算法，该算法用来计算一个列表中的元 素是否通过一个分层集合选择条件与另一个列表中的元素相匹配。但是这种算法仅适用 于字典数据模型。 文献【3 2 】提出了x 儿数据元素位置的表示方式，还考虑了用p a t 文本的片断来为文本 的数据库建立索引，并且还讨论了对a l g e b r a 的优化技术。但是所做的工作仅仅是理论 上的研究，没有提出一种计算煳l 元素之间关系的有效算法。 文献【3 3 】中的z h a n g 等人就利用n u m b e r i n gs c h e m a 的优点，提出了执行约束查询的 多个谓词合并算法( 肝m g ：i n ) ，该算法用于查找所有的基本结构关系。他们用两种原生 的数据库系统比较了约束查询的效果，结果证明了m p m g j n 算法优于标准的r d b m s 连接 算法。 文献州的s t a c k - t r e e - n e s c 连接算法充分利用了( d o c i d ，s t a r t p o s ：e n d p o s ， l e v e l n u m ) 表示x m l 元素的位置，( d o c l d ，e n d p o s ，l e v e l n u m ) 代表了字符串的位 置，是二种新颖的匹配结构关系的优化的连接算法。它代表了结构连接算法的先进水 平，它假设每个元素列表都按照s t a r t 值的顺序来进行存储，并且它还引进了栈的机制 来存放要连接的元素。虽然s t a c k - t r e e - d e s c 连接算法代表了结构连接算法的先进水 平，但是它没有利用索引结构而是顺序浏览输入列表。这样，浏览大量不参加连接的元 素必然浪费i o 资源，影响连接的速度。 综上所述，索引技术在如何加速查询方面做了大量的工作，x m ls c h e m a 作为一种 描述x m l 文档模式信息即结构信息的标准，对于) 强也索引的建立及查询效率的提高有着 重要的作用。本文提出了一种基于s c h e m a 的删l 文档的结构索引，提高了查询效率。 建立了较小的索引后，对于带谓词的) ( p a t h 查询一直是研究的难点，基本的) a 也流 查询条件是一组) ( p a t h 式。一个x p a t h 式是对瑚l 文档节点进行定位的一个字符串，并 且可能包含对节点的谓词选择条件。x p a t h 式中去除谓词后剩余的部分称为主x p a t h 式，它确定x m l 查询匹配的候选结果节点。x p a t h 中谓词的存在使得查询的难度大大提 高，近年来对带谓词的) ( p a t h 查询算法主要有：x p u s h ，x s i e q ，x t r i e ，y f i l t e r 。 x p u s h d f l 使用修改了的p d a ，通过自底向上的计算对满足谓词的状态进行转换，到 文档解析结束时根据最终匹配的状态集得到查询结果。x p u s h 解决了n f a 自动机的表达 能力问题。这一扩展主要利用了支持表达路径之间a n d o r 关系的a f a ( a i t e r n a t i n g f i n i t ea u t o m a t o n ) 自动机，a f a 自动机利用扩展的状态来保存不同路径的执行情况。 ) ( p u s h 执行器也是基于确定化自动机，提高了系统的查询效率，但是自动机的确定化操 作同样也面临指数级别空间代价的问题。 x s i e o t j o j ( x 札s t r e a mq u e r yw i t hi m m e d i a t ee v a l u a t i o n ) 旨在建立一套高效的、 能立即计算谓词并即时输出的x m l 流查询引擎。当前，x s i e o 支持x p a t h 式的孩子、子 内蒙古科技大学硕士学位论文 孙、自身和属性轴，支持含相对x p a t h 式的复杂谓词( 包括嵌套谓词) 。x s i e q 采用索引 技术和缓冲机制，通过构造p d a 实现谓词的立即计算和查询结果的即时输出。x s i e q 根 据要查询的x p a t h 式构造自动机。为支持谓词，x s i e q 使用带栈的n f a ，即下推自动机 ( p d a ) 。x s i e o 通过前缀共享构造n f a ，解决了x p a t h 式状态共享问题；然而，查询中可 能存在大量相同的谓词计算，并且，对于含有多个谓词的查询，谓词计算仍是影响性能 的瓶颈。 x t r i e l 3 7 1 提出了只包含父子关系的子路径表达式的索引机制，并使用索引机制提取 多个查询的公共子路径，实现包含谓词逻辑的x p a t h 处理，x t r i e 是对基于n f a 自动机 的查询处理的一种扩展，n f a 自动机每接受一个元素事件，都查找相关的转换，但是 x t r i e 在接受元素事件序列之后，才选择相关的处理器进行响应。一般而言，响应元素 序列的x p a t h 处理机比响应单一元素的x p a t h 处理机要少得多。通过这种方式，x t r i e 减少了接受元素输入序列的查询处理机的数量，从而提高了运行时刻的处理效率。 y f il t e r 脚j 是对x f il t e r 的扩展，y f il t e r 将多个x p a t h 查询表达式合并成为一个 单独的非确定有限状态自动机( n f a ，n o n - d e t e r m i n i s t i cf i n i t e a u t o m a t o n ) ，实现多个 x p a t h 的高效查询处理；在解析x 儿时缓存所有的候选结果和谓词匹配的节点；在解析 结束后通过后续处理得到最终的查询结果。y f i l t e r 不支持在解析x m l 时立即计算谓词 并输出结果，不适合实时性要求高的应用场合。 本文在对带谓词的x p a t h 查询上采取先预处理x p a t h 的路径部分，然后在x m l 数据 流流过时处理谓词的方法。在根据) 口札文档的s c h e m a 获取它的文档结构得到结构索引 的基础上，利用结构索引( 像x 儿文档树一样) 来预处理x p a t h 查询的结构向导部分， 它将尝试找到查询的结构部分和x 扎文档树匹配的所有路径，然后每一个结构匹配的结 果被储存在索引结点中，得到带路径匹配的结构索引，然后用带路径匹配的结构索引处 理x m l 数据流完成谓词的匹配查询。 1 6 课题的主要工作 随着i n t e r n e t 的快速发展，尤其是电子商务、w e b 服务技术等的广泛使用，x m l 已 成为w e b 数据表示和交换的新标准，越来越多的信息处理系统采用x m l 文档作为信息存 储、交换和发布的载体，x 儿类型的数据已成为当前主流的数据形式。与此同时，x m l 应用领域也出现了一些值得关注的新情况，x m l 数据查询技术成为了当前的研究热点， 这些情况给x m l 索引与查询优化技术提出了严峻的挑战。随着网络技术的发展，数据流 得到广泛应用，因此，) m 。数据流的高效处理成为近年来研究的热点。 利用索引技术来优化x m l 查询，这几年得到了定的发展，一些索引技术相继被提 出。例如：d a t a g u i d e s ，t - i n d e x e s ，l o r e ，i n d e xf a b r i c ，t o x i n 。在对大量的索引进 内蒙古科技大学硕士学位论文 行研究的同时发现这些索引相对较大，经研究发现根据x m l 文档的s c h e m a 获取它的文 档结构，根据文档结构建立的索引比较小，因为文档结构中忽略了元素值，属性值，重 复元素和文档顺序。建立了较小的索引后，对于带谓词的) ( p a t h 查询一直是研究的难 点，x p u s h ，x s i e q ，x t r i e ，y f i l t e r 都实现了对带谓词的x p a t h 查询，但是对谓词的 查询效率不高。 本文在对带谓词的x p a t h 查询上采取先预处理) ( p a t h 的路径部分，然后在x m l 数据 流流过时处理谓词的方法。在根据x m l 文档的s c h e m a 获取它的文档结构得到结构索引 的基础上，利用结构索引( 像x m l 文档树一样) 来预处理x p a t h 查询的结构向导部分， 它将尝试找到查询的结构部分和x m l 文档树匹配的所有路径，然后每一个结构匹配的结 果被储存在索引结点中，得到带路径匹配的结构索引，然后用带路径匹配的结构索引处 理x m l 数据流完成谓词的匹配。， 本文完成的工作如下： 1 根据x m l 的s c h e m a 建立结构索引； 2 利用结构索引完成) ( p a t h 查询的路径匹配部分，得到带路径匹配的结构索引； 3 当有大量的查询时，可能有多个查询的谓词在结构索引的同一个结点匹配，用 链表来处理； 4 用带路径匹配的结构索引处理) 咖。数据流，完成谓词的匹配； 5 把查询的结果交给查询的用户。 内蒙古科技大学硕士学位论文 2 背景知识 2 1 数据库管理系统与数据流管理系统 传感器数据处理、金融证券管理、i n t e r n e t 流量监控、w e b 使用日志及电话呼叫记 录的在线分析等新型应用领域对数据的管理与分析提出了新的要求，比如直接反映数据 的本来面目、可以处理连续查询、能够处理异种数据、快速响应用户查询等，其本质是 对数据流的管理和分析。数据流是连续的、输入速率随时间变化的、有序项的序列，数 据流上的查询通常连续运行，当新数据到达时增量式地返回结果，即所谓的长时间运行 的、连续的、持久的查询，数据流所具有的特点使数据流管理系统与传统的数据库管理 系统存在着差异【3 9 1 。 2 1 1 数据流管理系统与数据库管理系统的区别 传统数据库管理系统的主要特点是数据持久存储，是稳定的，在某一时刻执行 查询并通过稳定查询计划给出精确的回答，而数据流处理系统正好相反，它强调数 据在线到达，是动态的，而查询持久存储，是稳定的。在数据流处理系统中，不可 能控制数据的到达，将所有到达的数据存储在本地进行管理和查询也是不现实的。 数据流管理系统与数据库管理系统的差异见表2 1 。 表2 1 数据流管理系统与数据库管理系统对比 内蒙古科技大学硕士学位论文 与传统d b m s 的一切为了保证结果的绝对正确性相反，d s m s 更看重自适应性， 允许向用户提供近似查询结果。目前还没有d b m s 提供内建的功能支持近似查询回 楚 口。 数据流管理系统与传统数据库管理系统相比，新颖性主要可概括为以下三个方 面： ( 1 ) 语义( s e m a n t i c s ) ：数据流按时间顺序输入，查询结果以流形式输出。 ( 2 ) 状态( s t a t e ) ：不能存储无终止的流，某些操作需要历史记录。 ( 3 ) 性能( p e r f o r m a n c e ) ：自适应性( a d a p t i v i t y ) 、速率可变性( v a r i a b i i i t y ) 、不 精确性( i m p r e c i s i o n ) 。 2 1 2 数据流管理系统必须具备的功能 ( 1 ) 数据模式和查询语义必须允许基于顺序和基于时间的操作，比如支持在5 分 钟尺寸大小的滑动窗口上的查询。 ( 2 ) 长时间运行的查询在执行生命期中可能会遇到系统条件的变化，例如流速率 的变化，需要设计具有自适应性的查询计划和调度策略。为即时准确地响应用户查 询和