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

@inproceedings{DBLP:conf/dolap/KoellerRH98,
  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, http://doi.acm.org/10.1145/294260.294273},
  crossref  = {DBLP:conf/dolap/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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(n³) 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 ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An2-4 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

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

Online Edition

Citation Page

References

[1]: Divyakant Agrawal, Amr El Abbadi, Ambuj K. Singh, Tolga Yurek: Efficient View Maintenance at Data Warehouses. SIGMOD Conference 1997: 417-427
[2]: 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
[3]: Ashish Gupta, Inderpal Singh Mumick, V. S. Subrahmanian: Maintaining Views Incrementally. SIGMOD Conference 1993: 157-166
[4]: ...
[5]: 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
[6]: ...
[7]: Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava: Answering Queries Using Views. PODS 1995: 95-104
[8]: Anisoara Nica, Amy J. Lee, Elke A. Rundensteiner: The CVS Algorithm for View Synchronization in Evolvable Large-Scale Information Systems. EDBT 1998: 359-373
[9]: Dallan Quass, Jennifer Widom: On-Line Warehouse View Maintenance. SIGMOD Conference 1997: 393-404
[10]: Elke A. Rundensteiner, Amy J. Lee, Anisoara Nica: On Preserving Views in Evolving Environments. KRDB 1997: 13.1-13.11
[11]: 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