Incremental query evaluation in a ring of databases
Incremental query evaluation in a ring of databases
复制标题
数据库环中的增量查询评估
DOI：
10.1145/1807085.1807100
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Christoph E. Koch
中科院分区：
文献类型：
--
作者：
Christoph E. Koch
本文从代数的角度解决了增量视图维护问题。我们构建数据库环的代数结构，并将其用作允许表达强大聚合查询的查询微积分设计的基础。查询演算继承了环的关键属性，例如具有正常形式的多项式形式，并在计算倒置和三角洲查询下关闭。无嵌套的多项式查询的k-th三角洲纯粹是更新的函数，而不是数据库的函数。这引起了一种消除昂贵查询操作员的方法，例如从执行增量视图维护的程序加入的方法。主要结果是，对于非巢查询，可以使用恒定的工作量来逐步维护每个单独的汇总值。这是非进取评估的不可能的。
This paper approaches the incremental view maintenance problem from an algebraic perspective. We construct the algebraic structure of a ring of databases and use it as the foundation of the design of a query calculus that allows to express powerful aggregate queries. The query calculus inherits key properties of the ring, such as having a normal form of polynomials and being closed under computing inverses and delta queries. The k-th delta of a polynomial query of degree k without nesting is purely a function of the update, not of the database. This gives rise to a method of eliminating expensive query operators such as joins from programs that perform incremental view maintenance. The main result is that, for non-nested queries, each individual aggregate value can be incrementally maintained using a constant amount of work. This is not possible for nonincremental evaluation.