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 Möglichkeiten Graphdaten zu speichern und abzufragen. Im Gegensatz zu relationalen Datenbanken ermöglichen Graphdatenbanken Anfragen, die direkt auf der Graphstruktur der Daten arbeiten. Zum Beispiel können Graphmuster zur Formulierung von Anfragen an die Graphdatenbanken verwendet werden.
Allerdings können wie für relationale Datenbanken komplexe Anfragen sehr zeitaufwendig sein und interaktive Anfrageszenarien mit der Datenbank verhindern. Ein möglicher Ansatz mit diesem Geschwindigkeitsproblem umzugehen, ist das Vorberechnen von Antworten für komplexe und hä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 zurückliefern als wenn sie ohne Datenbanksichten beantwortet werden, sodass Datenbanksichten gewartet werden müssen bevor Suchanfragen mit Hilfe dieser Datenbanksichten beantwortet werden. Eine solche Wartung von Datenbanksichten muss effizient erfolgen, anderenfalls kann sich der Aufwand für die Erzeugung und Wartung der Datenbanksichten nicht auszahlen.
Zum Zeitpunkt der Anfertigung dieses technischen Berichts, ist keine Graphdatenbank bekannt, die solche Datenbanksichten unterstützt. Lediglich Indizes werden durch Graphdatenbanken unterstützt, die es ermöglichen Knoten und Kanten eines Graphen für die schnelle Anfragenbeantwortung zu indizieren, aber ermöglichen es nicht vorberechnete Antworten auf Suchanfragen zu warten. Die Unterstützung von Datenbanksichten durch Graphdatenbanken wird zusätzlich erschwert wenn Negation und Rekursion unterstützt werden sollen wie bei relationalen deduktiven Datenbanken.
In diesen technischen Bericht beschreiben wir einen effizienten und skalierenden Ansatz zur inkrementellen Wartung von Dankenbanksichten für deduktive Graphdatenbanken. Das Hauptkonzept des Ansatzes ist ein sogenanntes verallgemeinertes Discrimination Network, dass es ermöglicht geschachtelte Graph Conditions inklusive Negation und Rekursion zu modellieren, die es ermöglichen den Inhalt von Datenbanksichten für Graphdatenbanken in Form von Graphmustern zu spezifizieren. Das Discrimination Network erlaubt die Ableitung von Regeln fü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 Graphdatensä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  -