Abstract
The incremental view maintenance problem deals with the efficient updating of materialized views in response to updates to base relations. This paper considers the problem in a distributed database environment, with communication cost minimization as the primary objective. The views considered are defined based on the relational join operation. The approach is to use “yes”/“no” tags as auxiliary data on tuples in the base relations to indicate whether the tuples participate in joins. These tags will help avoid sending irrelevant data over the network and thus reduce the communication cost. Two basic view maintenance algorithms are proposed using the tags. In addition to reducing communication costs, an important feature of these two basic algorithms is that they derive the “exact change” to views without looking at the old views. This feature allows us to maintain certain aggregates on views without actually materializing the views themselves; this feature is useful in applications such as active databases where many conditions or constraints must be tested whenever updates occur, since a condition is true exactly when some corresponding view has nonzero number of tuples. The paper then combines the use of tags with the counting algorithm to derive a tagged counting algorithm that further reduces the communication cost. The paper illustrates the algorithms by examples and studies their performance via a statistical analysis. The illustrating examples and the performance analysis show that, under uniform distribution with reasonable join participation rates, the use of tags significantly improves the efficiency of view maintenance over similar algorithms without tags. The performance analysis also identifies the situations where a particular algorithm is superior to others. The use of tags for memoing values of subexpressions in a view definition is also explored in the paper.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J. A. Blakeley, P.-A. Larson, and F. W. Tompa. Efficiently updating materialized views. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 61-71, 1986.
S. Ceri and G. Pelagatti. Distributed Databases: Principles and Systems. McGraw-Hill Book Co, 1986.
D. Chao, G. Diehr, and A. N. Saharia. Maintaining join-based remote snapshots using relevant logging. In Proc. of the Workshop on Materialized Views: Techniques and Applications (in cooperation with ACM SIGMOD), June 1996.
G. Dong and J. Su. Incremental and decremental evaluation of transitive closure queries by first-order queries (extended abstract). In Proc. 16th Australian Computer Science Conference, 1993. Full version appears in [5].
G. Dong and J. Su. Incremental and decremental evaluation of transitive closure by first-order queries. Information and Computation, 120(1):101-106, July 1995. Preliminary version in [4].
G. Dong, J. Su, and R. Topor. Nonrecursive incremental evaluation of Datalog queries. Annals of Mathematics and Artificial Intelligence, 14(2-4):187-223, 1995.
G. Dong and R. Topor. Incremental evaluation of Datalog queries. In Proc. Int'l Conference on Database Theory, pages 282-296, Berlin, Germany, October 1992. Full version appears as part of [6].
T. Griffin and L. Libkin. Incremental maintenance of views with duplicates. In Proc. ACM SIGMOD Int. Conf. on Management of Data, 1995.
A. Gupta, H.V. Jagadish, and I. S. Mumick. Data integration using self-maintainable views. In Proc. First Int. Conf. on Extending Database Technology, 1996.
A. Gupta, I. S. Mumick, and V. S. Subrahmanian. Maintaining views incrementally. In Proc. ACMSIGMOD Int. Conf. on Management of Data, pages 157-166, 1993.
A. Gupta and I. S. Mumick. Maintenance of materialized views: problems, techniques, and applications. IEEE Data Engineering Bulletin, Special Issue on Materialized Views and Warehousing, 18(2), 1995.
R. Hull and G. Zhou. A framework for supporting data integration using the materialized and virtual approaches. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 481-492, 1996.
H. F. Korth and A. Silberschatz. Database System Concepts. McGraw-Hill, 1991.
P. Mishra and M.H. Eich. Join processing in relational databases. ACM Computing Surveys, 24(1):63-113, 1992.
M.T. Özsu and P. Valduriez. Principles of Distributed Database Systems.Prentice-Hall, 1991.
X. Qian and G. Wiederhold. Incremental recomputation of active relational expressions. IEEE Trans. on Knowledge and Data Engineering, 3(3):337-41, 1991.
K. A. Ross, D. Srivastava, and S. Sudarshan. Materialized view maintenance and integrity constraint checking: Trading space for time. In Proc. ACM SIGMOD Int. Conf. on Management of Data, page to appear, 1996.
N. Roussopoulos. The incremental access method of ViewCache: Concept, algorithm, and cost analysis. ACM Trans. on Database Systems, 16(3):535-563, 1991.
A. Segev and W. Fang. Currency based updates to distributed materialized views. In Proceedings of the IEEE International Conference on Data Engineering, 1990.
A. Segev and J. Park. Maintaining materialized views in distributed databases. In Proceedings of the IEEE International Conference on Data Engineering, 1989.
O. Wolfson, H. M. Dewan, S. J. Stolfo, and Y. Yemini. Incremental evaluation of rules and its relationship to parallelism. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 78-87, 1991.
Y. Zhuge, H. Garcia-Molina, J. Hammer, and J. Widom. View maintenance in a warehousing environment. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 316-27, 1995.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Bailey, J., Dong, G., Mohania, M. et al. Incremental View Maintenance By Base Relation Tagging in Distributed Databases. Distributed and Parallel Databases 6, 287–309 (1998). https://doi.org/10.1023/A:1008683116381
Issue Date:
DOI: https://doi.org/10.1023/A:1008683116381