TY - THES A1 - Beyhl, Thomas T1 - A framework for incremental view graph maintenance T1 - Ein Framework für die inkrementelle Wartung von Sichten auf Graphen N2 - Nowadays, graph data models are employed, when relationships between entities have to be stored and are in the scope of queries. For each entity, this graph data model locally stores relationships to adjacent entities. Users employ graph queries to query and modify these entities and relationships. These graph queries employ graph patterns to lookup all subgraphs in the graph data that satisfy certain graph structures. These subgraphs are called graph pattern matches. However, this graph pattern matching is NP-complete for subgraph isomorphism. Thus, graph queries can suffer a long response time, when the number of entities and relationships in the graph data or the graph patterns increases. One possibility to improve the graph query performance is to employ graph views that keep ready graph pattern matches for complex graph queries for later retrieval. However, these graph views must be maintained by means of an incremental graph pattern matching to keep them consistent with the graph data from which they are derived, when the graph data changes. This maintenance adds subgraphs that satisfy a graph pattern to the graph views and removes subgraphs that do not satisfy a graph pattern anymore from the graph views. Current approaches for incremental graph pattern matching employ Rete networks. Rete networks are discrimination networks that enumerate and maintain all graph pattern matches of certain graph queries by employing a network of condition tests, which implement partial graph patterns that together constitute the overall graph query. Each condition test stores all subgraphs that satisfy the partial graph pattern. Thus, Rete networks suffer high memory consumptions, because they store a large number of partial graph pattern matches. But, especially these partial graph pattern matches enable Rete networks to update the stored graph pattern matches efficiently, because the network maintenance exploits the already stored partial graph pattern matches to find new graph pattern matches. However, other kinds of discrimination networks exist that can perform better in time and space than Rete networks. Currently, these other kinds of networks are not used for incremental graph pattern matching. This thesis employs generalized discrimination networks for incremental graph pattern matching. These discrimination networks permit a generalized network structure of condition tests to enable users to steer the trade-off between memory consumption and execution time for the incremental graph pattern matching. For that purpose, this thesis contributes a modeling language for the effective definition of generalized discrimination networks. Furthermore, this thesis contributes an efficient and scalable incremental maintenance algorithm, which updates the (partial) graph pattern matches that are stored by each condition test. Moreover, this thesis provides a modeling evaluation, which shows that the proposed modeling language enables the effective modeling of generalized discrimination networks. Furthermore, this thesis provides a performance evaluation, which shows that a) the incremental maintenance algorithm scales, when the graph data becomes large, and b) the generalized discrimination network structures can outperform Rete network structures in time and space at the same time for incremental graph pattern matching. N2 - Heutzutage werden Graphdatenmodelle verwendet um Beziehungen zwischen Entitäten zu speichern und diese Beziehungen später abzufragen. Jede Entität im Graphdatenmodell speichert lokal die Beziehungen zu anderen verknüpften Entitäten. Benutzer stellen Suchanfragen um diese Entitäten und Beziehungen abzufragen und zu modifizieren. Dafür machen Suchanfragen Gebrauch von Graphmustern um alle Teilgraphen in den Graphdaten zu finden, die über bestimmte Graphstrukturen verfügen. Diese Teilgraphen werden Graphmusterübereinstimmung (Match) genannt. Allerdings ist diese Suche nach Matches NP-vollständig für Teilgraphisomorphie. Daher können Suchanfragen einer langen Antwortzeit unterliegen, wenn die Anzahl von Entitäten und Beziehungen in den Graphdaten oder -mustern ansteigt. Eine Möglichkeit die Antwortzeiten von Suchanfragen zu verbessern ist Matches für komplexe Suchanfragen in sogenannten Sichten über die Graphdaten für spätere Suchanfragen bereitzuhalten. Allerdings müssen diese Sichten mittels einer inkrementellen Suche nach Matches gewartete werden um sie konsistent zu den sich ändernden Graphdaten zu halten. Diese Wartung ergänzt Teilgraphen, die Graphmuster erfüllen, in den Sichten und entfernt Teilgraphen, die Graphmuster nicht mehr erfüllen, aus den Sichten. Aktuelle Ansätze für die inkrementelle Suche nach Matches verwenden Rete Netzwerke. Rete Netzwerke sind sogenannte Discrimination Networks, die alle Matches für bestimmte Suchanfragen aufzählen und warten, indem sie ein Netzwerk aus einzelnen Teilgraphmustern anwenden, die zusammen eine vollständige Suchanfrage ergeben. Das Netzwerk speichert für jedes Teilgraphmuster welche Teilgraphen das Teilgraphmuster erfüllen. Daher haben Rete Netzwerke einen hohen Speicherverbrauch, da sie alle Zwischenergebnisse speichern müssen. Jedoch sind es gerade diese gespeicherten Zwischenergebnisse, die es dem Rete Netzwerk ermöglichen die gespeicherten Zwischenergebnisse effizient zu warten, da diese Zwischenergebnisse für das Auffinden neuer Matches ausgenutzt werden. Allerdings existieren andere Arten von Discrimination Networks, die hinsichtlich Speicher- und Zeitverbrauch effizienter sind, aber derzeit nicht für die inkrementelle Suche nach Matches verwendet werden. Diese Doktorarbeit wendet eine verallgemeinerte Art von Discrimination Networks an. Diese verallgemeinerte Art ermöglicht es die Balance zwischen Speicher- und Zeitverbrauch für die inkrementelle Suche nach Matches zu steuern. Dafür stellt diese Arbeit eine Modellierungssprache vor, die es ermöglicht verallgemeinerte Arten von Discrimination Networks effektiv zu spezifizieren. Darauf aufbauend stellt diese Arbeit einen inkrementellen Algorithmus vor, der die gespeicherten Matches effizient und skalierbar wartet. Abschließend stellt diese Arbeit eine Evaluierung vor, die aufzeigt dass die Modellierungssprache eine effektive Spezifikation von verallgemeinerten Discrimination Networks erlaubt. Außerdem zeigt die Evaluierung, dass a) der inkrementelle Wartungsalgorithmus für große Graphdaten skaliert und b) die Netzwerkstrukturen von verallgemeinerten Discrimination Networks im Vergleich zu den Netzwerkstrukturen von Rete Netzwerken im Speicher- und Zeitverbrauch für die inkrementelle Suche nach Matches effizienter sein können. KW - incremental graph pattern matching KW - discrimination networks KW - Rete networks KW - Gator networks KW - model-driven software engineering KW - inkrementelle Graphmustersuche KW - Discrimination Networks KW - Rete Netzwerk KW - Gator Netzwerk KW - modellgetriebene Softwareentwicklung Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-405929 ER - 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 - TY - BOOK A1 - Beyhl, Thomas A1 - Giese, Holger T1 - Efficient and scalable graph view maintenance for deductive graph databases based on generalized discrimination networks N2 - Graph databases provide a natural way of storing and querying graph data. In contrast to relational databases, queries over graph databases enable to refer directly to the graph structure of such graph data. For example, graph pattern matching can be employed to formulate queries over graph data. However, as for relational databases running complex queries can be very time-consuming and ruin the interactivity with the database. One possible approach to deal with this performance issue is to employ database views that consist of pre-computed answers to common and often stated queries. But to ensure that database views yield consistent query results in comparison with the data from which they are derived, these database views must be updated before queries make use of these database views. Such a maintenance of database views must be performed efficiently, otherwise the effort to create and maintain views may not pay off in comparison to processing the queries directly on the data from which the database views are derived. At the time of writing, graph databases do not support database views and are limited to graph indexes that index nodes and edges of the graph data for fast query evaluation, but do not enable to maintain pre-computed answers of complex queries over graph data. Moreover, the maintenance of database views in graph databases becomes even more challenging when negation and recursion have to be supported as in deductive relational databases. In this technical report, we present an approach for the efficient and scalable incremental graph view maintenance for deductive graph databases. The main concept of our approach is a generalized discrimination network that enables to model nested graph conditions including negative application conditions and recursion, which specify the content of graph views derived from graph data stored by graph databases. The discrimination network enables to automatically derive generic maintenance rules using graph transformations for maintaining graph views in case the graph data from which the graph views are derived change. We evaluate our approach in terms of a case study using multiple data sets derived from open source projects. N2 - Graphdatenbanken bieten natürliche Möglichkeiten Graphdaten zu speichern und abzufragen. Im Gegensatz zu relationalen Datenbanken ermöglichen Graphdatenbanken Anfragen, die direkt auf der Graphstruktur der Daten arbeiten. Zum Beispiel können Graphmuster zur Formulierung von Anfragen an die Graphdatenbanken verwendet werden. Allerdings können wie für relationale Datenbanken komplexe Anfragen sehr zeitaufwendig sein und interaktive Anfrageszenarien mit der Datenbank verhindern. Ein möglicher Ansatz mit diesem Geschwindigkeitsproblem umzugehen, ist das Vorberechnen von Antworten für komplexe und häufig gestellt Suchanfragen in Form von sogenannten Datenbanksichten. Dabei muss sichergestellt sein, dass Anfragen, die mit Hilfe von Datenbanksichten beantwortet werden, zu jeder Zeit die gleichen Suchergebnisse zurückliefern als wenn sie ohne Datenbanksichten beantwortet werden, sodass Datenbanksichten gewartet werden müssen bevor Suchanfragen mit Hilfe dieser Datenbanksichten beantwortet werden. Eine solche Wartung von Datenbanksichten muss effizient erfolgen, anderenfalls kann sich der Aufwand für die Erzeugung und Wartung der Datenbanksichten nicht auszahlen. Zum Zeitpunkt der Anfertigung dieses technischen Berichts, ist keine Graphdatenbank bekannt, die solche Datenbanksichten unterstützt. Lediglich Indizes werden durch Graphdatenbanken unterstützt, die es ermöglichen Knoten und Kanten eines Graphen für die schnelle Anfragenbeantwortung zu indizieren, aber ermöglichen es nicht vorberechnete Antworten auf Suchanfragen zu warten. Die Unterstützung von Datenbanksichten durch Graphdatenbanken wird zusätzlich erschwert wenn Negation und Rekursion unterstützt werden sollen wie bei relationalen deduktiven Datenbanken. In diesen technischen Bericht beschreiben wir einen effizienten und skalierenden Ansatz zur inkrementellen Wartung von Dankenbanksichten für deduktive Graphdatenbanken. Das Hauptkonzept des Ansatzes ist ein sogenanntes verallgemeinertes Discrimination Network, dass es ermöglicht geschachtelte Graph Conditions inklusive Negation und Rekursion zu modellieren, die es ermöglichen den Inhalt von Datenbanksichten für Graphdatenbanken in Form von Graphmustern zu spezifizieren. Das Discrimination Network erlaubt die Ableitung von Regeln für die Wartung der Datenbanksichten wenn die Graphdaten von denen die Datenbanksichten abgeleitet wurden modifiziert werden. Wir evaluieren den Ansatz in Form einer Fallstudie und mehreren Graphdatensätzen, die aus Open Source Projekten abgeleitet wurden. T3 - Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam - 99 KW - incremental graph pattern matching KW - graph databases KW - view maintenance KW - inkrementelles Graph Pattern Matching KW - Graphdatenbanken KW - Wartung von Graphdatenbanksichten Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-79535 SN - 978-3-86956-339-8 SN - 1613-5652 SN - 2191-1665 IS - 99 PB - Universitätsverlag Potsdam CY - Potsdam ER -