| Author |
 Topic  |
|
zeus1
Starting Member
3 Posts |
 Posted - 09/16/2006 : 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
Flowing Fount of Yak Knowledge
USA
2365 Posts |
Posted - 09/16/2006 : 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
Slovenia
11741 Posts |
|
|
zeus1
Starting Member
3 Posts |
Posted - 09/16/2006 : 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
Sweden
29156 Posts |
Posted - 09/17/2006 : 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 |
Edited by - SwePeso on 09/17/2006 03:52:19 |
|
|
|
SwePeso
Patron Saint of Lost Yaks
Sweden
29156 Posts |
Posted - 09/17/2006 : 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 ContactsNB: 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 |
|
|
|
SwePeso
Patron Saint of Lost Yaks
Sweden
29156 Posts |
Posted - 09/17/2006 : 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 |
Edited by - SwePeso on 09/17/2006 04:04:10 |
|
|
|
harsh_athalye
Flowing Fount of Yak Knowledge
India
5509 Posts |
Posted - 09/17/2006 : 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" |
Edited by - harsh_athalye on 09/17/2006 03:56:56 |
|
|
|
SwePeso
Patron Saint of Lost Yaks
Sweden
29156 Posts |
Posted - 09/17/2006 : 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
Flowing Fount of Yak Knowledge
India
5509 Posts |
Posted - 09/17/2006 : 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
Sweden
29156 Posts |
Posted - 09/17/2006 : 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 |
Edited by - SwePeso on 09/17/2006 04:08:56 |
|
|
|
harsh_athalye
Flowing Fount of Yak Knowledge
India
5509 Posts |
Posted - 09/17/2006 : 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
Sweden
29156 Posts |
Posted - 09/17/2006 : 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 |
Edited by - SwePeso on 09/17/2006 08:32:21 |
|
|
|
SwePeso
Patron Saint of Lost Yaks
Sweden
29156 Posts |
Posted - 09/18/2006 : 14:11:42
|
No answer, no feedback, from original poster.
Maybe the question was not that important after all?
Peter Larsson
Helsingborg, Sweden |
|
|
|
DonAtWork
Flowing Fount of Yak Knowledge
2113 Posts |
|
|
SwePeso
Patron Saint of Lost Yaks
Sweden
29156 Posts |
Posted - 09/18/2006 : 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 |
Edited by - SwePeso on 09/18/2006 14:45:11 |
|
|
|
zeus1
Starting Member
3 Posts |
|
|
isfaar
Starting Member
11 Posts |
Posted - 10/03/2006 : 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
Sweden
29156 Posts |
Posted - 10/03/2006 : 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
Sweden
29156 Posts |
Posted - 10/03/2006 : 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 functionCREATE 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
Sweden
29156 Posts |
Posted - 10/03/2006 : 09:28:53
|
Here is some error management too!
The function returns -1 if no path is foundCREATE 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 |
|
|
|
Topic |
|
Social Networking > SQL Statement
