PDF de programación - Tesis: César Alejandro Galindo - OPTIMACION DE CONSULTAS A BASE DE DATOS BASADA EN REGLAS

CENTRO DE INVESTIGACION Y DE ESTUDIOS AVANZADOS DEL

INSTITUTO POLITECNICO NACIONAL

DEPARTAMENTO DE INGENIERIA ELECTRICA

SECCION DE COMPUTACION

"OPTIMACION DE CONSULTAS A BASE DE DATOS BASADA EN REGLAS"

Tesis que presenta el Ing. César Alejandro Galindo Legaría
para obtener el grado de MAESTRO EN CIENCIAS en la especialidad
Trabajo
de INGENIERIA ELECTRICA con opción de COMPUTACION.
dirigido por el Dr. Renato Barrera Rivera.

Becario de CONACYT.

México D. F., 25 de Septiembre de 1987.

Introducción

que se

da comunmente a estos programas, que

Un componente importante de los sistemas de base de datos es
el optimador de consultas.
Esto se debe a que pueden usarse
lenguajes de consulta de muy alto nivel, que proporcionan
operaciones abstractas muy fáciles de usar y entender pero cuya
ejecución puede ser costosa.
El papel del optimador es generar
un plan de acceso eficiente para obtener ciertos datos, a partir
de una consulta formulada por un usario.
Esta importancia del optimador se manifiesta a partir de la
propuesta del modelo relacional y su lenguaje de consulta [15].
A partir de entonces se han desarrollado lenguajes de consulta de
muy alto nivel para sistemas de base de datos relaciónales, así
como métodos de optimación para encontrar planes de acceso
El problema es
eficientes a partir de una consulta dada.
complejo, y el término "optimador" no es exacto; pero ese es el
nombre
no
necesariamente ecuentran el mejor plan de ejecución para cada
consulta, sino solamente un plan que sea razonablemente "bueno".
Recientemente, se han venido desarrollando nuevas propuestas
sobre modelos de base de datos, con otro tipo de operandos y
operaciones [6,17,32] y en las que el optimador juega un papel
importante para una implantación eficiente.
Se habla incluso de
bases de datos
de
objetos con sus operaciones propias. En un sistema de este tipo,
como ya se ha señalado [11,19,23,29], se requiere de un optimador
extensible:
deben poder agregarse nuevos objetos y operaciones;
nuevos métodos para llevarlas a cabo, con estructuras y costos
propios; y sugerencias en cuanto a cómo efectuar la optimación.
En este trabajo se propone la arquitectura de un optimador
Dada la experiencia
general extensible basado en reglas (OG).
que existe en la optimación de consultas para el
modelo
relacional,
OG
construyendo un optimador para bases de datos relaciónales
distribuidas (ORD).
En el capítulo 1 se presentan los conceptos básicos del
modelo relacional, junto con las técnicas de optimación propias
en el capítulo 2, conceptos básicos y técnicas de
del mismo;
optimación para una base de datos distribuida que usa el modelo
En el capítulo 3 se presentan los principios
relacional.
generales de la optimación basada en reglas, así como la
arquitectura del OG.
En el capítulo 4 se describen en detalle
los módulos que componen al ORD. Finalmente, en el capítulo 5 se
hace una comparación del OG y ORD con otros trabajos.
Se asume
el conocimiento de cierta terminología de gráficas que puede
consultarse en [2],

en las que se puedan agregar nuevos tipos

se

ilustra

la arquitectura general del

3

1.

EL MODELO DE BASE DE DATOS RELACIONAL

La propuesta del modelo relacional [15] trae una serie de
cambios importantes en la manera de ver y usar las bases de
datos. Entre otras cosas, se propone un modelo de datos uniforme
y teóricamente manejable, y se hace énfasis en la independencia
entre el lenguaje de consulta y las estructuras de almacenamiento
de los datos.
A partir de entonces se han desarrollado sistemas
de base de datos que siguen este modelo, se ha adquirido
experiencia en su uso y luego, a partir de esta experiencia, se
han propuesto otros modelos. Por esto el modelo relacional es un
buen punto de partida para el estudio de las bases de datos, y
también para realizar las primeras pruebas en cuanto a optimación
basada en reglas.
En este capítulo se presentan los conceptos básicos de un
sistema de base de datos, y se repasa brevemente el modelo
relacional. Para más información se puede consultar [34].

1.1. Conceptos básicos

Para facilitar el uso de una base de datos se manejan varios
niveles de abstracción.
Cada nivel corresponde a una forma de
ver la misma información, de acuerdo con un propósito. El nivel
físico especifica cómo deben verse los datos en cuanto a su
almacenamiento;
esto es, qué estructuras deben usarse para
guardarlos de manera eficiente y confiable.
El nivel conceptual
especifica cómo se pueden presentar los datos al usuario para que
los entienda fácilmente, y se debe usar algún formato que ponga
de relieve las relaciones conceptuales entre ellos.
Estos
niveles se ilustran a continuación.

Ejemplo 1.1. Supóngase que en una base de datos guardamos,
entre otras cosas, información acerca de los libros que se
tienen en una biblioteca.
En el nivel físico, se puede ver
que los datos de los libros están almacenados en un archivo
que tiene un índice sobre el campo autor y otro sobre el
En el nivel conceptual, por otro lado, los
campo numlibro.
datos se visualizan en la forma de una tabla en cuyos
renglones aparece la información de cada libro.
Esto se
esquematiza en la Fig. 1.1.
El uso de estos niveles de abstracción plantea un problema
El usuario describe sus consultas según la manera
importante:
como él ve los datos (nivel conceptual), pero éstas deben ser
resultas en términos del nivel físico.
Para cada consulta del
usuario debe determinarse un plan de acceso que obtenga los datos
solicitados, de acuerdo con la manera en que están almacenados.
Al componente que se encarga de encontrar un plan de acceso
eficiente para resolver una consulta dada se le llama optimador.
Este módulo realiza su tarea guiado por heurísticas que se han
desarrollado a lo largo de los aftos.
Mientras mayor sea la
diferencia entre los niveles físico y conceptual y mientras más
abstractos sean los lenguajes de consulta que se usen, más

4

autor .ind

libros.dat

numlibro.ind

(a ) Nivel físico: archivos do datos.

titulo
Data Structures and Algorithms
Principles of Compiler Design
Distributed Databases
Programming in Prolog
Artificial Intelligence
Artificial Intelligence

autor
Aho
Aho
Ceri
Clocksin
Rich
Winston

nombree
Addison-Wesley
Addison-Wesley
McGraw-Hill
Springer-Verlag
McGraw-Hill
Addison-Vesley

numlibro
8476
3645
9087
1324
5789
3867

(b) Nivel conceptual : tablas de datos.

Fig. 1.1. Niveles de abstracción.

importante es la tarea del optimador, que nos debe llevar de la
facilidad de expresión a la eficiencia de ejecución.
Hay varios enfoques en cuanto a la manera en que deben verse
los datos en el nivel conceptual;
estos enfoques reciben el
nobre de modelos de datos.
Un modelo de datos se compone de dos
partes:
una notación matemática para describir los datos y sus
relaciones, y un conjunto de operaciones para manipularlos.
Aunque el objetivo principal es la claridad y facilidad de uso,
los modelos de datos propuestos están influenciados por alguna
estructura de almacenamiento físico.

1.2. El modelo relacional

Después de la propuesta inicial del modelo relacional, se
han presentado varias versiones de sus operadores que, aunque son
muy semejanntes, guardan ciertas diferencias en notación o
significado.
En lo que sigue nos basaremos en la notación usada
en [ 13].

1.2.1. La relación

En el modelo relacional los datos aparecen al usuario en la
Cada tabla tiene un formato fijo en cuanto al
forma de tablas.
numero de columnas y tipo de datos que almacena.
Típicamente,
Cada tabla
una base de datos está compuesta por varias tablas.
tiene un número variable de renglones, que no se duplican, y que

5

libros :

titulo
Data Structures and Algorithms
Principles of Compiler Design
Distributed Dat^b^ses
Programming in Prolog
Artificial Intelligence
Artificial Intelligence

autor
Aho
Aho
Ceri
Clocks in
Rich
Vinston

norribree
Addison-Wesley
Addison-Vesley
McGraw-HiTl
Springer-Verlag
McGraw-Hill
Addison-Vesley

numübro
8476
3645
9087
1324
5789
3867

editoriales :

nombree

Addison-Vesley
McGraw-Hill
Springer-Verlag

usuarios :

direcce
1027 5th Ay
558 7th Av
879 3rd Av

ciudad*
Nueva York
Nueva York
Nueva York

nombre
García
López

dirección
Fresnos *528
J.SBach « 55

ciudad
Querétaro
Mexico D J .

numusr
196
435

prestamos:

numusr
196
435
196

numlibro
1324
8476
5789

.

fecha
1/8/87
3/8/87
7/8/87

Fig. 1 2. Lina base de datos en tablas.

pueden agregarse o eliminarse.
representación se aprecia en el siguiente ejemplo.

La claridad de este tipo de

Queremos guardar en una base de datos la
Ejemplo 1.2.
información concerniente a una biblioteca.
Nos interesa
guardar información sobre los libros que tenemos y sus
editoriales, nuestros usuarios y qué libros les hemos
prestado.
Determinamos qué datos nos interesa registrar de
cada libro, usuario, editorial y