Domain Ordering and Box Cover Problems for Beyond Worst-Case Join Processing
Domain Ordering and Box Cover Problems for Beyond Worst-Case Join Processing
复制标题
最坏情况连接处理之外的域排序和盒盖问题
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Kaleb Alway
中科院分区：
文献类型：
--
作者：
Kaleb Alway
加入查询是关系数据库管理系统中的一项基本计算任务。次级次数。最糟糕的案例最佳，这意味着它们与具有相同形状的任何查询和相同数量的输入元组成正比的时间成正比。通过利用输入实例的结构，而不是查询形状，tetris是最佳的，并且在其运行时间上提供了一个算法。输入查询的几何盒子证书的最小尺寸。当我们根据域上订购了域中的值不同时，许多查询实例中没有包含的元组。允许较小的盒子证书，使用置换的查询作为tetris的输入，然后使用逆域排序转换结果，如果我们可以有效地计算最佳订单，我们可以比固定域订购的速度更快地计算查询。域订购查询，然后我们可以说出一个超出最差的界限，该结合比Tetris提供的更强大[1]。订购的目的是最小化最小框证书的大小或给定输入查询的最小盒子盖我们将研究的大多数盒子封面最小化问题Boxminpdomf被证明是NP-HARD，但我们可以计算大小的近似值（（k ∗）A·r），其中k ∗是最小盒子盖尺寸在任何域排序中，A是查询图中属性的最大程度，R是关系中的最大属性数量。 r·（W +1） +z），其中n是输入元组，W是查询的树宽，Z是输出元组的数量对于该界限，该界限呈指数型小于任何界限由Tetris提供。
Join queries are a fundamental computational task in relational database management systems. For decades, complex joins were most often computed by decomposing the query into a query plan made of a sequence of binary joins. However, for cyclic queries, this type of query plan is sub-optimal. The worst-case run time of any such query plan exceeds the number of output tuples for any query instance. Recent theoretical developments in join query processing have led to join algorithms which are worst-case optimal, meaning that they run in time proportional to the worstcase output size for any query with the same shape and the same number of input tuples. Building on these results are a class of algorithms providing bounds which go beyond this worst-case output size by exploiting the structure of the input instance rather than just the query shape. One such algorithm, Tetris, is worst-case optimal and also provides an upper bound on its run time which depends on the minimum size of a geometric box certificate for the input query. A box certificate is a subset of a box cover whose union covers every tuple which is not present in the query output. A box cover is a set of n-dimensional boxes which cover all of the tuples not contained in the input relations. Many query instances admit different box certificates and box covers when the values in the attributes’ domains are ordered differently. If we permute the input query according to a domain ordering which admits a smaller box certificate, use the permuted query as input to Tetris, then transform the result back with the inverse domain ordering, we can compute the query faster than was possible if the domain ordering was fixed. If we can efficiently compute an optimal domain ordering for a query, then we can state a beyond worst-case bound that is stronger than what is provided by Tetris [1]. This thesis defines several optimization problems over the space of domain orderings where the objective is to minimize the size of either the minimum box certificate or the minimum box cover for the given input query. We show that most of these problems are NP-hard. We also provide approximation algorithms for several of these problems. The most general version of the box cover minimization problem we will study, BoxMinPDomF, is shown to be NP-hard, but we can compute an approximation of size Õ((K∗ ) a·r), where K∗ is the minimum box cover size under any domain ordering, a is the maximum degree of an attribute in the query graph, and r is the maximum number of attributes in a relation. This result allows us to compute join queries in time Õ(N + (K∗ ) a·r·(w+1) +Z), where N is the number of input tuples, w is the treewidth of the query, and Z is the number of output tuples. This is a new beyond worst-case bound. There are queries for which this bound is exponentially smaller than any bound provided by Tetris.