![]() |
stored procedures esempi |
espansione di gerarchie
spesso i db memorizzano informazioni gerarchiche
padre figlio
------------------ --------------------
Mondo Europa
Mondo Nord America
Europa Francia
Francia Parigi
Nord America Stati Uniti
Nord America Canada
Stati Uniti New York
Stati Uniti Washington
New York New York City
Washington Redmond
la procedura che segue espande un gerarchia di profondit� arbitraria
espansione di reti
alcune volte i db memorizzano informazioni reticolari
partenza destinazione
------------------ --------------------
Chicago New York
Chicago Milwaukee
Denver Chicago
Seattle Chicago
Seattle Denver
Seattle San Francisco
quando il livello > 0, la procedura esegue i seguenti passi:
se la tabella voli contiene anche i costi, si pu� trovare l'itinerario meno costoso
salvando l'itinerario corrente se il suo costo totale � inferiore all'attuale costo migliore:
ecco un esempio di una gerarchia geografica: ogni voce ha un solo superiore
tabella geografia
ma la struttura � chiara solo cos�:
Mondo
Europa
Francia
Parigi
Nord America
Canada
Stati Uniti
Washington
Redmon
New York
New York City
(sebbene si possa usare la recursione, � pi� efficiente usare una tabella temporanea con funzioni di stack)
create proc espandi (@current char(20)) as
set nocount on
declare @level int, @line char(20)
create table #stack (item char(20), level int)
insert into #stack values (@current, 1)
select @level = 1
while @level > 0
begin
if exists (select * from #stack where level = @level)
begin
select @current = item from stack
where level = @level
select @line = space(@level -1) + @current
print @line
delete from #stack
where level = @level and item = @current
insert #stack
select figlio, @level + 1 from geografia
where padre = @current
if @@rowcount > 0 select @level = @level + 1
end
else
select @level = @level -1
end
ecco un esempio di una rete geografica in cui ogni voce pu� avere pi� di un superiore:
tabella voli
si vogliano trovare tutti gli itinerari tra due citt� date:
Itinerari
---------------------------------------
Seattle, Chicago, New York
Seattle, Denver, Chicago, New York
con pochi cambiamenti alla procedura per l'espansione di una gerarchia
si pu� risolvere il problema:
create proc espandi2 (@current char(20), @dest char(20), @maxlevel int = 5) as
set nocount on
declare @level int
create table #stack (city char(20), level int)
create table #list (city char(20), level int)
insert into #stack values (@current, 1)
select @level = 1
while @level > 0
begin
if exists (select * from #stack where level = @level)
begin
select @current = city from stack
where level = @level
delete from #stack
where level = @level and item = @current
delete from #list
where level >= @level
if exists (select * from #list where city = @current)
continue
insert into #list values (@current, @level)
if (@current = @dest)
begin
select itinerario = city from #list
continue
end
insert #stack
select destinazione, @level + 1 from voli
where partenza = @current and @level < @maxlevel
if @@rowcount > 0 select @level = @level + 1
end
else
select @level = @level -1
end
l'istruzione IF EXISTS all'inizio del ciclo salta la citt� corrente se � gi� presente nell'itinerario corrente
select @cost = sum(cost) from #list
if @cost < @lower_cost
begin
@lower_cost = @cost
truncate table #best_route
insert #best_route
select * from #list
end
per aumentare ancora l'efficienza, si pu� troncare l'espansione
se il costo attuale supera il costo migliore:
if (select sum(cost) form #list) > @lower_cost
continue
infine, se la tabella voli contiene anche l'orario di partenza e quello di arrivo,
si possono espandere solo i percorsi che hanno l'orario di partenza almeno un'ora dopo l'ora di arrivo:
if ((select sum(cost) from #list) > @lower_cost)
and datediff(hh, dep_time, @arr_time) > 1)
continue