14 Incremental computing on the derived variables

Incremental computing is important for performance. When the base variables are updated, there is a need to efficiently update the derived varables, rather than simply recalculate them from scratch.

In database systems where views are materialised, this is called view maintenance.

A view can be maintained immediately, as a part of the transaction that updates the base variables. Immediate maintenance imposes a signicant overhead on update transactions that cannot be tolerated in many applications.

In contrast, deferred maintenance allows a view to be stale, it is only eventually consistent.

Incremental computation can be achieved by building a dependency graph of all the data elements that may need to be recalculated, and their dependencies.

Literature

• A Comprehensive Study of View Maintenance Approaches in Data Warehousing Evolution by Hemant Jain and Anjana Gosain 2012.
• "Incremental Maintenance of Views with Duplicates" Griffin and Libkin SIGMOD, 1995.
• Algorithms for Deferred View Maintenance by Colby, Griffin and Libkin.
• Incremental View Maintenance CPS 296.1. Topics in Database Systems
• Incremental View Maintenance with Triple Lock Factorization Benefits 2018 by Milos Nikolic and Dan Olteanu.
• Incremental Computation with Names by Hammer, Dunfield, Headley, Labich, Foster, Hicks and Horn (2015).