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) 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 t…