Graph databases are one in a plethora of NoSQL databases now found in the wild. They\u2019re unique among their sibling database types by having a unique internal data structure. Graph databases make the relationships within the data a first-class citizen on the same level as the data itself.<\/p>\n
Consequently, they are most popular in social networking, big data, and science and research communities. These domains have datasets that are as much about the relationships they encode as they are about the data. When everything\u2019s interconnected \u2014 say, like on the web \u2014 then the real power of this model starts to become apparent.<\/p>\n
So, rather than focusing on pairing data values to meaning (column heading, key name, etc), graph databases express things using:<\/p>\n
Here\u2019s what a graph database might look like:<\/p>\n
BigBlueHat writesFor Codeship<\/p><\/blockquote>\n
Reads like a sentence, right? In fact, in \u201ctriplestores\u201d (a common graph database implementation type), these terms map to the following, more grammatically friendly names:<\/p>\n
\n
- Subject \u2014 the thing being talked about (node)<\/li>\n
- Predicate \u2014 what\u2019s being said about the subject relative to the object (edge)<\/li>\n
- Object \u2014 the thing related to the subject (property)<\/li>\n<\/ul>\n
Simpler, right? Here are some more:<\/p>\n
BigBlueHat contributesTo LevelGraph<\/p>\n
BrightBall writesFor Codeship<\/p>\n
BigBlueHat postsCodeAt https:\/\/github.com\/bigbluehat<\/p><\/blockquote>\n
These statements use the same \u201cwritesFor\u201d predicate, so finding out \u201cwho writes for Codeship\u201d would be trivial. But what if we wanted to ask \u201cWhere do authors at Codeship post code?\u201d If you squint, you\u2019ll see two sets of potential algebraic-looking sentences in there:<\/p>\n
X writesFor Codeship<\/p>\n
X postsCodeAt Y<\/p><\/blockquote>\n
This ability to stack and relate other relationships into cascading related queries is one of the core powers of graph databases.<\/p>\n
Mind blown yet? Let\u2019s back up.<\/p>\n
How to Build a Hexastore<\/h2>\n
LevelGraph<\/a> is an implementation of a \u201chexastore\u201d which is built upon LevelUp<\/a> and LevelDB<\/a>. Hexastores combine the consistent nature of triplestores with the boring but beneficial power of materialized indexes.<\/p>\n
Given the triples we used above, you could imagine a key\/value-based master index with all the triples (subject, predicate, object) stored as the key with
null<\/code> or1<\/code> or anything stored as the value. Doing that would give one the power to find all the relationships of a single subject.<\/p>\nFor instance, you can imagine the statements above stored in Redis (or whatever) as these keys \u2014 each with a value of
1<\/code>:<\/p>\nBigBlueHat|writesFor|Codeship<\/p>\n
BigBlueHat|contributesTo|LevelGraph<\/p>\n
BrightBall|writesFor|Codeship<\/p>\n
BigBlueHat|postsCodeAt|https:\/\/github.com\/bigbluehat<\/p><\/blockquote>\n
Given the above, we could answer simple queries like \u201cwho does BigBlueHat writeFor?\u201d or \u201cwhat do we know about Brightball?\u201d But we could not ask the more complex query mentioned above or answer something more common like \u201cwho writesFor Codeship?\u201d<\/p>\n
Hexastores use this same basic \u201ckey-heavy\u201d storage style, but they store the same data six different ways. Seriously. Let\u2019s have a look.<\/p>\n
We\u2019ll store S P O as our triple (for simplicity). A hexastore would store these six keys:<\/p>\n
S|P|O<\/p>\n
S|O|P<\/p>\n
P|O|S<\/p>\n
P|S|O<\/p>\n
O|S|P<\/p>\n
O|P|S<\/p><\/blockquote>\n
Seem crazy? Maybe. But it\u2019s also crazy efficient for lookups.<\/p>\n
Let\u2019s look at that query from earlier:<\/p>\n
X writesFor CodeShip<\/p>\n
X postsCodeAt Y<\/p><\/blockquote>\n
Given that query, we\u2019d use the keys that have a P|O|S structure first (to answer for \u201cX\u201d) and, once we\u2019ve solved for X, we\u2019d check the S|P|O keys where X = S.<\/p>\n
Remember, these are range-based, boring-old, materialized lookups. They\u2019re not doing table scans. They\u2019re jumping straight to that point in the index and returning what they find. Afterword, there\u2019s some combination \u2014 if needed.<\/p>\n
The above query, then, we\u2019d check this range first:<\/p>\n
writesFor|CodeShip|*<\/p><\/blockquote>\n
which would return these keys from our little dataset:<\/p>\n
writesFor|CodeShip|BigBlueHat<\/p>\n
writesFor|CodeShip|BrightBall<\/p><\/blockquote>\n
Then, using those results, we\u2019d hit the index again, looking for this range:<\/p>\n
BigBlueHat|postsCodeAt|*<\/p><\/blockquote>\n
Which would result in this key:<\/p>\n
BigBlueHat|postsCodeAt|https:\/\/github.com\/BigBlueHat<\/p><\/blockquote>\n
We now have the answers to our \u201ccomplex\u201d little question. Pretty rad, right?<\/p>\n
Onward.<\/p>\n
Meet LevelGraph<\/h2>\n
LevelGraph is (as mentioned) an implementation of a hexastore. It uses LevelUp and LevelDB as a foundational key\/value store. In the browser, it uses level.js<\/a> to store the same sort of hexastore key-based master index (as seen above) into an IndexedDB database.<\/p>\n
LevelGraph can be installed via browserify<\/a>. Installation instructions<\/a> can be found in the
levelgraph<\/code> GitHub repo<\/a>.<\/p>\nPutting data into LevelGraph looks like:<\/p>\n
db.put({\r\n subject: \"BigBlueHat\",\r\n predicate: \"writesFor\",\r\n object: \"Codeship\"\r\n}, function(err) {\r\n if (err) throw err;\r\n});<\/pre>\nIn this case, if there\u2019s an error, it will get thrown. Otherwise, it\u2019s safe to assume the triple went in verbatim.<\/p>\n
Once the data has been added to LevelGraph, the underlying LevelDB (or IndexedDB if you\u2019re in a browser) will show keys looking rather similar to the ones above.<\/p>\n
Getting data out of LevelGraph takes one of three forms:<\/p>\n
\n
db.get()<\/code> for a all triples containing any combination of a subject, predicate, or object<\/li>\ndb.search()<\/code> for doing queries like the one we did before + filtering + materialization<\/li>\ndb.nav.*<\/code> chained queries using methods similar to the Gremlin query system from Apache Tinkerpop and friends<\/li>\n<\/ul>\nLet\u2019s take a look at each of those in turn.<\/p>\n
First, a basic
db.get()<\/code> could be used to answer the \u201cwho writesFor Codeship?\u201d question above:<\/p>\ndb.get({\r\n predicate: \"writesFor\",\r\n object: \"Codeship\"\r\n}, function(err, rv) {\r\n if (err) throw err;\r\n console.log('rv', rv);\r\n});<\/pre>\nThe output is a an array of triples (subject, predicate, object) that contain the \u201cwritesFor\u201d predicate and the \u201cCodeship\u201d object values. We can use the callback to extract just the subjects from those objects giving an array of answers to our question:<\/p>\n
db.get({\r\n predicate: \"writesFor\",\r\n object: \"Codeship\"\r\n}, function(err, rv) {\r\n if (err) throw err;\r\n writers = rv.map(function(triple) {\r\n return triple.subject;\r\n });\r\n console.log('writers', writers);\r\n \/\/ writers = [\"BigBlueHat\", \"Brightball\"]\r\n});<\/pre>\nNext, let\u2019s take a look at that more complex query using the
db.search()<\/code> API.<\/p>\n\/\/ X writesFor Codeship\r\n\/\/ X postsCodeAt Y\r\ndb.search([\r\n {\r\n subject: db.v('x'),\r\n predicate: \"writesFor\",\r\n object: \"Codeship\"\r\n },\r\n {\r\n subject: db.v('x'),\r\n predicate: \"postsCodeAt\",\r\n object: db.v('y')\r\n }\r\n],\r\n{}, \/\/ we'll talk about this shortly\r\nfunction(err, rv) {\r\n if (err) throw err;\r\n console.log('rv', rv);\r\n});<\/pre>\nThe output is an array of results mapped to their
db.v()<\/code> value holders.<\/p>\n\/\/ output of the above `db.search`\r\nrv = [{x: \"BigBlueHat\", y: \"https:\/\/github.com\/bigbluehat\"}]<\/pre>\nIt\u2019s also possible to include a
filter<\/code> function alongside any triple used in the search queries. This can be helpful for further limiting the output as the queries cascade into each other. For instance, if we only wanted code posted on GitHub, we could make the second search query object read:<\/p>\n{\r\n subject: db.v('x'),\r\n predicate: \"postsCodeAt\",\r\n object: db.v('y'),\r\n filter: function(triple) {\r\n return triple.object.search(\"github.com\") > -1;\r\n }\r\n}<\/pre>\nOnce the results are in, we can also provide a final
filter<\/code> in that second parameter we say earlier (currently set to{}<\/code>). However, those filter functions take a slightly different using a callback function to confirm or reject the result (aka the solution to the query):<\/p>\nfunction filter(solution, callback) {\r\n \/\/ we're only looking for things starting with `B`\r\n if ('x' in solution && solution.x.search(\/\\^B\/) > -1) {\r\n \/\/ confirm\/keep the solution\/result\r\n callback(null, solution);\r\n } else {\r\n \/\/ reject\/skip\r\n callback(null);\r\n }\r\n}<\/pre>\nAdditionally, if we wanted to reshape the output back into triples, we can use the
materialized<\/code> object. This is most useful when creating new triples within the graph based on results found from a search query.<\/p>\nFor example:<\/p>\n
{\r\n materialized: {\r\n subject: \"Codeship\",\r\n predicate: \"authorCodeRepository\",\r\n object: db.v('y')\r\n }\r\n}<\/pre>\nThe result in this case being a new triple of:<\/p>\n
Codeship authorCodeRepository https:\/\/github.com\/bigbluehat<\/p><\/blockquote>\n
This can be super handy when you need to change the shape of the graph or make new statements into other graphs. Additionally, you can use the materialized output to do additional
db.get()<\/code> anddb.search()<\/code> requests using the materialized output as the query options in the next request or perhaps even removing any remaining statements from the graph that used a different predicate.<\/p>\nRemoving triples looks rather like putting them, only the method is
db.del()<\/code>:<\/p>\ndb.del(\r\n {subject: \"BigBlueHat\", predicate: \"postsCodeAt\",\r\n object: \"https:\/\/github.com\/bigbluehat\"},\r\n function(err) { if (err) throw err; });<\/pre>\nLevelGraph looks up the six variations of the triple-based keys in the hexastore and deletes them. If it can\u2019t find the key(s), it throws an error.<\/p>\n
Now. Editing is going to feel a bit odd\u2026<\/p>\n
Because these are key names and not values, we can\u2019t just alter them in place. We have to remove them and then put the new ones in.<\/p>\n
Let\u2019s change the
https:\/\/github.com\/bigbluehat<\/code> URL tohttps:\/\/github.com\/BigBlueHat\/<\/code> (which is technically more accurate). We\u2019ll start with thedb.del()<\/code> operation above, and thendb.put()<\/code> the replacement:<\/p>\ndb.del(\r\n {subject: \"BigBlueHat\", predicate: \"postsCodeAt\",\r\n object:\"https:\/\/github.com\/bigbluehat\"},\r\n function(err) {\r\n if (err) throw err;\r\n db.put({subject: \"BigBlueHat\", predicate: \"postsCodeAt\",\r\n object: \"https:\/\/github.com\/BigBlueHat\/\"},\r\n function(err) { if (err) throw err; });\r\n });<\/pre>\nThat should do it. In fact, you could reverse those, so you\u2019d be sure that the new stuff made it in before you removed the old one. Let\u2019s do that in the next example.<\/p>\n
The code above works when we know a single triple that has the string we need to update in it. If we need to update all occurrences of the string in the graph, then we\u2019ll need to search for them all and then re-put them. Like so:<\/p>\n
db.search([\r\n {subject: db.v('s'), predicate: db.v('p'),\r\n object:\"https:\/\/github.com\/bigbluehat\"}],\r\n {},\r\n function(err, rv) {\r\n rv.forEach(function(r) {\r\n \/\/ putting the new stuff in first, to be sure it makes it in\r\n db.put({subject: r.s, predicate: r.p,\r\n object: \"https:\/\/github.com\/BigBlueHat\/\"},\r\n function(err) {\r\n if (err) throw err;\r\n \/\/ new stuff is in, so let's remove the old\r\n db.del({subject: r.s, predicate: r.p,\r\n object: \"http:\/\/github.com\/bigbluehat\"},\r\n function(err) { if (err) throw err; }\r\n );\r\n }\r\n );\r\n });\r\n });<\/pre>\nWhile that may seem tedious, it has the advantage of being progressive improvement \u2014 good stuff in, then bad stuff out \u2014 or the other way around if you\u2019d like. It\u2019s up to you.<\/p>\n
One thing worth noting is that we\u2019ve not had to name any columns or figure out primary or secondary keys. We didn\u2019t even have to determine what we were going to index before we stored something. Since the data has this consistent, triple-based shape throughout the process, those things are implicitly handled.<\/p>\n
Let\u2019s move on to Linked Data.<\/p>\n
Linked Data Land<\/h2>\n
LevelGraph is one of many hexastore implementations, but it\u2019s use in Node.js and the browsers, meaning that it\u2019s an ideal candidate for building apps for working with Linked Data.<\/p>\n
Linked Data uses this same graph-based thinking plus the webby nature of graphs (or is it the graphy nature of the web\u2026) and brings that to data \u2014 not just documents.<\/p>\n
Our examples above were fine for what they are, but they assumed (rashly) a closed world environment in which \u201cwritesFor\u201d is seen as sufficient within the closed world of our little graph. However, what happens when the two of us exchange data and you used something like \u201cauthorsFor\u201d? What happens if English isn\u2019t your native language?<\/p>\n
That\u2019s where Linked Data comes in.<\/p>\n
Let\u2019s go back to that very first triple:<\/p>\n
BigBlueHat writesFor Codeship<\/p><\/blockquote>\n
In this triple, we\u2019re using plain strings made of English words to be the identifiers of the things themselves. Trouble is, that don\u2019t scale so good.<\/p>\n
Here\u2019s what that same triple would look like using the Schema.org Linked Data vocabulary developed by Google, Microsoft, Yahoo, Yandex, and friends and developed in a W3C Community Group:<\/p>\n
https:\/\/blog.codeship.com\/json-ld-building-meaningful-data-apis\/ http:\/\/schema.org\/author http:\/\/bigbluehat.com\/#me<\/p>\n
https:\/\/blog.codeship.com\/json-ld-building-meaningful-data-apis\/ http:\/\/schema.org\/publisher https:\/\/codeship.com\/#<\/p><\/blockquote>\n
We\u2019ve now made two global-friendly statements using five total identifiers. Interestingly, we\u2019ve now introduced an identifier (and in this case it\u2019s also a locator) of something published and<\/em> authored \u2014 which is information we\u2019d lacked before.<\/p>\n
However, there\u2019s now no direct relationship between the \u201cBigBlueHat\u201d identifier and the \u201cCodeship\u201d (blog) identifier. That said, we now specify one of the things that \u201cBigBlueHat\u201d actually wrote for \u201cCodeship\u201d and a URL of where it\u2019s published, so those are wins to be sure.<\/p>\n
But how do we find out \u201cwho writes for the Codeship blog\u201d now?<\/p>\n
db.search([\r\n {\r\n subject: db.v('article'),\r\n predicate: \"http:\/\/schema.org\/author\",\r\n object: db.v('author')\r\n },\r\n {\r\n subject: db.v('article'),\r\n predicate: \"http:\/\/schema.org\/publisher\",\r\n object: db.v('publisher')\r\n }],\r\n {},\r\n function(err, rv) {\r\n if (err) throw err;\r\n console.log('rv', rv);\r\n }\r\n);<\/pre>\nThe output should look like this:<\/p>\n
rv = [\r\n {\r\n author: \"http:\/\/bigbluehat.com\/#me\",\r\n article: \"https:\/\/blog.codeship.com\/json-ld-building-meaningful-data-apis\/\",\r\n publisher: \"https:\/\/codeship.com\/#\"\r\n }\r\n];<\/pre>\nIf we were to update Brightball\u2019s triple statements to use the Schema.org vocabulary, there\u2019d be more results. Additionally, we could use a
filter<\/code> function at the end to clear out the article names if we were only interested in authors, for instance. However, in this case, we have even richer data returned than we did earlier, not to mention more accurately defined data!<\/p>\nConclusion<\/h2>\n
This only scratches the surface of both LevelGraph and Linked Data. The graph model can take some time to get your head around, but it\u2019s one that\u2019s been increasingly delightful to work with as I learn the tooling, understand graph querying, and build more tools around it.<\/p>\n
If you\u2019re new to all this and want to play with LevelGraph without the installation setup, give the LevelGraph Playground<\/a> a look.<\/p>\n
You can add colloquial (\u201cclosed world\u201d) graphs if you\u2019d like, but it also supports common Linked Data formats such as JSON-LD, Turtle, and N3. JSON-LD is increasingly common and if you\u2019ve landed at the Schema.org site while reading this article, you might enjoy testing out their JSON-LD examples on the playground.<\/p>\n
The graphs that will be stored don\u2019t always connect, so they\u2019re not necessarily great for testing queries against. However, those examples should give you a quick way to build up a larger graph.<\/p>\n
Lastly, you can also then output any filtered results into JSON-LD or Turtle and send them off to other people who can add them to their graph. If you use the same vocabulary, then you\u2019ll both benefit from the shared meaningful data that you can query across your own personal knowledge store.<\/p>\n
\n