Parsing graphs. applying parser combinators to graph traversals

Abstract

Connected data such as social networks or business process interactions are frequently mod-eled as graphs, and increasingly often, stored in graph databases. In contrast to relational data-bases where SQL is the proven query language, there is no established counterpart for graph databases. One way to explore and extract data from a graph database is to specify the struc-ture of paths (partial traversals) through the graph. We show how such traversals can be ex-pressed by combining graph navigation primitives with familiar grammar constructions such as sequencing, choice and repetition -- essentially applying the idea of parser combinators to graph traversals. The result is trails [6], a Scala combinator library that provides an implementation for the neo4j graph database [7] and for the generic graph API blueprints [8].