match circulaire

Question

J'ai une base de données avec trois tables: userid_tbl, need_tbl, have_tbl

create table userid_tbl 
(user_id varchar2(15) not null primary key); 

create table need_tbl 
(user_id varchar2(15) not null, 
have_item varchar2(100) not null, 
foreign key (user_id) references userid_tbl (user_id) 
); 

create table have_tbl 
(user_id varchar2(15) not null, 
have_item varchar2(100) not null, 
foreign key (user_id) references userid_tbl (user_id) 
); 

Chaque utilisateur peut créer un nombre illimité d'enregistrements de besoins ou des services qu'ils peuvent fournir aux autres dans la base de données. Les articles proviennent d'une liste prédéterminée.

Après avoir fait une jointure sur la nécessité et ont table, j'avons identifié les besoins et les besoins, et mis au rebut les demandes qui ne peuvent pas être remplies par un utilisateur dans une vue qui ressemble à ceci:

Item:   Need:   Have: 
1    Bob    George 
2    George   Herbie 
3    Herbie   Bob 
4    Larry   Wally 
5    Wally   Larry 
6    John    George 

J'essaye maintenant d'écrire une requête où je peux calculer le nombre de permutations de chaque utilisateur ayant leurs besoins demandés remplis. Par exemple, dans l'exemple ci-dessus, Bob, George et Herbie peuvent satisfaire ensemble les besoins de chacun, tout comme Larry et Wally, mais John ne le peut pas, donc le nombre total serait de 2.

J'ai d'abord commencé à le faire avec une boucle, mais il doit y avoir une façon plus simple et moins gourmande en ressources de le faire avec une seule requête.

Answer 1

Voir l'article dans mon blog pour des explications détaillées:

• Finding loops in a tree

Si vos utilisateurs se trouvent plus d'une fois dans la colonne needs de la table, il est une NP tâche complexe.

Dans le cas contraire, exécutez cette requête sur votre point de vue:

SELECT COUNT(*) 
FROM v_needs 
CONNECT BY NOCYCLE 
     need = PRIOR have 
WHERE CONNECT_BY_ISCYCLE = 1 

CONNECT BY NOCYCLE permet des boucles dans les requêtes hiérarchiques (NOCYCLE arrête juste une branche quand il trouve une boucle, pas NOCYCLE renvoie une erreur).

CONNECT_BY_ISCYCLE renvoie true à chaque fois qu'il trouve une boucle (il renvoie 1 pour l'enregistrement qui donnerait la racine de la branche en cours à l'itération suivante).

Notez que cette requête vous donnera tous les utilisateurs dans les boucles sans les regrouper.

Pour regrouper les utilisateurs, question cette requête:

SELECT n.*, CONNECT_BY_ROOT(have), level 
FROM v_needs n 
START WITH 
     have IN 
     (
     SELECT MIN(have) 
     FROM (
       SELECT have, CONNECT_BY_ROOT(have) AS root 
       FROM t_needs 
       START WITH 
         have IN 
         (
         SELECT have 
         FROM t_needs n 
         WHERE CONNECT_BY_ISCYCLE = 1 
         CONNECT BY NOCYCLE 
           needs = PRIOR have 
         ) 
       CONNECT BY NOCYCLE 
         have = PRIOR needs 
       ) 
     GROUP BY 
       root 
     ) 
CONNECT BY NOCYCLE 
     have = PRIOR needs 

Mise à jour:

De votre poste, je peux voir que vous avez une limitation de la durée maximale de la boucle.

Cela rend ce problème beaucoup plus facile à résoudre.

il suffit d'ajouter la condition de limitation de la boucle dans chacune des requêtes:

SELECT n.*, CONNECT_BY_ROOT(have), level 
FROM v_needs n 
START WITH 
     have IN 
     (
     SELECT MIN(have) 
     FROM (
       SELECT have, CONNECT_BY_ROOT(have) AS root 
       FROM t_needs 
       START WITH 
         have IN 
         (
         SELECT have 
         FROM t_needs n 
         WHERE CONNECT_BY_ISCYCLE = 1 
         CONNECT BY NOCYCLE 
           needs = PRIOR have 
           AND level <= 5 
         ) 
       CONNECT BY NOCYCLE 
         have = PRIOR needs 
         AND level <= 5 
       ) 
     GROUP BY 
       root 
     ) 
CONNECT BY NOCYCLE 
     have = PRIOR needs 
     AND level <= 5 

Cela arrêtera parcourir l'arborescence au niveau 5th.

Si vous avez 1,000,000 utilisateurs dans votre base de données et par utilisateur 5 matchs en moyenne, la requête devra examiner 1,000,000 * 5^5 = 3,125,000,000 les lignes, ce qui est un nombre observable de lignes.

La requête sera grandement améliorée si vous MATERIALIZE votre vue et créer des index sur «besoin» et «avoir».

Dans ce cas, la requête sera terminée en quelques minutes.

Answer 2

C'est un bon début pour moi. Je me suis cogné la tête contre le mur pendant des jours. Permettez-moi de donner quelques détails supplémentaires pour le rendre plus clair. Malheureusement, le problème est un problème de clique, et NP-complet parce que les trois colonnes ne sont pas uniques.

Voici l'application du monde réel: Je fais un projet de recherche sur l'efficacité de la réciprocité négative, c'est-à-dire le troc, au lieu d'un échange monétaire où il est inapproprié ou illégal.

L'exemple spécifique est la transplantation d'organes. Disons que Bob a besoin d'un rein, et que sa femme est prête à donner un rein, il n'y a aucune garantie qu'elle soit une allumette. Cependant, elle peut correspondre à un autre utilisateur de la base de données qui, en retour, peut fournir à Bob un rein correspondant. Si j'ai une base de données avec des milliers de destinataires, et des dizaines de milliers de donateurs potentiels, je peux potentiellement négocier une transaction multi-voies pour maximiser les avantages pour autant de destinataires que possible.

Il est évident que le nombre maximal de niveaux requis pour fermer la boucle doit être limité. Une transaction à cinq est possible, mais une transaction à 100 voies n'est tout simplement pas réalisable d'un point de vue logistique.

Je n'avais jamais entendu parler d'Oracle Spatial jusqu'à aujourd'hui. Il semble que ce soit exactement le produit dont j'ai besoin pour rendre cela plus facile.