On Functional Aggregate Queries with Additive Inequalities
On Functional Aggregate Queries with Additive Inequalities
复制标题
DOI：
10.1145/3294052.3319694
复制
发表时间：
2018-12
期刊：
影响因子：
--
通讯作者：
Mahmoud Abo Khamis;Ryan R. Curtin;Benjamin Moseley;H. Ngo;X. Nguyen;Dan Olteanu;Maximilian Schleich
中科院分区：
文献类型：
--
作者：
Mahmoud Abo Khamis;Ryan R. Curtin;Benjamin Moseley;H. Ngo;X. Nguyen;Dan Olteanu;Maximilian Schleich
受数据库和关系机器学习的基本应用的启发，我们提出并研究了函数聚集查询(FAQ)的回答问题，其中部分输入因素由变量之间的加性不等定义。我们将这些查询简称为FAQ-AI。为了回答布尔半环中的FAQ-AI问题，我们定义了松弛树分解以及松弛子模和分数阶超树宽度参数。我们证明了利用Chazelle几何数据结构解决半群范围搜索问题的Inside Out算法的扩展可以在这些新的宽度参数给定的时间内回答布尔FAQ-AI。与已有的FAQ-AI算法相比，该算法具有更低的复杂度。它还恢复了数据库查询应答中的一些已知结果。我们的第二个贡献是对多拟阵集合的松弛，它产生了由#subw表示的子模宽度的计数版本。这个新的宽度被夹在子模和分数超树宽度之间。一个半环上的任何FAQ和FAQ-AI都可以在时间上与#subw成比例地回答，并分别与#subw的放松版本成比例。我们给出了我们的FAQ-AI框架在关系机器学习中的三个应用：K-均值聚类，训练线性支持向量机，以及使用非多项式损失的训练模型。这些优化问题可以在数据库上渐进地比计算数据库关系的连接更快地解决。
Motivated by fundamental applications in databases and relational machine learning, we formulate and study the problem of answering functional aggregate queries (FAQ) in which some of the input factors are defined by a collection of additive inequalities between variables. We refer to these queries as FAQ-AI for short. To answer FAQ-AI in the Boolean semiring, we define relaxed tree decompositions and relaxed submodular and fractional hypertree width parameters. We show that an extension of the InsideOut algorithm using Chazelle's geometric data structure for solving the semigroup range search problem can answer Boolean FAQ-AI in time given by these new width parameters. This new algorithm achieves lower complexity than known solutions for FAQ-AI. It also recovers some known results in database query answering. Our second contribution is a relaxation of the set of polymatroids that gives rise to the counting version of the submodular width, denoted by #subw. This new width is sandwiched between the submodular and the fractional hypertree widths. Any FAQ and FAQ-AI over one semiring can be answered in time proportional to #subw and respectively to the relaxed version of #subw. We present three applications of our FAQ-AI framework to relational machine learning: k-means clustering, training linear support vector machines, and training models using non-polynomial loss. These optimization problems can be solved over a database asymptotically faster than computing the join of the database relations.