degrees of separation - 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 2005 Forums

Transact-SQL (2005)

degrees of separation

Author

Topic

waelation
Starting Member

13 Posts

Posted - 2009-05-19 : 03:00:29

I have a task of creating a stored procedures for family tree table..
The procedure will have a complicated logic. I will give an example to explain what I have and what result I want from the procedure.
IT goes as follows:

I have a table that has the relations between members with their member ID's and Family ID's:
The relation Id's (REL_ID) are
1 => father
2 => Mother
3 => Married

F_ID is the family (Last Name) ID

my family F_ID is 20
and Friend's F_ID is 30
My mother's F_ID is 40
My friend's mother F_ID is 50

Lets say my uncle married my friend's sister and the ID's are

Member ID's
My ID : 1
My Father's ID : 2
My Mother's ID: 3
My uncle's ID: 4
My Grandfather's ID 5
My Friend's father ID: 6
My friend's mother ID: 7
My friend's ID: 8
My friend's bother ID : 9
My friend's sister ID: 10

lets say I want to get the link on the shortest degree between Me and My friend

The link would be

ME => My Uncle => My Friend's Sister (Uncle's wife) => My friend

In Member Id's:

1 => 4 => 10 => 8

Following are the scripts to create the tables and insert the data for the above example..It shows how I have the data and how it should be saved in the table:

SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
SET ANSI_PADDING ON
GO
CREATE TABLE [dbo].[FAMILY_MEMBER_REL](
[M_ID] [varchar](100) NOT NULL,
[P_ID] [varchar](100) NOT NULL,
[REL_ID] [varchar](20) NOT NULL,
[F_ID] [numeric](18, 0) NULL,
[P_F_ID] [numeric](18, 0) NULL
) ON [PRIMARY]

GO
SET ANSI_PADDING OFF

insert into family_member_rel values ('2', '1','1','20','20')
insert into family_member_rel values ('3', '1','2','40','20')
insert into family_member_rel values ('5', '2','1','20','20')
insert into family_member_rel values ('5', '4','1','20','20')
insert into family_member_rel values ('3', '2','3','40','20')
insert into family_member_rel values ('6', '8','1','30','30')
insert into family_member_rel values ('7', '8','2','50','30')
insert into family_member_rel values ('6', '9','1','30','30')
insert into family_member_rel values ('7', '9','2','50','30')
insert into family_member_rel values ('6', '10','1','30','30')
insert into family_member_rel values ('7', '10','2','50','30')
insert into family_member_rel values ('7', '6','3','50','30')
insert into family_member_rel values ('10', '4','3','30','20')

SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
SET ANSI_PADDING ON
GO
CREATE TABLE [dbo].[FMLY_LNK](
[FRM_M_ID] [varchar](100) NOT NULL,
[TO_M_ID] [varchar](100) NOT NULL,
[M1] [varchar](100) NULL,
[M2] [varchar](100) NULL,
[M3] [varchar](100) NULL,
[M4] [varchar](100) NULL,
[M5] [varchar](100) NULL,
[M6] [varchar](100) NULL,
[M7] [varchar](100) NULL,
[M8] [varchar](100) NULL,
[M9] [varchar](100) NULL,
[M10] [varchar](100) NULL,
[M11] [varchar](100) NULL,
[M12] [varchar](100) NULL,
[M13] [varchar](100) NULL,
[M14] [varchar](100) NULL,
[M15] [varchar](100) NULL,
[M16] [varchar](100) NULL,
[M17] [varchar](100) NULL,
[M18] [varchar](100) NULL,
[M19] [varchar](100) NULL,
[M20] [varchar](100) NULL,
CONSTRAINT [PK_FMLY_LNK] PRIMARY KEY CLUSTERED
(
[FRM_M_ID] ASC,
[TO_M_ID] ASC
)WITH (IGNORE_DUP_KEY = OFF) ON [PRIMARY]
) ON [PRIMARY]

GO
SET ANSI_PADDING OFF

insert into [FMLY_LNK] ([FRM_M_ID], [TO_M_ID], [M1], [M2]) values ('1', '8', '4', '10')

Note that this link is a one degree link which means that there may be different people from different families that can make up the link but i always want the shortest path:
I may be married to a woman who is the cousin (from mother's side) of my friend's wife
So to get the link between me and my friend, its ME => My wife =>My wife's mother => My friend's wife => My friend

I know that its complicated but I have this task and I should submit it as soon as possible.

Thanks in advance..

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2009-05-19 : 03:19:09

I have written several algorithms for this.

See among others this
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=73079
and this
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=72097

E 12°55'05.63"
N 56°04'39.26"

waelation
Starting Member

13 Posts

Posted - 2009-05-19 : 03:57:01

Thanks for the quick reply...

These functions don't work for my case.
The first link gives the number of nodes between two points..
The second link only gives the common friends between 2 people.
What i need is to select the friends that make up the link between two people even if the link was 7 or 8 nodes away.

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2009-05-19 : 05:15:40

Did you also check the second function written 03/26/2007 : 04:28:01
here http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=73079 ?
You can very easy rewrite the function to return a table (@Friends table) instead of a integer value.

E 12°55'05.63"
N 56°04'39.26"

waelation
Starting Member

13 Posts

Posted - 2009-05-19 : 05:23:51

Sorry for being kind of pushy, but can you please help me or tell me how I can change it to return the the friends ?

Thanks a lot for the help..

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2009-05-19 : 05:35:30

1. Instead of RETURNS INT, change to RETURNS @Friends TABLE (...)
2. Remove @Friends table declaration
3. Change RETURN variable to just RETURN

E 12°55'05.63"
N 56°04'39.26"

waelation
Starting Member

13 Posts

Posted - 2009-05-19 : 06:54:19

I tried it but its still not working

Can you post it according to the example you gave in that post..
I hope u understand what I meant..I want the list of all the friends that are between two nodes or people..

thanks again

Transact Charlie
Master Smack Fu Yak Hacker

3451 Posts

Posted - 2009-05-19 : 08:26:43

quote:

I tried it but its still not working

Why don't you post what you have tried?

Charlie
===============================================================
Msg 3903, Level 16, State 1, Line 1736
The ROLLBACK TRANSACTION request has no corresponding BEGIN TRANSACTION

waelation
Starting Member

13 Posts

Posted - 2009-05-19 : 08:50:30

Msg 4121, Level 16, State 1, Line 2
Cannot find either column "dbo" or the user-defined function or aggregate "dbo.fnFriendsBetween", or the name is ambiguous.

Transact Charlie
Master Smack Fu Yak Hacker

3451 Posts

Posted - 2009-05-19 : 09:20:22

Please post your code -- we'll be able to see *why* the message was generated!

Charlie
===============================================================
Msg 3903, Level 16, State 1, Line 1736
The ROLLBACK TRANSACTION request has no corresponding BEGIN TRANSACTION

waelation
Starting Member

13 Posts

Posted - 2009-05-19 : 10:04:57

CREATE TABLE Contacts (pFrom VARCHAR(2), pTo VARCHAR(2))

INSERT Contacts
SELECT 'A', 'B' UNION ALL
SELECT 'B', 'D' UNION ALL
SELECT 'C', 'A' UNION ALL
SELECT 'C', 'E' UNION ALL
SELECT 'G', 'C' UNION ALL
SELECT 'B', 'G' UNION ALL
SELECT 'F', 'D' UNION ALL
SELECT 'E', 'F'

select * from contacts

CREATE FUNCTION dbo.fnFriendsBetween
(
@From VARCHAR(2),
@To VARCHAR(2)
)
RETURNS @Friends TABLE (Generation INT, p VARCHAR(2))
AS

BEGIN

DECLARE @Generation INT

SELECT @Generation = 0

INSERT @Friends
(
Generation,
p
)
SELECT 0,
@From

WHILE @@ROWCOUNT > 0 AND NOT EXISTS (SELECT * FROM @Friends WHERE p = @To)
BEGIN
SELECT @Generation = @Generation + 1

INSERT @Friends
(
Generation,
p
)
SELECT @Generation,
pTo
FROM Contacts
WHERE pFrom IN (SELECT p FROM @Friends WHERE Generation = @Generation - 1)
AND pTo NOT IN (SELECT p FROM @Friends)
UNION ALL
SELECT @Generation,
pFrom
FROM Contacts
WHERE pTo IN (SELECT p FROM @Friends WHERE Generation = @Generation - 1)
AND pFrom NOT IN (SELECT p FROM @Friends)
END

RETURN
END

select dbo.fnFriendsBetween(pfrom, pto) from contacts

drop table contacts

Transact Charlie
Master Smack Fu Yak Hacker

3451 Posts

Posted - 2009-05-19 : 10:29:55

You need to split it into batches. CREATE FUNCTION needs to be the first statement in a batch. Also the function is a table value function so you have to SELECT FROM it. and you can't use it inline.

You could CROSS APPLY it but that's probably not required.

Try



CREATE TABLE Contacts (pFrom VARCHAR(2), pTo VARCHAR(2))

INSERT	Contacts
SELECT	'A', 'B' UNION ALL
SELECT	'B', 'D' UNION ALL
SELECT	'C', 'A' UNION ALL
SELECT	'C', 'E' UNION ALL
SELECT	'G', 'C' UNION ALL
SELECT	'B', 'G' UNION ALL
SELECT	'F', 'D' UNION ALL
SELECT	'E', 'F'


select * from contacts
GO

CREATE FUNCTION	dbo.fnFriendsBetween
(
@From VARCHAR(2),
@To VARCHAR(2)
)
RETURNS @Friends TABLE (Generation INT, p VARCHAR(2))
AS

BEGIN


DECLARE	@Generation INT

SELECT @Generation = 0

INSERT	@Friends
(
Generation,
p
)
SELECT	0,
@From

WHILE @@ROWCOUNT > 0 AND NOT EXISTS (SELECT * FROM @Friends WHERE p = @To)
BEGIN
SELECT @Generation = @Generation + 1

INSERT	@Friends
(
Generation,
p
)
SELECT	@Generation,
pTo
FROM	Contacts
WHERE	pFrom IN (SELECT p FROM @Friends WHERE Generation = @Generation - 1)
AND pTo NOT IN (SELECT p FROM @Friends)	
UNION ALL
SELECT	@Generation,
pFrom
FROM	Contacts
WHERE	pTo IN (SELECT p FROM @Friends WHERE Generation = @Generation - 1)
AND pFrom NOT IN (SELECT p FROM @Friends)
END

RETURN	
END



GO

select *
FROM
     dbo.fnFriendsBetween('A', 'F')

drop table contacts

What does that code do?

Charlie
===============================================================
Msg 3903, Level 16, State 1, Line 1736
The ROLLBACK TRANSACTION request has no corresponding BEGIN TRANSACTION

waelation
Starting Member

13 Posts

Posted - 2009-05-19 : 10:38:58

The function worked...
but the problem is that its not what i want..I want the list of the people that make up the relation..

Transact Charlie
Master Smack Fu Yak Hacker

3451 Posts

Posted - 2009-05-19 : 10:50:03

You've posted in the SQL server 2000 forum. Are you sure that's what you have got. If you have sql server 2005 then I know a way to do this but id doesn't work on 2000

Charlie
===============================================================
Msg 3903, Level 16, State 1, Line 1736
The ROLLBACK TRANSACTION request has no corresponding BEGIN TRANSACTION

waelation
Starting Member

13 Posts

Posted - 2009-05-19 : 11:01:40

I have SQL Server 2005...I posted here because I thought I thought that this is a database development issue and there's no development in 2005..

Transact Charlie
Master Smack Fu Yak Hacker

3451 Posts

Posted - 2009-05-19 : 11:19:30

Ok -- in that case there are a lot of other methods available.

You should probably contact an admin to move this thread into a 2005 forum -- you'll get a lot more replies.

Charlie
===============================================================
Msg 3903, Level 16, State 1, Line 1736
The ROLLBACK TRANSACTION request has no corresponding BEGIN TRANSACTION

Transact Charlie
Master Smack Fu Yak Hacker

3451 Posts

Posted - 2009-05-19 : 11:30:56

Do you want the shortest possible relation?

So if there are two links (one between 3 friends and one between 7) do you want only to show the 3?

Charlie
===============================================================
Msg 3903, Level 16, State 1, Line 1736
The ROLLBACK TRANSACTION request has no corresponding BEGIN TRANSACTION

Transact Charlie
Master Smack Fu Yak Hacker

3451 Posts

Posted - 2009-05-19 : 11:34:54

You could customise this -- used to get shortest journeys -- your node map would be far less circuitous.


DECLARE @Stations TABLE (
	[stationID] INT
	, [name] VARCHAR(255)
)

INSERT	@Stations
SELECT 1, 'Glasgow' UNION ALL
SELECT 2, 'Edinburgh' UNION ALL
SELECT 3, 'York' UNION ALL
SELECT 4, 'London' UNION ALL
SELECT 5, 'Aberdeen' UNION ALL
SELECT 6, 'Bjuv' UNION ALL
SELECT 7, 'Båstad'

DECLARE @Links TABLE (
	[fromID] INT
	, [toID] INT
)

INSERT @Links
SELECT 1, 2 UNION ALL -- Glasgow, Edinburgh
SELECT 1, 5 UNION ALL -- Glasgow, Aberdeen
SELECT 1, 3 UNION ALL -- Glasgow, York
SELECT 2, 1 UNION ALL -- Edinburgh, Glasgow
SELECT 2, 3 UNION ALL -- Edinburgh, York
SELECT 2, 7 UNION ALL -- Edinburgh, Båstad
SELECT 3, 2 UNION ALL -- York, Edinburgh
SELECT 3, 4 UNION ALL -- York, London
SELECT 4, 3 UNION ALL -- London, York
SELECT 5, 1 UNION ALL -- Aberdeen, glasgow
SELECT 6, 4 UNION ALL -- Bjuv, London
SELECT 6, 7 UNION ALL -- Bjuv, Båstad
SELECT 7, 2 UNION ALL -- Båstad, Edinburgh
SELECT 7, 6 -- Båstad, Bjuv

/*  -- Node Map (* = Go to)

      A
     *
    /
   *
  G *---* E --* Bd
   \     *       *
    \   /        |
     * *         |
      Y          |
      *          |
      |          |
      *          *
      L *------ Bj

*/
;WITH paths([stationIDs], [pathLength], [hopPath], [fromID], [fromName], [toName])
AS (
	SELECT
		CAST([stationID] AS VARCHAR(MAX))
		, CAST(0 AS INT)
		, CAST([name] AS VARCHAR(MAX))
		, [stationID]
		, CAST([name] AS VARCHAR(MAX))
		, CAST(NULL AS VARCHAR(MAX))
	FROM
		@Stations
	UNION ALL SELECT
		p.[stationIDs] + '/' + CAST(l.[toID] AS VARCHAR(MAX))
		, [pathLength] + 1
		, p.[hopPath] + ' -> ' + s.[name]
		, l.[toID]
		, p.[fromName]
		, CAST(s.[name] AS VARCHAR(MAX))
	FROM
		paths p
		INNER JOIN	@Links l ON l.[fromID] = p.[fromID]
		INNER JOIN	@Stations s ON s.[stationID] = l.[toID]
	WHERE
		'/' + p.[stationIDs] + '/' NOT LIKE '%/' + CAST(l.[toID] AS VARCHAR(MAX)) + '/%'
	)
SELECT
	d.[fromName]
	, d.[toName]
	, d.[hops]
	, d.[hopPath]
FROM
	(
	SELECT
		[fromName]
		, [toName]
		, [pathLength] AS hops
		, [hopPath]
		, ROW_NUMBER() OVER (PARTITION BY fromName, toName ORDER BY pathLength) AS recID
	FROM
		paths
	WHERE
		pathLength >= 1
	) d
WHERE
	[recID] = 1
ORDER BY
	[fromName]
	, [toName]
OPTION (MAXRECURSION 0)

Charlie
===============================================================
Msg 3903, Level 16, State 1, Line 1736
The ROLLBACK TRANSACTION request has no corresponding BEGIN TRANSACTION

waelation
Starting Member

13 Posts

Posted - 2009-05-19 : 11:36:03

yes...that is what I want..The shortest possible relation..

can any admin who sees this please help me out in moving this thread to the 2005 section ?

Transact Charlie
Master Smack Fu Yak Hacker

3451 Posts

Posted - 2009-05-19 : 11:38:31

The recursive method for journeys should do what you want then.

Charlie
===============================================================
Msg 3903, Level 16, State 1, Line 1736
The ROLLBACK TRANSACTION request has no corresponding BEGIN TRANSACTION

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2009-05-19 : 14:09:37

Explanation and more details here
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=115290

E 12°55'05.63"
N 56°04'39.26"

Next Page

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources