Boolean Tensor Decomposition for Conjunctive Queries with Negation
Boolean Tensor Decomposition for Conjunctive Queries with Negation
复制标题
带有否定的联合查询的布尔张量分解
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Dan Suciu
中科院分区：
文献类型：
--
作者：
Mahmoud Abo Khamis;H. Ngo;Dan Olteanu;Dan Suciu
我们提出了一种算法，用于以否定的方式回答连接性查询，在该查询中，否定关系的程度有限。它的数据复杂性与输入查询的正子查询的最著名算法相匹配，并根据分数乳房宽度和下一个宽度表示。查询复杂性取决于否定子查询的结构；通常，它在否定关系中发生的联接变量的数量中是指数的，但对于几类查询，它变成了多项式。
该算法取决于几项贡献。我们展示了如何通过否定关系的否定来重写查询，以与不可及的（NAE）谓词相等的结合查询，这是一个多维的不平等类似物（不是等于）。然后，我们将已知的颜色编码技术概括为NAE谓词的结合，并通过布尔张量张量分解NAE谓词的分解。可以通过概率结构来实现这种分解，该概率结构可以有效地取代。
We propose an algorithm for answering conjunctive queries with negation, where the negated relations have bounded degree. Its data complexity matches that of the best known algorithms for the positive subquery of the input query and is expressed in terms of the fractional hypertree width and the submodular width. The query complexity depends on the structure of the negated subquery; in general it is exponential in the number of join variables occurring in negated relations yet it becomes polynomial for several classes of queries.
This algorithm relies on several contributions. We show how to rewrite queries with negation on bounded-degree relations into equivalent conjunctive queries with not-all-equal (NAE) predicates, which are a multi-dimensional analog of disequality (not-equal). We then generalize the known color-coding technique to conjunctions of NAE predicates and explain it via a Boolean tensor decomposition of conjunctions of NAE predicates. This decomposition can be achieved via a probabilistic construction that can be derandomized efficiently.