Cita:
Empezado por mamcx
Efectivamente uso Dijkstra. No tengo problema en saber la ruta minima.
MI problema es como extraigo un subconjunto del grafo total que representa todas las relaciones de las tablas en la BD a uno mas pequeño que solo contenga las que se seleccionaron y las que hacen falta para conectar esas tablas entre si.
Si tengo una tabla cliente, encabezado y detalle de factura, y selecciono a detalle y cliente, quiero que devuelva a las 3, porque encabezado es indispensable para relacionar a cliente y detalle.
|
Hola Mamx,
Le he estado dando vuelta a esto, y debe ser algo que no termino de comprender.
Yo apliqué un algoritmo sencillo, un Dikjstra disponible en
Wikipedia y con él obtengo no sólo la ruta mínima sino que además se queda guardado en vector de punteros aquel conjunto de nodos que garantiza la ruta mínima.
Lo hice a mano, con el DER de la DB de ejemplo que viene en Firebird.
la estructura es como sigue:
Código:
+---+ +---+
| 1 |---------------<| 2 |
+---+ +---+
| Y
| +---+ +---+ |
+---<| 3 |---<| 4 | |
+---+ +---+ |
V |
| +---+ +---+
+--| 5 |---<| 6 |
+---+ +---+
L \
/ A
+---+ +---+
| 7 | | 8 |
+---+ +---+
| Y
A |
+---+ +---+
| 9 |>--------| 10|
+---+ +---+
El lado del muchos es aquel que tenga un <, >, A, L, Y.
1. Ciudad
2. Trabajos
3. Clientes
4. Ventas
5. Empleados
6. HistorialSalario
7. Depto
8. AsignacionesProyecto
9. PresupuestoDepartamental
10. Proyecto
El grafo es análogo, simplemente borrares el muchos y tenemos uno.
¿Cual es problema? Los pesos. Por ejemplo si asumimos un valor uniforme a todos, es posble que obtengamos una ruta no muy deseada.
Por ejemplo, digamos que tu buscas la relación entre 4 (Ventas) y (Proyecto). Hay dos caminos posibles, pero el algoritmo te encuentra uno.
Si el costo es 1 para todos, obtendrás esta salida:
D={2,2,1,0,1,2,2,2,3,3}
P={3,5,4,4,4,5,5,5,7,8}
C={/,/,/,/,/,/,/,/,/,/,10} /significa quitado de lista
En la lista P se obtiene en forma inversa, las tablas que intervienen.
P(z), que representa a la tabla destino (z = 10), apunta a 8.
P(8), apunta a 5.
P(5), apunta 4. La inicial.
Entonces intervienen: Proyecto, AsignacionesProyecto, Empleado, Ventas.
Haciendo analogía con lo que tu pides y buscando la manera de interpretar adecuadamente ese "indispensable para relacionar" que tu mencionas puedo llegar a la conclusión de que no necesariamente la ruta más corta te llevará por aquellas relaciones que tu consideras necesarias.
Por ejemplo, haz de cuenta que la tabla 10 es tu Detalle y que la 9 es el Encabezado (se que en el ejemplo no da pero mantengamos el supuesto).
Se ve por la forma de las relaciones que el algoritmo (con estos pesos) prefiere irse por otro lado.
El tema es que mientras exista más de una posibilidad a una tabla no se puede garantizar de que el camino tocará alguna de potencial interés para obtener algo coherente a lo que buscamos.
Volviendo al caso del ejemplo que yo hice: ¿Tiene alguna utilidad haber relacionado las ventas con los empleados, y los proyectos a los cuales fue asignado el empleado?
Puede que si... puede que no... ¿realmente se quería eso? O por el contrario ¿Andaba buscando otra relación?
Y como dije, esto sucede por tener el mismo peso. ¿Que hubiera pasado si la relación entre asignaciones y proyectos tuviera un valor más alto? Por ejemplo 3. El algoritmo hubiera preferido irse por la otra rama.
Y si nos volvemos a aquel supuesto... entonces ahora si fue por un lugar adecuado.
A lo que voy, es que mientras exista más relaciones entre las tablas y exista cierta uniformidad en los pesos no se puede garantizar que pasará por algún punto que realmente sea de interés.
La solución que yo estoy analizando es favorecer con un peso bajo a las relaciones de "amistad" entre las tablas y penar con un valor alto a las tablas que no tienen tanta afinididad. Esto también dependerá también del verdadero y potencial uso que le atribuya el cliente.
¿A que podemos entender afinidad? Pues existe mayor afinidad entre la tablas Encabezados con sus respectivos Detalles que con una tabla a la que actua de esclava.
Por ejemplo es posible que la relación entre Ventas y Empleado tenga un valor bajo mientras que entre Empleado y Asignaciones un valor alto. Cabe la posibilidad de que el cliente le resulta más útil un cubo formado por los datos entre las ventas por Empleado que saber las asignaciones por empleado.
Bueno, eso es lo que mi cansado cerebro está pensando.
Es muy posible de que lo que acabo de decir no sea útil, siento que algo se me está escapando, que algo no estoy comprendiendo
.
No se que tan útil te puedo estar siendo.
Saludos,