(last updated June 15, 1998)

EVE: Optimization in View Synchronization

Project Overview

WWW-based information services such as data warehousing, digital libraries, data mining typically gather data from a large number of interconnected Information Sources (ISs). In order to provide efficient information access to such information services, relevant data is often retrieved from several sources, integrated as necessary, and then assembled into a materialized view (data warehouse). Besides providing simplified information access to customers without the necessary technical background, materialized views also offer higher availability and query performance.

In our recent work we study the maintenance of data warehouses defined over distributed dynamic information sources. A view can survive schema changes of its underlying information sources by making use of meta-information about those sources and applying algorithms for rewriting the view query; a process to which we refer to as view synchronization and which is accomplished through several view synchronization algorithms. We have proposed a model of relaxed query semantics to allow for the rewritings of view queries that preserve different view extents and view interfaces (we call this the quality of the view) and result in different view maintenance costs. Since we will in general be able to generate a number of different such rewritings for a given situation, we need to compare rewritings with each other and with the original view to determine their desirability for a view user, which is done through the QC-Model.

In this paper, we now examine the complexity of this view synchronization process. We identify that its most powerful algorithm has a high complexity (in O(n!)). We now reduce this complexity by mapping the problem of complex view synchronization to a polynomial complexity graph traversal problem. One key ingredient of our solution is the observation that the computation of quality and cost measures, namely the ranking of view queries, previously done as a post-processing step to each view query identified by the view synchronization algorithm, can be decomposed into a stepwise computation by expressing view synchronization as a graph problem. This also allows us to integrate the query ranking phase with the phase of finding of rewritings instead of executing two separate phases of view synchronization. We term our solution the Optimized CVS algorithm and show that the algorithm has a complexity in O(n^3).

Project Members

Advisor

Elke Rundensteiner

Graduate Students

Andreas Koeller

Publications

1999

Andreas Koeller and Elke A. Rundensteiner.
View Synchronization: Using an Integrated Approach of Rewriting and Ranking View Queries.
Computer Science Information Management Journal, Volume 2 Number 1, ???-??? (1999), Maximilian Press Publisher

1998

A. Koeller, E. A. Rundensteiner, and N. Hachem.
Integrating the Rewriting and Ranking Phases of View Synchronization
Technical Report WPI-CS-TR-98-23, Worcester Polytechnic Institute, Dept. of Computer Science, 1998.

A. Koeller, E. A. Rundensteiner, and N. Hachem.
"Integrating the Rewriting and Ranking Phases of View Synchronization"
ACM First International Workshop on Data Warehousing and OLAP Computer Science (DOLAP '98), Washington, D.C., Nov. 7, 1998.