Daniel Valland Daniel Valland - 4 months ago 16
SQL Question

Get rows by transitivity in mysql

Suppose i have the following table:

Images

|id | similarTo|
|---|----------|
|1 | 2 |
|2 | 3 |
|--------------|


Where similarTo is a foriegn key to id. What i want is a query that can fetch the transitive closure of an id down to 2 levels both ways. In other words, what we have is: A --> B ---> C
and also C --> B --> A

And so in this case i would like it to return:

Given 1: 2,3
Given 2: 1,3
Given 3: 1,2


Essentially i am storing the function (Image A) similarTo(Image B) in a table. This function goes both ways, so if A is similar to B, then B is similar to A. Now i need a query that can find all images similar to a given image by up to two levels/steps... (that is if given A --> B --> C --> D, now if i want to find all images similar to A, it would return B,C)

Answer

May be a query like below:

SELECT 
id,
similarTo
From images

UNION ALL

SELECT 
t1.id,
t2.similarTo
FROM images t1
INNER JOIN images t2 ON t1.similarTo = t2.id AND t1.id < t2.id

DEMO

The second query actually begets the transitive relation. And the first one gets all the defined relationships in your table.

Output:

You will get output like below:

| id | similarTo |
|----|-----------|
|  1 |         2 |
|  2 |         3 |
|  1 |         3 |

EDIT:

For specific id say id=2:

SELECT 
id,
similarTo
From images
WHERE id=2 or similarTo=2

UNION ALL

SELECT 
t1.id,
t2.similarTo
FROM images t1
INNER JOIN images t2 ON t1.similarTo=2 AND t2.id =2 AND t1.id < t2.id

DEMO