Beziehungen zwischen Benutzern ermitteln

[ArSeN]

Hallo!

Sicherlich bin ich nicht der erste mit diesem Problem, leider finde ich bei Google aber gar nichts zu dem Thema und in der Forensuche habe ich nur diesen Thread gefunden.

Derjenige der dort eine Lösung für das Problem gefunden hat war leide rnicht willens sie zu posten. Ich habe auch selbst bereits zwei Lösungen für mein Anliegen gefunden. Die Probleme dabei sind aber, dass die Rekursive Lösung vieeeeel zu lange braucht weil Sie sich hunderte oder gar tausende male selbst aufruft, was meinen RAM natürlich ganzschön belastet. Dann habe ich noch eine Iterative Lösung mit ganz viele Schleifen gefunden, aber die Arrays werden dabei auch so groß, dass das ganze Performancemäßig nicht akzeptabel ist.

Zunächst muss ich noch sagen: Es handelt sich hierbei um Freundschaften zwischen den einzelnen Benutzern. Das heißt, ich habe zwei Attribute in meinem Entitätstyp, und jeder Benutzer kann X-Beliebig viele Freunde haben.

Problematischerweise haben tatsächlich ein Großteil der Benutzer so 20-40 Freunde, was das ganze nicht gerade vereinfacht.

Mein endgültiges Ziel ist es, 3 Beziehungen über maximal 6 "Ebenen" (also über 4 User zwischen dem Start- und dem End-User) zu "berechnen".

Meine Frage daher: Gibts vielleicht irgend'ne Möglichkeit das ganze direkt in MySQL realisieren? Oder gibts sonst noch irgendeine Möglichkeit, die mir die Performance akzeptabel machen kann?

Ich wäre für jede Hilfe dankbar und bedanke mich schonmal im Voraus. Danke!

[asp2php]

hm ... das ist nur eine m:n Beziehung, die man mit 3 Tabellen - bzw. hier 2 - leicht aufbauen kann, wasfür Probleme hast du?

[ArSeN]

Mit der m:n-Beziehung an sich habe ich kein Problem.

Es gibt 2 Tabellen, die benutzertabelle, und die freundetabelle.

In der freundetabelle steht jetzt sowas wie:

benutzer_id          freund_id
433                       467
433                       448
433                       458
433                       400
487                       876
467                       1387
1387                     5387

Wenn ich jetzt wissen will, welche Beziehung der benutzer 433 zum Benutzer 5387 haben will, soll dabei herauskommen: 433 -> 467 -> 1387 -> 5387.

Dazu brauche ich sowohl bei der rekursiven als auch bei der iterativen Variante relativ viele Abfragen. Undzwar deswegen, weil ich, wenn ich vom Benutzer 433 ausgehe ja zunächst grundsätzlich alle Freunde auswählen muss, weil ich ja nicht weiß, welcher im Endeffekt auch wirklich zum Gewünschten Benutzer führt. Ich müsste also obwohl hier nur der Freund 467 zutreffen würde, auch die Freunde 448, 458 und 400 auswählen, und deren Freunde auch wieder, und und und....

Das ganze frisst performance ohne ende. Daher suche ich nach einer anderen Variante.

[closure]

Hi,

dein problem lässt sich als graph interpretieren. Wenn du
alle freunde von einem bestimmten knoten haben willst, dann musst
du die transitive hülle der freundschaftrelation bestimmen.
Wenn du mal nach graphen-algorithmen und transitive closure suchst
dann findest du schon mal die theorie dahinter.
Unglücklicherweise eignen sich relationale datenbanken nicht
sonderlich zum abbilden von graphen. Ein möglichkeit is sicher
eine adjazenzmatrix oder in deinem fall sicher interessanter in
form einer kantenliste. Aber hier tritt ja bereits das problem auf,
eine abfrage über alle beziehungen funktioniert nur über rekursive
queries.

Eine möglichkeit wäre es auf die graphendarstellung zu verzichten
weil du ausser dem finden der transitiven hülle, keine anderen
graphen-algorithmen brauchst.
Du könntest dann beim einfügen der daten bereits die bekanntschafts
beziehungen ermitteln und in der datenbank so speichern dass eine
abfrage schnell geht.
Dadurch dauert zwar das speichern/löschen länger aber die
abfrage geht schnell. Du musst entscheiden was öfter vorkommt.
Inbesondere durch deine einschränkung der beziehungstiefe
könnte das ein gangbarer weg sein.

greets

[ArSeN]

Hi!

Also unter deinen Stichworten habe ich das hier gefunden. Allerdings würde ich lügen wenn ich behaupten würde ich würde den Großen teil davon verstehen, geschweige denn hätte jetzt ne Idee wie ich das umsetzen kann.

hast du vielleicht noch n besseren Link für mich oder ne konkretere Idee wie ich da sjez umsetzen könnte?


Edit: Ach nochwas, das mit dem "Beziehungen abspeichern" und dann einfach aus der DB auslesen hab ich mir auch schon gedacht. Allerdings ist das bei fast 30 Tausend Benutzern, bei denen ich ja von jedem alle möglichen Beziehungen zu jedem anderen abspeichern müsste, sehr unrelaistisch knapp eine Million beziehungen abzuspeichern, oder nicht?

[closure]

Hi,

das hier sieht gut aus transitive closures in sql

greets

[ArSeN]

Huhu!

Sorry das ich schonwieder nerve.

Ehm.. ehrlichgesagt finde ich außer dem Abstract auf der Seite kaum Inhalt.

[closure]

Hi,

oben rechts gibt es einen link zu dem dokument in diversen formaten.

greets