基于共享技术的谓词窗口数据流查询优化研究

摘要

近年来，随着网络、电信和传感器技术的发展，数据库技术得到了新的应用。在其中一种应用中，数据不再来自存储于永久介质的数据库，而是以连续、快速、随时间变化、无限的数据流的形式到达。在许多领域中存在这类应用，如网络监控，网络流量管理，入侵检测，传感器的数据处理，生产线管理，股市信息分析等等。 数据流具有连续性和无限性的特点，数据流管理系统在大多数的情况下无法处理全部的数据。为了适应数据流的诸多特点和其实际应用的需要，在数据流管理系统中广泛采用了窗口技术，对数据流中的数据进行分片处理。目前在数据流上应用最广泛的是滑动窗口查询模型。尽管滑动窗口模型能满足数据流查询中通常关心最近到达的数据的特点，但是它不能反映出整个数据流的变化，因此，普渡大学提出了一种新的窗口查询模型——谓词窗口查询模型，并引入了负元组的概念，用以表示过期元组或不符合窗口谓词的元组。 谓词窗口查询模型是一种新的窗口查询模型，目前对它的研究还比较少。本文主要研究了基于共享技术的谓词窗口数据流查询优化。针对两种不同的查询——预定义查询和即席查询，分别提出了不同的优化方法。 对于预定义查询，由于查询是在相关数据到来之前已经在数据流管理系统定义的，可以预先制定查询计划进行优化。具体来讲，就是采用多重查询处理优化的方法，对一组查询语句，求出它们的公共子表达式，在查询过程中，公共子表达式仅被执行一次，得到一个中间结果，所有包含该公共子表达式的查询都使用这一中间结果。这样就使得查询代价大为降低，提高了查询处理的效率。 对于即席查询，由于查询是当需要获得相关信息时而提交的，不能预先制定查询计划进行优化，需要动态地决定查询执行的过程。本文中采用了一种基于负元组的增量式结果估算方法。具体来讲，由于在谓词窗口查询模型中引入了负元组，使得各个操作符需要处理的元组大大增加。考虑到连接操作的耗费比较大，通过设置“时间信息”元组，避免处理与相应的正元组相同的负元组的连接操作。同时，在以前的计算结果的基础上估算新的结果，避免全部重新计算，达到查询优化的目的。通过文中的例子可以看出，这种方法使需要处理的负元组的数量大大减少，提高了查询处理的效率。

目录

文摘

英文文摘

声明

第一章引言

1.1研究背景

1.2研究内容

1.3论文结构

第二章数据流及其研究现状

2.1数据流管理系统简介

2.1.1数据流的概念

2.1.2数据流管理系统的体系结构

2.2数据流的应用领域

2.2.1传感器网络

2.2.2网络流量分析

2.2.3事务日志分析

2.2.4股票行情自动收录

2.3数据流领域的研究现状

2.4本章小结

第三章数据流处理机制

3.1数据流查询处理机制

3.2数据流查询处理的特点

3.3数据流查询的特殊问题

3.4查询计划

3.5查询中的适应性

3.6本章小结

第四章窗口技术概述

4.1窗口技术

4.1.1窗口定义

4.1.2目前常用的窗口分类

4.2滑动窗口的适应性

4.3 SteMs技术

4.4谓词窗口查询模型

4.4.1谓词窗口查询模型的基本定义

4.4.2连续谓词窗口查询语义

4.4.3谓词窗口查询的形式化表示

4.4.4谓词窗口查询操作符

4.5本章小结

第五章基于共享技术的谓词窗口数据流查询优化

5.1多重查询优化技术——针对预定义查询的优化方法

5.1.1多重查询优化技术的提出

5.1.2启发式公共子表达式求取方法

5.1.3实例描述

5.1.4预定义查询的优化方法的图示

5.2基于负元组的增量式结果估算方法——针对即席查询的优化方法

5.2.1“时间信息”(Time-Message)元组的概念

5.2.2 Join操作符中“时间信息”(Time-Message)元组的使用

5.2.3实例描述

5.2.4小结

第六章总结和进一步研究

致谢

参考文献