Stanford InfoLab Publication Server

Speeding Up View Maintenance Using Cheap Filters at the Warehouse

Huyn, N. (2000) Speeding Up View Maintenance Using Cheap Filters at the Warehouse. In: 16th International Conference on Data Engineering (ICDE 2000), February 28 - 3 March 3, 2000, San Diego, California.




We consider the problem of speeding up the incremental maintenance of materialized views defined by conjunctive queries (CQ) over external base relations, when querying these base relations is {\em expensive}. Our approach consists of detecting, {\em without} using the base relations, situations where a view either is not affected by a base update (VDU) or can be maintained using only the views in the warehouse (VSM). We are doing runtime optimization of view maintenance, since the tests take the current state of the warehouse database into account. Testing VSM for CQ views in general is known to be co-NP-complete in the size of the views, and testing VDU is conjectured to be as hard. In this paper, we identify important subclasses of CQ views for which VDU and VSM can be tested {\em completely} and {\em efficiently}, using only a small constant number of view lookups. This result is significant because, by maintaining indexes on selected view attributes, we can speed up view maintenance practically without incurring any substantial overhead. For more general CQ views, we show sufficient tests for VDU and VSM that have comparable efficiency. To demonstrate the performance of our method, we implement a view manager in Oracle PL-SQL which maintains a simple view under various synthetic update streams and under various delays in querying the base relations. Our results clearly show situations where tremendous speedup can be achieved. While further performance studies remain to be done, we believe our approach has a great potential to significantly speed up incremental data warehouse maintenance.

Item Type:Conference or Workshop Item (Paper)
Uncontrolled Keywords:View Maintenance; Runtime Optimization
Subjects:Computer Science > Data Warehousing
Projects:Information Integration
Related URLs:Project Homepage
ID Code:435
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:27 Dec 2008 14:42

Download statistics

Repository Staff Only: item control page