Afrati, Foto and Li, Chen and Ullman, Jeff (2001) Generating Efficient Plans for Queries Using Views (Full Version). Technical Report. Stanford.
This is the latest version of this item.
We study the problem of generating efficient, equivalent rewritings using views to compute the answer to a query. We take the closed-world assumption, in which views are materialized from base relations, rather than views describing 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 infinite number of different rewritings that compute the same answer, yet have quite different performance. Query optimizers take a logical plan (a rewriting of the query) as an input, and generate efficient physical plans to compute 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 physical 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 develop an efficient algorithm for finding rewritings with the minimum number of subgoals. We then consider a cost model that counts the sizes of intermediate relations of a physical plan, without dropping any attributes, and give a search space for finding optimal rewritings. Our final cost model allows attributes to be dropped in intermediate relations. We show that, by careful variable renaming, it is possible to do better than the standard ``supplementary relation'' approach, by dropping attributes that the latter approach would retain. Experiments show that our algorithm of generating optimal rewritings has good efficiency and scalability.
|Item Type:||Techreport (Technical Report)|
|Additional Information:||Full version of the corresponding ACM SIGMOD paper, with detailed proofs.|
|Uncontrolled Keywords:||Information integration, answering queries using views, efficiency of rewritings|
|Subjects:||Computer Science > Databases and the Web|
Computer Science > Data Integration and Mediation
Computer Science > Query Processing
|Related URLs:||Project Homepage, Project Homepage||http://infolab.stanford.edu/serf/, http://infolab.stanford.edu/tsimmis/tsimmis.html|
|Deposited By:||Import Account|
|Deposited On:||10 Mar 2001 16:00|
|Last Modified:||26 Dec 2008 17:13|
Available Versions of this Item
- Generating Efficient Plans for Queries Using Views. (deposited 04 Mar 2001 16:00)
- Generating Efficient Plans for Queries Using Views (Full Version). (deposited 10 Mar 2001 16:00) [Currently Displayed]
Repository Staff Only: item control page