Home > Articoli > Recursive CTEs and Bill Of Materials problem (part two: cyclic references)

Recursive CTEs and Bill Of Materials problem (part two: cyclic references)

Nel precedente post Recursive CTE and Bill Of Materials problem abbiamo descritto una CTE ricorsiva nel tentativo di risolvere un problema del mondo reale, ovvero l’esplosione scalare a tutti i livelli della distinta materiali di un prodotto fornito in input.

Prima di realizzare la CTE ricorsiva CTE_BillOfMaterials abbiamo ipotizzato che le distinte materiali memorizzate nelle tabelle Production.BillOfMaterialsHeader e Production.BillOfMaterialsDetail avessero tutte una struttura ad albero aciclica (come è nella realtà). Alcune volte, le ipotesti più credibili non vengono verificate sui dati in produzione, ed è stato così, si è semplicemente assunto che l’ipotesi fosse vera. Durante il deploy della CTE, però, ci siamo accorti che questa ipotesi non era verificata per tutte le distinte memorizzate. Accadeva, di tanto in tanto, che gli utenti lamentassero un errore durante il tentativo di esplodere la distinta di un prodotto. Il seguente errore, che si verificava solo per alcuni prodotti, poteva essere il sintomo di un problema nei dati:

Messaggio 530, livello 16, stato 1, riga 1
Istruzione interrotta. Numero massimo di ricorsioni 100 esaurito prima del completamento dell’istruzione.

Durante l’esecuzione veniva raggiunto il numero massimo di ricorsioni previsto, by default, prima del completamento dell’istruzione. Questo accadeva perché nella distinta materiali di un sotto insieme era presente il riferimento di un prodotto di livello superiore per lo stesso ramo.

In alcuni scenari avere riferimenti ciclici è naturale, pensiamo ad esempio al sistema di strade che collega due città, ma se rileviamo un riferimento ciclico in una struttura che abbiamo ipotizzato essere aciclica, allora questo potrebbe indicare un problema nei dati.

Simuliamo il problema, utilizziamo il seguente frammento di codice T-SQL per creare 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] );

I seguenti comandi di INSERT permetto di allestire la distinta materiali (semplificata) del prodotto “Mountain Bike”.

insert into Production.BillOfMaterialsHeader
(StartDate, EndDate, ProductID)
values
(GETDATE(), null, ‘Mountain Bike’),
(GETDATE(), null, ‘Gruppo Ruote’),
(GETDATE(), null, ‘Gruppo Luci’),
(GETDATE(), null, ‘Luci Anteriori’),
(GETDATE(), null, ‘Supporto Luci-A’);
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’)),
   ‘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 Luci’,
   1
),
(
  (select
     bh.BillOfMaterialsHeaderID
   from
     Production.BillOfMaterialsHeader bh
   where
     (bh.ProductID = ‘Gruppo Luci’)),
   ‘Luci Anteriori’,
   1
),
(
  (select
     bh.BillOfMaterialsHeaderID
   from
     Production.BillOfMaterialsHeader bh
   where
     (bh.ProductID = ‘Luci Anteriori’)),
   ‘Supporto Luci-A’,
   1
),
(
  (select
     bh.BillOfMaterialsHeaderID
   from
     Production.BillOfMaterialsHeader bh
   where
     (bh.ProductID = ‘Supporto Luci-A’)),
   ‘Staffa in ferro’,
   1
),
(
  (select
     bh.BillOfMaterialsHeaderID
   from
     Production.BillOfMaterialsHeader bh
   where
     (bh.ProductID = ‘Luci Anteriori’)),
   ‘Lampadina 12V’,
   1
),
(
  (select
     bh.BillOfMaterialsHeaderID
   from
     Production.BillOfMaterialsHeader bh
   where
     (bh.ProductID = ‘Luci Anteriori’)),
   ‘Lampadina 24V’,
   1
);

Consultiamo i dati inseriti:

select * from Production.BillOfMaterialsHeader;

select * from Production.BillOfMaterialsDetail;

Figura 1 – Dati inseriti nelle tabelle Production.BillOfMaterialsHeader e Production.BillOfMaterialsDetail

Generiamo ora un riferimento ciclico: nella distinta materiali del sotto insieme "Supporto Luci-A" viene inserito il riferimento al sotto insieme "Gruppo Luci" già presente ad un livello superiore nello stesso ramo di distinta.

insert into Production.BillOfMaterialsDetail
(
  BillOfMaterialsHeaderID,
  ComponentID,
  ProductQty
)
values
(
  (select
     bh.BillOfMaterialsHeaderID
   from
     Production.BillOfMaterialsHeader bh
   where
     (bh.ProductID = ‘Supporto Luci-A’)),
   ‘Gruppo Luci’,
   1
);

L’esecuzione della seguente CTE ricorsiva viene interrotta perché raggiunge il massimo numero di iterazioni previsto by default (100).

declare @ProductID as varchar(20) = ‘Mountain Bike’;

with CTE_BillOfMaterials as
(
  — select "àncora" (anchor member)
  select
    h.ProductID
    ,d.ComponentID
    ,d.ProductQty
    ,1 as level
    — path of root
    ,CAST(‘.’ + CAST(ltrim(rtrim(h.ProductID)) as varchar(20)) + ‘.’ as varchar(max)) as path
    — sort path
    ,CAST(1 as varbinary(max)) + cast(ROW_NUMBER() over(order by (select null)) as binary(4)) as sort_path
  from
    Production.BillOfMaterialsHeader h
  join
    Production.BillOfMaterialsDetail d
      on d.BillOfMaterialsHeaderID=h.BillOfMaterialsHeaderID
  where
    (h.ProductID = @ProductID)

  union all

  — select "ricorsiva" (recursive member)
  select
    h.ProductID
    ,d.ComponentID
    ,CAST((t.ProductQty * d.ProductQty) as decimal(8, 2)) as ProductQty
    ,(t.level + 1) as level
    — path of child
    ,CAST(t.path + CAST(ltrim(rtrim(h.ProductID)) as varchar(20)) + ‘.’ as varchar(max)) as path
    — sort path
    ,t.sort_path + CAST(ROW_NUMBER() over(partition by h.ProductID order by d.ComponentID) as BINARY(4)) as sort_path
  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
  qe.ProductID
  ,qe.ComponentID
  ,qe.ProductQty
  ,qe.level
  ,qe.path
  ,REPLICATE(‘ | ‘, level) + qe.ComponentID
  ,ROW_NUMBER() over(order by sort_path) as sortval
from
  CTE_BillOfMaterials qe
order by
  sortval

Questo l’errore restituito:

Figura 2 – Messaggio di errore 530

Individuare i riferimenti ciclici con T-SQL può essere complesso e costoso in termini computazionali. Di seguito, modificheremo la precedente CTE ricorsiva in modo da renderla capace di individuare riferimenti ciclici con prestazioni ragionevoli. L’idea di base, dopo aver costruito il path di ogni ramo esaminato, è quella di verificare se il sotto insieme che si sta elaborando è già presente all’interno del path (da cui deriva). La colonna cycle terrà traccia di questa situazione, il valore zero indicherà che il sotto insieme non è già stato aggiunto al path precedentemente, il valore uno identificherà invece il riferimento ricorsivo.

Nella SELECT “àncora” che estrae il primo livello della distinta, la colonna cycle assumerà sempre il valore zero per tutte le righe. Nella SELECT “ricorsiva” utilizzeremo il predicato LIKE per verificare che il codice del sotto insieme che si sta elaborando non sia già presente nel path (composto con il codice dei sotto insiemi a livello superiore). Nel caso sia presente, la colonna cycle riporterà il valore uno. In aggiunta, per evitare che la CTE entri in un loop senza fine (motivo dell’errore) aggiungiamo un filtro in modo che vengano restituiti solo i sotto insiemi nel cui livello padre la colonna cycle ha valore zero.

Riportiamo di seguito la CTE CTE_BillOfMaterials modificata:

declare @ProductID as varchar(20) = ‘Mountain Bike’;

with CTE_BillOfMaterials as
(
  — select "àncora" (anchor member)
  select
    h.ProductID
    ,d.ComponentID
    ,d.ProductQty
    ,1 as level
    — path of root
    ,CAST(‘.’ + CAST(ltrim(rtrim(h.ProductID)) as varchar(20)) + ‘.’ as varchar(max)) as path
    — sort path
    ,CAST(1 as varbinary(max)) + cast(ROW_NUMBER() over(order by (select null)) as binary(4)) as sort_path
    ,0 as cycle
  from
    Production.BillOfMaterialsHeader h
  join
    Production.BillOfMaterialsDetail d
      on d.BillOfMaterialsHeaderID=h.BillOfMaterialsHeaderID
  where
    (h.ProductID = @ProductID)

  union all

  — select "ricorsiva" (recursive member)
  select
    h.ProductID
    ,d.ComponentID
    ,CAST((t.ProductQty * d.ProductQty) as decimal(8, 2)) as ProductQty
    ,(t.level + 1) as level
    — path of child
    ,CAST(t.path + CAST(ltrim(rtrim(h.ProductID)) as varchar(20)) + ‘.’ as varchar(max)) as path
    — sort path
    ,t.sort_path + CAST(ROW_NUMBER() over(partition by h.ProductID order by d.ComponentID) as BINARY(4)) as sort_path
    ,(case when t.path like ‘%.’ + CAST(ltrim(rtrim(d.ComponentID)) as varchar(20)) + ‘.%’
      then 1
      else 0
      end) as cycle

  from
    CTE_BillOfMaterials as t
  join
    Production.BillOfMaterialsHeader h
      on t.ComponentID=h.ProductID
      — filtriamo la select ricorsiva in modo che restituisca i figli
      — solo se il campo cycle del padre è uguale a zero (false)
      and (t.cycle = 0)

  join
    Production.BillOfMaterialsDetail d
      on d.BillOfMaterialsHeaderID=h.BillOfMaterialsHeaderID
)
— query esterna (outer query)
select
  qe.ProductID
  ,qe.ComponentID
  ,qe.ProductQty
  ,qe.cycle
  ,qe.level
  ,qe.path
  ,REPLICATE(‘ | ‘, level) + qe.ComponentID
  ,ROW_NUMBER() over(order by sort_path) as sortval
from
  CTE_BillOfMaterials qe
order by
  sortval

I riferimenti ciclici posso essere facilmente identificati come illustrato nella figura seguente:

Figura 3 – Identificazione riferimenti ciclici

 

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 …