Approximate Aggregate Queries Under Additive Inequalities
Approximate Aggregate Queries Under Additive Inequalities
复制标题
加性不等式下的近似聚合查询
DOI：
10.1137/1.9781611976489.7
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Samadian, A.
中科院分区：
文献类型：
--
作者：
Abo-Khamis, M.;Im, S.;Moseley, B.;Pruhs, K.;Samadian, A.
我们考虑的问题，评估某些类型的功能聚集查询的关系数据的加法不等式。这样的聚合查询，具有少量的加法不等式，在许多应用中，特别是在学习应用中自然/常见地出现。我们给出了一个相对完整的分类计算的复杂性，这样的问题。我们首先证明了这个问题是NP-困难的，即使在一个加法不等式的情况下。因此，我们转向近似查询。我们的主要结果是一个有效的算法近似，任意小的相对误差，许多自然的聚集查询与一个加法不等式。我们给出的自然查询，可以有效地解决使用该算法的例子。相比之下，我们表明，两个加法不等式的情况是完全不同的，通过显示，它是NP-难的简单的聚合查询，两个加法不等式，任何有界的相对误差进行评估。
We consider the problem of evaluating certain types of functional aggregation queries on relational data subject to additive inequalities. Such aggregation queries, with a smallish number of additive inequalities, arise naturally/commonly in many applications, particularly in learning applications. We give a relatively complete categorization of the computational complexity of such problems. We first show that the problem is NP-hard, even in the case of one additive inequality. Thus we turn to approximating the query. Our main result is an efficient algorithm for approximating, with arbitrarily small relative error, many natural aggregation queries with one additive inequality. We give examples of natural queries that can be efficiently solved using this algorithm. In contrast, we show that the situation with two additive inequalities is quite different, by showing that it is NP-hard to evaluate simple aggregation queries, with two additive inequalities, with any bounded relative error.
带有否定的联合查询的布尔张量分解
DOI：
--
发表时间：
2017
期刊：
International Conference on Database Theory
影响因子：
--
作者：
Mahmoud Abo Khamis;H. Ngo;Dan Olteanu;Dan Suciu
通讯作者：
Dan Suciu
DOI：
--
发表时间：
2019-01
期刊：
--
影响因子：
--
作者：
A. Burkov
通讯作者：
A. Burkov
回答带有不等式的连接查询
影响因子：
0.5
作者：
Paraschos Koutris;Tova Milo;Sudeepa Roy;Dan Suciu
通讯作者：
Dan Suciu