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

Models and Relationships




Model Example Fast for Relationships
Documental MongoDB
Relational MySQL
Graph OrientDB

The smallest possible graph



  • "A" is called subject
  • "B" is called object
  • "A" and "B" are also called vertexes
  • "C" is called predicate
  • "C" is also called arc

Query Examples



  • Give me all the vertex that go from "A"
  • Give me all the pairs connected by "C"
  • Give me all the vertex that go to "B"
  • Give me all the vertex that go to "B" through "C"
  • ...

Hexastore: the fastest data structure for a Graph

My Secret Ingredient for a Graph Database

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

LevelDB



basic features:
  • get
  • put
  • del
  • batch
  • ordered iterator

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

Tools
lev levelweb
Packages
tacodb couchup LevelGraph firedup level-assoc
level-static level-store level-session level-fs LevelTTLCache
Extensions
level-live-stream map-reduce level-queryengine Level-Multiply
multilevel level-replicate level-master Level TTL
Extensibility
sublevel level-hooks level-mutex
Core
LevelUP
Storage
LevelDOWN LevelDOWN (Hyper) LevelDOWN (Basho) LevelDOWN (RocksDB) MemDOWN level.js leveldown-gap LMDB mysqlDOWN

LevelUp's Committers

Rod VaggGitHub/rvaggTwitter/@rvagg
John ChesleyGitHub/cheslesTwitter/@chesles
Jake VerbatenGitHub/raynosTwitter/@raynos2
Dominic TarrGitHub/dominictarrTwitter/@dominictarr
Max OgdenGitHub/maxogdenTwitter/@maxogden
Lars-Magnus SkogGitHub/ralphtheninjaTwitter/@ralphtheninja
David BjörklundGitHub/keslaTwitter/@david_bjorklund
Julian GruberGitHub/juliangruberTwitter/@juliangruber
Paolo FragomeniGitHub/hij1nxTwitter/@hij1nx
Anton WhalleyGitHub/No9Twitter/@antonwhalley
Matteo CollinaGitHub/mcollinaTwitter/@matteocollina
Pedro TeixeiraGitHub/pgteTwitter/@pgte
James HallidayGitHub/substackTwitter/@substack

How to use LevelUp to build a Graph Database

Let's build an Hexastore!

Hexastore



We store 6 keys for each triple:
  • spo::A::C::B
  • sop::A::B::C
  • ops::B::C::A
  • osp::B::A::C
  • pso::C::A::B
  • pos::C::B::A

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

http://github.com/mcollina/levelgraph

LevelGraph

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?

..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"   } ]
})

Linked Open Data

What does that mean?

Is your data accessible?

Linked Open Data Cloud

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");
});

LevelGraph

http://github.com/mcollina/levelgraph

http://github.com/mcollina

Yet Another Node.js Course

Node.js Basics

http://www.insana-academy.com/node-js-basics/

My Book: JavaScript Best Practices

Thanks!


If you need help with node.js:


hello@matteocollina.com

@matteocollina on Twitter

www.matteocollina.com