Doppelte Einträge bei Rekursion

Hi!
Ich habe ein Problem bei einer rekursiven Abfrage. Und zwar geht es um ein Freundenetzwerk und ich möchte einen Weg finden, wie man von einem Anfangsfreund zu einem Endfreund kommt (also Freund 1 ist befreundet mit Freund 2 und Freund 2 ist befreundet mit Freund 3).
Bis jetzt probiere ich es so:

WITH RECURSIVE tempfreunde(freundvon, pfad, tiefe) AS (
    SELECT f.freundvon, '1', 1
    FROM istbefreundetmit f
    WHERE befreundetmit = 1 AND freundschaftsgrad > 1
UNION
    SELECT DISTINCT ON (f.freundvon) f.freundvon, pfad || ', ' || f.freundvon, tf.tiefe + 1
    FROM istbefreundetmit f, tempfreunde tf
    WHERE f.befreundetmit = tf.freundvon AND f.freundschaftsgrad >= 1 AND f.freundvon <> 1 AND tiefe < 6
    )
SELECT *
FROM tempfreunde;

Leider funktioniert das aber nicht, weil die Abfrage kein Ende findet (habe die Tiefe nur eingebaut, damit PostgreSQL nicht jedes mal bei einem neuen Test abstürzt). Wenn ich den Pfad nicht einbaue klappt es ja wunderbar, aber mit Pfad bekomme ich es irgendwie nicht hin, dass er keine Freunde doppelt einfügt.
Hoffentlich kann mir jemand helfen und sagen wo mein Fehler liegt.

Danke schonmal! :slight_smile:

Was ist jetzt das Problem, daß es rekursiv nicht ended und Du die Tiefe begrenzen mußt (was IMHO keine soo schlechte Idee ist…) oder daß Einträge doppelt kommen?

Letzteres kannst Du sicherlich vermeiden, wenn Du das DISTINCT noch mal außen drum herum anlegst.

Vielleicht kannst Du ja mal guttenbergfreundlich ein CREATE TABLE und ein paar INSERT-Befehle für Testdaten bringen? Oder vielleicht als angepappte Datei?


Andreas

Beides. Nicht DIREKT doppelt, aber schon irgendwie.
Beispiel:
Ich suche den Pfad von 1 zu 6. Richtig wäre: 1, 5, 6
Dieser wird auch angezeigt, allerdings zeigt er auch an:
1, 5, 6, 5, 6
Hier werden also Freunde doppelt benutzt.

Wo genau meinst du? Bei dem abschließenden SELECT * am Ende?

Testdaten kann ich später noch nachliefern, wenn meine Erklärung hier nocht nicht ausgereicht hat :wink:

Testdaten sind aber für akretschmer der Weg, dir dein Problem anhand eines Beispiels zu erklären :wink:

Hmm, David Fetter seine Webseite ist down, da sind ein paar nette Beispiele.
So lange kannst du dir seinen Vortrag hier mal anschauen:

Trees and More With PostgreSQL MSCOSCONF09 #MOSC2010

Werd morgen mal Testdaten hochladen. Weiß aber nicht warum er mir mein Problem erklären soll, ich kenne doch mein Problem. Mein Problem ist, dass ich in meiner Abfrage PostgreSQL nicht sage, dass Freunde nicht mehrmals eingefügt werden sollen. Dachte durch UNION und DISTINCT hätte ich das gemacht, aber anscheinend stimmt da irgendwas nicht, weil er immernoch meint es wäre nicht dasselbe (weil der Pfad eben anders ist).

Habe ich mir angeschaut. Was mir fehlt ist halt Tree Query Termination. In meinem Fall wäre das WHERE f.freundvon NOT IN (tf.freundvon). Funktioniert aber nicht, habe immernoch haufenweise Freunde doppelt drin.
Naja wie gesagt, haue morgen mal Testdaten hier rein.

Danke schonmal an euch beide!

Soooo, wie bereits gestern angekündigt hier die Testdaten:
Download: Tabelle+Daten.zip | xup.in

Ich hoffe jetzt kann einer von euch beiden mir meinen Fehler zeigen :slight_smile:

Danke!

Gegen die unendliche Rekursion in die Tiefe hab ich grad auch keine Idee, aber ich hoffe mal, dies bringt Dich schon mal weiter:

test=*# select distinct on (freundvon) freundvon, tiefe from (with recursive tempfreunde(freundvon, pfad, tiefe) AS ( SELECT f.freundvon, '1', 1 FROM istbefreundetmit f WHERE befreundetmit = 1 AND freundschaftsgrad > 1 union all select f.freundvon, pfad || ', ' || f.freundvon, tf.tiefe + 1 FROM istbefreundetmit f, tempfreunde tf WHERE f.befreundetmit = tf.freundvon AND f.freundschaftsgrad >= 1 AND f.freundvon <> 1 AND tiefe < 6 ) select * from tempfreunde) foo order by 1,2;
 freundvon | tiefe
-----------+-------
         2 |     1
         3 |     1
         4 |     2
         5 |     2
         6 |     3
(5 rows)

Das mit dem Pfad stimmt glaube nicht so wirklich, ist mir aber egal.


Andreas

Danke für die Mühe. Das Problem hatte ich schon vorher gelöst, bisschen anders mit nem ORDER BY.
Theoretisch würde mir das auch reichen, ALLERDINGS ist das eine Aufgabe für die Uni und nicht für eine praktische Anwendung (wo ich es auch logisch fände eine maximale Tiefe einzusetzen, das würde ja sonst hammermäßig auf die Performance gehen). Deswegen muss ichs leider ohne Tiefe machen sondern mit der Abbruchbedingung “alle Freunde wurden hinzugefügt”.
Vielleicht kann mir ads oder jemand anders nochmal weiterhelfen :wink:

Ach, da bin ich ja froh, da nicht weiter dran geknobelt zu haben, denn Du sollst die Aufgabe ja lösen :wink:

Aber: wäre schön, wenn Du das Ergebniss hier zeigen würdest, wenn Du eines hast!


Andreas