Ontology, graphs and turtles - Part II - Unladen swallow

In a previous article, I introduced the notion of ontology and knowledge graph.

Let’s go deeper into the concept and apply some technology to create an actual graph structure and eventually play with it.

At the end of this article, we well have parsed a triplestore in turtle format and created a graph structure in Go (based on gonum’s interface)

The triplestore

As explained in the last post, our knowledge database is a triple store. As a matter of example, I will rely on the ontology exposed by schema.org.

Schema.org is a collaborative, community activity with a mission to create, maintain, and promote schemas for structured data on the Internet, on web pages, in email messages, and beyond. Founded by Google, Microsoft, Yahoo and Yandex, Schema.org vocabularies are developed by an open community process […]. You can grab the complete ontology with this command:

The complete definition is available in turtle format and can be downloaded easily:

1curl -O -s https://schema.org/version/latest/schemaorg-current-http.ttl

Parsing the store

Basic explanation of the parser

To parse the store, I am using the package gon3 from Andrei Sambra. Even though there is no license attached, Andrei allowed me to use it and to modify it for non-profit code.

I forked the repo to make some minor adjustments I needed for my experiments.

The entry point of the package is a Parser structure. Its purpose is to read a byte stream (io.Reader) and turn it into a functional structure called Graph. The Graph structure within the package is not representing all the edges. Still, it consists of an array of Triples (aka rdf graph):

1// An RDF graph is a set of RDF triples
2type Graph struct {
3	triples []*Triple
4	uri     *IRI
5}

A Triple is a structure holding three Term. One is the subject, one is a predicate, and the last one is the object.

1// see http://www.w3.org/TR/rdf11-concepts/#dfn-rdf-triple
2type Triple struct {
3	Subject, Predicate, Object Term
4}

In the previous article, we saw that a term in RDF can be expressed in different types. As of today, the way to represent generic types in Go is to use interfaces. Therefore, a Term has an interface based definition:

1type Term interface {
2	String() string
3	Equals(Term) bool
4	RawValue() string
5}

Two important objects are implementing the Term interface:

IRI
Literal

Generate the RDF Graph

If we glue all the concepts together we have the possibility to create a basic structure:

1import "github.com/owulveryck/gon3" // Other imports omited for brevity
2
3func main() {
4        baseURI := "https://example.org/foo"
5        parser := gon3.NewParser(baseURI)
6        gr, _ := parser.Parse(os.Stdin) // Error handling is omited for brevity
7        fmt.Printf("graph contains %v triples", len(gr.Triples()))
8}

Then we can test the plumbing with the file we downloaded from schema.org previously:

1> cat schemaorg-current-http.ttl| go run main.go
2graph contains 15323 triples

We can check that roughly the number of triple matches what’s expected by counting the rdf separators from the file:

1> cat schemaorg-current-http.ttl | egrep -v '^@|^$' | egrep -c ' \.$| \;$|\,$'
215329

The numbers are not identical but alike (the grep command does not evaluate the literal and some punctuation may be wrongly counted)

Generating a Graph

Understanding the graph structure

We have an “RDF” graph in memory; sadly, this structure is not a directed graph. I mean that it is not de facto possible to navigate from nodes to nodes or to identify the edges.

To create a graph, the best option in Go is to rely on the abstraction created by gonum

In Gonum a graph is an interface that manages two objects fulfilling the Node and Edge such as:

1type Graph interface {
2    Node(id int64) Node
3    Nodes() Nodes
4    From(id int64) Nodes
5    HasEdgeBetween(xid, yid int64) bool
6    Edge(uid, vid int64) Edge
7}

1type Node interface {
2    ID() int64
3}

1type Edge interface {
2    From() Node
3    To() Node
4    ReversedEdge() Edge
5}

Note: all comments have been removed for brevity. The full definition is available here

Once the graph objects are fulfilling those interfaces, it becomes possible to use all the graph algorithms that have been implemented by the gonum team. Please go to this link if you wish to learn more about the capabilities: pkg.go.dev/gonum.org/v1/gonum/graph#section-directories

Our graph structure

We will create a top-level structure that will act as a receiver for our graph. For the graph itself, we rely on the simple.DirectedGraph implementation provided by the gonum’s project.

So we have:

1type Graph struct {
2    *simple.DirectedGraph
3}

Then we will create a function to create and fill our graph from our rdfGraph.

1func NewGraph(rdfGraph *gon3.Graph) *Graph {
2   	g := simple.NewDirectedGraph()
3    // ... fill the graph
4    return &Graph{
5        DirectedGraph: g,
6    }
7}

Structure of the graph

Remember that the rdf graph contains an array of triples. Each triple is a term.

The object of a predicate is the subject of another triple. For example:

1schema:subject1 schema:predicate schema:object1 .
2schema:object1 schema:otherPredicate schema:object2 .

Would lead to the following graph:

This indicates a choice I’ve made: I want to produce a graph where its node corresponds to a subject declared inside the triplestore. Therefore, in the example, object2 is not a node because it is not defined as a subject to a sentence. It is relatively easy to change this behavior and reference other nodes, but let’s keep that apart.

Declaration of the node

The node object declaration is pretty straightforward. A node is a structure holding:

an id
a subject as seen before
and a map of predicates and objects associated with the predicate.

1type MyNode struct {
2    id              int64
3    Subject         rdf.Term
4    PredicateObject map[rdf.Term][]rdf.Term
5}

Adding a method ID() that returns an int64 makes it compatible with gonum’s Node interface. Therefore it is possible to add it to a simple graph. So far, this codes compiles (but is useless):

1g := &Graph{
2    DirectedGraph: simple.NewDirectedGraph(),
3}
4g.DirectedGraph.AddNode(&MyNode{})

Declaration of the edge

Using the same principle, we create an Edge structure that holds two nodes From and To as well as a term that defines the edge.

1type Edge struct {
2    F, T graph.Node
3    Term rdf.Term
4}

Therefore, this code compiles (but is useless):

1g := &Graph{
2    DirectedGraph: simple.NewDirectedGraph(),
3}
4n0:=&MyNode{id:0}
5n1:=&MyNode{id:1}
6g.DirectedGraph.AddNode(n0)
7g.DirectedGraph.AddNode(n1)
8e := Edge{F: n0, T: n1}
9g.SetEdge(e)

We have created a graph with two nodes and an edge between them.

Parsing the rdf graph to generate our directed graph

The first thing we’ll do is to create a tree of terms. We do that thanks to a hash map. The key is a subject, and the value is another map. The map value’s key is a predicate and the value is an array of objects (remember that a predicate can point to several objects)

1tree := make(map[gon3.Term]map[gon3.Term][]gon3.Term)

But before parsing the rdf graph to fill the tree, we have to address a little gotcha. a Term is an interface. Therefore it is a pointer. Therefore in the rdf graph, if we consider two Terms t1 and t2 such as:

1t1 := gon3.NewLiteral("bla")
2t2 := gon3.NewLiteral("bla")

t1 is different from t2 (even is their values are the same)

To address this, we will track a dictionary of terms indexed by their RawValue().

1type Dict map[string]rdf.Term
2
3func (d Dict) getOrInsert(t rdf.Term) rdf.Term {
4    //...
5}

Then we iter over the triples from our rdf graph to fille the tree and the dictionary.

1for s := range rdfGraph.IterTriples() {
2    // ... fill dict and tree
3}

Note: for convenience, we will also set the dictionary as an attribute to our graph for later. The structure becomes:

1type Graph struct {
2    *simple.DirectedGraph
3    Dict map[string]rdf.Term}

We can now range over the tree, and create all the nodes in the graph for each subject:

1for s, po := range tree {
2    n := &Node{
3        id:              g.NewNode().ID(),
4        Subject:         s,
5        PredicateObject: po,
6    }
7    g.AddNode(n)
8    reference[s] = n
9}

Note: once again, for convenience, we track the nodes in a hash map. This reference map has the subject as a key and the node as a value (its type is map[rdf.Term]*Node).

Finally, we loop once again through the tree to create the edges:

 1for s, po := range tree {
 2    me := reference[s]
 3    for predicate, objects := range po {
 4        for _, object := range objects {
 5            if me == to { // self edge
 6                continue
 7            }
 8            to := reference[object]
 9            e := Edge{ F: me, T: to, Term: predicate, }
10            g.SetEdge(e)
11        }
12    }
13}

Note: error handling is omited for brevity

Putting all together

Now that we have the graph builder ok, we can test it with the data from schema.org we downloaded earlier.

Let’s write a simple program that creates the graph and do a simple query. For example, we may want to get all the nodes directly linked to the PostalAddress in schema.org.

 1baseURI := "https://example.org/foo"
 2parser := rdf.NewParser(baseURI)
 3gr, err := parser.Parse(os.Stdin)
 4if err != nil {
 5    log.Fatal(err)
 6}
 7g := graph.NewGraph(gr)
 8postalAddress := g.Dict["http://schema.org/PostalAddress"]
 9node := g.Reference[postalAddress]
10it := g.To(node.ID())
11for it.Next() {
12    n := it.Node().(*graph.Node) // need inference here because gonum's simple graph returns a type graph.Node which is an interface
13    fmt.Printf("%v -> %v\n", node.Subject, n.Subject)
14}

This prints the following output:

 1❯ cat schemaorg-current-http.ttl| go run main.go
 2<http://schema.org/PostalAddress> -> <http://schema.org/deliveryAddress>
 3<http://schema.org/PostalAddress> -> <http://schema.org/postalCode>
 4<http://schema.org/PostalAddress> -> <http://schema.org/servicePostalAddress>
 5<http://schema.org/PostalAddress> -> <http://schema.org/originAddress>
 6<http://schema.org/PostalAddress> -> <http://schema.org/addressCountry>
 7<http://schema.org/PostalAddress> -> <http://schema.org/location>
 8<http://schema.org/PostalAddress> -> <http://schema.org/billingAddress>
 9<http://schema.org/PostalAddress> -> <http://schema.org/addressLocality>
10<http://schema.org/PostalAddress> -> <http://schema.org/postOfficeBoxNumber>
11<http://schema.org/PostalAddress> -> <http://schema.org/streetAddress>
12<http://schema.org/PostalAddress> -> <http://schema.org/address>
13<http://schema.org/PostalAddress> -> <http://schema.org/addressRegion>
14<http://schema.org/PostalAddress> -> <http://schema.org/gameLocation>
15<http://schema.org/PostalAddress> -> <http://schema.org/itemLocation>

If we check on schema.org’s website (https://schema.org/PostalAddress), we find those elements but in two different tables:

Remember, we are dealing with ontology; therefore, the link has a meaning. And this meaning has been set as an attribute of the edge. If we tweak the code to display the edge like this:

1for it.Next() {
2    n := it.Node().(*graph.Node) // need inference here because gonum's simple graph returns a type graph.Node which is an interface
3    e := g.Edge(n.ID(), node.ID()).(graph.Edge)
4    fmt.Printf("%v -%v-> %v\n", node.Subject, e.Term, n.Subject)
5}

we obtain:

 1<http://schema.org/PostalAddress> -<http://schema.org/domainIncludes>-> <http://schema.org/addressRegion>
 2<http://schema.org/PostalAddress> -<http://schema.org/rangeIncludes>-> <http://schema.org/billingAddress>
 3<http://schema.org/PostalAddress> -<http://schema.org/rangeIncludes>-> <http://schema.org/servicePostalAddress>
 4<http://schema.org/PostalAddress> -<http://schema.org/domainIncludes>-> <http://schema.org/streetAddress>
 5<http://schema.org/PostalAddress> -<http://schema.org/domainIncludes>-> <http://schema.org/addressCountry>
 6<http://schema.org/PostalAddress> -<http://schema.org/domainIncludes>-> <http://schema.org/postOfficeBoxNumber>
 7<http://schema.org/PostalAddress> -<http://schema.org/domainIncludes>-> <http://schema.org/addressLocality>
 8<http://schema.org/PostalAddress> -<http://schema.org/rangeIncludes>-> <http://schema.org/location>
 9<http://schema.org/PostalAddress> -<http://schema.org/rangeIncludes>-> <http://schema.org/itemLocation>
10<http://schema.org/PostalAddress> -<http://schema.org/rangeIncludes>-> <http://schema.org/deliveryAddress>
11<http://schema.org/PostalAddress> -<http://schema.org/rangeIncludes>-> <http://schema.org/address>
12<http://schema.org/PostalAddress> -<http://schema.org/domainIncludes>-> <http://schema.org/postalCode>
13<http://schema.org/PostalAddress> -<http://schema.org/rangeIncludes>-> <http://schema.org/gameLocation>
14<http://schema.org/PostalAddress> -<http://schema.org/rangeIncludes>-> <http://schema.org/originAddress>

Conclusion

We’ve built a graph structure in memory quickly. What’s important is not the structure by itself. The important is the perspectives it opens. So far, we have worked on schemas, but the semantics applies to the data itself. On top of that, the graph we have generated is reasonably generic. Therefore, the same principle could be used to store our knowledge graph within a persistent database such as dgraph or maybe neo4j.

In the next article, we will work with the graph and set up a template engine to create generic documentation of our knowledge graph using go template.

Meanwhile, you can fetch the code (which is not production-ready) on my github