一种基于决策树的选择查询算法

邓冬梅 谭键龙

1. 湖南师范大学计算机教学部，湖南 长沙 410081 2. 中国科学院计算技术研究所，北京 100190

一种基于决策树的选择查询算法

邓冬梅1谭键龙2

1. 湖南师范大学计算机教学部，湖南 长沙 410081 2. 中国科学院计算技术研究所，北京 100190

本文提出了一种基于决策树的查询索引结构，笔者称之为查询决策树。查询决策树不仅利用了查询内各个谓词间的合取关系，还充分利用了单个属性上的谓词索引。

数据流管理系统;查询决策树

引言

流动数据处理长期以来没有受到足够重视，目前并不存在像数据库管理系统一样的成熟的、通用的数据流处理平台。但随着互联网技术的发展和广泛应用，国际、国内对数据流的研究已逐步得到重视。

1.选择多查询处理及其分类

数据流管理系统和传统的数据库管理系统最重要的区别之一是持续查询在数据流管理系统中的重要地位，而选择查询是数据流持续查询中最基本、也是最重要和使用得最广泛的一类查询。

直观的说，一个选择查询就是一个过滤条件，当流数据到达时，数据流管理系统查询处理引擎在选择查询上进行条件测试，如果条件测试的结果为真，我们说这个选择查询得到满足（或者说这个选择查询得到匹配）。

数据流管理系统中一般都注册有大量的选择查询。数据流S上的选择多查询处理是指：给定S上的选择查询集合Qset{Q1,Q2,…,Qn}，当S的一个数据元组t到达时，返回查询集合中所有取值为真的查询的编号。

Qset也可用表1直观地表示，其中谓词P[i, j]是查询Qi在属性aj上的谓词。

表1 选择多查询的表格表示

一个流数据元组到达后，按照多查询处理算法在表1中的处理顺序，已有的多查询处理算法可分为3类：

1.1 行顺序处理方法：当一个数据流元组到达后，多查询处理引擎逐行（逐查询）处理表1中各查询；

相对于传统的人际互动、书信来往等交往方式，新媒体环境下人们之间的交往更加多样化。除了传统交往方式外，QQ、BBS、微博、微信等使大学生人际之间的交往更加多样和便捷。

1.2 列顺序处理方法：当一个数据流元组到达后，多查询处理引擎逐列（逐属性）处理表1中的查询；

1.3 行列交错处理方法：当一个数据流元组到达后，多查询处理引擎按照行（查询）、列（属性）交错的顺序处理表1中的查询。

2.基于决策树的选择查询算法

本文提出一种新的数据流选择多查询的处理算法，这种多查询的索引具有决策树形式的结构，笔者称之为数据流多查询的决策树索引算法。多查询的决策树索引同时利用了单个属性上的谓词索引和单个查询内各属性谓词间的合取关系，因而能更大程度减少冗余计算。各种单属性上的谓词索引能很容易集成到多查询的决策树索引中。这种多查询的决策树处理算法被归入到行列交错处理算法类别。

2.1 查询决策树的构造

设数据流S用模式R(a1:Ω 1, a2: Ω 2, …, am: Ω m)描述，Qset{Q1,Q2,…,Qn}是在S上定义的查询集合，下面讨论如何在Qset上建立基于决策树的查询索引。

查询决策树是以自上向下的方式构造的，在构造的过程当中，每个结点关联一个查询集合和一个属性集合，查询集合是以当前结点为根结点的子树所索引的查询子集，属性集合是当前结点可选的划分属性集合。构造从决策树的根结点开始，根结点关联的查询集合包含了原始查询集合Qset中的所有查询，根结点关联的属性集合包含了数据流模式S的所有属性。利用一个先进后出的栈(stack)来保存将要被扩展的结点，及其关联的查询集合和属性集合。初始化栈时，把根结点及其关联的查询集合和属性集合压入栈，然后每次从栈的头部弹出一个待扩展结点，将这个结点扩展，再将扩展得到的新结点压入栈，重复这个过程直到栈变为空为止。使用栈来保存待扩展结点，按照先进后出的顺序依次扩展每个结点，是一种深度优先的树构造策略。

假设当前从栈顶弹出的待扩展结点关联的查询集合为Qset{Q1,Q2,…,Qn}，属性集合为Aset{a1, a2, …, am}。从Aset中选择一个属性做为划分属性。预先对数据流的各属性赋以一个序号，结点扩展时总是选择Aset中序号最小的属性做为划分属性。

条件(I)和(II)保证了，aj的任何一个可能取值落入且仅仅落入某一个值域子集σ k（1≤k≤s）。条件(III)保证了，对于任意值域子集σk，任意查询在划分属性上的谓词P[i,j]确定的值域子集ωi要么完全包含σk，要么σk和不相交。等价的描述是，对于σk（1≤k≤s）中的任意两个不同值x和y，P[i,j](x)=P[i,j](y) (" 1≤i≤n, 1≤j≤m)。在满足上面三个条件的前提下，应使s尽量的小。

图1 查询决策树结点扩展示意图

在给定属性aj的值域Ω上，定义关系R：对于任意的x, y，xRy当切仅当对所有的1≤i≤n有P[i,j](x)=P[i,j](y)。容易证明R是Ω上的一个等价关系，而σ1，σ 2，……，σs则是由这个等价关系划分出的一族等价类。

接下来，为当前结点创建s个子结点，每个子结点分别对应于一个值域子集。每个子结点都和属性集合Aset{aj}关联，其中aj是当前结点的划分属性。每个子结点初始时都和一个空的查询集合关联，然后对于Qset中的每个查询Qi和每个值域子集σk，如果P[i, j]完全包含了σk，则将Qi插入到第k个子结点关联的查询集合中。后面用Qset’[k]表示当前结点第k个子结点关联的查询集合。注意，一个查询可能被插入到多个子结点所关联的查询集合中。然后，这新建立的s个子结点及其关联的属性集合和查询集合被压入栈顶。每个子结点关联的属性集合为Aset{aj}，也就是说，每个子结点所关联的属性集合大小至少比其父结点关联的属性集合少1，因此，构造的查询决策树的最大深度为M，这里M是数据流属性的个数。

最后，为当前结点关联的查询集合Qset在划分属性aj的谓词上建立匹配器matcher，matcher是划分属性上的谓词索引。利用matcher，对于给定的划分属性值，能快速计算它落入了哪个值域子集。各种单属性上的谓词索引都可以用来建立matcher。

给一个查询决策树结点扩展的简单例子。假设当前结点关联的查询集合为：Q1:(50

2.2 查询决策树的匹配算法

利用查询决策树，搜索给定的数据流元组T满足了哪些查询的匹配算法，是一个从树的根结点往下遍历直到某个叶结点的过程。初始化时将匹配结果查询ID集合Rset置为空，结点指针P指向查询决策树的根结点，那么递归的匹配算法可以描述如下：

match (P, Rset, T) //P为指向当前访问结点的指针，Rset为存放匹配结果查询ID的集合, T为待匹配的数据流元组

匹配算法中，访问每个非叶结点时，用数据元组的划分属性值搜索当前结点的谓词索引，如果元组的划分属性值落入了第k个值域子集，那么将搜索以第k个子结点为根的子树，而直接跳过了其它的子结点及其子树。因此，查询内各属性谓词间的合取关系得到了充分利用。

匹配算法最多需要搜索M个结点的谓词索引，这里M是查询决策树的最大深度，即数据流属性的个数。如果每个结点中的谓词索引的搜索时间不大于O(f(N))，其中N是查询的个数，f(N)为单属性谓词索引的搜索时间复杂度上界，那么上述匹配算法的最坏情况时间复杂度为O(Mf(N))。一般情况下，常用的单属性上的谓词索引能满足f(N) = O(log(N))。多查询行顺序处理算法、列顺序处理算法和行列交错处理算法最坏情况下的时间复杂度都为O(MN)，而查询决策树O(Mlog(N))的最坏情况时间复杂度显然更适合实时数据流应用。

3.结语

查询决策树不仅使用了单个属性上的谓词索引，各种单属性上的谓词很容易集成到查询决策树结构中，而且还充分利用了查询内各谓词间的合取关系，相对于以前的各种多查询处理算法，能更有效减少冗余计算。

最后在一个模拟的网络入侵检测环境下测试了查询决策树的匹配时间效率和存储使用量，并将其和改进的行顺序处理算法及列顺序处理算法进行对比，验证了查询决策树在匹配时间效率上的巨大优势。

[1]徐恪,徐明伟,吴建平,吴剑.路由查找算法研究综述.软件学报，Vol.13(1),pp42～50

[2]陈有祺.形式语言与自动机.南开大学出版社，1999，pp.45～78

[3]王晓东.计算机算法设计与分析.电子工业出版社，pp210～216, 2001

10.3969/j.issn.1001-8972.2012.03.033