A study of optimization and Rule/Goal Graph for a logical query

Static optimization of logical queries is, in substance, to move selections down as far as possible in evaluating logical queries. This paper extends Ullman's RGG (Rule/Goal Graph)[6] and introduces P-graph, with which a wide range of recursive logical queries can be statically optimized top-down and evaluated bottom-up, some of which are usually optimized by dynamic approaches. The paper also shows that for some logical queries the complexity of pushing selections down and computing bottom-up is related to the complexity of base relation in the queries.