PDF de programación - Una propuesta para el manejo de recursión en SQL

Imágen de pdf Una propuesta para el manejo de recursión en SQL

Una propuesta para el manejo de recursión en SQLgráfica de visualizaciones

Publicado el 30 de Mayo del 2018
274 visualizaciones desde el 30 de Mayo del 2018
269,1 KB
7 paginas
Creado hace 12a (30/01/2008)
Una propuesta para el
manejo de recursión en SQL

RESUMEN

En este artículo se propone un método para
la concepción de consultas recursivas en SQL
(Structured Query Language). Este método
constituye una alternativa que puede ser consi-
derada tanto desde el punto de vista de la
optimización de consultas como de Sistemas
de Gestión de Bases de Datos que no dispo-
nen de operadores especializados para sopor-
tar tales tipos de consultas.

Palabras clave: árboles, consultas recursivas,
jerarquías, lenguajes de consulta, SQL,
recursión.

A proposal to the treatment of
recursion in SQL

ABSTRACT

In this article an alternative method is
proposed in order to pose recursive queries in
SQL (Structured Query Language). This method
is an alternative that can be considered from the
point of view of query optimization as well as
Database Management Systems that do not have
specialized operators for such types of queries.

Key words: trees, recursive queries,
hierarchies, query languages, SQL, recursion.

1.

INTRODUCCIÓN

Desde 1996 con la inclusión de la opción
procedimental o PSM (Persistent Stored Modu-
les) al SQL [1] éste se vuelve computacionalmente
completo, gracias a las estructuras clásicas de pro-
gramación: secuencia, decisión e iteración. Se pue-
de distinguir entre el SQL “puro” y el SQL +
PSM. Los PSM se han incorporado en diversos
Sistemas de Gestión de Bases de Datos (SGBD).
En Oracle por ejemplo la opción procedimental
se llama PL/SQL y en SQL Server TSQL.

Con la incorporación de la opción
procedimental es posible resolver prácticamente
cualquier consulta por medio de SQL debido

a que las funciones, que se programan en PSM,
pueden ser invocadas desde las consultas. Es-
tas funciones pueden ser tan complejas como
se requiera, incluso pueden ser recursivas. Por
otro lado el aspecto de la optimización de con-
sultas en los SGBDs es un problema priorita-
rio y en constante investigación.

Aunque la recursión es una técnica poderosa
para dar solución a determinados problemas
tiene como contraparte su enorme costo
computacional. Varios SGBDs poseen opera-
dores especializados para lograr la recursión en
SQL puro, por ejemplo en Oracle, CONNECT
BY [2] y en DB2 WITH [3] (véase la Sección 3).
Con el mismo fin, desde el SQL estándar 1999
[4] se ha adicionado un operador [5], con el
mismo nombre que en DB2; aunque la versión
de este operador en DB2 no posee todas las
características que establece el SQL estándar [3].
Por otro lado, Libkin [6] demuestra que existen
consultas recursivas que definitivamente no pue-
den ser expresadas mediante el SQL estándar
anterior al SQL-99 y realiza un análisis sobre la
expresividad de SQL.

Date [7] propone un operador EXPLODE el
cual puede ser incorporado en un lenguaje
relacional de consulta para solucionar consultas
tipo “explosión de partes” (véase la Sección 2).
Agrawal [8] propone extender el álgebra relacional
con un operador recursivo denominado
ALPHA, Ahad [9] propone un lenguaje espe-
cializado basado en álgebra relacional denomi-
nado RQL (Recursive Query Language) y Shan
[10] propone extender el álgebra relacional me-
diante un operador FIXPOINT para soportar
consultas recursivas.

Linnemann [11] aborda el problema de con-
sultas recursivas pero para relaciones que no
están en primera forma normal (relaciones que
en la intersección de una fila y columna pue-
den tener múltiples valores).

Tillquist [12] propone los operadores
TCLOSE (transitive closure), COMPOUND,

Francisco Javier
Moreno Arboleda 1

Jaime Alberto
Guzmán Luna 2

1 Profesor de la Escuela de
Sistemas de la Facultad de
Minas, Universidad Nacional
de Colombia.

2 Profesor de la Escuela de
Sistemas de la Facultad de
Minas, Universidad Nacional
de Colombia.

Artículo recibido en Abril de

2006, aprobado para publicación

en Agosto de 2007

23

REVISTA CIENTÍFICA Y TECNOLÓGICA DE LA FACULTAD DE INGENIERÍA, UNIVERSIDAD DISTRITAL FRANCISCO JOSÉ DE CALDAS

Vol.11 No.2
Ingeniería

23

El método
descrito no
requiere extender
el lenguaje SQL
con operadores
especializados

GROUP BY NODES y GROUP BY
LEAVES para tratar consultas recursivas en
QUEL [13] (un lenguaje de consulta similar a
SQL). Los autores explican que dichos opera-
dores pueden también ser propuestos para
SQL. Jagadish [14] acude también al concepto
de cierre transitivo [15] para abordar consultas
recursivas en bases de datos pero orientadas a
lenguajes tipo Prolog. Prolog es un lenguaje
basado en reglas utilizado en el campo de la
inteligencia artificial. En este tipo de lenguajes
el planteamiento de expresiones recursivas es
natural. Prolog se ha extendido para consultas
en bases de datos, dicha extensión se conoce
como Datalog, una detallada explicación de
este lenguaje puede verse en Maier [16].
Koymen [17] propone un operador recursivo
para SQL similar a como se trabaja en Datalog.
Rosenthal [18] presenta algoritmos eficientes
para la implementación de la operación cierre
transitivo y como éstos pueden incorporarse
en el optimizador de un SGBD. Introduce el
concepto de traversal recursions el cual es una
generalización del cierre transitivo y que per-
mite mayor flexibilidad para el planteamiento
de consultas recursivas.

James [19] propone operadores especializa-
dos para “tablas con árboles” y Biskup [20] pro-
pone extender SQL con un conjunto de opera-
dores que faciliten la concepción de consultas
para tablas “basadas en grafos”. Cruz [21] pro-
pone un lenguaje especializado llamado G para
la concepción de consultas recursivas. Tal y como
lo exponen los autores, su lenguaje no pretende
ser una alternativa para lenguajes de consulta
relacionales, sino un lenguaje complementario
en el cual las consultas recursivas son el objetivo.

Partiendo de la propuesta del SQL-99 para
la concepción de consultas recursivas, Ordonez
[22] trata los aspectos relativos a la optimización
de tales consultas.

Todas las propuestas mencionadas conciben
un lenguaje especializado para tratar consultas
recursivas o proponen extender el SQL o el ál-
gebra relacional con operadores especializados.

El método aquí planteado no requiere ex-
tender al SQL con un operador especializado.
En la misma línea de trabajo se encuentran las
siguientes propuestas. Celko [23][24] propone
un método denominado “anidado de árbo-
les”, sin embargo es complejo manejar ciertas
consultas en él, por ejemplo para hallar la altu-

ra del árbol (el cual se genera a raíz de una
tabla que exhibe una relación recursiva, véase
la Sección 2) se requiere una reunión de la ta-
bla consigo misma más una operación de gru-
po (GROUP BY); en el método aquí propues-
to no se requiere ni la reunión ni el agrupa-
miento (véase la consulta 4 en la subsección
3.3.1). Similarmente hallar los descendientes
directos de un nodo implica en su método una
consulta con reunión más una subconsulta
correlacionada (confróntese con la consulta 2
en la subsección 3.3.1).

Moreau [25] presenta un método denomina-
do ruta posicional. Posee similitudes con el método
aquí propuesto, pero no maneja bien ciertas con-
sultas ya que requiere subconsultas o reuniones
que pueden ser evitadas (véase la consulta 3 en la
subsección 3.3.1).

El método propuesto en este artículo para
el planteamiento de consultas recursivas en
SQL es una alternativa que puede ser contem-
plada tanto desde el punto de vista de
optimización de consultas como de SGBDs
que no posean operadores especializados para
consultas recursivas o que aunque posean al-
guna versión de PSM o interactúen con un len-
guaje que permita la recursión (Java, C++, C#
etc.) su costo computacional sea alto.

El artículo se desarrolla así: en la Sección 2 se
presenta un caso de estudio que ejemplifica una
situación recursiva. En la Sección 3 se explica y
ejemplifica el método propuesto para plantear
consultas recursivas. En la Sección 4 se exponen
algunas limitaciones del método y posibles for-
mas de evitarlas. Finalmente, en la Sección 5 se
presentan conclusiones y trabajos futuros.

2. CASO DE ESTUDIO

Las consultas recursivas pueden surgir en
muchas situaciones: (i) requisitos u objetivos que
poseen a su vez subrequisitos o subobjetivos,
(ii) árboles genealógicos, (iii) descomposición
estructural de una compañía en departamentos
y éstos a su vez en sub-departamentos y (iv)
composición de productos basados en otros
productos, situación conocida como “explo-
sión de partes” [7].

Sea la consulta “obtener todos los productos
que componen a otro producto”. Una solu-
ción impráctica [26] a este tipo de consultas es
realizar una serie de reuniones de una tabla con-

24 Vol.11 No.2
Ingeniería

REVISTA CIENTÍFICA Y TECNOLÓGICA DE LA FACULTAD DE INGENIERÍA, UNIVERSIDAD DISTRITAL FRANCISCO JOSÉ DE CALDAS

24

sigo misma n veces, donde n indica el nivel de
descomposición o profundidad deseado, es
decir, si se desea, por ejemplo, en el caso de un
árbol genealógico, determinar los bisnietos de
un individuo, se debe realizar una triple reunión
de la tabla consigo misma. Aparte de impráctico,
porque el máximo nivel de profundidad se des-
conoce normalmente, el costo computacional
de una n auto reunión es enorme.

Se plantea a continuación un método alter-
nativo para abordar este tipo de consultas.
Considérese la siguiente situación: supóngase
que un cliente puede recomendar a muchos
clientes y a su vez cada uno de éstos puede
recomendar a otros y así sucesivamente. Un
cliente no tiene necesariamente que haber sido
recomendado por otro cliente pero en caso
de que lo sea sólo puede ser recomendado por
uno y sólo uno.

En la Figura 1 se muestra un modelo entidad
relación que representa la situación descrita

Dicho modelo implantado de
  • Links de descarga
http://lwp-l.com/pdf11456

Comentarios de: Una propuesta para el manejo de recursión en SQL (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios
Es necesario revisar y aceptar las políticas de privacidad