Selection propagation in deductive databases from pushing selections to magic sets

摘要

This paper discusses the relationship between two optimization methods in deductive databases: the distribution of selections and the magic sets method. The former is a direct generalization of pushing selections in relational databases, and the latter realizes a more general view of selection propagation. The characteristics of the generalized form of the distribution of selections are discussed and compared to other methods. It is shown that the distribution of selections corresponds to one of the least effective variations of the magic sets method. It is also shown that both methods have essentially the same power for non-recursive queries. Hence, the magic sets method can be regarded as a natural generalization of pushing selections in relational databases.