Home > Articoli > Recursive CTE and Bill Of Materials problem

Recursive CTE and Bill Of Materials problem

CTE, dalla versione 2005 di SQL Server, è l’acronimo di Common Table Expression. Una Table Expression è una tabella derivata, completamente virtuale, originata da una query. Una tabella derivata può essere citata nella clausola FROM come una qualsiasi altra tabella fisica. La visibilità di una tabella derivata è limitata alla query esterna della CTE.

SQL Server, attraverso le CTE, fornisce la possibilità di utilizzare query ricorsive che permettono di interrogare e manipolare strutture ad albero, gerarchie ecc…

Per descrivere le CTE ricorsive utilizzeremo un esempio del mondo reale: ci viene fornito in input l’identificativo univoco (ProductID) di un prodotto finito la cui (testata) distinta base (o distinta materiali) è memorizzata nella tabella Production.BillOfMaterialsHeader. L’output richiesto è rappresentato dall’esplosione scalare, a tutti i livelli, della distinta base del prodotto fornito in input. La tabella di testata Production.BillOfMaterialsHeader è relazionata alla tabella di dettaglio Production.BillOfMaterialsDetail attraverso la colonna BillOfMaterialsHeaderID. E’ richiesto che siano esplose anche tutte le eventuali distinte basi dei sottoprodotti (o prodotti intermedi) presenti nella distinta base del prodotto finito.

In questo problema non è noto il numero di prodotti intermedi, aventi distinta base, contenuti nella distinta del prodotto finito.

Il seguente frammento di codice T-SQL permette di create le tabelle Production.BillOfMaterialsHeader e Production.BillOfMaterialsDetail sul database AdventureWorks.

use [AdventureWorks];
go

— Setup tabelle

if OBJECT_ID(‘Production.BillOfMaterialsDetail’, ‘U’) is not null
  drop table Production.BillOfMaterialsDetail;
go

create table Production.BillOfMaterialsDetail
(
  BillOfMaterialsDetailID int identity(1, 1) not null,
  BillOfMaterialsHeaderID int not null,
  ComponentID varchar(20) not null,
  ProductQty decimal(8, 2) not null
  primary key(BillOfMaterialsDetailID)
);
go

if OBJECT_ID(‘Production.BillOfMaterialsHeader’) is not null
  drop table Production.BillOfMaterialsHeader;
go

create table Production.BillOfMaterialsHeader
(
  BillOfMaterialsHeaderID int identity(1, 1) not null,
  StartDate datetime not null,
  EndDate datetime null,
  ProductID varchar(20) not null
  primary key(BillOfMaterialsHeaderID)
);
go

alter table Production.BillOfMaterialsDetail add constraint
  fk_BillOfMaterialsHeader foreign key(BillOfMaterialsHeaderID)
    references Production.BillOfMaterialsHeader(BillOfMaterialsHeaderID);
go

create index idx_BOMDetail_HeaderID on Production.BillOfMaterialsDetail
(
  [BillOfMaterialsHeaderID] );
go

create index idx_BOMDetail_ComponentID on Production.BillOfMaterialsDetail
(
  [ComponentID] )
include (ProductQty);
go

create index idx_BOMHeader_ProductID on Production.BillOfMaterialsHeader
(
  [ProductID] );

Inseriamo ora la distinta materiali (semplificata) del prodotto finito “Mountain Bike”.

— Inserimento dati di prova

insert into Production.BillOfMaterialsHeader
(StartDate, EndDate, ProductID)
values
(‘20100101’, null, ‘Mountain Bike’),
(‘20100101’, null, ‘Gruppo Pedali’),
(‘20100101’, null, ‘Gruppo Ruote’);
go

insert into Production.BillOfMaterialsDetail
(
  BillOfMaterialsHeaderID,
  ComponentID,
  ProductQty
)
values
(
  (select
     bh.BillOfMaterialsHeaderID
   from
     Production.BillOfMaterialsHeader bh
   where
     (bh.ProductID = ‘Mountain Bike’)),
   ‘Manubrio’,
   1
),
(
  (select
     bh.BillOfMaterialsHeaderID
   from
     Production.BillOfMaterialsHeader bh
   where
     (bh.ProductID = ‘Mountain Bike’)),
   ‘Sella’,
   1
),
(
  (select
     bh.BillOfMaterialsHeaderID
   from
     Production.BillOfMaterialsHeader bh
   where
     (bh.ProductID = ‘Mountain Bike’)),
   ‘Adesivi’,
   6
),
(
  (select
     bh.BillOfMaterialsHeaderID
   from
     Production.BillOfMaterialsHeader bh
   where
     (bh.ProductID = ‘Mountain Bike’)),
   ‘Gruppo Ruote’,
   1
),
(
  (select
     bh.BillOfMaterialsHeaderID
   from
     Production.BillOfMaterialsHeader bh
   where
     (bh.ProductID = ‘Gruppo Ruote’)),
   ‘Ruota anteriore’,
   1
),
(
  (select
     bh.BillOfMaterialsHeaderID
   from
     Production.BillOfMaterialsHeader bh
   where
     (bh.ProductID = ‘Gruppo Ruote’)),
   ‘Ruota posteriore’,
   1
),
(
  (select
     bh.BillOfMaterialsHeaderID
   from
     Production.BillOfMaterialsHeader bh
   where
     (bh.ProductID = ‘Mountain Bike’)),
   ‘Gruppo Pedali’,
   1
),
(
  (select
     bh.BillOfMaterialsHeaderID
   from
     Production.BillOfMaterialsHeader bh
   where
     (bh.ProductID = ‘Gruppo Pedali’)),
   ‘Pedale’,
   2
);

Consultiamo i dati inseriti in figura 1:

select * from Production.BillOfMaterialsHeader;

select * from Production.BillOfMaterialsDetail;

Figura 1 – Dati di prova inseriti

 

L’output richiesto si ottiene con la seguente CTE ricorsiva:

with CTE_BillOfMaterials as
(
  — select "àncora" (anchor member)
  select
    h.ProductID
    ,d.ComponentID
    ,d.ProductQty
    ,1 as level
  from
    Production.BillOfMaterialsHeader h
  join
    Production.BillOfMaterialsDetail d
      on d.BillOfMaterialsHeaderID=h.BillOfMaterialsHeaderID
  where
    (h.ProductID=’Mountain Bike’)

  union all

  — select "ricorsiva" (recursive member)
  select
    h.ProductID
    ,d.ComponentID
    ,d.ProductQty
    ,(t.level + 1) as level
  from
    CTE_BillOfMaterials as t
  join
    Production.BillOfMaterialsHeader h
      on t.ComponentID=h.ProductID
  join
    Production.BillOfMaterialsDetail d
      on d.BillOfMaterialsHeaderID=h.BillOfMaterialsHeaderID
)
— query esterna (outer query)
select
  ProductID
  ,ComponentID
  ,level
from
  CTE_BillOfMaterials;

Figura 2 – Esplosione scalare della distinta materiali del prodotto Mountain Bike

 

Il corpo di una CTE ricorsiva è composto da almeno due query, conosciute come membri. La prima query, che compare nella precedente CTE, rappresenta il membro “àncora” (anchor member). Questa prima query restituisce semplicemente la tabella di base per la ricorsione.

Nel nostro caso, il seguente frammento T-SQL nella CTE, restituisce il primo livello della distinta materiali del prodotto finito (ProductID = ‘Mountain Bike’).

— select "àncora" (anchor member)
select
  h.ProductID
  ,d.ComponentID
  ,d.ProductQty
  ,1 as level
from
  Production.BillOfMaterialsHeader h
join
  Production.BillOfMaterialsDetail d
    on d.BillOfMaterialsHeaderID=h.BillOfMaterialsHeaderID
where
  (h.ProductID=’Mountain Bike’)

La seconda query, riprodotta nel seguente frammento di codice T-SQL, rappresenta il membro “ricorsivo” (recursive member) della precedente CTE.

— select "ricorsiva" (recursive member)
select
  h.ProductID
  ,d.ComponentID
  ,d.ProductQty
  ,(t.level + 1) as level
from
  CTE_BillOfMaterials as t
join
  Production.BillOfMaterialsHeader h
    on t.ComponentID=h.ProductID
join
  Production.BillOfMaterialsDetail d
    on d.BillOfMaterialsHeaderID=h.BillOfMaterialsHeaderID

Nel momento in cui scriviamo la query ricorsiva, dichiariamo una referenza ricorsiva al nome della CTE, nell’esempio CTE_BillOfMaterials.

Referenziare il nome della CTE nella query ricorsiva è diverso dal referenziare il nome della CTE nella query esterna (outer query). La query esterna restituisce, infatti, la tabella finale risultante dalla CTE e non scatena ricorsioni. L’elemento chiave che scatena la ricorsione è rappresentato dalla INNER JOIN che coinvolge la tabella CTE nel membro ricorsivo. Nel nostro caso la query ricorsiva restituisce l’esplosione scalare delle distinte basi dei prodotti intermedi contenuti nella distinta del prodotto finito.

Il processo di ricorsione di una CTE non ha un flag esplicito che ne determina l’interruzione, la ricorsione si ferma non appena la query ricorsiva restituisce un result set vuoto. Nel nostro caso, la query ricorsiva restituisce un result set vuoto per i componenti "Manubrio", "Sella" e "Adesivi" … mentre per il "Gruppo Ruote" e per il "Gruppo Pedali" restituisce rispettivamente la distinta materiali del "Gruppo Ruote" e la distinta materiali del "Gruppo Pedali".

Quando viene referenziato il nome della CTE nella query esterna, SQL Server concatena il result set del membro “àncora” (prima query) con i results sets di tutte le ricorsioni eseguite, il risultato è una tabella virtuale.

Qualora nasca il sospetto che i dati contengano riferimenti circolari o che il codice della CTE contenga un bug logico, si potrà specificare, nella query esterna, l’hint MAXRECURSION. Questa opzione rappresenta una misura di sicurezza per limitare il numero delle iterazioni ricorsive. Non appena il limite specificato viene superato, SQL Server restituirà un errore e l’esecuzione della CTE verrà interrotta. By default, il numero massimo di ricorsioni è impostato a 100. Per eliminare questo limite, è sufficiente specificare zero nell’hint MAXRECURSION.

Per capire come SQL Server processa le CTE ricorsive diamo un’occhiata al piano di esecuzione, illustrato in figura 3, prodotto per la precedente CTE.

Figura 3 – Piano di esecuzione prodotto per la precedente CTE

 

Osserviamo che il result set della SELECT “àncora” (ProductID = ‘Mountain Bike’) viene reperito con una scansione dell’indice Cluster sulla tabella Production.BillOfMaterialsDetail ed un operazione di Index Seek sulla tabella Production.BillOfMaterialsHeader. La successiva operazione Compute Scalar determina il contatore delle iterazioni (all’inizio è impostato a zero) che viene incrementato di uno per ogni iterazione della SELECT ricorsiva.

La SELECT “àncora” viene eseguita ed il result set prodotto viene trattato dal task Table Spool, anche la SELECT ricorsiva viene eseguita ed utilizza lo Spooler per risolvere la referenza ricorsiva al nome della CTE. Da questo momento in poi tutti i result set vengono trattati nello Spooler, la query ricorsiva verrà eseguita di nuovo e potrà utilizzare il nuovo result set presente nello Spooler… e così via…

Avrete sicuramente notato il task di creazione dell’indice temporaneo nel task Index Spool.

L’operatore Assert verifica che il contatore delle iterazioni non superi le 100 iterazioni (default per l’opzione MAXRECURSION), questo operatore è in grado di interrompere l’esecuzione della CTE nel caso in cui il numero delle iterazioni superi il limite fissato dall’opzione MAXRECURSION.

L’operatore Concatenation, esegue il concatenamento unificando i result set di tutte le iterazioni eseguite, il risultato è la tabella virtuale restituita dal Task SELECT.

 

Bonus CTE

Miglioriamo la precedente CTE ricorsiva:

  • Aggiungiamo l’estrazione della colonna quantità materiale sia in formato numerico che in formato grafico
  • Aggiungiamo l’estrazione del livello in formato stringa
  • Presentiamo i dati in modo ordinato, dopo il primo livello della distinta del prodotto finito elenchiamo il primo sottoprodotto e la relativa distinta base, e così via…

— Bonus CTE
with CTE_BillOfMaterials as
(
  — select "àncora" (anchor member)
  select
    h.ProductID
    ,d.ComponentID
    ,d.ProductQty
    ,cast(replicate(‘*’, round(d.ProductQty, 0, 1)) as varchar(max)) as gQty
    ,1 as level
    ,cast(‘1’ as varchar(max)) as str_level
    ,ROW_NUMBER() over(order by (select null)) as r_num
  from
    Production.BillOfMaterialsHeader h
  join
    Production.BillOfMaterialsDetail d
      on d.BillOfMaterialsHeaderID=h.BillOfMaterialsHeaderID
  where
    (h.ProductID=’Mountain Bike’)

  union all

  — select "ricorsiva" (recursive member)
  select
    h.ProductID
    ,d.ComponentID
    ,d.ProductQty
    ,cast(replicate(‘*’, round(d.ProductQty, 0, 1)) as varchar(max)) as gQty
    ,(t.level + 1) as level
    ,cast(t.str_level + ‘ + 1’ as varchar(max)) as str_level
    ,t.r_num
  from
    CTE_BillOfMaterials as t
  join
    Production.BillOfMaterialsHeader h
      on t.ComponentID=h.ProductID
  join
    Production.BillOfMaterialsDetail d
      on d.BillOfMaterialsHeaderID=h.BillOfMaterialsHeaderID
)
— query esterna (outer query)
select
  ProductID
  ,ComponentID
  ,ProductQty
  ,gQty
  ,level
  ,str_level
from
  CTE_BillOfMaterials order by r_num

Ed ecco l’output:

Figura 4 – Esplosione scalare migliorata  della distinta materiali del prodotto Mountain Bike

 

Pulizia DB

/*
  Pulizia DB
*/

if OBJECT_ID(‘Production.BillOfMaterialsDetail’, ‘U’) is not null
  drop table Production.BillOfMaterialsDetail;
go

if OBJECT_ID(‘Production.BillOfMaterialsHeader’) is not null
  drop table Production.BillOfMaterialsHeader;

 

Chi è Sergio Govoni

Sergio Govoni è laureato in Scienze e Tecnologie Informatiche. Da oltre 16 anni lavora presso una software house che produce un noto sistema ERP, distribuito a livello nazionale ed internazionale, multi azienda client/server su piattaforma Win32. Attualmente si occupa di progettazione e analisi funzionale, coordina un team di sviluppo ed è responsabile tecnico di prodotto. Lavora con SQL Server dalla versione 7.0 e si è occupato d'implementazione e manutenzione di database relazionali in ambito gestionale, ottimizzazione delle prestazioni e problem solving. Nello staff di UGISS si dedica alla formazione e alla divulgazione in ambito SQL Server e tecnologie a esso collegate, scrivendo articoli e partecipando come speaker ai workshop e alle iniziative del primo e più importante User Group Italiano sulla tecnologia SQL Server. Ha conseguito la certificazione MCP, MCTS SQL Server. Per il suo contributo nelle comunità tecniche e per la condivisione della propria esperienza con altri, dal 2010 riceve il riconoscimento SQL Server MVP (Microsoft Most Valuable Professional). Nel corso dell'anno 2011 ha contribuito alla scrittura del libro SQL Server MVP Deep Dives Volume 2 (http://www.manning.com/delaney/).

Leggi Anche

Unit testing: Come scrivere la tua prima unit test!

Nell’articolo precedente, il secondo di questa serie, abbiamo descritto come installare il framework tSQLt, il …