On the Complexity of Division and Set Joins in the Relational Algebra Dirk Leinders and Jan Van den Bussche   View Paper (PDF)   Return to Research Session 2: Complexity and Performance Evaluation Abstract We show that any expression of the relational division operator in the relational algebra with union, difference, projection, selection, and equijoins, must produce intermediate results of quadratic size. To prove this result, we show a dichotomy theorem about intermediate sizes of relational algebra expressions (they are either all linear, or at least one is quadratic); we link linear relational algebra expressions to expressions using only semijoins instead of joins; and we link these semijoin algebra expressions to the guarded fragment of first-order logic. ©2006 Association for Computing Machinery