Maintaining Triangle Queries under Updates

Ahmet Kara, Hung Q. Ngo, Milos Nikolic, Dan Olteanu, Haozhe Zhang

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the problem of incrementally maintaining the triangle queries with arbitrary free variables under single-tuple updates to the input relations. We introduce an approach called IVM-ϵ that exhibits a trade-off between the update time, the space, and the delay for the enumeration of the query result, such that the update time ranges from the square root to linear in the database size while the delay ranges from constant to linear time. IVM-ϵ achieves Pareto worst-case optimality in the update-delay space conditioned on the Online Matrix-Vector Multiplication conjecture. It is strongly Pareto optimal for the triangle queries with zero or three free variables and weakly Pareto optimal for the triangle queries with one or two free variables.
Original languageEnglish
Article number11
Pages (from-to)1-46
Number of pages46
JournalACM Transactions on Database Systems
Volume45
Issue number3
DOIs
Publication statusPublished - 26 Aug 2020

Keywords

  • Incremental view maintenance
  • Pareto worst-case optimality
  • amortized update time
  • enumeration delay
  • complexity trade-off

Cite this