Ich habe folgendes Problem:
In meiner Community kann man freunde zu seinem Profil hinzufügen.
diese werden in einer mysql Tabelle gespeichert. 3 Spalten (antragsteller|emfpfänger|status)

nun möchte ich dem user anzeigen, über wieviele 'ecken' er den user kennt, den er gerade anschaut.

kann mir da jemand helfen?

Gibt es eine SQL Abfrage die das automatisch anzeigt, oder muss man das über Schleifen regeln?

gruß AT

Nun, im Grunde ist das ein Algorithmus, welcher einfach nach einen gemeinsamen Nenner sucht. Ich würde die Tiefe dabei unbedingt begrenzen(!), weil man einfach jeden Kontakt durchgehen muss und mehrere (SQL-)Abfragen stellt. Hier mal eine kleine Skizze, wie der Algorithmus aufgebaut sein könnte:

"benutzer" sind die beiden Benutzer, von welchen man gerne den Bekanntheitsweg erfahren möchte, "kontakt-1" stellt die erste Ebene des Durchlaufes auf den beiden Seiten dar, "konktakt-2" den zweiten Durchlauf. So würde es weitergehen, je nach Anzahl der gewünschten Ebenen [1], ich habe aber in der Skizze mal nach dem zweiten Durchlauf einen Treffer eingebaut.

Bedacht werden sollte, dass kein Benutzer doppelt aufgerufen wird, damit der Algorithmus nicht zu viel Rechenleistung benötigt (also im Prinzip weniger durchläufe machen muss), auch stellt die Skizze nur ein Funktionsprinzip dar, es kann halt auch durchaus sein, dass vom oberen Benutzer in zweiten Druchlauf ein Kontakt der zweiten Ebene auf einen Kontakt der ersten Ebene vom unteren Benutzer zutrifft. Es kann auch sein, dass ein Kontakt der dritten Ebene auf einen Kontakt der ersten Ebene passt.

Das sind nur meine Überlegungen, welche ich so kurzzeitig vor kurzen für ca. 5 min hatte, also kann es durchaus noch bessere Lösungswege geben, nur das wäre der erste Lösungsweg, welcher mir einfällt. Lass Dich nicht von der Skizze täuschen, um den Algorithmus möglichst wenige Durchläufe durchgehen zu lassen, ist ein etwas komplizierter Programmcode von nöten.



Möglichkeit Zwei
Wäre im Prinzip einfach nur von einen Benutzer auszugehen, und die Kontaktebene rekursiv durchzuarbeiten bis man die ID des anderen Benutzer findet, bzw. bis der Vorgang einfach abgebrochen wird. Welcher von beiden Algorithmen der bessere kann ich nicht sicher sagen, ich gehe aber davon aus, dass der Erstere besser ist.



MfG Sascha Ahlers

[1] Die Durchläufe und die Bezeihungsteife sind bei diesen Algorithmus nicht unbedingt gleich, sie können leicht voneinander abweichen!

Nicht mit Schleifen arbeiten. Das dauert nur ewig lange, wenn viele User registriert sind und ist ein Performance-Killer.

Kleiner Tipp: für jede Ebene des "Freundes-Netzwerkes" sollte eine SQL-Anweisung ausreichen. Kennt man erst einmal die Ebene, zu dem ein User gehört, reicht eine weitere SQL-Anweisung aus, um die verschiedenen "Wege" anzuzeigen. Mehr als 5 Ebenen würde ich allerdings auch nicht durchforsten.

Um Bäume abzuarbeiten gibt es verschiedene Ansätze, ich würde mal nach "preorder tree traversal" suchen.

Es gibt da zum Teil unterschiedliche Ansätze, manche speichern z.B. die Ebene des Knotens ab.

Irgendwo sollte ich ein php-Magazin mit unterschiedlichen Methoden dazu haben, allerdings weiß ich nicht mehr wo es abgelegt ist....

vielen dank für die antworten.

root@localhost [druid]> show create table f\G
*************************** 1. row ***************************
Table: f
Create Table: CREATE TABLE `f` (
`l` int(10) unsigned NOT NULL,
`r` int(10) unsigned NOT NULL,
UNIQUE KEY `l` (`l`,`r`),
UNIQUE KEY `r` (`r`,`l`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

root@localhost [druid]> select * from f;
+---+---+
| l | r |
+---+---+
| 1 | 2 |
| 2 | 3 |
| 2 | 4 |
| 2 | 5 |
| 3 | 6 |
| 3 | 7 |
| 3 | 8 |
| 4 | 1 |
| 4 | 3 |
| 4 | 6 |
| 5 | 6 |
| 6 | 2 |
| 6 | 4 |
| 7 | 1 |
| 7 | 2 |
| 7 | 4 |
| 8 | 1 |
+---+---+
17 rows in set (0.02 sec)


Direkte Bekannte:

root@localhost [druid]> select a.l, a.r from f as a where a.l = 1 and a.r =2;
+---+---+
| l | r |
+---+---+
| 1 | 2 |
+---+---+
1 row in set (0.02 sec)

Das ist im EXPLAIN const, also löst der Optimizer die Query auf und der Executor wird noch nicht mal bemüht.

Über einen Bekannten:

root@localhost [druid]> select a.l, a.r, b.r from f as a join f as b on a.r = b.l where a.l = 1 and b.r =3 limit 1;
+---+---+---+
| l | r | r |
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
1 row in set (0.00 sec)

root@localhost [druid]> explain select a.l, a.r, b.r from f as a join f as b on
a.r = b.l where a.l = 1 and b.r =3 limit 1;
+----+-------------+-------+--------+---------------+------+---------+-----------------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+--------+---------------+------+---------+-----------------+------+-------------+
| 1 | SIMPLE | a | ref | l,r | l | 4 | const | 1 | Using index |
| 1 | SIMPLE | b | eq_ref | l,r | l | 8 | druid.a.r,const | 1 | Using index |
+----+-------------+-------+--------+---------------+------+---------+-----------------+------+-------------+
2 rows in set (0.02 sec)

Wie man sieht ist a const, wird also wegoptimiert. b ist eq_ref auf l (key_len 8), also wird der ganze Index (l, r) verwendet. Außerdem ist "using index" - alle benötigten Daten kommen aus dem index, und die Daten werden gar nicht gebraucht.

Das LIMIT 1 sorgt dafür, daß der Executor aufhören kann, sobald eine Lösung gefunden ist - wir wollen ja nicht alle Lösungen.

Mit zwei Hops:

root@localhost [druid]> select a.l, a.r, b.r, c.r
from f as a
join f as b on a.r = b.l
join f as c on b.r = c.l
where a.l = 1 and c.r =8 limit 1;
+---+---+---+---+
| l | r | r | r |
+---+---+---+---+
| 1 | 2 | 3 | 8 |
+---+---+---+---+
1 row in set (0.00 sec)

root@localhost [druid]> explain select a.l, a.r, b.r, c.r from f as a join f as b on a.r = b.l join f as c on b.r = c.l where a.l = 1 and c.r =8 limit 1;
+----+-------------+-------+--------+---------------+------+---------+---------------------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |+----+-------------+-------+--------+---------------+------+---------+---------------------+------+-------------+
| 1 | SIMPLE | a | ref | l,r | l | 4 | const | 1 | Using ndex |
| 1 | SIMPLE | c | ref | l,r | r | 4 | const | 1 | Using index |
| 1 | SIMPLE | b | eq_ref | l,r | l | 8 | druid.a.r,druid.c.l | 1 | Using index |
+----+-------------+-------+--------+---------------+------+---------+---------------------+------+-------------+
3 rows in set (0.00 sec)

a ist const, c ist const, also bleibt für den Executor ein eq_ref (len 8) lookup in b. Superschnell.

root@localhost [druid]> select a.l, a.r, b.r, c.r, d.r
from f as a
join f as b on a.r = b.l
join f as c on b.r = c.l
join f as d on c.r = d.l
where a.l = 1 and d.r =6 limit 1;
+---+---+---+---+---+
| l | r | r | r | r |
+---+---+---+---+---+
| 1 | 2 | 4 | 3 | 6 |
+---+---+---+---+---+
1 row in set (0.00 sec)

root@localhost [druid]> explain select a.l, a.r, b.r, c.r, d.r from f as a join f as b on a.r = b.l join f as c on b.r = c.l join f as d on c.r = d.l where a.l = 1 and d.r =6 limit 1;
+----+-------------+-------+--------+---------------+------+---------+---------------------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+--------+---------------+------+---------+---------------------+------+-------------+
| 1 | SIMPLE | a | ref | l,r | l | 4 | const | 1 | Using index |
| 1 | SIMPLE | b | ref | l,r | l | 4 | druid.a.r | 2 | Using index |
| 1 | SIMPLE | d | ref | l,r | r | 4 | const | 3 | Using index |
| 1 | SIMPLE | c | eq_ref | l,r | l | 8 | druid.b.r,druid.d.l | 1 | Using index |
+----+-------------+-------+--------+---------------+------+---------+---------------------+------+-------------+
4 rows in set (0.00 sec)

Die Datenbank muß anfangen zu arbeiten - und zwar tut sie das von oben (a) und unten (d) gleichzeitig, wie man sehen kann: a und d werden wegoptimiert und mit dem a.r = b.l geht es in b. Zugleich wird ja durch die const-Optimierung d.r zu d.l = c.r und wir können dann mit dem b.r = c.l aus dem Schritt 2 den finalen eq_ref lookup in c machen. Die Badness der Query ist zum ersten Mal größer als 1: Rows sind 1*2*3*1 = 6.

Mit fünf Tables:

root@localhost [druid]> explain select a.l, a.r, b.r, c.r, d.r, e.r from f as a
join f as b on a.r = b.l join f as c on b.r = c.l join f as d on c.r = d.l join
f as e on d.r = e.l where a.l = 1 and e.r =8 limit 1;
+----+-------------+-------+--------+---------------+------+---------+---------------------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+--------+---------------+------+---------+---------------------+------+-------------+
| 1 | SIMPLE | a | ref | l,r | l | 4 | const | 1 | Using index |
| 1 | SIMPLE | e | ref | l,r | r | 4 | const | 1 | Using index |
| 1 | SIMPLE | b | ref | l,r | l | 4 | druid.a.r | 2 | Using index |
| 1 | SIMPLE | c | ref | l,r | l | 4 | druid.b.r | 16 | Using index |
| 1 | SIMPLE | d | eq_ref | l,r | l | 8 | druid.c.r,druid.e.l | 1 | sing index |
+----+-------------+-------+--------+---------------+------+---------+---------------------+------+-------------+
5 rows in set (0.00 sec)

Und 6 Tables:

root@localhost [druid]> select a.l, a.r, b.r, c.r, d.r, e.r, f.r
from f as a
join f as b on a.r = b.l
join f as c on b.r = c.l
join f as d on c.r = d.l
join f as e on d.r = e.l
join f on e.r = f.l
where a.l = 1 and f.r =8 limit 1;
+---+---+---+---+---+---+---+
| l | r | r | r | r | r | r |
+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 6 | 2 | 3 | 8 |
+---+---+---+---+---+---+---+
1 row in set (0.00 sec)

Eine Schleife!

root@localhost [druid]> explain select a.l, a.r, b.r, c.r, d.r, e.r, f.r from f
as a join f as b on a.r = b.l join f as c on b.r = c.l join f as d on c.r = d.l
join f as e on d.r = e.l join f on e.r = f.l where a.l = 1 and f.r =8 limit 1;
+----+-------------+-------+--------+---------------+------+---------+---------------------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+--------+---------------+------+---------+---------------------+------+-------------+
| 1 | SIMPLE | a | ref | l,r | l | 4 | const | 1 | Using index |
| 1 | SIMPLE | f | ref | l,r | r | 4 | const | 1 | Using index |
| 1 | SIMPLE | b | ref | l,r | l | 4 | druid.a.r | 2 | Using index |
| 1 | SIMPLE | c | ref | l,r | l | 4 | druid.b.r | 2 | Using index |
| 1 | SIMPLE | d | ref | l,r | l | 4 | druid.c.r | 2 | Using index |
| 1 | SIMPLE | e | eq_ref | l,r | l | 8 | druid.d.r,druid.f.l | 1 | Using index |
+----+-------------+-------+--------+---------------+------+---------+---------------------+------+-------------+
6 rows in set (0.00 sec)

Wir müssen zur Schleifenfreiheit auch noch verlangen, daß a.l != a.r != b.r != c.r != d.r != e.r != f.r. Das sind mir in Paaren ausgedrückt nun aber zu viele Bedingungen... Viel Spaß beim Tippen.