Остановите войну!
for scientists:
default search action
Review
- Krithi Ramamritham:
Review - View Indexing in Relational Databases. ACM SIGMOD Digit. Rev. 2 (2000)
This paper was perhaps the first to talk about the "view selection problem", a problem that has since seen numerous papers published on it.
Clearly, if we want to support views, we have two extreme options: (a) using the view definition to construct the view each time the view is needed, or (b) keeping the view materialized at all times;
(a) can be time consuming and (b) is likely to place demands on both space and time. These would have been especially true in the 70's, when this paper was conceived.
Hence the author chooses an intermediate option with less space and time overheads for view usage and maintenance.
The basic idea is to select a set of views and maintain indexes for each of them. The index of each view contains pointers to the tuples of the base relations used to construct the view. Even though constructing the view using the index information will incur I/O and CPU overheads, it is not hard to see that it is still preferable to options (a) or (b) above. Of course, keeping such index information for all the defined views is likely to be impossible given that the indexes do consume space and must be maintained when updates occur. Also, it is likely to be overkill since some of the views are likely to be rarely referenced. Hence the problem of selecting the right views for which indexes must be maintained becomes important. Roussopoulos presents an efficient algorithm to achieve this.The goal of the algorithm is to select a subset of the user-specified views in such a way that it minimizes the total cost of answering queries and making updates while satisfying the requirement that additional disk storage required by the indexes is below a specified limit. To this end, the paper develops a cost model for constructing a query result and for updating a view. This cost model assumes the availability of information pertaining to the probability with which a query on the database will use a particular view and the probability with which a databse update will affect a relation used to construct a particular view.
Besides identifying this important problem and offering an efficient solution for it, the paper has a number of other novelties which have stood the test of time:
- The first of these is the use of the AND/OR directed acyclic graph model for representing alternative query plans. This model was the basis for the Volcano query optimizer and has since been adopted by Tandem and Microsoft database products.
- The paper recognized the need for exploiting the possibility that multiple queries may share some views - if these views are selected (indexed, in the paper's terminology), the multiple queries can be more efficiently processed. That is, the paper was insigtful in pointing out that two or more nonoptimal query graphs may in fact produce optimal query execution sequences if the right views are maintained. Selection of views (or subexpressions common to multiple queries) is one of the key ingredients of the multi query optimization problem.
- The need for systematically managing related (e.g., hierarchically organized) views is recognized as a problem by itself. This has recently been the subject of many papers that deal with efficiently computing data cubes where such hierarchies occur naturally during the computation of the aggregates.
The number of papers that have since appeared on topics that were, in one single paper, introduced by Roussopoulos is remarkable. Of course, the solution space has broadened - given the relatively better endowed disk storage units and faster processors, today, we can afford to keep selected views themselves as opposed to just indexes for the selected views.
Also, noteworthy has been Professor Roussopoulos's persistence with views, subsequently enlarged to encompass the related issue of caching and (incremental) cache maintenance, as seen by the series of papers related to his ADMS project. The most recent is the award-winning paper on Dynamic View Management System called DynaMat [2] that was presented in SIGMOD '99.
But, indicative of Computer Scientists' inclination to "view" only the recent literature is the observation that the 1982 TODS paper is not the one typically cited when authors refer to many of the problems that it introduced. In fact, one does not find a citation for it in author's own latest SIGMOD paper!
- Krithi Ramamritham:
Review - View Indexing in Relational Databases. ACM SIGMOD Digit. Rev. 2 (2000)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.