Not logged in.

Quick Search - Contribution

Contribution Details

Type Master's Thesis
Scope Discipline-based scholarship
Title CaVieR: CAscading VIEw tRees
Organization Unit
Authors
  • Johann Schwabe
Supervisors
  • Dan Olteanu
  • Haozhe Zhang
Language
  • English
Institution University of Zurich
Faculty Faculty of Business, Economics and Informatics
Date 2023
Abstract Text Maintaining multiple complex queries on large, dynamic datasets in real time poses a major challenge. Thus, this thesis introduces CAscading VIEw tRees (CaVieR), an extension to Factorized Incremental View Maintenance (F-IVM) that addresses this challenge. CaVieR adds a method to F-IVM that joins the view trees of multiple conjunctive queries into a directed acyclic graph (DAG). This can efficiently handle updating and enumerating a set of Cascading Q-Hierarchical Queries. Reducing redundant query maintenance significantly reduces computational workload and can even reduce the theoretical asymptotic complexity of maintaining Cascading Q-Hierarchical Queries. The algorithm was tested against F-IVM on synthetic and real-world datasets with different sets of Cascading Q-Hierarchical Queries. In experiments, the two main performance indicators in IVM were measured: update time and enumeration delay. While in most scenarios, a significant improvement in both measurements was observed, it was found that F-IVM, when using batch updates and ordered input relation streams, can outperform CaVieR. To verify that this is the only scenario where individually maintaining the view trees is better than joining them, various parameters were tested, and their influence on update time and enumeration delay was recorded. While parameters like the cardinality of the input relations and the number of free vari- ables significantly influenced the update time and enumeration delay, CaVieR outperformed F-IVM consistently. Thus this thesis not only presents a new method of optimization to F-IVM that can decrease the asymptotic complexity of the problem, including theoret- ical proofs of correctness and completeness. It also includes an implementation and experiments to estimate its performance impact.
PDF File Download
Export BibTeX