Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries

Ahmet Kara, Milos Nikolic, Dan Olteanu, Haozhe Zhang

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

Abstract

We investigate trade-offs in static and dynamic evaluation of hierarchical queries with arbitrary free variables. In the static setting, the trade-off is between the time to partially compute the query result and the delay needed to enumerate its tuples. In the dynamic setting, we additionally consider the time needed to update the query result in the presence of single-tuple inserts and deletes to the input database.
Our approach observes the degree of values in the database and uses different computation and maintenance strategies for high-degree and low-degree values. For the latter it partially computes the result, while for the former it computes enough information to allow for on-the-fly enumeration.
The main result of this work defines the preprocessing time, the update time, and the enumeration delay as functions of the light/heavy threshold. By conveniently choosing this threshold, our approach can recover a number of prior results when restricted to hierarchical queries.
Original languageEnglish
Title of host publicationProceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
PublisherAssociation for Computing Machinery (ACM)
Pages375-392
Number of pages44
ISBN (Electronic)9781450371087
DOIs
Publication statusPublished - 14 Jun 2020
Event2020 ACM SIGMOD/PODS International Conference on Management of Data - Portland, United States
Duration: 14 Jun 202019 Jun 2020
https://sigmod2020.org/

Conference

Conference2020 ACM SIGMOD/PODS International Conference on Management of Data
Abbreviated titleSIGMOD/PODS 2020
Country/TerritoryUnited States
CityPortland
Period14/06/2019/06/20
Internet address

Keywords

  • adaptive query evaluation
  • hierarchical queries
  • incremental view maintenance
  • sublinear enumeration delay
  • sublinear update time

Cite this