Generating Low-cost Plans From Proofs

We look at generating plans that answer queries over restricted interfaces, making use of information about source integrity constraints, access restrictions, and access costs. Our method can exploit the integrity constraints to find low-cost access plans even when there is no direct access to relations appearing in the query. The key idea of our method is to move from a search for a plan to a search for a proof that a query is answerable, and then generate a plan from a proof. Discovery of one proof allows us to find a single plan that answers the query; exploration of several alternative proofs allows us to find low-cost plans. We start by mapping out a correspondence between proofs and restricted interface plans in the context of arbitrary first-order constraints, based on interpolation. The correspondence clarifies the connection between preservation and interpolation theorems in predicate logic and reformulation problems, and generalizes it in several dimensions. We then provide algorithms for schemas based on tuple-generating dependencies. These algorithms perform interpolation, but generate plans directly. Finally, we show how the direct plan-generation approach can be adapted to take into account the cost of plans.