Существует ли элегантный способ хранения двойных отношений (т.е. пользователь 1 и пользователь 2 являются друзьями)

Question

В этом месяце я столкнулся с одной и той же проблемой на двух разных работах:

Version 1: User 1 & User 2 are friends
Version 2: Axis 1 & Axis 2 when graphed should have the quadrants colored...

Проблема в том, что я не вижу элегантного способа использования СУБД для хранения и запроса этой информации.

Есть два очевидных подхода:

Подход 1:

store the information twice (i.e. two db rows rows per relationship):
u1, u2, true 
u2, u1, true
u..n, u..i, true
u..i, u..n, true

have rules to always look for the inverse on updates: 
on read, no management needed
on create, create inverse
on delete, delete inverse
on update, update inverse

Advantage:    management logic is always the same.
Disadvantage: possibility of race conditions, extra storage (which is admittedly cheap, but feels wrong)

Подход 2:

store the information once (i.e. one db row per relationship)
u1, u2, true
u..n, u..i, true

have rules to check for corollaries:
on read, if u1, u2 fails, check for u2, u1 
on create u1, u2: check for u2, u1, if it doesn't exist, create u1, u2
on delete, no management needed
on update, optionally redo same check as create

Advantage: Only store once
Disadvantage: Management requires different set of cleanup depending on the operation

Мне интересно, есть ли 3-й подход, который идет по принципу «ключа» с использованием f (x, y), где f (x, y) уникален для каждой комбинации x, y и где f (x, y) === f (y, x) "

Моя интуиция говорит мне, что должна быть некоторая комбинация побитовых операций, которая может удовлетворить эти требования. Что-то вроде двух колонок:

key1 = x && y key2 = x + y

Я надеюсь, что люди, которые провели больше времени в математическом отделе и меньше времени в социологическом отделе, увидели доказательство возможности или невозможности этого и могут обеспечить быстрое "[Вы, придурок], это легко доказано (im) возможно, см. эту ссылку "(имя не обязательно)

Любой другой элегантный подход также будет приветствоваться.

Спасибо

Answer 1

Существует также способ использовать 2-й подход, добавив дополнительное ограничение.Убедитесь, что u1 < u2:

CREATE TABLE User
( Name VARCHAR(10) NOT NULL
, PRIMARY KEY (Name)
) ;

CREATE TABLE MutualFriendship
( u1 VARCHAR(10) NOT NULL
, u2 VARCHAR(10) NOT NULL
, PRIMARY KEY (u1, u2)
, FOREIGN KEY (u1) 
    REFERENCES User(Name)
, FOREIGN KEY (u2) 
    REFERENCES User(Name)
, CHECK (u1 < u2) 
) ;

Правила чтения, создания, вставки или обновления должны использовать (LEAST(u1,u2), GREATEST(u1,u2)).

Answer 2

В SQL легко реализовать ограничения для поддержки вашего первого подхода:

CREATE TABLE MutualFriendship
(u1 VARCHAR(10) NOT NULL,
 u2 VARCHAR(10) NOT NULL,
 PRIMARY KEY (u1,u2),
 FOREIGN KEY (u2,u1) REFERENCES MutualFriendship (u1,u2));

INSERT INTO MutualFriendship VALUES
('Alice','Bob'),
('Bob','Alice');

Answer 3

Для всех, кто заинтересован, я поиграл с несколькими побитовыми операциями и обнаружил, что следующее, кажется, соответствует критериям для f (x, y):

#Python, returns 3 tuple
def get_hash(x, y):
  return (x & y, x | y, x * y)

Хотя я не могу доказать это.

Answer 4

"x - друг y".

Определить таблицу (x, y) пар и ввести каноническую форму, например, x

Answer 5

Вы, похоже, ограничиваете количество друзей до 1. Если это так, то я бы использовал что-то вроде u1, u2 u2, u1 u3, null u4, u5 u5, u4

u3 не имеетдруг.