Y at-il une façon élégante de stocker une relation double (à savoir l'utilisateur 1 et l'utilisateur 2 sont des amis)

Question

J'ai couru dans le même problème dans deux pièces différentes de travail ce mois-ci:

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

Le problème est, je ne vois pas une manière élégante, en utilisant un SGBDR, pour stocker ces informations et requête.

Il existe deux approches évidentes:

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

Approche 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

Je me demande s'il y a une 3ème approche qui va dans le sens de « clé en utilisant f (x, y) où f (x, y) est unique pour chaque x, combinaison y et où f (x, y) === f (y, x) »

Mon instinct me dit qu'il devrait y avoir une combinaison d'opérations qui peuvent répondre à bitwise ces exigences. Quelque chose comme un à deux colonnes:

clé1 = x && y key2 = x + y

J'espère que les gens qui ont passé plus de temps dans le département de mathématiques, et moins de temps dans le département de sociologie ont vu une preuve de la possibilité ou l'impossibilité de cela et peut apporter une réponse rapide « [Crétin,] sa facile à prouver (im) possible, voir ce lien »(nom de l'appelant en option)

Toute autre approche élégante serait très bienvenue.

Merci

Answer 1

Il y a aussi un moyen d'utiliser la 2ème approche en ajoutant une contrainte supplémentaire. Assurez-vous 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) 
) ;

Les règles à lire, créer, insérer ou mettre à jour devront utiliser le (LEAST(u1,u2), GREATEST(u1,u2)).

Answer 2

Dans SQL il est facile de mettre en œuvre les contraintes pour soutenir votre première approche:

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

Pour toute personne qui est intéressé, j'ai joué avec quelques opérations binaires et a constaté que les éléments suivants semble remplir les critères pour f (x, y):

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

Je ne peux pas le prouver, cependant.

Answer 4

"x est un ami de y".

définir une table de (x, y) paires et d'appliquer une forme canonique, par exemple x

Créer une vue comme SELECT x, y AMIS DE L'UNION SELECT x que y, y que x de ses amis.

Faites vos mises à jour sur la table de base (inconvénient: updaters doivent être conscients de la forme canonique appliquée)., Faites vos requêtes sur la vue

Answer 5

Vous semblez limiter le nombre d'amis à 1. Si tel est le cas, alors j'utiliser quelque chose comme u1, u2 u2, u1 u3, null U4, U5 U5, U4

u3 ne dispose pas d'un ami.