PDF de programación - Tesis: Jose Martinez - REPRESENTACIÓN DE SISTEMAS DE CONSULTA EN TABLEAUX Y SU IMPLEMENTACIÓN EN UNA BASE DE DATOS RELACIONAL

CliiTRt I! I«W! SlPUCOH 1 Ill

U T U ~ ! U AVU 2AtU Ill

I. P . N .

D I .. L I O T IIl OA
·~•r. f NI EI!I A El f:CTRICJ

CENTRO DE INVESTIGACION
Y DE ESTUDIOS A V ANZADOS

DEL I. P. N.

DEPARTAMENTO DE INGENIERiA ELECTRICA

SECCION DE COMPUTACION

REPRESENT ACtON DE SISTEMAS DE CONSULT A EN
TABLEAUX Y SU IMPLEMENT ACtON EN UNA BASE DE

DATOS RELACIONAL

T

E

s

I

s

QUE PARA OBTENER EL GRADO DE:

CIN VEST A V 'f

l P N

ADOU/5 /Ci Ñ
DE LI SROS

MAESTRO EN CIENCIAS EN LA ESPECIALIDAD DE
INGENIERiA ELECTRICA

PRES E N T A:

JOSE ALEJANDRO MARTiNEZ HERNANDEZ

DIRECTOR DE TESIS

DR. SERGIO VICTOR CHAPA VERGARA

MEXICO, D.F.

Wnl D! III¥!STIU COH Y h
fS TU !JUIS 4 V U Z ~J O S 9H

I. P . N .

• IB L I O T E OA
~• r.E NI E III ~ ELECTRICI

1998

CONTENIDO

Capitulo I. Los Sistemas de Consulta Form ales

1.1 £1 Algebra Relacional

1.1.1 Operaciones Booleanas
1.1.2 El Operador Selecciona
1.1.3 El Operador Proyecta
1.1.4 El Operador Junta
1.1.5 El Operador Divide

1.2 El C:ilculo Relacional de Tuplas

1.2.1 FOrmulas del C:ilculo Relaciona l de Tuplas
1.2.2 Variables Libres y Ligadas

1.3 El C3.1culo Relacional de Dominios
lA Las Expresiones ALPHA
1.5 El Algoritmo de Reducci6n

Capitulo 2. Sistema de Consulta Tableaux

l.l Desarrollo de Consultas por Tableaux
1.2 Traducci6n de Expresiones Algebraicas a Tableaux
2.3 Consullas Tableaux que vienen de Expresiones Algebraicas
2.4 Consultas Tableaux en Multi Relaciones
2.5 Consultas Tableaux en Conjuntos
2.6 Consultas Conj untivas

Capitulo 3. Implementacion del Sistema de Consulta

Tablusql

3.1 ImplementaciOn de Tableaux como un Traductor de Lenguajes
3.2 Fase de An:.llisis "ode RevisiOn"
3.3 Fase Tableaux
3.4 Fase de EjecuciOn

3.-U Procesador del Lenguaje de Coosulta

3.3 Fase de RecuperaciOn "o Fetch"

Capitulo 4. Implementacion del Sistema de Manejador

de Ia Base de Datos

4.1 Funciones y Estructuras de Datos del Sistema Manejador de

Ia Base de Datos

4.2 lnterrelaciOn de las Estructuras de Datos Maestras

10
II
14
IS
17

22

22
28
32
33
35
37

39

40
~2
47
51
52
57

60

61
64

CUTI'te CE tHVE S116 lC!e. Y • •

HT Uiii " S • n" l•. fi OS BEl

I. p N .

B I Rt L I OT EOA
... ~rNIERIA ELECTRIC~

Capitulo 5. Implementacion de un Problema de Base de

Datos

5. 1 Descripci6n de un Problema de Base de Datos
5.2 l mplementaci6n del Problema
5.3 Resultados

Conclusiones

Bibliografia

72

69

70

77

86

88

CUT"I Ot IIIH SlltACh!. Y k
UT UOIIS AV A,.- Z.t.liOS Dlil

I. P . N .

BI !B L I O T EO A
•• • '":I' NIE RIA EL ECTRICI

Quisiera expresar un sincero agradecimiento al Centro de Investigaci6n y de
Estudios A vanzados del lnstituto Politecnico Nacional por Ia oportunidad que me dicron
para avanzar en mi formaci6n profesional y cumplir con uno mas de mis objetivos. En
particular a Ia Secci6n de Computaci6n del departamento de Ingenieria EJectrica y a\ Dr.
Sergio V. Chapa Vergara por su confianza y comprensi6n como maestro y amigo. A los
Doctores Arturo Diaz Perez y Juan Francisco Corona Burguefio por su interCs y
comentarios en este trabajo de tesis.

A mis padres, Sara Hernandez Angeles y Luis Martinez Godinez por cl amor.

coraje, y trabajo infinito, porque con ello se puede lograr todo en Ia vida.

A mis Esposa Raquel Bueno Arias porque en ella encontre un nuevo sentido a Ia
vida y me impulso para que continuar con lo que habia iniciado. A mis hijos Alejandro.
Maria Fernanda y Guadalupe Martinez Bueno para que vean en este esfuerzo, un ejcmplo
de que las casas si sc pucden Jograr.

A mis suegros Raquel y Enrique Bueno Padilla por su apoyo y a todos mis
hermanos y demas familiares les dedico este esfuerzo y con ella solo una parte de mi vida.
fi nalmente quisiera dedicar este trabajo a todos mis sobrinos para que vean que Ia vida cs
tmis interesante cuando se real iza un sacrificio y un esfuerzo por alcanzar sus mctas.

I:IIITRt II lllfiiTIUCIH Y ..

IITUI IIS HU Z1ItS IH

I. p N .

•
I B L I OT EOA
"'' r.I': NIEI!IA ELECTRIC,

Resumen

Bas<indonos en los fundamentos del modelo de datos relacional. un sistema de
consulta formal puede ser llevado a su implementaciOn en un Sistema Manejador de Base
de Datos. El paradigma de tableaux descrito por Ullman y Maier es usado para
representaciOn de sistemas fonnales de consulta [Aha 1979][Ullman 1982][Maier \983).
Tableaux se implanta con sus reglas de composici6n y sus estructuras de datos para permitir
un media de consulta eficaz tanto de los lenguajes de QBE como el de SQL a traves de las
reglas de transfonnaci6n dadas par los fundamentos del modelo relacional de datos y
considerando Ia estrategia de descomposici6n de procesamiento de consultas de Eugene
Wong y Karel Youssefi [Wong 1976J. Proponemos el descriptor de archivos [Chapa 1985]
como Ia estructura de datos principal que comunica al sistema manejador de datos con el
sistema de consulta basado en tableaux.

IOUITU I! NfUS TIU CIU y t l

ISTUt iU H'.A" lA US DEL

I. P . N .

• III LI OT E o "
"" r, E: NIEI'IIA ELECTRIC!

Palabras clave: Modelo relacional de datos I Sistemas Formales de Consulta I Tab leaux I
Sistema Manejador de Bases de Datos I Estructuras de Datos I Descriptor de Archivos I
QBE I SQL.

lntroduccion

El modelo de datos reiacional presentado por Codd [Codd \970J ha influ ido en el
diseii.o de sistemas actuales de bases de datos. y un nUmero de nuevas sistemas se
construyen alrededor de este modelo. Sus principales virtudes son Ia independencia de
datos y Ia capacidad de formulae consultas no procedurales en h~rminos dd ctilculo
relacional y. en menor extensiOn. del algebra relacional. Los sistemas de consulta no
procedurales son de alto nivel porque liberan al usuario de tener que elaborar una respuesta
deseada. dejando que el trabajo de esta determinaciOn caiga fundamentalrne nte en el
procesador del lenguaje de consulta del sistema de Ia base de datos. micntras que. en
sistemas de consulta procedurales como el <i.lgebra relacional se da un conjunto de
operaciones en relaciones y eJ arden en que deben de ejecutarse. Bas<indonos en los
fundamentos del mode le relacional un sistema de consulta puede ser
llevado a su
implementaci6n en un Sistema Manejador de Base de Datos. Resultados de varios grados
de generalidad en estrategias de construcci6n y procesamiento de sistemas de consulta
fonnales han sido reportados por [Astrahan 1975][Wong 1976] [Ullman 1979] [Aha 1979],
sin embargo Ia carencia de un enfoque general para Ia construcci6n de sistemas
manejadores de bases de datos junto con sistemas de consulta y Ia interrelaci6n con sus
estructuras de datos internas mantienen un impedimenta principal para a lcanzar un grado
satisfactorio de conocimiento de sistemas manejadores de base de datos [Chapa 1985]
[Guzman 1985]. El o bjetivo principal de nuestro trabajo es implantar e l paradigma de
tableaux para procesamiento de sistemas de consulta descrito por Tableaux [Aho 1979]
(Ullman 1982] [Maier \983] con sus reg las de com posiciOn y sus estructuras de datos para
pennitir un media de consulta eficaz tanto de los lenguajes de QBE como e l de SQL a
traves de las reglas de transformaci6n dadas par los fundamentos de l modelo relacional de
datos y considerando Ia estrategia de descomposici6n de procesamiento de consuhas de
Eugene Wong y Karel Youssefi [Wong 1976]. Utilizamos Ia metodologia Tableaux como
un traductor de lenguajes de alto nivel y proponemos el descriptor de archives [Chapa
1985) como Ia principal estructura de datos que comunican al sistema manejador de datos
con el sistema de consulta basado en tableaux. Este sistema es Ia interfaz con un Sistema
Manejador de Base de Datos, que incluye un modelo fisico con un sistema de organizaci6 n
basado en irboles B desarrollado por AI Stevens [Stevens 1987].

Este trabajo fue hecho en e l contexto de desarrollar un consultador para una base de
datos que contiene infonnaci6n referente a coordenadas geognificas para Ia localizaci6n de
pozos petroleras junto con Ia tesis de maestria "'Sistemas de InformaciOn GeogriJfica para
Ia Exploraci6n Petrolera" que obtiene infonnaci6n gnifica de una area se leccionada
[Fiorentino 1996] yes Ia base para nuevas desarrollos en Openslep y Raphsody. Eltrabajo
contempla dos niveles de usuaries: usuario administrqdor donde se da un conjunto de
herramientas para definir Ia base de datos, de tal manera que el sistema manejador sea Ia
interfaz entre e l administrador de Ia base de datos y Ia base de datos fisica: usuario final en
donde se ofrece un lenguaje de consulta no procedural. con facilidades para seleccionar
datos compartidos, utiliza vistas de tab las propias y externas definidas en otra base de datos.

El Lenguaje de consulta desarrollado en lenguaje ··c" es un prototipo dd lenguaje
SQL (Structured Query Language) y es traducido a Ia metodologia tableaux dentro del
modelo relacional. La metodologia tableaux. no es un sistema de consulta completo en
comparaciOn con el algebra relacional por considerar solo los operadores selecciOn
proyecciOn y junta. sin embargo. las consultas por tableaux abarcan un gran nU.mero de
consuhas que pudieran surgir en aplicaciones de bases de