Complex relationship mapping
Posted: Fri Jan 11, 2008 7:17 am
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 ...
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
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, 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