create table test_connect_by (
  parent     number,
  child      number,
  constraint uq_tcb unique (child)
);
[download]

insert into test_connect_by values ( 5, 2);
insert into test_connect_by values ( 5, 3);
insert into test_connect_by values (18,11);
insert into test_connect_by values (18, 7);
insert into test_connect_by values (17, 9);
insert into test_connect_by values (17, 8);
insert into test_connect_by values (26,13);
insert into test_connect_by values (26, 1);
insert into test_connect_by values (26,12);
insert into test_connect_by values (15,10);
insert into test_connect_by values (15, 5);
insert into test_connect_by values (38,15);
insert into test_connect_by values (38,17);
insert into test_connect_by values (38, 6);
insert into test_connect_by values (null,38);
insert into test_connect_by values (null,26);
insert into test_connect_by values (null,16);
[download]

select lpad(' ',2*(level-1)) || to_char(child) s 
  from test_connect_by 
  start with parent is null
  connect by prior child = parent;
[download]

38
  15
    10
    5
      2
      3
  17
    9
    8
  6
26
  13
  1
  12
16
[download]

its not working in sql 2005

It won't, Microsoft SQL Server 2005 doesn't support CONNECT BY PRIOR. See recursive common table expression. Supported by Oracle (version dependent) and SQL Server.

Update: See also Simulation of CONNECT BY PRIOR of ORACLE in SQL SERVER

ten reasons postgresql is better than sqlserver.

Here are a few links that may be helpful:

• storing tree-like structures in tables
• RFC: DBIx::Tree::NestedSet
• http://mark.stosberg.com/Bookmarks/Database/Information_on_Tree_data/

HTH

The thread got a little traction today so FTR I'll add the newer and extremely interesting: DBIx::Class::Tree::Mobius.

You will have to run one query per degree of separation.

I'll assume the following schema (SQLite dialect):

CREATE TABLE person (
    id   INTEGER NOT NULL,
    name TEXT,
    PRIMARY KEY ( id )
);
CREATE TABLE friend (
    person INTEGER NOT NULL,
    friend INTEGER NOT NULL,
    PRIMARY KEY ( person, friend )
);
[download]

Then your graph would be

With this you can figure out a person's friends by joining the tables:

sqlite> SELECT P1.name, P2.name                              
   ...> FROM person P1 
   ...> JOIN friend F ON P1.id = F.person 
   ...> JOIN person P2 ON F.friend = P2.id 
   ...> WHERE P1.name = 'Bob' ;
P1.name|P2.name
Bob|Al
Bob|Doug
Bob|Gary
[download]

For the friends' friends you use a subselect:

sqlite> SELECT P1.name, P2.name
   ...> FROM person P1
   ...> JOIN friend F ON P1.id = F.person
   ...> JOIN person P2 ON F.friend = P2.id
   ...> WHERE P1.id IN (     
   ...>   SELECT F.friend
   ...>   FROM person P
   ...>   JOIN friend F ON P.id = F.person
   ...>   WHERE P.name = 'Bob'
   ...> ) ;
P1.name|P2.name
Al|Bob
Al|Chuck
Al|Frank
Al|Ibrahim
Doug|Bob
Doug|Chuck
Doug|Hamza
Gary|Bob
Gary|Hamza
Gary|Ibrahim
[download]

And so on and so forth, analogously:

sqlite> SELECT P1.name, P2.name
   ...> FROM person P1
   ...> JOIN friend F ON P1.id = F.person
   ...> JOIN person P2 ON F.friend = P2.id
   ...> WHERE P1.id IN (
   ...>   SELECT F.friend
   ...>   FROM person P
   ...>   JOIN friend F ON P.id = F.person
   ...>   WHERE P.id IN (
   ...>     SELECT F.friend
   ...>     FROM person P
   ...>     JOIN friend F ON P.id = F.person
   ...>     WHERE P.name = 'Bob'
   ...>   )
   ...> );
Bob|Al
Bob|Doug
Bob|Gary
Chuck|Al
Chuck|Doug
Chuck|Ed
Chuck|Frank
Frank|Al
Frank|Chuck
Hamza|Doug
Hamza|Gary
Ibrahim|Al
Ibrahim|Gary
[download]

I used SELECT P1.name, P2.name at the top level SELECT for demonstration purposes. In practice you will want SELECT DISTINCT P2.name.

Makeshifts last the longest.

boulevard,

Since I specifically remember talking to you earlier about this scenario, here are some additional links that I think you will find useful.

NOTE: The numbers after the links are my own 'relevance ratings' based on the similarity of the content to your current project and background (i.e., you already have something that "works", and now you just want alternatives)(i.e., you are looking for reader-friendly overview materials on this subject). If this is a fair characterization of your situation, then these are definitely for you.

NOTE: The links provided here could also be found further down in the articles and nodes in dbwiz's excellent answer.

NOTE: If you are already using Oracle (which I just blankly assumed you weren't) then these links are probably not as useful, but still good reading in case you're interested. Try the Oracle-specific approach mentioned elsewhere in this thread.

update: Aristotle's answer also matches what you were looking for, he's faster with the "create article" button than scooterm :)

Something like this should work, except you'll need to use code specific to your database where I've written the select statements inline.

@new = ('Al');
while(@new){
 $key = shift @new;
 push @old, $key;
 @friends = (select col1 from table where col2 = $key,
             select col2 from table where col1 = $key);
 %unique = ();
 @unique{@friends} = undef;
 delete @unique{@new, @old};
 push @new, keys %unique;
}
[download]

If

• Your number of people is small
• You plan on asking this question a ton of times

The major improvement that this has over a SQL solution is that it will scale better the more friendships you have. If you have, say, 50 people in your database and each is friends with 20 people, you have 50 vertices and 1000 edges. If each person meets 5 people, you still have 50 people, but 1250 edges. If done poorly, the friendship table in Aristotle's solution will bog you down.

I also have a version of Graph::Undirected^* that is optimized for this type of analysis (unique edges between vertices) which is up to 4x faster than the generic Graph::Undirected on CPAN.

*: Jarrko's aware of it.