find relationships in a many-to-many structure with sql

Question

Hi, my question is near a parent-child problem, and may need some recursive query, but i didn't find any answers by browsing forums. here is my problem: I've got 3 tables:

T1 (people)      T2 (places)  T3 (relationship betwenn A and B)
-------         ------      --------
id1 (pk)        id2 (pk)    id3 (pk)
name            city        id_A
                            id_B 

I would like to identify groups of places and people that are related. For example, if
John visits London and Paris,
Mary visits Paris and New York,
Peter visits Bangalore and Tokyo,
I would like to affect the same group code to Mary, John, Paris, London and New York, and another group code to Peter, Tokyo and Bangalore.

I really don't know how to do this with sql. Any Idea?

Thanks

Answer 1

This problem is "finding isolated subgraphs".

It's quite a simple problem, though it cannot be efficiently solved with a single SQL query.

It's quite easy to write a simple stored procedure:

1. Create a staging table:

   group_id   city_id
   

2. For each city, find group_id's of all its neighbors (all other cities the city's visitors have also visited)

3. If the neighbors belong to different group_id's, update the staging table, setting all the group_id's to the least one of the set.

4. Insert the city with the new group_id into the staging table.