A multi-relational graph maintains two or more relations over a vertex set. This article defines an algebra for traversing such graphs that is based on an n-ary relational alge- bra, a concatenative single-relational path algebra, and a tensor- based multi-relational algebra. The presented algebra provides a monoid, automata, and formal language theoretic foundation for the construction of a multi-relational graph traversal engine.

The second half of the dicussion would cover Gremlin. Gremlin is a graph traversal language. Gremlin works over those graph databases/frameworks that implement the Blueprints property graph data model. Examples include TinkerGraph, Neo4j, OrientDB, DEX, InfiniteGraph, Rexster, and Sail RDF Stores. Gremlin is a style of graph traversal that can be natively used in various JVM languages. Currently, Gremlin provides native support for Java, Groovy, and Scala. Except where otherwise stated, the documentation herein is respective of the Groovy implementation (minor syntactic tweaks are required to map the ideas over to other JVM implementations).