Message-ID: <422A8A26.1070704@foo.at>
Date: Sun, 06 Mar 2005 05:42:14 +0100
From: Stefan Weiss <spaceman@foo.at>
Organization: Foo Orbital Operations
User-Agent: Mozilla Thunderbird 1.0 (X11/20041206)
MIME-Version: 1.0
To: pgsql-sql@postgresql.org
Subject: Links between rows in a table
Content-Type: text/plain; charset=ISO-8859-15
Content-Transfer-Encoding: 7bit

Hi.

We are currently designing a web-based application in which users can
add other users as "friends". These links are bi-directional, meaning
that when A adds B to his friends, he is automatically one of B's
friends. Eventually we will have to add a feature that shows how A is
is related to some other user E (via B->C->D->...) - similar to the way
Friendster, Orkut and others work, but on a much smaller scale (some
5000 users).

Probably the most annoying part is that it has to work with different
database vendors, including MySQL4 (default install, MyISAM tables, no
foreign keys, no stored procedures, no triggers, no views etc). Most of
the logic will have to live in the application, and I won't be able to
use anything beyond plain SQL.

I can see several ways how such links could be modeled in a relational
database, but I was wondering if there was some tried-and-true recipe
that would spare me from reinventing the wheel. Putting aside for the
moment everything but the links, the simplest way of connecting users
would be a "friends" table (user_id int, friend_id int). We could get a
user's friends with a simple query like this:

        SELECT friend_id FROM friends WHERE user_id   = X
  UNION SELECT user_id   FROM friends WHERE friend_id = X;

Is there a better way, or any reason why we should not go that way,
especially considering other likely queries such as "friends of friends"
or the connection chain mentioned above?

We are also thinking of precalculating possible connection chains, or
trees, at night (to a certain depth) in order to avoid performance
problems in the peak hours. Any ideas on how such precalculated results
could be stored and queried efficiently?


Thanks in advance,
Stefan Weiss