Muhammad Idris
Stijn Vansummeren
ABSTRACT
Modern 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 trade-off between the space needed to maintain the materialized results and the time used to process updates. In this paper, we show that the full materialization of results is a barrier for more general optimization strategies. In particular, we present a new approach for evaluating queries under updates. Instead of the materialization of results, we require a data structure that allows: (1) linear time maintenance under updates, (2) constant-delay enumeration of the output, (3) constant-time lookups in the output, while (4) using only linear space in the size of the database. We call such a structure a Dynamic Constant-delay Linear Representation (DCLR) for the query. We show that DYN, a dynamic version of the Yannakakis algorithm, yields DCLRs for the class of free-connex acyclic CQs. We show that this is optimal in the sense that no DCLR can exist for CQs that are not free-connex acyclic. Moreover, we identify a sub-class of queries for which DYN features constant-time update per tuple and show that this class is maximal. Finally, using the TPC-H and TPC-DS benchmarks, we experimentally compare DYN and a higher-order IVM (HIVM) engine. Our approach is not only more efficient in terms of memory consumption (as expected), but is also consistently faster in processing updates.
- S. Abiteboul, R. Hull, and V. Vianu. Foundations of databases. Addison-Wesley, 1995. Google Scholar
Digital Library
- M. Abo Khamis, H. Q. Ngo, and A. Rudra. FAQ: Questions asked frequently. In Proc. of PODS, pages 13--28, 2016. Google ScholarDigital Library
- M. E. Adiba and B. G. Lindsay. Database snapshots. In Proc. of VLDB 1980, pages 86--91, 1980. Google ScholarDigital Library
- S. M. Aji and R. J. McEliece. The generalized distributive law. IEEE Trans. Information Theory, 46(2):325--343, 2006. Google ScholarDigital Library
- G. Bagan, A. Durand, and E. Grandjean. On acyclic conjunctive queries and constant delay enumeration. In Proc. of CSL, pages 208--222, 2007. Google ScholarDigital Library
- N. Bakibayev, T. Kočiský, D. Olteanu, and J. Závodný. Aggregation and ordering in factorised databases. Proc. of VLDB, 6(14):1990--2001, 2013. Google ScholarDigital Library
- C. Berkholz, J. Keppeler, and N. Schweikardt. Answering conjunctive queries under updates. In Proc. of PODS, 2017. To appear. Google ScholarDigital Library
- J. A. Blakeley, N. Coburn, and P.-V. Larson. Updating derived relations: Detecting irrelevant and autonomously computable updates. ACM TODS, (3):369--400, 1989. Google ScholarDigital Library
- J. A. Blakeley, P.-A. Larson, and F. W. Tompa. Efficiently updating materialized views. In Proc. of SIGMOD, pages 61--71, 1986. Google ScholarDigital Library
- J. Brault-Baron. De la pertinence de l'énumération: complexité en logiques. PhD thesis, Université de Caen, 2013.Google Scholar
- O. P. Buneman and E. K. Clemons. Efficiently monitoring relational databases. ACM TODS, (3):368--382, 1979. Google ScholarDigital Library
- S. Ceri and J. Widom. Deriving production rules for incremental view maintenance. In Proc. of VLDB, pages 577--589, 1991. Google ScholarDigital Library
- R. Chirkova and J. Yang. Materialized Views. Now Publishers Inc., Hanover, MA, USA, 2012. Google ScholarDigital Library
- T. Cormen. Introduction to Algorithms, 3rd Edition:. MIT Press, 2009. Google ScholarDigital Library
- G. Cugola and A. Margara. Processing flows of information: From data stream to complex event processing. ACM CSUR, 44(3):15:1--15:62, 2012. Google ScholarDigital Library
- N. Dalvi and D. Suciu. The dichotomy of probabilistic inference for unions of conjunctive queries. J. ACM, 59(6):30:1--30:87, 2013. Google ScholarDigital Library
- R. Fink and D. Olteanu. Dichotomies for queries with negation in probabilistic databases. ACM TODS, 41(1):4:1--4:47, 2016. Google ScholarDigital Library
- G. Gottlob, M. Grohe, n. Musliu, M. Samer, and F. Scarcello. Hypertree decompositions: Structure, algorithms, and applications. In Proc. of WG, pages 1--15, 2005. Google ScholarDigital Library
- G. Gottlob, N. Leone, and F. Scarcello. Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width. J. Comput. Syst. Sci., 66(4):775--808, 2003. Google ScholarDigital Library
- A. Gupta, I. S. Mumick, and V. S. Subrahmanian. Maintaining views incrementally. In Proc. of SIGMOD, pages 157--166, 1993. Google ScholarDigital Library
- H. Gupta and I. S. Mumick. Incremental maintenance of aggregate and outerjoin expressions. Information Systems, (6):435--464, 2006. Google ScholarDigital Library
- M. Henzinger, S. Krinninger, D. Nanongkai, and T. Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proc. of STOC, pages 21--30, 2015. Google ScholarDigital Library
- M. R. Joglekar, R. Puttagunta, and C. Ré. Ajar: Aggregations and joins over annotated relations. In Proc. of PODS, pages 91--106, 2016. Google ScholarDigital Library
- A. Kawaguchi, D. Lieuwen, I. Mumick, and K. Ross. Implementing incremental view maintenance in nested data models. In Proc. of DBPL, pages 202--221, 1997. Google ScholarDigital Library
- C. Koch. Incremental query evaluation in a ring of databases. In Proc. of PODS, pages 87--98, 2010. Google ScholarDigital Library
- C. Koch, Y. Ahmad, O. Kennedy, M. Nikolic, A. Nötzli, D. Lupei, and A. Shaikhha. Dbtoaster: higher-order delta processing for dynamic, frequently fresh views. VLDB Journal, pages 253--278, 2014. Google ScholarDigital Library
- P. Koutris and D. Suciu. Parallel evaluation of conjunctive queries. In Proc. of PODS, pages 223--234, 2011. Google ScholarDigital Library
- I. S. Mumick, D. Quass, and B. S. Mumick. Maintenance of data cubes and summary tables in a warehouse. SIGMOD Records, 26(2):100--111, 1997. Google ScholarDigital Library
- H. Q. Ngo, C. Ré, and A. Rudra. Skew strikes back: New developments in the theory of join algorithms. SIGMOD Records, 42(4):5--16, 2014. Google ScholarDigital Library
- M. Nikolic, M. Dashti, and C. Koch. How to win a hot dog eating contest: Distributed incremental view maintenance with batch updates. In Proc.of SIGMOD, pages 511--526, 2016. Google ScholarDigital Library
- D. Olteanu and J. Závodný. Size bounds for factorised representations of query results. ACM TODS, 40(1):2:1--2:44, 2015. Google ScholarDigital Library
- C. H. Papadimitriou. Computational complexity. In Encyclopedia of Computer Science, pages 260--265. 2003.Google ScholarDigital Library
- X. Qian and G. Wiederhold. Incremental recomputation of active relational expressions. IEEE Trans. on Knowl. and Data Eng., 3(3):337--341, 1991. Google ScholarDigital Library
- K. A. Ross, D. Srivastava, and S. Sudarshan. Materialized view maintenance and integrity constraint checking: Trading space for time. In Proc. of SIGMOD, pages 447--458, 1996. Google ScholarDigital Library
- N. Roussopoulos. Materialized views and data warehouses. SIGMOD Records, 27(1):21--26, 1998. Google ScholarDigital Library
- M. Schleich, D. Olteanu, and R. Ciucanu. Learning linear regression models over factorized joins. In Proc. of SIGMOD, pages 3--18, 2016. Google ScholarDigital Library
- L. Segoufin. Constant delay enumeration for conjunctive queries. SIGMOD Record, 44(1):10--17, 2015. Google ScholarDigital Library
- M. Y. Vardi. The complexity of relational query languages (extended abstract). In Proc. of STOC, pages 137--146, 1982. Google ScholarDigital Library
- M. Yannakakis. Algorithms for acyclic database schemes. In Proc. of VLDB, pages 82--94, 1981. Google ScholarDigital Library
Index Terms
- The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates
Recommendations
Maintaining Acyclic Foreign-Key Joins under Updates
SIGMOD '20: Proceedings of the 2020 ACM SIGMOD International Conference on Management of DataA large number of analytical queries (e.g., all the 22 queries in the TPC-H benchmark) are based on acyclic foreign-key joins. In this paper, we study the problem of incrementally maintaining the query results of these joins under updates, i.e., ...
Incremental Techniques for Large-Scale Dynamic Query Processing
CIKM '18: Proceedings of the 27th ACM International Conference on Information and Knowledge ManagementMany applications from various disciplines are now required to analyze fast evolving big data in real time. Various approaches for incremental processing of queries have been proposed over the years. Traditional approaches rely on updating the results ...
Differential evaluation of continual queries
ICDCS '96: Proceedings of the 16th International Conference on Distributed Computing Systems (ICDCS '96)We define continual queries as a useful tool for monitoring of updated information. Continual queries are standing queries that monitor the source data and notify the users whenever new data matches the query. In addition to periodic refresh, continual ...
Comments