Incremental View Maintenance with Triple Lock Factorization Benefits

Milos Nikolic, Dan Olteanu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

We introduce F-IVM, a unified incremental view maintenance (IVM) approach for a variety of tasks, including gradient computation for learning linear regression models over joins, matrix chain multiplication, and factorized evaluation of conjunctive queries.

F-IVM is a higher-order IVM algorithm that reduces the maintenance of the given task to the maintenance of a hierarchy of increasingly simpler views. The views are functions mapping keys, which are tuples of input data values, to payloads, which are elements from a task-specific ring. Whereas the computation over the keys is the same for all tasks, the computation over the payloads depends on the task. F-IVM achieves efficiency by factorizing the computation of the keys, payloads, and updates.

We implemented F-IVM as an extension of DBToaster. We show in a range of scenarios that it can outperform classical first-order IVM, DBToaster's fully recursive higher-order IVM, and plain recomputation by orders of magnitude while using less memory.
Original languageEnglish
Title of host publicationProceedings of the 2018 International Conference on Management of Data
Place of PublicationNew York, NY, USA
Number of pages16
ISBN (Print)978-1-4503-4703-7
Publication statusPublished - 27 May 2018
Event2018 ACM SIGMOD/PODS International Conference on Management of Data - Houston, United States
Duration: 10 Jun 201815 Jun 2018

Publication series

NameSIGMOD '18


Conference2018 ACM SIGMOD/PODS International Conference on Management of Data
Abbreviated titleSIGMOD'18
Country/TerritoryUnited States
Internet address

Keywords / Materials (for Non-textual outputs)

  • factorized representation
  • incremental view maintenance
  • materialized views
  • query optimization
  • rings
  • stream processing


Dive into the research topics of 'Incremental View Maintenance with Triple Lock Factorization Benefits'. Together they form a unique fingerprint.

Cite this