TY - JOUR A1 - Beyhl, Thomas A1 - Giese, Holger T1 - Incremental View Maintenance for Deductive Graph Databases Using Generalized Discrimination Networks JF - Electronic proceedings in theoretical computer science N2 - 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. Y1 - 2016 U6 - https://doi.org/10.4204/EPTCS.231.5 SN - 2075-2180 VL - 10 SP - 57 EP - 71 PB - Open Publishing Association CY - Sydney ER - TY - BOOK A1 - Beyhl, Thomas A1 - Blouin, Dominique A1 - Giese, Holger A1 - Lambers, Leen T1 - On the operationalization of graph queries with generalized discrimination networks N2 - Graph queries have lately gained increased interest due to application areas such as social networks, biological networks, or model queries. For the relational database case the relational algebra and generalized discrimination networks have been studied to find appropriate decompositions into subqueries and ordering of these subqueries for query evaluation or incremental updates of query results. For graph database queries however there is no formal underpinning yet that allows us to find such suitable operationalizations. Consequently, we suggest a simple operational concept for the decomposition of arbitrary complex queries into simpler subqueries and the ordering of these subqueries in form of generalized discrimination networks for graph queries inspired by the relational case. The approach employs graph transformation rules for the nodes of the network and thus we can employ the underlying theory. We further show that the proposed generalized discrimination networks have the same expressive power as nested graph conditions. N2 - Graph-basierte Suchanfragen erfahren in jüngster Zeit ein zunehmendes Interesse durch Anwendungsdomänen wie zum Beispiel Soziale Netzwerke, biologische Netzwerke und Softwaremodelle. Für relationale Datenbanken wurden die relationale Algebra und sogenannte generalisierte Discrimination Networks bereits studiert um Suchanfragen angemessen in kleinere Suchanfragen für die inkrementelle Auswertung zu zerlegen und zu ordnen. Allerdings gibt es für Graphdatenbanken derzeit keine formale Grundlage, die es erlaubt solche Zerlegungen zu finden. Daher schlagen wir ein Konzept für die Zerlegung und Ordnung von komplexen Suchanfragen vor. Das Konzept basiert auf generalisierten Discrimination Networks, die aus relationalen Datenbanken bekannt sind. Der Ansatz verwendet Graphtransformationsregeln für Knoten in diesen Netzwerken, sodass die Theorie von Graphen und Graphtransformationen angewendet werden kann. Darüber hinaus zeigen wir auf, dass diese Discrimination Networks die gleiche Ausdrucksstärke besitzen wie Nested Graph Conditions. T3 - Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam - 106 KW - graph queries KW - discrimination networks KW - incremental graph pattern matching KW - nested graph conditions KW - Graph-basierte Suche KW - Discrimination Networks KW - Inkrementelle Graphmustersuche KW - Nested Graph Conditions Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-96279 SN - 978-3-86956-372-5 SN - 1613-5652 SN - 2191-1665 IS - 106 PB - Universitätsverlag Potsdam CY - Potsdam ER -