Fehler in der Rekursion

Hallo liebe pg’ler,

und zwar habe ich ein Problem, welches ich an folgenden Beispieldaten erläutern möchte:


Als Ausgangslage habe ich vereinfacht folgende Tabelle im postgreSQL erstellt:

Person.id	Person.id
1	3
1	101
2	94
3	5
5	3
7	5
10	11
11	13
12	13
94	1
94	3

Weiterhin habe ich mir folgende Query zusammengebastelt, die alle Elternelemente von 1 ausgeben soll, mit der jeweiligen Ebene (bzw. Distanz) und den Pfad dieser Elemente.

with recursive Bekanntenliste (apid, bpid, breadth , path, cycle) as (
  select  apid, bPid, 1, ARRAY[apid], false
  
FROM subset
WHERE aPID=1 OR bPID=1
   union all
   select  c.apid, c.bpid,sg.breadth +1, path || c.apid , c.apid=ANY(path) 
   from subset c, Bekanntenliste sg
  where (c.apid=sg.bpid OR c.bpid=sg.apid) AND NOT cycle )

select DISTINCT *
from Bekanntenliste
where (apid <> 1 OR bpid <>1)
order by breadth

Als Ergebnis erscheint nun:
result.PNG
Um jetzt zur eigentlichen Frage zu kommen:
Allerdings ist das Ergebnis nicht ganz richtig, da z.B.: die 7 erst in der Ebene 4 auftaucht, und schon in der Ebene 3 sein müsste. Weiterhin sind auch Elemente doppelt, u.a. 1 - 3 auf Ebene 1 und dann nochmal 1 - 3 auf Ebene 2. Das macht wenig Sinn, oder jedenfalls möchte ich das so nicht haben. :frowning:

Hat jemand eine Idee?

Viele Grüße,
Kevin

Deine anfangs gezeigte Tabelle hat a) nix mit dem Rest im Posting zu tun und ist b) falsch (2 mal die gleiche Spalte), deine Vermutungen, was wo auftachen müßte ist für keinen außer Dir nachvollziehbar. Tue Dir und uns den Gefallen, eine Frage nachvollziehbar zu stellen. Ein Copy&Paste - fahiger Dump zum Nachbauen ist übrigens ca. Faktor 10.000 mal besser als ein Bild. Ich habe jedenfalls NULL Bock, aus dem Krams reverse die Ausgangslage zu frickeln.

Ich möchte alle ID’s ermitteln die mit der ID 1 im Testdatensatz direkt oder indirekt verbunden sind und das mit dem Pfad und der Entfernung (Ebene/Distanz) der anderen ID’s.



Okay, dann nochmal so wie Du es wünschst:

Hier ist der Dump zum Erzeugen und die Testdaten zum befüllen der Tabelle:

CREATE Table IF NOT EXISTS subset (apid bigint, bpid bigint )



INSERT INTO subset VALUE (1,3);
INSERT INTO subset VALUE (1,101);
INSERT INTO subset VALUE (2,94);
INSERT INTO subset VALUE (3,5);
INSERT INTO subset VALUE (5,3);
INSERT INTO subset VALUE (7,5);
INSERT INTO subset VALUE (10,11);
INSERT INTO subset VALUE (11,13);
INSERT INTO subset VALUE (12,13);
INSERT INTO subset VALUE (94,1);
INSERT INTO subset VALUE (94,3)

Das (hier schematisch vereinfachte und gekürzte) Ergebnis der oben gezeigten Query sollte nun sein:

apid, bpid , ebene
1 , 3 , 1
1, 101 , 1
94 , 1 , 1
3 , 5, 2
...
test=*# with recursive Bekanntenliste (apid, bpid, breadth , path, cycle) as (
  select  apid, bPid, 1, ARRAY[apid], false
 
FROM subset
WHERE aPID=1 OR bPID=1
   union all
   select  c.apid, c.bpid,sg.breadth +1, path || c.apid , c.apid=ANY(path)
   from subset c, Bekanntenliste sg
  where (c.apid=sg.bpid OR c.bpid=sg.apid) AND NOT cycle )
select DISTINCT *
from Bekanntenliste
where (apid <> 1 OR bpid <>1);
 apid | bpid | breadth |      path      | cycle 
------+------+---------+----------------+-------
    5 |    3 |       3 | {1,3,5}        | f
    1 |    3 |       2 | {94,1}         | f
   94 |    1 |       1 | {94}           | f
   94 |    3 |       4 | {94,1,3,94}    | t
   94 |    3 |       4 | {1,94,2,94}    | t
    2 |   94 |       3 | {1,94,2}       | f
    7 |    5 |       4 | {1,3,5,7}      | f
   94 |    1 |       4 | {1,94,2,94}    | t
    5 |    3 |       6 | {94,1,3,5,7,5} | t
    3 |    5 |       5 | {94,1,3,5,3}   | t
   94 |    1 |       2 | {1,94}         | f
    1 |    3 |       3 | {1,94,1}       | t
    1 |  101 |       1 | {1}            | f
    3 |    5 |       2 | {1,3}          | f
    1 |    3 |       3 | {1,3,1}        | t
   94 |    1 |       3 | {94,1,94}      | t
    3 |    5 |       3 | {94,1,3}       | f
   94 |    3 |       5 | {1,3,94,2,94}  | t
    5 |    3 |       5 | {1,3,5,7,5}    | t
    3 |    5 |       4 | {1,3,5,3}      | t
   94 |    1 |       3 | {94,2,94}      | t
    2 |   94 |       2 | {94,2}         | f
    1 |  101 |       3 | {1,94,1}       | t
    1 |    3 |       1 | {1}            | f
    1 |    3 |       4 | {94,1,3,1}     | t
    5 |    3 |       4 | {94,1,3,5}     | f
   94 |    3 |       3 | {94,2,94}      | t
    3 |    5 |       4 | {1,3,94,3}     | t
    1 |  101 |       2 | {94,1}         | f
    2 |   94 |       4 | {1,3,94,2}     | f
   94 |    3 |       3 | {1,3,94}       | f
   94 |    1 |       5 | {1,3,94,2,94}  | t
    7 |    5 |       5 | {94,1,3,5,7}   | f
(33 Zeilen)

test=*# create view z as (with recursive Bekanntenliste (apid, bpid, breadth , path, cycle) as (
  select  apid, bPid, 1, ARRAY[apid], false
 
FROM subset
WHERE aPID=1 OR bPID=1
   union all
   select  c.apid, c.bpid,sg.breadth +1, path || c.apid , c.apid=ANY(path)
   from subset c, Bekanntenliste sg
  where (c.apid=sg.bpid OR c.bpid=sg.apid) AND NOT cycle )
select DISTINCT *
from Bekanntenliste
where (apid <> 1 OR bpid <>1));
CREATE VIEW
test=*# select apid, bpid, min(array_length(path, 1)) from z group by apid, bpid;
 apid | bpid | min 
------+------+-----
    3 |    5 |   2
    7 |    5 |   4
    1 |  101 |   1
   94 |    1 |   1
    1 |    3 |   1
    5 |    3 |   3
    2 |   94 |   2
   94 |    3 |   3
(8 Zeilen)

test=*#

Besser?

das mit der 7, was du noch hast, kommt wohl daher, daß (3,5) und (5,3) drin ist, du solltest sicherstellen, daß sowas nicht passieren kann. Constraints helfen.

Besser schon, ja. Aber scheinbar leider immernoch nicht ganz richtig.

Ich habe nun das Päarchen 5;3 aus der Tabelle entfernt, und kann die 7 immernoch nicht erreichen.

Das Resultat ist nach dem
DELETE WHERE apid=5 AND bpid=3
ist:

1;101;1
94;1;1
1;3;1
3;5;2
2;94;2
94;3;3

Ich habe die SQL-Abfrage etwas verändert und bin jetzt nahezu am gewünschten Ergebnis.
Die folgende Query

select distinct apid, cnt FROM(

select distinct apid, bpid, min(array_length(path, 1)) cnt from ((with recursive Bekanntenliste (apid, bpid, breadth , path, cycle) as (
  select  apid, bPid, 1, ARRAY[apid], false
 
FROM subset
WHERE aPID=1 OR bPID=1
   union all
   select distinct c.apid, c.bpid,sg.breadth +1, path || c.apid , c.apid=ANY(path)
   from subset c, Bekanntenliste sg
  where (c.apid=sg.bpid OR c.bpid=sg.apid or c.bpid=sg.bpid) AND NOT cycle )
select DISTINCT *
from Bekanntenliste
where (apid <> 1 OR bpid <>1))) as x  group by apid, bpid order by cnt) as f
where apid != 1

UNION 
select distinct bpid, cnt FROM(

select distinct apid, bpid, min(array_length(path, 1)) cnt from ((with recursive Bekanntenliste (apid, bpid, breadth , path, cycle) as (
  select  apid, bPid, 1, ARRAY[apid], false
 
FROM subset
WHERE aPID=1 OR bPID=1
   union all
   select distinct c.apid, c.bpid,sg.breadth +1, path || c.apid , c.apid=ANY(path)
   from subset c, Bekanntenliste sg
  where (c.apid=sg.bpid OR c.bpid=sg.apid or c.bpid=sg.bpid) AND NOT cycle )
select DISTINCT *
from Bekanntenliste
where (apid <> 1 OR bpid <>1))) as x  group by apid, bpid order by cnt) as f
where bpid != 1
order by cnt
;

gibt mir das Ergebnis

101;1
94;1
3;1
3;2
94;2
2;2
5;2
5;3
7;3

Jetzt wäre es noch wünschenswert, wenn die doppelten Zahlen (z.B. 94 und 3) rausfallen und nur einmal in der kleinsten Ebene angezeigt werden. Also hier 94;1 5;2 und 3;1. Jemand eine Idee?

das ist jetzt darauf aber nur ein select x, min(y) group by x.