SQL Server: how to select First, Second and Third degree contacts

Question

I'm working on a social web-site project and I need to list "First, Second and Third Degree Contacts" of my contacts. I'm using SQL Server AND C#

Assume a contact table like this:

For first degree contact:

• If gulsah is me then my first degree contacts are burak,sennur

Query I use to select this:

SELECT contact_2 FROM Contacts_Table WHERE contact_1 like 'gulsah'

For second degree contact:

If gulsah is me again then my second degree contacts are: mali

What makes it difficult is to select contacts of my contacts who are not my first degree contact.

I can select mutual contacts but I guess it is not the right approach.

For example, to select mutual contacts of me (gulsah) and burak:

SELECT contact_1 FROM (SELECT * FROM Contact_Test 
  WHERE contact_2 like 'burak') a
     INNER JOIN (SELECT contact_1 FROM Contact_Test 
     WHERE (contact_2 = 'gulsah')) b 
ON a.contact_1 = b.contact_1

This query works but as I said, it's not the right approach for this job.

For third degree contact:

If gulsah is me again then my third degree contacts are_ mehmet,ahmet

I need to select contacts of my contacts' contacts who are not my first and second degree contact :)

Here is a post from Linkedin which explains contact level.

Thanks for responses.

Answer 1

What makes it difficult is to select contacts of my contacts who are not my first degree contact.

You could use the EXCEPT operator.

First-degree contacts:

SELECT contact_2 FROM contact WHERE contact_1 = 'gulsah'

Second-degree contacts who are not first-degree contacts:

SELECT
  contactB.contact_2
FROM 
  contact AS contactB
  INNER JOIN contact AS contactA ON contactA.contact_2=contactB.contact_1
WHERE contactA.contact_1 = 'gulsah'
EXCEPT
SELECT contact_2 FROM contact WHERE contact_1 = 'gulsah'

EXCEPT tells SQL server to return all the results from the first SELECT that do NOT appear in the second SELECT.

For third-degree contacts (who are not first- or second-degree contacts):

SELECT
  contactC.contact_2
FROM 
  contact AS contactC
  INNER JOIN contact AS contactB ON contactB.contact_2=contactC.contact_1
  INNER JOIN contact AS contactA ON contactA.contact_2=contactB.contact_1
WHERE contactA.contact_1 = 'gulsah'
EXCEPT
(
SELECT contact_2 FROM contact WHERE contact_1 = 'gulsah'
UNION
SELECT
  contactB.contact_2
FROM 
  contact AS contactB
  INNER JOIN contact AS contactA ON contactA.contact_2=contactB.contact_1
WHERE contactA.contact_1 = 'gulsah'
)

I don't hold high hopes for performance, but of course you will need to check this yourself.

---

As a side note:

I can select mutual contacts but I guess it is not the right approach.

Use INTERSECT for this.

Answer 2

Here's my approach:

1. Add my contact to a special collected contact list.

2. For every contact in the collected list as Contact_1 of the contact table, add its corresponding Contact_2 unless that contact is already in the collected list.

3. Repeat step #2 the number of times that is the target degree number minus one.

4. Repeat the query in step #2 once more, but this time simply return the result set (do not add the rows to the collected list).

The script:

DECLARE @MyContact varchar(50), @DegreeNumber int;
SET @MyContact = 'gulsah';
SET @DegreeNumber = 3;

DECLARE @CollectedContacts TABLE (Contact varchar(50));
INSERT INTO @CollectedContacts (Contact) VALUES (@MyContact);

WHILE @DegreeNumber > 1 BEGIN
  INSERT INTO @CollectedContacts (Contact)
  SELECT ct.Contact_2
  FROM Contacts_Table ct
    INNER JOIN @CollectedContacts cc ON ct.Contact_1 = cc.Contact
    LEFT JOIN @CollectedContacts cc2 ON ct.Contact_2 = cc2.Contact
  WHERE cc2.Contact IS NULL;

  SET @DegreeNumber = @DegreeNumber - 1;
END;

SELECT ct.Contact_2
FROM Contacts_Table ct
  INNER JOIN @CollectedContacts cc ON ct.Contact_1 = cc.Contact
  LEFT JOIN @CollectedContacts cc2 ON ct.Contact_2 = cc2.Contact
WHERE cc2.Contact IS NULL;

As you can see, both the degree number and 'my' contact are parametrisable. I'm using the varchar type for contacts, but that of course can easily be replaced with int, if needed.

Answer 3

maybe this helps: http://techportal.ibuildings.com/2009/09/07/graphs-in-the-database-sql-meets-social-networks/