Abstract
We propose an algorithm called CReaM to incrementally maintain materialized aggregate views with user-defined aggregates in response to changes to the database tables from which the view is derived. CReaM is optimal and guarantees the self-maintainability of aggregate views that are defined over a single database table. For aggregate views that are defined over multiple database tables and do not contain all of the non-aggregated attributes in the database tables, CReaM speeds up the time taken to update a view as compared to prior view maintenance techniques. The speed up in the time taken to update a materialized view with n tuples is either \(\tfrac{n}{\log n}\) or logn depending on whether the materialized view is indexed or not. For other types of aggregate views, CReaM updates the view in no more time than that is required by prior view maintenance techniques to update the view.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Blakeley, J.A., Coburn, N., Larson, P.A.: Updating derived relations: Detecting irrelevant and autonomously computable updates. ACM TODS (1989)
Blakeley, J.A., Larson, P.A., Tompa, F.W.: Efficiently updating materialized views. SIGMOD (1986)
Buneman, O.P., Clemons, E.K.: Efficiently monitoring relational databases. ACM TODS (1979)
Ceri, S., Widom, J.: Deriving production rules for incremental view maintenance. VLDB (1991)
Colby, L.S., Kawaguchi, A., Lieuwen, D.F., Mumick, I.S., Ross, K.A.: Supporting multiple view maintenance policies. SIGMOD (1997)
Dong, G., Topor, R.W.: Incremental evaluation of datalog queries. ICDT (1992)
Fredman, M.L.: A lower bound on the complexity of orthogonal range queries. J. ACM (1981)
Fredman, M.L.: The complexity of maintaining an array and computing its partial sums. J. ACM (1982)
Gallaire, H., Minker, J., Nicolas, J.M.: Logic and databases: A deductive approach. ACM Computing Surveys (1984)
Griffin, T., Libkin, L.: Incremental maintenance of views with duplicates. SIGMOD (1995)
Gupta, A., Jagadish, H.V., Mumick, I.S.: Data integration using self-maintainable views. EDBT (1996)
Gupta, A., Jagadish, H.V., Mumick, I.S.: Maintenance and self-maintenance of outerjoin views. NGITS (1997)
Gupta, A., Mumick, I.S.: Maintenance of materialized views: Problems, techniques, and applications. In: Materialized Views (1999)
Gupta, A., Mumick, I.S., Subrahmanian, V.S.: Maintaining views incrementally. SIGMOD (1993)
Gupta, H., Mumick, I.S.: Incremental maintenance of aggregate and outerjoin expressions. Information Systems (2006)
Harrison, J.V., Dietrich, S.W.: Maintenance of materialized views in a deductive database: An update propagation approach. In: Workshop on Deductive Databases, JICSLP (1992)
Huyn, N.: Efficient view self-maintenance. Views (1996)
Kuchenhoff, V.: On the efficient computation of the difference between consecutive database states. DOOD (1991)
Mohania, M., Kambayashi, Y.: Making aggregate views self-maintainable. ACM TKDE 32 (1999)
Mohapatra, A., Genesereth, M.: Reformulating aggregate queries using views. SARA (2013)
Mumick, I.S., Quass, D., Mumick, B.S.: Maintenance of data cubes and summary tables in a warehouse. SIGMOD (1997)
Nicolas, J.M.: Yazdanian: An outline of bdgen: A deductive dbms. Information Processing (1983)
Orman, L.V.: Differential relational calculus for integrity maintenance. ACM TKDE (1998)
Palpanas, T., Sidle, R., Cochrane, R., Pirahesh, H.: Incremental maintenance for non-distributive aggregate functions. VLDB (2002)
Păatraşcu, M., Demaine, E.D.: Tight bounds for the partial-sums problem. SODA (2004)
Qian, X., Wiederhold, G.: Incremental recomputation of active relational expressions. ACM TKDE (1991)
Quass, D.: Maintenance expressions for views with aggregation. Views (1996)
Quass, D., Mumick, I.S.: Optimizing the refresh of materialized view. Technical Report (1997)
Ross, K.A., Sagiv, Y.: Monotonic aggregation in deductive databases. PODS (1992)
Shmueli, O., Itai, A.: Maintenance of views. SIGMOD (1984)
Stonebraker, M.: Implementation of integrity constraints and views by query modification. SIGMOD (1975)
Tompa, F.W., Blakeley, J.A.: Maintaining materialized views without accessing base data. Information Systems (1988)
Ullman, J.D.: Principles of Database and Knowledge-Base Systems: Volume II (1989)
Wolfson, O., Dewan, H.M., Stolfo, S.J., Yemini, Y.: Incremental evaluation of rules and its relationship to parallelism. SIGMOD (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Mohapatra, A., Genesereth, M. (2014). Incremental Maintenance of Aggregate Views. In: Beierle, C., Meghini, C. (eds) Foundations of Information and Knowledge Systems. FoIKS 2014. Lecture Notes in Computer Science, vol 8367. Springer, Cham. https://doi.org/10.1007/978-3-319-04939-7_20
Download citation
DOI: https://doi.org/10.1007/978-3-319-04939-7_20
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-04938-0
Online ISBN: 978-3-319-04939-7
eBook Packages: Computer ScienceComputer Science (R0)