complexité / MySQL analyse des performances du temps

Question

Configurer (MySQL):

create table inRelation(
    party1 integer unsigned NOT NULL,
    party2 integer unsigned NOT NULL,
    unique (party1,party2)
);

insert into inRelation(party1,party2) values(1,2),(1,3),(2,3),(1,4),(2,5),(3,5),(1,6),(1,7),(2,7),(5,7);

mysql> select * from inRelation a
    -> join inRelation b on a.party2=b.party1
    -> join inRelation c on b.party2=c.party1
    -> where a.party1=1 and c.party2=7;
+--------+--------+--------+--------+--------+--------+
| party1 | party2 | party1 | party2 | party1 | party2 |
+--------+--------+--------+--------+--------+--------+
|      1 |      2 |      2 |      5 |      5 |      7 |
|      1 |      3 |      3 |      5 |      5 |      7 |
+--------+--------+--------+--------+--------+--------+
2 rows in set (0.00 sec)

mysql> explain select * from inRelation a
    -> join inRelation b on a.party2=b.party1
    -> join inRelation c on b.party2=c.party1
    -> where a.party1=1 and c.party2=7;
+----+-------------+-------+--------+---------------+--------+---------+---------------------+------+-------------+
| id | select_type | table | type   | possible_keys | key    | key_len | ref                 | rows | Extra       |
+----+-------------+-------+--------+---------------+--------+---------+---------------------+------+-------------+
|  1 | SIMPLE      | b     | index  | party1        | party1 | 8       | NULL                |   10 | Using index |
|  1 | SIMPLE      | a     | eq_ref | party1        | party1 | 8       | const,news.b.party1 |    1 | Using index |
|  1 | SIMPLE      | c     | eq_ref | party1        | party1 | 8       | news.b.party2,const |    1 | Using index |
+----+-------------+-------+--------+---------------+--------+---------+---------------------+------+-------------+

Ceci est une solution BFS pour mon post précédent:

Défi, comment mettre en œuvre un algorithme pour six degrés de séparation?

Mais quelle est la complexité de celui-ci? Supposons qu'il y ait des documents totalement n.

Answer 1

En supposant qu'il y a N sommets et des arêtes E. Pour chaque table il peut y avoir une jointure entre chaque paire de sommets et ont besoin de vérifier tous les sommets pour l'égalité. Donc, pire performance de cas sera O (| V | + | E |)

Mise à jour: Si vous envisagez de Mysql, il y a beaucoup de choses qui affectent la complexité, si vous avez index de clé primaire sur le champ, l'indice b-arbre sera utilisé. Si son indice unclustered normale, l'indice de hachage sera utilisé. Il y a des coûts différents pour chacune de ces structures de données.

De votre autre question, je vois cela est vos besoins 1. Calculer le chemin de UserX à Usery 2. Pour UserX, calculer tous les utilisateurs qui est pas plus de 3 pas.

Pour la première, la meilleure chose est d'appliquer Djikstra algorithme et construire une table en java, puis le mettre à jour dans le tableau. Notez que, en ajoutant chaque nouveau nœud, a besoin d'un traitement complet.

Autre solution à cela d'utiliser SQL récursif introduit dans la norme SQL 1999 pour créer une vue contenant le chemin de UserX à Usery. Faites-moi savoir si vous avez besoin des références pour les requêtes récursives.

Pour la seconde, la requête que vous avez écrit fonctionne parfaitement.