Wie funktionieren openBC-Verbinden?

[prego]

Du braucht einen Graphen mit ungerichteten Kanten - sprich: die Verbindungen müssen doppelt abgelegt werden. Ansonsten musst du wilde if-Konstruktionen in der Query machen um alle Freune von User 1 zu finden. (select freunde-id from tab where user-id = xx - das findet dann ja nur die freundschaften die xx initiert hat)

Desweiteren solltest du dich von deiner autoincrement-id verabschieden. Überleg mal was einen Datensatz bei dir ein-eindeutig macht... stimmt... user-id - freund-id Kombination. Also sollte dein Primary key diese beiden Spalten umfassen. Erst dann kannst du mit mysql ordentlich mit umgehen. Stichwort "insert on duplicate key update".

Du solltest ein externes Script nehmen was die Beziehungen untereinander berechnet und in einer dritten Spalte das Ergebnis speichern. Dieses Ergebnis kann zb ein serialisierter Array sein, wo du die ID's ablegst die die Verbindung herstellen. Beim Ausfragen suchst du dann einfach nach der Kombination die du wissen willst.

$sql = "select payload from tab where user-id = ".$user_id." and freund-id = ".$freund_id; 

Danach machst du einfach eine Abfrage nach den ID's die die Verbindung herstellen in deiner user db.

$sql = "select name from user where id in(".implode(",", unserialize($payload))."))"; 

Im Falle von user 1 und Freund 2 würde der Array zB so aussehen

array(1,5,23,2) 

Wir haben hier mittlerweile eine mysql-Tabelle mit 49Millionen Freundschaftsrelationen (ungerichtet - also 1 kennt 2 und 2 kennt 1; also 49Mil Rows in der Tabelle) und wir machen darin Abfragen in unter 200ms.

Das Script was wir einsetzen nutzt den oben im Thread beschriebenen Dijkstra Algo um direkte Verbindungen raus zu finden - vorher wir allerdings versucht das ganze mit Floyd-Wharshall zu lösen um "alle" Verbindungen zwischen Bekannten rauszufinden. Erst wenn der Teilgraph dafür zu groß ist, wird Dijkstra benutzt.

//edit:
Oh, die Lösung hier sieht wirklich interessant aus http://www.artfulsoftware.com/mysqlb...qled1ch20.html - wenns mal wieder nicht so spät ist, schau ich mirs ma an

[Friedward74]

Langsam werd ich schlauer...

...das macht bei mir natürlich erstmal ne Umstrukturierung der DB und diverser Skripte notwendig, denn wie Du schon richtig festgestellt hast, arbeite ich hier bisher mit wilden if-clauses, die allerdings bis auf eine etwas schlechtere Performance aber akzeptable funktionieren. Ist ein ungerichteter Graph denn zwingende Voraussetzung für Dikstra?

Das externe Skript wurde hier ja schon mehrfach erwähnt. Allerdings noch eine Frage als relativer Newbie: Wann läuft dieses Skript denn und was wird da jeweils abgefragt und aktualisiert? Denn wenn eine neue Beziehung hinzukommt kann sich ja bei zig anderen auch die "payload" ändern, oder? Und dann nochmal meine leider immer noch nicht beantwortete Frage, wie initialisiere ich denn das Array für das Skript? Muß die gesamte DB in das Skript-Array zur Analyse eingelesen werden bzw. werden in Deinem Fall bei jeder Auswertung 49 Mio. Datensätze in das Array eingelesen und analysiert?
Gibt dieses Array

array(1,5,23,2) 

denn jetzt die Mitglieder der jeweils kürzesten Relation wieder (1-5-23-2)) oder die beiden kürzesten Relationen 1-5-2 und 1-23-2? Denn was passiert wenn es mehrere gleich lange Relationen gibt? Wird dann ne Zufallsauwahl getroffen und hat man die Möglichkeit sich zumindest die anderen gleich langen Pfade anzusehen? Wie habt Ihr denn das gelöst? Irgendwie sind da bei mir noch eine Menge Fragen offen

[Slava]

Ich stelle mir für darstellung von solchen bezihungen eine pfad-model vor, die ich schon für darstellung von menu benutzt habe.
bei einfügen den neuen user wird der ganzer pfad abgespeichert.
zbs
tabelle pfad
id| pfad (ein text in dem alle idis durch komma getrennt abgespeichert sind.)
der pfad sieht etwa so aus '0,7,34,56'

jeder user bekommt zusätzlich eine spalte, die id von dem pfad erhält.
scenario:
der neuer User Y wird in tabelle eingefügt, der bekannter von User X ist.
1)User Y einfügen
2)wenn ein pfad , der User X hat + ',id_userX' am ende, dann id von diesem pfad zwischenspeichern und zum (3) springen,
sonnst neuer pfad erstellen, der User X hat + ',id_userX' am ende hat und die Id von diesem pfad merken.
3)User Y bekommt in pfad_id der vorgemerkter wurde.

die Suche wird dan etwa so realisiert.
frage: über wenn kennt user Z den user V
1)die pfade von Z und V auslesen
2)
2.1)Erster zeichen dafür, dass eine Verbindung überhaupt vorhanden ist,
der Pfad von Z muss komplet an erster stelle von dem Pfad V stehen oder umgekehrt.
(zbs Z hat pfad (1,5,7,34) und pfad von V hat ( (1,5,7,34,47,80), also sehen wir, dass die beiden user in einem Ast befinden.
2.2) wenn 2.1 stimmt, dann schneiden wir die gemeinsam teil von beiden pfade und speichern es.
zbs in beispiel Oben, bekommen wir (47,80) also substr(pfadV,strlen(pfadZ)).
3) jetzt machen wir einfacher select, der alle User mit den ids die zwischen gespeichert sind abruft, und zwar sortiert nach id.
select username form user where id in(47,80)

für eine sehr grosse tabellenstruktur ist diese model nicht besonders gut geeignet, aber für eine tabellenstruktur, die etwa 300,400 Tiffe von dem wurzel hat, ist es eigentlich gut geeignet.

[Seikilos]

Hey,
ich grabe mal diesen Thread aus.
Was ist damals daraus geworden?

Dieses jeder kennt jeden über 6 Ecken funktioniert doch nur, wenn es so genannte Super-Spreader gibt, die wesendlich mehr Leute, als andere kennen.

Wenn jeder nur 6 Freunde hat,
dann sind das 6^6 = 46656 Beziehungen, die zudurchsuchen sind.

Wenn man im Durschnitt mal größere Seiten anguckt, bei denen die Leute >10 bis 100 Leute kennen, dann kann man im Schnitt von
20^6 = 64.000.000 Beziehungen ausgehen.

So etwas würde mit einer Datenbank und PHP nicht schön werden, nicht wahr? Mal 64 Mill Elemente in PHP zur Laufzeit geladen

Ergo läuft es auf Stored Procedures aus, die auf der Tabelle laufen, aber dennoch, ob ungerichtet (hauptsache Weg), oder gerichtet (hauptsache Kurz), die Komplexität dieses Aufwands bei einer Begrenzung von 6 Knoten ist dennoch so hoch, dass man es eigentlich kaum in einer sinnvollen Zeit berechnen kann, oder irre ich mich da?

Da stellt sich mir die Frage, wie läuft das bei facebook/studivz dann ab? permanentes Cachen aller Kombinationen halte ich für Unwahrscheinlich, aber was dann? Einmalige Suche, die gecached wird?

[admin]

schön, habe diesen Tread vollkommen übersehen.

Ich erarbeite gerade selbst an einer solchen Lösung und freue mich doch SEHR über die hier angegebenen Links....

cu
benri

[aimbot]

Original geschrieben von Seikilos
Da stellt sich mir die Frage, wie läuft das bei facebook/studivz dann ab? permanentes Cachen aller Kombinationen halte ich für Unwahrscheinlich, aber was dann? Einmalige Suche, die gecached wird?

stichwort: c++ daemon