《一种分布式数据流查询重用算法研究.doc》由会员分享，可在线阅读，更多相关《一种分布式数据流查询重用算法研究.doc（6页珍藏版）》请在三一文库上搜索。
1、一种分布式数据流查询重用算法研究0引言 近年来，在很多应用领域中均出现了一种称为数据流的新型数据模式。例如传感器网络中的监测数据､互联网中流动的IP数据包､Web服务器上的用户登录记录､电信公司的通话记录等。与传统的数据模式不同，数据流数据的特点是实时无限的，无法全部保存下来进行处理。对这种数据流进行各种处理(主要是查询操作)后得到的结果也同样可能是流的形式。 随着数据流应用的逐渐普遍，数据流管理系统(DSMS)成为数据库领域的一个研究热点。数据流管理系统主要可以分为两类:一类是集中式数据流管理系统，如STREAM1､Aurora2和Te
2、legraphCQ3等;另一类是分布式数据流管理系统，如Medusa4､Borealis5等。目前在大量数据流应用系统中，数据是来自于地理上分布的数据源或不同的自治单元。其本身非常适合于分布式处理，如传感器网络､分布式网络监控等。相对于集中式的数据流查询处理，对数据流进行分布式查询处理能更好地满足数据流的应用需要6。 分布式数据流管理系统根据用户输入的连续查询语句生成查询树。数据流从树状查询树的叶子节点处进入，以流水线的方式执行查询树中的查询操作。查询的最终结果从查询树的根部输出给用户。大量的连续查询在分布式数据流管理中同时执行，并且许多连续查询之间至少部分是相互重
3、叠的。对重叠的连续查询实现重用不仅能提高查询性能而且能节省系统资源7。 文献8提出了连续查询分组优化算法实现了连续查询的重用，但是它不适用于分布式数据流查询处理。针对分布式数据流查询处理，文献7提出了四种查询重用方案来实现查询重用，但是其查询重用粒度过粗，不能满足分布式数据流管理系统的需要。针对以上问题，本文提出了一种基于查询树匹配的分布式数据流查询重用算法。 1问题描述 1.1分布式数据流查询处理模型 在大量数据流应用中，数据流是来自分布在不同地理位置上的数据源，其本身非常适合于分布式处理。对数据流查询进行分布式处理可以更好地满足数据流应用的需求。如图1所示，一个分布式数据流查询处理模型主要
4、由三部分组成，即数据源､分布式数据流管理系统和应用。 数据源向分布式数据流管理系统提供连续的数据流。分布式数据流管理系统是一个由许多数据流处理节点组成的庞大的数据流查询处理网络，负责对来自不同地理位置上的数据流进行分布式的查询处理，并把最终处理结果交给应用。应用向分布式数据流管理系统提交查询，并从分布式数据流管理系统获得查询结果。 1.2问题定义 在分布式数据流管理系统中一般用一棵查询树来表达一个用户提交的连续查询。其定义如下: 定义1查询树是一棵树T=V，E。其中:V是节点集，树中的节点至多有两个孩子节点，非叶子节点是数据流查询操作，叶子节点是数据源(即查询涉及的数据流);E是
5、边集，eE，e是有向的且从孩子节点指向双亲节点，e记为(i， j)，i为孩子节点， j为双亲节点。 分布式数据流管理系统同时处理多个查询树，不同的查询树有重叠的查询操作。如图2所示，查询树A与B存在重叠的查询操作S1与S2。查询树A中查询操作S1和S2的查询结果可以直接被查询树B中的查询操作J2所用。 当系统生成一个新的查询树，在系统已有的查询树中有许多查询树均与该查询树有重叠的查询操作。如何最大限度地重用重叠的查询操作成为查询重用算法要解决的重点问题。新生成的查询树记为Tnew，分布式数据流管理系统中已有的查询树记为ST(n)=T1，T2，Ti，Tn。其中n为查询树的个数。 2分布式数据流查
6、询重用算法 定义2重用收益。定义一棵查询树T对查询树Tnew的重用收益为YT=Cr/CTnet。其中:YT表示重用收益;CT表示查询树T总的执行代价9;Cr表示查询树T与查询树Tnew中重叠的查询操作的执行代价之和。 重用收益表征了查询树T与查询树Tnew重叠的查询操作的执行代价占查询树Tnew总的执行代价的比重。 针对查询重用问题，本文提出了一种基于查询树匹配的分布式数据流查询重用算法。其由两个子算法组成，即查询树匹配算法和查询树选择算法。 2.1查询树匹配算法 查询树匹配算法把新生成的查询树Tnew和系统中已有的查询树ST(n)按后序遍历的顺序生成带索引的线性 2.2查询树选择算法 算法2
7、查询树选择算法 输入:系统中已有查询树ST(n)，新生成查询树Tnew和重用收益Yn 输出:查询树Tnew最终的查询收益Ynew a)从ST(n)中选出对Tnew重用收益最大的查询树Tj; b)检查Ti与Tnew重叠的查询操作是否标记为reused; c)重用未标记为reused的重叠查询操作，并把重用了的查询操作标记为reused; d)update(Ynew); e)Yi=0; f)重复a)e); 其中:a)选出了对Tnew重用收益最大的查询树Ti，其时间复杂性为O(n);b)e)实现了Ti与Tnew重叠的查询操作的重用，其时间复杂性为O(M);f)最多执行n次，其时间复杂性为O(n+M)
8、。于是，查询树选择算法的总时间复杂性为O(n(n+M)。 3实验结果 笔者在P4 2.4 GHz CPU､1 GB主存､100 GB硬盘的微型计算机环境下进行了模拟实验。随机地产生了100和200个连续查询，用于考察执行代价总和在实施查询重用之前与之后的变化情况。 实验中查询树的特征信息均随机生成，并根据文献9的评估模型计算出每棵查询树中查询操作的执行代价。当查询数量大于20后，开始实施查询重用算法。 实验结果如图4､5所示。从这两个图中可以看出，查询重用前后执行代价总量变化明显，表明查询重用在很大程度上减少了连续查询的执行代价总量，并且可以看出，本文算法在减少了连续查询的执行代价总量方面要优于文献7的算法。 4结束语 数据流管理系统的研究已经成为当前数据库领域的一个热点问题。本文提出了一种分布式数据流查询重用算法。实验结果表明，本文提出的算法能够显著地节省系统资源，提高了分布式数据流查询处理的性能。