nucleation

LIT-1114: Maintaining Views Incrementally

2 min read

Properties4
StatusActive — read in full 2026-10-15 from the ACM's typeset PDF of the SIGMOD '93 extended abstract (pp. 157–166), as posted on Columbia University's Ph.D. candidacy exam reading list in database systems (www.cs.columbia.edu/~gravano/Qual/Papers/13%20-%20Maintaining%20Views%20Incrementally.pdf); a scan with an OCR layer, so definitions and theorems were read from page images. The full version with the proofs (AT&T Bell Labs TR 921214-19-TM, 1992) was not found. Worth reading as the source of the two standard incremental view maintenance algorithms: counting, which stores one derivation count per derived tuple and is stated correct for nonrecursive views with stratified negation and aggregation under set or duplicate semantics (THEORY-362), and DRed, which for recursive views under set semantics overdeletes, rederives what still has a derivation and then inserts, and is stated to give exactly what the new base derives (THEORY-387). The theorems are stated without proof here, and cost claims are argued, not measured. For QUESTION-105 it shows that, for revisions given as changes to base facts under a fixed program, the retained state can be a count per conclusion when support is acyclic and nothing beyond the materialization when it is not, with support rechecked at revision time; neither is provenance or a record of defeated alternatives. For CLAIM-303 it shows the dependency-tracking cost can sit at derivation time (counting) or at revision time (DRed), without measuring either, and that a view kept this way never goes stale.
Tagsdatabases, logic
Cited as “paper” byNOTE-915 — Gupta, Mumick & Subrahmanian — Maintaining views incrementally
Cited as “source” byTHEORY-362 — For nonrecursive Datalog or SQL views with safe stratified negation and stratified aggregation, under set or duplicate semantics, storing with each derived tuple only the number of its derivations suffices to maintain the view under insertions and deletions of base tuples: signed counts propagated through delta rules stratum by stratum give each tuple's change as its new count minus its old, a tuple leaves when its count reaches zero, and a MIN or MAX group whose extreme is deleted is recomputed from the stored lower stratum, THEORY-387 — For positive recursive Datalog views under set semantics, deleting every derived tuple that has any derivation through a deleted base fact, then restoring each deleted tuple that still has a derivation from what remains, then adding what insertions derive, leaves exactly the tuples derivable from the new base (E − Δ⁻) ∪ Δ⁺, with no derivation counts stored; the extension to stratified negation and aggregation is asserted, not shown, and the size of the overestimate is not measured

Graph View

Gupta, A., Mumick, I. S. and Subrahmanian, V. S. (1993). Maintaining views incrementally. In Proc. ACM SIGMOD 1993, pp. 157–166. DOI 10.1145/170035.170066

Key takeaways

Read in full (NOTE-915). Two algorithms compute the changes to a stored derived relation (a view) from changes to the base relations, without recomputing it. Counting stores, for each derived tuple, the number of its derivations and propagates signed counts through delta rules stratum by stratum; it is stated correct for nonrecursive Datalog or SQL views with stratified negation and aggregation, under set or duplicate semantics, and is argued to cost little beyond evaluating the view. DRed (delete and rederive), for recursive views under set semantics only, deletes an overestimate of what a deletion invalidates, puts back those tuples that still have a derivation from what remains, then adds what insertions derive; it is stated to yield exactly the tuples derivable from the new base. The paper is an extended abstract: the theorems are stated without proof (proofs are referred to a 1992 AT&T report), cost claims are argued, not measured, and there are no experiments.

Why this is here

QUESTION-105 and CLAIM-303’s dependency tracking: counting keeps one derivation count per derived result for nonrecursive views, and delete-and-rederive handles recursive views under set semantics, keeping what has another derivation. The theorems are stated without proof and the costs are argued, not measured.

Backlinks