Effiziente Datenbankstruktur für soziale Netzwerke gesucht

[Dani]

Servus!

Einige kennen sicherlich die Website XING. Im Wesentlichen plegt man dort Geschäftskontakte. Ein nettes Feature ist, dass man sich zu jedem User anzeigen lassen kann, über welche Ecken man mit dem User in Verbindung steht. Man kann sowohl die kürzeste Verbindung als auch alle Verbindungen der Länge N <= 5 anzeigen lassen.
Beispiel:
dies ist nicht XING, sondern so soll das Ganze eines Tages mal aussehen
... S c h n i p p ...

Dieses Feature soll ich nun in einer ähnlichen Website realisieren. Die Frage ist, wie eine effiziente Implementierung aussehen könnte. Auf der Datenbankseite hab ich bisher nur die 'naive' Struktur:
http://img143.imageshack.us/img143/7149/dbschemabp5.png
Damit bliebe wohl nur eine Breitensuche, wenn wirklich alle Verbindungen gefunden werden müssen. Etwas subpotimal
Falls jemand schonmal etwas in die Richtung gemacht hat, wäre ich für Tipps unendlich dankbar

[edit=Sharky]Bild auf wunsch des Autors entfernt. Mfg, Sharky[/edit]

[SirTwist]

Hm... nur ein paar verworrene Gedanken meinerseits:

Wenn Du 1000 Benutzer hast, dann könnte man über eine Matrix (1000 x 1000) angeben, über wieviele Ecken zwei Leute sich kennen (minimal). Dabei könntest Du eine Grenze max_ecken einführen, die dafür sorgt, dass nicht alle Felder besetzt werden (nämlich jeweils die Felder von je Personen, die sich über mehr als max_ecken kennen, bleiben leer).

Wenn nun max_user größer wird und max_ecken klein bleibt, wird deine Matrix sehr spärlich besetzt und es kann sinnvoll sein, sie über eine Tabelle (user1, user2, anz_ecken) zu ersetzen. Außerdem ist die Matrix natürlich diagonalsymetrisch (da gabs auch mal einen Fachausdruck für), so dass Du (user2, user1, anz_ecken) gar nicht erst zu setzen brauchst.

Natürlich müsste die Tabelle immer aktualisiert werden, wenn user1 oder user2 an seinen oder ihren Kontakten rumfummelt. Das dürfte aber deutlich seltener auftreten als die Anzeige der möglichen Verbindungen.

Nun weißt Du aber nur, welche Beziehungen es sich lohnt anzugucken. Man könnte aber die Tabelle erweitern (user1, user2, anz_ecken, pfad). Wobei pfad eine Liste der UserIDs ist, über die die Beziehung aufgebaut ist. Ich speichere sowas gerne als Text-Feld ab und mache mir dann die MySQL-spezifische(?) Funktion FIND_IN_SET zu Nutze. Mit "FIND_IN_SET(user.id, relation.pfad)" kann ich alle User-Einträge auswählen, deren IDs in der Liste vorkommen.

Keinen blassen Schimmer, ob Dir das weiterhilft. ist jedenfalls reine Theorie und basiert auf keinerlei Erfahrung mit großen Userzahlen Viel Spaß!

Sir Twist

[jfheins]

Übrigens: falls du es doch so machen musst, ,wie eingangs vorgeschlagen, könnte es effizienter sein, nicht von einem ausgehend bis zu einer tiefe von 6 zu suchen, sondern vielmehr von beiden ausgehend bbis zu einer tiefe von 3. Da sich mit jedem Schritt in die Tiefe die Breite exponentiell erhöht, könnte man damit wesentlichen Aufwand sparen

Außerdem kannst du - bei der Suche nach einer Verbindung - in deer Breite die Suche bei den KOntakten beginnen, die ihrerseits die meisten Kontakte haben

[alzaimar]

Wenn Du deine 'user_has_contact' 1x mit sich selbst verjoinst, dann hast Du schon alle Verbindungen der Länge 1 (Ich->Kumpel->Du)
Du musst also nur die Tabelle 5x mit sich selbst verknüpfen und dann hast Du alles, was Du brauchst.

Das dürfte sogar einigermaßen fix gehen, weil Du das ja nur für eine Person machst.

[Dani]

Vielen Dank schonmal für die Anregungen!
Ich habe in der Zwischenzeit versucht, Alzairmars Ansatz als Query umzusetzen. Das kam dabei heraus:

SQL-Query für Verbindungen der Länge 5 (Maximum)

SQL-Code:

SELECT DISTINCT
   -- Benötigt wird in diesem Beispiel der Name und die ID des Benutzers
   c1.user_iduser AS u1_id, u1.name AS u1_name,
   c2.user_iduser AS u2_id, u2.name AS u2_name, 
   c3.user_iduser AS u3_id, u3.name AS u3_name,
   c4.user_iduser AS u4_id, u4.name AS u4_name,
   c5.user_iduser AS u5_id, u5.name AS u5_name
FROM
   -- u1 ist der erste Benutzer im Kontakte-Pfad (Start), u5 der letzte (Ziel)
   `user_has_contact` AS c1, 
   `user_has_contact` AS c2,
   `user_has_contact` AS c3,
   `user_has_contact` AS c4,
   `user_has_contact` AS c5,
   `user` AS u1,
   `user` AS u2,
   `user` AS u3 ,
   `user` AS u4,
   `user` AS u5
WHERE  
    -- Die Namen der Benutzer stehen in der Tabelle 'user'
    (c1.user_iduser=u1.iduser) AND (c2.user_iduser=u2.iduser) AND (c3.user_iduser=u3.iduser) AND
    (c4.user_iduser=u4.iduser) AND (c5.user_iduser=u5.iduser) AND

    -- Der Pfad muss mit dem Start-Benutzer u1 beginnen.
    (c1.user_iduser=%s) AND 

    -- Der Pfad muss über 5 Benutzer (u1..u5) gehen, wobei zwischen u_n und u_n+1 eine
    -- "Ist-Kontakt-Von" Beziehung bestehen muss.
    (c1.contact_iduser=c2.user_iduser) AND 
    (c2.contact_iduser=c3.user_iduser) AND 
    (c3.contact_iduser=c4.user_iduser) AND
    (c4.contact_iduser=c5.user_iduser) AND

    -- Der Pfad muss mit dem Ziel-Benutzer u5 enden.
    (c5.user_iduser=%s) AND

    -- Der Pfad darf keine Zyklen enthalten. Die Zusicherung, dass kein User sich 
    -- selbst als Kontakt haben darf, wurde hier verwendet.
    -- Dadurch wird auch verhindert, dass der Ziel-Benutzer an einer anderen Position 
    -- als dem letzten Pfadelement steht.
    (c1.user_iduser!=c3.user_iduser) AND (c1.user_iduser!=c4.user_iduser) AND
    (c2.user_iduser!=c4.user_iduser) AND (c2.user_iduser!=c5.user_iduser) AND
    (c3.user_iduser!=c5.user_iduser)

Da ich ein Datenbanken/SQL-Neuling bin, gibt es hier bestimmt noch einiges an Optimierungspotential
Falls jemandem etwas auffällt, nur raus damit!

[Dani]

Wäre es evtl. sinnvoll, die Query durch eine View zu vereinfachen oder wäre dann zu erwarten, dass der Speicherverbrauch der Datenbank explodiert?

[alzaimar]

Eher eine Funktion (UDF). Eine View ist nur eine kompilierte Query, sodaß beim Aufruf der Overhead des Übersetztens eingespart wird. Speicher verbraucht eine View (bis auf den Quellcode) nicht.

[Dani]

Ah, okay. Wie man sieht, muss ich noch jede Menge Unwissenheit abbauen

Tausend Dank nochmal