Graph Databases 101
cray.com
cray.com
For the particular project we ended up using Redis and storing the graph as an adjacency list in a machine with 128GB of RAM.
The reason I don't think there ever will be a "graph database" is because there are so many different ways you can store a graph, so many things you might want to do with one. It's trivial to build a "graph database" in a few lines of any programming language - graph traversal is (hopefully) taught in any decent CS course.
Also - the latest versions of PostgreSQL have all the features to support graph storage. It's ironic how PostgreSQL is becoming a SQL database that is gradually taking over the "NoSQL" problem space.
(FWIW, I had previously read some Barabasi papers and had come away seriously unimpressed, see also https://news.ycombinator.com/item?id=9555547)
Yes, scale-free networks (and so on, and so on), are oversold. Is his work really that bad though?
https://aws.amazon.com/blogs/aws/new-store-and-process-graph...
https://en.wikipedia.org/wiki/Graph_database#List_of_graph_d...
Oh but I love a challenge. Are there reasons to choose cypher besides a gentle learning curve?
There was some post about enabling SPARQL in Neo4J, but when you install Neo4J it comes with cypher by default (not sure if it supports anything else).
I use Apache Jena + SPARQL, but had to use Neo4J to help in a master thesis. Took me a few hours of "How the heck can I do that same thing I'd do in SPARQL that way?", plus some reading of the tutorials.
Edit: some old post with example of Cypher, Gremlin and SPARQL: http://kinoshita.eti.br/2014/09/09/cypher-gremlin-and-sparql...
One example: https://github.com/thinkaurelius/neo4j-gremlin-plugin
Also can use the Tinkerpop3 or Blueprints APIs to access your graph with Gremlin.
The most fun things are in-query dataflow which allows you to pass information from one query part to the next (projected, aggregated, ordered etc).
And the really cool collection and map functions, so you save a lot of roundtrips between client and server.
[1] http://conceptnet5.media.mit.edu
Here's a list of databases, some of them graph databases, some of them barely databases, where I've tried to store and look up edges of ConceptNet:
- SQLite
- PostgreSQL
- MongoDB
- Some awful IBM quad-store
- HypergraphDB
- Tinkerpop
- Neo4J
- Solr
- Riak
- SQLite with APSW to speed up importing
- Just a hand-rolled hashtable on disk
- PostgreSQL
- SQLite with APSW to speed up importing
- Just a hand-rolled hashtable on disk
If this has changed, please point me at an open-source graph database that's not terrified of gigabytes. (No trying to sell me SaaS, please.)
NB: TinkePop is not a graph DB -- it's a graph software stack / computing framework for graph DBs (OLTP) and graph analytic systems (OLAP). Since TinkerPop is integrated with almost all of the graph DBs and graph processing engines, its mailing lists are good place to discuss and get help with graph-related projects.
[1] http://tinkerpop.incubator.apache.org/
[2] TinkerPop / Gremlin Users Mailing List http://groups.google.com/group/gremlin-users
[3] TinkerPop Developer Mailing List http://mail-archives.apache.org/mod_mbox/incubator-tinkerpop...
Using distributed computing on mere gigabytes of data is silly.
I think TinkerPop was something else back in 2011, but apologies if I've used the wrong terminology.
It really depends on the kind of algorithm you run on the database.
Based on open source project, in read/write mode, no db can help you since you load everything into memory. As a noob NLP user, I rather use something like AjguDB https://github.com/amirouche/ajgudb
Did your hand-rolled hashtable have any characteristics that would make its performance characteristics difficult for a smarter optimizer (if such a thing existed in Neo4j)?
Can you psudocode an example slow query/operation and indicate how many edges/vertices were being considered at each step?
Sorry to ask these kinds of questions, I'm just really curious about the situation you described.
Here's what I have to be able to do in the database:
1. Import millions of edges from a flat file (time limit: 24 hours)
2. Query any node to return up to 100 edges connected to it (time limit: 100 milliseconds)
3. (nice to have) Find the maximal core of nodes that all have degree at least n to each other (time limit: a few hours)
4. Iterate all the edges between the nodes in a specified subset, such as the degree-3 core, which may still be millions of edges (time limit: a few hours)
#3 is optional, and the alternative is to export all the edges and compute it outside the database. But it's the only thing here that's actually a graph algorithm. However, every open-source graph database I've tried is orders of magnitude too slow at one of the other steps. They either fail at importing, fail at iterating, or fail to respond to trivial queries in a timely manner.
I forgot to mention one other non-graph-database system that met my requirements, which is Kyoto Cabinet. The main downside of it is the GPLv3 license.
SQLGraph: An Efficient Relational-Based Property Graph Store http://research.google.com/pubs/archive/43287.pdf
Previous discussion: https://news.ycombinator.com/item?id=11101013
Also, if you don't mind me asking, how does it not being a property graph affect modelling your data and queries? At a glance it seems that queries would get significantly more complex if you wish to take several properties of a vertex into account.
To insert in the 'embedded' mode you can do: https://github.com/google/cayley/wiki/Cayley-Go-API-(as-a-Li....
Join #cayley on freenode and https://groups.google.com/forum/#!forum/cayley-users and get help from our community.
https://github.com/GovernmentCommunicationsHeadquarters/Gaff...
From what I've seen, our use has a lot in common with Seed-DB, only in a different economic sector/activity.
Also, I know it's being used by some companies. you can ask directly the people who uses it on IRC - #cayley (freenode).
¹ https://www.arangodb.com/2015/10/benchmark-postgresql-mongod...
That is a huge drawback when compared to relational databases.
A good follow-up question would be: which open-source graph databases can reasonably import and store graph data that's not small -- that is, more data than fits in than RAM? Without proprietary extensions?
Let me explain this quotation. When your graph data (including indices) do no longer fit into the RAM of a single server, you can either live with the higher latency of loading data from disk or you can use sharding, which will lead to communication and therefore slower traversals.
That does not mean that things stop working, but performance will be less good, you can no longer visit tens of millions of nodes per second in a traversal as in RAM on a single server.
If you actually only traverse a much smaller hot subgraph, I would probably go for the disk based single server approach.
If your graph has a natural known clustering, then an optimized sharding solution with fine tuned sharding keys us probably your best bet.
You can do all this with ArangoDB.
However, graph traversals vary greatly in many respects, and your mileage may vary accordingly, with any approach.
I would love to chat in more detail about your use case.
Can easily load large to very large graphs.
A good example would be the graph of Wikipedia links. About 100 million edges among 5 million nodes, last I checked. The nodes have large differences in degree.
The raw data for this is not the slightest bit large. We're only talking about gigabytes. But it would absolutely destroy Neo4J to even try to import it, to say nothing of running an interesting algorithm that justifies using a graph database on it, and Neo4J seems to be everyone's favorite open-source graph database for some reason.
See previous discussion: https://news.ycombinator.com/item?id=11197880
There are more but these are opensource and I know them. And money more commercial ones.
Gun doesn't meet anyone's definition of "graph database" other than your own. If I load some JSON from a URL, and use lodash to pluck some data out of it, is it a graph database?
GUN can do efficient traversal and filtering, and this is going to be even better in our 0.5.x release with lexical cursor support.
By "anyone" do you mean Wikipedia's? https://en.m.wikipedia.org/wiki/Graph_database , because GUN does match its definition. Although we haven't implemented Dijkstra's.
I'm out in France right now and just boarded a plane to Slovenia, so I won't be able to reply again. Have a good one.
This is not what gun does. It alternately calls itself "the simplest database out there", "not a database" and "a distributed cache". It provides a mechanism for sharing a list of objects across multiple peers, but must transfer all of the data to each peer. It is conceptually similar to downloading a large chunk of JSON from a server and using lodash, ramda etc to query it, but no one would call that a graph database.
First part is matching the commonly accepted definition (the one that had been around for about 50 years). The second part is your own invention.
> This is not what gun does
I did not even have a chance to take a look at that product yet. So far I'm just puzzled by the graph database definition some people seem to be using in this thread.
And it makes the most sense. After all, as programmers we're rarely concerned about the layout of data in memory, but rather the abstract data type (ADT) that we have to work with. An ADT is defined not by it's memory layout (i.e., a set of vertices and a set of edges do not a graph make (set, of course, also being an ADT) -- there are several possible ways to represent a graph in memory), but by the operations that are defined for the data type and their characteristics (i.e., an adjacency relation (possibly along with an incidence relation) does a graph make). Of course, specialized traversal operations are more of a convenience than a necessity (and they typically allow greater performance than implementing solely in terms of the adjacency relation), but the point stands.
Consider that a list may be represented in several ways: cons cells, classes, closures (just to name a few). But for clients of the list, none of that really matters. It only matters if a list has certain operations: cons, car, cdr (or some equivalent interface). As far as clients are concerned, any object which provides the list interface is a list; inversely, any object which does not provide that interface is not a list.
In a relational database, it hardly matters how data are stored in memory. What matters is that they provide an interface that allows relational algebra (or some close approximation) to be performed on the data. Likewise, I'd argue that how a graph database stores its data is inconsequential, and the only requirement is that it expose graph operations on that data.
Otherwise, you can think of it as tradeoff, between expressiveness and computing speed (over an area of expertise) so really in between Memory Layout and ADT.
> In a relational database, it hardly matters how data are stored in memory.
Of course it does. It depends on where you want to optimise for speed.
> I'd argue that how a graph database stores its data is inconsequential, and the only requirement is that it expose graph operations on that data.
No. It makes different trade-offs for different purpose so it's not inconsequential.
GraphDB might be only a niche where only a few people have to use it. But still worth engineering because it help the ADT/expresiveness cause.
> I don't mean to imply that choice of data layout/representation doesn't matter at all, but that it doesn't matter for the purpose of deciding what constitutes a graph and distinguishing graphs from non-graph objects. Of course, as with any ADT, there are various trade-offs that need to be considered before deciding on a particular memory layout.
The beauty of ADTs is that once you've exposed your operations, you are free to change the memory layout without breaking clients -- or even to supply multiple structures with different layouts at the same time, each optimized for a different use case -- and in doing so, you never change the notion of what constitutes a graph.
None of such databases ever featured a query language capable of defining a Dijkstra algorithm.
And, no, for a typical use of a graph database, it matters most how cheap it is to follow a graph arc. Therefore, representation matters. Otherwise a graph interface on top of a relational storage would have been sufficient.
That doesn't contradict my view. In fact, I'd argue that it counts, due to the fact that graph operations are provided.
> None of such databases ever featured a query language capable of defining a Dijkstra algorithm.
Most modern graph databases do seem to feature some sort of query language. I won't argue that it's strictly necessary, as long as you have well-suited, well-defined operations on graphs. I can't speak to Dijkstra's algorithm -- that was a part of the thread that I overlooked previously.
> And, no, for a typical use of a graph database, it matters most how cheap it is to follow a graph arc. Therefore, representation matters. Otherwise a graph interface on top of a relational storage would have been sufficient.
I don't mean to imply that choice of data layout/representation doesn't matter at all, but that it doesn't matter for the purpose of deciding what constitutes a graph and distinguishing graphs from non-graph objects. Of course, as with any ADT, there are various trade-offs that need to be considered before deciding on a particular memory layout.
Yes, because Dijkstra is not what is the most interesting stuff to write against a graph in every day use. Dijkstra is a primitive than you use but that you have to tweak to solve the particular problem. What is the interest of optimizing writing that particular algorithm?
You seem to follow the idea that there is a super-algorithm to define the way mind works instead I think that's it many small algorithms with similar purpose.
I'd encourage you to look at the product and see whether it meets your definition.
But I've never seen a complex query language that would allow to express any complex traversal strategies (like Dijkstra algorithm), and from your wording I concluded that this was your requirement for something to be called a graph database.
The provenance was Cray Research -> SGI -> Tera/Cray according to those that have been around since the Cray Research days.
Source: err, I work here and asked a couple people a few cubes over. :)
The Sun deal was apparently more SGI wouldn't be caught dead with a supercomputer that ran on sparc so it got sold off to Sun.
Also, I made an hypergraphdb, atom-centered instead of hyperedge focused in Scheme https://github.com/amirouche/Culturia/blob/master/culturia/c....
Did you know that Gremlin, is only srfi-41 aka. stream API with a few graph centric helpers.
edit: it's srfi 41, http://srfi.schemers.org/srfi-41/srfi-41.html
http://www.cray.com/blog/how-cray-graph-engine-manages-graph...
My feeling is that graph databases are not suitable/ready for — for lack of a better term — the kind of document-like entity relationship graphs we typically use in webapps. Typical data models don't represent data as vertices and edges, but as entities with relationships ("foreign keys" in RDBMS nomenclature) embedded in the entities themselves.
This coincidentally applies to the relational model, in its most pure, formal, normal form, but the web development community has long established conventions of ORMing their way around this. The thing is, you shouldn't need an ORM with a graph database.
2-Instead, do graph DB engines try to break through bottlenecks for big data and analytics scenarios?
In fact, most (if not all) graph algorithms can be expressed using linear algebra (with specific addition and multiplication). And matrix multiplication is a select from two matrices, related with "where i=j" and aggregation over identical result coordinates.
The selection of multiplication and addition operations can account for different "data stored in links and nodes".
So there is no such dichotomy "graph vs relational".
Just because something can be done, doesn't mean it can be done easily or well. I've done a lot of work with relational databases, and I love them for a lot of data sets. But I also have done a lot of work with graph databases - and they make working with graph shaped data a pleasure. I could do a graph in SQL, it's even moderately straight-forward in postgres these days by using WITH RECURSIVE - but it's still not as simple as just loading orient or arango for those tasks.
It's the same reason I keep multiple knives in my kitchen. Sure I could do everything with an 8" chef's knife, but the paring knife and the boning knife just make some tasks easier.
I read that and implement my own version with SQL in < 500 lines of python code and found it just perfect for my own use cases. I can easily query any edges, notes in web speed ( < 10 ms) from databases with millions of nodes, edges, GBs of info.
I am curious what I might be missing with that approach as compare to a real graph database?
If I need more info for particular "Edge type", I just add new Node entry type "Edge_info" that link the Edge type to a JSON that content such info. I found that very flexible, but I have not used any real graph database.
I am part of the team developing Russian CAD system [0]. It uses what one can consider a hypergraph db (relation includes many objects), but that DBMS system has queries on par with SQL. And they prove themselves very useful in development of CAD.
What you describe can be explained with development inertia. Most CADs are C/C++ and these languages are not very well suited for changes that go through all code base (change of storage engine and data model).
I also made experiments during a dev of graph analytics engine in one part of my experience. The relational model (actually, linear algebra model) has proven itself very competitive. It allows for easy distribution of data, the operations over distributed data are close to optimal, etc, etc.
[0] http://dd.ru/
Keep in mind that in such a CAD designs are huge. Think of an aircraft carrier scale of "huge". And it was designed when memory was very limited. Therefore, pretty much all the CAD operations depended on the database access.
So, nobody really cared about the queries, they were insignificant. What people cared about was:
* Performance of following an arc
* Transactions
* Data consistency
* Compactness of representation (remember, disk space is also a limited thing when you're building aircraft carriers).
* Nice API (even in a very limited language)
You tell us about some old project, written in hard to maintain languages, which had many failures to adapt to new tech. This is exactly what to expect.
I am talking about relatively modern language (C#) using good DB tech (lagging about seven, maybe five years from the state of art). Maybe, the story will be different in our case.
Fundamentally nothing changed in the relational storage. Follow-a-graph-edge operation is as expensive as it used to be (involves an index lookup, it cannot be cheap).
If you know a relational arrangement suitable for a cheap O(1) edge traversal - please share. But I am very skeptical.
And I cannot see how the host language is relevant at all. C#, Haskell, whatever - none can make data access operations cost less than what the data model predicts.
I cannot help but feel that what you describe is a classic example of technical inertia due to massive technical debt. It cannot prove that relational DBs are bad for CADs.
As for the bulk operations, they're in most cases totally useless. Rendering - maybe, but most of the other CAD operations require precise edge following.
And why even going into all the troubles with using this totally unsuitable relational representation when a proper graph dbms is so much easier? Relational religion is so funny, almost as funny as OOP.
You can look at these indices as O(1) operations. Btrees are just like that.
(if you think that memory access is O(1), you are wrong)
Graph DBs, more often than not, are ad hoc bug ridden slow poor implementation of one tenth of relatively complete implementation of relational DB.
CSG, place and route (pipes, cables, etc.), design constraint checks, all that stuff.
> I bet they follow many links from nodes (note the plural!) in most of them.
Not that many, mostly single-digit numbers.
> This is true for scheme/PCB editor
Which is very, very different from an oil refinery or an aircraft carrier. Both in a scale and typical operations.
> You can look at these indices as O(1) operations. Btrees are just like that.
WAT?!? Not even close. O(log n) at best. And a multiplier there is huge.
> Graph DBs, more often than not, are ad hoc bug ridden slow poor implementation of one tenth of relatively complete implementation of relational DB.
What?
Graph DBs are orders of magnitude simpler than any relational pile of a mess. It's really hard to screw them up. Everything is trivial there, including transactions, logging, referential transparency and all that.
Now I'll leave conversation. We clearly have different view on almost everything, including, but not limited to "huge multipliers".
Your argument is effectively because Haskell can be implemented in C, there is a false dichotomy between the two languages.