Page 1 of 1

Complex relationship mapping

Posted: Fri Jan 11, 2008 7:17 am
by Stryks
I've got an upcoming project which has me stumped for a table design.

I don't know if you're familiar with the idea of six degrees of separation but that's pretty much what I'd like to find a way to map.

Basically, I want to store a list of people, along with a list of locations that each person has been to, and be able to pull a list of people who they are connected to, up to the 6th degree.

First, to relate people to locations, my basic model would be something like ...

Code: Select all

CREATE TABLE `tbl_locations` (
  `LOCATION_ID` int(11) NOT NULL auto_increment,
  `location_name` varchar(16) NOT NULL,
  PRIMARY KEY  (`LOCATION_ID`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

CREATE TABLE `tbl_users` (
  `USER_ID` int(11) NOT NULL auto_increment,
  `user_name` varchar(16) NOT NULL,
  PRIMARY KEY  (`USER_ID`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

CREATE TABLE `tbl_user_location` (
  `UL_PK` int(11) NOT NULL auto_increment,
  `LOCATION_ID` int(11) NOT NULL,
  `USER_ID` int(11) NOT NULL,
  PRIMARY KEY  (`UL_PK`),
  KEY `location_fk` (`LOCATION_ID`),
  KEY `user_fk` (`USER_ID`),
  CONSTRAINT `location_fk` FOREIGN KEY (`LOCATION_ID`) REFERENCES `tbl_locations` (`LOCATION_ID`) ON DELETE CASCADE ON UPDATE CASCADE,
  CONSTRAINT `user_fk` FOREIGN KEY (`USER_ID`) REFERENCES `tbl_users` (`USER_ID`) ON DELETE CASCADE ON UPDATE CASCADE
) ENGINE=InnoDB DEFAULT CHARSET=latin1;
So .. all good. I can pull a user and see all their locations, and I can pull a location and pull all the users.

So, can anyone give me any advice on how I could retrieve all users who are connected by having shared a location at some point, sorted in order of separation from 1 to 6. 1 degree being the people directly connected to an item (has been physically in the same location) and 2 degrees being all the people who are connected directly to any of those people. Likewise in depth for 3 through 6 degrees.

It's a pretty big ask really .... given that in theory, every person would be able to connect to everyone else. However I wouldn't need to actually pull a list of all of them, perhaps just a random 10 of each degree. Or even, say, a list of total people connected to (I could just state total users, but that would be cheating, as it wouldn't be definite.

Single query, subqueries, individual queries, or even an interim table of some kind storing relationships .... I don't know.

Any help would be great guys. Thanks

Re: Complex relationship mapping

Posted: Fri Jan 11, 2008 3:05 pm
by Kieran Huggins
That's going to turn into one messy query... are you sure you want to do 6 degrees? Your results will grow geometrically. That's big.

Re: Complex relationship mapping

Posted: Fri Jan 11, 2008 5:06 pm
by Stryks
Yeah ... It's not going to be pretty. Given the number of records, and the fact that the data will be pretty huge with a good chance of everyone linking to everyone else at least once ... well ... I guess I was just hoping that someone might say, "yeah, just store your data like this, and you're all set". :lol:

Ah well. We can dream.

I might just lose the 'list' idea and just let the user navigate for themselves through locations. I would expect people to only follow the things that interest them anyhow.


Thanks for the feedback :)

Re: Complex relationship mapping

Posted: Fri Jan 11, 2008 10:03 pm
by Kieran Huggins
Since the theory was that everybody knows everybody else by 6 degrees of separation, this should do the trick:

Code: Select all

SELECT * FROM users

Re: Complex relationship mapping

Posted: Sat Jan 12, 2008 7:07 am
by Stryks
Hehehe ... that's cheating. :lol:

Fair call though.

Re: Complex relationship mapping

Posted: Sat Jan 12, 2008 5:11 pm
by RobertGonzalez
Are you looking to select users or just counts of users per degree?

Re: Complex relationship mapping

Posted: Sat Jan 12, 2008 6:37 pm
by Stryks
Well ... the original thought was both. Kind of a
You have 1 degree of spearation from xxxxx people.

Random 20
Fred
Jimmy
Archibald
etc.
Or it could have been most active 20. The idea was to have the person -> location -> person navigation (which is straightforward with the schema above), but at the bottom to have 6 columns with short lists of people in different levels of separation. Perhaps the ability to pull a list of all of one degree. I don't know. I started trying to come up with the storage method and it was making my head hurt too much to evolve it much further.

You think you might have an approach?

Re: Complex relationship mapping

Posted: Sat Jan 12, 2008 6:53 pm
by RobertGonzalez
The approach is simple: You are one degree from me. I am one degree from you and Joe Shmoe. Soin your profile it would show me, then show all the one degrees from me, then all the one degrees from my one degrees.

Essentially you drill down through all the one degree relationships. The set up would have to be along the lines of I am one degree from you AND you are one degree from me, so we are related. There can be no one way relationships to make this work.

Re: Complex relationship mapping

Posted: Sat Jan 12, 2008 8:41 pm
by Stryks
Damn ... that's a really smart way to look at it.

You're right of course ... Instead of trying figure out a way to map six levels deep, I only really need to map one level.

Do you think this would be best achieved with a 'relationships' table, created on the fly? So, user A joins location A, where user B is already a member, so a relationship is created (user a id -> user b id).

Just that pulling that data might be easier if I could say select all where partner_1 = u_id or partner_2 = u_id, and so on and so forth. The location shows the relationship, but later on I might want to add if it's a direct relationship (as in "both people at the same time" as opposed to "have both been in the kitchen at some time") and also it would prevent mapping of dual relationships.

Of course, it's hard to let go of my previous thinking, so I might be heading in the wrong direction again. Any more thoughts?

Thanks for the help too by the way. I was really stumped and your different perspective has really helped. :)

Re: Complex relationship mapping

Posted: Sat Jan 12, 2008 11:33 pm
by RobertGonzalez
Generally speaking a relationship is set up between two people, not by your application. So say I sign up. I don't want you telling me who I am relationshipped with. I want to choose that. When I sign up I can then search for people (or alternately know their URL in the network so I can hit their profile) and add them as a relationship. They would in turn either accept my request to relate or not. Once I am related to them I am now one degree separated from them. I am two degrees separated from those that they know THAT ARE NOT ME.

To go deeper you would then look at who the relationships are of the second degree THAT ARE NOT ME and so on and so forth.

Your table would look something like:

tbl_users
user_id (INT PK AUTOINCREMENT)
user_name (VARCHAR(50) NOT NULL)
... other fields ...

tbl_users_relationships
user_id_primary (INT PK)
user_id_secondary (INT PK)

A relationship would be made when user_id 3 requests a relationship with user_id 20 (just a plain example) and user_id 20 accepts. Now there would an entry in the relationships table with TWO new rows: 3, 20 and 20, 3. This means that 20 is related to 3 AND 3 is related to 20. All relationship queries would then join on this table from the users table to match relationships.

Does any of this make sense?

Re: Complex relationship mapping

Posted: Sun Jan 13, 2008 1:05 am
by Stryks
Yeah, that makes things much clearer, thanks.

In this case the relationship would be automatic, though the ability to create 'friend' relationships would also be a possibility. In either case, you've given me a much clearer idea of the methodology.

Now that I can see the possibility, I'll have to sit down and collect my thoughts about how the rest of it will and to come together and what data I'm going to need to track.

Many thanks for you help. Greatly appreciated. :D