Efficient Computation of Quantiles over Joins
Efficient Computation of Quantiles over Joins
复制标题
通过连接高效计算分位数
DOI：
10.1145/3584372.3588670
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Riedewald, Mirek
中科院分区：
文献类型：
--
作者：
Tziavelis, Nikolaos;Carmeli, Nofar;Gatterbauer, Wolfgang;Kimelfeld, Benny;Riedewald, Mirek
我们提出了一种高效的分位连接查询算法，简称%jq。在连接查询(JQ)的答案上的某种排序下，%JQ在指定的相对位置(例如，对于中位数为50%)处询问答案。我们的目标是避免物化所有连接答案的集合，并在数据库大小上实现准线性时间，而不考虑答案的总数。最近的二分法结果排除了对于一般的查询和订单族存在这样的算法的可能性。具体地说，对于没有自联接的非循环JQ，只要我们联接两个以上的关系(并且这些联接不是微不足道的交集)，按和排序的问题就变得棘手起来。此外，即使对于超过和的基本排序函数，如对不同属性的最小或最大排序函数，到目前为止还不知道是否存在非平凡易处理的%JQ。在这项工作中，我们发展了一种新的方法来求解%JQ，并展示了这种方法如何不仅可以恢复已知结果，而且可以推广它们和解决公开情况。我们的解决方案使用两个子例程：第一个子例程需要选择我们所称的“Pivot Answer”。第二个子例程根据该透视图对查询答案空间进行分区，并在一个分区中继续搜索，该分区表示为新数据库上的new%jq。对于枢轴选择，我们开发了一种算法，该算法适用于一大类适当单调的排名函数。第二个子例程需要为手边的特定排序函数定制构造。我们通过使用它来建立几个新的复杂性结果，展示了该方法的好处和通用性。首先，我们证明了所有非循环JQ的最小和最大可处理性，从而解决了上述问题。其次，我们将前面的%jq二分法推广到所有部分和(属性的所有子集上)。第三，我们通过设计一个适用于每个非循环JQ的确定性近似方案来处理难以处理的SUM情况。
We present efficient algorithms for Quantile Join Queries, abbreviated as %JQ. A %JQ asks for the answer at a specified relative position (e.g., 50% for the median) under some ordering over the answers to a Join Query (JQ). Our goal is to avoid materializing the set of all join answers, and to achieve quasilinear time in the size of the database, regardless of the total number of answers. A recent dichotomy result rules out the existence of such an algorithm for a general family of queries and orders. Specifically, for acyclic JQs without self-joins, the problem becomes intractable for ordering by sum whenever we join more than two relations (and these joins are not trivial intersections). Moreover, even for basic ranking functions beyond sum, such as min or max over different attributes, so far it is not known whether there is any nontrivial tractable %JQ.In this work, we develop a new approach to solving %JQ and show how this approach allows not just to recover known results, but also generalize them and resolve open cases. Our solution uses two subroutines: The first one needs to select what we call a "pivot answer". The second subroutine partitions the space of query answers according to this pivot, and continues searching in one partition that is represented as new %JQ over a new database. For pivot selection, we develop an algorithm that works for a large class of ranking functions that are appropriately monotone. The second subroutine requires a customized construction for the specific ranking function at hand.We show the benefit and generality of our approach by using it to establish several new complexity results. First, we prove the tractability of min and max for all acyclic JQs, thereby resolving the above question. Second, we extend the previous %JQ dichotomy for sum to all partial sums (over all subsets of the attributes). Third, we handle the intractable cases of sum by devising a deterministic approximation scheme that applies to every acyclic JQ.
登录
查看更多内容
聚合相对于正则表达式提取的复杂性
DOI：
--
发表时间：
2020
期刊：
International Conference on Database Theory
影响因子：
--
作者：
J. Doleschal;Noa Bratman;B. Kimelfeld;W. Martens
通讯作者：
W. Martens
3SUM 的次二次算法
影响因子：
1.1
作者：
Ilya Baran;E. Demaine;M. Patrascu
通讯作者：
M. Patrascu
用于直接访问连接查询的排名答案的易于处理的顺序
影响因子：
1.8
作者：
Carmeli, Nofar;Tziavelis, Nikolaos;Gatterbauer, Wolfgang;Kimelfeld, Benny;Riedewald, Mirek
通讯作者：
Riedewald, Mirek
DOI：
10.1137/1.9781611976489.7
发表时间：
2021
期刊：
Symposium on Algorithmic Principles of Computer Systems (APOCS
影响因子：
--
作者：
Abo-Khamis, M.;Im, S.;Moseley, B.;Pruhs, K.;Samadian, A.
通讯作者：
Samadian, A.
带有否定的联合查询的布尔张量分解
DOI：
--
发表时间：
2017
期刊：
International Conference on Database Theory
影响因子：
--
作者：
Mahmoud Abo Khamis;H. Ngo;Dan Olteanu;Dan Suciu
通讯作者：
Dan Suciu