Complex relationship mapping

Questions about the MySQL, PostgreSQL, and most other databases, as well as using it with PHP can be asked here.

Moderator: General Moderators

Post Reply
User avatar
Stryks
Forum Regular
Posts: 746
Joined: Wed Jan 14, 2004 5:06 pm

Complex relationship mapping

Post 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
User avatar
Kieran Huggins
DevNet Master
Posts: 3635
Joined: Wed Dec 06, 2006 4:14 pm
Location: Toronto, Canada
Contact:

Re: Complex relationship mapping

Post 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.
User avatar
Stryks
Forum Regular
Posts: 746
Joined: Wed Jan 14, 2004 5:06 pm

Re: Complex relationship mapping

Post 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 :)
User avatar
Kieran Huggins
DevNet Master
Posts: 3635
Joined: Wed Dec 06, 2006 4:14 pm
Location: Toronto, Canada
Contact:

Re: Complex relationship mapping

Post 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
User avatar
Stryks
Forum Regular
Posts: 746
Joined: Wed Jan 14, 2004 5:06 pm

Re: Complex relationship mapping

Post by Stryks »

Hehehe ... that's cheating. :lol:

Fair call though.
User avatar
RobertGonzalez
Site Administrator
Posts: 14293
Joined: Tue Sep 09, 2003 6:04 pm
Location: Fremont, CA, USA

Re: Complex relationship mapping

Post by RobertGonzalez »

Are you looking to select users or just counts of users per degree?
User avatar
Stryks
Forum Regular
Posts: 746
Joined: Wed Jan 14, 2004 5:06 pm

Re: Complex relationship mapping

Post 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?
User avatar
RobertGonzalez
Site Administrator
Posts: 14293
Joined: Tue Sep 09, 2003 6:04 pm
Location: Fremont, CA, USA

Re: Complex relationship mapping

Post 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.
User avatar
Stryks
Forum Regular
Posts: 746
Joined: Wed Jan 14, 2004 5:06 pm

Re: Complex relationship mapping

Post 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. :)
User avatar
RobertGonzalez
Site Administrator
Posts: 14293
Joined: Tue Sep 09, 2003 6:04 pm
Location: Fremont, CA, USA

Re: Complex relationship mapping

Post 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?
User avatar
Stryks
Forum Regular
Posts: 746
Joined: Wed Jan 14, 2004 5:06 pm

Re: Complex relationship mapping

Post 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
Post Reply