一句话：通过按值度数采用轻重策略，统一刻画层次查询在静态与动态求值中预处理、更新与枚举延迟的权衡。
本文研究带任意自由变量的层次查询在静态与动态求值中的权衡。静态设置关注部分计算结果的时间与枚举元组延迟之间的取舍；动态设置还考虑单元组插入或删除后更新结果的时间。方法上，算法观察数据库值的度数，对高度数（heavy）和低度数（light）值采用不同策略：对 light 值部分计算并物化结果，对 heavy 值只计算足以支持按需枚举的信息。作者将预处理时间、更新时间与枚举延迟表示为 light/heavy 阈值的函数，并说明适当选择阈值可恢复若干已有结果。最后证明，对一类受限层次查询，在 Online Matrix-Vector Multiplication 猜想下，该方法达到最坏情况最优的更新时间和枚举延迟。
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 under single-tuple inserts or deletes to the database. Our approach observes the degree of values in the database and uses different computation and maintenance strategies for high-degree (heavy) and low-degree (light) values. For the latter it partially computes the result, while for the former it computes enough information to allow for on-the-fly enumeration. We define the preprocessing time, the update time, and the enumeration delay as functions of the light/heavy threshold. By appropriately choosing this threshold, our approach recovers a number of prior results when restricted to hierarchical queries. We show that for a restricted class of hierarchical queries, our approach achieves worst-case optimal update time and enumeration delay conditioned on the Online Matrix-Vector Multiplication Conjecture.
@article{paperbot2199,
title = {Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries},
author = {Ahmet Kara and Milos Nikolic and Dan Olteanu and Haozhe Zhang},
journal = {Logical Methods in Computer Science},
volume = {Volume 19, Issue 3},
year = {2023},
doi = {10.46298/lmcs-19(3:11)2023}
}