SQL - Consulta SQL compleja

Estimados Amigos,

Tal vez no sea un asunto de la consulta SQL como tal, sino del modelo de base de datos que tengo planteado. Si ven una mejor forma de hacer lo que hago, gustoso estaré de aceptar sus sugerencias.

El asunto es que, dadas 2 ciudades, debo encontrar la ruta o las rutas que las unen. Es una aplicación Web desarrolada en ASP y por el momento, utilizo una base de datos Access, aunque la idea es migrar a SQL Server.

Tengo una tabla de ciudades, donde, obviamente, almaceno cada ciudad con su código.

codigo Descripción
50 Maracaibo
51 Ciudad Ojeda
53 Barquisimeto
54 Carora
55 Quibor
56 San Felipe
59 Nirgua
61 Valencia
62 Morón
64 Maracay
66 Pto. Cabello
67 Pto. Fijo
68 Coro
69 San Cristobal
71 San Antonio
72 Caracas
75 Villa Del Rosario
76 Machiques
77 Cabimas
78 Lagunillas
79 Rio de Janeiro
80 Salvador
81 Tia Juana
82 Santa Rita
83 El Venado
84 Bachaquero
85 Bejuma
86 Chivacoa
87 Yaritagua
88 La Manzanita

Otra tabla, a la que llamo PRÓXIMA con tiene las ciudades próximas a una ciudad dada. Es decir, las que conectan directamente con un tramo de carretera.

cod origen destino distancia tipo de via
1 50 75 80 B
2 50 77 30 B
3 51 77 15 B
4 51 78 10 B
5 53 54 100 A
6 53 55 30 B
7 53 59 120 B
8 54 53 100 A
9 54 55 75 B
10 54 78 110 B
11 59 53 120 B
12 59 61 80 B
13 61 59 80 B
14 61 62 40 B
15 61 64 60 A
16 64 61 60 A
17 64 72 60 A
18 72 64 60 A
19 77 50 30 B
20 77 51 15 B
21 78 51 10 B
22 54 83 80 A
23 83 50 100 A
24 51 88 30 A
25 88 50 22 A

Con la finalidad de poder realizar pruebas con esta data he elegido como origen la ciudad 53 (Barquisimeto) y como destino, la ciudad 50 (Maracaibo)

Entre esta 2 ciudades hay 3 rutas

Ruta 1 : 53 - 54 -83 -50

Ruta 2 : 53 - 54 - 78 - 51 - 77 - 50

Ruta 3 : 53 - 54 -78 - 51 - 88 - 50

Ahora bien, luego de plantear el problema, voy a realizar las preguntas:

¿Es posible realizar consultas SQL que permitan hallar los tramos (union entre una y otra ciudad) que concatenados me den la ruta entre el origen y el destino?

Veamos lo siguiente:

select * from proxima where origen = 53 and destino = 50

Traería la ruta directa (si existe) entre el origen y el destino. Eso aplica para ciudades "proximas" una de la otra.

Pero si la ciudad destino es proxima de una proxima al origen..

¿Cual sería la sentencia SQL?

Tengo esta, en la cual uso ciudades que están separadas por una sola ciudad, en este caso 78 y 77 (que están separadas por la 51, como pueden ver en la ruta 2):

select * from proxima where cod_poblacion_origen = 78 and cod_poblacion_destino in (select cod_poblacion_origen from proxima where cod_poblacion_destino = 77) union
select * from proxima where cod_poblacion_destino = 77 and cod_poblacion_origen in (select cod_poblacion_destino from proxima where cod_poblacion_origen = 78)

y si la ciudad destino es proxima de una proxima de una proxima al origen?

Logré hacer este SQL:

select * from proxima where cod_poblacion_origen = 78 and cod_poblacion_destino in (select cod_poblacion_origen from proxima where cod_poblacion_destino in (select cod_poblacion_origen from proxima where cod_poblacion_destino = 50))
union all
select * from proxima where cod_poblacion_origen in (select cod_poblacion_destino from proxima where cod_poblacion_origen = 78 and cod_poblacion_destino in (select cod_poblacion_origen from proxima where cod_poblacion_destino in (select cod_poblacion_origen from proxima where cod_poblacion_destino = 50))) and
cod_poblacion_destino in (select cod_poblacion_origen from proxima where cod_poblacion_destino = 50 and cod_poblacion_origen in (select cod_poblacion_destino from proxima where cod_poblacion_origen in (select cod_poblacion_destino from proxima where cod_poblacion_origen = 78)))
union all
select * from proxima where cod_poblacion_destino = 50 and cod_poblacion_origen in (select cod_poblacion_destino from proxima where cod_poblacion_origen in (select cod_poblacion_destino from proxima where cod_poblacion_origen = 78))

Suponiendo que estos SQL que hice logren resolver el problema de los 3 primeros casos (rutas directas, separadas por 1 ciudad y separadas por 2 ciudades) estoy seguro que luego la cosa se va a complicar a un extremos que no podré manejar. En Venezuela existen ciudades que están separadas una de otra por 20 ciudades y ni siquiera quiero imaginar el SQL que tendré que hacer.

El esquema de ciudades y próximas se me ocurrió como una forma de resolver este problema, sin embargo, sinceramente me parece que tal vez deba manejar otro tipo de estructura de base de datos.

Otra idea que se me ocurrió es crear una tabla de "rutas", que tocan varias ciudades, pero no se como manejarlo adecuadamente.

Saludos y mil gracias de antemano por la ayuda que puedan prestarme.

Luis Vásquez

Una BD relacional no es lo mejor para solucionar esos problemas.
Yo no intentaría hacer nada parecido en SQL, si lo consiguieras sería lentísimo y muy caro en recursos de la máquina.
Hazlo por programa, te ahorrarás dolores de cabeza.

Hola Luis,
Desde ayer estoy dando vueltas a este problema, y lo que voy a proponerte anda bien con los datos que mandaste, habría que hacer pruebas con más información, para controlar no solo que devuelva las rutas correctas, sino además los tiempos de ejecución.
Espero que te sirva y que disfrutes tratando de entenderlo, tanto como yo al lograrlo.

DECLARE @Origen char(2), @Destino char(2)
SELECT @Origen = '53', @Destino = '50'

SELECT Ruta = CONVERT(VARCHAR(8000), Origen + Destino)
INTO #Tra1
FROM #Proxima

-- Arma cadena de ciudades de destino hasta que se termina la ruta
WHILE ( SELECT @@ROWCOUNT ) > 0
BEGIN
UPDATE #Tra1
SET Ruta = CASE WHEN CHARINDEX ( Destino , Ruta) = 0 -- que no repita ciudades en la cadena
THEN Ruta + Destino ELSE Ruta END
FROM #Proxima
WHERE RIGHT ( Ruta, 2) = Origen
AND CHARINDEX ( Destino , Ruta) = 0 -- que no repita ciudades en la cadena
END

SELECT @Origen = @Origen

-- Arma cadena de ciudades de origen hasta que se termina la ruta
WHILE ( SELECT @@ROWCOUNT ) > 0
BEGIN
UPDATE #Tra1
SET Ruta = CASE WHEN CHARINDEX ( Origen , Ruta) = 0 -- que no repita ciudades en la cadena
THEN Origen + Ruta ELSE Ruta END
FROM #Proxima
WHERE LEFT ( Ruta, 2) = Destino
AND CHARINDEX ( Origen , Ruta) = 0 -- que no repita ciudades en la cadena
END

SELECT DISTINCT
SUBSTRING ( Ruta, CHARINDEX ( @Origen , Ruta), CHARINDEX ( @Destino, Ruta) + 2 - CHARINDEX ( @Origen, Ruta))
FROM #Tra1

WHERE CHARINDEX ( @Origen , Ruta) > 0 AND
CHARINDEX ( @Destino, Ruta) > 0 AND
CHARINDEX ( @Origen, Ruta) < CHARINDEX ( @Destino, Ruta)
order by 1