• search hit 1 of 1
Back to Result List

On the operationalization of graph queries with generalized discrimination networks

  • 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.
  • 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.

Download full text files

  • tbhpi106.pdfeng
    (2282KB)

    SHA-1:643821990b12fa79ce700ee457a32d14d2ed8900

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics
Metadaten
Author:Thomas Beyhl, Dominique Blouin, Holger GieseORCiDGND, Leen LambersORCiDGND
URN:urn:nbn:de:kobv:517-opus4-96279
ISBN:978-3-86956-372-5
ISSN:1613-5652 (print)
ISSN:2191-1665 (online)
Series (Serial Number):Technische Berichte des Hasso-Plattner-Instituts für Digital Engineering an der Universität Potsdam (106)
Publisher:Universitätsverlag Potsdam
Place of publication:Potsdam
Document Type:Monograph/Edited Volume
Language:English
Year of first Publication:2016
Year of Completion:2016
Publishing Institution:Universität Potsdam
Publishing Institution:Universitätsverlag Potsdam
Release Date:2016/09/20
Tag:Discrimination Networks; Graph-basierte Suche; Inkrementelle Graphmustersuche; Nested Graph Conditions
discrimination networks; graph queries; incremental graph pattern matching; nested graph conditions
Issue:106
Pagenumber:33
RVK - Regensburg Classification:ST 230
Organizational units:An-Institute / Hasso-Plattner-Institut für Digital Engineering gGmbH
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Publication Way:Universitätsverlag Potsdam
Licence (German):License LogoKeine Nutzungslizenz vergeben - es gilt das deutsche Urheberrecht
Notes extern:
In Printform erschienen im Universitätsverlag Potsdam:

On the operationalization of graph queries with generalized discrimination networks / Thomas Beyhl, Dominique Blouin, Holger Giese, Leen Lambers. – Potsdam: Universitätsverlag Potsdam, 2016. – 33 S. : graph. Darst.
(Technische Berichte des Hasso-Plattner-Instituts für Softwaresystemtechnik an der Universität Potsdam ; 106)
ISSN (print) 1613-5652
ISSN (online) 2191-1665
ISBN 978-3-86956-372-5
--> bestellen