Abstract
In this talk, I discuss the incremental view maintenance problem from an algebraic perspective. The algebraic structure of a ring of databases is constructed and extended to form a powerful aggregate query calculus. The calculus has a normal form of polynomials and is closed under a universal difference operator. This difference operator allows to express the so-called delta queries of the incremental view maintenance literature, but also deltas to the deltas. The k-th delta of a query of polynomial degree k is purely a function of the update, not of the database. This gives rise to a multi-layered incremental view maintenance scheme in which a view is maintained using a hierarchy of auxiliary materialized views of k-th deltas. What is gained by this hierarchy is that the work required to keep all views fresh given an update is extremely simple. The method allows to eliminate expensive query operators such as joins and aggregate sums entirely from programs that perform incremental view maintenance. For non-nested queries, each individual aggregate value can be incrementally maintained using a constant amount of work. As a byproduct, we obtain a query language that is significant in its own right. It is an algebraic language in which queries, like in relational calculus, are built up from base objects (generalized relations) using an extremely small set of connectives – addition, multiplication, and aggregation. It is based on a family of algebraic structures called avalanche (semi)rings which algebraizes range-restriction. These structures guarantee finite query results in the presence of inequalities, without making use of an explicit selection operation. The entire language behaves like a polynomial ring of relations and thus makes algebraic manipulation very easy. As a simple algebraic language of interesting expressive power – relational algebra with SQL-style aggregation and unlimited nesting – it is a natural internal representation language for query processors and compilers.
Incremental Query Evaluation in a Ring of Databases.
Christoph Koch
Technical Report, 2013.
DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views.
Yanif Ahmad, Oliver Kennedy, Christoph Koch, and Milos Nikolic
Proc. VLDB 2012, Istanbul, Turkey.
Incremental Query Evaluation in a Ring of Databases.
Christoph Koch
Proc. PODS 2010, Indianapolis, Indiana.