DBA

Graph – Shortest Path

‘Shortest path’ is by far the most feature of SQL Graph for now. What does this even mean?

‘Shortest path’ is the term accorded to the shortest distance between any two points, referred to as nodes in graph databases. The algorithm that helps you find the shortest distance between node A and node B is called the Shortest Path Algorithm.

Let us go back to the movie database. We have two people, say Amrish Puri and Harrison Ford. Amrish wants to meet Harrison Ford. He has not acted with Ford, he may have a few connections in common – or people who know him. Or people who know him who know him. This is one way to get an introduction. Or, let us say you are interviewing for a job. You want to see if someone in your network works at that place – so that you can get an idea of what the job or the company is like. So you go on linkedin – do a search for the company, look under ‘people’, and it tells you if anyone in your network is there, or someone is 2 levels away, or 3. Those numbers are what we get from the shortest path feature.

Aside from social media examples, what are the specific uses for this feature? Below are a few ways you can put this to use –

1 Find the path to person you want access to from a large organizational chart
2 Find connections between specific tables in an ERDiagram (yes that is graph data too)
3 Find connection between two resources in a data center graph model
4 Find which store is closest to customer or various applications related to geography

You can even make a graph data model of characters in a complex novel and explore relationships that way.

And so on.

In this I will illustrate the examples of shortest path with the movie db:

Below illustrates connections from Harrison Ford to all other actors in the database

SELECT STRING_AGG(toActor.PersonName, '->') WITHIN GROUP (GRAPH PATH) AS FriendConnections,

          LAST_VALUE(toActor.PersonName) WITHIN GROUP (GRAPH PATH) AS FriendName,

          COUNT(toActor.PersonName) WITHIN GROUP (GRAPH PATH) AS levels

FROM

          PersonNode AS fromActor,

          CoActorLink FOR PATH AS f,

          PersonNode FOR PATH AS toActor

WHERE

               MATCH(SHORTEST_PATH((toActor<-(f)-)+fromActor))

               AND fromActor.PersonName = 'Harrison Ford'

The results show us how many levels away the person is as well, and who are the people on the path if they are more than one level away.

We can filter this of course to find only people who are only one hop away, or two levels away.

SELECT PersonName, Friends

FROM (

       SELECT

              Person1.Personname AS PersonName,

              STRING_AGG(Person2.Personname, '->') WITHIN GROUP (GRAPH PATH) AS Friends,

              COUNT(Person2.Personname) WITHIN GROUP (GRAPH PATH) AS levels

       FROM

              PersonNode AS Person1,

              CoActorLink FOR PATH AS fo,

              PersonNode FOR PATH  AS Person2

       WHERE MATCH(SHORTEST_PATH(Person1(-(fo)->Person2){1,3}))

       AND Person1.Personname = 'Harrison Ford'

) Q

WHERE Q.levels = 1

If we want connections between two specific people, we can do it as below.

SELECT PersonName, Friends, levels

FROM (

       SELECT

              Person1.Personname AS PersonName,

              STRING_AGG(Person2.Personname, ‘->’) WITHIN GROUP (GRAPH PATH) AS Friends,

              LAST_VALUE(Person2.Personname) WITHIN GROUP (GRAPH PATH) AS LastNode,

              COUNT(Person2.Personname) WITHIN GROUP (GRAPH PATH) AS levels

       FROM

       PersonNode AS Person1,

              CoActorLink FOR PATH AS fo,

              PersonNode FOR PATH  AS Person2

       WHERE MATCH(SHORTEST_PATH(Person1(-(fo)->Person2)+))

       AND Person1.Personname = ‘Harrison Ford’

) AS Q

WHERE Q.LastNode = ‘Tom Cruise’

In following posts I will explore more specific, every day examples of this.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s