Thomas Beyhl, Dominique Blouin, Holger Giese, Leen Lambers

On the operationalization of graph queries with generalized discrimination networks

ISBN: 978-3-86956-372-5
33 pages, Monographie
Release year 2017

Series: Technische Berichte des Hasso-Plattner-Instituts für Softwaresystemtechnik an der Universität Potsdam , 106

0,00 

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