TY - JOUR
T1 - Answering Graph Pattern Queries using Compact Materialized Views
AU - Lan, Michael
AU - Wu, Xiaoying
AU - Theodoratos, Dimitri
N1 - Funding Information:
*The research of this author was supported by the National Natural Science Foundation of China under Grant No. 61872276.
Publisher Copyright:
© Copyright 2022 for this paper by its author(s). Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0)
PY - 2022
Y1 - 2022
N2 - We address the problem of evaluating graph pattern queries involving reachability (edge-to-path mapping) and direct (edge-to-edge mapping) relationships under homomorphisms on data graphs using materialized graph pattern views. We propose an original approach for view materialization which materializes views as summary graphs, an approach that records, in a compact way, all the homomorphisms of the view to the data graph. In this context, we characterize view usability in terms of query edge coverage and provide necessary and sufficient conditions for answering queries using views. We design algorithms for deciding whether a query can be answered using a set of views, for generating the summary graph of a query from the view materializations, and for producing a minimal view set capable of answering a query. Our experimental evaluation demonstrates that our approach outperforms, by several orders of magnitude, a state-of-the-art approach which does not use materialized views, and substantially improves upon its scalability.
AB - We address the problem of evaluating graph pattern queries involving reachability (edge-to-path mapping) and direct (edge-to-edge mapping) relationships under homomorphisms on data graphs using materialized graph pattern views. We propose an original approach for view materialization which materializes views as summary graphs, an approach that records, in a compact way, all the homomorphisms of the view to the data graph. In this context, we characterize view usability in terms of query edge coverage and provide necessary and sufficient conditions for answering queries using views. We design algorithms for deciding whether a query can be answered using a set of views, for generating the summary graph of a query from the view materializations, and for producing a minimal view set capable of answering a query. Our experimental evaluation demonstrates that our approach outperforms, by several orders of magnitude, a state-of-the-art approach which does not use materialized views, and substantially improves upon its scalability.
UR - http://www.scopus.com/inward/record.url?scp=85129141579&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85129141579&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:85129141579
SN - 1613-0073
VL - 3130
SP - 51
EP - 60
JO - CEUR Workshop Proceedings
JF - CEUR Workshop Proceedings
T2 - 24th International Workshop on Design, Optimization, Languages and Analytical Processing of Big Data, DOLAP 2022
Y2 - 29 March 2022
ER -