Why it is a question
THEORY-387 now states that, for positive recursive Datalog under set semantics, DRed’s three steps (overestimate the deletions, rederive what still has a derivation from what remains, add what insertions derive) leave exactly the tuples derivable from the new base, with no derivation counts stored. The proof given for that case uses monotonicity: deletions can only remove tuples. Under stratified negation a deletion in a lower stratum can add tuples in a higher one, and under aggregation a deletion changes a value rather than removing a tuple, so the same argument does not go through. The paper says both are handled “in [GMS92]”, a technical report the record has not found. It also gives no bound or measurement of how many tuples the first step deletes and the second puts back, and calls incremental maintenance “only a heuristic”.
What would answer it
A proof, read by the record, of DRed’s correctness with stratified negation and aggregation, in the 1992 report or a later published treatment, or a re-derivation, would answer the first part yes; a stratified program and a change after which the maintained view differs from the recomputed one would answer it no. A bound on the overestimate in terms of the change and the program, or measurements across workloads against the true deletions and against recomputation, would answer the second part. Worked examples settle neither.