3 ms·
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, 'Ke
by 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 agoIt 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 agoYes -- 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 agoIt’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 agoThere'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 agoGraph 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 agoThere'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.
- dragonwriter 7y agoOTOH, if you could have it opt-in on a per-FK basis in an RDBMS, the cost could be avoided where not needed, but the performance benefit available where needed.
- seanhunter 7y agoThis 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 agojfc... 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 agoMaybe 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)