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

摘要

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

主权项

一种基于部分二进制前缀编码的XML流缓存管理方法，其特征在于具体步骤如下：(1)构造XQuery查询的紧凑查询树，将用户提交的所有XQuery查询构造为单颗紧凑查询树，并为每一个返回节点构造一个缓存池；在紧凑查询树中，所有查询共享公共前缀；(2)查询匹配，查询匹配过程包括自顶向下和自底向上两部分，在查询匹配的过程中，执行缓存管理的基本操作，包括进行缓存结果的加入和删除；(3)缓存管理过程，缓存管理过程优化与XQuery查询匹配的返回结果的缓存，包括：(a)建立缓存管理的数据结构：XQuery查询中的每一个缓存节点对应于一个缓存池，所有缓存池构成一个链表，其中，每两个缓冲池之间的链接由缓存池中返回节点之间的语义关系定义，包括父子关系、子孙关系、兄弟关系和共同祖先关系；(b)建立基于运行时栈的部分二进制前缀编码表示，通过运行时栈驱动基于二进制的前缀编码，在运行时确定结果集中节点之间的关系，迟早构成返回结果元组，避免中间结果集之间的连接操作；(c)进行返回结果的缓存管理；所述的XQuery的紧凑查询树，定义如下：定义1：一颗紧凑查询树是表示XQuery的查询树，其中的节点称为查询节点，记为QNode，具有惟一标识，查询节点分为以下两种类型：(1)OQNode：不带有谓词的定位步，称为通常查询节点，在紧凑查询树中，OQNode关联相关信息，包括节点名字“name”和表示父子“/”或子孙“//”关系的算子，用两元组表示；(2)PQNode：带有谓词的定位步，称为谓词查询节点，谓词查询节点是紧凑查询树中的特殊节点，它通过AND/OR逻辑谓词将其子树连接起来；除了节点标识，节点名和父子或者子孙外，还关联一个逻辑表达式；该逻辑表达式在内部表示为抽象语法树；该抽象语法树的每一个叶子节点都维护一个到其对应的节点的引用；(3)RNode：返回结果节点，即是指那些构成XQuery结果元组的节点；定义2：谓词子树，在一个紧凑查询树中，以距离根节点最近的谓词节点为根所形成的子树称为谓词子树；同时扩充相应的节点结构：谓词子树中的OQNode，也关联一个逻辑表达式，该逻辑表达式是只含有一个项，即其孩子节点的标识；而如果OQNode是叶子 节点，则含有一个逻辑标记，初始为真，当遇到CLOSE事件后，将逻辑标记的值赋为假；定义3：接受节点，在一颗紧凑查询树的表示中，距离根节点最近的谓词节点称为该树所表示查询的接受节点；如果计算过程中，接受节点相关逻辑表达式的值为真，则该文档与查询匹配；如果一个XQuery是不带谓词的一般查询XP{/，//，*}，其接受节点则是其通常查询树的叶子节点；如果在匹配过程中到达接受节点，则该文档与查询匹配；所述的查询匹配，其过程分为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，则文档与该查询不匹配；如果是一个返回节点，在确定匹配成功或失败时，从缓存中删除相应节点；所述建立基于运行时栈的部分二进制前缀编码表示，具体步骤如下：根节点编码为空串empty；为任一个节点X下的第i个子节点Y分配一个二进制串bits(i)；子节点的编码Label(Y)就是其父节点的编码与分配的二进制串的连接即Label(X)·bits(i)；分配的二进制串bit(s)，必须满足子节点的编码是前缀无关的，即没有一个子节点的编码是另一个的前缀；根据前缀编码，通过两个基本操作确定两个节点之间的任何关系。