《运用k—约束减少数据流持续查询所需存储器容量的研究》由会员分享，可在线阅读，更多相关《运用k—约束减少数据流持续查询所需存储器容量的研究（20页珍藏版）》请在金锄头文库上搜索。
1、运用K约束减少数据流持续查询所需存储容量的研究Shivnath Babu, Utkarsh Srivastava, and Jennifer WidomStanford University_shivnath,usriv,widom_cs.stanford.edu目 录摘要11前言111数据流约束总述1111顺序到达的约束2112成群到达约束2113连接约束212持续查询和执行总述313K约束的持续监控314开发K约束的结构415本文要点42相关工作53基础531数据流和持续查询532基本查询执行算法633简化大纲7331消除元组7332消除列834滑动窗口835数据流特性和实验84参考完整性
2、约束941开发RIDS(k)的改进算法942监控RIDS(k)1043RIDS(K)的实验分析115成群到达约束1251开发CA(K)的改进算法1252监控CA(K)1353CA(K)实验分析136按序到达约束1461开发OAP(K)的改进算法1562监控OA(K)1563OAP(K)实验分析157计算成本178同时开发不同的K约束179总结19摘要在数据流上的持续查询可能要求保存大量的运行时状态，我们可以通过在输入流中，使用约束来减少这些状态。通常，数据流不能完全满足约束条件，但可以和约束条件很接近。为了利用这样一种情况，我们提出了K约束的概念。其中，K是一个“忠诚度参数”，表示给定的数据流
3、在多大程度上符合约束条件。我们将给出利用一个或多个K约束来减少所需存储容量的查询算法。由于K的值可能无法预测。也可能随时发生变化，所以我们也将给出算法，在不同约束类型中监控输入流来估计K值。我们已经实现了查询处理结构，它把基于约束的查询算法与追踪相关K值的监控组件有效地结合起来。试验结果表明，使用K约束后，状态被大大减少；而我们的查询和监控算法只需要一定的计算量。1前言在现实生活中，数据流持续查询具有广泛的应用前景。在持续查询中，我们面临的主要挑战是需要大量存储必要的运行时状态。在本文中，我们提出一个查询处理结构，它在数据流上运用约束来减少持续查询所需的存储容量。根据持续数据流环境，我们定义了
4、三种约束类型，分别针对顺序、成群、基于流的参考完整性。因为数据流不能完全和约束条件符合，所以引入了K约束的概念。当K0时，它表示一个数据流或数据流集合在多大程度上符合约束条件。当K0时，表示约束不起作用。在数据流上下文中，K约束的概念是相当重要的：由于数据产生、网络负荷的不同，以及其他一些原因，我们不可能要求数据流时时严格满足约束。但是，数据流又常常和约束条件很接近，K约束使我们能够很好的利用这些情况。当然，即使数据流精确满足K约束，K值也不能事先得知，而且还可能随时变化。在本文中，我们利用K约束建立了数据流系统。我们提出监控输入流的算法，它可以发现有用的K约束，并跟踪实际K值的变化。我们将给
5、出利用一个或多个K约束来减少所需存储容量的查询算法。由于K的值可能无法预测。也可能随时发生变化，所以我们也将给出一个算法，在不同约束类型中监控输入流来估计K值。我们已经实现了一个查询处理结构，它把基于约束的查询算法与追踪相关K值的监控组件有效地结合起来。试验结果表明，使用K约束后，状态被大大减少；而我们的查询和监控算法只需要一定的计算量。11数据流约束总述我们首先描述约束类型和忠诚度参数，以及怎样在查询操作中使用它们。实例来自于监控网络通信量的应用。111顺序到达的约束知道数据流是跟据某个属性（如时戳）按序到达是很有用的。比如说，我们将两个数据流连接起来，而且两者的属性都是有序的，那么就可以执
6、行合并类型的连接，并只需保持较少的运行时状态。在网络监控领域，网络测量流是同过UDP协议传输的，而不是通过更可靠、也更昂贵的TCP协议传输。尽管UDP可能颠倒数据包的次序，但是我们可以通过限制数据流中重排的数目加以改善。我们根据数据流中与忠诚度参数K相关的S.A属性，来定义顺序到达约束。对数据流S中的每个元组s来说，s后面的至少K+1个元组的A值大于或等于s 的A值。那么任何两个乱序到达的元组，一定在彼此的K个元组中。注意到，当K0时，得到一个严格非减的属性。同时，虽然在本文中我们选用了基于元组的约束，但是基于时间的约束同样可行。112成群到达约束即使数据流元组没有次序，他们也可以根据某个属性
7、形成集合。成群也帮助我们减少连接时的状态，因为当一个集合完成时，我们可以只保留完成的数据流中的元组，而将其他元组丢弃。在网络监控领域，如果我们产生数据流来跟踪通过多重路由的数据包，那么某个包ID的所有元组将被紧密聚集在一起。我们根据数据流中与忠诚度参数K相关的S.A属性，来定义成群到达约束。如果数据流S中的两个元组有相同的A属性值v，那么在它们之间至多有K个非v值的元组。113连接约束对于无序且不成群的数据流，如果知道两个数据流是怎样被连接的，我们也可以减少状态。假设将数据包跟踪流和流动记录流连接起来。因为流动是由很多包形成的，而连接是从多个到单个的过程，那么当一个数据包跟踪元组到来时，如果连
8、接流动记录已经到达，那么可以发送连接结果元组，并马上丢弃包跟踪元组。添加连接约束可以限制连接的“多个”方面元组（在本例中的包跟踪元组）到达与“单个”方面元组（流记录）到达之间的延迟。如果流记录已被采样或筛选，这种限制允许将“未选中”的流记录丢弃，从而避免了保存大量与“未选中”流记录连接的包跟踪元组，而这些元组又不可能成为连接结果的一部分。我们根据数据流S1到S2的多个到单个的连接，来定义参考完整性约束。当S1中的元组s1到达，它对应的S2中的s2元组将在S2中K个元组到达后到达。对于K0这个特例，这种约束就是说s2总是比s1先到。12持续查询和执行总述在本文中，持续查询就是数据流上使用可选滑动
9、窗口的选择项目连接（SPJ）查询。假设查询中的所有连接都是常见的多个到单个（单对单也是其中的一个特例）的等连接。虽然我们总的方法和算法与这个假设基本无关，但是，在多个到多个的连接中，我们算法的优越性减小了。我们的SPJ查询是比较直接的，如下所示：Select *From S1 Rows 50,000, S2 Rows 50,000Where S1.A = S2.A and S2.B 10“Rows 50,000”表示在任何时候，S1中滑动窗口都保持了了最后50,000个元组；对S2也一样。如果窗口没有指定大小，那么我们使用无限窗口，即保持流中所有元组。这个查询例子产生所有满足条件的S1和S2的
10、连接元组。实现查询的直接方法就是保持S1和S2的大纲（synopse）。当S1的新元组到达时，它和S2的大纲相连接，并加入到S1的大纲中，如果窗口已满，则替换掉一个存在的元组；S2的操作也一样。注意，谓词筛选不能在连接前独立使用，因为大纲的大小必须建立在S2流中的所有元组之上。上述的简单方法没有涉及约束，但它可以在大纲中逻辑地保持元组到达的次序，所有即使我们没有保存元组本身，还能正确保持窗口。这个步骤帮助我们删除S2中不满足谓词筛选的元组。比如说，如果谓词筛选率是50，那么S2大纲平均保持25,000个元组。我们将这种算法称为滑动窗口连接（SWJ）。假设连接是从S1到S2的多个到单个。一旦S1
11、大纲中的元组和S2中的元组连接起来，那么S1中的元组就可以被删除，这样做往往可以大量减少S1大纲的规模。对于S2中不满足谓词筛选的元组s2，我们一般将它保存起来，因为这有助于删除S1中的元组。如果在连接时使用严格的参考完整性，那么不再需要S1的大纲，因为当S1的元组到达时，S2中与它将匹配的元组不是马上出现在S2的大纲中，就是已经不在S2的窗口中了。如果有结合忠诚度参数K的参考完整性，那么S1中的元组s1必须被存储，因为很可能在s1到达之后，K才到达S2。进一步，如果S2满足K序到达，那么S1中的元组s1必须被存储，因为K后的S2.A有可能比S1.A要大。这些例子说明了怎样使用K约束来减小大纲
12、的规模。但是，要减少大多数情况下的存储容量使用是很复杂的，因为必须考虑各种查询和数据流约束组合。13K约束的持续监控在有些情况下，可以根据输入流的产生和传送，来静态地指定数据流约束和相关的忠诚度参数K，而且K值保持不变。但是，更多情况下，对约束的忠诚度无法预测，并随着时间改变。我们探测K约束的方法是根据当钱的持续查询，定义对减少运行时状态可能有用的约束，然后持续监控输入流获得对这些约束的忠诚度。查询执行的算法假设K约束的忠诚度在给定的K值中。特别是，在查询执行过程中，抛弃了一些状态，如果没有约束或者K值更高（表明更低的忠诚度）的话，这些状态可能不会被抛弃。如果监控算法低估了K，特别是如果K增长
13、得很快时，那么假否定（错过的元组）将出现查询结果中。在很多流应用中，为了获得更高效率的执行，查询结果中的适当错误是可接受的，特别是如果错误只持续一小段时间。图1.K监控结构如果在任何情况下，假否定都不能被容忍，那么我们的方法仍旧可以使用，将“可能不必要”的状态存储在磁盘中，而不是将它抛弃。14开发K约束的结构查询过程的结构被称为K监控，它完成了监控K约束和在查询执行过程中开发它们的功能。K监控的基础结构显示在图1中。查询登记部分记录了持续查询，从而在输入流的已知K约束之上建立起初始的查询计划。查询执行部件执行这个计划。同时，查询登记部分告知约束监控部件，关于将用于减少查询所需存储容量的约束。为
14、SPJ定义可能有用的约束是简单的，这个将在3.2节的查询执行算法中有所体现。监控部件持续监控输入流，并且在约束的K值变化时告知查询执行部件。执行部件通过调整它的K值来适应这些变化。在本文中，我们为按序、成群、参考完整性约束示例了K监控结构。我们的监控算法为各种约束类型都测量和跟踪了忠诚度的变化。查询执行算法使用通过监控探测到的K约束来减少所需存储容量。15本文要点第3部分指出我们考虑到的一些查询和基本的查询执行算法。第46部分形式化三种约束类型，并将它们结合到执行算法中，给出监控算法，包括每种约束类型的实验结果。第7部分测试了我们结构的计算能力。第8部分涵盖了同时使用不同约束。第九部分以附录的
15、形式给出了一些细节和证据。2相关工作略3基础31数据流和持续查询持续数据流就是相关元组的无限数据流。为了说明，我们将首先考虑窗口不限的持续SPJ查询。要扩展到滑动窗口是很简单的，将在3.4节具体描述。在某个时间T，在数据流S1,S2,Sn上持续查询Q的结果是持续相关的。使用S（T）来标示在T时刻到达数据流S的元组。既然我们考虑的查询都是单调的，那么假设查询结果本身也是数据流，所以不必说明存储查询结果的花费。假设所有数据流属性都包含在查询结果中。考虑3.3.2.节中的工程。本文中的选择条件是将单一流上的谓词过滤和不同流的预先同等连接联合起来。为了表述清楚，先假设查询的谓词建立在应用上的。象前面所说的那样，假设查询中的所有连接是多到单的。就是说，如果Q包括S1和S2的一个或多个预连接，那么我们保证S1的每个元组最多和S2的一个元组连接（例如，如果Q包括S1.A = S2.B
