（计算机软件与理论专业论文）一种xml数据流查询过滤算法.pdf

i 中 文 摘 要 近年来， xml数据流的查询处理引起了国内外学者的广泛兴趣。 如何在xml 数据流中有效地查询大量xpath表达式是当今研究的一个热点问题。目前，已经 提出很多种在xml文档上进行xpath查询的方法，其中大部分是采用基于自动机 的查询方法，它又可分为基于不确定有穷自动机（nondeterministic finite automata）和基于确定有穷自动机（deterministic finite automata）两种。除此之 外，还有基于索引的以及基于谓词的查询方法。 对于nfa中的一个状态，同一个输入下可能发生很多个状态转移，为了查找 下一个指定的状态需要花费很长的时间。然而对于dfa中的一个状态而言，同一 个输入下发生了确定的状态转移，但是随着xpath查询表达式数目的增加，自动 机的状态数会迅速增加，这样需要占用很多的存储空间。 本文对xml数据流查询处理中所存在的问题进行了比较详尽的研究，针对 目前存在的xml文档处理方法的不足，提出了一种索引结构，在索引结构的基 础上又提出了一种查询算法。本文的主要工作如下： （1）提出了一种新颖的索引机制-xml文档的索引结构。首先从给定的 xml文档中提取出文档结构，然后根据文档结构建立一个个索引节点，组成文 档的索引结构。 （2）利用所构造的文档的索引结构，对给定的一系列xpath查询表达式进行 预处理。将与索引节点匹配的查询表达式标注于对应索引节点的谓词列表框内。 （3）提出了一种解决线性路径查询的算法lxpf。 （4）通过实验将本文提出的算法跟以往所提出的算法进行比较，结果表明 其有效性。 关键词：xml文档；数据流；xpath查询表达式；索引结构；过滤算法 iii abstract in recent years, the query evaluation of xml data stream has attracted scholars widespread interest at home and abroad. how to effectively implement a large number of xpath expressions over an xml stream is a hot spot in todays research. at present, many xpath query methods over xml document have been proposed. most of the ways have based on automata, which can be divided into based on nondeterministic finite automata and based on deterministic finite automata. in addition, there are means that based on index or predicate. for a state of nfa , the same input may occur many state transition .it takes quite a long time to find the next specified state. however, for a state of dfa, the same input will occur determinate state transition , but with the increase of the number of xpath query expression, the number of automata states will rapidly increase, so it need to take a lot of storage space. in this paper , problems existed in xml data stream query processing were discussed and researched. aiming at the lack of the remaining processing methods of xml document. an index structure and a kind of algorithm which based on the index structure are proposed. the main works of this paper are summarized as follows: (1) in this paper, a novel indexing mechanism - an index structure of xml document is proposed. firstly, it extracts the document structure from a given xml document. secondly, it constructs the index nodes according to the document structure. the index structure of the document is composed of the index nodes. (2)a series of xpath query expression were pretreated by making use of the index structure of the document. the query expression which are matched with the index nodes are marked in the predicate list box of their corresponding index node. iv (3)in this paper, an algorithm lxpf to solve linear path query is proposed. (4) the algorithm which has been proposed in this paper is compared with the previously proposed algorithm, and the experimental results show its effectiveness. keywords: xml document; data stream; xpath query expression; index structure; filtering algorithm 第一章 绪论 1 第一章 绪论 1.1 研究背景与国内外研究现状 目前，随着互联网的不断发展，不同计算机之间的信息交换越来越频繁，但信 息格式的不一致，给信息交换造成了障碍。xml 很好地解决了数据格式的不一致 性问题。由于 xml 具有简单性、兼容性、表达能力强等特点，已成为当下研究的 热点。 xml 应用的不断增长，尤其是互联网与无线通信网的出现，产生了大量数据 流类型的数据。目前广泛应用在网络监控，股票交易，金融服务、地质测量、气象 观测等领域中。当 xml 数据以一个持续不断的方式传送时，就形成了数据流。它 具有自动产生、数据量大以及持续到达等特点。由于 xml 流查询主要是 xpath 表 达式的查询，因此 xpath 查询成为一个焦点问题。近几年，已经提出很多种解决 xml 文档查询的方法，下面分别阐述它们的优势与不足。 xfilter1在已经修改的有限状态机上引入索引机制，并提出匹配算法。当 xml 文档到来时估计查询，一旦匹配，则将整个文档返回给特定的用户。但是对 于相似查询没有进行合并处理，也没有对含有谓词的查询进行处理。文献2对多 个 xpath 查询进行了索引， 利用栈结构存储当前的活动状态和先前处理过的状态， 当 xml 文档到来时，发生状态发生转换，最后得出与文档匹配的 xpath，但是没 有解决谓词查询问题。yfilter34将多个 xpath 合并为一个 nfa,利用前缀共享避 免重复操作。将 xpath 过滤问题分成结构匹配和谓词匹配。尽管在一定程度上改 善了 xfilter,然而效率仍然依赖于查询工作量。文献5引入双索引结构，对 xml 文档中每个元素，将其子节点集和子孙节点集用一个表格存储起来。当一个元素 节点到达时，从表格中查找它的子节点集和子孙节点集，越过那些对匹配没有任 何帮助的节点。最后提出一种过滤算法。然而对每个元素搜索子节点集和子孙节 点集时，耗费很多时间。 xtrie6支持带有谓词的 xpath 查询。最大优点是：一个元素解析事件到达 之后，并不单独进行处理，而是在一个元素解析事件序列到达之后，此时才选择 有关的查询处理器进行相应的处理，但它提出的索引机制只针对于包含 p-c 关系 的子路径表达式。 树自动机7与传统的方法相比，主要增强了自动机的表达能力。该自动机模式 采用局部确定化、自上而下与自下而上相结合的优化策略，然而对谓词的处理没有 一种 xml 数据流查询过滤算法 2 进行研究。 lazy dfa8克服了许多基于 dfa 查询处理中，随着查询量的增加，dfa 状 态数急剧增加的缺陷，这里的 dfa 状态数比较少，仅在运行时懒惰构造,只构造 那些对查询有关的状态。onizuka 9对具有复杂定义模式的 xml 文档应用 lazy dfa 进行处理，实时地构造 dfa 结构；将一个大的查询工作量进行分解，对分解 得到的一些小的查询分别进行查询处理。然而这样处理的查询效率仍然依赖于查 询的总工作量。xpush machine10 利用确定的下推自动机，以一种自底向上的方 式，处理具有嵌套路径的复杂查询，尽管这种方法从理论上分析时间近似于一个 常量，然而由于转移函数庞大，结果发现实际处理效率与查询工作量的大小成线 性关系。而且并不支持 xpath 查询表达式的更新问题。 1.2 本文主要工作 .2 本文主要工作 针对线性路径的查询问题： （1）提出了xml文档的索引结构。首先从给定的xml文档中提取出文档结构， 然后根据文档结构建立一个个索引节点，组成文档的索引结构。 （2）利用所构造的索引结构，对给定的一系列xpath查询表达式进行预处理， 将与索引节点匹配的查询标注在索引节点对应的谓词列表框中。 （3）提出了一种解决线性路径查询的算法lxpf。 （4）通过实验将本文提出的算法跟以往算法进行比较，结果显示lxpf具有高 效性。 1.3 本文组织结构 第一章介绍在xml数据流上进行xpath查询的研究背景和国内外研究现状； 第二章介绍一些相关概念，如：xml文档、xml文档树、xml流以及xml中 常用的规范； 第三章简要介绍了xpath查询表达式，sax解析，xml数据流查询模型，并将其 与传统数据模型进行了比较，提出了xml文档的文档结构、索引结构，对利用索引 结构处理xml文档流的思想也做了详细介绍； 第四章“一种xml数据流查询的过滤算法”提出一种基于xml文档索引结构的 过滤算法，并对算法的执行过程进行了详细阐述；还对实验结果进行了分析，将文 中算法与以往算法进行比较，结果显示本文算法具有高效性； 第五章“总结与展望” ，对本文中所做的工作进行了详尽的总结，对使用文中算 第一章 绪论 3 法无法处理的情形进行了概括，并指出了以后需要继续探讨的问题和研究方向。 一种 xml 数据流查询过滤算法 4 第二章 背景知识 2.1 xml文档与 xml 文档树 一个 xml 文档11基本由下列内容构成：xml 声明部分，元素、属性，处理指 令（可选） 、注释、命名空间等。 xml文档的声明部分对于大小写是敏感的。首先声明的是xml版本号，如表明使用的版本是xml 1.0；其次是对文字编码的声明，如： encoding=“utf-16”指出建立文档所使用的字符集，此时指定为默认值utf-16 （unicode transformation format-16） ； 最后是对独立文件的声明， 如： standalone=“yes” 或者standalone=“no”前者表示文件是独立文件，其中包括与其有关的全部信息；后者 表示文件不是独立文件，可能存在指定的外部实体，或者使用了外部模式，应用程 序若要完成此种文件的解析需要获得其所有的外部信息。 元素是 xml 文档中最重要的组成部分。文档中通常包括一个或者多个元素， 如果有且仅有一个元素，则表明该文档只有根元素。每个元素均有元素标记名，它 通过使用开始标记和结束标记与其它内容分开。xml 语法要求所有元素之间的嵌 套关系必须正确。 属性是用来对元素的一些额外信息加以补充说明的。元素的属性出现在开始标 记中，属性值应该放在引号中。 处理指令是为处理文档的应用程序或者解析器提供信息的，处理指令由处理指 令的目标、数据两部分内容组成。格式如：。 如果需要注释，应该将注释内容嵌在开始字符序列“” 之间。 命名空间是为解决命名之间的重名问题而出现的。通常在文档的开始部分对命 名空间进行声明。如：其中 school 是用户定义的命 名空间的名称，uri（uniform resource identifier 统一资源标记符）是命名空间的网 址。 下面给出一个有关于学校基本信息的xml文档。 第二章 背景知识 5 1007 李强 571 2008 赵星 612 游泳 该xml文档定义了一个school元素， 描述了一个学校的信息， 并且该元素包括了 若干个dept子元素，其中每个dept元素又包括了一个系名name属性和若干个学生 student子元素，每个student元素描述了一个学生的基本信息,包括学生学号sno、学生 姓名sname、学生总分total score和学生选课selected course等子元素。 一般情况下，将一个xml文档看作是一棵文档树，这棵树有树根、有顺序而且 带有很多个标记。树中的节点可能代表元素节点、属性节点或文本节点。每个节点 都有一个标记名，用来跟其它节点相区分。树中由边所反映出来的节点之间的关系 与文档中节点之间的嵌套关系保持一致。 该xml文档所对应的xml文档树12如图2.1 所示： 一种 xml 数据流查询过滤算法 6 school dept name maths name english school dept name maths name english student snosname 2008赵星 student snosname 2008赵星612 ts 612 tssc 游泳 sc 游泳 dept dept student sno 1007 sname 李强 ts 571 student sno 1007 sname 李强 ts 571 studentstudentstudentstudent 图2.1 xml文档树 图中sc代表selected course，即学生所选择的课程。ts代表total score,即学生成 绩的总分。 2.2 xml数据流 xml数据流查询有其自身的特点：数据流是持续到达的,而且数据流的大小几乎 是无法确定的；还有一个特点是预定查询，预先将查询注册，当xml流到达时，及 时将满足条件的节点输出，无需等到数据流结束时再将结果全部输出，这在很大程 度上满足了实时的需要。由此可见将此种数据流全部放入存储器后再进行查询是不 太可能的。 大多数情况下，xml 文档是以数据流的形式传输和处理的。对 xml 流的处理 有以下要求：对于 xml 文档中的每一个元素节点要么不访问，要么只访问一次； 处理过程尽可能占用少的存储空间；为了满足实时的需要，对每个节点花费尽可能 少的处理时间。 定义 2.2.1 xml 流表达13 给定 xml 文档树 t， 对 t 中节点进行先序遍历所得 的节点序列称为 xml 树的流表达。记作 st=(x1,x2,xn),xit,序列 x1,x2,xn实际 上是 xml 流的元素访问顺序。 图2.1所示的xml 文档树，其流表达为st =（x1,x2,xn） ，其中x1 =element （school）,x2 = element（dept）,，xn = text（游泳） 。st=（element（school） ， element（dept） ，element（name） ，text（maths） ，element（student） ，element（sno） ， text（1007） ，element（sname） ，text（李强） ，element（ts） ，text（571） ， element （student） ， ， element （dept） ， element （name） ， text （english） ， element （student） ， ， element （student） ， element （sno） ， text （2008） ， element （sname） ， text（赵星） ，element（ts） ，text（612） ，element（sc） ，text（游泳） 。 第二章 背景知识 7 2.3 xml规范 xml 文档的基本规则通过 xml 规范14来进行定义。xml 的规范存在很多， 如：定义文档结构标准的 dtd、schema；定义文档格式标准的 css、xst；定义 文档查询标准的 xpath、xquery；定义文档链接标准的 xlink、xpointer；定义文 档解析标准的 sax、dom。图 2.2 是 xml 中用到的主要规范。 xmlxml 文档结构 标准 文档结构 标准 文档格式 标准 文档格式 标准 文档查询 标准 文档查询 标准 文档链接 标准 文档链接 标准 文档解析 标准 文档解析 标准 dtd schema dtd schema css xst css xst xpath xquery xpath xquery sax dom sax dom xlink xpointer xlink xpointer 图2.2 xml主要规范 2.3.1 文档类型定义文档类型定义 dtd 文档类型定义(document type definition) 11是一种用来描述 xml 文档结构的 模型。dtd 不仅定义了使用在 xml 文档中的词汇表，而且定义了其中元素、属性 以及实体之间的相互关系。文档结构的一系列规则都是由 dtd 定义的，例如：规 定 student 元素只有一个 sno 子元素，只有一个 sname 子元素，只有一个 total score 子元素，可以有一个或者多个 selected course 子元素。下面是一个 dtd 实例。其 中 element、attlist 分别是对元素和属性的描述。 操作符+代表至少出现1次，即学 校至少有一个系 #required表明文件中必须出现该属性 操作符*代表不出现或出现多次， 即学生可以没有选课，也可以选择 一种 xml 数据流查询过滤算法 8 多门课程 #pcdata代表文本或字符数据 该 dtd 的描述适用于 2.1 中的 xml 文档。多个 xml 文档也可以共享同一个 dtd 描述。 2.3.2 xml 模式模式 xmlschema xml 模式11也是一种用来表示 xml 文档结构的模型， 由于 dtd 存在没有定 义数据类型，不遵循 xml 语法结构，不可以无限制得扩展以及约束能力有限等缺 点，xmlschema 应运而生，它涵盖了以下功能：定义多种数据类型，包括：简单 类型和由简单类型扩展来的复杂类型；支持命名空间；模式定义可重用；同时 xml schema 本身就是一个 xml 文档，符合 xml 文档的语法规则，不需要定义特殊的 格式。 2.3.3 文档对象模型文档对象模型 dom dom（document object model）的工作方式是将文档全部解析之后，将解析得 到的数据内容与数据关系全部存储到内存中，等待查询要求的到来。当文档比较小 时，dom 解析的效率还是比较高的，然而当查询文档相对较大时，就会占用大量 的内存空间，此时 dom 解析就不适用了。 2.3.4 xml 解析简单应用程序接口解析简单应用程序接口 sax 为了解决解析大文档时， 占用大量内存空间的问题， 出现了 sax(simple api for xml parser)解析，与 dom 解析相比，sax 解析具有明显的优势，它首先将文档解 析得到一些事件流，然后随着 xpath 表达式查询处理的进行，部分匹配节点就会输 出，这样可以节省大量的内存空间；对于查询只对 xml 文档的个别信息感兴趣时， sax 解析呈现出更大的优越性，例如：学校对学生的学习成绩进行考核，只需关心 学生的总成绩 total score,也即学生信息中的学号，选课信息对于查询都是无关紧要 的信息，此时如果使用 dom 解析，需要将全部信息解析之后存放到内存中，但是 第二章 背景知识 9 如果使用 sax 解析，只需解析 total score 即可，这样显著提高了查询效率。 2.4 本章小结 本章较为详细的介绍了xml文档、xml文档树、xml数据流的基本概念和表 示。还解释了xml的一些常用的规范：文档定义格式dtd、schema；文档解析格式 dom、sax。 一种 xml 数据流查询过滤算法 10 第三章 基于 xml数据流的 xpath 查询 3.1 xml数据流查询模型 传统的静态数据查询，是将数据全部存入存储器，等接收到用户的查询要求 后再对数据进行查询，这种情况下数据是相对稳定的，而用户的查询会根据自己 的需要不断变化。而目前流行的xml流查询，与传统静态数据查询不同，相对稳 定的是用户的查询，预先将查询要求注册到查询系统中，当持续数据流到达时再 进行查询处理。图3.115是传统数据模型和xml数据流模型的比较： 图3.1 传统数据模型和数据流模型比较 xml数据流查询具有传送数据量大，不方便存储和数据瞬间到达的特点，所 以传统的处理数据模型不适合处理数据流。图3.2表示了数据流的查询处理模型： xml document query processor xml parser (sax_based ) userelement events selected data user interests （ xpath expressions） 图3.2 xml数据流查询模型图 在xml数据流查询模型中，核心部件是query processor，即查询处理器。通常情 况下，用xpath表达式来表达用户的特定需求，预先将xpath注册到查询系统中，当 xml文档到来时，通过xml的sax解析器， 将产生的元素事件传送到查询处理器， 这样经过一系列处理之后， 将匹配的结果返回给指定的用户。 这样就完成了基于xml 数据的xpath查询。 3.2 xpath 表达式 xpath16是由 w3c（world wide web consortium 万维网联盟）定义的，可以用 第三章 基于 xml 数据流的 xpath 查询 11 来遍历文档中的元素和属性，从而达到对 xml 文档进行查询的目的。xpath 表达 式的构建采用一种类似于文件夹中查找文件的方法。如：school/dept/student 该表达 式是要获得 student 的信息，首先打开 school 文件夹，然后再打开指定的某个 dept 子文件夹，最后再找到指定的 student 信息。 每个 xpath 表达式由一系列定位步组成。每个定位步又由三部分组成：轴、节 点测试、谓词部分（可选） 。xpath 的查询源头总是当前处理的节点，也即上下文节 点。从当前节点开始对 xpath 进行查询，返回满足条件的节点。 例如给出四个 xpath 查询表达式，在后面的查询处理中将会用到。 q1：/ a / b /* / d text= “mon” q2：/ c / d text= “tue” q3：/ a / * / e / f text= “wed” q4：/ e / f text= “thu” q5：/ a / b m=”fri” 其中操作符“/ ”、“/”分别表示节点间是父子关系、祖孙关系，“*”代表任何数据元素。 3.3 sax解析 对于给定xml文档的xpath查询，首先需要通过sax解析器进行处理，产生 一系列事件流，如startdocument( ), startelement( ) ，text( ), endelement( ) , enddocument( )。然后针对所遇到的事件，进行相应的处理。下面给出一个xml 文档片段。 1007 李强 571 一种 xml 数据流查询过滤算法 12 表3.1 xml文档与所对应的sax解析事件流 xml流 sax解析事件流 startdocument（ ） startelement(school ) startelement(dept) startelement(name) text( “maths”) endelement(name) startelement(student) 1007 startelement(sno) text(“1007”) endelement(sno ) 李强 startelement( sname) text(“李强”) endelement( sname) 571 startelement(total score) text(“571”) endelement(total score ), endelement(student) endelement(dept) endelement(school) enddocument( ) 3.4 文档索引结构 在大量xml数据流查询处理中，观察发现通常给定的xml文档是比较短的，尽 管dtd或schema定义时似乎允许xml文档是无限的， 同时还发现给定的xml文档结 构大体相似。 介于此种情况，在本节中，主要介绍一种xml文档的索引结构，它来源于输入 的xml文档，实质上是文档结构的一种表示形式。 定义3.4.1：对于同一个标记a,在按照xml文档建立文档结构和依据文档结构构 造索引结构时，根据其出现的先后顺序，依次在文档结构和索引节点中冠以下标， 如：a1,a2,依此类推。对于其它的标记b,c,d ,等，记录方法与此相同。 3.4.1 xml 文档结构文档结构 xml文档结构17虽然是一个反映文档的最小的结构，其中却包括大量的信息， 这些信息足够查找与文档相匹配的xpath查询。在由xml文档构造文档结构时，忽略 了元素值， 属性值等这些对结构导航并不重要的内容。 例如： 对于xml文档中 17 第三章 基于 xml 数据流的 xpath 查询 13 ，文档结构中表示为： 不出现元素值；对于xml文档中r=“26”，文档结 构中表示为不出现属性值。 给定一个xml文档，如： 7 13 根据文档结构的构造方法，所对应的文档结构如下： 3.4.2 文档索引结构文档索引结构 索引结构的构造：对于文档结构中的每一个元素节点和属性节点都用一个索引 节点来表示，为了进行区分，元素索引节点、属性索引节点分别用圆圈、椭圆来表 示，索引节点之间的关系跟文档结构中节点之间的对应关系保持一致。 为xml文档建立索引结构是用来对多个给定的xpath表达式进行预处理的。 首先 在索引结构中尝试着找出所有可能匹配的路径，然后把结构匹配的查询存储在相应 一种 xml 数据流查询过滤算法 14 索引节点的文本框内，最后再对文本框内表达式中的谓词分别进行处理。与3.4.1节 中文档结构所对应的索引结构以及预处理q1、q2、q3、q4、q5查询表达式后的结 果如下图所示。其中，同心圆代表了根元素节点，文本框的内容是与此索引节点路 径匹配的查询。 a a b b c cd d1 1 d d2 2 e ef mm rr nn q1: /a/b/*/dtext=mon q2: /c/dtext=tue q1: /a/b/*/dtext=mon q2: /c/dtext=tue rootroot q5：/a/bm=”friq5：/a/bm=”fri q3: /a/*/e/ftext=wed q4: /e/ftext=thu q3: /a/*/e/ftext=wed q4: /e/ftext=thu 图3.3 预处理查询后的索引结构 从图3.3所示的索引结构可以看出，它不仅可以代表文档的结构，而且文本框中 内容可以反映查询之间的包含和平衡关系，如上图所示：可以观察到在索引结构下 q4包含q3，因为所有与q3匹配的节点均与q4匹配。 利用索引结构处理用sax解析的xml流： 用索引结构处理xml流时，需要用到两个指针p、top和两个栈s、t。p指针用来 指示当前的索引节点，top指针始终指向栈s的栈顶元素；而栈s用来存储早先的索引 节点，栈t用来辅助输出匹配路径上的节点序列。在此阶段，为了简化步骤，只处理 元素的开始标记和结束标记（字符作为一个结束标记对待） ，属性的处理只需在元素 名前冠以字符即可。依据这里的约定，3.3节给出的例子，对于事件dept、sno、 sname、total score均要作以下改动。 startelement(dept),startelement(name),endelement(“maths”),startelement(sno), endelement(“1007”),startelement(sname) ,endelement(“李强”),startelement(total score), endelement(“571”)。 基本思想：开始，指定当前的索引节点为root,当遇到一个开始元素事件 （startelement(b)） ，将root压入栈s中，进行查找，此时指定b为当前的索引节点，当遇 到下一个开始元素事件如（startelement(p)） ，则将b压入栈s中，进行查找，此时指定p 为当前的索引节点，如果继续遇到开始元素事件，包括属性元素开始事件，处理过程 同上,这仅花费o(1)的时间复杂度，因为查找是在一个哈希表中进行的。 第三章 基于 xml 数据流的 xpath 查询 15 当遇到一个结束事件时，有两种情况：一种情况遇到的是字符结束事件，用所 给定的字符对当前节点的基于值的谓词进行估计，这需要花费o(log2q)，因为基于值 的谓词索引是作为一个二叉查找树进行处理的，其中q代表与此索引节点匹配的谓词 的数目10。如果谓词是匹配的，也即基于值的谓词与文档中字符结束标记的内容相 同， 则将当前的索引节点压入另一个新栈t中，然后依次获取原来栈s中不是root的节 点元素，将获取到的这些节点元素依次压入新栈t中。最后对t栈是否为空进行判断， 当栈t不为空时，将栈中元素依次弹出并输出，得到的元素序列就是与文档所匹配的 路径节点序列；如果谓词不匹配，则首先要获取栈s的栈顶元素，然后将s的栈顶元 素弹出，并且指定获取到的栈顶元素为当前的索引节点。对于第二种情况遇到的是 元素结束事件，则处理方法与上述谓词不匹配时情况相同。 3.5 本章小结 本章首先介绍了xml数据流查询模型以及对传统模型和数据流模型进行了比 较；给出了xpath定位路径的解释以及具体的sax解析实例；重点介绍了文档索引结 构，在索引结构上对查询表达式进行预处理的过程，同时对利用索引结构处理xml 文档流的思想也进行了简单介绍。 一种 xml 数据流查询过滤算法 16 第四章 一种 xml数据流查询过滤算法 4.1 线性 xpath 的查询过滤算法 lxpf linear xpath_filter(index structure ，stream) 输入：index structure为代表xml文档的索引结构，其中与索引节点结构匹配的查询 已做过标注,相关的查询信息已经填入索引节点文本框中。 s为运行时栈结构，用来存储先前的索引节点。 t为栈结构，用来临时存放已完成匹配的路径上的索引节点。 p 为指针， 用来指向当前索引节点。 top为指针，始终指向堆栈s的栈顶元素。 stream为输入的xml文档流。 u 、v均代表一个元素节点。 输出：与输入的xml文档流匹配的xpath表达式序号以及相匹配的元素序列。 (1) 初始化栈s 、t，s 、t均为空栈。 (2) 初始化root为当前的索引节点。即 p=root。 (3) 从输入的xml文档流stream中解析出一个标记 sign。 while sign 不是文档的结束标记 enddocument( ) do if sign 是开始标记 startelement ( ) if sign 是元素的开始标记，如 startelement (b) pushstack (s,current index node) / 将当前索引节点压入堆栈s中 p = b; / 重置b为当前索引节点 else sign 是属性的开始标记，如 startelement (m) pushstack (s,current index node) p = m; / 重置m为当前索引节点 end if end if if sign 是结束标记 endelement ( ) if sign 是字符的结束标记，如 endelement (“text 1”) judge(current index node, endelement (“text 1”) /判断当前索引节 点是否有谓词匹配的查询 else sign 是元素的结束标记，如 endelement (b) 第四章 一种 xml 数据流查询过滤算法 17 u=get(sstack.top) /获取堆栈s的栈顶元素，用u代表这个索引节点 pop sstack.top from stack s /将栈顶元素弹出 p= u /重置弹出的栈顶元素为当前的索引节点。 end if end if sign = xml文档流中解析出的下一个标记 end while showresults ( ) 其中判断过程如下： judge(current index node, endelement (“text 1”) /判断当前索引节点是否有谓词 匹配的查询 for(每一个与索引节点路径匹配的查询) if（query qx.vbp.text=text 1） /找到与当前索引节点谓词匹配的查询 output(qx:) /输出匹配查询的序号 pushstack(t,current index node) while(top!=root) do v=get(sstack.top) pushstack(t,v) top+; /栈顶元素指针下移 end while /此while循环实现的是将满足匹配的节点全部压入栈t中 while(stackempty(t)!=null) /当堆栈t不为空时 pop element from stack t /将堆栈t中元素弹出 output(element); /输出弹出的元素 end while /此while实现的是将满足匹配的节点序列输出 u=get(sstack.top) pop sstack.top from stack s p = u else /当前索引节点没有与之谓词匹配的查询 u=get(sstack.top) pop sstack.top from stack s p = u 一种 xml 数据流查询过滤算法 18 end if 算法中用到的标记： startelement(b)：当前元素b的开始元素标记。 pushstack (s,element)：将元素element压入堆栈s中。 startelement (m)：当前属性元素m的开始元素标记。 endelement (“text 1”)：文本text 1的结束标记。 judge( )：judge函数，用来判断当前索引节点是否有谓词匹配的查询 endelement (b)：元素b的结束元素标记。 get(sstack.top) ：获得堆栈s的栈顶元素。 pop element from stack s ：从堆栈s中弹出元素element。 vbp：代表了基于值的谓词，是value_based predicate的缩写。 output( )：将括号中的内容输出。 showresults ( )：显示最终查询结果 表4.1 xml文档与经过专门定义后的sax事件流 2 mon 3 45 6 wed 7 startelement(a) startelement(b) startelement(m) endelement(“fri”) startelement(c) startelement(d1) endelement(“mon”) endelement(“2mon3”) endelement(b) startelement(d2) startelement(n) endelement(“sun”) startelement(e) startelement(f1) endelement(“45”) endelement(e) endelement(d) startelement(d) startelement(e) startelement(f2) endelement(“wed”) endelement(“6wed7”) endelement(d) endelement(a) 第四章 一种 xml 数据流查询过滤算法 19 针对一个xml文档片段算法的处理过程如下： 1)遇到startelement(a)，将root元素压入栈s中，并指定a为当前的索引节点 2)遇到startelement(b), 将a元素压入栈s中，并指定b为当前的索引节点。 3)遇到startelement(m),将b元素压入栈s中，并指定m为当前的索引节点。 4)遇到endelement(”fri”)，基于值的谓词是匹配的，将匹配路径序号以及节点输出， 然后将b元素弹出，并指定b为当前的索引节点。 5)遇到startelement(c)，将b元素压入栈s中，并指定c为当前的索引节点。 6)遇到startelement(d), 将c元素压入栈s中，并指定d为当前的索引节点。 7)遇到endelement(“mon “), 基于值的谓词是匹配的，将匹配路径序号以及节点输 出，然后将c元素弹出，并指定c为当前的索引节点。 8)遇到endelement(“2mon3”), 基于值的谓词不匹配，将b元素弹出，并指定b为当前 的索引节点。 9)遇到endelement(b)，将a元素弹出，并指定a为当前的索引节点。 图4.1表示了整个xml文档具体处理过程中，栈s中元素的存放情况和指针p的 指示情况。 为了记录简洁， 用 s 代表 startelement , e 代表 endelement , 2m3 代表 2mon3 , 6w7 代表 6wed7。下图中每个单元第一行是元素事件流，第二行是当前 索引节点即指针所指元素节点，第三行是栈s中元素存放情况。 s（b) b s（b) b a root a root s（a) a s（a) a rootroot s（m) m s（m) m b a root b a root e（fri) b e（fri) b a root a root s（c) c s（c) c b a root b a root s（d) d s（d) d1 1 c b a root c b a root e（sun) d e（sun) d a root a root s (n) n s (n) n d a root d a root s（d) d s（d) d2 2 a root a root e (b) a e (b) a rootroot e（2m3) b e（2m3) b a root a root e（mon) c e（mon) c b a root b a root s（e) e s（e) e d a root d a roo