Soziale Netzwerke: Kontaktorganisation

[Rafael]

Ich wundere mich schon seit einer Weile, wie Kontakte in Sozialen Netzwerken organisiert werden.
Zum Beispiel bei myspace.com: Glaubt ihr, dass es eine Tabelle gibt, in der alle Kontakt-Paare gespeichert werden?

Wie funktioniert das zum Beispiel im StudiVZ? Dort wird bis in die vierte Ebene angezeigt wer mit wem was zu tun hat. Das wären mit obiger Methode ja zig Abfragen.

Rein interessehalber: Weiß jemand, wie so etwas gelöst wird?

[Hamstar]

Rein interessehalber: Weiß jemand, wie so etwas gelöst wird?

Wissen ist nicht so mein Ding, aber ich könnte Dir mitteilen wie ich die Sache möglicherweise implementieren würde.

Wir haben zwei Tabellen "Menschen" und "Menschen_Beziehungen", letztere bildet eine "n:m"-Beziehung zwischen "Menschen" und "Menschen" ab.

In regelmässigen zeitlichen Abständen (stündlich?) haut sich ein Dienst den gesamten Datenbestand rein und erstellt eine Beziehungsdatei (ein "Dokument", XML bspw.), die nur der Darstellung dient (XSLTransformation?).

Andere Lösungen sind selbstverständlich denkbar, aber eine "Real Time"-Lösung halte ich für wenig wahrscheinlich, denn der Analyseaufwand (nicht das Laden, es sind nicht "zig Abfragen") ist m.E. beträchtlich.

Kannst das ja mal austesten.

[Henrico Hamstar]

Wir haben zwei Tabellen "Menschen" und "Menschen_Beziehungen", letztere bildet eine "n:m"-Beziehung zwischen "Menschen" und "Menschen" ab.

Wir brauchen natuerlich noch eine dritte Tabelle "Beziehungstyp".

[Johannes]

Rein interessehalber: Weiß jemand, wie so etwas gelöst wird?

Wie genau weiss ich jetzt nicht, aber sehr wahrscheinlich mit Graphen Algorithmen. Solche Sachen sind Probleme aus der theoretischen Informatik und sehr ähnlich z.B. zum Finden einer Route auf einer Landkarte oder der Verbindung von Leiterbahnen auf einem Mainboard. In die Lösung solcher Probleme haben eine Menge sehr intelligente Leute eine Menge Hirnschmalz reingesteckt. Mit einfachen rekursiven Abfrage geht es sicher nicht, das wäre viiieeeellll zu aufwändig.

Grüsse

Johannes

[Johannes Röckert]

Hi,

also wenn das DBMS Unterabfragen in SQL-Queries zulässt, dann sollte das ganze kein Problem sein.

Angenommen, es gibt die Relation 'beziehung' (Attribute 'von', 'mit'), welche die m:n-Beziehung innerhalb von 'benutzer' (Primärschlüssel 'name') speichert. Für die zweite Ebene z.B. (die Beziehungen der Beziehungen) würde die Abfrage des Benutzers 'dummy' dann lauten:

  
SELECT * FROM benutzer WHERE name IN  
 (SELECT mit FROM beziehung WHERE von IN  
   (SELECT mit FROM beziehung WHERE von='dummy')  
 )  

Wie es sich mit der Performance verhält, kann ich nicht sagen. Aber wenn ich mir StudiVZ so anschaue, scheinen sie es so realisiert zu haben.

Ansonsten:

Würde ich die Laufzeit optimieren wollen, wäre mein Ansatz eine Auslagerung der Beziehungstabelle auf einen externen Rechner (ähnlich wie ein Data Warehouse periodisch zu festgelegten Zeiten). Den "Beziehungsbaum" würde ich aufgrund der Datenmenge nicht zwischenspeichern (vorberechnen). Das Auflistungen der Beziehungen bis zu einer beliebigen Ebene könnte man aber mit relativ einfachen Mitteln so optimieren (Stichwort: Hashtabellen), dass die Zeit für die Suche vernachlässigbar klein wäre (natürlich wäre hier C++ die Sprache erster Wahl). Der Webserver würde dann einfach nach den Namen bis zu Beziehungsebene n fragen. Ich glaube nicht, dass das ein ernsthaftes Problem darstellen würde. Natürlich wäre die Laufzeit exponentiell relativ zu n - aber heißt für so kleine n nicht, dass es ernsthafte Probleme gibt. :)

Viele Grüße,
  Johannes Röckert

[Johannes Röckert]

Korrektur:

Ersetze SELECT in der "hypothetischen Abfrage" durch SELECT DISTINCT. So eliminiert man Schleifen im Beziehungsgraph (erst dann kann man von einem "Baum" sprechen ;-)  ).