Utilizing IDs to Accelerate Incremental View Maintenance∗

Prior Incremental View Maintenance (IVM) algorithms specify the view tuples that need to be modified by computing diff sets, which we call tuple-based diffs since a diff set contains one diff tuple for each to-be-modified view tuple. idIVM assumes the base tables have keys and performs IVM by computing ID-based diff sets that compactly identify the to-be-modified tuples through their IDs. This work makes the following contributions: (a) An ID-based IVM system for a large subset of SQL that includes the algebraic operators selection, join, grouping and aggregation, generalized projection involving functions, antisemijoin (and therefore nega-tion/difference) and union. The system is based on a modular ap-proach, allowing one to extend the supported language simply by adding one algebraic operator at-a-time, along with equations de-scribing how ID-based changes are propagated through the opera-tor. (b) An efficient algorithm that creates an IVM plan for a given view in four passes that are polynomial in the size of the view ex-pression. (c) A formal analysis comparing the ID-based IVM al-gorithm to prior IVM approaches and analytically showing when one outperforms the other. (d) An experimental comparison of the ID-based IVM algorithm to prior IVM algorithms showing the su-periority of the former in common use cases. 1