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