论文标题
在更新下维护三角查询
Maintaining Triangle Queries under Updates
论文作者
论文摘要
我们考虑了在输入关系的单键盘更新下使用任意自由变量来逐步维护三角形查询的问题。我们介绍了一种称为IVM $^ε$的方法，该方法在更新时间，空间和查询结果枚举的延迟之间表现出权衡，以使更新时间从数据库大小的平方根到线性范围，而延迟范围从持续的延迟到恒定的线性时间。 IVM $^ε$在在线矩阵 - 矢量乘法下的更新延迟空间中实现了帕累托最糟糕的最优性。对于零或三个自由变量的三角形查询，它非常最佳，并且对于具有一个或两个自由变量的三角形查询而言，弱帕累托最佳。
We consider the problem of incrementally maintaining the triangle queries with arbitrary free variables under single-tuple updates to the input relations. We introduce an approach called IVM$^ε$ that exhibits a trade-off between the update time, the space, and the delay for the enumeration of the query result, such that the update time ranges from the square root to linear in the database size while the delay ranges from constant to linear time. IVM$^ε$ achieves Pareto worst-case optimality in the update-delay space conditioned on the Online Matrix-Vector Multiplication conjecture. It is strongly Pareto optimal for the triangle queries with zero or three free variables and weakly Pareto optimal for the triangle queries with one or two free variables.
