How to Cook a Graph Database in a Night

@matteocollina

What is a Graph Database?

a graph database is any storage system that provides index-free adjacency

Anonymous Wikipedian

My Secret Ingredient for a Graph Database

http://500px.com/photo/52159764  

LevelUp!

http://github.com/rvagg/node-levelup

The LevelDB library for Node.js

LevelDB is an ordered key-value store that can be embedded in ANY app

http://500px.com/photo/52159764  

LevelUp

var db = level('your_database')
db.put('a', 'b', function() {
  db.put('b', 'c', function() {
    db.get('a', function(err, data) {
      alert(JSON.stringify(data))
    })
  })
})

ReadStream

var db = level('your_database')
var stream = db.createReadStream({
  start: 'a',
  end: 'd'
})
stream.on('data', function(data) {
  alert(JSON.stringify(data))
})
stream.on('end', function() {
  alert('end!')
})

LevelUp's Ecosystem

How to use LevelUp to build a Graph Database

Let's build an Hexastore!

Put a Triple in LevelDB

var db = level('your_database')
var triple = JSON.stringify({
  subject: 'A', predicate: 'C', object: 'B'
})
db.batch([
  { key: 'spo::A::C::B', value: triple, type: 'put' },
  { key: 'sop::A::B::C', value: triple, type: 'put' },
  { key: 'ops::B::C::A', value: triple, type: 'put' },
  { key: 'osp::B::A::C', value: triple, type: 'put' },
  { key: 'pso::C::A::B', value: triple, type: 'put' },
  { key: 'pos::C::B::A', value: triple, type: 'put' }
], alert.bind(null, 'Batch completed!'))

Ask a Triple to LevelDB

all nodes that are connected by "C"

var db = level('your_database')
var stream = db.createReadStream({
  start: 'pso::C::',
  end:   'pso::C::\xff'
})

stream.on('data', function(data) {
  alert(data.value)
})

LevelGraph

• is an Hexastore built on LevelDB and LevelUp
• v0.1.0 was built on the night between the 25th and 26th of April 2013
• v0.8.0 was released this Christmas
• 250+ commits and counting
• works on Node and in the Browser
• small in size (< 1000 own lines of code)
• big on dependencies (~ 11000 lines of code)
• available on npm, bower or straight from github

Put Triples in LevelGraph

var graph = levelgraph('your_graph')

var triples = [{
  subject: 'A', predicate: 'C', object: 'B'
}, {
  subject: 'D', predicate: 'C', object: 'E'
}]

graph.put(triples, function(err) {
  alert(err || "Successful!")
})

Ask Triples to LevelGraph

all nodes that are connected by "C"

var graph = levelgraph('your_graph')
var query = { predicate: 'C' }

graph.get(query, function(err, triples) {
  alert(JSON.stringify(triples))
})

Deleting Triples in LevelGraph

var graph = levelgraph('your_graph')
var triples = [
  { subject: 'A', predicate: 'C', object: 'B' },
  { subject: 'D', predicate: 'C', object: 'E' }
]
graph.del(triples, function(err) {
  graph.get({ predicate: 'C' }, function(err, triples) {
    alert('LG found ' + triples.length + ' triples')
  })
})

Stream Triples in LevelGraph

var graph = levelgraph('your_graph')
var stream = graph.putStream()

stream.write({
  subject: 'matteo', predicate: 'friend', object: 'lucio'
})
stream.write({
  subject: 'lucio', predicate: 'likes', object: 'beer'
})
stream.write({
  subject: 'lucio', predicate: 'lives', object: 'brescia'
})
stream.end(null, alert.bind(null, 'Successful!'))

Stream Triples out of LevelGraph

all people that likes beer

var graph = levelgraph('your_graph')

var stream = graph.getStream({
  predicate: 'likes',
  object: 'beer'
})

stream.on('data', function(triple) {
  alert(JSON.stringify(triple))
})

Is it all?

We did not build a graph  just  for this, right?

Searches

All my friends that like beer and live in Brescia

var graph = levelgraph('your_graph')
var x = graph.v('x')
graph.search([
  { subject: 'matteo', predicate: 'friend', object: x },
  { subject: x, predicate: 'likes', object: 'beer' },
  { subject: x, predicate: 'lives', object: 'brescia' }
], function(err, solutions) {
  alert(JSON.stringify(solutions))
})

Searches

All my friends that like beer and live in Brescia, with Streams

var graph = levelgraph('your_graph')
var x = graph.v('x')
var stream = graph.searchStream([
  { subject: 'matteo', predicate: 'friend', object: x },
  { subject: x, predicate: 'likes', object: 'beer' },
  { subject: x, predicate: 'lives', object: 'brescia' }
]);

stream.on('data', function(triple) {
  alert(JSON.stringify(triple))
})

How fast is LevelGraph?

• GET  Up to 50.000 triples per second
• PUT  Up to 22.000 triples per second
• SEARCH  Up to 20.000 triples per second for two conditions

..but I want to store JS Objects!

LevelGraph-JSONLD

an Object Document Mapper for LevelGraph

var db = jsonld(levelgraph('jsonld'));
db.jsonld.put({
  "@context": {
    "name": "http://xmlns.com/foaf/0.1/name",
    "knows": "http://xmlns.com/foaf/0.1/knows" },
  "@id": "http://matteocollina.com",
  "name": "Matteo",
  "knows": [ { "name": "Daniele" }
             { "name": "Lucio"   } ]
})

Our Dataset

@prefix c: <http://example.org/cartoons#>.
c:Tom   a c:Cat.
c:Jerry a c:Mouse;
        c:smarterThan c:Tom;
        c:place "fantasy".
        

That has id '#dataset'

Importing a Dataset

var graph = n3(levelgraph("n3"));
var dataset = document.querySelector("#dataset");

graph.n3.put(dataset.innerText, function() {
  alert("import completed!")
  
  var stream = graph.getStream({})
  
  stream.on('data', function(triple) {
    alert(JSON.stringify(triple))
  })
});

Importing a Dataset with Streams

var graph = n3(levelgraph('n3'));
var fs = require("fs");

var stream = fs.createReadStream("./triples.n3")
               .pipe(graph.n3.putStream());
               
stream.on("finish", function() {
  console.log("Import completed");
});

Yet Another Node.js Course

Node.js Basics

• Events, Streams, Buffer, HTTP, Ereditarietà
• Testing con Mocha, Chai e Sinon
• Express
• WebSocket
• Grunt
• MongoDB and Mongoose
• ... lots of fun in Italian! :)

My Book: JavaScript Best Practices

Thanks!

If you need help with node.js:

hello@matteocollina.com

@matteocollina on Twitter

www.matteocollina.com