Eladio Rincón

CTEs recursivas en SQL Server 2005

Seguramente ya has oído hablar de las CTEs (o expresiones de tablas comunes) recursivas en SQL Server 2005.

El ejemplo típico del que habrás oído hablar será de la típica relación Empleado – Jefe, ¿verdad?

Vamos a ver un caso diferente, porque seguramente ya estarás aburrido de ese ejemplo 

Acostumbrados a pasar demasiado tiempo en los aeropuertos, y además, de algún modo descontento con las aplicaciones web a través de las cuales compramos nuestros vuelos, me llegó a la idea de los grafos que me hicieron volver a los viejos tiempos en las clases de Matemática Discreta.

Bueno, al tema; veamos el siguiente ejemplo, dada la siguiente tabla:

if exists (select * from sys.tables where name = 'routes')
drop table dbo.routes

go

create table dbo.routes (
origin char(3)
, destination char(3)
, price money)

En la que:

• origin representa el origen del vuelo,
• destination, representa el destino del vuelo,
• y, price, el precio del vuelo.

Y dadas las siguientes combinaciones de vuelos:

insert dbo.routes select 'ALC', 'MAD', 100
insert dbo.routes select 'ALC', 'ROM', 1200
insert dbo.routes select 'ALC', 'BCN', 250
insert dbo.routes select 'MAD', 'ALC', 100
insert dbo.routes select 'MAD', 'BCN', 75
insert dbo.routes select 'BCN', 'MAD', 75
insert dbo.routes select 'MAD', 'ROM', 750
insert dbo.routes select 'ROM', 'ALC', 1200
insert dbo.routes select 'BCN', 'ROM', 400
insert dbo.routes select 'MAD', 'TEF', 1300
insert dbo.routes select 'TEF', 'ROM', 1500

Donde podemos ver por ejemplo, que el vuelo de ALC, a MAD vale 100€, el vuelo de ALC a ROM vale 1200, y así sucesivamente.

Si quisiéramos buscar todos los vuelos cuyo origen tienen ALC, y su destino es ROM, podríamos aplicar la siguiente consulta:

select *
from dbo.routes

where
origin = 'ALC' and destination = 'ROM'

Que nos devolvería:

origin destination price
------ ----------- ---------
ALC ROM 1200.00

En realidad, esta consulta devolverá vuelos "directos" entre Alicante (ALC) y Roma (ROM), pero ¿qué pasa con las escalas? Porque en la lista anterior, para ir de Alicante a Roma, podríamos elegir las siguientes combinaciones de vuelos:

ALC-ROM
ALC-BCN-ROM
ALC-MAD-ROM
ALC-MAD-BCN-ROM
ALC-BCN-MAD-ROM
ALC-MAD-TEF-ROM
ALC-BCN-MAD-TEF-ROM

Es decir, las combinaciones serían: un vuelo directo, dos vuelos con una escala (pasando por BCN, o MAD), tres vuelos con dos escalas, y un "estratosférico" Alicante – Barcelona – Madrid – Tenerife – Roma, con cuatro escalas 

Pensemos un poco cómo debería funcionar una búsqueda de todos los trayectos cuyo origen es ALC, y su destino es ROM.

Para ello:

• Se localizan todos los vuelos cuyo origen es ALC.
• De todos los resultados de 1), para todos los vuelos existentes (toda la tabla) se buscan vuelos cuyo origen es el destino de la lista 1), y además, el destino no esté en alguno de los tramos anteriores – en otras palabras, evitar pasar dos veces por el mismo aeropuerto
• Así iterativamente, dejando de buscar cuando:
  • se hallan procesado todos los vuelos existentes.
  • O, se haya llegado al destino final que es ROM.

Y ¿cómo lo hacemos con TSQL? Para ello aparece el concepto de CTEs Recursivas de las que podéis ver una introducción aquí (http://technet.microsoft.com/es-es/library/ms186243.aspx) –si eres nuevo con las CTEs Recursiva, por favor, lee la URL anterior.

Vamos a empezar con la siguiente sentencia:

--
-- declaración de variables
--

DECLARE @origin CHAR(3)
DECLARE @destination CHAR(3)
DECLARE @stops INT

SET @origin = 'ALC'
SET @destination = 'ROM'

;WITH paths AS (
--
-- punto de entrada
--

SELECT origin, destination, price
, cast (origin + '-' + destination as varchar(200)) as [route]
, 1 as stops

FROM dbo.routes
WHERE origin = @origin

UNION ALL
--
-- elemento de recursión
--

SELECT M.origin, t.destination, t.price + M.price
, cast (M.[route] + '-' + t.destination as varchar(200))
, M.stops + 1

FROM dbo.routes AS t
JOIN paths AS M
ON t.origin = M.destination

WHERE M.[route] NOT LIKE '%-' + t.destination + '-%'
AND M.[route] NOT LIKE t.destination + '-%'
AND M.[route] NOT LIKE '%-' + t.destination

)
SELECT * FROM paths
WHERE destination = @destination
ORDER BY price ASC

Que devolverá los siguientes resultados:

Curiosidades:

• Los cálculos se codifican en los elementos de recursión (en la parte SELECT):
  • t.price + M.price, para incrementar en cada tramo el importe.
  • M.stops + 1, para llevar "registro" del número de escalas.
• La condición de ruptura de la recursión se implementa en el elemento de recursión:
  • WHERE M.[route] NOT LIKE '%-' + t.destination + '-%'
    AND M.[route] NOT LIKE t.destination + '-%'
    AND M.[route] NOT LIKE '%-' + t.destination
    • Es decir, cuando el trayecto (route), no tenga como destino, algún aeropuerto por el que ya haya pasado.
    • Nota: con el predicado WHERE M.[route] NOT LIKE '%' + t.destination + '%' sin guiones en los comodines, debería funcionar, pero no estoy seguro que no haya códigos de aeropuertos que sean subconjunto de otro, por ejemplo AL, y ALC, MA, y MAD, etc.
• Si quieres filtrar por número de escalas:
  • Se puede establecer el filtro dentro del "elemento de recursión".
  • O en la consulta externa (el alias paths).

Nota: juega con el predicado en ambos sitios, y fíjate que el predicado en el elemento de recursión debe ser una unidad mayor que en la consulta externa para que ambas opciones devuelvan los mismos resultados.