Integrating the Rewriting and Ranking Phases of View Synchronization.

Andreas Koeller, Elke A. Rundensteiner, Nabil I. Hachem: Integrating the Rewriting and Ranking Phases of View Synchronization. DOLAP 1998: 60-65
  author    = {Andreas Koeller and
               Elke A. Rundensteiner and
               Nabil I. Hachem},
  title     = {Integrating the Rewriting and Ranking Phases of View Synchronization},
  booktitle = {DOLAP '98, ACM First International Workshop on Data Warehousing
               and OLAP, November 7, 1998, Bethesda, Maryland, USA, Proceedings},
  publisher = {ACM},
  year      = {1998},
  pages     = {60-65},
  ee        = {db/conf/dolap/KoellerRH98.html,},
  crossref  = {DBLP:conf/dolap/98},
  bibsource = {DBLP,}


Materialized views (data warehouses) are becoming increasingly important in the context of distributed modern environments such as the World Wide Web. Information sources (ISs) in such an environment may change their capabilities (schema), causing a data warehouse to become undefined. This process to evolve (rewrite) view queries after capability changes of ISs is referred to as view synchronization. Current view synchronization algorithms generate a potentially large number of valid solutions for the rewriting of a view query and according to our analysis in this paper have high complexity (in O(n!)). We propose to reduce this complexity by representing the synchronization problem as a graph traversal problem. Once this mapping has been applied, the problem can be reduced to a single-source shortest-path problem in graphs, which can be solved with O(n3) complexity using the Bellman-Ford algorithm.

Copyright © 1998 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 2 Issue 4, CIKM, DOLAP, GIS, SIGFIDET, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

DOLAP '98, ACM First International Workshop on Data Warehousing and OLAP, November 7, 1998, Bethesda, Maryland, USA, Proceedings. ACM 1998
Contents BibTeX

Online Edition

Citation Page BibTeX


Divyakant Agrawal, Amr El Abbadi, Ambuj K. Singh, Tolga Yurek: Efficient View Maintenance at Data Warehouses. SIGMOD Conference 1997: 417-427 BibTeX
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to Algorithms. The MIT Press and McGraw-Hill Book Company 1989, ISBN 0-262-03141-8,0-07-013143-0
Ashish Gupta, Inderpal Singh Mumick, V. S. Subrahmanian: Maintaining Views Incrementally. SIGMOD Conference 1993: 157-166 BibTeX
Amy J. Lee, Andreas Koeller, Anisoara Nica, Elke A. Rundensteiner: Data Warehouse Evolution: Trade-Offs between Quality and Cost of Query Rewritings. ICDE 1999: 255 BibTeX
Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava: Answering Queries Using Views. PODS 1995: 95-104 BibTeX
Anisoara Nica, Amy J. Lee, Elke A. Rundensteiner: The CVS Algorithm for View Synchronization in Evolvable Large-Scale Information Systems. EDBT 1998: 359-373 BibTeX
Dallan Quass, Jennifer Widom: On-Line Warehouse View Maintenance. SIGMOD Conference 1997: 393-404 BibTeX
Elke A. Rundensteiner, Amy J. Lee, Anisoara Nica: On Preserving Views in Evolving Environments. KRDB 1997: 13.1-13.11 BibTeX
Carel A. van den Berg, Martin L. Kersten: An Analysis of a Dynamic Query Optimization Scheme for Different Data Distributions. Query Processing for Advanced Database Systems, Dagstuhl 1991: 449-472 BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
DOLAP 1998 Proceedings, ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:07:20 2009