4 ms·

It introduces false dichotomy "graph vs relational". In fact, most (if not all) graph algorithms can be expressed using linear algebra (with specific addition

by thesz 11y ago

It introduces false dichotomy "graph vs relational". 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".

grandalf 11y ago
True but highly irrelevant to why anyone might choose to use a graph database (or choose not to use one in favor of a relational database)...
sklogic 11y ago
Of course you can express anything on top of a relational model. But for graphs such a representation would have been awfully inefficient. For this reason, CADs never even tried to switch to a relational data storage once that fancy new relational databases appeared, most of the professional CADs are still using good old graph databases.
- thesz 11y ago
  I beg to disagree. 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/ http://dd.ru/
  - sklogic 11y ago
    I worked on a (very old) ship-building and factory-building CAD, written mostly in PL/I and Fortran. It was built around a graph database. Throughout its long and turbulent history, there were many attempts of moving to a relational storage, every time resulting in orders of magnitude drop in performance. 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)
    - thesz 11y ago
      Had the state of art changed from the time of their last attempt to move to relational DB? Had the hardware changed during that time? 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.
      - sklogic 11y ago
        The last attempt was made in around 2008, AFAIR. 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.
        thesz 11y ago
        Use covering indices for edges, it is vastly cheaper than regular indices. Choose write-optimized storage layer (fractal indices (circa ~2007, BTW!), LSM) for DB. Don't do singular accesses, use bulk accesses (and now we hit the wall of PL/1 and Fortran you mentioned). I can go on. 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.
sophacles 11y ago
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 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.
- tkinom 11y ago
  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 < 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?
  - sophacles 11y ago
    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".
    - tkinom 11y ago
      I implemented a table for Nodes, one for Edges. The Nodes table has an entry for JSON for that Nodes. 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.
cbsmith 11y ago
linear algebra != relational calculus Your argument is effectively because Haskell can be implemented in C, there is a false dichotomy between the two languages.

by thesz 11y ago

grandalf 11y ago

True but highly irrelevant to why anyone might choose to use a graph database (or choose not to use one in favor of a relational database)...

sklogic 11y ago

Of course you can express anything on top of a relational model. But for graphs such a representation would have been awfully inefficient. For this reason, CADs never even tried to switch to a relational data storage once that fancy new relational databases appeared, most of the professional CADs are still using good old graph databases.

thesz 11y ago
I beg to disagree. 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/ http://dd.ru/
- sklogic 11y ago
  I worked on a (very old) ship-building and factory-building CAD, written mostly in PL/I and Fortran. It was built around a graph database. Throughout its long and turbulent history, there were many attempts of moving to a relational storage, every time resulting in orders of magnitude drop in performance. 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)
  - thesz 11y ago
    Had the state of art changed from the time of their last attempt to move to relational DB? Had the hardware changed during that time? 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.
    - sklogic 11y ago
      The last attempt was made in around 2008, AFAIR. 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.
      - thesz 11y ago
        Use covering indices for edges, it is vastly cheaper than regular indices. Choose write-optimized storage layer (fractal indices (circa ~2007, BTW!), LSM) for DB. Don't do singular accesses, use bulk accesses (and now we hit the wall of PL/1 and Fortran you mentioned). I can go on. 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.

sophacles 11y ago

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

tkinom 11y ago
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 < 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?
- sophacles 11y ago
  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".
  - tkinom 11y ago
    I implemented a table for Nodes, one for Edges. The Nodes table has an entry for JSON for that Nodes. 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.

cbsmith 11y ago

linear algebra != relational calculus Your argument is effectively because Haskell can be implemented in C, there is a false dichotomy between the two languages.