A Path Algebra for Multi-Relational Graphs by Marko A. Rodriguez, Peter Neubauer.
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 algebra, 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.
Only four (4) pages but it is heavy sledding from the first paragraph to the last. Still, if you want a peek at what fine minds, Rodriguez and Neubauer, think about when they see Neo4j and its future, this will be worth the effort.