Stanford InfoLab Publication Server

Speeding Up Materialized View Maintenance Using Cheap Filters at the Warehouse

Huyn, N. (1999) Speeding Up Materialized View Maintenance Using Cheap Filters at the Warehouse. Technical Report. Stanford. (Publication Note: A shortened version will appear in ICDE 2000)




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:Techreport (Technical Report)
Uncontrolled Keywords:View Maintenance; Runtime Optimization
Subjects:Computer Science > Data Warehousing
Projects:Information Integration
Related URLs:Project Homepage
ID Code:382
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:28 Dec 2008 09:18

Download statistics

Repository Staff Only: item control page