论文标题
安全的亚军无环连接
Safe Subjoins in Acyclic Joins
论文作者
论文摘要
通常由于中间关系较大，计算连接的昂贵。对于无环的联接，单调连接表达式可以保证产生的中间关系不大于在完全减少的数据库上计算结合的连接输出的大小。无环的任何子表达都不提供此保证，因为很容易证明。在本文中，我们也考虑加入预测，我们问一个问题，我们是否可以表征加入的子表达式，这些子表达式在每个完全减少的数据库中，一个没有悬挂式的输出的输出（在没有预测的情况下，将其转换为不超过联接输出大小的大小的输出）。我们称这种子表达为安全的子加入。令人惊讶的是，我们证明存在一个简单的特征，这是以下内容：当且仅当有一个结合的解析树（又称加入树）时，亚subjoin是安全的，使该子加入中的关系形成了它的子树。如果有的话，我们提供了一种算法，可以找到这样的解析树。
It is expensive to compute joins, often due to large intermediate relations. For acyclic joins, monotone join expressions are guaranteed to produce intermediate relations not larger than the size of the output of the join when it is computed on a fully reduced database. Any subexpression of an acyclic join does not offer this guarantee, as it is easy to prove. In this paper, we consider joins with projections too and we ask the question whether we can characterize join subexpressions that produce, on every fully reduced database, an output without dangling tuples (which translates, in the case of joins without projections, to an output of size not larger than the size of the output of the join). We call such a subexpression a safe subjoin. Surprisingly, we prove that there is a simple characterization which is the following: A subjoin is safe if and only if there is a parse tree of the join (a.k.a. join tree) such that the relations in the subjoin form a subtree of it. We provide an algorithm that finds such a parse tree, if there is one.
