Efficient and scalable graph view maintenance for deductive graph databases based on generalized discrimination networks

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.