Semantics for querying paths in graph databases: No-repeated-node or no-repeated-edge ?

Abstract

Patterns for walks in graphs usually include regular expressions, that may result in loops, thus producing infinite solutions. To overcome this issue, practical query languages bound result sets to en- sure finiteness. On this paper we compare two bounding methods: Edges are visited at most once; nodes are visited at most once. We show that despite these methods produce languages with different expressiveness, there is a duality, in the sense that the queries in one can be evaluated using the machinery used to evaluate the other.