Integrating the rewriting and ranking phases of view synchronization
Andreas Koeller, Elke Angelika Rundensteiner, Nabil I. Hachem · 1998
Material&d views (data warehouses) are becoming increasingly important in the context of distributed modem environments such as the World Wide Web.Information sources (I%) 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 ss 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 shortestpath problem in graphs, which can be solved with O(n3) complexity using the Bellman-Ford algorithm.