Consulta SQL para estructura en arbol

[PatrickM]

Hola amigos,

Tengo un problema de SQL que se me resiste. A ver si alguien me puede dar la solución. Tengo una tabla que me representa una estructura en arbol, como un arbol de directorios donde de un elemento le pueden colgar otros. Bien la tabla que tengo definida es como la siguiente:

CREATE TABLE Estructura (
CODIGO INTEGER,
DESCRIPCION VARCHAR(100),
CODIGO_PADRE INTEGER,
NIVEL INTEGER,
PRIMARY KEY(CODIGO)
)

Con esta tabla he conseguido tiempos de carga muy optimos utilizando el concepto de NIVELm y utilizando una sola consulta.

El problema que se me plantea ahora es que quiero saber a partir de un elemento, cual es su padre, su abuelo, su visabuelo, y asi hasta el que llegue al elemento raiz. Esto se puede hacer haciendo una funcion recursiva via codigo Delphi, pero es muy costoso en tiempo, i mas si lo que quiero es hacer para N elementos del arbol.

¿Alguien sabe como hacerlo con una sola consulta??

[[kuan-yiu]]

El problema del acceso óptimo a los árboles de datos tiene años y varias aproximaciones (que no soluciones). Yo lo di en varias asignaturas de la carrera y ahora mismo recuerdo 3 o 4 métodos, pero sólo a nivel teórico. Supongo que si buscas un poco encontrarás mucha documentación, pero yo no confiaría demasiado en encontrar ejemplos prácticos.

[PatrickM]

gracias por tu respuesta. A nivel teorico se que hay aproximaciones al problema, pero me gustaria saber si alguien ha encontrado la solución a mi problema con una sola consulta SQL.

En código delphi lo resolveria con una funcion recursiva, que como mucho se ejecutaria un numero de veces menor o igual a la altura del arbol. Algo similar a esto:

Código Delphi [-]
function DevuelveHerencia(Codigo: integer): integer;
   begin
     If codigo<>-1 Then Begin
       SentenciaSQL;
       GuardarCodigo(Codigo);
       DevuelveHerencia(Codigo_Padre);
     End;
   end;

El problema esta si quiero saber la Herencia de un conjunto de elementos del arbol. Entonces necesitaria ejecutar tantas sentencias SQL como Elementos tubiera, y esto multiplicado por la altura del arbol, es decir un coste N*Altura hablando en llamadas SQL, mientras que yo busco un coste 1.

[[kuan-yiu]]

A nivel teórico es imposible conseguir un coste uno, salvo que puedas leer TODA la estructura del arbol de una sola vez, pero eso crea un problema de manejo de la información en memoria.
Creo recordar cierto método para leer toda una rama, que es lo que creo que tú quieres, pero se apoya en una estructura diferente de la que tienes.

[PatrickM]

Hola kuan-yiu,

Cuando hablo de coste 1 no me refiero a coste de proceso O(1) como el que se habla en la teoria. Me refiero a coste 1 consulta SQL, en vez de N*Altura consultas SQL.

El coste en tiempo mas critico que hay en lanzar una consulta es el tiempo que se tarda entre que el Cliente lanza una consulta y el Servidor devuelve un resultado, por eso el Coste real de proceso no me importa ya que es infimo en comparación al coste de enviar la información por la red.

En temas de memoria el Servidor de Base de Datos tiene toda la información disponible, o sea que tampoco es problema, y tienes toda la estructura del arbol disponible, ya que esta se guarda integramente en una sola tabla de la Base de Datos.

[[kuan-yiu]]

Lo he pensado y no se me ocurre una única consulta en la que puedas conseguirlo todo , pero creo que la recursividad no es la mejor idea en este caso. Me parece que haciendo la consulta dentro de un bucle y utilizando el nivel como condición de ruptura funcionaría mejor que con recursividad.

Lamento no poder ayudarte.

[PatrickM]

Ya, la funcion recursiva en Delphi no es la mejor solución, ya que para cada llamada recursiva estoy haciendo una llamada SQL; pero de momento es la unica solución que he encontrado. Yo creo que la solución pasa por hacer algo recursivo pero en SQL, para que se ejecute dentro del Servidor de Bases de Datos.

A ver si alguien se anima y encuentra una solución.

Gracias de todas formas kuan-yiu.

[hach]

hola,
que base de datos usas?
en Firebird podrias hacer un procedure, que realice una consulta de toda la tabla y recorriendo los datos retornes solo los que te interesan
Como todo el trabajo lo hace el servidor no hay costo de transferencia de datos

la consulta SQl desde delphi seria algo asi como

select * from sp_rama_herencia(nodo_actual)

Saludos, espero que te sirva...

[PatrickM]

Gracias hach, creo que esto podria servir!

Aunque se me complica un poco el tema, ya que la aplicación usa tanto una Base de Datos Oracle como un SQL Server; es configurable externamente. Ya hago algunos cambios en los SQL antes de mandarlos a la BD para tener en cuenta los cambios en la sintaxis, pero aquí creo que seran muchos mas.

[hach]

no creo que tengas problemas, creo que ambas bases soportan procedures
La llamada desde delphi posiblemente cambie, y tal vez la sintaxis del procedure, pero deberias poder

[xander]

Definitivamente unProcedimiento Almacenado es lo que necesitas, solo recuerda hacer indices por los campos CODIGO y CODIGO_PADRE para optimizar el acceso a cada nodo, yo lo tengo hecho así para una aplicación con un arbol enorme (varios cientos de miles de registros) y todo funciona a la perfección.

Tambien claro que al mostrar el arbol en un TTreeView no se cargan todos los datos de golpe sino que los voy cargando por "Niveles" y por "Padre Comun" asi solo se traen de la BD los registros que se van solicitando.