"Wer kennt wen über wen" - Wie umsetzen? (mysql)

Hallo,

ich habe auf einer meiner Seiten vor eine "Wer kennt wen über wen" leiste zu
machen (wie auf www.openbc.com).

Tabellenstruktur:

friend | uid
0 1
1 2
2 3

Sollte der User mit der uid=1 nun das Profil des Users mit der uid 3
ansurfen, soll nun ausgegeben über wen der User (uid=1) den anderen User
(uid=3) kennt, in dem fall:

1 -> 2 -> 3

Natürlich hat diese Tabelle mehr als nur diese 3 Einträge, mehrere tausend.
Wie Setze ich das am besten um? Ich hab da absolut ne Denkblockade wie ich
die kürzeste Verbindung zwischen den 2 Usern herausfinden kann - und das
ziemlich schnell, ohne den mysqld in die Knie zu zwingen.


Ich hoffe auf viele Lösungsansätze/Tipps,


Mit freundlichen Grüßen
Martin Winkler

Re: "Wer kennt wen über wen" - Wie umsetzen? (mysql)

Hi!

Martin Winkler wrote:
> ich habe auf einer meiner Seiten vor eine "Wer kennt wen über wen" leiste zu
> machen (wie auf www.openbc.com).
> Natürlich hat diese Tabelle mehr als nur diese 3 Einträge, mehrere tausend.
> Wie Setze ich das am besten um? Ich hab da absolut ne Denkblockade wie ich
> die kürzeste Verbindung zwischen den 2 Usern herausfinden kann - und das
> ziemlich schnell, ohne den mysqld in die Knie zu zwingen.
>
> Ich hoffe auf viele Lösungsansätze/Tipps,

Das was Du beschreibst ist ja ein ziemlich großes Netz, in dem Du einen
Pfad von einem Knoten zu einem anderen suchst. Ich denke, dass es nur
für sehr zusammen liegende Knoten eine akzeptabel schnelle Lösung gibt.

Lies doch bitte mal hier nach:
http://www.iicm.edu/greif/node6.html
ob da etwas für Dich dabei ist.

Eines wird es höchstwahrscheinlich aber nicht geben: Ein schnelles SQL
Statement, das Dir den Pfad ausgibt. Um die Implementierung eines
Algorithmus wirst Du nicht herum kommen.

Gruß
Bernhard

Re: "Wer kennt wen über wen" - Wie umsetzen? (mysql)

Martin Winkler schrieb:

> ich habe auf einer meiner Seiten vor eine "Wer kennt wen über wen" leiste zu
> machen (wie auf www.openbc.com).
>
> Tabellenstruktur:
>
> friend | uid
> 0 1
> 1 2
> 2 3

Da hast Du ja die Bekannten erster ordnung schon da:

select me.uid, me.friend from tab me where me.uid = 0 and me.friend =3

Mit einem Self-join hast Du die Bekannten zweiter Ordnung:

select me.uid, me.friend, friend.friend from tab me left join tab friend
on me.friend = friend.uid where me.uid = 0 and friend.friend = 3

Und mit einem doppelten Self-join dann schon die Bekannten dritter
Ordnung. Muttu nurnoch Script machen, dass Dir die levels nacheinander
abklappert. Ausserdem würde ich mal austesten wie weit man das treiben
kann....

> Wie Setze ich das am besten um? Ich hab da absolut ne Denkblockade wie ich
> die kürzeste Verbindung zwischen den 2 Usern herausfinden kann - und das
> ziemlich schnell, ohne den mysqld in die Knie zu zwingen.

Ich denke mit - wie Du sagst - "paar"-tausend DS mit jeweils nur 2
integern wird das kein Problem sein. Bei "einigen"-tausend würde ich das
einfach mal austesten.

Grüße, Matthias

Re: "Wer kennt wen über wen" - Wie umsetzen? (mysql)

Hi Martin

Martin Winkler wrote:
> ich habe auf einer meiner Seiten vor eine "Wer kennt wen über wen" leiste zu
> machen (wie auf www.openbc.com).

Etwas Numerik: Hättest du eine Matrix B von #Leute x #Anzahl Leute und
da drin überall da ne eins, wo eine Beziehung besteht, kriegtest du mit
B^n die Beziehungsebene der n. Ordnung. Bei B^0>0 kennt jeder nur sich
selbst. Bei B^1>0 kennt jeder seine ersten Bekannten. B^2>0 zeigt an,
wen man denn über eine weitere Person kennt. Usw.

Ob das für dich praktikabel ist, sei mal dahingestellt. Aber ich find's
ne ganze nette Sache.

HTH, Johannes

Re: "Wer kennt wen über wen" - Wie umsetzen? (mysql)

"Martin Winkler" schrieb im Newsbeitrag
news:e4v38s$n1h$02$1@news.t-online.com...
> Hallo,
>
> ich habe auf einer meiner Seiten vor eine "Wer kennt wen über wen" leiste
> zu machen (wie auf www.openbc.com).
>
> Tabellenstruktur:
>
> friend | uid
> 0 1
> 1 2
> 2 3
>
> Sollte der User mit der uid=1 nun das Profil des Users mit der uid 3
> ansurfen, soll nun ausgegeben über wen der User (uid=1) den anderen User
> (uid=3) kennt, in dem fall:
>
> 1 -> 2 -> 3

Exakt für dieses Problem gibt es für Postgres in der contrib/tablefunc die
connectby-Funktionen, die aus solch einer Parent-Child-Struktur die
entsprechende Verknüpfungs-Kette z.B. 1->2->3 ausgibt. Hilft dir vielleicht
voerst nicht weiter, aber du könntest dir ja mal anschauen wie die
connectby-Funktionen implementiert sind und diese einfach umschreiben.

Gruß
M.K.