Completing relationship table
What I mean about completing relationship table is to define relationship 3 -> 1 whenever 1 -> 3 is defined. Thus, we’ll always have both directions of friendship relationship. Doing this can be done in straight SQL. Here’s what we need to do:
- Select all existing data from relationship table.
- Union it with the reverse direction relationship.
- Get the result of the union that doesn’t exist in existing table
- Insert the data above into relationship table.
Here’s the SQL to do that:
-- 4. Insert the resulting data into relationship. INSERT INTO relationship SELECT complete_relationship.* FROM ( -- 1. Select all existing data from relationship table. SELECT user_id, friend_id, weight FROM relationship UNION -- 2. Reverse direction relationship. SELECT friend_id AS user_id, user_id AS friend_id, weight FROM relationship ) AS complete_relationship -- 3. Data that doesn't exist in existing table LEFT JOIN relationship ON complete_relationship.user_id = relationship.user_id AND complete_relationship.friend_id = relationship.friend_id WHERE relationship.user_id IS NULL;
Start working towards Floyd-Warshal algorithm function
I’d like to try to make this function as closely resembles my PHP version that I wrote before in the article Computing degrees of separation in social networking.
Unlike the PHP version, PostgreSQL’s stored procedure function has access to the relationship data. Within the function, we can get the relationship data and the minimum & maximum user_id simply by querying relationship table. So let’s define the variables. First, we need to declare the variable to be used in PL/pgSQL.
DECLARE min_id INTEGER; max_id INTEGER; res INTEGER;
Then we need to populate the variables. Note that we can simply select the minimum and maximum values of user_id because we’ve made the table “complete”; e.g. relationship between 0 -> 3 and 3 ->0 are defined.
SELECT INTO min_id MIN(user_id) FROM relationship; SELECT INTO max_id MAX(user_id) FROM relationship;