（计算机应用技术专业论文）xml数据流的xpath查询算法研究.pdf

x m l 数据流的x p a t h 查询算法研究 张宏伟( 计算机应用技术) 指导教师：魏东平副教授 摘要 随着帆技术的不断发展及其应用领域的不断扩展，越来越多的数 据开始用札进行描述、存储和交换。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 数据流的x p a t h 查询系统。它可以在对x m l 流的一次单向读取过程 中处理查询，输出查询结果。论文最后对基于内存的x m l 查询算法和基 于流的x m l 查询算法进行了测试、比较、分析。 基于流的x m l 查询算法是为了满足些数据密集型应用对数据的 实时查询要求而引入的。这类应用处理的数据不宜用稳定的关系模型， 而应采用数据流模型。本论文的研究对这类实际应用将具有一定的理论 意义和实用价值。 关键词：x m l 数据流，x p a t h ，自动机，查询 x p a t hq u e r y a l g o r i t h m so f x m l s t r e a m z h a n g h o n g - w e i ( c o m p u t e r a p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db ya s s o c i a t ep r o f e s s o rw e i d o n g - p i n g a b s t r a c t x m lh a sb e t t , o m et h es t a n d a r do fd a t ad e s c r i p t i o na n de x c h a n g e i ti s u s e di nm a n yf i e l d s a st h ee v o l u t i o no f ) 帆t e c h n o l o g y , m o l ea n dm o r e i n f o r m a t i o nh a sb e e nd e s c r i b e da n de x c h a n g e di nx m l m e a n w h i l e ，t h e s t u d yo nx m l b l a c a mq u e r y i n gi so n eo ft h eh o t f c s tt o p i c sa m o n gt h e d a t a b a s ec i r c l ea l lo v e rt h ew o r l d i ne x i s t i n gx m l q u e r ya l g o r i t h m st h ew h o l ed o c u m e n tm u s tb el o a d e d i n t om e m o r y t h em e t h o dc a n th a n d l ew i t hb i gx m ld o c u m e n ta n dx m l s t r e a m ad i f f e r e n tm e t h o df o rq u e r yp r o c e s s i n gi sp r e s e n t e di nt h ep a p e r a c c o r d i n gt ot h eq u e r ye x p r e s s i o 玛aq u e r ya u t o m a t o ni s b u i l d t h ex m l s t r e a mi sp a r s e di n t oe l e m e n t t a g sa n de v e n t ss t r e a m t h ee v e n tt r i g g e r ss t a t e s t r a n s i t i o no fq u e r ya u t o m a t o n t h es t r e a mf r a g m e n tw i l lb e p u to u t i m m e d i a t e l yw h i l ei ti sf i tf o rt h eq u e r y a p r o t o t y p em o d e lt h a ti su s e df o rx m l s u e a mq u e r yi si n t r o d u c e x l t h em o d e lc o u l de v a l u a t et h ex p a t h e x p r e s s i o n a n dg e tt h er e s u l t i m m e d i a t e l y a tl a s t , w em a k eac o m p a r a t i v ee x p e r i m e n tt oi n v e s t i g a t et h e m e m o r y u s eb e t w e e n m e m o r y - b a s e da l g o r i t h m a n dt h es t r e a m - b a s a d a l g o r i t h m t h es y s t e mc a nb eu s e di ns o m ed a m - i n t e n s i v ea p p l i c a t i o n s i nt h e s e a p p l i c a t i o n s t r a d i t i o n a lm o d e lc a n td e a l w i t ht h es t r e a m i n gd a l 【a t h e r e s e a r c hi nt h i sp a p e rc o n t r i b u t e st ot h et h e o r ya n dp r a c t i c 宅o ft h i sk i n do f a p p l i c a t i o n s k e yw o r d s ：x m ls t r e a m ，x p a t h ，a u t o m a t o n ，q u e r y 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中国 石油大学或其它教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了 谢意。 签名：丛壑後少印年月 日 关于论文使用授权的说明 本人完全了解中国石油大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件及电子版，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手 段保存论文。 ( 保密论文在解密后应遵守此规定) 学生签名：! 茎壑鱼印印年尹月，日 导师签名： 鲤童! 聋劲卵7 年 中月，日 中国石油大学( 华东) 硕七论文第1 章前言 第1 章前言 1 ，1 问题的提出及研究意义 近年来，一类新的数据密集型应用已经得到广泛的认同，这类应用 的特征是：数据不宜用持久稳定的关系建模，而适宜用数据流【1 】建模。 这些应用的实例包括金融服务、网络监控、电信数据管理、传感检测等。 在这些数据流模型中，数据单元可能是网络监测、呼叫记录、传感器读 数等产生的数据。由于这些数据以大量、快速、实时的形式持续到达， 由此产生了一些新的研究问题。 传统的静态数据处理以数据为中心，整个数据集存储在一个相对稳 定的中央存储介质中，并随时准备接受随机到来的用户查询请求。在数 据集的生命周期，绝大部分是稳定不变的，而频繁变化的是用户随时可 能提交的查询。静态数据处理方式的典型应用包括：数据库管理系统、 检索系统、数据仓库系统等。长期以来，静态数据的查询处理得到了广 泛深入的研究，现在已经形成了成熟的技术和产业。 在上面提到的应用中，数据集表现为具有高度的流动性，而相对稳 定的是用户查询，大量预先定义的用户查询被注册到处理系统中，等待 数据的到来。一旦数据到来，将驱动查询的执行。若把不间断到达的数 据简单地放到传统的数据库管理系统中，并在其中进行操作，是不切实 际的。传统的数据库管理系统并不是为快速连续地存放单独的数据单元 而设计的，而且也不支持连续查询，而连续查询正是数据流应用的典型 特征。 连续数据流的查询，有两个重要的特点 ”】： 中国石油大学( 华东) 硬士论文第1 章前言 第一个特点是连续查询。传统的数据库管理系统查询是对数据集在 某个时间点上瞬间状态的一次计算；连续查询是在数据流持续到达情况 下的连续计算。连续查询的答案是基于时间的，它反映了到目前为止已 看到的数据流的情况。当新的数据流到达时，连续查询的结果可以被存 储或更新。； 第二个特点是预定查询。预定查询是指查询条件在任何相关数据到 达之前就提交给数据流管理系统的一种查询。传统数据库查询是在数据 已经达到后的查询。有两个原因使得传统查询对数据流管理系统来说难 以实现：一是由于查询的正确答案可能需要参考以前数据流中数据元素， 而这一元素已经被丢弃了；二是由于不能提前预知，无法优化查询，无 法找出不同查询间可以共享的公共子表达式。 考察一个大型网络，例如一个互联网服务提供商骨干网络的网络流 量管理系统。这种系统监控各种连续数据流，包括数据包跟踪、网络性 能测量等，而这些数据流的特征是不可预知、高速到达的。典型地，当 前数据流管理工具要么依赖于特定目的的系统，通过这些系统来支持对 简单手写代码生成的连续查询的在线处理，要么只是记录流量数据日志， 再执行周期性的离线查询处理。传统的数据库查询不适合提供这种在线 连续查询处理，而这种需求恰恰是这一领域中最有价值的问题。 随着订l 逐渐成为信息描述和数据交换的事实标准，数据流信息会 以_ m 的方式来表达。处理) m 亿流和处理内存中的咀。数据有许多 不同。对于内存中的) m 几数据，处理过程中可以随机访问任何节点 在有些环境下缓存整个文档是不实用也不可能做到的。合理的方法是充 分利用当前已经输入的数据，考虑咀流查询，接收部分数据后就有 可能判断出哪些节点是结果的一部分，尽快把这类节点输出。 流动数据查询处理长期以来没有受到足够重视，目前并不存在像数 2 中国石油大学( 华东) 硕士论文第1 章前言 据库管理系统一样成熟的平台。但随着互联网技术和数据密集型应用的 发展，数据流查询的研究已逐步得到重视。数据流查询是一个既有理论 研究价值，又有广泛的应用前景的研究方向。 1 2 国内外研究现状 目前，x m l 数据流的查询处理已经取得一定的成果，如x f i l t c r 4 】， y l i i 佃5 l ，x t r i e 6 1 ，砌能f i l 抚一7 】，蛐i 硼等。 ) f i l t e r 将有限状态机模型引入x m l 流的过滤处理，通过建立x p a t h 的确定状态机，实现简单x p a t h 路径表达式的处理。但是x f i l t e r 没有考 虑相似查询的冗余处理。 y f i l t e r 是对x f i l t e r 的扩展，y f i l t c 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 m l 时缓存所有 的候选结果和谓词匹配的节点；在解析结束后通过后续处理得到最终的 查询结果。y f i l t e r 不支持在解析x m l 时立即计算谓词并输出结果，不 适合实时性要求高的应用场合。 d a ns u c i u 在文献【9 】中提出首先根据x p a t h 构造n f a ，然后在n f a 上执行确定化操作。这样，系统在运行的任意时刻，始终只有一个状态， 系统的处理效率有了较大的提高。但是，当由x p a t h 构造的n f a 状态数 目较多时，确定化操作所需空间呈指数级增长。另外，这种方法也没有 解决对带谓词的x p a t h 查询的支持。 x t r i e 提出了只包含父子关系的子路径表达式的索引机制，并使用索 引机制提取多个查询的公共子路径，实现包含谓词逻辑的x p a t h 处理。 x t r i e 是对基于n f a 自动机的查询处理的一种扩展，n f a 自动机每接受 3 中国石油大学( 华东) 硕士论文第1 章前言 一个元素事件，都查找相关的转换，但是x t r i e 在接受元素事件序列之 后，才选择相关的处理器进行响应。一般而言，响应元素序列的x p a t h 处理机比响应单一元素的x p a t h 处理机要少得多。通过这种方式，x t r i e 减少了接受元素输入序列的查询处理机的数量，从而提高了运行时刻的 处理效率。 h h 解决了n f a 自动机的表达能力问题。这一扩展主要利用了支 持表达路径之间a n d o r 关系的a f a ( a l t e m a t i n gf i n i t ea u t o m a t o n ) 自动 机，a f a 自动机利用扩展的状态来保存不同路径的执行情况。x p u s h 执 行器也是基于确定化自动机，提高了系统的查询效率，但是自动机的确 定化操作同样也面临指数级别空间代价的问题。 北京大学信息科学技术学院的高军等提出了基于树自动机的x p a t h 在x m l 数据流上的高效执行算法x e b t t 埘。他们的工作主要体现在： 采用树自动机作为x e b t 的基础，树自动机能利用d t d ( d o c u m e n tt y p e d e f i n i t i o n ) 完成x e b t 的进一步优化；提出了局部的x e b t 的优化策略， 以有限空间为代价，减少x e b t 中同时运行的状态，从而提高效率；提 出了自上而下和自下而上相结合的x e b t 的优化策略，在查询满足判定 的代价不增加的情况下，减少查询集合中的重复操作。 另外，一些数据流处理原型系统有：( 1 ) 布朗大学的大型流监控系统 a u r o r a ，该系统是面向工作流的系统，用户可以通过组合查询操作符及 操作符问的数据流创建查询计划。( 2 ) 斯坦福大学的通用流系统s t r e a m 是基于关系的流系统，该系统强调内存管理和近似查询。( 3 ) 纽约大学的 高速时间序列数据流在线统计系统s a t s u e a m 是用于计算跨越多个数据 流的在线统计监控系统。( 4 ) o p e n c q 是监控w e b 内容流的连续查询系统， 该系统注重可伸缩的事件驱动查询处理，并使用了一种基于增量视图保 持技术的查询处理算法 中国石油大学( 华东) 硕士论文第1 章前言 1 3 论文的研究内容及章节安排 本文围绕“x m l 数据流查询”这一主题展开，主要研究内容如下： ( 1 ) 研究x m l 查询及解析规范，为x m l 数据流查询选择合适的查 询语言和解析工具；分析数据流建模的方法，建立x v i l 数据流模型。 ( 2 ) 分析自动机技术在数据流查询中的应用，包括处理流程、状态的 生成、路径优化等，在此基础上提出了一种基于流索引的优化查询的算 法一 ( 3 ) 研究带谓词的x p a t h 查询的处理方法，在此基础上提出了一种 将对谓词的处理蕴含于查询自动机构造的处理方法。 ( 4 ) x m l 数据流查询模型的设计与实现：设计并实现模型的各个模 块，分析各个模块的功能，测试并分析查询模型的性能。 论文的组织结构如下； 第l 章前言。主要介绍了x m l 数据流查询的研究意义和目前国内 外研究现状。 第2 章x m l 相关技术及数据流建模方法。介绍了x m l 的相关知识， 分析了x m l 的优点：简要分析了x m l 的相关技术，特别是x m l 解析 与查询的相关规范；讨论了数据流常用的建模方法；最后给出了本文中 用到的数据流模型的定义。 第3 章自动机匹配查询处理技术。本章的内容是自动机技术在x m l 数据流查询中的应用。讨论了自动机与正规表达式的等价性；根据x p a t h 表达式构造查询自动机的方法：最后给出了一种利用流索引优化查询的 方法。 第4 章带谓词的x p a t h 查询的预处理。本章提出了一种带谓词的 x p a t h 查询的预处理技术，根据谓词的不同分别讨论其处理方式。 中国石油大学( 华东) 硕士论文第1 章前言 第5 章查询模型的设计与实现。设计并实现了一种基于流的x l v l i , 查询模型；分析了各个模块的功能，最后对查询模型进行了测试和分析。 第6 章总结与展望。总结了本文的工作及对本课题进行了展望。 6 中国石油大学( 华东) 硕士论文第2 章x m l 相关技术及数据流建模方法 第2 章x m l 相关技术及数据流建模方法 2 1x m l 简介 可扩展标记语言咀 ( e x t e n s i b l em a r k u pl 柚g u a g e ) 是由万维网联 盟( w 3 c ，w o r l dw i d ew e bc o n s o r t i u m ) 开发的。 x l v l 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 ( 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 ) 。h t m l 由于其简单、易学、通用，迅速成为网页制作的标准 语言格式。但随着网络的发展，互联网的应用由信息共享逐渐转向商务 应用。h t m l 由于结构上的限制、难以扩展等特点，使其在电子数据交 换、数据库和搜索引擎等领域的应用存在着障碍。x m l 之所以能够出现 是因为h t m l 的成功。因此，x m l 具有h t m l 的很多优秀特性。x m l 之所以能够出现也是因为h t m l 已经不能满足人们新的需求。因此，在 适当的地方，x m l 将打破原来的传统。 蹦l 主要有三个要素：文档类型声明d 1 巾或s c h e n i a 、可扩展样 式表语言x s l ( e x t e n s i b l es t y l es h e e tl a n g u a g e ) 和可扩展链接语言 x l i n k ( e x t e n s i b l e l i n k l a n g u a g e ) 。d t d s c h e m a 规定了x m l 文件的逻辑 结构，定义了x m l 文件中的元素、元素的属性以及元素和元素的属性 之间的关系。x s l 是用于规定x m l 文档样式的语言。x l i n k 将进一步 扩展目前w e b 上已有的简单链接。 x m l 主要优剧2 1 如下： ( 1 ) 可扩展性 众所周知，各个不同的行业会有不同的特殊要求，要想定义一套各 行各业能够普遍应用的标记非常困难，x m l 允许各个不同的行业根据自 7 中国石油大学( 华东) 硕士论文第2 章x m l 相关技术及数据流建模方法 己的需要制定自己的一套标记，例如：化学标记语言c i v i l ，数学标记语 言m a t h m l 。这就使得该领域中的人们可以自由交换信息，而不用担心 接收端的人是否有特定的软件来查看信息。 ( 2 ) 内容和形式相分离 x m l 文档用于描述数据及其相互之间的关系，x s l 和c s s 用于表 现其内容，这样，同一内容可以根据实际要求呈现多种表现形式，用户 可以自行定制数据显示方式。 ( 3 ) 遵循严格的语法要求 一 h t m l 的语法要求并不严格，浏览器可以显示有语法错误的h t m l 文件。儿有严格的语法要求，制定了一整套基本规范，例如：x m l 文档必须有且只有一含根元素，标记要配对出现，每个元素都必须有起 始和结束标记等。x m l 非常注重准确性，如果语法有丝毫错误，分析器 就停止对它的进一步处理。这样，保证x m l 文档具有较好的可读性和 可维护性。 ( 4 ) 便于不同系统之间信息的传输 当前的计算机世界，不同企业、不同部门中存在着许多不同的系统。 操作系统有w m d o w s 、u n i x ，数据库系统有s q ls e r v e r 、d b 2 等。在 这些异构的平台、数据库之间传输信息比较困难。由于x m l 是非专有 的并易于阅读和编写，这就使得它成为在不同的应用问交换数据的理想 格式。 ( 5 ) 具有较好的保值性 x m l 的保值性来源自s g m l 语言，s g m l 最初设计的一大目标就是 要为文档提供5 0 年以上的寿命。s g m l 和x m l 不但能够长期作为一种 通用的标准，而且很容易和其它格式的文档转换。 由于上述特点，x m l 在信息管理、电子商务、移动通信、电子文档 8 中国石油大学( 华东) 硕士论文第2 章瑚l 相关技术及数据流建模方法 交换等诸多领域得到了广泛的应用，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 文档的能力，以及在不同的存储形式之间以 x m l 格式交换信息的能力，将成为未来l m e m e t 应用的关键。 2 1 1 订l 规范 x m l 规范定义了x m l 文档的基本规则。x m l 规范由一系列标准和 协议组成，其中x m l l 0 规范是核心。此外，还有d o m 、x s l 、x l i n k 、 x p o i n t e r 、x m ls c h e m a 、x q u e r y 等数十种相关的规范。从总体上来看， 这些规范可以分为数据描述和数据操纵两类。其中数据描述规范主要是 x m l l 0 ，而数据操纵规范包含x s l 、x l i n k 、x p a t h 、x p o i n t e r 等。图 2 1 给出了沮。的主要规范。 ( 1 ) x m l 文档类型定义：d t d 或x m l s c h e m a 1 3 , 1 4 , t s l 。用于规定x m l 文件的逻辑结构，定义x m l 文件元素、元素属性以及属性之问的关系。 d t d 包含多种类型的声明，这些声明包括d o c r 四e 、e n t i t y 、 n a i 蜘o n 、e l e m e n t 和a t r l i s t 声明。e n t i t y 和n o t a t i o n 声明 用于组成文档的逻辑结构，e l e m e n t 和a t t l i s t 声明则用于描述或约 束文档逻辑结构的细节部分。 9 中国石油大学( 华东) 硕士论文第2 章x m l 相关技术及数据流建模方法 一 图2 1 x m l 相关规范 。 d t d 将带来以下优越性。首先，通过创建d t d ，能够正式而精确地 定义词汇表。所有词汇表规则都包含在d t d 中。许多解析器都可以利用 d t d 验证文档实例的有效性。只要在文档实例中写入一条简单的声明语 句，解析器就能够获取d t d ，并将其中的内容与文档实例比较。另外， x m l 创作工具也可以通过类似的方法使用d t d 。一旦选择了d t d ，创 作工具就能够实施d t d 中的规则，它根据d t d 中说明的结构，仅允许 用户在文档中添加d t d 允许的元素或属性。 如果格式正规的文档是遵循一些隐式规则编写的，解析器无法根据 这些规则检查文档中的错误。这个系统的完整性取决于创建和使用x m l 的应用程序的完整性。代码中的错误可能很难放发现，它们还可能引起 其他程序的中断，或者导致错误的数据进入系统。然而如果某个x m l 文档引用了d t d ，解析器应该读取d t d ，并确保文档符合d t d 中描述 的语法。如果需要完善的错误检测机制，只需使用d t d 和验证有效性的 解析器。当然，有效性验证并不能避免应用程序逻辑方面的失误，但是 它能够过滤出代码中的无效数据。 作为x m l1 0 规范的重要组成部分，d t d 对于x m l 文档的结构起 到很好的描述作用，是近几年来x m l 技术领域所使用的最广泛的一种 l o 中国石油大学( 华东) 硕士论文第2 章x m l 相关技术及数据流建模方法 模式。但是，它也有一些缺点，如采用非x m l 的语法规则、支持数据 类型有限、扩展性较差等。因此w 3 c 于2 0 0 1 年5 月正式推荐x m l s c h e m a 为x m l 的标准模式，显然，w 3 c 希望以x m ls c h e m a 作为x m l 模式描述语言的主流，并逐步替代d 1 m 。 x l 沮。s c h e m a 是一种描述信息结构的模型，它用来定义x m l 文件 的文本结构、数据类型等x m l 文件描述规则，并为一类文档建立了一 个模式，x m ls c h e m a 规范了文档中的标记( t a g ) 和文本( t e x t ) 可能的组合 方式。x m ls c h e m a 不仅包括了d t d 能实现的所有功能，而且本身就是 规范的x m l 文档。x m ls c h e m a 的优点主要有： 丰富的数据类型。这些数据类型包括：布尔型、数字、日期时间、 时间间隔等等多达4 0 多种的数据类型，相对于d t d 的1 0 种数据类型要 多出许多。而且x m ls c h e m a 还支持由这些简单的类型派生出的复杂类 型。 与x m l 文档保持一致。x m l s c h e m a 是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 文档的结构，使得x m l 达到了从内到外的完 美统一，也为x m l 的进一步发展奠定了坚实的基础。 可以对数据类型进行扩展和限制，具有极其强大的数据结构定义 功能。 同命名空间更紧密的结合。x m ls c h e m a 利用名称空间将文档中 特殊的节点与s c h e m a 说明相联系，一个x m l 文件可以有多个对应的 s c h e m a 。由于x m ls c h e m a 比d t d 有更大的优越性d 2 , z 3 1 ，现在s c h e m a 取代d t d 已成大势所趋，它必将替代d t d 。国际上一些知名企业和组 织纷纷提供对) 0 ls c h e m a 的支持。 中国石油大学( 华东) 硕士论文第2 章x m l 相关技术及数据流建模方法 ( 2 ) x m l 文档显示格式：级联样式表c s s ( c a a d es t y l es h e e t ) 或可扩 展样式语言x s l 0 6 1 ( e x t e n s i b l es t y l el a n g u a g e ) ，用于定义x m l 文档的显 示格式，方便用户的查看。 x s l 是用来表现x m l 的语言，x s l 定义包含了一套元素集的x m l 语法规范，该语法规范把x m l 文件转换成h t m l 、x m l 或其他格式的 文档。要实现用x s l 表现x m l ，需做两件事：生成x s l ，然后再将它 与x m l 文档相结合。实际应用中，可以将样式表作为处理指令放在x m l 文档的序言部分来与x l v i l 文档结合。 。 x s l 的第一部分x s l t 的功能是由源文档构建结果树( r e s u l tt r e e ) 。 使用x s l t ，开发者可以描述从现有的x m l 文档建立新的结构化文档的 方法，这将由x s l t 引擎实现。x s l t 并不是编程语言，其实现方法是给 出实例，而不是描述执行过程。开发者要做的是把模板提供给引擎，并 指明在进行转换时何时何地使用该模扳。 0 ) x m l 文档查询语言：x q u e f y l l 7 1 十分灵活，可以在包括数据库和 文档的多种x m l 数据源之上进行查询。x q u e r y 的1 0 版本包含了x p a t h 的2 0 版本作为它的一个子集。所有在x q u e r y l 0 和x p a t h2 0 中语法上 均有效且均可以成功执行的表达式，必然得到相同的查询结果。由于这 两种语言有着如此紧密的联系，他们在语法和语言描述以及数据模型的 表示上都是统一的。 ( 4 ) x m l 文档链接语言：x l i n k 的规格说明书是用来描述和创建x m l 文档中资源之问的链接语言规范。这个规范定义了两种链接声明类型， 即简单型的( 类型为s i m p l e 的) 和扩展型的( 类型为e x t 鲍d e d ) 。利用 x p o i n t e r 可以链接文件的区段，选择特定的属性和元素 ( 5 ) x m l 文档解析：一个x m l 文档在使用之前，它必须首先经过 x m l 解析器的处理。解析器从文档中提取实际的数据，然后创建新的数 1 2 中国石油大学( 华东) 硕士论文第2 章x 札相关技术及数据流建模方法 据模型。文档对象模型d o m l l 刀( d o c u m e n to b j e c tm o d e ) 是w 3 c 标准， 是一个主要的分析模型。d o m 是一种便于应用程序对x m l 文档进行加 载、控制和保存等操作的接口。在解析文档的时候，d o m 把x m l 的全 部内容保存在一种叫“结点”的数据结构里，并且把数据之间的关系以 “树”的数据结构保存起来，全部的结点和树的信息都放在内存里。在 应用程序看来，经过d o m 解析后的x m l 文档是一棵树，树的每个结点 保存相关的x m l 数据，并和原文件的标签、属性或指令等一一对应起 来。 一 简单应用程序接e ls a x ( s i r n p l ea p if o rx m l ) 和d o m 有完全不同的 工作方式。用s a x 编程时，程序员不能要求解析器随时提供任意位置的 节点信息。相反，是解析器在解析文件的时候随时向应用程序报告事件。 s a x 分析器在对x m l 文档进行分析时，触发一系列的事件，应用程序 通过事件处理函数实现对x m l 文档的访问。由于事件触发本身是有时 序性的，因此s a x 分析器提供的是一种对x m l 文档的顺序访问机制。 对于已经分析过的部分，不能再倒回去重新处理。s a x 分析器在实现时， 它只是顺序地检查x m l 文档年的字节流，判断当前字节是x m l 语法中 的哪一部分，检查是否符合x m l 语法并触发相应的事件。对于事件处 理函数本身，要由应用程序自己来实现。相对于d o m ，s a x 至少可以 更好地在下面两种情况下工作： 一是解析很大的x m l 文件。因为d o m 是把文件解析之后将数据以 一定的结构保存在内存中，所以要耗费很大的空间。如果碰到较大的文 件，对内存空间将会有很大的压力。s a x 使用的内存一般都远远小于 d o m 所需要的内存，而且不随文件的大小丽改变。因此，在解析很大的 ) m l l 文件而内存空间不足的时候就只能用s a x 了。 二是只需要得到x m l 文件的一个小信息子集的场合。比如在一个关 中国石油大学( 华东) 硕士论文第2 章x m l 相关技术及数据流建模方法 于书籍信息的x m l 文件中要想得到书的平均价格，显然程序里用到的 只有 这个元素的数据，其他元素和数据都可以忽略。如果使用 d o m ，所有信息都需要呈现在内存中；而使用s a x 时程序员可以很容 易地忽略那些他们不感兴趣的数据。这样程序运行起来肯定会大大加快， 而使用的内存空间也会大大减少。 2 1 2 帆路径查询概述 随着存储在x m l 文档中的信息量的增长；能有效并且高效地存取 x m l 文档中的信息也变得越来越重要。要做到这一点，必须要有一个能 够准确获取所需信息、更新x m l 数据源中数据的可表达的查询语言。 x m l 查询语言是以x m l 的逻辑模型为输入、处理和输出的数据模型， 它独立于x m l 文件的物理存储；可以用不同的方式实现。 x p a t h 是w 3 c 豹标准1 1 l ，埘，它提供了关于路径导航o a t hn a v i g a t i o n ) ， 节点定位( n o d el o c a t i o n ) ，谓词选择等方面精确的规范x p a t h 采用类似 于文件路径的方式来定位x m l 文档中的x m l 元素。路径使用强调节点 之间的层次关系的符号来表达节点模式。从语法的观点来看，x p a t h 表 达式看起来像由文件夹和文件名组成的文件系统路径。x p a t h 表达式总 是在上下文节点中计算的上下文节点由应用程序指定，表示查询的起 始节点 x p a t h 中最重要的组成部分是定位路径( 1 0 c a t i o np a t h ) ，定位路径分为 绝对定位路径( a b s o l u t el o c a t i o np a t h ) 和相对定位路径( r e l a t i v el o c a t i o n p a t h ) 两种。前者是从根节点到某个节点的路径，后者是从当前选定的节 点到某个节点的路径。 符合表达式的各个节点构成了上下文节点集。实际上，返回给应用 程序的最终节点集是仅包含了匹配指定节点的上下文节点集的子集。 1 4 中国石油大学( 华东) 硕士论文第2 章x m l 相关技术及数据流建模方法 x p a t h 表达式可以返回以下任何一种类型：b o o l e a n 、s t r i n g 、n u m b e r 或 n o d e 一哦。然而在通常情况下，它会返回一个节点集。 每个x p a t h 路径表达式由多个定位步组成，一个定位步有三个部分： 一个轴，它指定了定位步选择的节点与上下文节点之间的树状关 系： 一个节点测试，它指定了定位步选择的节点类型； 零个或零个以上的判定词，它使用专有的表达式进一步细化定位 步选择的节点集合 定位步的句法是由两个冒号分开的轴名和节点测试组成的，节点测 试后可跟随零个或零个以上在方括号内的判定词。例如：在 c h i l d ：p a r a p o s i t i o n o = 1 ，c h i l d 是轴名，p a r a 是节点测试而 p o s i t i o n ( ) = 1 是判定词。 以下是常用到的轴： c h i l d 轴选择上下文节点的孩子节点： d e s c e n d a n t 轴选择上下文节点的予孙节点，子孙轴从来不包含属 性或命名空间节点； - p a r e n t 轴选择上下文节点的父节点，如果有的话： a n c e s t o r 轴选择上下文节点的祖先，祖先轴总是包括根节点； f o l l o w i n g - s i b l i n g 轴选择上下文节点的所有在其后的兄弟，如果上 下文节点是属性节点或命名空阀节点，则f o l l o w i n g - s i b l i n g 轴为空； p r e c e d i n g s i b l i n g 轴选择上下文节点的所有在其前的兄弟，如果上 下文节点是属性节点或命名空间节点，贝i jp r e c e d i n g s i b l i n g 轴为空； f o l l o w i n g 轴选择在上下文节点所在的同一文档中，所有依照文档 顺序在上下文节点后的节点，但排除所有的子孙，也排除属性节点以及 命名空间节点： 中国石油大学( 华东) 硕士论文第2 章煳l 相关技术及数据流建模方法 p r e a i n g 轴选择在上下文节点所在的同一文档中，所有依照文档 顺序在上下文节点前的节点，但排除所有的子孙，也排除属性节点以及 命名空间节点； s e l f 轴只包含上下文节点自己； d e s c e n d a n t o r - s e l f 轴包含上下文节点和上下文节点的子孙； a n c e s t o r - o r - s e l f 轴包含上下文节点和上下文节点的祖先；这样该轴 总是包括根节点。 2 2 数据流建模方法 模型是现实系统的简化。建模是对现实系统进行适当过滤，用适当 的表现规则描绘出简洁的模型。通过模型，可以了解所研究事物的本质， 而且在形式上便于对之进行分析和处理。区别于传统数据模型，数据流 模型的特点有：流中的数据元素在线到达；数据到达次序独立，不受应 用系统的控制。从理论上说，数据流的潜在大小是无界的，系统能存储 的数据相对数据流的大小是非常有限的；一旦数据流的某个元素经过处 理，要么被丢弃，要么被归档存储。下面是几种常用的数据流建模方法 2 2 1 标点模型 标点模型团l 的研究动机来自于对两种操作算子的处理，一种是块操 作，例如g r o u p - b y ，需要等待所有数据到达后才能输出结果；另一种是 无边界状态的操作算子，例如j o i n ，维持状态所需要的空间无限制增长。 该数据流处理模型基于这样一个简单的事实：当一个输入完全读取后， 块操作算子能够输出结果，面无边界状态的操作算子会清除状态。当一 个特定的子集完全读取后，查询算子是不是也可以做同样的处理? 基于 1 6 中国石油大学( 华东) 硕士论文第2 章x 札相关技术及数据流建模方法 这样的想法，考虑使用嵌入在数据流中的某些标记来表示数据流子集的 结束。我们把这些标记称为“标点”( p u n c t u a t i o n ) 。 一个标点的出现表示在随后的数据流中不再包含满足条件的数据。 因此，可以将标点看成一个“黑箱”布尔代数。事实上，标点可以表示 很多语义，在不同的应用中，标点表示的语义是不同的。标点是一个模 式的有序集合，每个模式是与元组的每个属性相对应的。 如何将标点嵌入到数据流中呃? 通过一个标点操作模块可以进行标 点的插入，有以下几种考虑； ( 1 ) 在数据源产生时：当数据流在数据源频繁产生时，数据源可以产 生标点加入到数据流中。例如在传感器中，当个小时结束时，自动嵌 入当前一个小时的结束标记。 ( 2 ) 访问顺序的知识：扫描和获取操作可能知道数据源信息，根据这 些知识产生标点。 ( 3 ) 流的信息或者应用语义：事先知道数据源的语义，例如温度传感 器的限制是在- 2 0 。c 到5 0 。c 之间，则可以把这种语义插入到数据流中。 ( 4 ) 辅助信息：可以用一些辅助的信息指导标点的嵌入。 ( 5 ) 有时需要对输出的元组强加一些语义。 将标点语义加入到数据流中的优点是能够得到数据流的某个“子 集”，使一些操作的执行变得方便可行。但是在数据流中嵌入一些语义是 一个很复杂的问题，对标点的感知和解释机制也是很复杂的事情。 2 2 2 界标模型 界标模型是标点模型的简化。与标点模型相比，界标模型少了一些 语义信息，但这种模型却更容易使用。令押表示当前时间戳，t 表示一个 1 7 中国石油大学( 华东) 硕士论文第2 章x 札相关技术及数据流建模方法 已知的时间戳。界标模型的查询范围从某个已知的初始时间点到当前的 时间点为止，即 口，口。 。 下面是一些基于界标模型创建数据流的概要数据结构的方法： ( 1 ) 直方图。直方图技术犯1 捌就是将一个大数据集划分为很多个连续 的桶，每个桶都由一个数字来代表其特征。直方图表示法直观、简洁， 能很好地表示大数据的轮廓。直方图又可划分为等宽直方图、压缩直方 图、v - 优化直方图等。 ( 2 ) 抽样方法。抽样方法从数据集中抽取小部分数据代表整个数据 集，并根据该样本获得查询结果。抽样方法可以分为均匀抽样和偏倚抽 样两种。在均匀抽样方法中，数据集中各元素以相同的概率被选取到样 本集合中；而在偏倚抽样方法中，不同元素入选的几率可能不同。水库 抽样方法和精确抽样方法都属于均匀抽样方法，而计数抽样方法则属于 偏倚抽样方法。 ( 3 ) 小波方法小波分析方法是一种通用的数字信号处理技术，它也 可以被应用到数据库领域，如对高维数据进行降维处理、生成直方图等 文献1 提出了一种基于哈尔小波技术。在数据流上生成直方图的算法。 该算法将整个数据集变换成一系列的小波参数，并且有选择地保留有限 个高能量参数，从而近似模拟原始数据集。 2 2 3 窗口模型 窗口模型【躺硐的主要思想是，在大部分的应用中，用户往往只关心 菜一部分数据。例如，只有一个星期之内的数据被认为是对结果有用的。 因此在建模的过程中强调某一部分数据的重要性，把各种操作的范围限 制在易管理的窗口内处理。如何定义模型强调最近数据的重要性是关键 i s 中国石油大学( 华东) 硕士论文第2 章】