Quiver and RDF

[bblfish]

I left a note 5 years ago on @runarorama's great blog post A Comonad of Graph decompositions pointing to work in RDF. I was just starting to learn category theory as part of a PhD at the Uni of Southampton at the time, so I did not have time to look into how this could tie in with banana-rdf. Verizon stopped the quiver project soon thereafter for some reason, but the code is still being developed on getnelson's repo.

I will have time to spend a good month on banana-rdf as part of the Solid-Control EU project. So this is something I could look at.

Graph

Banana-rdf has it's own implementation of RDF Graphs called Plantain, that uses HashMaps to build a graph (see Graph.scala). That is good for forward traversal of the graph, but not good for backward traversal, which is often very useful, such as when one is looking for all nodes of a type, by searching backwards along rdf:type.

Looking at the Quiver code, the principal declarations are:

case class Graph[N,A,B](rep: GraphRep[N,A,B]) { ... }
type GraphRep[N,A,B] = Map[N, GrContext[N,A,B]]
case class GrContext[N,A,B](inAdj: Map[N, Set[B]],
                            label: A,
                            outAdj: Map[N, Set[B]])

We see that this is very close to Plantain's Graph

case class Graph[S, P, O](spo: Map[S, Map[P, Vector[O]]], size: Int) { ...}

the main difference being that Quiver links in and out from a node.

Context and PointedGraph

This generic type of the graphs allows decomposition into contexts, which gives the comonadic view on the graph as located on a node (see also @ekneumann ideas on how comonads could fit the web). These contexts also appear in banana-rdf has with PointedGraphs and their wrapper methods such as / for search.

A potential problem with banana-rdf's PointedGraph, is that the pointer can be located on a non-existing node in the graph. The Quiver Context answers that problem

case class Context[N,A,B](inAdj: Adj[N,B], vertex: N, label: A, outAdj: Adj[N,B])
type Adj[N,B] = Vector[(B, N)]

Comonads

Quiver's Contexts are also what allows a comonadic view of the graph, as explained in Runar's blog post.
This is enabled by abstracting over the types of nodes, allowing the duplicate natural transformation to turn a graph into a graph with graphs at the nodes, as shown by this excellent diagram
(or labels of nodes, I am not quite sure what the reason for this difference in roles yet, and how this ties to RDF). Except that it could be used for the quads, perhaps...

Other Notes

Q: I am not quite sure how graph decomposition works for non-connected graphs, which are possible in RDF
A: the GraphRep would just index on that context node. There is no requirement that graphs be connected.

Q: How useful would the comonadic Graph be for solving problems in RDF?
Set of Answers: @ekneumann wrote up a list of ideas on how comonads can be applied to the web referring to Runar's post. But it would be useful to start off with some simple examples, perhaps searching for an Access Control pattern in a Graph, to see what emerges.