Beziehungen zwischen Benutzern ermitteln

Einklappen
X
 
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • Beziehungen zwischen Benutzern ermitteln

    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!
    Nur wenige wissen, wieviel man wissen muss, um zu wissen, wie wenig man weiß.

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

    Kommentar


    • #3
      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:

      Code:
      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.
      Nur wenige wissen, wieviel man wissen muss, um zu wissen, wie wenig man weiß.

      Kommentar


      • #4
        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
        (((call/cc call/cc) (lambda (x) x)) "Scheme just rocks! and Ruby is magic!")

        Kommentar


        • #5
          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?
          Zuletzt geändert von ArSeN; 03.05.2007, 10:59.
          Nur wenige wissen, wieviel man wissen muss, um zu wissen, wie wenig man weiß.

          Kommentar


          • #6
            Hi,

            das hier sieht gut aus transitive closures in sql

            greets
            (((call/cc call/cc) (lambda (x) x)) "Scheme just rocks! and Ruby is magic!")

            Kommentar


            • #7
              Huhu!

              Sorry das ich schonwieder nerve.

              Ehm.. ehrlichgesagt finde ich außer dem Abstract auf der Seite kaum Inhalt.
              Nur wenige wissen, wieviel man wissen muss, um zu wissen, wie wenig man weiß.

              Kommentar


              • #8
                Hi,

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

                greets
                (((call/cc call/cc) (lambda (x) x)) "Scheme just rocks! and Ruby is magic!")

                Kommentar

                Lädt...
                X