首页> 外文期刊>ACM transactions on database systems >Relational Languages and Data Models for Continuous Queries on Sequences and Data Streams
【24h】

Relational Languages and Data Models for Continuous Queries on Sequences and Data Streams

机译:序列和数据流上连续查询的关系语言和数据模型

获取原文
获取原文并翻译 | 示例

摘要

Most data stream management systems are based on extensions of the relational data model and query languages, but rigorous analyses of the problems and limitations of this approach, and how to overcome them, are still wanting. In this article, we elucidate the interaction between stream-oriented extensions of the relational model and continuous query language constructs, and show that the resulting expressive power problems are even more serious for data streams than for databases. In particular, we study the loss of expressive power caused by the loss of blocking query operators, and characterize nonblocking queries as monotonic functions on the database. Thus we introduce the notion of NB-completeness to assure that a query language is as suitable for continuous queries as it is for traditional database queries. We show that neither RA nor SQL are NB-complete on unordered sets of tuples, and the problem is even more serious when the data model is extended to support order—a sine-qua-non in data stream applications. The new limitations of SQL, compounded with well-known problems in applications such as sequence queries and data mining, motivate our proposal of extending the language with user-defined aggregates (UDAs). These can be natively coded in SQL, according to simple syntactic rules that set nonblocking aggregates apart from blocking ones. We first prove that SQL with UDAs is Turing complete. We then prove that SQL with monotonic UDAs and union operators can express all monotonic set functions computable by a Turing machine (NB-completeness) and finally extend this result to queries on sequences ordered by their timestamps. The proposed approach supports data stream models that are more sophisticated than append-only relations, along with data mining queries, and other complex applications.
机译:大多数数据流管理系统都基于关系数据模型和查询语言的扩展,但是仍需要对这种方法的问题和局限性以及如何克服它们进行严格的分析。在本文中,我们阐明了关系模型的面向流的扩展与连续查询语言构造之间的相互作用,并表明,对于数据流,所产生的表达能力问题甚至比对数据库更严重。特别是,我们研究由于阻塞查询运算符的丢失而导致的表达能力的下降,并将非阻塞查询表征为数据库上的单调函数。因此,我们引入了NB完整性的概念,以确保查询语言与传统数据库查询一样适用于连续查询。我们证明,在无序元组集上RA和SQL都不是NB完整的,当数据模型扩展为支持有序时,问题甚至更加严重,这在数据流应用程序中是一个正弦波。 SQL的新局限性加上诸如序列查询和数据挖掘之类的应用程序中的众所周知的问题,促使我们提出使用用户定义的聚合(UDA)扩展语言的建议。根据简单的语法规则,可以将非阻塞聚合与阻塞聚合区别开来,这些可以用SQL本机编码。我们首先证明带有UDA的SQL是图灵完整的。然后,我们证明具有单调UDA和联合运算符的SQL可以表示可由Turing机器计算的所有单调集合函数(NB完整性),最后将此结果扩展到对按其时间戳排序的序列的查询。所提出的方法支持比仅追加关系更为复杂的数据流模型,以及数据挖掘查询和其他复杂的应用程序。

著录项

  • 来源
    《ACM transactions on database systems》 |2011年第2期|p.1-32|共32页
  • 作者单位

    Bioinformatics Institute, 30 Biopolis Street, Singapore 138671;

    Microsoft Research Asia, 49 Zhichun Road, Beijing 100080, China;

    Computer Science Department, University of California, Los Angeles,CA 90095;

  • 收录信息 美国《科学引文索引》(SCI);美国《工程索引》(EI);
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    data streams; queries; expressivity;

    机译:数据流;查询;表现力;

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号