A Model for Evaluating and Comparing Materialized View Maintenance Algorithms
No Thumbnail Available
Date
1999-11-01T00:00:00Z
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Providing integrated access to information from multiple, distributed, autonomous data sources has received much attention from both the research communities and industries in recent years. Having a materialized view is a straightforward solution to provide fast access to such information, but maintaining such a view to reflect the changes at the data sources is not an easy task. Numerous algorithms have been proposed to handle the materialized view maintenance. The problems faced in this view maintenance include the presence of interfering updates, misordering of messages and the loss of these messages. In this paper, we provide a framework for comparing the merits of each of these approaches. We classify our criteria under four main categories in terms of the environment that they function in, the correctness of the algorithms, their efficiency, and the application requirements that these algorithms provide. The environment criteria includes the number of data sources the algorithm supports, and the nature of the compensation process. The correctness criteria looks at how accurate is the identification of interfering updates, and the proper working of the view maintenance process when messages are misordered or lost during their transmission through the network. Efficiency consideration includes the number of base relations accessed per sub-query of the incremental computation, the sequential or parallel handling of incremental computation both within the same update and between different updates, the use of partial self-maintenance in the incremental computation and how is modification handled. Application requirement involves the flexibility of the view definition, degree of consistency provided, and whether is quiescent state of the system necessary before the view can be refreshed. Based on these criteria, we evaluate and compare the existing algorithms in detail.