Degrees of Kevin Bacon Using Postgres(crunchydata.com)

https://www.crunchydata.com/blog/six-degrees-of-kevin-bacon-postgres-style

19 comments

They call the dijkstra implementation slow but that's because they aren't using the full information it presents. Dijkstra gives shortest paths from one node to every other node in the graph, so you run it once and materialize it and now you have a full Kevin Bacon database

compsciphd2 anni fa

Eh? you have a full graph of one node to every other node. not shortest path between every pair (which I assume is what a full kevin bacon database would be).

its_bbq2 anni fa

Yes I meant specifically for Kevin Bacon. There are other all pairs shortest paths algorithms besides running Dijkstra N times

compsciphd2 anni fa

oh that's true, for some reason I was thinking path from A->Bacon. But dijkstra from Bacon->A is just as computational intensive and much more valuable to keep around.

ant6n2 anni fa

But there's only one Kevin Bacon.

I mean there's also Erdos, but that's a different story.

its_bbq2 anni fa

Erdos-Bacon number is a join and sum ;)

jtwaleson2 anni fa

Couldn’t you “just” create a nullable distance column and update anything that’s null and reachable by Bacon and set it to 1. Then update anyone still null and reachable by 1 to 2, etc. Then you have a materialized view of everyone’s Bacon number.

Not a generic solution of course, but seems extremely effective for the Bacon case.

mdp20212 anni fa

Very, very good: perfect for didactic. I thought I'd try this on SQLite, but I am in a rush right now... So I checked the documentation to refresh my memory about the extent of relevant SQL implementation in SQLite, and...

TIL that the 'WITH' clause in SQLite can draw the classic Mandelbrot Set:

https://www.sqlite.org/lang_with.html#outlandish_recursive_q...

(And there is a Sudoku puzzle solver below that.)

jnordwick2 anni fa

Now do the Erdos number: defined the same way but for coauthors of papers linked to the absurdly production (and always high on amphetamines) great Paul Erdos. The most glorious of all, the Erdos-Bacon number, is defined as the sum of your Bacon number and Erdos number.

Mathematicians Daniel kleitman and Bruce Reznik both tie for top spot with a number of 3 (Erdos 1s and Bacon 2s). Danica McKellar and Elon both in there with 6s. And Mayim Bialik, Natalie Portman, and Kristen Stewart all up there with 7s.

https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Bacon_numbe...

mr_mitm2 anni fa

My ex had an erdos-bacon number of six or seven when she was in grad school. One paper with your thesis advisor and having one role as an extra gets you there quickly.

robryk2 anni fa

I don't see why one has to create the actor-actor relation table. I would rather search for shortest paths in the bipartite graph where nodes are movies and actors, and divide the results by 2.

harel2 anni fa

That's all very cool. As an aside I always remembered the bacon number was between Bacon and anyone else, Hollywood actor or not. Keeping it withing Hollywood makes a lot more sense.

defrost2 anni fa

Hollywood bleeds out across the boundaries, quoting the Head of the Theoretical Physics Group at Imperial College (2011-2016):

    I have an Erdos-Bacon number of six (having written a paper with Shing-Tung Yau and appeared in the film Windrider with Nicole Kidman).

https://profiles.imperial.ac.uk/j.gauntlett

orthoxerox2 anni fa

Oracle's CONNECT BY is much easier to write and understand than recursive CTE. It's a pity it's not standart.

anotherevan2 anni fa

For slow changing, read-heavy scenarios like this, make your recursive CTE a materialised view and whack some indexes on it for big performance gains.

[deleted]2 anni fa

mr_mitm2 anni fa

Is there something like Cypher that can be leveraged to make the queries against a postgres graph a bit more digestible?

[deleted]2 anni fa

willf2 anni fa

Let’s normalize recursive CTEs.