持续SPJ查询的有界内存可计算性研究

摘要

30多年来,数据库技术发展迅速且得到了广泛应用.一方面,数据建模形式多样,从层次数据库、网状数据库、关系数据库、对象数据库,直到关系对象数据库等等;另一方面,数据规模也越来越大.传统数据库技术的一个共同点是:数据存储在介质中,可以多次利用;但是在20世纪末,一种新型应用对它提出了有力的挑战.这种名为数据流(datastream)的应用模型广泛出现在众多领域,数据流不同于存储在磁盘上的关系数据,而是以流的形式快速、无限、连续、实时地出现.典型的数据流包括无线传感器网络应用环境中由传感器传回的各种监测数据、股票交易所的股票价格信息数据、网络监测系统与道路交通监测系统的监测数据、电信部门的通话记录数据,以及网站的日志信息等.能够处理数据流的系统环境统称为数据流系统.数据流可以被看作是一个允许元素重复出现的无限集合,集合中每个元素具有形式,其中s是数据流的一个数据项(可能是一个元组),t为标识s的时间戳,t的取值可由s进入数据流系统的时间或者数据源产生s的时间确定.由于内存资源有限,数据流无限,有界的内存空间无法存储数据流中的全部数据,因此,数据流系统通过在内存中开辟滑动窗口(slidingwindow)来保存最近一段时间内到达的数据流数据,实时地支持查询请求.与传统数据库系统的查询不同,数据流系统的多数查询在系统中长期处于执行状态.随着数据流源源不断地进入数据流系统,这些查询不断地接收新数据,进行查询处理,产生新的查询结果.本文通过其导出的LTO查询有界内存是否可计算的方法来判定一个SPJ查询有界内存是否可计算.给出了LTO查询有界内存是否可计算的判定定理.最后给出了相关的判定算法.下一步的工作是在此基础上找出更一般的查询有界内存是否可计算与一个有界内存可计算的SPJ查询需要的内存模型.