Seleccione un par de filas que obedezcan una regla

Question

Tengo una gran tabla (filas 1M) con las siguientes columnas: fuente, dest, distancia. Cada fila define un enlace (de A a B).

Necesito encontrar las distancias entre un par usando un nodo anoter. Un ejemplo: Si desea encontrar la distancia entre A y B, si encuentro un nodo x y tienen: x -> A x -> B puedo añadir estas distancias y tienen la distancia beetween A y B Mi pregunta: ¿Cómo puedo encontrar todos los nodos (como x) y obtener sus distancias a (A y B)? Mi propósito es seleccionar el valor mínimo de distancia.

P.s: A y B son solo una conexión (tengo que hacerlo para conexiones de 100K). Gracias!

Answer 1

Suponiendo que desea obtener la ruta desde A-B con muchos pasos intermedios, es imposible hacerlo en SQL simple durante un número indefinido de pasos. En pocas palabras, carece de poder expresivo, vea http://en.wikipedia.org/wiki/Expressive_power#Expressive_power_in_database_theory. Como dijo Andomar, cargue los datos en un proceso y use el algoritmo de Djikstra.

Answer 2

Esto suena como traveling salesman problem.

Desde el punto de vista de la sintaxis SQL: connect by prior construiría el árbol después de usar el inicio y limitaría el número de capas que puede atravesar; sin embargo, hacer no garantizará el mínimo.

Answer 3

Me puede resultar desfavorable, pero me parece un problema interesante. Deseo que esta sea una discusión más abierta, ya que creo que podría aprender mucho de esto.

Parece que debería ser posible lograr esto haciendo múltiples instrucciones de selección, algo así como SELECT id FROM mytable WHERE source="A" ORDER BY distance ASC LIMIT 1. Envolver algo como esto en un ciclo while, y reemplazar "A" con una variable de id, haría el truco, ¿no?

Por ejemplo (A es la fuente, B es el destino final):

DECLARE var_id as INT 
WHILE var_id != 'B' 
    BEGIN 
    SELECT id INTO var_id FROM mytable WHERE source="A" ORDER BY distance ASC LIMIT 1 
    SELECT var_id 
    END 

¿No sería algo así como este trabajo? (El código es descuidado, pero la idea parece sólida.) Los comentarios son más que bienvenidos.

Answer 4

Únase a la tabla con el destino unido a la fuente. Agrega la distancia desde los dos enlaces. Inserte eso como un nuevo enlace con la fuente del lado izquierdo, el lado derecho del destino y la distancia total si eso no está ya en la tabla. Si eso está en la tabla pero con una distancia total más corta, actualice la fila existente con la distancia más corta.

Repita esto hasta que no se agreguen nuevos enlaces a la tabla y no haya actualizaciones con una distancia más corta. Su tabla ahora contiene un enlace para cada combinación posible de origen y destino con la distancia mínima entre ellos. Sería interesante ver cuántas repeticiones esto tomaría.

Esto no hará un seguimiento de la ruta intermedia entre el origen y el destino, pero solo proporciona la distancia más corta.

Answer 5

Como dijo Andomar, que necesita el algoritmo de Dijkstra, aquí hay un enlace a ese algoritmo en el T-SQL: T-SQL Dijkstra's Algorithm

Answer 6

IIUC esto debería hacer, pero no estoy seguro de si esto es realmente viable (rendimiento -wise), debido a la gran cantidad de filas involucradas y para el CROSS JOIN

SELECT 
    t1.src AS A, 
    t1.dest AS x, 
    t2.dest AS B, 
    t1.distance + t2.distance AS total_distance 
FROM 
    big_table AS t1 
CROSS JOIN 
    big_table AS t2 ON t1.dst = t2.src 
WHERE 
    A = 'insert source (A) here' AND 
    B = 'insert destination (B) here' 
ORDER BY 
    total_distance ASC 
LIMIT 
    1 

el fragmento anterior funcionará para el caso en el que hay dos filas en la forma A-> X y X> B pero no para otras combinaciones (por ejemplo, A-> xy B-> x). Extenderlo para cubrir las cuatro combinaciones debería ser trivial (por ejemplo, crear una vista que duplique cada fila y canjear src y dest).