/*************************************************************
 * Berechnung der Vorfahren einer Generation.
 * Um die Anfragen einfach zu halten, wird auf 
 * die Unterscheidung der Geschlechter
 * (Großmütter, Großväter etc.) verzichtet.
 *
 * Um die Namen der Personen ausgeben zu können, wird 
 * die View eltern an Stelle der Beziehungstabelle
 * Eltern verwendet.
 *************************************************************/

-- Alle Eltern:
SELECT   p_id, p_name, e_id, e_name
FROM     eltern
ORDER BY p_name, e_name
;

-- Alle Personen sowie deren Eltern, sofern diese bekannt sind:
SELECT   p_id, p_name, e_id, e_name
FROM     person LEFT JOIN eltern USING (p_id, p_name)
ORDER BY p_name, e_name
;



-- Alle Großeltern:
SELECT   e1.p_id, e1.p_name, e2.e_id, e2.e_name
FROM     eltern e1 JOIN eltern e2 ON e1.e_id = e2.p_id
ORDER BY p_name, e_name
;

-- Alle Personen sowie deren Großeltern, sofern diese bekannt sind:
SELECT   p.p_id, p.p_name, e2.e_id, e2.e_name
FROM     person p
         LEFT JOIN
         (eltern e1 JOIN eltern e2 ON e1.e_id = e2.p_id)
         ON p.p_id = e1.p_id
ORDER BY p_name, e_name
;



-- Alle Urgroßeltern:
SELECT   e1.p_id, e1.p_name, e3.e_id, e3.e_name
FROM     eltern e1 JOIN eltern e2 ON e1.e_id = e2.p_id
                   JOIN eltern e3 ON e2.e_id = e3.p_id
ORDER BY p_name, e_name
;


-- Alle Personen sowie deren Urgroßeltern, sofern diese bekannt sind:
SELECT   p.p_id, p.p_name, e3.e_id, e3.e_name
FROM     person p
         LEFT JOIN
         (eltern e1 JOIN eltern e2 ON e1.e_id = e2.p_id
                    JOIN eltern e3 ON e2.e_id = e3.p_id
         )
         ON p.p_id = e1.p_id
ORDER BY p_name, e_name
;


-- Alle Ururgroßeltern:
SELECT   e1.p_id, e1.p_name, e4.e_id, e4.e_name
FROM     eltern e1 JOIN eltern e2 ON e1.e_id = e2.p_id
                   JOIN eltern e3 ON e2.e_id = e3.p_id
                   JOIN eltern e4 ON e3.e_id = e4.p_id
ORDER BY p_name, e_name
;


-- Alle Personen sowie deren Ururgroßeltern, sofern diese bekannt sind:
SELECT   p.p_id, p.p_name, e4.e_id, e4.e_name
FROM     person p
         LEFT JOIN
         (eltern e1 JOIN eltern e2 ON e1.e_id = e2.p_id
                    JOIN eltern e3 ON e2.e_id = e3.p_id
                    JOIN eltern e4 ON e3.e_id = e4.p_id
         )
         ON p.p_id = e1.p_id
ORDER BY p_name, e_name
;


/*************************************************************
 * Berechnung "aller" Vorfahren ohne Rekursion.
 *************************************************************/

-- Maximale Anzahl der Vorfahren je Generation

SELECT g_bezeichnung, 2^g_id AS max_anzahl
FROM   generation
;
 
 
-- Alle Vorfahren bis zur Ururgroßeltern-Generation:

SELECT   e1.p_id, e1.p_name, e_id AS v_id, e_name AS v_name,
         1 AS v_generation
FROM     eltern e1

UNION

SELECT   e1.p_id, e1.p_name, e2.e_id AS v_id, e2.e_name AS v_name,
         2 AS v_generation
FROM     eltern e1 JOIN eltern e2 ON e1.e_id = e2.p_id

UNION

SELECT   e1.p_id, e1.p_name, e3.e_id AS v_id, e3.e_name AS v_name,
         3 AS v_generation
FROM     eltern e1 JOIN eltern e2 ON e1.e_id = e2.p_id
                   JOIN eltern e3 ON e2.e_id = e3.p_id
           
UNION

SELECT   e1.p_id, e1.p_name, e4.e_id AS v_id, e4.e_name AS v_name,
         4 AS v_generation
FROM     eltern e1 JOIN eltern e2 ON e1.e_id = e2.p_id
                   JOIN eltern e3 ON e2.e_id = e3.p_id
                   JOIN eltern e4 ON e2.e_id = e4.p_id

-- Und so weiter. Für jede weitere Generation folgt
-- eine weitere SELECT-Anweisung mit jeweils einem
-- weitern eltern-JOIN.

ORDER BY p_name, v_generation
;


-- Alle Personen (Generation 0) sowie deren Vorfahren 
-- (bis zu den Urgroßeltern), die bekannt sind:

SELECT   p.p_id, p.p_name, p.p_id AS v_id, p.p_name AS v_name,
         0 AS v_generation
FROM     person p

UNION

SELECT   e1.p_id, e1.p_name, e_id AS v_id, e_name AS v_name,
         1 AS v_generation
FROM     eltern e1

UNION

SELECT   e1.p_id, e1.p_name, e2.e_id AS v_id, e2.e_name AS v_name,
         2 AS v_generation
FROM     eltern e1 JOIN eltern e2 ON e1.e_id = e2.p_id

UNION

SELECT   e1.p_id, e1.p_name, e3.e_id AS v_id, e3.e_name AS v_name,
         3 AS v_generation
FROM     eltern e1 JOIN eltern e2 ON e1.e_id = e2.p_id
                   JOIN eltern e3 ON e2.e_id = e3.p_id
-- Und so weiter. Für jede weitere Generation folgt
-- eine weitere SELECT-Anweisung mit jeweils einem
-- weitern eltern-JOIN.

ORDER BY p_name, v_generation
;

/*************************************************************
 * Berechnung "aller" Vorfahren mit Rekursion.
 *************************************************************/

-- Alle Vorfahren:
WITH RECURSIVE vorfahren (p_id, p_name, v_id, v_name, v_generation)
AS
( -- Die Eltern sind Vorfahren der ersten Generation
  -- (nicht-rekursiver Zweig).
  SELECT   v.p_id, v.p_name, e_id AS v_id, e_name AS v_name,
           1 AS v_generation
  FROM     eltern v
  UNION
  -- Die Eltern der Vorfahren der n-ten Generation
  -- sind Vorfahren der n-plus-ersten Generation
  -- (rekursiver Zweig).
  SELECT   v.p_id, v.p_name, e.e_id AS v_id, e.e_name AS v_name,
           v.v_generation+1 AS v_generation
  FROM     vorfahren v JOIN eltern e ON v.v_id = e.p_id
)
SELECT   p_id, p_name, v_id, v_name, v_generation
FROM     vorfahren
ORDER BY p_name, v_generation
;


-- Alle Personen (Generation 0) sowie deren Vorfahren 
-- (bis zu den Urgroßeltern), die bekannt sind:
WITH RECURSIVE vorfahren (p_id, p_name, v_id, v_name, v_generation)
AS
( -- Die Personen selbst sind Vorfahren der nullten Generation
  -- (nicht-rekursiver Zweig).
  SELECT   v.p_id, v.p_name, v.p_id AS v_id, v.p_name AS v_name,
           0 AS v_generation
  FROM     person v
  UNION
  -- Die Eltern der Vorfahren der n-ten Generation
  -- sind Vorfahren der n-plus-ersten Generation
  -- (rekursiver Zweig).
  SELECT   v.p_id, v.p_name, e.e_id AS v_id, e.e_name AS v_name,
           v.v_generation+1 AS v_generation
  FROM     vorfahren v JOIN eltern e ON v.v_id = e.p_id
)
SELECT   p_id, p_name, v_id, v_name, v_generation
FROM     vorfahren
ORDER BY p_name, v_generation
;

-- Alle Personen (Generation 0) sowie deren Vorfahren
-- (bis zu den Urgroßeltern), die bekannt sind:
-- mit Bezeichnung der Generation
WITH RECURSIVE vorfahren
 (p_id, p_name, p_geschlecht, v_id, v_name, v_geschlecht, v_generation)
AS
( -- Die Personen selbst sind Vorfahren der nullten Generation
  -- (nicht-rekursiver Zweig).
  SELECT   v.p_id, v.p_name, v.p_geschlecht,  
           v.p_id, v.p_name, v.p_geschlecht,
           0
  FROM     person v
  
  UNION ALL -- UNION = UNION DISTINCT würde auch funktionieren,
            -- wäre aber weniger performant.
			
  -- Die Eltern der Vorfahren der n-ten Generation
  -- sind Vorfahren der n-plus-ersten Generation
  -- (rekursiver Zweig).
  SELECT   v.p_id, v.p_name, v.p_geschlecht,
           e.e_id, e.e_name, e.e_geschlecht,
           v.v_generation+1
  FROM     vorfahren v JOIN eltern e ON v.v_id = e.p_id
)
SELECT   p_id, p_name, p_geschlecht,
         v_id, v_name, v_geschlecht,
         v_generation,
         g_bezeichnung,
         CASE
          WHEN v_geschlecht = 'Frau' 
            THEN g_bezeichnung_frau
            ELSE g_bezeichnung_mann
         END AS g_bezeichnung_geschlecht,
         2^v_generation AS max_anzahl
FROM     vorfahren JOIN generation ON v_generation = g_id
ORDER BY p_name, v_generation
;

-- Pfade zu allen Vorfahren einer Person.
WITH RECURSIVE vorfahren (p_id, p_name, v_ids, v_namen)
AS
( -- Für Personen, für die keine Eltern bekannt sind,
  -- besteht der Vorfahrenpfad nur aus der Person selbst
  -- (nicht-rekursiver Zweig).
  SELECT   p.p_id, p.p_name,
           -- Der Pfad enthält nur die Person selbst.
           ARRAY[p.p_id]   AS v_ids,
           ARRAY[p.p_name] AS v_namen
  FROM     person p
  WHERE    NOT EXISTS -- Es gibt für p.p_id keinen
                      -- Eintrag in der Eltern-Relation.
           (SELECT * FROM eltern e WHERE e.p_id = p.p_id) 

  UNION ALL 
  
  -- Für Personen e.p_id, für deren Eltern bereits Personenpfade
  -- bekannt sind, berechnet man die Personenpfade, 
  -- indem man ihre Namen den Personenpfaden der
  -- Eltern voarnstellt.
  SELECT   e.p_id, e.p_name,
           ARRAY[e.p_id]   || v_ids    AS v_ids,
           ARRAY[e.p_name] || v_namen  AS v_namen
  FROM     vorfahren v JOIN eltern e ON v.p_id = e.e_id
)
SELECT p_id, p_name, v_ids, v_namen
FROM vorfahren
ORDER BY p_name, p_id
;

-- Die vorherige Loesung hat noch den Nachteil, dass für
-- eine Person nicht ein Vorfahrensbaum, sondern diverse 
-- unabhängige Pfade generiert werden.
--
-- Die Funktion ARRAY_AGGREGATE_DISTINCT kann nicht 
-- verwendet werden, weil bei Arrays alle Elemente vom 
-- selben Typ sein müssen. Ein Vorfahrenbaum enthält 
-- jedoch Namen sowie Bäume als Elemente.
WITH RECURSIVE vorfahren (p_id, p_name, v_ids, v_namen)
AS
( -- Für Personen, für die keine Eltern bekannt sind,
  -- besteht der Vorfahrenbaum nur aus der Person selbst
  -- (nicht-rekursiver Zweig).
  SELECT   p.p_id, p.p_name,
           -- Der Pfad enthält nur die Person selbst.
           '[' || p.p_id || ']'   AS v_ids,
           '[' || p.p_name || ']' AS v_namen
  FROM     person p
  WHERE    NOT EXISTS -- Es gibt für p.p_id keinen
                      -- Eintrag in der Eltern-Relation.
           (SELECT * FROM eltern e WHERE e.p_id = p.p_id)

  UNION ALL 

  -- Für Personen e.p_id, für deren Eltern bereits Personenbäume
  -- bekannt sind, berechnet man den Personenbaum, 
  -- indem man ihren jeweilgen Namen der Vereigigung (Aggregation) der
  -- Personenbäumen der Eltern voranstellt. Um einen Vorfahrenbaum 
  -- zu generieren, muss das ganze noch aggregiert werden.
  SELECT   p_id, p_name,
           '[' || p_id   || ',' ||
           SUBSTRING(STRING_ARRAY_AGGREGATE_DISTINCT(v_ids) FROM 2)   AS v_ids,
           '[' || p_name || ',' ||
           SUBSTRING(STRING_ARRAY_AGGREGATE_DISTINCT(v_namen) FROM 2) AS v_namen
  FROM     -- Diese Dummy-Subquery ist notwendig, da Postgres keine
           -- Aggregationsfunktionen in Subqueries enthalten darf,
           -- die auf die rekursiv definierte View zugreifen.
           (SELECT e.p_id, e.p_name, v_ids, v_namen
            FROM vorfahren v JOIN eltern e ON v.p_id = e.e_id
           ) AS dummy
  GROUP BY p_id, p_name
)
SELECT p_id, p_name, v_ids, v_namen
FROM vorfahren
ORDER BY p_name, p_id
;

-- Und dasselbe noch einmal mit JSON (genauer gesagt: JSONB,
-- das heißt, mit der JSON-Variante, die mit alle 
-- Postgres-Domänen kompatibel ist).
WITH RECURSIVE vorfahren (p_id, p_name, v_ids, v_namen)
AS
(
  -- Für Personen, für die keine Eltern bekannt sind,
  -- besteht der Vorfahrenpfad nur aus der Person selbst
  -- (nicht-rekursiver Zweig).
  SELECT   p.p_id, p.p_name,
           -- Der Pfad enthält nur die Person selbst.
           JSONB_BUILD_ARRAY(p.p_id)   AS v_ids,
           JSONB_BUILD_ARRAY(p.p_name) AS v_namen
  FROM     person p
  WHERE    NOT EXISTS -- Es gibt für p.p_id keinen
                      -- Eintrag in der Eltern-Relation.
           (SELECT * FROM eltern e WHERE e.p_id = p.p_id) 

  UNION ALL

  -- Für Personen e.p_id, für deren Eltern bereits Personenpfade
  -- bekannt sind, berechnet man die Personenpfade, 
  -- indem man ihre Namen den Personenpfaden der
  -- Eltern voarnstellt.
  SELECT   e.p_id, e.p_name,
           TO_JSONB(e.p_id)   || v_ids   AS v_ids,
           TO_JSONB(e.p_name) || v_namen AS v_namen
  FROM     vorfahren v JOIN eltern e ON v.p_id = e.e_id
)
SELECT p_id, p_name, v_ids, v_namen
FROM vorfahren
ORDER BY p_name, p_id
;


WITH RECURSIVE vorfahren (p_id, p_name, v_ids, v_namen)
AS
(
  -- Für Personen, für die keine Eltern bekannt sind,
  -- besteht der Vorfahrenpfad nur aus der Person selbst
  -- (nicht-rekursiver Zweig).
  SELECT   p.p_id, p.p_name,
           -- Der Pfad enthält nur die Person selbst.
           JSONB_BUILD_ARRAY(p.p_id)   AS v_ids,
           JSONB_BUILD_ARRAY(p.p_name) AS v_namen
  FROM     person p
  WHERE    NOT EXISTS -- Es gibt für p.p_id keinen
                      -- Eintrag in der Eltern-Relation.
           (SELECT * FROM eltern e WHERE e.p_id = p.p_id) 

  UNION ALL

  -- Für Personen e.p_id, für deren Eltern bereits Personenbäume
  -- bekannt sind, berechnet man den Personenbaum, 
  -- indem man ihren jeweilgen Namen der Vereigigung (Aggregation) der
  -- Personenbäumen der Eltern voranstellt. Um einen Vorfahrenbaum 
  -- zu generieren, muss das ganze noch aggregiert werden.
  SELECT   p_id, p_name,
           TO_JSONB(p_id)   || JSONB_AGG(v_ids)   AS v_ids,
           TO_JSONB(p_name) || JSONB_AGG(v_namen) AS v_namen
  FROM     -- Diese Dummy-Subquery ist notwendig, da Postgres keine
           -- Aggregationsfunktionen in Subqueries enthalten darf,
           -- die auf die rekursiv definierte View zugreifen.
           (SELECT e.p_id, e.p_name, v_ids, v_namen
            FROM vorfahren v JOIN eltern e ON v.p_id = e.e_id
           ) AS dummy
  GROUP BY p_id, p_name
)
SELECT p_id, p_name, v_ids, v_namen
FROM vorfahren
ORDER BY p_name, p_id
;