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.
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 language | English |
---|---|
Title of host publication | Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems |
Publisher | Association for Computing Machinery (ACM) |
Pages | 375-392 |
Number of pages | 44 |
ISBN (Electronic) | 9781450371087 |
DOIs | |
Publication status | Published - 14 Jun 2020 |
Event | 2020 ACM SIGMOD/PODS International Conference on Management of Data - Portland, United States Duration: 14 Jun 2020 → 19 Jun 2020 https://sigmod2020.org/ |
Conference
Conference | 2020 ACM SIGMOD/PODS International Conference on Management of Data |
---|---|
Abbreviated title | SIGMOD/PODS 2020 |
Country/Territory | United States |
City | Portland |
Period | 14/06/20 → 19/06/20 |
Internet address |
Keywords
- adaptive query evaluation
- hierarchical queries
- incremental view maintenance
- sublinear enumeration delay
- sublinear update time