Graph navigational languages define binary relations in terms of pair of nodes in a graph subject to the existence of a path satisfying a certain regular expression. The goal of this paper is to give a novel characterization of navigational languages in terms of the structure of the graph embracing the results of a query. We define novel graph-based query evaluation semantics and efficient algorithms able to represent and capture intermediate nodes/edges linking pairs of nodes in the answer. We enhance the language of Nested Regular Expressions (NREs) with our machineries, thus defining the language of Structural NREs (sNREs).

Structural Characterization of Graph navigational Langauges

2017

Abstract

Graph navigational languages define binary relations in terms of pair of nodes in a graph subject to the existence of a path satisfying a certain regular expression. The goal of this paper is to give a novel characterization of navigational languages in terms of the structure of the graph embracing the results of a query. We define novel graph-based query evaluation semantics and efficient algorithms able to represent and capture intermediate nodes/edges linking pairs of nodes in the answer. We enhance the language of Nested Regular Expressions (NREs) with our machineries, thus defining the language of Structural NREs (sNREs).
2017
Istituto di Calcolo e Reti ad Alte Prestazioni - ICAR
Graph databases
Expressiveness
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.14243/332467
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact