Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/33404
Title: | The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates | Authors: | Idris, Muhammad Ugarte, Martín VANSUMMEREN, Stijn |
Issue Date: | 2017 | Publisher: | Association for Computing Machinery | Source: | Proceedings of the 2017 ACM International Conference on Management of Data, Association for Computing Machinery, p. 1259 -1274 | 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. | Keywords: | Incremental View Maintenance;Dynamic query processing;Acyclic joins | Document URI: | http://hdl.handle.net/1942/33404 | ISBN: | 9781450341974 | DOI: | 10.1145/3035918.3064027 | ISI #: | WOS:000452550000084 | Category: | C1 | Type: | Proceedings Paper |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
main.pdf Restricted Access | Published version | 618.47 kB | Adobe PDF | View/Open Request a copy |
WEB OF SCIENCETM
Citations
37
checked on Oct 19, 2024
Page view(s)
26
checked on Sep 5, 2022
Download(s)
4
checked on Sep 5, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.