Computing relationships - SQL Server Forums

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

SQL Server 2000 Forums

Transact-SQL (2000)

Computing relationships

Author

Topic

aiken
Aged Yak Warrior

525 Posts

Posted - 2003-11-23 : 00:12:37

Not FK relationships, but relationships among records.

For instance, I have a join table that tells me that anna has met bob and chris, and that bob has met darlene and eddie, and that darlene has met francis.

I want to query on anna and see that she has 2 firsthand relationships with bob and chris, and 2 second hand relationships with darlene and eddie (through bob), and 1 third hand relationship (anna-bob-darlene-francis).

I also want to query on chris and see that he has 1 firsthand relationship (anna), 1 secondhand relationship (bob through anna), and two third hand relationships (darlene and eddie through bob).

I'm struggling with two things here: the table structure is a bit weird, with the concept of source and target

Tables and sample data:


create table users (i int,handle varchar(20))
create table rels (i_users_one int,i_users_two int)

insert into users (handle) VALUES (1,'anna')
insert into users (handle) VALUES (2,'bob')
insert into users (handle) VALUES (3,'chris')
insert into users (handle) VALUES (4,'darlene')
insert into users (handle) VALUES (5,'eddie')
insert into users (handle) VALUES (6,'francis')

insert into rels (i_users_one,i_users_two) VALUES (1,2)
insert into rels (i_users_one,i_users_two) VALUES (1,3)
insert into rels (i_users_one,i_users_two) VALUES (2,4)
insert into rels (i_users_one,i_users_two) VALUES (2,5)
insert into rels (i_users_one,i_users_two) VALUES (4,6)

Desired results:


For anna:
user       distance
   2              1
   3              1 
   4              2
   5              2
   6              3

For chris:
user       distance
   1              1
   2              2
   4              3
   5              3
[/code]

Of course, the results would probably be joined back to users, but it's the fundamental counting concept that I'm having trouble with.

Thanks!
-b

nr
SQLTeam MVY

12543 Posts

Posted - 2003-11-23 : 10:20:36

This is a hierarchy. You'll have to use a loop to get the result.
Do a search for trees on this site or look at
http://www.nigelrivett.net/RetrieveTreeHierarchy.html

==========================================
Cursors are useful if you don't know sql.
DTS can be used in a similar way.
Beer is not cold and it isn't fizzy.

SamC
White Water Yakist

3467 Posts

Posted - 2003-11-23 : 10:42:10

This may be a good challenge question as the only solution I see looks like brute force. Here it is.

I had some trouble keeping things straight with the sample column names. To make it easier for me, I used the following

CREATE TABLE Users (
UserID INT,
Username VARCHAR (50))

CREATE TABLE Rels (
UserIDa INT,
UserIDb INT )
The rows you show in the example don't include Anna's ID along with her relationships. I'm going to take a guess that the rowset you want is:

Username, UserIDn as UserID, n as Distance
e.g. Username=Anna, Useridn is the ID of each user, n is distance...

SELECT U.Username, U1.UserID, 1 as Distance
FROM Users U
LEFT OUTER JOIN Rels R1 ON R1.UserIDa = U.UserID
LEFT OUTER JOIN Users U1 ON U1.UserID = R1.UserIDb
WHERE U1.UserID IS NOT NULL
UNION ALL
SELECT U.Username, U2.UserID, 2 as Distance
FROM Users U
LEFT OUTER JOIN Rels R1 ON R1.UserIDa = U.UserID
LEFT OUTER JOIN Users U1 ON U1.UserID = R1.UserIDb
LEFT OUTER JOIN Rels R2 ON R2.UserIDa = U1.UserID
LEFT OUTER JOIN Users U2 ON U2.UserID = R2.UserIDb
WHERE U2.UserID IS NOT NULL
UNION ALL
SELECT U.Username, U3.UserID, 3 as Distance
FROM Users U
LEFT OUTER JOIN Rels R1 ON R1.UserIDa = U.UserID
LEFT OUTER JOIN Users U1 ON U1.UserID = R1.UserIDb
LEFT OUTER JOIN Rels R2 ON R2.UserIDa = U1.UserID
LEFT OUTER JOIN Users U2 ON U2.UserID = R2.UserIDb
LEFT OUTER JOIN Rels R3 ON R3.UserIDa = U2.UserID
LEFT OUTER JOIN Users U3 ON U3.UserID = R3.UserIDb
WHERE U3.UserID IS NOT NULL

If you want the recordset ordered

SELECT Username, UserID, Distance
FROM (
SELECT U.Username, U1.UserID, 1 as Distance
FROM Users U
LEFT OUTER JOIN Rels R1 ON R1.UserIDa = U.UserID
LEFT OUTER JOIN Users U1 ON U1.UserID = R1.UserIDb
WHERE U1.UserID IS NOT NULL
UNION ALL
SELECT U.Username, U2.UserID, 2 as Distance
FROM Users U
LEFT OUTER JOIN Rels R1 ON R1.UserIDa = U.UserID
LEFT OUTER JOIN Users U1 ON U1.UserID = R1.UserIDb
LEFT OUTER JOIN Rels R2 ON R2.UserIDa = U1.UserID
LEFT OUTER JOIN Users U2 ON U2.UserID = R2.UserIDb
WHERE U2.UserID IS NOT NULL
UNION ALL
SELECT U.Username, U3.UserID, 3 as Distance
FROM Users U
LEFT OUTER JOIN Rels R1 ON R1.UserIDa = U.UserID
LEFT OUTER JOIN Users U1 ON U1.UserID = R1.UserIDb
LEFT OUTER JOIN Rels R2 ON R2.UserIDa = U1.UserID
LEFT OUTER JOIN Users U2 ON U2.UserID = R2.UserIDb
LEFT OUTER JOIN Rels R3 ON R3.UserIDa = U2.UserID
LEFT OUTER JOIN Users U3 ON U3.UserID = R3.UserIDb
WHERE U3.UserID IS NOT NULL

) X
ORDER BY Username, Distance, UserID -- Distance order by user

aiken
Aged Yak Warrior

525 Posts

Posted - 2003-12-03 : 20:00:53

Sorry to be slow responding -- got swamped there and then was away for thanksgiving.

Nigel, isn't treating this as a tree or hierarchy going to have problems with there are cross links? For instance, in my example, francis might have met anna.

SamC, that's close to working for me, but it doesn't seem to work bidirectionally; that is, if finds all the links when there is a relationship with UserIDa = x, but not when UserIDb = x. Hopefully that makes sense.

That difficulty makes me wonder if there isn't some better way of expressing the relationship than arbitrarily calling one ID "a" and the other "b". I think I see how the data could first be massaged so that every link appears both ways, but isn't that needlessly complicating things and probably indicative of a fundamental bit of stupidity on my part?

Thanks for the excellent advice, as always. I learn a lot here.

Cheers
-b

ehorn
Master Smack Fu Yak Hacker

1632 Posts

Posted - 2003-12-03 : 21:25:52

I am seeing this as finding how many nodes away a given i is
from every other i in the tree.

In your sample output


For chris = 3
user       distance
   1              1
   2              2
   4              3
   5              3

francis is not represented at a distance of 4?
Should he be present in the output or am I misunderstanding
or are you only searching for nodes up to 3 away.

The following code will give you nodes distances for all nodes != i


declare	@node int 
set @node = 4 --Defines i

declare @lev int; set @lev=0
create table #t (lev int, node int)
insert into #t select @lev, @node

--down the tree
while @lev<=(select max(i) from users)
	begin
		insert into #t select @lev, i_users_one from rels
		where i_users_two in (select node from #t where lev=@lev-1)
		set @lev=@lev+1
	end

--up the tree
set @lev=0
while @lev<=(select max(i) from users)
	begin
		insert into #t select @lev, i_users_two from rels
		where i_users_one in (select node from #t where lev=@lev-1)
		set @lev=@lev+1
	end


select i,handle,(select top 1 min(distance) from #t t where t.node=a.i) distance
from
(
	select t.node i, u.handle ,t.lev distance
	from users u
	join #t t on t.node=u.i
	where t.node <> @node
) a
group by i,handle
order by distance,i

drop table #t

SamC
White Water Yakist

3467 Posts

Posted - 2003-12-03 : 22:42:41

SELECT U.Username, U1.UserID, 1 as Distance
FROM Users U
LEFT OUTER JOIN Rels R1 ON R1.UserIDa = U.UserID OR R1.UserIDb = U.UserID
LEFT OUTER JOIN Users U1 ON U1.UserID = R1.UserIDb OR U1.UserID = R1.UserIDa
WHERE U1.UserID IS NOT NULL AND U1.UserID <> U.UserID
UNION ALL
SELECT U.Username, U2.UserID, 2 as Distance
FROM Users U
LEFT OUTER JOIN Rels R1 ON R1.UserIDa = U.UserID OR R1.UserIDb = U.UserID
LEFT OUTER JOIN Users U1 ON U1.UserID = R1.UserIDb OR U1.UserID = R2.UserIDb
LEFT OUTER JOIN Rels R2 ON R2.UserIDa = U1.UserID OR R2.UserIDb = U1.UserID
LEFT OUTER JOIN Users U2 ON U2.UserID = R2.UserIDb OR U2.UserID = R2.UserIDa
WHERE U2.UserID IS NOT NULL
AND U.UserID <> U1.UserID
AND U1.UserID <> U2.UserID

I wonder if doubling up the join conditions solves your problem?

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources