  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.

Databases