Incremental View Maintenance for Deductive Graph Databases Using Generalized Discrimination Networks
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 match...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2016-12-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1612.01641v1 |
| _version_ | 1818538445456277504 |
|---|---|
| author | Thomas Beyhl Holger Giese |
| author_facet | Thomas Beyhl Holger Giese |
| author_sort | Thomas Beyhl |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-11T21:29:04Z |
| format | Article |
| id | doaj.art-04094916dca04390a43fea530679be00 |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-12-11T21:29:04Z |
| publishDate | 2016-12-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-04094916dca04390a43fea530679be002022-12-22T00:50:13ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802016-12-01231Proc. GaM 2016577110.4204/EPTCS.231.5:1Incremental View Maintenance for Deductive Graph Databases Using Generalized Discrimination NetworksThomas Beyhl0Holger Giese1 Hasso Plattner Institute at the University of Potsdam 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.http://arxiv.org/pdf/1612.01641v1 |
| spellingShingle | Thomas Beyhl Holger Giese Incremental View Maintenance for Deductive Graph Databases Using Generalized Discrimination Networks Electronic Proceedings in Theoretical Computer Science |
| title | Incremental View Maintenance for Deductive Graph Databases Using Generalized Discrimination Networks |
| title_full | Incremental View Maintenance for Deductive Graph Databases Using Generalized Discrimination Networks |
| title_fullStr | Incremental View Maintenance for Deductive Graph Databases Using Generalized Discrimination Networks |
| title_full_unstemmed | Incremental View Maintenance for Deductive Graph Databases Using Generalized Discrimination Networks |
| title_short | Incremental View Maintenance for Deductive Graph Databases Using Generalized Discrimination Networks |
| title_sort | incremental view maintenance for deductive graph databases using generalized discrimination networks |
| url | http://arxiv.org/pdf/1612.01641v1 |
| work_keys_str_mv | AT thomasbeyhl incrementalviewmaintenancefordeductivegraphdatabasesusinggeneralizeddiscriminationnetworks AT holgergiese incrementalviewmaintenancefordeductivegraphdatabasesusinggeneralizeddiscriminationnetworks |