On the operationalization of graph queries with generalized discrimination networks

Thomas Beyhl; Dominique Blouin; Holger Giese; Leen Lambers

doi:10.1007/978-3-319-40530-8_11

On the operationalization of graph queries with generalized discrimination networks

Thomas Beyhl
, Dominique Blouin
, Holger Giese
, Leen Lambers

Hasso Plattner Institute

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

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

Original language	English
Title of host publication	Graph Transformation - 9th International Conference, ICGT 2016 in Memory of Hartmut Ehrig, Held as Part of STAF 2016, Proceedings
Editors	Mark Minas, Rachid Echahed
Publisher	Springer Verlag
Pages	170-186
Number of pages	17
ISBN (Print)	9783319405292
DOIs	https://doi.org/10.1007/978-3-319-40530-8_11
Publication status	Published - 1 Jan 2016
Externally published	Yes
Event	9th International Conference on Graph Transformation, ICGT 2016 in Memory of Hartmut Ehrig held as part of Conference on Software Technologies: Applications and Foundations, STAF 2016 - Vienna, Austria Duration: 5 Jul 2016 → 6 Jul 2016

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9761
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	9th International Conference on Graph Transformation, ICGT 2016 in Memory of Hartmut Ehrig held as part of Conference on Software Technologies: Applications and Foundations, STAF 2016
Country/Territory	Austria
City	Vienna
Period	5/07/16 → 6/07/16

Access to Document

10.1007/978-3-319-40530-8_11

Cite this

Beyhl, T., Blouin, D., Giese, H., & Lambers, L. (2016). On the operationalization of graph queries with generalized discrimination networks. In M. Minas, & R. Echahed (Eds.), Graph Transformation - 9th International Conference, ICGT 2016 in Memory of Hartmut Ehrig, Held as Part of STAF 2016, Proceedings (pp. 170-186). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9761). Springer Verlag. https://doi.org/10.1007/978-3-319-40530-8_11

Beyhl, Thomas ; Blouin, Dominique ; Giese, Holger et al. / On the operationalization of graph queries with generalized discrimination networks. Graph Transformation - 9th International Conference, ICGT 2016 in Memory of Hartmut Ehrig, Held as Part of STAF 2016, Proceedings. editor / Mark Minas ; Rachid Echahed. Springer Verlag, 2016. pp. 170-186 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{8e6d34eedfbc45d187b144a9973d0ec7,

title = "On the operationalization of graph queries with generalized discrimination networks",

abstract = "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 queries. 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.",

author = "Thomas Beyhl and Dominique Blouin and Holger Giese and Leen Lambers",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 9th International Conference on Graph Transformation, ICGT 2016 in Memory of Hartmut Ehrig held as part of Conference on Software Technologies: Applications and Foundations, STAF 2016 ; Conference date: 05-07-2016 Through 06-07-2016",

year = "2016",

month = jan,

day = "1",

doi = "10.1007/978-3-319-40530-8\_11",

language = "English",

isbn = "9783319405292",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "170--186",

editor = "Mark Minas and Rachid Echahed",

booktitle = "Graph Transformation - 9th International Conference, ICGT 2016 in Memory of Hartmut Ehrig, Held as Part of STAF 2016, Proceedings",

}

Beyhl, T, Blouin, D, Giese, H & Lambers, L 2016, On the operationalization of graph queries with generalized discrimination networks. in M Minas & R Echahed (eds), Graph Transformation - 9th International Conference, ICGT 2016 in Memory of Hartmut Ehrig, Held as Part of STAF 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9761, Springer Verlag, pp. 170-186, 9th International Conference on Graph Transformation, ICGT 2016 in Memory of Hartmut Ehrig held as part of Conference on Software Technologies: Applications and Foundations, STAF 2016, Vienna, Austria, 5/07/16. https://doi.org/10.1007/978-3-319-40530-8_11

On the operationalization of graph queries with generalized discrimination networks. / Beyhl, Thomas; Blouin, Dominique; Giese, Holger et al.
Graph Transformation - 9th International Conference, ICGT 2016 in Memory of Hartmut Ehrig, Held as Part of STAF 2016, Proceedings. ed. / Mark Minas; Rachid Echahed. Springer Verlag, 2016. p. 170-186 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9761).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On the operationalization of graph queries with generalized discrimination networks

AU - Beyhl, Thomas

AU - Blouin, Dominique

AU - Giese, Holger

AU - Lambers, Leen

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2016.

PY - 2016/1/1

Y1 - 2016/1/1

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

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

UR - https://www.scopus.com/pages/publications/84977533225

U2 - 10.1007/978-3-319-40530-8_11

DO - 10.1007/978-3-319-40530-8_11

M3 - Conference contribution

AN - SCOPUS:84977533225

SN - 9783319405292

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 170

EP - 186

BT - Graph Transformation - 9th International Conference, ICGT 2016 in Memory of Hartmut Ehrig, Held as Part of STAF 2016, Proceedings

A2 - Minas, Mark

A2 - Echahed, Rachid

PB - Springer Verlag

T2 - 9th International Conference on Graph Transformation, ICGT 2016 in Memory of Hartmut Ehrig held as part of Conference on Software Technologies: Applications and Foundations, STAF 2016

Y2 - 5 July 2016 through 6 July 2016

ER -

Beyhl T, Blouin D, Giese H, Lambers L. On the operationalization of graph queries with generalized discrimination networks. In Minas M, Echahed R, editors, Graph Transformation - 9th International Conference, ICGT 2016 in Memory of Hartmut Ehrig, Held as Part of STAF 2016, Proceedings. Springer Verlag. 2016. p. 170-186. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-40530-8_11

On the operationalization of graph queries with generalized discrimination networks

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this