Italiano English

Firebird: Tree data mangement with recursive CTE

Last update: 05/01/2011 - Viewed: 6939 dal 05 Jan 2011 - Vote:5.0 (1 Votes)
Keywords: SQL, FireBird
Categories: Firebird: Tree data mangement
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

Vote this page
0    1    2    3    4    5   

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

Comments

0 comments (Send your comment)

Leave your comment:

Name:

Email:

Emails will not be visible or used in any way, and are not required

Comment:


Verify code:


Type the code you can see here on the left
 

Note:
  • Please keep comments relevant
  • Any content deemed inappropriate or offensive may be edited and/or deleted
  • No HTML code is allowed. Please use BBCode to format your text
  • URLs, complete of "http://" o "mailto:" , will be auto-linked