Social Networking > SQL Statement

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

SQL Server Development (2000)

Social Networking > SQL Statement

Author

Topic

zeus1
Starting Member

3 Posts

Posted - 2006-09-16 : 07:52:17

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
Master Smack Fu Yak Hacker

2365 Posts

Posted - 2006-09-16 : 16:37:43

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!"

spirit1
Cybernetic Yak Master

11752 Posts

Posted - 2006-09-16 : 16:39:42

care to show us the whole article?

Go with the flow & have fun! Else fight the flow

blog thingie: http://weblogs.sqlteam.com/mladenp

zeus1
Starting Member

3 Posts

Posted - 2006-09-16 : 18:21:20

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

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-09-17 : 03:27:20

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.

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

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-09-17 : 03:47:28

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

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-09-17 : 03:48:27

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

harsh_athalye
Master Smack Fu Yak Hacker

5581 Posts

Posted - 2006-09-17 : 03:55:59

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"

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-09-17 : 04:03:26

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

harsh_athalye
Master Smack Fu Yak Hacker

5581 Posts

Posted - 2006-09-17 : 04:05:31

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"

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-09-17 : 04:07:54

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

harsh_athalye
Master Smack Fu Yak Hacker

5581 Posts

Posted - 2006-09-17 : 04:11:45

Sorry Peter,

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

Harsh Athalye
India.
"Nothing is Impossible"

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-09-17 : 04:15:37

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

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-09-18 : 14:11:42

No answer, no feedback, from original poster.
Maybe the question was not that important after all?

Peter Larsson
Helsingborg, Sweden

DonAtWork
Master Smack Fu Yak Hacker

2167 Posts

Posted - 2006-09-18 : 14:40:06

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

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-09-18 : 14:43:55

So less than a day is too long for exams?

And he did answer back 11 hours after first posting...

Peter Larsson
Helsingborg, Sweden

zeus1
Starting Member

3 Posts

Posted - 2006-09-20 : 12:44:08

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

isfaar
Starting Member

11 Posts

Posted - 2006-10-03 : 07:15:42

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

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-10-03 : 07:41:50

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

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-10-03 : 08:55:22

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

SwePeso
Patron Saint of Lost Yaks

30421 Posts

Posted - 2006-10-03 : 09:28:53

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

Next Page

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources