We study the problem of generating efficient, equivalent rewritings using v
iews to compute the answer to a query. We take the closed-world assumption,
in which views are materialized from base relations, rather than views des
cribing sources in terms of abstract predicates, as is common when the open
-world assumption is used. In the closed-world model, there can be an infin
ite number of different rewritings that compute the same answer, yet have q
uite different performance. Query optimizers take a logical plan (a rewriti
ng of the query) as an input, and generate efficient physical plans to comp
ute the answer. Thus our goal is to generate a small subset of the possible
logical plans without missing an optimal physical plan.
We first consider a cost model that counts the number of subgoals in a phys
ical plan, and show a search space that is guaranteed to include an optimal
rewriting, if the query has a rewriting in terms of the views. We also dev
elop an efficient algorithm for finding rewritings with the minimum number
of subgoals. We then consider a cost model that counts the sizes of interme
diate relations of a physical plan, without dropping any attributes, and gi
ve a search space for finding optimal rewritings. Our final cost model allo
ws attributes to be dropped in intermediate relations. We show that, by car
eful variable renaming, it is possible to do better than the standard "supp
lementary relation" approach, by dropping attributes that the latter approa
ch would retain. Experiments show that our algorithm of generating optimal
rewritings has good efficiency and scalability.