Optimization of Linear Recursive Queries in SQL
Recursion is a fundamental computation mechanism which has been incorporated into SQL. This work focuses on the optimization of linear recursive queries in SQL. Query optimization is studied with two important graph problems: computing the transitive closure of a graph and getting the power matrix of its adjacency matrix. The authors present SQL implementations for two fundamental algorithms: Seminaive and Direct. Five query optimizations are studied: storage and indexing; early selection; early evaluation of non-recursive joins; pushing duplicate elimination; pushing aggregation.