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!"
Go to Top of Page

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
Go to Top of Page

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
Go to Top of Page

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.

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
Go to Top of Page

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
Go to Top of Page

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
Go to Top of Page

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"
Go to Top of Page

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
Go to Top of Page

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"
Go to Top of Page

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
Go to Top of Page

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"
Go to Top of Page

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
Go to Top of Page

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
Go to Top of Page

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
Go to Top of Page

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
Go to Top of Page

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
Go to Top of Page

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
Go to Top of Page

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
Go to Top of Page

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
Go to Top of Page

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
Go to Top of Page
  Previous Page&nsp;  Next Page

- Advertisement -