Fehler in der Rekursion

Fragen und Probleme zu PL/pgSQL.
Antworten
wir12flb
Neuer Benutzer
Beiträge: 4
Registriert: Do 9. Jun 2016, 14:20
Wohnort: Leipzig
Kontaktdaten:

Fehler in der Rekursion

Beitrag von wir12flb » Do 9. Jun 2016, 15:19

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:

Code: Alles auswählen

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.

Code: Alles auswählen

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
result.PNG (17.65 KiB) 3462 mal betrachtet
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. :(

Hat jemand eine Idee?

Viele Grüße,
Kevin

akretschmer
Erfahrener Benutzer
Beiträge: 7677
Registriert: So 29. Okt 2006, 13:35
Wohnort: Kaufbach, Sachsen, Germany, Germany
Kontaktdaten:

Re: Fehler in der Rekursion

Beitrag von akretschmer » Do 9. Jun 2016, 16:15

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.
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

wir12flb
Neuer Benutzer
Beiträge: 4
Registriert: Do 9. Jun 2016, 14:20
Wohnort: Leipzig
Kontaktdaten:

Re: Fehler in der Rekursion

Beitrag von wir12flb » Do 9. Jun 2016, 16:36

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:

Code: Alles auswählen

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

Code: Alles auswählen

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:

Code: Alles auswählen

apid, bpid , ebene
1 , 3 , 1
1, 101 , 1
94 , 1 , 1
3 , 5, 2
...

akretschmer
Erfahrener Benutzer
Beiträge: 7677
Registriert: So 29. Okt 2006, 13:35
Wohnort: Kaufbach, Sachsen, Germany, Germany
Kontaktdaten:

Re: Fehler in der Rekursion

Beitrag von akretschmer » Do 9. Jun 2016, 17:01

Code: Alles auswählen

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.
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

wir12flb
Neuer Benutzer
Beiträge: 4
Registriert: Do 9. Jun 2016, 14:20
Wohnort: Leipzig
Kontaktdaten:

Re: Fehler in der Rekursion

Beitrag von wir12flb » Sa 11. Jun 2016, 19:37

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:

Code: Alles auswählen

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

wir12flb
Neuer Benutzer
Beiträge: 4
Registriert: Do 9. Jun 2016, 14:20
Wohnort: Leipzig
Kontaktdaten:

Re: Fehler in der Rekursion

Beitrag von wir12flb » So 12. Jun 2016, 17:25

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

Code: Alles auswählen


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

Code: Alles auswählen

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?

akretschmer
Erfahrener Benutzer
Beiträge: 7677
Registriert: So 29. Okt 2006, 13:35
Wohnort: Kaufbach, Sachsen, Germany, Germany
Kontaktdaten:

Re: Fehler in der Rekursion

Beitrag von akretschmer » So 12. Jun 2016, 18:42

das ist jetzt darauf aber nur ein select x, min(y) group by x.
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Antworten