1993/06/01 by Ashish Gupta, Inderpal Singh Mumick, V. S. Subrahmanian
Computer Science · Decision Sciences · #Advanced Database Systems and Queries #Data Quality and Management #Semantic Web and Ontologies
paper · pdf · doi:10.1145/170036.170066
openalex publication_date 1993/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/25
We present incremental evaluation algorithms to compute changes to materialized views in relational and deductive database systems, in response to changes (insertions, deletions, and updates) to the relations. The view definitions can be in SQL or Datalog, and may use UNION, negation, aggregation ( e.g. SUM, MIN), linear recursion, and general recursion. We first present a counting algorithm that tracks the number of alternative derivations (counts) for each derived tuple in a view. The algorithm works with both set and duplicate semantics. We present the algorithm for nonrecursive views (with negation and aggregation), and show that the count for a tuple can be computed at little or no cost above the cost of deriving the tuple. The algorithm is optimal in that it computes exactly those view tuples that are inserted or deleted. Note that we store only the number of derivations, not the derivations themselves. We then present the Delete and Rederive algorithm, DRed, for incremental maintenance of recursive views (negation and aggregation are permitted). The algorithm works by first deleting a superset of the tuples that need to be deleted, and then rederiving some of them. The algorithm can also be used when the view definition is itself altered.