¿Hay una manera elegante para almacenar una relación dual (es decir, el usuario 1 y el usuario 2 son amigos)

Question

me he encontrado con el mismo problema en dos piezas diferentes de trabajo de este mes:

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

El problema es , No veo una manera elegante, usando un RDBMS, para almacenar y consultar esta información.

Hay dos enfoques obvios:

Enfoque 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) 

Enfoque 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 

Me pregunto si hay un enfoque tercero que va a lo largo de las líneas de " tecla usando f (x, y) donde f (x, y) es único para cada combinación x, y y donde f (x, y) === f (y, x) "

Mi instinto me dice que debe haber una combinación de operaciones bit a bit que puedan cumplir estos requisitos. Algo así como una de dos columnas:

key1 = x & & y clave2 = x + y

que espero que la gente que pasaban más tiempo en el departamento de matemáticas, y menos tiempo en el departamento de sociología tienen visto una prueba de la posibilidad o imposibilidad de esto y puede proporcionar un rápido "[Usted es idiota,] es fácilmente probado (im) posible, consulte este enlace" (nombre de llamada opcional)

Cualquier otro enfoque elegante también sería muy Bienvenido.

Gracias

Answer 1

También hay una manera de utilizar el segundo enfoque mediante la adición de una restricción adicional. Compruebe que 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) 
) ; 

Las reglas para leer, crear, insertar o actualizar tendrán que utilizar el (LEAST(u1,u2), GREATEST(u1,u2)).

Answer 2

Se parecen limitar el número de amigos a 1. Si este es el caso, entonces me gustaría utilizar algo así como U1, U2 u2, u1 U3, U4 nula, U5 U5 , u4

u3 no tiene ningún amigo.

Answer 3

En SQL que es fácil de implementar las restricciones para apoyar su primera aproximación:

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 4

Para cualquiera que esté interesado, He jugado un poco con algunas operaciones bit a bit y se encontró que el siguiente parece cumplir los criterios para f (x, y):

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

no puedo demostrar que, aunque .

Answer 5

"x es un amigo de y".

Defina una tabla de pares (x, y) y aplique una forma canónica, p. x < y.Esto asegurará que no pueda tener ambos (p, q) y (q, p) en su base de datos, por lo que se asegurará de "almacenar una vez".

Crear una vista como SELECCIONAR x, y DESDE FRIENDS UNION SELECCIONAR x como y, y como x DE FRIENDS.

Actualice la tabla base (aspecto negativo: los actualizadores deben tener en cuenta la forma canónica obligatoria), haga sus consultas en contra de la vista.