Italiano - English

Firebird: Tree data mangement with recursive CTE

Table of Contents

    Firebird: Tree data mangement
    1. Firebird: Tree data mangement with recursive Stored Procedure
    2. Firebird: Tree data mangement with recursive CTE
    Translation for this document is not available or is not complete,
    if you are intrested to receive information please write to

    This document shown how to use Firebird Recursive Common Table Expression to managing trees

    Una Common Table Expression (CTE) è una vista con la stessa validità di uno statement principale. Su una CTE è ammessa la ricorsione questo permette di navigare attraverso strutture dati ad albero con una singola select.

    Di seguito la struttura di una CTE ricorsiva:

     
    WITH RECURSIVE
      cte_alias AS 
      (
        SELECT root_data FROM Table1 T1 -- root node data
        UNION ALL
        SELECT child_data FROM Table1 T2 -- children’s data
          JOIN cte_alias ON parent LINK
      )
    SELECT * FROM cte_alias

    La JOIN può essere definita sulla stessa tabella

    Un Esempio pratico

    Facendo riferimento alla tabella FAMILY ed i dati presentati nella pagina principale

    • GrandFather1,  Età:80
      • Son1, Età:60
        • GrandSon1, Eta 14
        • GrandSon2, Età 19
      • Son2, Età 58

    Tramite una CTE ricorsiva è possibile interrogare la tabella FAMILY ed ottenere la struttura correttamente elencata. Ad esempio la seguente CTE

     
    WITH RECURSIVE
      FAMILYTREE AS
      (
        SELECT * FROM FAMILY T1 -- root node data
        WHERE T1.idfather IS NULL
     
        UNION ALL
     
        SELECT * FROM FAMILY T2 -- children’s data
          JOIN FAMILYTREE ON T2.idfather = FAMILYTREE.id
      )
    SELECT * FROM FAMILYTREE

    produce il seguente risultato:

    ID IDFATHER NOME AGE
    1 null GrandFather1 80
    2 1 Son1 60
    4 2 GrandSon1 14
    5 2 GrandSon2 19
    3 1 Son2 58

    All'interno della CTE e' possibile combinare le informazioni per ottenere ulteriori campi. Ad esempio la sequente CTE

     
    WITH RECURSIVE
      FAMILYTREE AS
      (
        SELECT
          0 AS DEPTH,
          CAST('|' AS VARCHAR(50)) AS IDENT,
          CAST(T1.NOME AS VARCHAR(150)) AS PATH,
          T1.*
        FROM FAMILY T1 -- root node data
        WHERE T1.idfather IS NULL
     
        UNION ALL
     
        SELECT
          FAMILYTREE.DEPTH + 1 AS DEPTH,
          FAMILYTREE.IDENT || '------' AS IDENT,
          FAMILYTREE.path || '>' || T2.nome AS path,
          T2.*
          FROM FAMILY T2 -- children’s data
          JOIN FAMILYTREE ON T2.idfather = FAMILYTREE.id
      )
    SELECT ID,idfather,AGE,DEPTH,IDENT||nome AS Name,PATH
    FROM FAMILYTREE

    produce il seguente risultato:

    ID IDFATHER AGE DEPTH NAME PATH
    1 null 80 0 |GrandFather1 GrandFather1
    2 1 60 1 |-----Son1 GrandFather1>Son1
    4 2 14 2 |----------GrandSon1 GrandFather1>Son1>GrandSon1
    5 2 19 2 |----------GrandSon2 GrandFather1>Son1>GrandSon2
    3 1 58 1 |-----Son2 GrandFather1>Son2

    Utilizzare una CTE in una View

    Una CTE può essere utilizzata come una normale query, ma per semplificare le interrogazioni, è anche possibile creare una view che contiene una CTE.

    Una view con la CTE dell'esempio precedente puo' essere la seguente:

     
    CREATE VIEW VIEW_FAMILYTREE(
        ID,
        IDFATHER,
        DEPTH,
        NAME,
        PATH)
    AS
    WITH RECURSIVE
      FAMILYTREE AS
      (
        -- root nodes data
        SELECT
          0 AS DEPTH,
          CAST('|' AS VARCHAR(50)) AS IDENT,
          CAST(T1.NOME AS VARCHAR(150)) AS PATH,
          T1.*
        FROM FAMILY T1
        WHERE T1.idfather IS NULL
     
        UNION ALL
        -- childrens data
        SELECT
          FAMILYTREE.DEPTH + 1 AS DEPTH,
          FAMILYTREE.IDENT || '------' AS IDENT,
          FAMILYTREE.path || '>' || T2.nome AS path,
          T2.*
          FROM FAMILY T2
          JOIN FAMILYTREE ON T2.idfather = FAMILYTREE.id
      )
    SELECT ID,idfather,AGE,DEPTH,IDENT||nome AS Name,PATH
    FROM FAMILYTREE
    ;

    Utilizzare una CTE in un trigger per memorizzare informazioni sulla struttura ad albero

    Come si è detto una CTE è una normale query e può essere eseguita ogni volta che serve interrogare la struttura albero, tuttavia è bene ricordare che si tratta di una query ricorsiva che se pur seguita sul server, potrebbe essere onerosa.

    Nel caso in cui la struttura non cambia troppo di frequente è possibile utilizzare una CTE all'interno di un trigger per mantenere aggiornati alcuni campi utili ai fini della struttura.

    Ad esempio nella tabella FAMILY si potrebbero creare i seguenti campi per memorizzare le informazioni relative alla struttura:

    • TREE_SORT_KEY: per memorizzare l'ordine sequenziale nella struttura
    • IDROOT: per memorizzare la radice a cui appartiene un record
    • PATH: per avere il percorso dei nomi sempre disponibile
    • PATHID: per avere il percorso degli ID sempre disponibile

    Modifichiamo quindi la tabella FAMILY:

     
    ALTER TABLE FAMILY ADD TREE_SORT_KEY INTEGER;
    ALTER TABLE FAMILY ADD IDROOT INTEGER;
    ALTER TABLE FAMILY ADD PATH VARCHAR(150);
    ALTER TABLE FAMILY ADD PATHID VARCHAR(50)

    Infine creiamo un trigger AFTER INSERT/UPDATE/DELETE per compilare al volo i campi appena creati.

     
    CREATE OR ALTER TRIGGER FAMILY_AIUD0 FOR FAMILY
    ACTIVE AFTER INSERT OR UPDATE OR DELETE POSITION 32000
    AS
      DECLARE VARIABLE ID INTEGER;
      DECLARE VARIABLE IDROOT INTEGER;
      DECLARE VARIABLE PATHID BLOB SUB_TYPE 1;
      DECLARE VARIABLE PATH BLOB SUB_TYPE 1;
      DECLARE VARIABLE AUTOINC INTEGER;
    BEGIN
      AUTOINC = 0;
      IF ( (NEW.ID IS DISTINCT FROM OLD.ID) OR
           (NEW.IDFATHER IS DISTINCT FROM OLD.IDFATHER) OR
           (NEW.NOME IS DISTINCT FROM OLD.NOME) ) THEN
     
      FOR WITH RECURSIVE
    FAMILYTREE AS (
        SELECT
            T1.ID,
            T1.ID AS IDROOT,
            CAST(T1.NOME AS VARCHAR(150)) AS PATH,
            CAST(';' || T1.ID || ';' AS BLOB SUB_TYPE 1) AS PATHID
        FROM FAMILY T1
        WHERE (T1.IDFATHER IS NULL)
     
        UNION ALL
     
        SELECT
            T2.ID,
            FAMILYTREE.IDROOT,
            FAMILYTREE.PATH || '>' || T2.NOME  AS PATH,
            FAMILYTREE.PATHID || T2.ID || ';' AS PATHID
        FROM FAMILY T2
        JOIN FAMILYTREE ON (T2.IDFATHER = FAMILYTREE.ID)
    )
    SELECT ID,IDROOT,path,pathid FROM FAMILYTREE
      INTO :ID,:IDROOT,:path,:pathid
      DO
      BEGIN
        UPDATE FAMILY SET
            IDROOT         = :IDROOT,
            PATHID         = :PATHID,
            PATH           = :PATH,
            TREE_SORT_KEY  = :autoinc
        WHERE ID = :ID;
        autoinc = autoinc+1;
      END
    END
     
    Questo trigger modifica i campi IDROOT,PATHID,PATH,TREE_SORT_KEY di tutti i record della tabella, ogni volta che uno dei campi "sensibili" ID,IDFATHER, NOME di un singolo record viene modificato.
    Questo implica che la modifica ad un singolo campo "sensibile" è molto onerosa inquanto viene eseguita una CTE ricorsiva da cui viene generato un UPDATE sull'intera tabella. Si consiglia di ulilizzare questa tecnica solo per strutture i cui campi "sensibili" cambiano molto di rado mentre al contrario le interrogazioni sulla struttura sono molto frequenti.

    Una volta creato il trigger, ogni volta che si esegue una modifica ai record le informazioni sulla struttura vengono aggiornate quindi si puo' interrogare la struttura con una semplice query:

     
    SELECT * FROM family ORDER BY TREE_SORT_KEY

    E ottenere il sequente risultato

    ID IDFATHER AGE NAME PATH TREE_SORT_K EY IDROOT PATHID
    1 null 80 GrandFather1 GrandFather1 0 1 ;1;
    2 1 60 Son1 GrandFather1>Son1 1 1 ;1;2;
    4 2 14 GrandSon1 GrandFather1>Son1>GrandSon1 2 1 ;1;2;4;
    5 2 19 GrandSon2 GrandFather1>Son1>GrandSon2 3 1 ;1;2;5;
    3 1 58 Son2 GrandFather1>Son2 4 1 ;1;3;

    Il vantaggio di questa soluzione è che le interrogazioni sulla struttura non sono ricorsive quindi veloci, lo svantaggio è che ogni aggiornamento è ricorsivo sull'intera tabella e potrebbe risultare lento.

    Ad ogni modo Il trigger garantisce che i campi PATH,TREE_SORT_KEY,IDROOT e PATHID saranno sempre aggiornati a patto di verificare la consitenza in caso di multiutenza e modifiche concorrenti.

    Ordinare i Padri e i Figli: Usare ORDER BY nelle CTE

    Uno dei problemi della tecnica qui mostrata è che non è possibile (almeno al momento in cui si scrive il presente articolo) utilizzare ORDER BY nelle UNION quindi nelle CTE, ovvero non è possibile gestire un ordinamento dei padri e dei figli. Ad esempio non è possibile elencare i record in ordine di età mantendo la relazione padre/figlio, ovvero ottenere il sequente risultato:

    ID IDFATHER NO   ME    AGE (DESC)
    1 null GrandFather1 80
    2 1 Son1 60
    5 2 GrandSon2 19
    4 2 GrandSon1 14
    3 1 Son2 58
    ID IDFATHER NO   ME AGE (ASC)  
    1 null GrandFather1 80
    3 1 Son2 58
    2 1 Son1 60
    4 2 Gra ndSon1 14
    5 1 GrandSon2 19

    Per avere la massima flessibilità nelle interrogazioni, e quindi anche gli ordinamenti delle strutture ad albero è necessario utilizzare le Stored Procedure ricorsive

    The coding examples presented here are for illustration purposes only. The author takes no responsibility for end-user use
    This work is property of Pk Lab. You can use it for free but you must retain author's copyright.
    Vote this page:

    Leave your comment:

    Note:
    • Your email email will not be visible or used in any way, and is not required
    • Please keep comments relevant
    • Any content deemed inappropriate or offensive may be edited and/or deleted
    • HTML code is not allowed. Please use BBCode to format your text
      [b]bold[/b], [u]underline[/u], [i]italic[/i], [code]code[/code]

    Comments

    0 comments