4 ms·

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 ins

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.
      - dragonwriter 7y ago
        OTOH, 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.
      - tossAfterUsing 7y ago
        interviewed with a know-it-all type sr. engineer once, and he asked me an incredibly defensive question like, "why would i use a graph database instead of postgresql, it cant do anything that can't be done in postgres!?!?" i'm no expert on any of this, but my response was still sufficient to get hired: you don't need a graph db, but it's easier to understand what cypher is doing than what sql is doing... that means more productivity to your lower-cost junior developers.
      - AndrewBowman 7y ago
        There is a older, but seemingly relevant, question/answer for this on stack overflow: https://stackoverflow.com/a/5611541/92359 https://stackoverflow.com/a/5611541/92359 > if you shrink a table, or update a partitioned table (causing a row to move to another partition) or if you are rebuilding a table, or export/import a table, or... or... or... the rowid will change. If the rowids are not stable across db operations, it wouldn't make sense to use them for implementing index-free adjacency. Do any alternatives remain? If not you're back to joins. One of the reasons why Neo4j can use index-free adjacency is that the ids used for nodes and relationships are pointers to the location of the nodes and relationships in the relevant store files. Those are stable across updates and deletes of other data, and when you delete a node, all its relationships must be deleted first so there are no hanging relationships.
  - waffle_ss 7y ago
    It's inherently slower because of the explosion in join table size as your depth increases and the slowness of using b-tree indexes instead of direct pointers to neighbor nodes ("index-free adjacency") or the newer sparse matrix transforms (GraphBLAS) that graph databases use. What kind of database sizes have you used in your SQL Server experience? The linked StackOverflow question uses Postgres with 1M records, 50M relationships, and does index the join key columns. Maybe I'll have to replicate it on SQL Server in case there's some secret sauce but I'm highly skeptical.
    - benkrug 7y ago
      Here's a super-basic test using MySQL CTEs w/1.6M nodes and 30M edges that I did a few years ago - https://intertubes.wordpress.com/2017/11/28/benchmarketing-neo4j-and-mysql/ https://intertubes.wordpress.com/2017/11/28/benchmarketing-n...
      - taffer 7y ago
        There is also this [1] paper claiming that > [...] solutions using relational database technology [...] can offer performance superior to that of the dedicated graph databases. [1] https://event.cwi.nl/grades2013/07-welc.pdf https://event.cwi.nl/grades2013/07-welc.pdf
        AndrewBowman 7y ago
        Note that this is an old paper. They are using Neo4j 1.8.2 for this (and the community version at that), which was released in February of 2013. Neo4j is at 3.5.9 currently, with 4.0 on the horizon, so there have been 2 major releases, nearly 3, since the paper, and dozens of minor releases and patch releases. I'm sure Oracle has been making improvements as well (all of the authors are from Oracle), so in any case the paper itself is too outdated to be useful.
        taffer 7y ago
        The benchmark [1] that Neo4j uses in its advertising [2] is from 2014, so not much newer either. [1]: https://github.com/opencredo/neo4j-in-action https://github.com/opencredo/neo4j-in-action [2]: https://neo4j.com/business-edge/connected-data-cripples-relational-performance/ https://neo4j.com/business-edge/connected-data-cripples-rela...

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.
    - dragonwriter 7y ago
      OTOH, 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.
    - tossAfterUsing 7y ago
      interviewed with a know-it-all type sr. engineer once, and he asked me an incredibly defensive question like, "why would i use a graph database instead of postgresql, it cant do anything that can't be done in postgres!?!?" i'm no expert on any of this, but my response was still sufficient to get hired: you don't need a graph db, but it's easier to understand what cypher is doing than what sql is doing... that means more productivity to your lower-cost junior developers.
    - AndrewBowman 7y ago
      There is a older, but seemingly relevant, question/answer for this on stack overflow: https://stackoverflow.com/a/5611541/92359 https://stackoverflow.com/a/5611541/92359 > if you shrink a table, or update a partitioned table (causing a row to move to another partition) or if you are rebuilding a table, or export/import a table, or... or... or... the rowid will change. If the rowids are not stable across db operations, it wouldn't make sense to use them for implementing index-free adjacency. Do any alternatives remain? If not you're back to joins. One of the reasons why Neo4j can use index-free adjacency is that the ids used for nodes and relationships are pointers to the location of the nodes and relationships in the relevant store files. Those are stable across updates and deletes of other data, and when you delete a node, all its relationships must be deleted first so there are no hanging relationships.
- waffle_ss 7y ago
  It's inherently slower because of the explosion in join table size as your depth increases and the slowness of using b-tree indexes instead of direct pointers to neighbor nodes ("index-free adjacency") or the newer sparse matrix transforms (GraphBLAS) that graph databases use. What kind of database sizes have you used in your SQL Server experience? The linked StackOverflow question uses Postgres with 1M records, 50M relationships, and does index the join key columns. Maybe I'll have to replicate it on SQL Server in case there's some secret sauce but I'm highly skeptical.
  - benkrug 7y ago
    Here's a super-basic test using MySQL CTEs w/1.6M nodes and 30M edges that I did a few years ago - https://intertubes.wordpress.com/2017/11/28/benchmarketing-neo4j-and-mysql/ https://intertubes.wordpress.com/2017/11/28/benchmarketing-n...
    - taffer 7y ago
      There is also this [1] paper claiming that > [...] solutions using relational database technology [...] can offer performance superior to that of the dedicated graph databases. [1] https://event.cwi.nl/grades2013/07-welc.pdf https://event.cwi.nl/grades2013/07-welc.pdf
      - AndrewBowman 7y ago
        Note that this is an old paper. They are using Neo4j 1.8.2 for this (and the community version at that), which was released in February of 2013. Neo4j is at 3.5.9 currently, with 4.0 on the horizon, so there have been 2 major releases, nearly 3, since the paper, and dozens of minor releases and patch releases. I'm sure Oracle has been making improvements as well (all of the authors are from Oracle), so in any case the paper itself is too outdated to be useful.
        taffer 7y ago
        The benchmark [1] that Neo4j uses in its advertising [2] is from 2014, so not much newer either. [1]: https://github.com/opencredo/neo4j-in-action https://github.com/opencredo/neo4j-in-action [2]: https://neo4j.com/business-edge/connected-data-cripples-relational-performance/ https://neo4j.com/business-edge/connected-data-cripples-rela...