基于部分二进制前缀编码的XML流缓存管理方法

摘要

本发明属于可扩充标记语言(XML)管理技术领域，具体为一种基于部分二进制前缀编码的XML流缓存管理方法。该方法包括：通过运行时栈驱动的基于二进制的前缀编码，在运行时确定结果集中节点之间的关系，避免中间结果集之间的连接操作；定义一个查询的“最低公共祖先谓词节点”，以便尽早删除缓存中的节点，处理在XQuery查询中包含“∥”并且XML文档中含有递归、嵌套结构的情况；缓存管理方法同时处理多个含有复杂谓词的XQuery查询，并支持多个XQuery查询结果中公共缓存节点的共享。本发明能够有效支持针对XQuery查询的XML流的缓存管理，缓存的效率明显提高，可应用于基于Web的个性化推荐服务、信息监测等领域。

说明书

技术领域

本发明属于可扩充标记语言(XML)管理技术领域，具体涉及一种针对XML流的XQuery查询的缓存管理方法。

背景技术

在新的需求背景下，人们在20世纪90年代初，提出了一种新型的数据模型，即数据流处理模型。例如，在事件驱动的股票行情系统中，一个典型用例是将过去10分钟内价格上升10％的所有股票的名称发送给某个用户；再例如，在一个网络分析系统中，报告所有具有某些特定目的地址的包。这类应用的共同特点是实时地、持续地处理连续到达的、无限的数据流。传统的数据库管理技术不能适用于这样的应用。传统数据库管理系统的主要特点是：数据持久存储，在某一时刻执行查询并通过稳定查询计划给出精确的回答；而数据流管理系统强调：数据在线到达、查询持久存储，并且能够在有限内存中单遍处理数据流。由于可扩充标记语言(XML)已经成为Web上数据交换的标准，用于各种应用和信息源之间的数据交换，XML流处理的理论和技术引起工业界和学术界的广泛关注。

这类系统面临的一个挑战是：面对海量的用户查询(通常用XQuery^[1]查询语言或XPath^[2]查询语言)所产生的大量结果，如何对返回结果集进行有效管理，使系统能够在有限的内存中实时、高效地处理用户查询。

对于XQuery^[1]查询，当查询处理引擎遇到某些XML元素的时候，并没有足够的信息来判断是否该元素就是最终结果的一部分，此时，则必需对某些元素进行缓存。图1列出了一个XQuey查询，它要求列出Addison-Wesley出版社在1991年后出版的书的名字和出版时间。若XML流中的″title″在″year″之前到达，该查询在遇到″title″时，并没有足够的信息来判断″year″是否满足条件，因此，需要先将″title″缓存起来。XML流查询系统所需的空间可能会随着查询结果集的增长呈指数级增长，使得查询结果集变得十分巨大。例如，对于纳斯达克的实时股票行情服务系统，假定每秒到达的消息个数是5000个，消息的数据量是1KB，用户查询的数量是1千万个，查询的平均匹配率是0.001％，则结果集的数据量可能达到大约每秒4G。

已有许多XML流处理系统，其中，很多研究采用基于自动机的方法处理XML流数据^{[3，4，5，6，7，8，9]}；也有一些采用基于索引的方法^[10]，基于Bloom Filter的方法^[11]以及FiST方法^[12]等。需要指出的是，这些方法都只是用作过滤器，向用户返回真假值(表示XML流是否与查询相匹配)，而不是向用户返回查询结果的内容，因而根本没有考虑结果集的缓存管理。参考文献^[13]针对XML流，系统地研究了XPath的缓存管理问题。他们针对具有谓词的XPath表达式，考虑缓存所需的最小边界。他们给出处理非递归XML流的算法，并指出一个只包含前向轴的XPath查询在处理非递归文档时的空间和时间复杂度。该研究没有考虑算法同时处理多个XPath查询时的情况。另外，也没有考虑XQuery查询结果集的缓存管理。相对于XPath，XQuery则要复杂得多。XSQ^[14]也初步讨论了针对XPath的缓存管理问题。XSQ使用缓存区暂存可能的结果，其缓存操作是由自动机驱动的。XSQ同样只是考虑单个XPath查询，没有涉及XQuery查询的缓存结果管理问题。

TurboXPath^[15]和FluX^[16]采用XQuery表示用户的查询，同时考虑了查询结果的缓存管理。TurboXPath使用一个输出缓存来存储可能的返回结果并保持他们的顺序。由于他们的输出缓存中缓存了一些中间结果，并且采用后置处理的方法在构造返回结果元组时对节点集合之间进行连接操作，因而影响了算法的效率以及增加了缓存的空间耗费。FluX只考虑了在DTD模式下如何优化XQuery查询结果的缓存管理，并且不能处理″//″轴。这两种方法也没有考虑同时处理多个查询。XSM^[17]支持XQuery的缓存管理，但是不支持递归、嵌套的XML文档。

发明内容

本发明的目的在于提出一种能够有效实现针对XML流的XQuery查询结果的缓存管理方法，并能够避免产生不必要的中间结果。

本发明提出的针对XML流的XQuery查询结果缓存管理方法是基于部分二进制前缀编码的XML流缓存管理方法，记为BBM。方法的具体步骤如下：

(1)构造XQuery查询的紧凑查询树，将用户提交的所有XQuery查询构造为单颗紧凑查询树，并为每一个返回节点构造一个缓存池；在紧凑查询树中，所有查询共享公共前缀；

(2)查询匹配，查询匹配过程包括自顶向下和自底向上两部分，在查询匹配的过程中，执行缓存管理的基本操作，包括进行缓存结果的加入和删除等；

(3)缓存管理过程，缓存管理过程优化与XQuery查询匹配的返回结果的缓存，包括：

(a)建立缓存管理的数据结构：XQuery查询中的每一个缓存节点对应于一个缓存池，所有缓存池构成一个链表，其中，每两个缓冲池之间的链接由缓存池中返回节点之间的语义关系定义，包括父子关系、子孙关系、兄弟关系、共同祖先关系等；

(b)建立基于运行时栈的部分二进制前缀编码表示，通过运行时栈驱动基于二进制的前缀编码，在运行时确定结果集中节点之间的关系，尽早构成返回结果元组，避免中间结果集之间的连接操作；

(c)进行返回结果的缓存管理。

1.构造XQuery查询的紧凑查询树

(1)将XQuery表示为一颗紧凑查询树。一颗紧凑查询树是表示XQuery的查询树，其中的节点称为查询节点(QNode)，具有惟一标识，查询节点分为以下几种类型：

(a)OQNode：不带有谓词的定位步，称为通常查询节点(Ordinary Query Node，OQNode)。在紧凑查询树中，OQNode关联相关信息，包括节点名字(“*”的名字为“*”)和表示父子(“/”)或子孙(“//”)关系的算子，用两元组<name，“/”or“//”>表示。

(b)PQNode：带有谓词的定位步称为谓词查询节点(Predicate Query Node，OQNode)。谓词查询节点是紧凑查询树中的特殊节点，它通过逻辑关系将其子树连接起来。除了节点标识，节点名和“/”或者“//”外，还关联一个逻辑表达式。该逻辑表达式在内部表示为抽象语法树。该抽象语法树的每一个叶子节点都维护一个到其对应的节点(谓词节点的孩子节点)的引用。

(c)RNode：返回结果节点(Return Node)，即是指那些构成XQuery结果元组的节点。

(2)标识谓词子树(Predicate Sub-Tree)。在一个紧凑查询树中，以距离根节点最近的谓词节点为根所形成的子树称为谓词子树。同时扩充相应的节点结构：谓词子树中的OQNode(叶子节点除外)，也关联一个逻辑表达式，该逻辑表达式是只含有一个项，即其孩子节点的标识。而如果OQNode是叶子节点，则含有一个逻辑标记，初始为真(TRUE)，当遇到CLOSE事件后，将逻辑标记的值赋为假(FALSE)。

(3)标识接受节点(Accepting Node)。在一颗紧凑查询树的表示中，距离根节点最近的谓词节点称为该树所表示查询的接受节点。如果计算过程中，接受节点相关逻辑表达式的值为真，则该文档与查询匹配。如果一个XQuery表达式是不带谓词的一般查询(XP{/，//，*})，其接受节点则是其通常查询树的叶子节点。如果在匹配过程中到达接受节点，则该文档与查询匹配。

图1中的XQuery的紧凑查询树如图2所示，其中，粗线矩形框表示接收节点，带阴影矩形框表示返回节点。在来自用户的大量查询中，可能会具有许多共同的部分，共享其共同部分可以节省系统的存储空间和执行时间。因此，将所有的XQuery查询的查询树合并为共享前缀的单颗紧凑查询树。合并步骤具体如下：

(1)对于任意两个XQuery查询Q_a和Q_b，其共享前缀的紧凑小枝模式查询树为Q_ab。

(2)为Q_ab创建一个根r₀，以Q_a为基础构造Q_ab。

(3)前序遍历Q_a和Q_b，若Q_b中存在与Q_a节点名以及算子(“/”或“//”)相同的前缀则可以合并，否则，将Q_b中的节点加入到Q_a中。

(4)重复步骤(3)，直到完成对Q_b的遍历。

2.查询匹配

在对XML数据流处理的过程中，对带有谓词的节点及其子节点，采用自底向上的匹配过程，而对于其它部分则采用自顶向下的匹配过程，因此，查询匹配过程分为OPEN和CLOSE两部分。

(a)OPEN事件通过回调函数调用该句柄，传入事件名字，元素名字和元素的文档层次；对每一个到达的XML元素，进行节点测试和文档层次检查；如果节点检查返回TRUE，则该节点被压入一个运行时栈；若遇到的节点是PQNode或谓词子树的子节点，其状态标记的值设为FALSE。若遇到的节点是一个查询的接受节点，且不是PQNode节点，则一个查询匹配发生。若遇到的节点是同一节点的不同层次(递归文档会出现这种情况)，则将其作为不同的状态节点，用节点标识和文档层次来共同识别该状态节点。如果该接受节点是PQNode，则需要等到遇到CLOSE事件时才能判定文档与查询是否匹配。若遇到的是返回结果节点(RNode)，则将该节点放入缓存池中。

(b)在CLOSE事件发生时，如果遇到的节点是OQNode，简单地将节点从栈中弹出。如果遇到的节点是PQNode或谓词子树的子节点，将执行下列步骤：a)如果是叶子节点，将其状态标记赋为TRUE，意味着该节点匹配成功.从运行栈弹出该节点，并将当前栈顶对应的节点中相关的逻辑表达式中对应的项赋值为TRUE；如果是谓词子树中的中间节点，计算其逻辑表达式，若为TRUE，则其状态标记赋值为TRUE，否则为FALSE，从栈中弹出该节点，并将当前栈顶节点的相关逻辑表达式中的对应项赋值为其状态标记的值(TRUE或FALSE)。如果是一个查询的接受节点，计算其逻辑表达式，并将逻辑表达式的结果赋给状态标记。如果是TRUE，则文档与该查询匹配；如果是FALSE，则文档与该查询不匹配。如果是一个返回节点，在确定匹配成功或失败时，从缓存中删除相应节点。

3.缓存管理过程

在查询的过程中，由于需要单遍处理XML流，因此，当遇到返回节点的时候，要将该节点放入缓存中。缓存中存储的是可能的查询结果集，如前面所述，它对XML流数据处理的质量有着重要的影响。为了优化XML流处理的缓存管理，我们提出需要遵循的四个原则：(a)缓存中只存放可能构成结果元组的节点；(b)：尽早删除缓存中不满足条件的返回节点；(c)尽早将缓存中满足条件的节点构造为结果元组分发给用户，并且从缓存中删除后面不会再使用的返回节点；(d)共享缓存中的多个查询的返回结果的公共节点。

3.1建立缓存管理的数据结构

本发明定义一组缓存池来存放要缓存的节点。缓存池是存放缓存节点的动态数组，而对于每一个返回节点，都定义一个缓存池与其相关联。根据用户提交的查询可以得知不同缓存池中的节点之间应该具有的语义关系(父子关系、子孙关系、兄弟关系、共同祖先关系)，并用这样的关系将这些缓存池链接起来。这样，各个缓存池中节点根据缓存池之间的语义关系链接起来的一条路径，就构成了返回结果中的一个元组，同时又保证了元素之间的顺序关系。

考虑图3(a)显示一个XML文档D1和图3(b)显示的查询Q₁。对于文档D₁和查询Q₁，要向用户返回所有满足a的子孙c和b构成的元组，即{<c₁，b₁>，<c₁，b₂>}。根据查询Q₁，缓存池b中的节点与缓存池a中的节点之间的语义关系是：具有共同的祖先a。当查询处理遇到D₁中c₁元素时，因为它是返回节点，所以将其放入与c关联的缓存池；当遇到b1元素时，将b1放入与b相关联的缓存池中，因为c1和b1具有共同的祖先a，所以建立c1到b1的引用；当确定查询Q₁得到满足时，可将(c1，b1)组成的元组返回给用户；在遇到元素b₂时，将b₂放入与b相关联的缓存池中(由于b₂和c₁具有共同的祖先a，建立c₁到b₂的引用)，当确定询查Q₁再次得到满足(又得到一个满足查询的元组)，可将(c₁，b₂)组成的元组返回给用户。如图3(b)中的Buffer₁所示。

再考虑图3(c)中的文档D₂和图3(d)查询Q₂，用户希望返回所有由a元素的子元素c和b组成的元组。当查询处理遇到D₂中的c₁元素时，将其缓存于c的缓存池中；同样，c₂也是如此；遇到b₂元素时，将其缓存于b的缓存池中。根据查询Q₂，要求c的缓存池中的元素和b的缓存池中的元素是兄弟关系。现在，由于a是接受节点，故对其进行谓词逻辑表达式运算并确定结果为真，由此得到查询的一个匹配。此时，c的缓存池中分别有c₁和c₂元素，b节点缓存池中有一个b₂元素，因此，必须判定匹配的结果是(c₂，b₂)而不是(c₁，b₂)，因为c₁和b₂并不是兄弟节点。为此，本发明采用基于运行时栈的前缀编码来进行判断。

3.2建立基于运行时栈的部分二进制前缀编码表示

当返回结果中包含两个以上的节点时，如果要确定缓存中的节点是否构成合法的返回元组，就需要判断它们是否满足查询所要求的节点之间的关系，例如，子孙关系、父子关系、兄弟关系(如图3(c)中的c₂和b₂)、共同祖先关系(两个元素是否具有某个共同的祖先，如图3(a)中的c₁和b₂元素，其共同祖先是a元素)等。利用基于前缀的编码方法，可以很容易判断我们需要的各种关系。前缀编码的大致思想是：在一个文档树中，假定某个父节点的编码是P_Code，对于它的每个子节点Ci，算法分配给它们各自互不相同的某个独立编码Ci_Code，则子节点的最终编码是由父节节点编码作为前缀码跟自身的独立编码进行串接构成的，即C_Code＝P_Code·Ci_Code.由此可知，如果节点a是节点b的祖先，则b编码的前缀必然包含a的编码；如果节点a是节点b的兄弟，则a的前缀码必然与b的前缀码相同等等。

在实际实现中，本发明使用一种二进制串前缀编码方案。这种编码的方法是：根节点编码为空串empty；为任一个节点X下的第i个子节点Y分配一个二进制串bits(i)；子节点的编码Label(Y)就是其父节点的编码与分配的二进制串的连接即Label(X)·bits(i)。分配的二进制串bit(s)，必须满足子节点的编码是前缀无关(prefix-free)的，即没有一个子节点的编码是另一个的前缀。这种bit(s)函数有很多种，我们使用bits(i)＝1i-10.如图4所示(节点10不是节点0.10的祖先节点，因为10不是0.10的一个前缀。节点0.10与0.110是兄弟节点，则它们的前缀码(父节点的编码)必然相同)。根据前缀编码，通过两个基本操作(父子关系和子孙关系)可以确定两个节点之间的任何关系。

在本发明的查询匹配过程中，只需要在返回结果的缓存管理时候才会使用文档节点的二进制编码信息。因此，本发明不是对整个文档编码，而是只对进入运行时栈的节点编码，这样，通过缩小编码的范围，可以提高处理的效率。

定理1：在前面查询匹配算法中，对于XML文档D(它对应于一颗文档树T)和查询Q，进入运行时栈查询节点所对应文档元素构成了一棵文档树T′，T′与原文档树T同根，并且是T的一颗子树。

证明：从前面查询匹配算法的运算过程可以得知，处理引擎通过SAX解析器获得输入文档D的事件流，对文档D的处理顺序实际上是按照对其文档树T的先序遍历顺序进行的：对每一个到达的XML元素，进行节点测试和文档层次检查，当一个节点包含父子轴算子时，文档层次要求相同；当一个节点包含子孙轴算子时，忽略文档层次的检查.当查询节点名字是“*”时，节点名字的测试永远返回TRUE；如果节点检查返回TRUE(即节点匹配发生)，则相应的文档节点被压入运行时栈.因此，进入运行时栈的文档D的节点是与查询Q匹配的那些节点，而不满足查询匹配的节点是不会进入到运行时栈中的，那么，它对应的文档节点自然就是可能与查询匹配的那部分文档，而且是与原文档树T同根的文档树T′，显然，T′是T的一颗子树.

例如，图5的右面是用户提交的查询Q₃，左面表示的是对应的一颗XML文档树D₃。在XML流处理过程中，对于查询Q₃，进入运行时栈的查询节点对应的XML文档部分就是在文档树中用曲线勾勒出来的部分，这部分构成一棵与原文档的同根的子树.因此，由运行时栈驱动进行的前缀编码，只是对整个XML文档的一部分进行编码，而同时又能正确地反映文档节点之间的关系。

3.3进行返回结果的缓存管理。

返回结果的缓存管理包括下面几个主要功能：向缓存中加入返回节点；构造满足用户查询条件的元组，并将结果元组分发给用户；从缓存中删除无用的节点；缓存结果的共享。

(1)向缓存中加入返回节点。

对于XQuery查询的一颗紧凑查询树，当在XML流处理过程中遇到返回节点，则将该节点放入缓存。由于缓存中必然存放的是可能构成结果元组的节点，因此，遵循原则1是很自然的。

(2)构造结果元组。

在将缓存节点放入缓存池的时候，同时构造结果元组。直观地讲，构造结果元组的一个时机是在查询匹配过程完成后，通过不同节点集合之间的连接操作来确定哪些节点可以组成一个满足查询条件的结果元组。但这样做有两点不足：其一，构造的返回结果元组构造可能含有中间结果(即含有不满足用户查询条件的结果节点)，从而增加缓存的空间耗费；其二，节点集合之间的连接操作会增加系统的时间耗费。因此，本发明提出在查询匹配的过程中，根据节点的二进制前缀编码和缓存池之间的语义链接来构造满足查询条件的结果元组。

(3)缓存管理的删除操作

要遵循原则3，需要在两种情况下及时从缓存中删除相应节点：

第一，在查询匹配的过程中，当确定匹配不成功时，及时从缓存中删除相应的结果节点(如果缓存中存放了这样的节点)。以节省缓存管理的内存耗费以及提高缓存管理的性能。根据前面的XML流处理算法很容易实现这一点。考虑图6所示的例子，当遇到b₁元素的结束标记的时候，通过对b的逻辑表达式的计算(其值为“FALSE”)，可以确定b₁和c₁不满足查询匹配条件，因此，这时应该及时将b₁和c₁从缓存中删除(如图6的Buffer4所示)。

第二，另一种需要执行删除操作的是，在查询匹配成功时，除了要向用户分发查询结果集，直观上讲，同时也应该从缓存中删除相应节点(如图6，在查询匹配成功时，b₂、c₂以及d₂构成了返回结果的一个元组，则在向用户分发后，可以将它们从缓存中删除)。但是，实际情况要复杂得多。由于一个XML文档流中会存在多个文档片断满足一个XQuery查询，并且不同的片断之间会共用某些结果节点，因此，并不总是能在查询匹配时立即删除某些节点，需要找出合适的时机进行删除操作，以改进缓存管理的空间耗费。我们再回过头来考虑图3所示的例子：对于图3(a)所示的文档D₁和图3(b)所示的查询Q₁，在XML流处理过程中，当遇到内层a元素的结束标记时(D1文档中的第5行)，查询匹配成功，得到一个元组<c₁，b₁>，这时可以将该元组分发给用户，但是却不能删除缓存中的c1和b1，因为对于该查询，可能有多个与查询匹配的元组，后面遇到的b元素还可能与c₁构成满足条件的元组。在这个例子中，造成这种情况的原因是，D₁是递归文档并且查询Q₁中a与c和b之间是子孙轴(“//”)。而对于图3(c)的文档D₂和图3(d)的Q²，在遇到内层的a元素的结束标记时(D₂文档中的第5行)，查询匹配成功，得到一个元组<c₂，b₂>，而这时显然应该可以将c₂和b₂从缓存中删除。

对于一个查询和一个文档，另一种使得有多个匹配的元组的原因是：文档的DTD中含有1对多的关系。考虑DTD：<！ELEMENT a(b，c+)>，从该DTD可知，a与b是1对1关系，a与c是1对多关系，从而可推知，对于查询“a[b][c]”(假定b和c是返回元素)，b与c是1对多关系，也就是说，一个b元素可能与多个c元素构成多个返回元组。

从上面的分析可知，造成这种复杂性的原因是递归文档和查询中的“//”，以及元素之间的1对多关系。但是，在有些应用中，并不知道关于DTD或XML Schema的任何信息，为了及时删除缓存中的已经“无用”节点(这里“无用”的含义是指，将这些节点构成的元组分发给用户后，其中的节点不会与查询处理后面遇到的节点构成新的返回元组)，我们分两种情况确定查询匹配成功后缓存节点删除的时机。

第一种情况：如果构成返回元组的节点是通常查询节点，即不是任何一个谓词节点的子节点，则在遇到该节点的关闭标记(即CLOSE事件)时，在缓存中执行对该节点删除操作。图7演示了该过程。

第二种情况：如果构成返回元组的节点是谓词子树的子节点(包含谓词节点)，则本发明给出如下定义：

定义1：最低公共祖先谓词节点(LCAPN)：如果查询中的一个节点是LCAPN，则需满足下列条件：

●该节点是一个谓词节点。

●该节点是所有返回节点的一个公共祖先。

●在所有返回节点的全部公共祖先中，该节点不是其他任何一个的父亲节点。

根据LCAPN的概念，在文档处理过程中，当遇到文档中对应于LCAPN的节点的关闭标记(即CLOSE事件)，并且能够判断查询匹配成功时，即可将缓存中的返回节点从缓存中删除。图8演示了该过程。

在图8中，Q₆中的LCAPN是“c”，返回节点是“d”和“e”，因此，在遇到文档D6中的“c”的关闭标记时(即“<c1/>和<c2/>”)，从缓存中删除节点。

对于递归的嵌套文档，并且查询中的LCAPN与返回节点之间包含“//”，就可能会出现这样一种情况：文档中存在着处于不同层次上的多个节点与LCAPN对应，这时，只能在遇到相应的最外层节点的关闭标记时执行缓存的删除操作。例如图3(a)和图3(b)中，查询Q₁的LCAPN是“a”，在文档D₁中(该文档是递归嵌套文档)，它对应于第1行的“<a>”和第2行的“<a>”，由于Q₁中的LCAPN与其返回节点(“c”和“b”)之间是“//”关系，因此，LCAPN对应于文档最外层的“a”，即D₁中第一行的“<a>”，也就是说，在遇到第7行的“</a>”时删除缓存中所有的节点；而在图3(c)和图3(d)中，虽然D2是递归嵌套文档，但由于Q₂中的LCAPN(“a”)与返回节点(“c”和“b”)之间是“/”，因此，在遇到第6行的“</a>”时，将“b₂”和“c₂”从缓存中删除，在遇到第7行的“</a>”时，将“c₁”从缓存中删除。

(4)缓存管理的共享

前面说明了针对单个查询的缓存管理问题。在实际的系统中，XML流数据处理系统通常面对的是大量用户。因此，要求系统具有同时处理大量查询的能力，而来自用户的大量查询中，可能会具有许多共同的部分，共享其共同部分可以节省系统的存储空间和执行时间，对改善系统性能非常重要。为此，本发明将所有XQuery的紧凑查询树合并为一个单一的共享前缀的紧凑查询树。其中，节点名以及算子(“/”或“//”)相同的前缀可以合并。另外，若返回结果中的节点是一个多个查询共享的节点，则缓存结果节点的缓存池就被这些查询所共享。

如同共享前缀的紧凑查询树中的其他节点一样，共享的结果节点的缓存池关联有查询标识。如果两个缓存池被多个查询共享，则两个缓存池构成的缓存池链也同样被共享。因此，在多查询的情况下，缓存结果的共享不仅有效地节省了缓存的空间，同样优化了构造缓存结果元组的性能。但是，缓存的共享可能延迟共享缓存节点的删除时间，因为对于一个查询而言可以删除的缓存节点，可能还被其他查询使用，而只有共享该缓存节点的所有查询都认为这个节点″无用″时，才可将其从缓存中删除。

本发明提出一种新方法(基于部分二进制前缀编码的XML流缓存管理方法)，可以应用于股票行情系统、交通控制系统、信息发布与订阅等应用中，具有下面独特的特性：

1、为了能够有效减少缓存的内存耗费，提高处理性能，该发明提出的方法遵循四个基本原则：a)缓存中只存放可能构成结果元组的节点；b)尽早删除缓存中不满足条件的返回节点；c)尽早将缓存中满足条件的节点构造为结果元组分发给用户，并且从缓存中删除后面不会再使用的返回节点；d)共享缓存中的多个查询的返回结果的公共节点。

2、当一个XML文档流中存在多个文档片断满足一个XQuery查询的时候，需要确定哪些节点会构成一个满足用户查询的返回结果集的元组。本发明利用节点间语义关系连接起来的缓存池，来存储XQuery的返回节点，并通过运行时栈驱动的基于二进制的前缀编码，在运行时确定结果集中节点之间的关系，尽早构成返回结果元组，避免了中间结果集之间的连接操作。

3、有些情况下，尤其是在XQuery查询中包含″//″并且XML文档中含有递归、嵌套结构的时候，一个XML文档流中会存在多个文档片断满足一个XQuery查询，这时，面对XML流，没有足够的信息来判断缓存中的节点是否还会被后面的匹配结果用到。因此，本发明定义一个查询的″最低公共祖先谓词节点(LCAPN)″，来帮助我们尽早删除缓存中的节点，而不是等到整个文档结束之后。

4、本发明的缓存管理方法能够同时单遍处理多个含有复杂谓词的XQuery，并支持多个XQuery查询结果中公共缓存节点的共享。

附图说明

图1为XQuery查询示例。

图2为XQuery的紧凑查询树。

图3为查询例子，其中(a)显示一个XML文档例子D1，(b)显示查询例子Q₁，(c)显示XML文档例子D2，(d)显示查询例子Q2。

图4为二进制前缀的编码方案。

图5为运行时栈驱动的前缀编码示例。

图6为查询匹配失败时缓存节点的删除。

图7为缓存节点删除例子1。

图8为缓存节点删除例子2。

图9为本发明与XSQ在性能方面的比较。其中，(a)为Q1的实验结果，(b)为Q2实验结果。

图10为LeoXSSII，XSQ以及XMLTaskForce在内存实验方面的比较。其中，(a)为使用10M数据集的实验结果，(b)为使用30M数据集的实验结果。

图11为查询文档大小变化对查询性能影响。其中，(a)为文档大小为1M，(b)为文档大小为3M。

图12为文档大小为3M情况下，系统的内存使用随查询数目增加的变化情况。

具体实施方式

基于部分二进制前缀编码的XML流缓存管理方法是与查询匹配方法集成在一起的，包括两部分：第一部分是处理XML的OPEN标记的部分，第二部分是处理CLOSE标记的部分。在实施该方法该时，需要与基于事件的XML解析器集成在一起(例如IBM的解析器^[18])，通过解析器来回调该方法。

算法使用伪码描述如下：

缓存管理算法(OPEN部分)

输入：即将压入运行时栈的活跃查询节点QNode；

输出：查询匹配发生时，从缓存中搜集结果输出。

1.Element＝QNode.Name；

2.Query＝Current Query；

3.BpEncoder＝Current Binary Prefix Encoder；

4.If(Query is a simple query AND Query matches input document)

5.   Collector.outputResult(GRT.TupleHead，Element)；

6.   Collector.clearRubbish()；

7.Else

8.    If(Query is a twig pattern AND GRT.acceptingNode.evaluate()＝TRUE)

9.       Collector.outputResult(GRT.TupleHead，Element)；

10.          Collector.clearRubbish()；

11.      Endif

12.   Else

13.    If(QNode is a RETURN node)

14.       NewBufferNode＝new BufferNode(Element，BpEncoder.Code)；

15.       QNode.addBufferNode(NewBufferNode)；

16.       SL＝QNode.SemanticLink；

17.       If(SL！＝NULL)

18.           RefQNode＝SL.Reference；

19.           Foreach BufferNode in RefQNode.BufferPool

20.              If(NewBuffrNode and BufferNode SATISFY SL.Relationship)

21.                  BufferNode.addTupleLink(NewBufferNode)；

22.                Endif

23.              Endfor

24.            Endif

25.          Endif

26.        Endif

CLOSE部分

输入：即将弹出运行时栈栈顶的查询节点QNode；

输出：查询匹配发生时，从缓存中搜集结果输出。

1.Element＝QNode.Name；

2.IfQNode is a LCAPN node

3.    Collector.outputResult(GRT.TupleHead，Element)；

4.  Collector.clearRubbish()；

5.Endif

6.If(GRT.acceptingNode.evaluate()＝TRUE)

7.    Collector.outputResult(GRT.TupleHead，Element)；

8.     Collector.clearRubbish()；

9.Endif

二进制前缀编码的定义如下：

class BinaryPrefixEncoder{

   //operations

   int size()；               //取得动态数组的大小；

    void reset(int pos)；     //重置pos处的前缀码，设置为0；

   void assignbits(int pos)； //重新分配pos处的前缀码，在原前缀码前加1；

   void allocate(int pos)；   //在pos处新开辟一个前缀空间；

   //data

    ArrayList<BitSet>Code；

} 

基于运行时栈的二进制前缀编码：

输入：一个二进制前缀编码器BpEncoder，全局运行时栈对象RmStack；

输出：编码器BpEncoder中记录了运行时栈顶节点所匹配元素的前缀编码。

EncodeOnPush(BpEncoder)

1.Index＝RmStack.size()-2；

2.If(Index>BpEncoder.size()-1)

3.    BpEncoder.allocate(Index)；

4.Else

5.    BpEncoder.assignbits(Index)；

6.Endif

EncodeOnPop(BpEncoder)

1.Index＝RmStack.size()-1；

2.If(index<BpEncoder.size())

3.    BpEncoder.reset(Index)；

4.Endif

缓存节点的数据结构定义如下：

class BufferNode{

     String    ElementName；       //元素名称；

     BitSet[]    BinaryPrefixCode；    //二进制前缀编码；

     ArrayList<BufferNode>NextNodes；  //元组链；

    SemanticLink Next；//增加语义链；

}

缓存节点之间语义关系的定义：

class SemanticLink{

   int    Relationship；//语义关系；

    QNodeReference；//链头节点；

}

查询节点的定义：

class QNode{

    String    Name；  //节点名称

    Boolean  Existed；//节点存在标记

    Hashtable<String，QNode>  Children；       //子节点哈希索引

    Hashtable<Qid，QInfoItem>  QInfoItems；    //关联信息项哈希索引

    // operations

    void addBufferNode(BufferNode bn)；   //加入缓存节点bn；

    void removeBufferNode(BufferNode bn)；//删除缓存节点bn；

    //data

    LinkedList<BufferNode>BufferPool；

}

本发明的积极效果

本发明用Java实现了该方法，实现的系统称为LeoXSSII。系统运行的环境是Eclipse3.1，机器的主频是2.7G，内存为512M。构成实验的组件包括：文档生成器，DTD解析器，基于事件的XML解析器等。

本发明能够同时处理多个XQuery，每一个XQuery可以指定多个返回结果。在现有方法中，TurboXPath、XSQ和FluX采用XQuery表示用户的查询不具备同时处理多个查询的能力。

因此，本发明通过两部分实验来说明其效果：第一部分是考虑单个查询、单个返回结果，从系统的运行性能和内存使用情况两个方面，将该方法与一个XML流数据处理系统XSQ和一个XML主存数据库(非流数据)XMLTaskForce^[19]进行比较；第二部分实验说明在同时处理大量查询，以及指定不同返回节点个数的时候，该方法在内存使用和性能方面的表现。

在这第一部分的实验中，将本发明的方法与XSQ和XMLTaskForce进行比较。其中使用两个数据集：第一个数据集是XMark^[20]，使用默认的auction DTD；第二个是用IBM的文档生成器以BookDTD^[21]为输入手工生成的数据集合，其中参数NumberLevelsbounds设为15，参数MaxRepeats设为6，其余的使用默认参数.这些数据集的大小是从8M到32M不等.由于XSQ和XMLTaskForce只支持一次处理一个查询且返回一个元素，因此，特定设计了一些查询来进行实验，表1列出了其中使用的一些查询。

图9给出了本发明和XSQ在性能方面的比较(XSQ用Java实现，其源码可从http://www.cs.umd.edu/projects/xsq/xsqf.tar.gz获得)，实验的数据集是由BookDTD手工生成的数据集合(使用XMark得到的实验结果类似)，查询是表1对应的Q1和Q2.我们用下面几个指标进行实验比较和分析：(1)输入文档的大小，(2)不同的查询(Q1和Q2)，(3)性能.

图9的X轴反映了输入文档大小的变化(从8M到32M)，Y轴反映的是系统的性能(m)。从实验结果可以看出，对于查询Q1和Q2，随着文档大小的增加，LeoXSSII的处理时间缓慢增加，而XSQ的处理时间增加幅度较大，并且LeoXSSII的性能始终优于XSQ。

图10给出了LeoXSSII，XSQ以及XMLTaskForce在内存实验方面的比较，实验的数据集同样是使用由BookDTD手工生成的数据集合(使用XMark得到的实验结果类似)。图中Y轴是表1对应的Q1，Q2和Q3，X轴表示系统的内存使用峰值。我们分别使用10M和30M的数据集进行实验，实验结果表明LeoXSSII和XSQ在内存使用方面文档流的大小对其产生的影响非常小，内存使用峰值几乎没有变化。而主存XML数据库XMLTaskForce在内存使用方面则对输入文档的大小很敏感，在输入文档大小增加的时候，内存使用峰值增加很快。另外，LeoXSSII在内存使用方面的情况要明显好于XSQ，而XSQ则明显好于XMLTaskForce。

在第二部分的实验中，由于还没有具有同样功能的类似系统，本发明考虑在同时处理大量的XQuery的情况下，LeoXSSII在性能和内存使用方面的情况。我们使用实验的度量指标如下：(1)输入文档的大小，(2)查询的数目，(3)性能，(4)内存使用峰值，(4)返回结果所包含的元素个数(即输出元组中的元素个数).这里使用的数据集是DBLP^[22].

如图11所示，文档的大小分别是1M和3M，X轴表示查询的数目从5000递增到100000，Y轴表示性能的变化情况，图表反映的是随着查询数目的递增(从5000到100000)，查询的返回结果所包含元素的数目(从一个元素到三个元素)的变化，系统在输入文档流分别为1M和3M的情况下性能的变化情况.从实验结果可以看出，随着查询数量的增加，以及文档大小的增加(1M到3M)，系统的运行时间逐步递增.但查询数目从50000增加到100000时，系统处理时间增加幅度较大。而输出结果包含的元素个数(这里没有考虑输出结果的分布情况，即它们之间是子孙关系还是兄弟关系等)，对系统性能的影响不明显。

图12显示了文档的大小为3M的情况下，系统的内存使用随查询数目增加的变化情况：随着查询数目的增加，系统使用的内存逐步增加。在查询数目很大的时候，每一个查询数目的返回结果数目虽然不同，但整体分布情况大致相似，因此，对内存使用的影响不大。

表1实验中使用的查询

    BookDTD数据集 Q1//book//section//title Q2/section[figure]/title Q3/book//section[title and figure]/^*

参考文献

[1]XQuery 1.0：An XML Query Language.http://www.w3.org/TR/2006/CR-xquery-20060608/

[2]Anders Berglund，Scott Boag，Dong Chamberlin，Mary F.Fernandez，Michael Kay，Jonathan Robie，and Jrme Simon.XML Path Language(XPath)2.0 W3C working draft 16.Technical Report WD-xpath20-20020816：USA，World Wide Web Consortium，2002.http://www.w3.org/TR/2002/WD-xpath20-20020816/.

[3]Altinel，M.，and Franklin，M.J.Efficient Filtering of XML Documents for SelectiveDissemination of Information.Abbadi，A.E.，Brodie，M.L.，Chakravarthy，S.，Dayal，U.，Kamel，N.Schlageter，G.，Whang，K.Y.，eds.Proceedings of the 26^th InternationalConference on Very Large Data Bases(VLDB00).Cairo，Egypt：Morgan Kaufmann，2000.53-64.

[4]Yanlei Diao，Mehmet Altinel，Michael J.Franklin，Hao Zhang and Peter Fischer.PathSharing and Predicate Evaluation for High-performance XML Filtering.ACM Transactionson Database System(TODS03).2003，28(4)：467-516.

[5]Gupta，A.and Suciu，D.Stream Processing of XPath Queries with Predicates.Halevy，A.Y.，Ives，Z.G.，Doan，A.，eds.Proceedings of 2003 ACM SIGMOD International Conference onManagement of data(SIGMOD03).San Diego，California：ACM Press，2003.419-430.

[6]Green，T.J.，Miklau，G.，Onizuka，M.，and Suciu，D.Processing XML Streams withDeterministic Automata and Stream Indexes.ACM Transactions on Database Systems(TODS04).2004，29(4)：752-788.

[7]Dan Olteanu，Tobias Kiesling，Francois Bry.An Evaluation of Regular Path Expressionswith Qualifiers against XML Streams.Dayal，U.，Ramaritham，K.，Vijayaraman，T.M.，eds.Proceedings of 19^th International Conference on Data Engineering(ICDE’03).Bangalore，India：IEEE Computer Society，2003.702-704

[8]Bertram Ludscher，Pratik Mukhopadhyay and Yannis Papakonstantinou.ATransducer-Based XML Query Processor.Bressan，S.，Chaudhri，A.B.，Lee，M.L.，Yu，J.X.，Lacroix，Z.，eds.Proceedings of the 28^th International Conference on Very Large Data Bases(VLDB02).Hong Kong，China：ACM Press，2002.227-238.

[9]GAO Jun，YANG Dong-Qing，TANG Shi-Wei，WANG Teng-Jiao.Tree-Automata BasedEfficient XPath Evaluation over XML Data Stream.Journal of Software.2005.16(2)：223-232.

[10]Bruno，N.，Gravano，L.，Koudas，N.，and Srivastava，D.Navigation-vs.Index-Based XMLMulti-Query Processing.Dayal，U.，Ramaritham，K.，Vijayaraman，T.M.，eds.Proceedingsof the 19^th International Conference on Data Engineering(ICDE’03).Bangalore，India：IEEE Computer Society，2003.139-150

[11]Xueqing Gong，Weining Qian，Ying Yan，and Aoying Zhou，Bloom Filter-based XMLPackets Filtering for Millions of Path Queries.Proceedings of the 21^st InternationalConference on Data Engineering(ICDE’05).Tokyo，Japan：IEEE Computer Society，2005.890-901.

[12]Joonho Kwon，Praveen Rao，Bongki Moon，Sukho Lee.FiST：Scalable XML DocumentFiltering by Sequencing Twig Patterns.Bhm，K.，Jensen，C.S.，Haas.L.M.，Kersten，M.L.，Larson，P.，Ooi，B.C.，eds.Proceedings of 31^st International Conference on Very Large DataBases(VLDB05).Trondheim，Norway：VLDB Endowment，2005.217-228.

[13]Ziv BarYossef，Marcus Fontoura，Vanja Josifovski，Buffering in Query Evaluation overXML Streams.PODS 2005 June 1315，2005，Baltimore，Maryland.

[14]FENG PENG and SUDARSHAN S.CHAWATHE.XSQ：A Streaming XPath Engine，ACM Transactions on Database Systems，Vol.30，No.2，June 2005，Pages 577-623.

[15]Yanlei Diao，Shariq Rizvi，and Michael J.Franklin.Towards an Internet-Scale XMLDissemination Service.In Proceedings of VLDB2004，August 2004

[16]Hiroyuki Uchiyama Makoto Onizuka Takashi Honishi，Distributed XML Stream FilteringSystem with High Scalability，Proceedings of the 21st International Conference on DataEngineering(ICDE2005)

[17]B.Ludascher，P.Mukhopadhay，Y.Papakonstantinou“A Transducer-Based XML QueryProcessor”，In VLDB 2002

[18]David Megginson.Simple API for XML.http://sax.sourceforge.net

[19]G.Gottlob，C.Koch，and R.Pichler.Efficient Algorithms for Processing XPath Queries.InProceedings of VLDB，2002

[20]BUSSE，R.，CAREY，M.，FLORESCU，D.，KERSTEN，M.，MANOLESCU，I.，SCHMIDT，A.，AND WAAS，F.2001.Xmark：An XML benchmark project.http://monetdb.cwi.nl/xml/index.html..

[21]W3C.XML Query Use Cases，2003.http://www.w3.org/TR/xquery-use-cases.

[22]LEY，M.2001.DBLP DTD.http://www.acm.org/sigmod/dblp/db/about/dblp.dtd.