Answering Graph Pattern Queries using Compact Materialized Views

Michael Lan, Xiaoying Wu, Dimitri Theodoratos

Research output: Contribution to journalConference articlepeer-review

1 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)51-60
Number of pages10
JournalCEUR Workshop Proceedings
StatePublished - 2022
Event24th International Workshop on Design, Optimization, Languages and Analytical Processing of Big Data, DOLAP 2022 - Edinburgh, United Kingdom
Duration: Mar 29 2022 → …

All Science Journal Classification (ASJC) codes

  • General Computer Science


Dive into the research topics of 'Answering Graph Pattern Queries using Compact Materialized Views'. Together they form a unique fingerprint.

Cite this