Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Graph Databases 101

cray.com

Post reply on HN
Print view View original

81–90 of 107 posts

Re: Graph Databases 101

#81

Post by amirouche »

rspeer wrote: post #63
grandalf wrote: post #61

Earlier quoted context omitted.

Explain

ConceptNet [1] started out as an academic project that I was responsible for for a while. Since then I've left to start a company but I still maintain ConceptNet and build lots of stuff on it. [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 awf…

Knowing the ConceptNet project a little, still I don't understand the workload/algorithms you run on the database. Otherwise said, «this doesn't work for us» doesn't help anybody.

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

Re: Graph Databases 101

#82

Post by amirouche »

groovy2shoes wrote: post #54
sklogic wrote: post #43

Earlier quoted context omitted.

> a database which can efficiently represent graphs and offers functionality for traversing them 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 usin…

I only just discovered graph databases a few years ago, so I have no idea what the definition of "graph database" was in ye olde days, but the parent's definition is the only one I'm familiar with. 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 layo…

> 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

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.

Re: Graph Databases 101

#83

Post by grandalf »

rspeer wrote: post #63
grandalf wrote: post #61

Earlier quoted context omitted.

Explain

ConceptNet [1] started out as an academic project that I was responsible for for a while. Since then I've left to start a company but I still maintain ConceptNet and build lots of stuff on it. [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 awf…

It's interesting. I suppose most graph db operations could be easily enough broken down into a series of steps that could be performed in a more scalable but slower way.

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.

Re: Graph Databases 101

#84

Post by groovy2shoes »

sklogic wrote: post #69
groovy2shoes wrote: post #54

Earlier quoted context omitted.

I only just discovered graph databases a few years ago, so I have no idea what the definition of "graph database" was in ye olde days, but the parent's definition is the only one I'm familiar with. 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 layo…

A typical graph dbms exposes a node selection (often only allowing to start at a single entry node or selecting a set of nodes by tags) and arc selection / filtering. Given that they were mostly used for CADs such an interface makes a lot of sense. 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 i…

> A typical graph dbms exposes a node selection (often only allowing to start at a single entry node or selecting a set of nodes by tags) and arc selection / filtering.

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.

Re: Graph Databases 101

#85

Post by amirouche »

sklogic wrote: post #69
groovy2shoes wrote: post #54

Earlier quoted context omitted.

I only just discovered graph databases a few years ago, so I have no idea what the definition of "graph database" was in ye olde days, but the parent's definition is the only one I'm familiar with. 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 layo…

A typical graph dbms exposes a node selection (often only allowing to start at a single entry node or selecting a set of nodes by tags) and arc selection / filtering. Given that they were mostly used for CADs such an interface makes a lot of sense. 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 i…

> None of such databases ever featured a query language capable of defining a Dijkstra algorithm.

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.

Re: Graph Databases 101

#86

Post by phpnode »

sklogic wrote: post #70
phpnode wrote: post #46

Earlier quoted context omitted.

perhaps this is a terminology issue, I'll admit that I'm too young to have used pre-relational graph databases, but presumably they have a way of navigating / jumping between documents/vertices, (presumably based on pointers), otherwise what point would there be in having a graph? I'd encourage you to look at the product and see whether it meets your definition.

Yes, of course you could always select a node (often you'd always have to start from a single root node), select arcs, filter the arcs by some criteria, etc. 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.

Query language isn't a requirement but exposing the capability to do those kinds of selects / filtering operations is. It doesn't have to support Dijkstra's algorithm but it should be possible to implement it (efficiently).

Re: Graph Databases 101

#87

Post by groovy2shoes »

amirouche wrote: post #82
groovy2shoes wrote: post #54

Earlier quoted context omitted.

I only just discovered graph databases a few years ago, so I have no idea what the definition of "graph database" was in ye olde days, but the parent's definition is the only one I'm familiar with. 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 layo…

> 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 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 stor…

I see now that I didn't make this clear in my comment, but I'll reproduce part of my reply to the sibling:

> 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.

Re: Graph Databases 101

#88

Post by lobster_johnson »

I've seen people using graph databases as a general-purpose backing store for webapps/microservices. What are people's opinions about this?

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.

Re: Graph Databases 101

#89

Post by sophacles »

tkinom wrote: post #77
sophacles wrote: post #58

Earlier quoted context omitted.

Strictly speaking yeah. Practically speaking: Not really true. 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 pos…

Facebook has a very good paper descriptions on how they do graph on top of relational database. Google "facebook tao" for details. I read that and implement my own version with SQL in I am curious what I might be missing with that approach as compare to a real graph database?

From my quick read of tao, it seems to be doing essentially what graph databases do but with the data storage layer being in sql rather than some other object store. And with the interface layer being not quite as feature complete. So the query layer in tao seems to lack a way to follow multiple edges without first returning to the application code, which graph dbs present as a native feature. The other thing that's lacking, which some graph dbs provide, is labeled edges - that is edges that contain data besides just an "edge type".

Re: Graph Databases 101

#90

Post by espeed »

akarambir wrote: post #71
rspeer wrote: post #63

Earlier quoted context omitted.

ConceptNet [1] started out as an academic project that I was responsible for for a while. Since then I've left to start a company but I still maintain ConceptNet and build lots of stuff on it. [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 awf…

Can you explain how you were using PostgreSQL as Graph Database?

FYI: See this recent paper by Google Research and IBM Watson Research:

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

Post reply on HN