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üssten diese Sichten mittels einer inkrementellen Suche nach Matches gewartet 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 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. Die 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 die Arbeit einen inkrementellen Algorithmus vor, der die gespeicherten Matches effizient und skalierbar wartet. Abschließend stellt die 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.
