Incremental maintenance of recursive views using relational calculus/SQL

Views are a central component of both traditional database systems and new applications such as data warehouses. Very often the desired views (e.g. th e transitive closure) cannot be defined in the standard language of the und erlying database system. Fortunately, it is often possible to incrementally maintain these views using the standard language. For example, transitive closure of acyclic graphs, and of undirected graphs, can be maintained in r elational calculus after both single edge insertions and deletions. Many su ch results have been published in the theoretical database community. The p urpose of this survey is to make these useful results known to the wider da tabase research and development community. There are many interesting issues involved in the maintenance of recursive views. A maintenance algorithm may be applicable to just one view, or to a class of views specified by a view definition language such as Datalog. The maintenance algorithm can be specified in a maintenance language of differ ent expressiveness, such as the conjunctive queries, the relational calculu s or SQL. Ideally, this maintenance language should be less expensive than the view definition language. The maintenance algorithm may allow updates o f different kinds, such as just single tuple insertions, just single tuple deletions, special set-based insertions and/or deletions, or combinations t hereof. The view maintenance algorithms may also need to maintain auxiliary relations to help maintain the views of interest. It is of interest to kno w the minimal arity necessary for these auxiliary relations and whether the auxiliary relations are deterministic. While many results are known about these issues for several settings, many further challenging research proble ms still remain to be solved.