Incremental Evaluation of Relational Expressions

Abstract

This thesis is about the field of relational databases. It investigates techniques that allow to incrementally maintain the results of relational queries when the database content changes. The main use-case is keeping up-to-date materialized views, which are queries whose results are stored in the database system. The considered query language is the relational algebra based on set semantics, including the generalized projection operator to express aggregation. Modeling the changes of the database content happens by, for each relation, specifying a set of tuples to delete and a set of tuples to insert. The update that should be applied to the value of a view to keep it up-to-date with the new database content, is modeled in different ways, depending on which technique is under investigation. The models used are count tables, deltas and change tables. Also investigated is the notion of self-maintainability of (sets of) views, which expresses whether (sets of) views can be maintained without access to the relations they are based on.