基于转换累计自动机
,我们给出查询集合动态
增加过程中查询执行器的调整算法
1已有的查询自
动机也可以看做是采用动态增加的策略来构建的

输入
: XPath查询
p;查询集合自动机
A =

(b)自动机
B; (c)自动机
C1 ,F1 ,C1)1
输出
:增加了查询
p之后的转换累计自动机
A 1
步骤
11根据查询
p,构造特定查询自动机
P =
(Q2 ,Σ2 ,i2 ,δ2 ,F2 ,C2);
步骤
21查询自动机
P执行确定化操作
,对于
P的每个状态转换
t,t [count] =1 ;

步骤
31自动机
A的初始状态
i1标记为待处理
状态
a,i1状态在自动机
P的对应状态
i2作为待处
理状态
p;

步骤
41假定自动机
P当前状态
p,转换规则
tp:{ p} -D1 →{p1};自动机
A当前状态
a,转换规
则
ta:{ a} -D2 →{a T 1} 1则
:

步骤
4111如果
D1和
D2没有交集
,则自动机
A增加状态转换
t :{ a} -D1 →{ ap1 },t [count] =
1 ,同时
A中的状态集合增加
{ ap1 },A中数据输入
集合增加
{D1 } 1 ap1状态标记为待处理状态
, ap1
状态在
P中的对应状态为
p1 ;

步骤
4121如果
D1和
D2等价
,自动机
A中
ta
[ count ] = ta [count] +11标记
a1状态为待处理状
态
,a1状态在
P中的对应状态为
p1 ;

步骤
4131如果
D1和
D2存在交集
,但是并不
完全等价
,令
D11 = D1 ∩D2 ,D12 = D1-D2 ,D13 =
D2-D1 ,则自动机
A增加状态转换
t1= { a} -D11

→{a1 p1},t1 [ count ] = ta [count] + tp [count],标
记
a1 p1状态为待处理状态
,a1 p1状态在
P中的对
应状态为
p1 ;修改转换
ta为转换
{ a} -D12 →{a2},
其中转换累计不变
;增加转换
t2 :{ a} -D13 →
{ ap1},t2 [ count ] =1 ,标记
ap1状态为待处理状
态
, ap1状态在
P中的对应状态为
p1 ,同时增加

计算机研究与发展　
2005 , 42 (5)

774

{ ap1}到
R中的状态集合
,增加
{D13 }到
R的数据
集合
;

步骤
51按照步骤
4重复处理自动机
A的所有
待处理状态
,直到完毕为止
1

分析上述流程
,我们知道在增量过程中产生新
状态是增量计算复杂性的根源所在
,而新状态的产
生主要来源于
XPath查询的
“
∥”和“
3 ”操作符号
1
314　XPath查询执行器中查询的动态删除

给定
XPath查询
p,如何在查询集合自动机中
删除查询
p所关联的状态和转换是本节所研究的
一个问题
1这个过程相当于动态增加的逆过程
1按
照前面的分析
,实现动态删除可能的操作包括在查
询集合自动机中定位被删除的特定查询自动机的相
关状态转换
,减少关联状态转换的计数
,删除计数为
0的状态转换

1下面,给出整个算法的具体描述1
算法21 XPath查询的动态删除1
输入:XPath查询p ;查询集合自动机A 1
输出:删除查询p后的查询集合自动机A 1
目1图3说明增量维护之后的查询集合自动机在空
间代价上并不能等价于直接构建得到的查询集合自
动机1
Fig1 3　The illustration of the problem on redundancy
space1 (a) Automata A ; (b) Automata B ; (c) Automata
C ; and (d) Automata D1
图3　空间冗余问题示意1 (a)自动机A ; (b)自动机B ;
(c)自动机C ; (d)自动机D
②特定查询自动机
①根据查询构造特定查询自动机P;
P执行确定化操作
;
③获取查询集合自动机
A的初始状态
a1和特
定查询自动机
P的初始状态
p1 ;
④假定自动机
P在状态
p1上接受数据
D转
换到状态
p2 ,查询集合自动机
A按照状态转换
ta
在状态
a1上接受数据
D转换到状态
a2 ,
ta [count] = ta [count] -1 ,如果
ta [count] =0 ,则
删除转换
ta;

⑤递归处理下一个状态对
(a2 ,p2 ),直到自动
机
P到达终止状态
1

315　转换自动机删除后空间冗余问题

以上两节提出的增量维护策略能够正确调整查
询执行器
,从而满足最新查询集合的要求
1但是
,增
量维护可能带来查询执行器内部空间冗余
,我们通
过一个例子说明这个问题

例
21 XPath查询
p1
1= ∥a, XPath查询
p2=
PaPb,我们分别构造图
3中确定化的查询自动机
A
和
B,执行合并操作
,获得了查询自动机
C,在查询
自动机
C中删除查询自动机
B,得到查询自动机

D 1
我们没有在自动机
C中注明转换累计
1实际
上
,自动机
C中状态
“13”到状态
“23”转换的计数是
2 ,状态
“23”到状态
“15”转换的计数是
21自动机
A
和自动机
D在表达能力方面是一致的
,也都是确定
自动机
1但是
,自动机
D的状态和状态转换规则数
目都远远大于自动机
A的状态和状态转换规则数

我们以图
3为例分析上述问题出现的原因
1自
动机
D中“24”状态接受数据
b, a,[all -a -b]转
换到新的状态
1自动机
A中“1”状态接受数据
a和
[ all -a]转换到新的状态
1数据集合划分得越细
,
自动机中状态和状态转换规则数目越多
1在
XML
数据流处理环境中
,由于系统资源有限
,避免空间冗
余是很必要的
1我们进一步分析这一问题
,发现支
持数据集合的状态转换规则在查询追加过程中产生
大量新状态和新状态转换规则是空间冗余产生的
原因

1
在当前的
XML数据流环境中
,XML数据大都
遵循
D TD或者
XML Schema模式的约束
1XML数
据模式会对查询处理器的增量维护产生两方面的影
响
:一方面
,由于增量操作不会产生大量新的状态
,
因而
XPath增量增加步骤的时间复杂性会显著降
低1基于本文提出的转换累计自动机
,新增查询的
作用主要体现在状态转换之上累计值的增加
1另一
方面
,由于增加过程不会产生大量的无效状态
,删除
操作不会产生明显的空间冗余问题
1我们通过实验
证明了上述结论

3.3要求对应画出后边fig.3那个图