Paper Info
Title
Utilizing IDs to Accelerate Incremental View Maintenance
Abstract
Prior Incremental View Maintenance (IVM) algorithms specify the view tuples that need to be modified by computing diff sets, which we call tuple-based diffs since a diff set contains one diff tuple for each to-be-modified view tuple. idIVM assumes the base tables have keys and performs IVM by computing ID-based diff sets that compactly identify the to-be-modified tuples through their IDs. This work makes the following contributions: (a) An ID-based IVM system for a large subset of SQL that includes the algebraic operators selection, join, grouping and aggregation, generalized projection involving functions, antisemijoin (and therefore negation/difference) and union. The system is based on a modular approach, allowing one to extend the supported language simply by adding one algebraic operator at-a-time, along with equations describing how ID-based changes are propagated through the operator. (b) An efficient algorithm that creates an IVM plan for a given view in four passes that are polynomial in the size of the view expression. (c) A formal analysis comparing the ID-based IVM algorithm to prior IVM approaches and analytically showing when one outperforms the other. (d) An experimental comparison of the ID-based IVM algorithm to prior IVM algorithms showing the superiority of the former in common use cases.
Year
DOI
Venue
2015
10.1145/2723372.2750546
ACM SIGMOD Conference
Keywords
Field
DocType
materialized views,incremental view maintenance
SQL,Data mining,Algebraic number,Use case,Polynomial,Tuple,Computer science,Operator (computer programming),Modular design,Materialized view,Database
Conference
Citations 
PageRank 
References 
3
0.37
25
Authors
4
Name
Order
Citations
PageRank
Yannis Katsis1153.12
Kian Win Ong219911.72
Yannis Papakonstantinou35657837.56
Kevin Keliang Zhao4244.10