Traversing and Getting Nodes in Graph without Loop

Question

I have a person table which keeps some personal info. like as table below.

+----+------+----------+----------+--------+
| ID | name | motherID | fatherID |  sex   |
+----+------+----------+----------+--------+
|  1 | A    | NULL     | NULL     | male   |
|  2 | B    | NULL     | NULL     | female |
|  3 | C    | 1        | 2        | male   |
|  4 | X    | NULL     | NULL     | male   |
|  5 | Y    | NULL     | NULL     | female |
|  6 | Z    | 5        | 4        | female |
|  7 | T    | NULL     | NULL     | female |
+----+------+----------+----------+--------+

Also I keep marriage relationships between people. Like:

+-----------+--------+
| HusbandID | WifeID |
+-----------+--------+
|         1 |      2 |
|         4 |      5 |
|         1 |      5 |
|         3 |      6 |
+-----------+--------+

With these information we can imagine the relationship graph. Like below;

Question is: How can I get all connected people by giving any of them's ID.

For example;

When I give ID=1, it should return to me 1,2,3,4,5,6.(order is not important)
Likewise When I give ID=6, it should return to me 1,2,3,4,5,6.(order is not important)
Likewise When I give ID=7, it should return to me 7.

Please attention : Person nodes' relationships (edges) may have loop anywhere of graph. Example above shows small part of my data. I mean; person and marriage table may consist thousands of rows and we do not know where loops may occur.

Smilar questions asked in :

PostgreSQL SQL query for traversing an entire undirected graph and returning all edges found http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=118319

But I can't code the working SQL. Thanks in advance. I am using SQL Server.

Are you using SQL Server Azure SQL Database or SQL Server 2017? Both have (limited) graph capabilities. — Mark Sinkinson
– Mark Sinkinson, Commented Mar 5, 2018 at 15:04
I tried SQL Server 2017 but I can not write a solution query. — Peter
– Peter, Commented Mar 5, 2018 at 15:19
use Neo4j :). Or, write a sproc, keep track of each node ID that you've crossed, and for each node that you're attempting to access, check first if you've already processed it (I did this a while back and it was the only way to prevent circular processing at the time... 2 years or so ago, prior to any graph-specific functionality in RDBMs) — jleach
– jleach, Commented Apr 2, 2018 at 21:09

wBob · Accepted Answer · 2018-04-02 20:47:05Z

From SQL Server 2017 and Azure SQL DB you can use the new graph database capabilities and the new MATCH clause to answer queries like this, eg

SELECT FORMATMESSAGE ( 'Person %s (%i) has mother %s (%i) and father %s (%i).', person.userName, person.personId, mother.userName, mother.personId, father.userName, father.personId ) msg
FROM dbo.persons person, dbo.relationship hasMother, dbo.persons mother, dbo.relationship hasFather, dbo.persons father
WHERE hasMother.relationshipType = 'mother'
  AND hasFather.relationshipType = 'father'
  AND MATCH ( father-(hasFather)->person<-(hasMother)-mother );

My results:

Full script available here.

For your specific questions, the current release does not include transitive closure (the ability to loop through the graph n number of times) or polymorphism (find any node in the graph) and answering these queries may involve loops, recursive CTEs or temp tables. I have attempted this in my sample script and it works for your sample data but it's just an example - I'm not 100% it will work with other sample data.

Collectives™ on Stack Overflow

Traversing and Getting Nodes in Graph without Loop

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related