Baum Abfragen mit SQL und CTE (Common Table Expression)

Ich habe eine interessante Projektanfrage bekommen. Es geht um die Erstellung von Auswertungen für Telefondaten z.B. aus einem Call Center.
Die Daten liegen in einer SQL-Datenbank vor und der aktuelle Bearbeiter kommt nicht so richtig weiter.
Ein Problem ist, dass die Weiterverbindung von Anrufen in einer Baumstruktur gespeichert wird. Zur Auswertung müssen Daten aller verbundenen Knoten (Teilnehmer) aggregiert werden.

Mit Programmlogik sicher kein Problem aber nur mit SQL? Mir fällt spontan Oracles CONNECT BY PRIOR ein aber es ist ein anderes DB-System.

Ich recherchiere dazu und stoße schließlich auf CTE. Common Table Expression sind im SQL 99 Standard definiert und werden von vielen großen Datenbanksystemen unterstützt (z.B. Oracle, DB/2, MSSQL Server, PostGre und mehr).

Die Syntax ist etwas gewöhnungsbedürftig und ich habe mir ein kleines Beispiel erstellt.


Tabelle mit Anrufen:

create table phone_call (
  id int primary key,
  delay int not null,
  duration int not null,
  parent_id int,
  agent varchar2(10)
);

• id: Primärschlüssel des Anrufs
• delay: Verzögerung in Sekunden bis ein Mitarbeiter abnimmt
• duration: Dauer des Gesprächs
• parent_id: Falls der Anruf innerhalb des Callcenters weiter verbunden wurde verweist parent_id auf den Anruf von dem weiterverbunden wurde.
• agent: Mitarbeiter des Callcenters (vereinfacht ohne Relation)

Die folgenden Inserts erzeugen Beispieldaten:

INSERT INTO phone_call VALUES(1, 3, 20, null, 'Müller');
INSERT INTO phone_call VALUES(2, 4, 15, 1, 'Meier');
INSERT INTO phone_call VALUES(3, 3, 300, 2, 'Schulze');

INSERT INTO phone_call VALUES(4, 5, 200, null, 'Pinnau');

INSERT INTO phone_call VALUES(5, 3, 20, null, 'Schulze');
INSERT INTO phone_call VALUES(6, 5, 120, 5, 'Pinnau');

• Die Beispieldaten loggen 3 von aussen eingehende Anrufe (erkennbar an parent_id = null). Der 1. Anruf wird von Müller weiter zu Meier und dann zu Schulze verbunden.
• Der 2. Anruf bleibt bei Pinnau und wird nicht weiterverbunden.
• Der 3. Anruf wird von Schulze angenommen und zu Pinnau verbunden.

Es soll jetzt eine Auswertung gemacht werden. Im Ergebnis soll jeder von aussen eingehende Anruf ausgegeben werden und folgende Statistiken geliefert werden:

1. Gesamtzeit des Telefonats (alle Stationen: delay + duration)
2. Gesamtzeit Warten (alle Stationen: delay)
3. Gesamtzeit Sprechen (alle Stationen: duration)
4. Anzahl der Weiterverbindungen

Für den Anfang starte ich mit folgendem CTE-SQL Block:

WITH call_tree (c_id, c_delay, c_duration, c_hops) AS
(
    -- Initial query (root elements, parent_id is null)
    SELECT id, delay, duration, 0 FROM phone_call
        WHERE parent_id is null
    
    UNION ALL
    
    -- children (recursive): JOIN phone_call with call_tree ALIAS
    SELECT id, delay + c_delay, duration + c_duration, 0
      FROM phone_call, call_tree WHERE parent_id = c_id
)
SELECT * from call_tree

Die entscheidenden Zeilen befinden sich innerhalb des WITH-Blocks. Um einen Baum von oben nach unten zu traversieren, startet man zunächst mit der Abfrage der Wurzel-Element. Im Beispiel sind das alle Anruf-Datesätze mit parent_id is null:

SELECT id, delay, duration, 0 FROM phone_call WHERE parent_id is null

Mit einem UNION ALL werden dann die Ergebnisse der rekursiven Abfrage (Kinder und Kindeskinder) hinzugefügt:

SELECT id, delay + c_delay, duration + c_duration, 0
    FROM phone_call, call_tree WHERE parent_id = c_id

Im rekursive Teil  werden die Tabellen phone_call und call_tree (WITH-Alias) per INNER JOIN verbunden (WHERE parent_id = c_id).

Das Ergenbnis sieht schonmal ganz gut aus. Es werden alle Anrufstationen mit den im Baum aufgelaufenen Summen für delay und duration ausgegeben.

C_ID	C_DELAY	C_DURATION	C_HOPS
1	3	20	0
4	5	200	0
5	3	20	0
2	7	35	0
6	8	140	0
3	10	335	0

Es gibt noch 3 Probleme:

1. c_hops ist immer 0 (Anzahl der Weiterverbindungen)
2. Die Ergebnismenge enthält für jeden Datensatz aus phone_call eine Zeile. Es soll nur eine Zeile pro eingehendem Anruf kommen.
3. Gesamtzeit aus duration + delay fehlt noch

Um die Hops zu ermitteln muss im rekursiven Teil die 0 nur durch c_hops+1 ersetzt werden. Im Initialteil bleibt die 0 stehen, damit der Hop-Zähler bei 0 anfängt:

WITH call_tree (c_id, c_delay, c_duration, c_hops) AS
(
    -- Initial query (root elements, parent_id is null)
    SELECT id, delay, duration, 0 FROM phone_call
        WHERE parent_id is null
    
    UNION ALL
    
    -- children (recursive): JOIN phone_call with call_tree ALIAS
    SELECT id, delay + c_delay, duration + c_duration, c_hops+1
      FROM phone_call, call_tree WHERE parent_id = c_id
)
SELECT * from call_tree

Jetzt sollen nur noch die letzten Datensätze im Baum (also die Blätter) angezeigt werden. Das ist etwas schwierig. Mir ist erstmal nichts besseres eingefallen als in der äußeren Abfrage mit einem COUNT()-Subquery zu filtern:

WITH call_tree (c_id, c_delay, c_duration, c_hops) AS
(
    -- Initial query (root elements, parent_id is null)
    SELECT id, delay, duration, 0 FROM phone_call
        WHERE parent_id is null
    
    UNION ALL
    
    -- children (recursive): JOIN phone_call with call_tree ALIAS
    SELECT id, delay + c_delay, duration + c_duration, c_hops+1
       FROM phone_call, call_tree WHERE parent_id = c_id
)
SELECT * from call_tree

-- Only leafs: children count = 0
WHERE ( SELECT count(*) from phone_call WHERE parent_id = c_id ) = 0

Im letzten Schritt muss noch die Summe aus delay und duration eingebaut werden:

WITH call_tree (c_id, c_delay, c_duration, c_hops) AS
(
    -- Initial query (root elements, parent_id is null)
    SELECT id, delay, duration, 0 FROM phone_call
       WHERE parent_id is null
    
    UNION ALL
    
    -- children (recursive): JOIN phone_call with call_tree ALIAS
    SELECT id, delay + c_delay, duration + c_duration, c_hops+1
      FROM phone_call, call_tree WHERE parent_id = c_id
)
SELECT c_id, c_delay + c_duration as c_total, c_delay,
    c_duration from call_tree
WHERE (SELECT count(*) from phone_call WHERE parent_id = c_id) = 0

Ergebnis:

C_ID	C_TOTAL	C_DELAY	C_DURATION
6	148	8	140
4	205	5	200
3	345	10	335

Man könnte noch mehr machen und z.B. auch die Namen der an der Anrufkette beteiligten Mitarbeiter als verketteten VARCHAR ausgeben usw.

Verbesserung

Für das konkrete Beispiel ist mir noch eine wesentliche Verbesserung eingefallen mit der auch das COUNT Subquery entfallen kann.
Dazu wird die Root-ID in alle Datensätze aufgenommen. Diese wird im Initial-Query selektiert und in den rekursiven Abfragen unverändert durchgeleitet. Damit kann man zum Schluß nach der Root-ID gruppieren und die Aggregate für jeden Ast des Baumes bilden:

WITH call_tree (c_id, c_delay, c_duration, c_root_id) AS
(
    -- Initial query (root elements, parent_id is null)
    SELECT id, delay, duration, id FROM phone_call
       WHERE parent_id is null
    
    UNION ALL
    
    -- children (recursive): JOIN phone_call with call_tree ALIAS
    SELECT id, delay, duration, c_root_id
      FROM phone_call, call_tree WHERE parent_id = c_id
)
SELECT c_root_id, sum(c_delay + c_duration) as c_total,
    sum(c_delay) as c_delay, sum(c_duration) as c_duration,
    count(c_root_id) - 1 as hops from call_tree
GROUP BY c_root_id

Die Hops ermittelt man mit COUNT(c_root_id) - 1.