Quadratic-Time Optimization of SPJ-Expressions Including Inequality Selections by Tableaux
Alois P. Heinz, Gottfried Vossen · Fundamenta Informaticae · 1985
The problem of optimizing algebraic queries to relational databases which are formulated with the help of inequality selection, projection, and natural join is addressed: We generalize the well-known tableau formalism to handle this type of queries and provide a quadratic-time optimization procedure. We show how optimized tableaux can be translated back into extended SPJ-expressions, thereby dispensing with the computationally harder cartesian product.