Christoph Koch
ABSTRACT
This paper approaches the incremental view maintenance problem from an algebraic perspective. We construct the algebraic structure of a ring of databases and use it as the foundation of the design of a query calculus that allows to express powerful aggregate queries. The query calculus inherits key properties of the ring, such as having a normal form of polynomials and being closed under computing inverses and delta queries. The k-th delta of a polynomial query of degree k without nesting is purely a function of the update, not of the database. This gives rise to a method of eliminating expensive query operators such as joins from programs that perform incremental view maintenance. The main result is that, for non-nested queries, each individual aggregate value can be incrementally maintained using a constant amount of work. This is not possible for nonincremental evaluation.
- S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995. Google Scholar
Digital Library
- U. A. Acar, G. E. Blelloch, and R. Harper. Adaptive functional programming. ACM Trans. Program. Lang. Syst., 28(6):990--1034, 2006. Google ScholarDigital Library
- Y. Ahmad and C. Koch. DBToaster: A SQL compiler for high-performance delta processing in main-memory databases. PVLDB, 2(2):1566--1569, 2009. Google ScholarDigital Library
- D. A. M. Barrington, N. Immerman, and H. Straubing. On uniformity within NC1. J. Comput. Syst. Sci., 41(3):274--306, 1990. Google ScholarDigital Library
- J. A. Blakeley, P.-Å. Larson, and F. W. Tompa. Efficiently updating materialized views. In Proc. SIGMOD Conference, pages 61--71, 1986. Google ScholarDigital Library
- R. P. Brent. The parallel evaluation of general arithmetic expressions. J. ACM, 21:201--206, 1974. Google ScholarDigital Library
- P. Buneman and E. K. Clemons. Efficient monitoring relational databases. ACM Trans. Database Syst., 4(3):368--382, 1979. Google ScholarDigital Library
- S. Ceri and J. Widom. Deriving production rules for incremental view maintenance. In Proc. VLDB, pages 577--589, 1991. Google ScholarDigital Library
- L. S. Colby, T. Griffin, L. Libkin, I. S. Mumick, and H. Trickey. Algorithms for deferred view maintenance. In Proc. SIGMOD, pages 469--480, 1996. Google ScholarDigital Library
- A. J. Demers, T. W. Reps, and T. Teitelbaum. Incremental evaluation for attribute grammars with application to syntax-directed editors. In Proc. POPL, pages 105--116, 1981. Google ScholarDigital Library
- G. Dong and J. Su. Incremental and decremental evaluation of transitive closure by first-order queries. Inf. Comput., 120(1):101--106, 1995. Google ScholarDigital Library
- D. S. Dummit and R. M. Foote. Abstract Algebra. John Wiley & Sons, 3rd edition, 2004.Google Scholar
- S. Ghandeharizadeh, R. Hull, and D. Jacobs. Heraclitus: Elevating deltas to be first-class citizens in a database programming language. ACM Transactions on Database Systems, 21(3):370--426, Sept. 1996. Google ScholarDigital Library
- T. J. Green, Z. Ives, and V. Tannen. Reconcilable differences. In Proc. ICDT, St. Petersburg, Russia, 2009. Google ScholarDigital Library
- T. J. Green, G. Karvounarakis, and V. Tannen. Provenance semirings. In Proc. PODS, pages 31--40, 2007. Google ScholarDigital Library
- T. Griffin and L. Libkin. Incremental maintenance of views with duplicates. In Proc. SIGMOD, 1995. Google ScholarDigital Library
- A. Gupta, D. Katiyar, and I. S. Mumick. Counting solutions to the view maintenance problem. In Proc. Workshop on Deductive Databases, JICSLP, 1992.Google Scholar
- A. Gupta, I. S. Mumick, and V. S. Subrahmanian. Maintaining views incrementally. In Proc. SIGMOD Conference, pages 157--166, 1993. Google ScholarDigital Library
- L. Henkin, J. Monk, and A. Tarski. Cylindric Algebras, Part I. North-Holland, 1971.Google Scholar
- W. Hesse. The dynamic complexity of transitive closure is in DynTC0. Theor. Comput. Sci., 296(3):473--485, 2003. Google ScholarDigital Library
- W. Hesse and N. Immerman. Complete problems for dynamic complexity classes. In Proc. LICS, 2002. Google ScholarDigital Library
- D. S. Johnson. A catalog of complexity classes. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume 1, chapter 2, pages 67--161. Elsevier Science Publishers B.V., 1990. Google ScholarDigital Library
- Y. Kotidis and N. Roussopoulos. A case for dynamic view management. ACM Transactions on Database Systems, 26(4):388--423, 2001. Google ScholarDigital Library
- S. Lang. Algebra. Graduate Texts in Mathematics. Springer-Verlag, revised 3rd edition, 2002.Google Scholar
- L. Libkin and L. Wong. Some properties of query languages for bags. In Proc. DBPL, pages 97--114, 1993. Google ScholarDigital Library
- L. Libkin and L. Wong. Incremental recomputation of recursive queries with nested sets and aggregate functions. In Proc. DBPL, pages 222--238, 1997. Google ScholarDigital Library
- L. Libkin and L. Wong. On the power of incremental evaluation in SQL-like languages. In Proc. DBPL, pages 17--30, 1999. Google ScholarDigital Library
- P. B. Miltersen, S. Subramanian, J. S. Vitter, and R. Tamassia. Complexity models for incremental computation. Theor. Comput. Sci., 130(1):203--236, 1994. Google ScholarDigital Library
- S. Patnaik and N. Immerman. Dyn-FO: A parallel, dynamic complexity class. J. Comput. Syst. Sci., 55(2):199--209, 1997. Google ScholarDigital Library
- W. Pugh and T. Teitelbaum. Incremental computation via function caching. In Proc. POPL, 1989. Google ScholarDigital Library
- A. Rajaraman, Y. Sagiv, and J. D. Ullman. Answering queries using templates with binding patterns. In Proc. PODS, pages 105--112, 1995. Google ScholarDigital Library
- N. Roussopoulos. An incremental access method for viewcache: Concept, algorithms, and cost analysis. ACM Transactions on Database Systems, 16(3):535--563, 1991. Google ScholarDigital Library
- O. Shmueli and A. Itai. Maintenance of views. In B. Yormark, editor, Proc. SIGMOD, pages 240--255. ACM Press, 1984. Google ScholarDigital Library
- R. Smolenski. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Proc. STOC, pages 77--82, 1987. Google ScholarDigital Library
- M. Y. Vardi. The complexity of relational query languages. In Proc. STOC, pages 137--146, May 1982. Google ScholarDigital Library
- W. P. Yan and P.-Å. Larson. Eager aggregation and lazy aggregation. In Proc. VLDB, pages 345--357, 1995. Google ScholarDigital Library
Index Terms
- Incremental query evaluation in a ring of databases
Recommendations
Incremental View Maintenance For Collection Programming
PODS '16: Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database SystemsIn the context of incremental view maintenance (IVM), delta query derivation is an essential technique for speeding up the processing of large, dynamic datasets. The goal is to generate delta queries that, given a small change in the input, can update ...
The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates
SIGMOD '17: Proceedings of the 2017 ACM International Conference on Management of DataModern computing tasks such as real-time analytics require refresh of query results under high update rates. Incremental View Maintenance (IVM) approaches this problem by materializing results in order to avoid recomputation. IVM naturally induces a ...
Thrifty Query Execution via Incrementability
SIGMOD '20: Proceedings of the 2020 ACM SIGMOD International Conference on Management of DataMany applications schedule queries before all data is ready. To return fast query results, database systems can eagerly process existing data and incrementally incorporate new data into prior intermediate results, which often relies on incremental view ...
Comments