Synonyms
Incremental Maintenance of Views with Aggregates
Definition
A view on a database is defined by a query over the database. When the database is updated, the value of the view (namely the answer to the query) will likely change. The computation of the new answer to the query using the old answer is called incremental query computation or incremental view maintenance. Incremental computation is typically performed by identifying the part in the old answer that need to be removed, and the part in the new answer that need to be added. Incremental computation is desirable when it is much more efficient than a re-computation of the query. Efficiency can be measured by computation time, storage space, or query language desirability/availability, etc. Incremental computation algorithms could use auxiliary relations (in addition to the query answer), which also need to be incrementally computed.
Two query languages can be involved for the incremental query computation problem. One is...
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Recommended Reading
Dong G, Libkin L, Su J, Wong L. Maintaining transitive closure of graphs in SQL. Int J Inf Technol. 1999;5(1):46–78.
Dong G, Pang C. Maintaining transitive closure in first-order after node-set and edge-set deletions. Inf Process Lett. 1997;62(3):193–9.
Dong G, Su J. Incremental and decremental evaluation of transitive closure by first-order queries. Inf Comput. 1995;120(1):101–6.
Dong G, Su J. Arity bounds in first-order incremental evaluation and definition of polynomial time database queries. J Comput Syst Sci. 1998;57(3):289–308. Preliminary version in the proceedings of the ACM symposium on principles of database systems, 1995.
Dong G, Su J. Incremental maintenance of recursive views using relational calculus/SQL. ACM SIGMOD Rec. 2000;29(1):44–51.
Dong G, Su J, Topor R. Nonrecursive incremental evaluation of datalog queries. Ann Math Artif Intell. 1995;14(2–4):187–223.
Dong G, Topor R. Incremental evaluation of datalog queries. In: Proceedings of the 4th International Conference on Database Theory; 1992. p. 282–96.
Griffin T, Libkin L, Trickey H. An improved algorithm for the incremental recomputation of active relational expressions. IEEE Trans Knowl Data Eng. 1997;9(3):508–11.
Gupta A, Mumick IS. Materialized views: techniques, implementations, and applications. Mass: MIT; 1999.
Immerman N. Descriptive complexity. New York: Springer; 1998.
Libkin L, Wong L. On the power of incremental evaluation in SQL-like languages. In: Proceedings of the 7th International Workshop on Database Programming Languages; 1999.p. 17–30.
Pang C, Dong G, Kotagiri R. Incremental maintenance of shortest distance and transitive closure in first-order logic and SQL. ACM Trans Database Syst. 2005;30(3):698–721.
Patnaik S, Immerman N. Dyn-FO: a parallel dynamic complexity class. J Comput Syst Sci. 1997;55(2):199–209. Preliminary version in the proceedings of the ACM symposium on principles of database systems, 1994.
Qian X, Wiederhold G. Incremental recomputation of active relational expressions. IEEE Trans Knowl Data Eng. 1991;3(3):337–41.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Section Editor information
Rights and permissions
Copyright information
© 2018 Springer Science+Business Media, LLC, part of Springer Nature
About this entry
Cite this entry
Dong, G., Su, J. (2018). Incremental Computation of Queries. In: Liu, L., Özsu, M.T. (eds) Encyclopedia of Database Systems. Springer, New York, NY. https://doi.org/10.1007/978-1-4614-8265-9_1351
Download citation
DOI: https://doi.org/10.1007/978-1-4614-8265-9_1351
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4614-8266-6
Online ISBN: 978-1-4614-8265-9
eBook Packages: Computer ScienceReference Module Computer Science and Engineering