Incremental view materialization in deductive databases

Abstract

This paper presents a unifying approach to processing of (recursive) queries and updates in a deductive database. To  improve query performance, a combined top-down and bottom-up evaluation method is used to compile rules into iterative programs that contain relational algebra operators. This method is based  on the lemma resolution that retains previous results to guarantee termination.

Due to locality in database processing (i.e. repetitive user query patterns), it is desirable to materialize frequently used queries against views of the database. Unfortunately, if updates are allowed, maintaining materialized views tables becomes a major problem. We propose to materialize views incrementally, as queries are being answered. Hence views in our approach are only partially materialized. For such views, we design algorithms to perform updates only when the underlying view tables are actually affected.

We compare our approach to two well-known methods for dealing with views: total materialization and query-modification. The first method materializes the entire view when it is defined while the second recomputes the view on the fly without maintaining any physical view tables. We demonstrate that our approach is a compromise between these two methods by determining the conditions under which it performs better.