5 ms·

Thanks for the response. I'm having trouble seeing what kinds of queries come up of this nature that SQL wouldn't be fit for, though. What would be an example o

Thanks for the response. I'm having trouble seeing what kinds of queries come up of this nature that SQL wouldn't be fit for, though. What would be an example of a realistic graph query one would want to do that would be too difficult to do in SQL?

zaphar 7y ago
Graphs have arbitrary depth. As a result some queries need an unknown number of joins on an unknown number of keys. Representing this in just SQL would be impossible. You could do it in a stored procedure but that is a superset of SQL not vanilla SQL. You can also do it by just making the SQL calls over and over in your code as you get each row but that's not going to be very optimized.
- deleted 7y ago
  [deleted]
pcl 7y ago
Let's assume we're playing the Kevin Bacon game. We've got actors, movies, and roles. Here's some sample data: INSERT INTO actors (id, name) VALUES (1, 'Kevin Bacon') INSERT INTO actors (id, name) VALUES (2, 'Frank Langella') INSERT INTO actors (id, name) VALUES (3, 'Cameron Diaz') INSERT INTO movies (id, name) VALUES (1, 'The Box') INSERT INTO movies (id, name) VALUES (2, 'Frost/Nixon') INSERT INTO roles (movie_id, actor_id) VALUES (1, 2) INSERT INTO roles (movie_id, actor_id) VALUES (1, 3) INSERT INTO roles (movie_id, actor_id) VALUES (2, 1) INSERT INTO roles (movie_id, actor_id) VALUES (2, 2) Given the above data model, it's not possible to select all the actors that are within 6 degrees of Kevin Bacon with a SQL statement. (Data from the incredible Oracle of Bacon, which uses custom graph traversal to serve up results: https://oracleofbacon.org/how.php https://oracleofbacon.org/how.php)
- irishsultan 7y ago
  It may not be obvious, but it should be possible. It's relatively easy to get those within 1 degree of separation, put that in a view, then repeat that, but instead of hardcoding Kevin Bacon do "within 1 degree of those within 1 degree of Kevin bacon". Repeat a few more times and you have your query. Of course if you want to know the degree between two random actors, or all actors within n degrees of Kevin Bacon (where n is unknown ahead of time) then it becomes really difficult (potentially still possible using common table expressions though).
  - pcl 7y ago
    Yes -- put more clearly, it's not possible in the relational calculus to fetch the number of degrees of separation between two actors.
  - waffle_ss 7y ago
    It’s possible with recursive CTEs, but very slow. https://stackoverflow.com/questions/52674380/improving-postgres-performance-on-graph-like-queries-of-multi-level-self-joins https://stackoverflow.com/questions/52674380/improving-postg...
    - kyllo 7y ago
      There's nothing essentially, inherently slower about recursive CTEs in SQL databases compared to graph database queries, it depends how they're implemented, particularly whether they take advantage of indexing and caching. They're both going to be doing fundamentally the same type of algorithm under the hood. I've gotten recursive CTEs in SQL Server to perform quite well just by indexing the join key columns.
      - johnymontana 7y ago
        Graph databases like Neo4j have a very important performance characteristic called "index-free adjacency". This means that a traversal from node to node (similar to a JOIN in a relational database) does NOT use an index. Instead, it's more like chasing pointers, jumping directly to an offset. Whereas relational databases do use an index to perform JOINS - it's essentially a set comparison, using an index to see where two sets overlap. What this means is that the performance of joins in relational databases is dependent on the overall size of the tables, while the performance of traversals in a graph database that implements index-free adjacency is not dependent on the overall size of the data (rather just the connectedness of the nodes being traversed), because an index is not used for traversals.
        twic 7y ago
        There's no reason that a relational database couldn't also have index-free adjacency. Alongside every foreign key, you store a file pointer to the row with that key. I assume that the reason relational databases don't do this is that the speedup isn't worth the complexity and performance cost of keeping those pointers up to date for the kinds of queries that relational databases usually do.
- seanhunter 7y ago
  This is an elegant and simple formulation of the problem and shows how bad SQL is at this. However, you can do this in SQL. with recursive bacon_movies as ( select a.id as actor_id , 0 as bacon_degree from actors a where a.name = 'Kevin Bacon' union select r1.actor_id , b.bacon_degree + 1 as bacon_degree from bacon_movies b join roles r on r.actor_id = b.actor_id join roles r1 on r.movie_id = r1.movie_id and r1.actor_id <> b.actor_id where b.bacon_degree < 6 ) select a.name , min(b1.bacon_degree) as bacon_degree from bacon_movies b1 join actors a on a.id = b1.actor_id group by a.name order by bacon_degree asc; ...not saying it's a good way to do this
  - tossAfterUsing 7y ago
    jfc... sql :( i've written thousands of lines of cypher queries. i just can't do sql though, it's not like i refuse either... it's that my brain just doesn't get it. practice would surely help. i took an intro class once, and that improved my skills a lot (i.e. 0 -> 0.1)... teaching about the math of what's being done and giving me some ways to think about it... but it all just seems so incredibly tedious.
  - taffer 7y ago
    > ...not saying it's a good way to do this It really depends. If you do these kinds of queries all the time, it's a good idea to use a graph DB, but if these queries are rare, it often doesn't make sense to add a new technology to your project.
  - bcoates 7y ago
    Maybe I have the brainworms from too much SQL but that seems pretty fine? It's an idiomatic CTE that more or less directly translates back to the problem statement. (nitpick: I'd exclude already-found rows from the union to do shortest-path in the CTE instead of doing it later)
kyllo 7y ago
Anything where you need transitive closure, that is, you need all the nodes that are reachable from a given starting node. You can do it in SQL dialects that support recursive common table expressions. In a previous job, I dealt with Bill of Materials data, which basically a parts list for a hardware product. Parts contain other parts, which contain other parts, and so on, recursively. The data was in SQL Server. I could have moved the data to Neo4j and gotten a much more concise and convenient syntax for traversing the parent-child relationships. But I decided it wasn't worth the trouble of moving data, so I bit the bullet and just wrote the recursive CTE in SQL. That's the biggest problem with graph databases. If your data's already in a SQL database, it often isn't worth it to _move all your data_ just to get a better query syntax.
- mehrdadn 7y ago
  Huh, interesting, thanks!
giardini 7y ago
Here's the classic and humorous letter critical of relational databases (RDBMS) penned in 1991 by Henry Baker and published in the Communications of the ACM: http://home.pipeline.com/~hbaker1/letters/CACM-RelationalDatabases.html http://home.pipeline.com/~hbaker1/letters/CACM-RelationalDat... Almost an "RDBMS Considered Harmful" screed, Baker's letter may seem humorous in today's environment and even ludicrous to those who did not live through the transition from older file-systems/DBMS to RDBMS. To those of us who did experience that transition, Baker was painfully on-point and his letter served as a scourge to improve systems performance for more than a decade beyond that period. More recently the major RDBMS vendors have complemented SQL with directives that address the storage and handling of hierarchical data, e.g., in POSTGRESQL: https://www.technobytz.com/closure_table_store_hierarchical_data.html https://www.technobytz.com/closure_table_store_hierarchical_... Baker was no prophet: his letter showed high hopes for object-oriented databases, another technology that noisily rose and quietly fell in popularity.
- taffer 7y ago
  > More recently the major RDBMS vendors have complemented SQL with directives that address the storage and handling of hierarchical data Oracle could do that 30 years ago, and recursive CTEs are part of SQL:1999.

zaphar 7y ago

Graphs have arbitrary depth. As a result some queries need an unknown number of joins on an unknown number of keys. Representing this in just SQL would be impossible. You could do it in a stored procedure but that is a superset of SQL not vanilla SQL. You can also do it by just making the SQL calls over and over in your code as you get each row but that's not going to be very optimized.

deleted 7y ago
[deleted]

pcl 7y ago

Let's assume we're playing the Kevin Bacon game. We've got actors, movies, and roles. Here's some sample data: INSERT INTO actors (id, name) VALUES (1, 'Kevin Bacon') INSERT INTO actors (id, name) VALUES (2, 'Frank Langella') INSERT INTO actors (id, name) VALUES (3, 'Cameron Diaz') INSERT INTO movies (id, name) VALUES (1, 'The Box') INSERT INTO movies (id, name) VALUES (2, 'Frost/Nixon') INSERT INTO roles (movie_id, actor_id) VALUES (1, 2) INSERT INTO roles (movie_id, actor_id) VALUES (1, 3) INSERT INTO roles (movie_id, actor_id) VALUES (2, 1) INSERT INTO roles (movie_id, actor_id) VALUES (2, 2) Given the above data model, it's not possible to select all the actors that are within 6 degrees of Kevin Bacon with a SQL statement. (Data from the incredible Oracle of Bacon, which uses custom graph traversal to serve up results: https://oracleofbacon.org/how.php https://oracleofbacon.org/how.php)

irishsultan 7y ago
It may not be obvious, but it should be possible. It's relatively easy to get those within 1 degree of separation, put that in a view, then repeat that, but instead of hardcoding Kevin Bacon do "within 1 degree of those within 1 degree of Kevin bacon". Repeat a few more times and you have your query. Of course if you want to know the degree between two random actors, or all actors within n degrees of Kevin Bacon (where n is unknown ahead of time) then it becomes really difficult (potentially still possible using common table expressions though).
- pcl 7y ago
  Yes -- put more clearly, it's not possible in the relational calculus to fetch the number of degrees of separation between two actors.
- waffle_ss 7y ago
  It’s possible with recursive CTEs, but very slow. https://stackoverflow.com/questions/52674380/improving-postgres-performance-on-graph-like-queries-of-multi-level-self-joins https://stackoverflow.com/questions/52674380/improving-postg...
  - kyllo 7y ago
    There's nothing essentially, inherently slower about recursive CTEs in SQL databases compared to graph database queries, it depends how they're implemented, particularly whether they take advantage of indexing and caching. They're both going to be doing fundamentally the same type of algorithm under the hood. I've gotten recursive CTEs in SQL Server to perform quite well just by indexing the join key columns.
    - johnymontana 7y ago
      Graph databases like Neo4j have a very important performance characteristic called "index-free adjacency". This means that a traversal from node to node (similar to a JOIN in a relational database) does NOT use an index. Instead, it's more like chasing pointers, jumping directly to an offset. Whereas relational databases do use an index to perform JOINS - it's essentially a set comparison, using an index to see where two sets overlap. What this means is that the performance of joins in relational databases is dependent on the overall size of the tables, while the performance of traversals in a graph database that implements index-free adjacency is not dependent on the overall size of the data (rather just the connectedness of the nodes being traversed), because an index is not used for traversals.
      - twic 7y ago
        There's no reason that a relational database couldn't also have index-free adjacency. Alongside every foreign key, you store a file pointer to the row with that key. I assume that the reason relational databases don't do this is that the speedup isn't worth the complexity and performance cost of keeping those pointers up to date for the kinds of queries that relational databases usually do.
seanhunter 7y ago
This is an elegant and simple formulation of the problem and shows how bad SQL is at this. However, you can do this in SQL. with recursive bacon_movies as ( select a.id as actor_id , 0 as bacon_degree from actors a where a.name = 'Kevin Bacon' union select r1.actor_id , b.bacon_degree + 1 as bacon_degree from bacon_movies b join roles r on r.actor_id = b.actor_id join roles r1 on r.movie_id = r1.movie_id and r1.actor_id <> b.actor_id where b.bacon_degree < 6 ) select a.name , min(b1.bacon_degree) as bacon_degree from bacon_movies b1 join actors a on a.id = b1.actor_id group by a.name order by bacon_degree asc; ...not saying it's a good way to do this
- tossAfterUsing 7y ago
  jfc... sql :( i've written thousands of lines of cypher queries. i just can't do sql though, it's not like i refuse either... it's that my brain just doesn't get it. practice would surely help. i took an intro class once, and that improved my skills a lot (i.e. 0 -> 0.1)... teaching about the math of what's being done and giving me some ways to think about it... but it all just seems so incredibly tedious.
- taffer 7y ago
  > ...not saying it's a good way to do this It really depends. If you do these kinds of queries all the time, it's a good idea to use a graph DB, but if these queries are rare, it often doesn't make sense to add a new technology to your project.
- bcoates 7y ago
  Maybe I have the brainworms from too much SQL but that seems pretty fine? It's an idiomatic CTE that more or less directly translates back to the problem statement. (nitpick: I'd exclude already-found rows from the union to do shortest-path in the CTE instead of doing it later)

kyllo 7y ago

Anything where you need transitive closure, that is, you need all the nodes that are reachable from a given starting node. You can do it in SQL dialects that support recursive common table expressions. In a previous job, I dealt with Bill of Materials data, which basically a parts list for a hardware product. Parts contain other parts, which contain other parts, and so on, recursively. The data was in SQL Server. I could have moved the data to Neo4j and gotten a much more concise and convenient syntax for traversing the parent-child relationships. But I decided it wasn't worth the trouble of moving data, so I bit the bullet and just wrote the recursive CTE in SQL. That's the biggest problem with graph databases. If your data's already in a SQL database, it often isn't worth it to _move all your data_ just to get a better query syntax.

mehrdadn 7y ago
Huh, interesting, thanks!

giardini 7y ago

Here's the classic and humorous letter critical of relational databases (RDBMS) penned in 1991 by Henry Baker and published in the Communications of the ACM: http://home.pipeline.com/~hbaker1/letters/CACM-RelationalDatabases.html http://home.pipeline.com/~hbaker1/letters/CACM-RelationalDat... Almost an "RDBMS Considered Harmful" screed, Baker's letter may seem humorous in today's environment and even ludicrous to those who did not live through the transition from older file-systems/DBMS to RDBMS. To those of us who did experience that transition, Baker was painfully on-point and his letter served as a scourge to improve systems performance for more than a decade beyond that period. More recently the major RDBMS vendors have complemented SQL with directives that address the storage and handling of hierarchical data, e.g., in POSTGRESQL: https://www.technobytz.com/closure_table_store_hierarchical_data.html https://www.technobytz.com/closure_table_store_hierarchical_... Baker was no prophet: his letter showed high hopes for object-oriented databases, another technology that noisily rose and quietly fell in popularity.

taffer 7y ago
> More recently the major RDBMS vendors have complemented SQL with directives that address the storage and handling of hierarchical data Oracle could do that 30 years ago, and recursive CTEs are part of SQL:1999.