Quadratic Algorithms for Minimizing Joins in Restricted Relational Expressions
Yehoshua Sagiv · SIAM Journal on Computing · 1983
An important step in the optimization of queries in relational databases is minimizing the number of join operations in the evaluation of a query. It is shown that three subclasses of tableaux (including the subclass of simple tableaux) have $O(n^2 )$ time equivalence and minimization algorithms. Since tableaux are nonprocedural representations of relational expressions over select, project and join, these minimization algorithms can be used to minimize the number of join operators in expressions whose tableaux belong to one of these subclasses.