General dynamic Yannakakis: conjunctive queries with theta joins under updates

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

  • Muhammad Idris - , Chair of Databases (Author)
  • Martín Ugarte - , Pontificia Universidad Católica de Chile (Author)
  • Stijn Vansummeren - , Université libre de Bruxelles (ULB) (Author)
  • Hannes Voigt - , Chair of Databases (Author)
  • Wolfgang Lehner - , Chair of Databases (Author)

Abstract

The ability to efficiently analyze changing data is a key requirement of many real-time analytics applications. In prior work, we have proposed general dynamic Yannakakis (GDyn), a general framework for dynamically processing acyclic conjunctive queries with θ-joins in the presence of data updates. Whereas traditional approaches face a trade-off between materialization of subresults (to avoid inefficient recomputation) and recomputation of subresults (to avoid the potentially large space overhead of materialization), GDyn is able to avoid this trade-off. It intelligently maintains a succinct data structure that supports efficient maintenance under updates and from which the full query result can quickly be enumerated. In this paper, we consolidate and extend the development of GDyn. First, we give full formal proof of GDyn ’s correctness and complexity. Second, we present a novel algorithm for computing GDyn query plans. Finally, we instantiate GDyn to the case where all θ-joins are inequalities and present extended experimental comparison against state-of-the-art engines. Our approach performs consistently better than the competitor systems with multiple orders of magnitude improvements in both time and memory consumption.

Details

Original languageEnglish
Pages (from-to)619-653
Number of pages35
JournalThe VLDB journal
Volume29
Issue number2-3
Publication statusPublished - 1 May 2020
Peer-reviewedYes

External IDs

Scopus 85075370130
dblp journals/vldb/IdrisUVVL20

Keywords

Keywords

  • Acyclic joins, Complex event processing, Dynamic query processing, Incremental view maintenance, Inequalities, Theta joins