Incremental View Maintenance for Collection Programming

In the context of incremental view maintenance (IVM), delta query derivation is an essential technique for speeding up the processing of large, dynamic datasets. The goal is to generate delta queries that, given a small change in the input, can update the materialized view more efficiently than via recomputation. In this work we propose the first solution for the efficient incrementalization of positive nested relational calculus (NRC+) on bags (with integer multiplicities). More precisely, we model the cost of NRC+ operators and classify queries as efficiently incrementalizable if their delta has a strictly lower cost than full re-evaluation. Then, we identify NRC+, a large fragment of NRC+ that is efficiently incrementalizable and we provide a semantics-preserving translation that takes any NRC+ query to a collection of IncNRC+ queries. Furthermore, we prove that incremental maintenance for NRC+ is within the complexity class NC0 and we showcase how recursive IVM, a technique that has provided significant speedups over traditional IVM in the case of flat queries, can also be applied to IncNRC+.

Published in:
PODS '16 Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 75-90
Presented at:
35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, San Francisco, California, USA, June 26th-July 1st, 2016
New York, NY, USA, ACM

 Record created 2016-07-15, last modified 2018-09-13

Publisher's version:
Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)