How to relate two rows in the same table

Question

I have a table where the rows can be related to each other, and logically, the relationship goes both ways (basically, is directionless) between the two rows. (And if you're wondering, yes, this really should be one table. It is two things of the exact same logical entity/type.) I can think of a couple ways to represent this:

1. Store the relationship and its reverse
2. Store the relationship one way, constrain the database from storing it the other way, and have two indexes with opposite orders for the FKs (one index being the PK index)
3. Store the relationship one way with two indexes and allow the second to be inserted anyway (sounds kind of yucky, but hey, completeness)
4. Create some kind of grouping table and have an FK to it on the original table to it. (Raises lots of question. Grouping table would only have a number; why even have the table? Make FK NULLable or have groups with single row associated?)

What are some major pros and cons of these ways, and of course, is there some way I haven't thought of?

Here's a SQLFiddle to play with: http://sqlfiddle.com/#!12/7ee1a/1/0. (Happens to be PostgreSQL since that's what I'm using, but I don't think this question is very specific to PostgreSQL.) It currently stores both the relationship and its reverse just as an example.

Answer 1

What you have designed is good. What needs to be added is a constraint to make the relationship directionless. So, you cannot have a (1,5) row without a (5,1) row being added as well.

This can be accomplished^* with a self referencing constraint on the bridge table.

*: _{it can be accomplished in Postgres, Oracle, DB2 and all DBMS that have implemented foreign key constraints as the SQL standard describes (deferred, e.g. checked at the end of transaction.) Deferred checking is not really needed anyway, as in SQL-Server that checks them at the end of statement and this construction still works. You cannot do this in MySQL because "InnoDB checks UNIQUE and FOREIGN KEY constraints row-by-row".}

So, in Postgres the following will match your requirements:

CREATE TABLE x
(
  x_id SERIAL NOT NULL PRIMARY KEY,
  data VARCHAR(10) NOT NULL
);

CREATE TABLE bridge_x
(
  x_id1 INTEGER NOT NULL REFERENCES x (x_id),
  x_id2 INTEGER NOT NULL REFERENCES x (x_id),
  PRIMARY KEY(x_id1, x_id2),
  CONSTRAINT x_x_directionless
    FOREIGN KEY (x_id2, x_id1)
    REFERENCES bridge_x (x_id1, x_id2)
);

Tested at: SQL-Fiddle

If you try to add a row (1,5):

INSERT INTO bridge_x VALUES
(1,5) ;

It fails with:

ERROR: insert or update on table "bridge_x" violates foreign key constraint "x_x_directionless"
Detail: Key (x_id2, x_id1)=(5, 1) is not present in table "bridge_x".:
INSERT INTO bridge_x VALUES (1,5)

Additionally, you can add a CHECK constraint if you want to forbid (y,y) rows:

ALTER TABLE bridge_x
  ADD CONSTRAINT x_x_self_referencing_items_not_allowed
    CHECK (x_id1 <> x_id2) ;

---

There are other ways to implement this as you mention, like storing only one direction of the relationship (in one row, not two) by forcing the lower id in x_id1 and the higher id in the x_id2 column. It looks easier to implement, but usually leads to more complex queries later:

CREATE TABLE bridge_x
(
  x_id1 INTEGER NOT NULL REFERENCES x (x_id),
  x_id2 INTEGER NOT NULL REFERENCES x (x_id),
  PRIMARY KEY(x_id1, x_id2),
  CONSTRAINT x_x_directionless
    CHECK (x_id1 <= x_id2)                       -- or "<" to forbid `(y,y)` rows
);