Assuming source data is in a table: Connections:(PersonID, KnowsPersonID)
1) This will have to use a breadth first approach. Your potential for good performance is limited due to the exponential nature of the problem (although this exponential nature is why theoretically you only need 6 degrees :D). Make sure you limit the depth of your search. Whichever flavour of SQL you choose you'll probably be better off using its iterative extensions as opposed to a pure set based solution.
The following would be the basic approach using Microsoft's T-SQL:
CREATE PROCEDURE FindPath (@UserX int, @UserY int)
CREATE TABLE #SixDegrees(
ConnectedUser int,
Depth int,
Path varchar(100),
CONSTRAINT PK_SixDegrees PRIMARY KEY CLUSTERED (
ConnectedUser
)
)
DECLARE @Depth int,
@PathFound varchar(100)
SET @Depth = 0
INSERT INTO #SixDegrees (@UserX, 0, CAST(@UserX as varchar))
/*Next line just in case X & Y are the same*/
SET @PathFound = (SELECT Path
FROM #SixDegrees
WHERE ConnectedUser = @UserY)
WHILE @Depth < 6 AND @PathFound IS NULL
BEGIN
SET @Depth = @Depth + 1
INSERT INTO #SixDegrees
SELECT k.KnowsPersonID, @Depth, (SELECT Path
FROM #SixDegrees
WHERE ConnectedUser = k.Link) + ',' + CAST(k.KnowsPersonID AS varchar)
FROM (
SELECT MIN(ConnectedUser) Link, KnowsPersonID
FROM #SixDegrees
JOIN Connections ON
PersonID = ConnectedUser
WHERE Depth = @Depth
/*EDIT: Added the following*/
AND KnowsPersonID NOT IN (
SELECT ConnectedUser
FROM #SixDegrees
)
GROUP BY KnowsPersonID
) k
SET @PathFound = (SELECT Path
FROM #SixDegrees
WHERE ConnectedUser = @UserY)
END
IF @Path IS NULL
PRINT 'No path found'
ELSE
PRINT @Path
GO
EDIT: In the above solution I originally forgot to exclude users already in the #SixDegrees temp table.
2) A little tweak on the above to always loop to a depth of 3 would leave you with #SixDegrees containing all the Users you're interested in.
However, the following pure set based solution should be more efficient:
SELECT DISTINCT KnowsPersonID
FROM Connections
WHERE PersonID IN (
SELECT DISTINCT KnowsPersonID
FROM Connections
WHERE PersonID IN (
SELECT KnowsPersonID
FROM Connections
WHERE PersonID = @UserX
) l1
) l2