Incremental View Maintenance for Deductive Graph Databases Using Generalized Discrimination Networks

Thomas Beyhl
(Hasso Plattner Institute at the University of Potsdam)
Holger Giese
(Hasso Plattner Institute at the University of Potsdam)

Nowadays, graph databases are employed when relationships between entities are in the scope of database queries to avoid performance-critical join operations of relational databases. Graph queries are used to query and modify graphs stored in graph databases. Graph queries employ graph pattern matching that is NP-complete for subgraph isomorphism. Graph database views can be employed that keep ready answers in terms of precalculated graph pattern matches for often stated and complex graph queries to increase query performance. However, such graph database views must be kept consistent with the graphs stored in the graph database.

In this paper, we describe how to use incremental graph pattern matching as technique for maintaining graph database views. We present an incremental maintenance algorithm for graph database views, which works for imperatively and declaratively specified graph queries. The evaluation shows that our maintenance algorithm scales when the number of nodes and edges stored in the graph database increases. Furthermore, our evaluation shows that our approach can outperform existing approaches for the incremental maintenance of graph query results.

In Alexander Heußner, Aleks Kissinger and Anton Wijs: Proceedings Second Graphs as Models Workshop (GaM 2016), Eindhoven, The Netherlands, April 2-3, 2016, Electronic Proceedings in Theoretical Computer Science 231, pp. 57–71.
Published: 4th December 2016.

ArXived at: https://dx.doi.org/10.4204/EPTCS.231.5 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org