SQL Server Forums
Profile | Register | Active Topics | Members | Search | Forum FAQ
 
Register Now and get your question answered!
Username:
Password:
Save Password
Forgot your Password?

 All Forums
 SQL Server 2000 Forums
 SQL Server Development (2000)
 Social Networking > SQL Statement
 New Topic  Reply to Topic
 Printer Friendly
Next Page
Author Previous Topic Topic Next Topic
Page: of 2

zeus1
Starting Member

3 Posts

Posted - 09/16/2006 :  07:52:17  Show Profile  Reply with Quote
I am looking for the most straightforward (one or two sql statements) approach to get information from a social networking
table.

Person A is connected to Person B
Person B is connected to Person C

The records on the CONTACTS table looks like this:

Contacts
---------
connected: person a,person b
connected: person b,person c

The link between person a and person c is that they are both connected to person b. I am looking for a one or two query
processing step that will tell me whether person a and person c
are connected by a mutual friend.

Thanks






blindman
Flowing Fount of Yak Knowledge

USA
2365 Posts

Posted - 09/16/2006 :  16:37:43  Show Profile  Reply with Quote
You have a recursive relationship. You will need to use some form of loop to plum through the binary tree and find all related records.
Here is one method, from an article I wrote:
------------------------------------------
The most flexible and robust method of storing hierarchical data in a database is to use a table with a recursive relationship. In this design, each record has an associated parent record ID that indicates its relative place in the hierarchy. Here is an example:

CREATE TABLE [YourTable]
([RecordID] [int] IDENTITY (1, 1) NOT NULL ,
[ParentID] [int] NULL)

The challenge is to find a way to return all the child records and descendants for any given parent record.

While recursion is supported within SQL Server, it is limited to 32 nested levels and it tends to be ineffecient because it does not take full advantage of SQL Server's set-based operations.

A better algorithm is a method I call the "Accumulator Table".

In this method, a temporary table is declared that accumulates the result set. The table is seeded with the initial key of the parent record, and then a loop is entered which inserts the immediate descendants of all the records accumulated so far which have not already been added to the table.

Here is some skeleton code to show how it works:

--This variable will hold the parent record ID who's children we want to find.
declare @RecordID int
set @RecordID = 13

--This table will accumulate our output set.
declare @RecordList table (RecordID int)

--Seed the table with the @RecordID value, assuming it exists in the database.
insert into @RecordList (RecordID)
select RecordID
from YourTable
where YourTable.RecordID = @RecordID

--Add new child records until exhausted.
while @@RowCount > 0
insert into @RecordList (RecordID)
select YourTable.RecordID
from YourTable
inner join @RecordList RecordList on YourTable.ParentID = RecordList.RecordID
where not exists (select * from @RecordList CurrentRecords where CurrentRecords.RecordID = YourTable.RecordID)

--Return the result set
select RecordID
from @RecordList

This method is both flexible and efficient, and the concept is adaptable to other hierarchical data challenges.

"I have HAD it with these muthu-f$#%in' cursors in my muthu-f$#%in' database!"
Go to Top of Page

spirit1
Cybernetic Yak Master

Slovenia
11751 Posts

Posted - 09/16/2006 :  16:39:42  Show Profile  Visit spirit1's Homepage  Reply with Quote
care to show us the whole article?



Go with the flow & have fun! Else fight the flow
blog thingie: http://weblogs.sqlteam.com/mladenp
Go to Top of Page

zeus1
Starting Member

3 Posts

Posted - 09/16/2006 :  18:21:20  Show Profile  Reply with Quote
Blindman, thanks for the input. I understand that i have a recursive relationship. Unfortunately, i do not have the luxury of designing
the table from the ground-up.

Pls can you show me how your approach can be applied to my current
table structure?

Thanks
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30240 Posts

Posted - 09/17/2006 :  03:27:20  Show Profile  Visit SwePeso's Homepage  Reply with Quote
This problems looks very much like Dijkstra's algorithm for finding closest way between two nodes.
With some changes, it should be able to get all ways between the two nodes.

                    A - B  
                   /     \   
                  C       D 
                   \     / 
                    E - F
Look at the above relationships. Get all mutual friends between C and B should render A, D, E, F?
Or only A, since A is connected to both B and C?


Peter Larsson
Helsingborg, Sweden

Edited by - SwePeso on 09/17/2006 03:52:19
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30240 Posts

Posted - 09/17/2006 :  03:47:28  Show Profile  Visit SwePeso's Homepage  Reply with Quote
If only MUTUAL friends are to be found, I see no need for recursive algorithm.

-- Prepare test data
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'

-- This is the node chart of connections
/*
                    A - B 
                   /   / \ 
                  C - G   D 
                   \     / 
                    E - F 
*/

SELECT		mf.Name
FROM		dbo.fnMutualFriends('C', 'B') mf
ORDER BY	mf.Name

SELECT		mf.Name
FROM		dbo.fnMutualFriends('B', 'C') mf
ORDER BY	mf.Name

-- Clean up
DROP TABLE Contacts
NB: The order of pFrom and pTo doesn't matter. Try for yourself to switch columns for some pFrom and pTo. You will get the same result.


Peter Larsson
Helsingborg, Sweden

Edited by - SwePeso on 09/17/2006 03:54:25
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30240 Posts

Posted - 09/17/2006 :  03:48:27  Show Profile  Visit SwePeso's Homepage  Reply with Quote
Ooops! I forgot the function...
CREATE FUNCTION	dbo.fnMutualFriends
(
	@Want1 VARCHAR(2),
	@Want2 VARCHAR(2)
)
RETURNS @Mutual TABLE
(
	Name VARCHAR(2)
)
AS

BEGIN
	INSERT		@Mutual
			(
				Name
			)
	SELECT		x.Name
	FROM		(
				SELECT		pFrom Name
				FROM		Contacts
				WHERE		pTo = @Want1
				UNION
				SELECT		pTo
				FROM		Contacts
				WHERE		pFrom = @Want1
			) x
	INNER JOIN	(
				SELECT		pFrom Name
				FROM		Contacts
				WHERE		pTo = @Want2
				UNION
				SELECT		pTo
				FROM		Contacts
				WHERE		pFrom = @Want2
			) y ON y.Name = x.Name

	RETURN
END

Peter Larsson
Helsingborg, Sweden

Edited by - SwePeso on 09/17/2006 04:04:10
Go to Top of Page

harsh_athalye
Flowing Fount of Yak Knowledge

India
5514 Posts

Posted - 09/17/2006 :  03:55:59  Show Profile  Visit harsh_athalye's Homepage  Click to see harsh_athalye's MSN Messenger address  Send harsh_athalye a Yahoo! Message  Reply with Quote
Peter,

I am not sure what's wrong...but I am getting following error on SELECT statement:

"Invalid object name 'Contacts'"

Even when I have CONTACTS table and function in place.

Note: Error is in the final two select statements.

Harsh Athalye
India.
"Nothing is Impossible"

Edited by - harsh_athalye on 09/17/2006 03:56:56
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30240 Posts

Posted - 09/17/2006 :  04:03:26  Show Profile  Visit SwePeso's Homepage  Reply with Quote
You have to put the last two posts together.

09/17/2006 : 03:47:28 Example code with sample values
09/17/2006 : 03:48:27 Function code


Peter Larsson
Helsingborg, Sweden
Go to Top of Page

harsh_athalye
Flowing Fount of Yak Knowledge

India
5514 Posts

Posted - 09/17/2006 :  04:05:31  Show Profile  Visit harsh_athalye's Homepage  Click to see harsh_athalye's MSN Messenger address  Send harsh_athalye a Yahoo! Message  Reply with Quote
quote:
Originally posted by Peso

You have to put the last two posts together.

09/17/2006 : 03:47:28 Example code with sample values
09/17/2006 : 03:48:27 Function code


Peter Larsson
Helsingborg, Sweden



I did that...that's what troubling me!!

I have CONTACTS table and i have function - dbo.fnMutualFriends - too!

But still getting error in the select...may be I am missing something!!

Harsh Athalye
India.
"Nothing is Impossible"
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30240 Posts

Posted - 09/17/2006 :  04:07:54  Show Profile  Visit SwePeso's Homepage  Reply with Quote
Comment out the DROP Contacts from the example code. Just create the table and fill with sample data.
Then create function.

Now run "select mf.name from dbo.fnMutualFriends('E', 'G') mf"

I have no more ideas why the code doesn't work on your computer. dbo maybe?
I know you have run these kind of queries before.


Peter Larsson
Helsingborg, Sweden

Edited by - SwePeso on 09/17/2006 04:08:56
Go to Top of Page

harsh_athalye
Flowing Fount of Yak Knowledge

India
5514 Posts

Posted - 09/17/2006 :  04:11:45  Show Profile  Visit harsh_athalye's Homepage  Click to see harsh_athalye's MSN Messenger address  Send harsh_athalye a Yahoo! Message  Reply with Quote
Sorry Peter,

it was the damn problem with the object ownership on my system. It's working now !!!


Harsh Athalye
India.
"Nothing is Impossible"
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30240 Posts

Posted - 09/17/2006 :  04:15:37  Show Profile  Visit SwePeso's Homepage  Reply with Quote
Great!
Don't go scaring me like that in the future

zeus1, you should probably change Name to some kind of ID in the function.


Peter Larsson
Helsingborg, Sweden

Edited by - SwePeso on 09/17/2006 08:32:21
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30240 Posts

Posted - 09/18/2006 :  14:11:42  Show Profile  Visit SwePeso's Homepage  Reply with Quote
No answer, no feedback, from original poster.
Maybe the question was not that important after all?


Peter Larsson
Helsingborg, Sweden
Go to Top of Page

DonAtWork
Flowing Fount of Yak Knowledge

2161 Posts

Posted - 09/18/2006 :  14:40:06  Show Profile  Reply with Quote
He needed the answer for his test faster than you gave it. Try and keep up with that.

[Signature]For fast help, follow this link:
http://weblogs.sqlteam.com/brettk/archive/2005/05/25.aspx
Learn SQL
http://www.sql-tutorial.net/
http://www.firstsql.com/tutor.htm
http://www.w3schools.com/sql/default.asp
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30240 Posts

Posted - 09/18/2006 :  14:43:55  Show Profile  Visit SwePeso's Homepage  Reply with Quote
So less than a day is too long for exams?
And he did answer back 11 hours after first posting...


Peter Larsson
Helsingborg, Sweden

Edited by - SwePeso on 09/18/2006 14:45:11
Go to Top of Page

zeus1
Starting Member

3 Posts

Posted - 09/20/2006 :  12:44:08  Show Profile  Reply with Quote
Thank alot peso!. I saw another interesting approach before you
posted > see link

http://www.sitepoint.com/article/hierarchical-data-database/2

Having, your approach works just and well and it suits my purpose
since I can use current table structure.

Thanks again
Go to Top of Page

isfaar
Starting Member

11 Posts

Posted - 10/03/2006 :  07:15:42  Show Profile  Reply with Quote
Hi,

I need to know if any knows how to implement Djikstra's Algorithm in MS SQL. If any knows please help. Peso do you know.

I need to show how many steps is a person from the other.

Regards
Isfaar
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30240 Posts

Posted - 10/03/2006 :  07:41:50  Show Profile  Visit SwePeso's Homepage  Reply with Quote
Post this question as a new TOPIC and we will help you.
When posting, please provide table layout and sample data.


Peter Larsson
Helsingborg, Sweden
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30240 Posts

Posted - 10/03/2006 :  08:55:22  Show Profile  Visit SwePeso's Homepage  Reply with Quote
Ok, here it is anyway.
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'

-- This is the node chart of connections
/*
                    A - B 
                   /   / \ 
                  C - G   D 
                   \     / 
                    E - F 
*/

SELECT		dbo.fnCommonFriendsStep('E', 'G')

DROP TABLE Contacts



And here is the function
CREATE FUNCTION	dbo.fnCommonFriendsStep
(
	@Want1 VARCHAR(2),
	@Want2 VARCHAR(2)
)
RETURNS INT
AS

BEGIN
	IF @Want1 = @Want2
		RETURN 0

	DECLARE	@Friends TABLE (Generation INT, p VARCHAR(2))
	DECLARE	@Generation INT

	SELECT @Generation = 0

	INSERT	@Friends
		(
			Generation,
			p
		)
	SELECT	0,
		pFrom
	FROM	Contacts
	WHERE	pTo = @Want1
	UNION 
	SELECT	0,
		pTo
	FROM	Contacts
	WHERE	pFrom = @Want1

	WHILE NOT EXISTS (SELECT 1 FROM @Friends WHERE p = @Want2)
		BEGIN
			SELECT @Generation = @Generation + 1

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

	RETURN @Generation + 1
END


Peter Larsson
Helsingborg, Sweden
Go to Top of Page

SwePeso
Patron Saint of Lost Yaks

Sweden
30240 Posts

Posted - 10/03/2006 :  09:28:53  Show Profile  Visit SwePeso's Homepage  Reply with Quote
Here is some error management too!
The function returns -1 if no path is found
CREATE FUNCTION	dbo.fnCommonFriendsStep
(
	@Want1 VARCHAR(2),
	@Want2 VARCHAR(2)
)
RETURNS INT
AS

BEGIN
	IF @Want1 = @Want2
		RETURN 0

	DECLARE	@Friends TABLE (Generation INT, p VARCHAR(2))
	DECLARE	@Generation INT

	SELECT @Generation = 0

	INSERT	@Friends
		(
			Generation,
			p
		)
	SELECT	0,
		pFrom
	FROM	Contacts
	WHERE	pTo = @Want1
	UNION 
	SELECT	0,
		pTo
	FROM	Contacts
	WHERE	pFrom = @Want1

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

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

	RETURN @Generation + 1
END


Peter Larsson
Helsingborg, Sweden
Go to Top of Page
Page: of 2 Previous Topic Topic Next Topic  
Next Page
 New Topic  Reply to Topic
 Printer Friendly
Jump To:
SQL Server Forums © 2000-2009 SQLTeam Publishing, LLC Go To Top Of Page
This page was generated in 0.17 seconds. Powered By: Snitz Forums 2000