Incremental View Maintenance with Triple Lock Factorization Benefits

Milos Nikolic, Dan Olteanu

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

Abstract

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
PublisherACM
Pages365-380
Number of pages16
ISBN (Print)978-1-4503-4703-7
DOIs
Publication statusPublished - 27 May 2018
Event2018 ACM SIGMOD/PODS International Conference on Management of Data - Houston, United States
Duration: 10 Jun 201815 Jun 2018
https://sigmod2018.org/

Publication series

NameSIGMOD '18
PublisherACM

Conference

Conference2018 ACM SIGMOD/PODS International Conference on Management of Data
Abbreviated titleSIGMOD'18
CountryUnited States
CityHouston
Period10/06/1815/06/18
Internet address

Keywords

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

Fingerprint

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

Cite this