Maintaining Acyclic Foreign-Key Joins under Updates

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

6 Citations (Scopus)


A large number of analytical queries (e.g., all the 22 queries in the TPC-H benchmark) are based on acyclic foreign-key joins. In this paper, we study the problem of incrementally maintaining the query results of these joins under updates, i.e., insertion and deletion of tuples to any of the relations. Prior work has shown that this problem is inherently hard, requiring at least ω(|db|1/2 -ϵ) time per update, where |db| is the size of the database, and ϵ > 0 can be any small constant. However, this negative result holds only on adversarially constructed update sequences; on the other hand, most real-world update sequences are "nice", nowhere near these worst-case scenarios. We introduce a measure λ, which we call the enclosureness of the update sequence, to more precisely characterize its intrinsic difficulty. We present an algorithm to maintain the query results of any acyclic foreign-key join in O(λ) time amortized, on any update sequence whose enclosureness is λ. This is complemented with a lower bound of ω(λ1-ϵ), showing that our algorithm is essentially optimal with respect to λ. Next, using this algorithm as the core component, we show how all the 22 queries in the TPC-H benchmark can be supported in ∼O(łambda) time. Finally, based on the algorithms developed, we built a continuous query processing system on top of Flink, and experimental results show that our system outperforms previous ones significantly.

Original languageEnglish
Title of host publicationSIGMOD 2020 - Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data
PublisherAssociation for Computing Machinery (ACM)
Number of pages15
ISBN (Electronic)9781450367356
Publication statusPublished - 11 Jun 2020
EventACM SIGMOD International Conference on Management of Data, SIGMOD 2020 - Portland, United States
Duration: 14 Jun 202019 Jun 2020

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)0730-8078


ConferenceACM SIGMOD International Conference on Management of Data, SIGMOD 2020
Country/TerritoryUnited States
Internet address

Scopus Subject Areas

  • Software
  • Information Systems

User-Defined Keywords

  • acyclic joins
  • incremental view maintenance
  • query evaluation under updates
  • sliding windows


Dive into the research topics of 'Maintaining Acyclic Foreign-Key Joins under Updates'. Together they form a unique fingerprint.

Cite this