database - tutorial - the django project

¿Existe una forma elegante de 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 trabajos diferentes 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 que 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 tercer enfoque que sigue las líneas de "clave 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 columna doble:

key1 = x && y key2 = x + y

Espero que las personas que pasaron más tiempo en el departamento de matemática y menos tiempo en el departamento de sociología hayan visto una prueba de la posibilidad o imposibilidad de esto y puedan proporcionar un rápido "[Usted es un imbécil,] es fácil de probar (im) posible, mira este enlace "(nombre de llamada opcional)

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

Gracias

Answer 1

"x es un amigo de y".

Defina una tabla de pares (x, y) y aplique una forma canónica, por ejemplo, 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".

Cree una vista como SELECT x, y FROM FRIENDS UNION SELECCIONE x como y, y como x FROM FRIENDS.

Haga sus actualizaciones en la tabla base (inconveniente: los actualizadores deben conocer la forma canónica impuesta), haga sus consultas en contra de la vista.

Answer 2

En SQL es fácil implementar las restricciones para respaldar su primer enfoque:

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

Para cualquiera que esté interesado, jugué con algunas operaciones bit a bit y descubrí que lo 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 probarlo, sin embargo.

Answer 4

Parece que limita el número de amigos a 1. Si este es el caso, entonces usaría algo como u1, u2 u2, u1 u3, null u4, u5 u5, u4

u3 no tiene un amigo

Answer 5

También hay una forma de usar el segundo enfoque agregando 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 usar (LEAST(u1,u2), GREATEST(u1,u2)) .