· agradecimientos agradezco a mis queridas hermanas jacqueline y juanita todo cuanto hicieron y...

SEP SEIT DGIT

CENTRO NACIONAL DE INVESTIGACION Y DESARROLLO TECNOLOGICO

cenídet

"OPTIMIZACION DE ESTRATEGIAS DE ACCESO PARA UN SISTEMA MANEJADOR DE BASES DE

DATOS DISTRIBUIDAS-

T E S I S QUE PARA OBTENER EL GRADO DE :

M A E S T R O E N C I E N C I A S

D E L A C O M P U T A C I O N CENTRO DE I N F O R ~ C ~ O N

C E N I D E T P R E S E N T A: c> G. E L S A J U A R E Z M E J I A

JUNIO DE 1995. CUERNAVACA, MOR.

Gracias Señor Jesús!

A mis adorables y queridos padres: Juan Juárez y Sabina Mejh por su gran amor, sacrificio y entrega.

Motivo de mi superación.

A mi querido hermano Juan José por su ejemplo de amor a la vida.. .

A mis querida hermanas Jacqueline y Juanita por su infinito amor.. .

AGRADECIMIENTOS

Agradezco a mis queridas hermanas Jacqueline y Juanita todo cuanto hicieron y contribuyeron para llegar al final de mis estudios de maestría.

Agradezco de manera muy especial a mis grandes y queridas amigas Míriam Sánchez y Emma Anzures, por su incondicional amistad y apoyo brindado en todo momento.

Expreso mi agradecimiento a la Maestra Gloria Mezquite por su confianza y motivación brindada.

Gracias a Enrique Wing por su incondcional amistad.

Gracias a mis compañeros y amigos de generación Leopoldo Zepeda S., Ariel Lira O., Víctor Sosa S., Juan de Dios Viniegra V., Juan Gabriel González S., Ricardo Amador G., Leticia Santaolalla por su amistad y por hacer inolvidable mi estancia en CENIDET.

Gracias a mis compañeros Anastasio Antolino, Miguel Ortíz M. y J. Antonio Martinez F. por su apoyo.

Expreso mi agradecimiento a mi asesor de tesis Dr. Rodolfo Pazos Rangel, por su apoyo, orientación y dedicación en todo el transcurso de la realización del trabajo de tesis.

Gracias al M.C. Joaquín Pérez Ortega por su apoyo e interés brindado para el desarrollo de este trabajo de tesis.

Agradezco a mis maestros por su orientación, su apoyo y por bridarme sus conocimientos.

Reconozco y agradezco el apoyo económico brindado por CONACYT para poder efectuar mis estudios y tesis de maestría.

Gracias al Instituto de Investigaciones Eléctricas por las facilidades otorgadas para la realización de este trabajo de tesis.

INDICE

CAPITULO 1

LNTRODUCCION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1. Desarrollo de las Bases de Datos Distribuidas (BDD) . . . . . . . . . . . . . . . . . . 2 1.2. Descripción del Problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3.Beneficios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.4. Alcances del Proyecto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.5. Estado del Arte . . . . . . . . . u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.6. Organización de la Tesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

CAPITULO 2

CONCEPTOS SOBRE BASES DE DATOS DISTRIBUIDAS . . . . . . . . . . . . . . . . 7 2.1. Bases de Datos Distribuida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.1.1. Ventajas de las Bases de Datos Distribuidas . . . . . . . . . . . . . . . . . . 8 2.2. Sistema Administrador de Bases de Datos Distribuidas . . . . . . . . . . . . . . . . . 9 2.3. Las Bases de Datos Distribuidas y el Modelo Relacional . . . . . . . . . . . . . . . 11

2.3.1. SQL Basado en el Modelo Relacional como Lenguaje de Consulta en un SMBDD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.4. Panorama General sobre el Proceso de Optimización de Consultas . . . . . . . . 15 2.4.1. Proceso General de Optimización ......................... 16

CAPITULO 3

CONCEPTOS Y TECNICAS PARA LA INDIZACION . . . . . . . . . . . . . . . . . . . 19 3.1. Indizacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.2. Utilización de Indices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.3. Tipos de Indices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.4. Archivos Indizados de Arboles B+ .............................. 22

3.4.1. Estructura y Elementos de un Indice de Arbol B+ . . . . . . . . . . . . . 23 3.4.1.1. Elementos de un Arbol B+ ...................... 23 3.4.2.2. Búsqueda, Inserción y Borrado sobre un Arbol B+ . . . . . . 26

3.4.2.2.1. Búsqueda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.4.2.2.2. inserción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.4.2.2.3. Borrado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.4.2.3. Definición de Indices sobre las Tablas . . . . . . . . . . . . . . . 30

. . .

CAPITULO 4

PLANTEAMIENTO Y SOEUCION DEL PROBLEMA . . . . . . . . . . . . . . . . . . . 32 4.1. Planteamiento del Problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

I

4.2. Antecedentes del Proyecto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.2.1. Primitivas del SMBDD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.2.2. Precompilador para un Lenguaje de Definición de Datos . . . . . . . . . 37 4.2.3 Lenguaje de Manipulación de Datos ....................... 37

4.3 Proceso General de Premmpilación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.4. El Problema de la Cláusula FROM de SQL . . . . . . . . . . . . . . . . . . . . . . . . 39 4.5. Aspectos Generales del Proceso General de Optimización . . . . . . . . . . . . . . 41 4.6. Importancia de la Cláusula WHERE en el Procesoe Optimización . . . . . . . . . 43

4.6.1. El Problema del Análisis de la Cláusula WHERE . . . . . . . . . . . . . . 44 4.6.1.1. Operadores Lógicos AND y OR . . . . . . . . . . . . . . . . . . . 45 4.6.1.2. Análisis de las Columnas para los Operadores

Lógicos AND y OR . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.6.1.3. Análisis de la Condición WHERE . . . . . . . . . . . . . . . . . 47

4.6.1.3.1. Pseudocódigo para el Análisis de la Expresión WHERE ..................... 49

4.6.1.4. El Problema de Selección del Indice para Accesar una Subconsulta . . . . . . . . . . . . . . . . . . . . . . . . 51

.4.6.1. 4.1 Elección del Indice para Procesar una Subconsulta ........................ 55

sobre el Indice . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.6.1.4.3 Algoritmo de Búsqueda de las Llaves . . . . . . . . . 61

4.7. El problema de los Renglones Duplicados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.8. El problema de la Tabla Derivada de la Cláusula FROM .................... 65

de la Tabla Resultante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

tabla en la Cláusula FROM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 72

Cláusula SELECT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 77

4.9. Proceso General de Optimización . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

CAPITULO 5

4.6.1.4.2 Algoritmo para la Defmción del Tipo de Búsqueda

4.8.1. Uso de la Cláusula SELECT para Determinar el Grado

4.8.2. Análisis de la Condición WHERE cuando se Especifica Más de un Nombre de

4.8.3. Evaluación de las Subconsultas para Recuperar los Renglones . . . . . . . . . . .

4.8.5. Ejecución del Producto Cartesiano para Obtener la Tabla Derivada

4.8.4. Almacenamiento de los Renglones para Obtener los Valores de Columnas de la

. . . . . . .

PRUEBAS AL OPTIMIZADOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 5.1. Objetivos de las Pruebas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 5.2. Condiciones de las b e b a s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 5.3. Presentación de las Pruebas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

CAPITULO 6

COMENTARIOS FINALES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

I1

6.1. Comentarios Finales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 6.2. Posibles Extensiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

BIBLIOGRAFIA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

CAPITULO 1

INTRODUCCION

CAPITULO 1

1.1. Desarrollo de las Bases de Datos Distribuidas (BDD)

iNTRODUCCION

El desarrollo de las bases de datos distribuída es un campo nuevo en el área de sistemas de bases de datos, convirtiéndose en un tema impomte de investigación, a tal grado que se cree que el desarrollo de esta tecnología impactará el procesamiento de datos provocando que los manejadores de bases de datos centralizados se enfoquen hacia esta nueva filosofía.

La integración de los datos operacionaies por medio del uso de bases de datos, permite tener un acceso controlado y centralizado sobre éstos, lo cual representa una gran ventaja para la administración de los datos.

Los sistemas de bases de datos centralizados (SBDCs) fueron los primeros en imponer un control centralizado sobre los datos. Cuando las empresas vieron las ventajas de integrar los datos, fue entonces que percibieron la necesidad de ello. Es en este cambio donde las empresas compuestas por diferentes unidades, las cuales operan en diferentes sitios y cuentan con varias computadoras conectadas entre sí por medio de una red de comunicaciones, comenzaron a experimentar el impacto de los problemas causados por el uso de los SBDCs para lograr este objetivo. Uno de los principales problemas que se presentaba era que el tiempo de respuesta de los programas era demasiado lento debido a que el SBDC realiza accesos a un sitio central para obtener la información.

Para resolver parte de estos problemas se tuvo la necesidad de tener en cada unidad de la empresa una parte de la base de datos. De esta forma los datos para aplicaciones locales se tenían disponibles en el sitio donde se originaran, y cada sitio podía entonces tener control y autonomía sobre sus datos. En estas circunstancias, io que se necesitaba era un adminisirador de bases de datos disíribuidas.

1.2. Descripción del Problema

En los sistemas distribuidos la transmisión de datos entre computadoras puede ser causa de que el sistema sea lento, debido al exceso en el vo lhen de información que se transfiere cuando la ejecución de una consulta se lleva a cabo sin utilizar una estrategia de optimización. Es decir, no se hace uso de mecanismos o técnicas mediante las cuales la información solicitada puede recuperarse de manera más rápida y eficiente. Lo anterior provoca que los accesos a memoria principal, memoria secundaria y a la red de comunicaciones sean demasiados para el procesamiento de una consulta, lo cual se traduce en un exceso de tiempo consumido para dar respuesta a una petición. Por lo tanto, el desempeño del sistema puede llegar a ser ineficiente, dejando al usuario la responsabilidad de que decida cuál es la mejor forma de diseñar las consultas con el fui de obtener resultados satisfactorios en cuanto a tiempo de respuesta y al uso de los recursos del sistema.

2

CAPITLKO I WTRODUCCION

El propósito de este trabajo de tesis consiste en desarrollar un optimizador de consultas que permita reducir al mínimo el tráfico de infokación sobre la red y los accesos a memoria (principal y secundaria), para disminuir el tiempo de respuesta a las peticiones realizadas por el usuario.

.

Para una consulta se pueden presentar varias estrategias de procesamiento; por lo tanto, el optimizador debe ser lo suficientemente inteligente para evaluar cada UM de ellas y decidir cuál es la mejor. Este aspecto es lo que hace que la implementación de un optimizador no sea un problema trivial, puesto que para tomar la decisión de ejecución de UM consulta necesita considerar por una parte aspectos definidos sobre UM tabla tales como cardinalidad, grado, rutas de acceso definidas sobre ésta que permitan recuperar más rápido la información; y por otra la estructura de la consulta, es decir la forma que presenta, con el fin de analizarla para traducirla internamente a otra que sea equivalente a la original pero que puede ser procesada de forma más eficiente. Para esto se requiere crear procedimientos que realicen semánticamente lo mismo que la consulta realizada.

1.3. Beneficios

Con el desarrollo de este trabajo de tesis, se logró obtener los siguientes beneficios:

Reducción del tiempo de respuesta. Uno de los objetivos que busca un SMBDD, es que el tiempo de respuesta a una consulta sea el menor.

Reducción del uso de recursos. Debido a que el algoritmo de optimización considera ,

aspectos para lograr que se realice el menor número de accesos a la memoria secundaria, memoria principal y red de comunicaciones, se obtuvo como resultado la minimización en el uso de estos elementos.

-

-

- Insensibilidad a la formulación de la consulta. Anteriormente se dejaba la responsabilidad al programador de aplicaciones de diseñar sus consultas de tal forma que se ejecutaran de manera eficiente; es decir, era el programador quien defiia la estrategia de ejecución. Con el desarrollo de este trabajo las consultas se pueden realizar de cualquier manera dejando la tarea de seleccionar la ejecución de la consulta al optimizador, lo cual se traduce en una mayor flexibilidad en el desarrollo de programas de aplicación.

Reducción de las tablas temporales. El tamaño de las tablas derivadas se redujo, a tal grado que sólo contienen la información necesaria.

-

3

C A P I m O 1

1.4. Alcances del Proyecto

MTRODUCCION

El trabajo de esta tesis está considerado dentro de una de las etapas de desarrollo de un SMBDD. Los alcances de este trabajo son los siguientes:

- Desarrollo e implementación de un algoritmo que permite implantar estrategias y técnicas para optimizu la ejecución de una consulta en el lenguaje SQL sobre una base de datos distribuida; el cual comprende las siguientes etapas:

a) Conversión de la consulta a una representación interna, que sea entendible para la computadora.

Creación y elección de procedimientos de bajo nivel para los operadores de SQL (reunión, proyección, producto cartesiano, selección, etc.).

Generación de planes de ejecución y elección del más eficiente.

Estrategias para consultas y actualización de datos distribuidos

b)

c)

d)

Uso de índices definidos sobre las tablas, como medio para recuperar más eficientemente los renglones.

Aplicación de la técnica de optimización de consultas a las instrucciones UPDATE y DELETE de SQL.

-

-

1.5. Estado del Arte

El área de bases de datos distribuidas está experimentando una evolución no solamente en el nivel de investigación y desarrollo de prototipos, sino también a nivel de desarrollo comercial y aplicaciones reales.

A continuación se mencionan algunos SMBDDs que han sido desarrollados, los cuales cuentan con un optimizador para decidir la estrategia de ejecución para las consultas a las bases de datos.

- SDD-1. Es un sistema para bases de datos distribuidas, desarrollado por la Computer Corporation of America. Fue el primer prototipo que se realizó con la filosofía de bases de datos distribuidas. El SDD-I realiza la optimización de las consultas, aprovechando la operación "semi-join"; la cual permite reducir la cardinalidad de las relaciones, cuando esta operación se ha aplicado al máximo, todas las relaciones se colocan en el mismo sitio, en donde la consulta puede ser ejecutada. El algoritmo utilizado para la optimización

4

CAPIlTJi.0 I INTRODUCCION

no considera el costo para la transmisión f m l del resultado desde el lugar seleccionado para el proceso al lugar original donde se solicitó la consulta. Utilizando esta estrategia de optimización, se reducen los programas basándose en el uso de selecciones, proyecciones y "semi-joins"; entonces los programas se ejecutan en lugares remotos, usando los datos disponibles en espacios locales de trabajo y recuperando los datos que se transmiten ai lugar de proceso.

MULTIBASE. Fue desarrollado en la Computer Corporation of America. El sistema da a los usuarios una vista uniforme de la base de datos en un lenguaje de manipulación de datos. MüLTiBASE tiene un alto nivel de interfaz para aplicaciones de lectura solamente, el cual es transparente a la localización de los datos y a la heterogeneidad de los SABDs. El método de optimización que se usa es el mismo que utiliza SDD-1.

-

- Proyecto R*. Desarrollado en los laboratorios de la IBM en California. El objetivo de R* es ofrecer autonomía de localización de los datos. Otra característica importante de R* es la transparencia de localización, con esto se logra que los programadores vean la base de datos como un sistema centralizado. R* está compuesto de tres componentes básicos: un sistema local de manejo para la base de datos; un componente de comunicación de datos el cual permite la transmisión de mensajes; y un manejador de transacciones, el cual coordina la implementación de transacciones.

El método de optimización se lleva a cabo en tres fases: primero, se realiza un procesamiento local sobre la tabla; después, se usan "semi-joins" para reducir el tamaño de las relaciones, las cuales se envían a una tabla localizada en un lugar común; finalmente, la consulta se realiza con la reducción de relaciones. Esto significa que si una consulta involucra la reunión de tres relaciones que están almacenadas en diferentes lugares, entonces la primera relación se envía a la segunda relación, donde se efectúa la reunión de éstas; el resultado se envía a la tercera relación, donde se realiza la reunión de esta relación y se produce el resultado final de la consulta.

SIRIUSDELTA. Desarrollado con el propósito de hacer más sencillas las interfaces con otros SMBDDs. Los trabajos desarrollados se centran en conectar SIRIUS-DELTA a otros SMBDD. SIRIüLS-DELTA usa el modelo relaciona1 para la descripción de los datos. Permite la fragmentación y transparencia de datos. La optimización consiste en transformar una expresión algebraica a un plan de acceso. La consulta se mapea primero a un árbol operador, donde las hojas son las relaciones globales. Después este árbol se transforma en un árbol interno, donde las hojas son fragmentos de la consulta; de esto resulta que se puede tener más de un camino para construir relaciones globales de los fragmentos. Por úitimo se realiza una fase de reducción generando un árbol.

-

Dado lo anterior podemos observar que la implementación de algoritmos de optimización no es nueva, pero observamos que existen varias formas de implementar la optimización de tal

5

CAPITULO I MTRODUCCION

manera que lo que se pretende realizar en este pioyecto de tesis es diseñar un método de optimización para bases de datos distribuidas.

1.6. Organización de la Tesis

El presente documento está organizado de la siguiente manera:

En el segundo capítulo se presentan conceptos sobre bases de datos distribuidas, el modelo relacional, una descripción del lenguaje SQL que se usa como interfaz en el sistema distribuido, y un panorama general sobre el proceso de optimización con el fm de que el lector comprenda mejor el trabajo realizado.

(,'

/ I En el tercer capítulo se introducen conceptos básicos sobre índices y técnicas de

indización, con el propósito de dar a conocer al lector la forma en que las tablas se pueden ordenar para tener un acceso más rápido a los renglones de éstas.

En el capítulo cuatro se mencionan los antecedentes del proyecto, la descripción del problema, y la metodología de solución empleada para resolver el problema de optimización. En este capítulo se presentan los algoritmos empleados para dar solución al problema.

En el capítulo cinco se describen las pruebas realizadas al optimizador de consultas con el fin de verificar si el tiempo empleado para dar respuesta a una consulta se redujo y si el empleo de los recursos del sistema se minimizó al utilizar la estrategia de solución generada por el optimizador.

En el capítulo seis se presentan los beneficios obtenidos con el desarrollo de este trabajo, las posibles extensiones y coment&os finales.

6

CAPITULO 2

CONCEPTOS SOBRE BASES DE DATOS DISTRIBUIDAS

El objetivo de este capítulo es el de explicar conceptos que serán utilizados a lo largo de la descripción del trabajo de tesis. El presente capítulo describe conceptos básicos sobre bases de datos distribuidas, la estructura de un sistema de base de datos. También se incluyen conceptos sobre el modelo relacional y la descripción del lenguaje de consulta SQL, que se usa como interfaz en el sistema distribuido para tener acceso a los datos de las relaciones. Por último se presenta un panorama general sobre el proceso de optimización.

CAPITüJ,O 2

2.1. Bases de Datos Distribuida

CONCEPTOS SOBRE BASES DE DATOS DLITRIBülüAS

Una base de datos distribuida (BDD) es una colección de datos que físicamente se encuentran repartidos en varias computadoras, la cuales están conectadas entre sí por medio de una red, permitiendo de esta forma la comunicación de los datos entre éstas. Cada computadora debe participar en la ejecución de por lo menos una aplicación global, en la cual se haga uso de los datos que se encuentran localizados en otras computadoras. Además, cada computadora tiene capacidad de procesamiento autónomo; es decir puede realiza;' aplicaciones locales que no necesitan de datos que se encuentran en otras computadoras. Las BDDs dan la apariencia al usuario de que los datos se encuentran localizados en la computadora que está utilizando.

,

2.1.1. Ventajas de las Bases de Datos Distribuidas

- Utilización compartida de los datos y distribución del control

El hecho de poder distribuir los datos permite que éstos sean colocados en donde se utilizan con mayor frecuencia; por lo tanto sólo se tendrán los datos necesarios para tener un mejor funcionamiento. Por ejemplo, en una empresa que está compuesta por varios departamentos (personal, ventas, almacén, proveedores), cada departamento sólo tendrá la información necesaria para su desempeño y actividad funcional.

Si los datos se colocan en donde más se usan, entonces se tendrá un mayor control sobre ellos. El contar con un mecanismo de comunicación permite que los datos puedan ser accesados de manera compartida por los usuarios. Por ejemplo, si el departamento de compras necesita saber la existencia de una pieza con el fin de determinar si se necesita realizu nuevos pedidos de ésta, es posible accesar los datos del departamento de almacén para obtener la cantidad en existencia que se tiene de dicha pieza.

Si la información que se tiene es demasiada y no se dispone de espacio suficiente en una computadora, entonces ésta puede repartirse entre las computadoras que dispongan del espacio requerido para guardar la información.

- Fiabilidad y disponibilidad

Si una computadora falla, es posible que las demás puedan seguir trabajando; por lo tanto no se necesita parar el sistema para corregir el error y se puede continuar con el trabajo como si todo estuviera correcto.

Cuando se está realizando una operación sobre un conjunto específico de datos, y ocurre una falla en una computadora que contiene datos del conjunto en el cual se efectúa la operación, puede ser posible que la ejecución de ésta continúe debido a que probablemente en otra

8

i

CAPITULO i CONCEPTOS SOBRE BASES DE DATOS DlSTRIBüiDAS

computadora que está trabajando correctamente esté una parte de los datos del conjunto que se necesitan para dar la respuesta. Por ejemplo, si un archivo se encuentra repartido en dos computadoras A y B, y desde otra computadora C se realiza una búsqueda de un registro sobre este archivo y ocurre una falla en la computadora B, la operación de búsqueda continuará aunque no toda la información del archivo esté disponible, de tal suerte que puede suceder que en la computadora A se encuentre el registro que necesita. Esto se puede realizar gracias a que se pueden distribuir los datos. En otras condiciones esto no sería posible debido a que cualquier falla ocurrida hm'a que todo el sistema se parará.

Cuando se lleva a cabo una operación sobre un conjunto de datos y existe una falla en una computadora en la cual esté contenida parte de la información del conjunto, es posible que una vez que se recupere de ese falla, se continúe con el proceso para concluir la operación.

- Agilización del procesamiento de consultas

Si una consulta realizada en una computadora involucra datos que se encuentren localizados en otro lugar, puede ser posible dividir la consulta en varias subconsultas, de tal forma que cada subconsulta se ejecute en el sitio en el que se encuentra el conjunto de datos que la satisfagan. En este caso sólo se enviarán a la computadora que realizó la petición los datos que cumplan cada subconsulta; evitando así la tarea de traerse de cada computadora todos los datos al lugar en donde se realizó la petición, y realizar el proceso de selección de los datos que cumplan la condición. Efectuando de esta forma una consulta, se logra dar una respuesta de manera más rápida y eficiente.

2.2. Sistema Administrador de Bases de Datos Distribuidas i

Un sistema administrador de bases de datos distribuidas (SABDD) es el "software" que administra la base de datos, el cual proporciona los siguientes servicios:

- Almacenar la información de las bases de datos.

- Mantener la seguridad en la base de datos por medio de restricciones de integridad y de proveer los respaldos necesarios para la recuperación de fallas.

- Ofrecer una interfaz pm, que los usuarios puedan accew las bases de datos.

El principio fundamental de un SABDD es que deberá comportarse como si fuera un sistema no distribuido; es decir, crear la ilusión de. que toda la base de datos se encuentra en el lugar en el que se está trabajando.

9

CAPITULO 2 CONCEPTOS SOBRE BASES DE DATOS DlSTRlBUmAS

De acuerdo con Date, existe una serie de doce reglas establecidas para lograr este objetivo, las cuales se describen a continuación:

1.

2.

3.

4.

5.

6.

7.

8.

Autonomía Local. Esta regla establece que todas las operaciones efectuadas en una computadora sólo son controladas por ésta. N h p ~ computadora dependerá de otra para su funcionamiento, de lo contrario una computadora podría ser incapaz de trabajar, aunque no tuviera ningún problema.

Independencia de un sitio central. Todas las computadoras deben ser tratadas por igual, ninguna es más necesaria que otra. En otras palabras no debe haber dependencia de un sitio central maestro para obtener un servicio central.

Operación continua. El sistema nunca deberá pararse para realizar alguna función planeada. Por ejemplo, el hecho de anexar otra computadora no debería ser motivo para parar el sistema.

Transparencia de locahción. Para hacer uso de los datos no es necesario que los usuarios sepan dónde están localizados físicamente y especificar su localización. Para ellos debe ser irrelevante donde se encuentran.

Transparencia de fragmentación. Se tiene fragmentación de datos si es posible dividir una relación en partes con propósitos de almacenamiento. Por ejemplo cuando una tabla es demasiado grande y no hay espacio suficiente para su almacenamiento en una computadora, puede ser posible su división y almacenar en varias computadoras partes de su información. Por lo tanto, esta regla especifica que los usuarios pueden hacer uso de los archivos como si no estuvieran divididos; es decir, crear la ilusión como si el archivo utilizado estuviera completo.

Independencia de repetición. Se cuenta con repetición de datos cuando se tienen varias copias de una relación. Por lo tanto, esta regla indica que los usuarios hacen uso de los archivos como si sólo existiera una sola copia del archivo.

Procesamiento distribuido de consultas. El sistema debe contar con un optimizador de consultas, cuya función es la de determinar una estrategia de ejecución para dar una respuesta más rápida y efectiva a UM consulta, de tal forma que se reduzcan los accesos a disco y se minimice el uso de los recursos del sistema (transmisión de datos entre las computadoras).

Manejo de transacciones distribuidas. Las transacciones que actualizan datos de varias computadoras deberán ejecutarse como si fueran transacciones seriales y deberán dejar la BDD en un estado congruente si ocurriera una falla.

10

C A P m 1 CONCEPTOS SOBRE BASES DE DATOS DlSTRIBUIDAS

9. Independencia con respecto ai equipo. El sistema debe poder ejecutarse en diferentes tipos de equipo.

independencia con respecto al sistema operativo. El sistema debe poder ejecutarse bajo diferentes clases de sistemas operativos.

Independencia con respecto a la red. El sistema debe poder ejecutarse bajo diferentes tipos de redes.

Independencia con respecto al SMBD. Debido a que se tienen varias computadoras debe ser posible que en cada una de ellas exista un SMBD diferente, de tal forma que se tenga una soia interfaz.

10.

11.

12.

2.3. Las Bases de Datos Distribuid& y el Modelo Relaciona1

El modelo relacional se ha destacado por su uso en aplicaciones comerciales de procesamiento de datos. El modelo relacional representa un sistema de bases de datos de una forma abstracta, es decir que el usuario percibe un conjunto de relaciones normalizadas de diversos grados que varían con el tiempo.

El modelo relacional se utiliza para representar y manipular datos, encargándose de tres aspectos de éstos, que son los siguientes:

1. Estructura 2. integridad 3. Manipulación

A continuación se explican cada uno de estos aspectos:

El primer punto se refiere a la forma de representar los datos, para lo cual se han establecido los términos que se explican enseguida. Antes de presentar los conceptos de los términos se muestra una equivalencia de éstos con términos utilizados comúnmente.

1.

.I 11

CAPlTVLO 2 CONCEPTOS WBRE BASES DE DATOS DlSTRlBUmAS

Dominio. Es el conjunto de valores atómicos que puede tomar un atributo. Entendiéndose por atómico la unidad minima que no es divisible.

Relación. Una relación sobre un conjunto de dominios D1, D2, ..., D, (no necesariamente distintos), se compone de dos partes: un encabezado y un cuerpo. El encabezado está formado por un conjunto fijo de atributos, en términos más concretos por pares atributo- dominio. El cuerpo está formado por un conjunto de tuplas. En donde cada tupla consta de un conjunto de pares atributo-valor.

El número de tuplas de una relación se conoce como cardinal¿dad. Al número de atributos de una relación se le conoce como gmdo. La Figura 2.1 muestra los elementos de una relación.

NOMBRE CIIUACION CIUDAD

claw primaria

,io.

C a r d I ” a I I d

d , a

\\ // Atrlbulos

Grado

Figura 2.1. Elementos de UM Relación

2. Este punto se refiere a que los valores de los datos defindos sobre las relaciones deben tener sentido. Si pensamos que estos valores están representando parte del mundo real, entonces deben estar acordes con éste. Por lo tanto, se deben establecer restricciones sobre los datos, para tener congruencia con la realidad. A estas reglas se les conoce como reglas de integridad y están relacionadas con los siguientes términos: llave primaria y llave foránea.

Llave primaria. En términos generales es un identificador único para una relación. Es posible que una relación S tenga más de un identificador único, por lo tanto se dice que se tienen varias llaves candidatas, a la llave elegida de entre éstas se le llama llave primaria y a las otras se les denomina llaves altemativas.

12

CAPITUU> 2 CONCEPTOS SOBRE BASES DE DATOS DISTRIBUIDAS

Llave foránea. En términos informales se dice que una llave foránea es un atributo de una relación R2 cuyos valores deben ser iguales a los de la llave primaria de una relación R1 (donde R1 y R2 no necesariamente son distintas).

Este punto trata sobre la forma de operar y manipular sobre las relaciones y sus datos. Para poder realizar'éstas se cuenta con un conjunto de operadores de alto nivel que operan sobre las relaciones, al cual se denomina álgebra relaeional; en donde cada uno de estos operadores toma como entrada una o dos relaciones y produce otra relación como resultado. Según Codd, existen ocho operadores para el álgebra relacional, los cuales se describen a continuación:

Restricción. Obtiene de una relación un conjunto de tuplas especificadas.

Proyección. Obtiene atributos específicos de una relación.

División. A partir de dos relaciones A y B, se construye una relación formada p r todos los valores de un atributo de la relación A que concuerdan con los valores de todos los atributos de la relación B.

Reunión. A partir de dos relaciones, se construye una relación que contiene todas las posibles combinaciones de tuplas, una de cada una de las dos relaciones, tales que las dos tuplas en una combinación dada cumplan una condición.

3.

A X Y

............................................. ~~. ReunYn

b2 c2 a2 b l c1

b3 c3 : a3 b2 Q

...................... .. .......................... .

Figura 2.2. Operadores Relacionales Especiales

13

.

CAPiTULO 2 CONCEPTOS SOBRE BASES DE DATOS DlSTRlllUIDAS

Unión. A partir de dos relaciones, se obtiene otra relación formada por todas las tuplas que aparezcan en cualquiera de las dos relaciones.

Producto. A partir de dos relaciones, obtiene otra relación la cual está formada por todas las combinaciones posibles de tuplas de ambas relaciones.

Intersección. Se obtiene una relación formada por las tuplas que aparezcan en las dos relaciones.

Diferencia. Se obtiene una relación formada por las tuplas que aparezcan en una relación, pero que no se encuentren en la otra.

............... : A g : 5

. . . . . . . . . .

Union 1 Interaeoción

...........

....................... ; c qp .... ...............

Produoto

Oilerencia (A - 6) b Figura 2.3. Operadores sobre Conjuntos Tradicionales

De acuerdo con lo anterior, se puede definir de manera informal que una base de datos relacional (BDR) es aquélla que es percibida por el usuario como una colección de relaciones sobre las cuales se pueden efectuar operaciones que dan como resultado nuevas relaciones.

2.3.1. SQL Basado en el Modelo Relaciona1 como Lenguaje de Consulta en un SMBDD

Los lenguajes formales proporcionan una notación concisa para la representación de una consulta. Sin embargo, los sistemas necesitan un lenguaje que sea amigable para el usuario. Por

14

. . .-

CAPITULO 2 CONCEPTOS SOBRE BASES DE DATOS DlSTRIBUIDAS

tanto, existía la necesidad de crear un lenguaje que permitiera una interfaz sencilla con la cual el usuario pueda explotar las bases de datos. De esta necesidad surge SQL.

La versión original de SQL fue desarrollada en el San Jose Research Laboratory de IBM. Este lenguaje, originalmente llamado Sequel, fue implementado como parte del proyecto del sistema R en los primeros años de la década de los setenta.

SQL se ha establecido como el estándar internacional oficial para el manejo de bases de datos relacionales @DR) por IS0 (International Organization for Standarization). Con este lenguaje se formulan operaciones relacionales, mediante las cuales se definen y manipulan datos en forma relacional en una BDR.

El lenguaje SQL está constituido por varias partes:

Lenguaje de definición de datos (LDD). Está constituido por instrucciones para definr esquemas de relación, eliminar relaciones, crear índices, y modificar esquemas de relación.

Lenguaje de manipulación de datos interactivo (LMD). Es un lenguaje de consultas basado en el álgebra y cálculo relacional de tuplas. Incluye instrucciones para insertar, borrar y modificar tuplas de la base de datos.

Lenguaje de manipulación de datos intercalado. La forma intercalada de SQL está diseñada para usarse dentro de los lenguajes de programación de propósito general tales como Cobol, Pascal, Fortran, PL/I, y C, con el fin de poder explotar características de estos lenguajes con las cuales no cuenta SQL.

Defdción de vistas. Se incluyen instrucciones para definir vistas.

Autorización. El LDD incluye instrucciones para especificar derechos de acceso a relaciones y vistas.

Control de transacciones. Se incluyen instrucciones para determinar el comienzo y final de transacciones.

2.4. Panorama General sobre el h e s o de Optimización de Consultas

Cuando se realiza una consulta a una base de datos usando un lenguaje de consultas de alto nivel como SQL, la ejecución interna de ésta se puede llevar a cabo siguiendo UM estrategia, la cual permite que la respuesta a la consulta sea lo m á s rápida y efectiva posible, y que además el uso de los recursos (memoria principal, memoria secundaria y uso de la red) se minimice.

15

. . . . .-

CAPITULO 2 CONCEPTOS SOBRE BASES DE DATOS DISTRIBUIDAS

En un SMBDD, al programa que realiza la estrategia de ejecución de una consulta se le denomina optimizaúor. Dada la complejidad que se presenta para encontrar la estrategia, debido a que se deben considerar varios elementos tales como tamaño de la tabla, índices definidos, organización física de los datos, etc., el objetivo del optimizador es tratar de buscar el mejor de los planes de ejecución para dar la respuesta.

El propósito de esta sección es presentar un panorama general sobre la forma en que se lleva a cabo el proceso de optimización.

2.4.1. h-oceso General de Optimización

De acuerdo a la referencia [6], existen varias etapas mediante las cuales es posible determina la estrategia de ejecución para una consulta. A continuación se describen dichas estrategias.

- Transformación de la consulta

Este es el primer paso que' realiza el optimizador, la consulta es transformada a alguna representación interna, la cual es más fácil que sea entendida y manipulada por la computadora, debido a que esta conversión e l i a consideraciones propias del lenguaje de consulta y del lenguaje d i t r ión en que se realiza la petición (tales como la sintaxis del lenguaje de consulta, sintaxis del lenguaje anfitrión, etc.).

Para lograr io anterior, la consulta se representa mediante una forma abstracta de un árbol o un grafo, las cuales se denominan árbol de consulta y grafo de consulta respectivamente. Estas formas de representación son semánticamente equivalentes a la consulta solicitada.

Un árbol de consulta es aquél que representa una expresión del álgebra relacional, en donde las hojas del árbol representan las relaciones y los nodos internos representan las operaciones. Por ejemplo, la Figura 2.4 muestra una representación de un árbol de consulta para la siguiente consulta en SQL

SELECT S.SNombre FROM S, SP WHERE S.SNo = SP.SNo AND SP.SNo = 'S2'

16

.I- . . . . . .~

CAPiTliLO 2 CONCEPTOS SOBRE BASES DE DATOS DISTRIBUIDAS

Resultado

Proyectar (SNombre)

I ........... Nodos ~ Re;;i& SP,SNo=,S2')

Internos . . . . . . . . . . . . . . . . . . . . . .

I Juntar (S.SNo = SPSNo)

/\ Hojas s SP

Figura 2.4. Arbol de Consulta

Para lograr la representación de la consulta en esta forma, ésta se analiza de manera semejante como la realizan los compiladores; es decir, primero se efectúa un análisis léxico en el que se identifican los componentes del lenguaje (token), el cual es realizado por el "saner"; posteriormente se realiza el análisis sintáctico para determinar si la consulta está formulada de acuerdo a las reglas de la gramática del lenguaje, esta etapa es efectuada por el "parser"; por último se efectúa el análisis semántico para determinar si tiene sentido la forma en cómo está expresada la consulta.

Para una consulta se pueden originar diferentes expresiones del álgebra relacional, las cuales son equivalentes a la consulta original. Al ser ejecutadas, éstas producen exactamente el mismo resultado, la diferencia entre ellas es la forma en que se ejecutan las operaciones (join, selección, proyección, etc.).

Dado lo anterior, en esta etapa no se realiza ningún tipo de optimización; lo que se busca es encontra una representación general de un árbol de consulta para la petición, y que posteriormente sea analizado para determinar la estrategia de procesamiento a seguir.

-Conversión a una forma canónica

Una vez que se tiene una representación general para la consulta, se puede iniciar el análisis de ésta, con el fin de encontrar una representación que sea mejor que la original, la cual puede ser ejecutada más eficientemente.

17

CAPITULO 2 CONCEPTOS SOBRE BASES DE DATOS DISTRlBUIDAS

Es en esta etapa donde el optimizador comienza su trabajo, mediante el análisis de la estructura de la representación de la consulta, identificando las tablas de la base de datos que están participando en ésta en busca de elementos (índices, tipos de índice, cardinalidad, distribución de los datos, etc.) defindos sobre éstas, que permitan recuperar los datos más rápidamente. Para ello el optimizador utiliza el diccionario de datos para revisar el estado actual de la base de datos con el fm de buscar cuáles de los elementos de las tablas pueden ser útiles para efectuar la estrategia de ejecución.

Otro aspecto que el optimizador debe considerar en esta etapa es la forma de la representación de la consulta. Es decir, el optimizador debe analizar qué tipo de operaciones (reunión, unión, interseccción, etc. ), condiciones ( and, or, etc.) y operadores relacionales (e , =, >, etc.) involucra la consulta con el fin de determinar cuáles reglas del álgebra relacional pueden aplicarse al árbol de la consulta para ser transformada en otra expresión que sea más eficiente. Esta etapa se ejecuta repetidamente hasta que se logra tener la mejor versión de ejecución para la expresión original.

- Selección y ejecución de la estrategia

Cuando se ha obtenido la versión final de la consulta, el optimizador debe entonces tomar la decisión acerca de la manera exacta de ejecución de ésta, y la selección especifica de los elementos definidos sobre las tablas, o si se necesita definir algún otro elemento a las tablas (definición de índices temporales) para la recuperación de los datos. Un punto importante en la selección de la estrategia es el número de accesos a disco que se realicen sobre la tabla para obtener los registros.

Dentro de esta etapa, se determina el orden en el que se procesarán las tablas y renglones participantes. Por ejemplo, si hemos elegido un índice, se tiene que determinar el tipo de búsqueda que se realizará sobre éste (búsqueda descendente o ascendente).

Para llevar a cabo lo anterior, el optimizador debe contar con rutinas en las que se implementan métodos y algoritmos para ejecutar los diferentes tipos de operaciones del álgebra relacional que se vayan presentando en la ejecución de la estrategia.

18

CAPITULO 3

CONCEPTOS Y TECNICAS PARA LA INDIZACION

Los renglones que satisfacen las condiciones de búsqueda en una consulta generalmente son una pequeña parte del total de los renglones de la tabla. Asi que leer cada uno de éstos y comprobar que satisfagan la condición resulta ineficiente, debido a que se necesitan realizar demasiados accesos a disco, lo que implica demasiado tiempo para el procesamiento de una consulta. Uno de los objetivos de un SMBDD es disminuir los tiempos de acceso a disco de tal forma que se pueda tener acceso a los renglones de una forma directa.

Para lograr la disminución de acceso a disco, existen diferentes técnicas cuyo objetivo es ordenar los datos para agilizar su recuperación. Una de estas técnicas es asociar estructuras adicionales a los archivos de las tablas, en donde hies estructuras ordenan de cierta forma los datos, lo cual permite localizar directamente los renglones.

El presente capítulo describe conceptos básicos sobre índices y técnicas de indización.

19

CAPITULO 3 COhCEPTOS Y TECNlCAS PARA LA WDIZACION ,

3.1. Indización

La indización es una técnica de estructura de almacenamiento que asocia una estructura adicional al archivo de la tabla denominado índice.

Un índice es un archivo que funciona de manera semejante a un catálogo de una biblioteca, el cual está ordenado alfabéticamente ya sea por autor, título, materia, etc. En estas circunstancias que cuando se necesita im libro que se encuentra en una posición determinada en un anaquel, la búsqueda del libro no se realiza directamente sobre éste, se busca sobre el catálogo, el cual (al estar ordenado) permite un búsqueda más rápida del libro. Una vez encontrado, la tarjeta del catálogo en algunos de sus datos indica la posición exacta del libro en el anaquel. Por lo tanto la ventaja es que no se necesita recorrer el anaquel de principio a fin para localizar el libro. su acceso es directo.

Un índice es un tipo de archivo almacenado, en el que cada renglón de éste se compone de dos valores:

- Un dato. Es el valor de alguno(s) de(1os) atributos de la tabla. A esta(s) columna(s), se ie(s) denomina campo indizado.

Un apuntador. Este identifica la posición del renglón dentro del archivo de la tabla que contiene el (los) valor(es) del campo indizado.

AI archivo de la tabla cuyos valores de las columnas forman parte del índice, se le conoce

-

como archivo indizado.

3.2. Utilización de Indices

De acuerdo a la cantidad de renglones a los que se tenga acceso por medio del indice, éste se puede utilizar para las siguientes operaciones:

- Acceso secuencial. Se tiene un acceso a todos los renglones del archivo indizado, con respecto al orden defiido por el valor del campo indizado. Con &te tipo de acceso se pueden realizar consultas tales como "Encontrar todos los proveedores cuya ciudad sea igual o mayor aifabéticamente que Cuautla".

Acceso Directo. El índice se utiliza para tener acceso a uno o unos cuantos renglones del archivo indizado. Por ejemplo cuando se realizan consultas en las que se desea listar nn conjunto de valores, tales como "Encontrar todos los proveedores cuya ciudad sea igual a Culiacán".

-

20

..

CAPITULO 5 CONCEPTOS Y TECMCAS PARA LA INDIZACION

- Prueba de existencia. Otra forma de hacer uso del índice, es utilizarlo de manera directa, sin tener que realizar ningún acceso al archivo de la tabla, para obtener una respuesta a cierto tipo de consultas, las cuales generalmente son pruebas de existencia. Por ejemplo "¿Existe algún proveedor en Pachuca?".

3.3. Tipos de Indices

Esta división de tipos de índices se da de acuerdo a cómo se está asociado el campo apuntador del renglón del índice, con los renglones del archivo indizado.

- Indice denso. Por cada valor del campo dato de cada uno de los renglones del índice se asocia un solo apuntador a cada renglón del archivo indizado, de tal forma que para cada valor del campo indizado de la tabla, existe un renglón en el índice. Una desventaja de estos índices es que van creciendo al igual que el archivo de la tabla, por lo que son demasiado grandes, de tal forma que para su revis ión3 se requiera demasiado tiempo. La Figura 3.1 muestra un ejemplo de este tipo de índice.

ARCHIYO PARA L4 TAB= DEPCSKTO

I I I I

Figura 3.1. Indice Denso para el Archivo Depósito

- indice disperso. Sólo existen unos cuantos renglones en el índice para algunos valores de los campos indizados de la tabla; de manera que, cuando se necesita buscar un renglón de la tabla, se tiene que buscar sobre el índice un valor mayor o menor al valor del campo del renglón deseado. UM vez localizado este valor, el renglón deseado se comienza a buscar sobre la tabla a partir de la posición dada por el campo apuntador del índice, siguiendo los apuntadores del archivo secuencialmente hasta encontrar el renglón

I 21

I CENTRO DE INFORMCION C E N I D E V

CAPITULO 3 CONCEPTOS Y TECNiCAS PARA LA INDlZACION

que se busca. Dada su característica del número de renglones que se almacenan, tiene la ventaja de que para su almacenamiento se necesita poco espacio y que la búsqueda de los valores se efectúa más rápidamente. La Figura 3.2 muestra un ejemplo de este tipo de índice.

ARCHIVO PARA LA TABLA DEPDSÍIU

Figura 32. Indice Disperso para el Archivo Depósito

3.4. Archivos Indizados de Arboles B+

Existen varias técnicas para disminuir el número de accesos a disco. La elección de una o varias de ellas depende de la aplicación específica de la base de datos; por lo tanto, para determinar cuál técnica usar, se requiere evaluar los siguientes puntos:

- Tiempo de acceso. Se refiere al tiempo que se utiliza para encontrar un dato determinado.

Tiempo de inserción. Este se refiere al tiempo utilizado para buscar la posición correcta del nuevo valor sobre el índice, así como el tiempo ocupado para actualizar el archivo de indización.

Tiempo de e l i a c i ó n . El cual incluye el tiempo utilizado para buscar el valor a borrar sobre la estructura y el tiempo para actualizar la estructura del archivo indizado.

Espacio extra. Se refiere al espacio utilizado para almacenar la estructura adicional.

-

-

-

22

. . -. . . . . . . . .

CAPITULO 3 CONCEPTOS Y TECNiCAS PARA LA INDIZACION

De acuerdo a lo anterior, se ha observado que los índices de árbo1.B' ofrecen un muy buen desempeño, sobre todo en los tiempos de inserciones y eliminaciones. Por tanto, en la mayoría de los sistemas relacionales comerciales, se incluye este tipo de índices como la mejor forma de estructura de almacenamiento.

Antes de empezar la explicación de lo que es un árbol B+, es necesario mencionar por qué el uso de esta estructura. Como sabemos, un índice se crea para evitar una búsqueda secuencial sobre la tabla. Sin embargo, sigue siendo necesaria una búsqueda secuencial sobre el índice, de tal forma que el tiempo de revisión sobre éste se va incrementando a medida que va creciendo el archivo indizado. Por lo tanto, se observa que la búsqueda sobre el índice provoca el mismo problema que la búsqueda secuencial sobre la tabla.

UM forma de solucionar este problema, es tratar a un índice como cualquier otro archivo de tabla al que se le puede crear un índice; es decir, crear un índice de índice. Por lo anterior, podemos pensar que se tienen varios niveles de índices, en donde cada nivel debe ser un índice disperso del nivel inferior. La razón de que los niveles superiores sean índices dispersos es evitar el problema de crecimiento en proporción igual al crecimiento de los archivos del nivel inferior.

3.4.1. EStniCtUra y Elementos de un Indice de Arb1 B+

Un índice de este tipo toma la forma de un árbol B+. Un árbol B+ de orden N muestra las siguientes propiedades:

- Todas las páginas, exceptuando la página raíz tienen al menos N elementos.

- Cada página tiene a lo m á s 2N elementos.

- La raíz tiene por lo menos dos hijos.

- Todas las páginas hoja se encuentran en el mismo nivel.

- Un nodo sin hojas con N llaves tiene N+l hijos.

3.4.1.1. Elementos de un Arbol B+

- Elemento. Este es la unidad básica de un árbol B+. Esta unidad es la que permite referencia la posición física de los renglones del archivo indizado. Se compone de tres elementos básicos:

23

CAPITULO 3 CONCEPTOS Y TECNICAS PARA LA INDIZAClON

Llave. Contiene el (los) valor(es) de la(s) columna(s) indizada(s) de la tabla; es decir, éste es el campo dato del índick.

Apuntador. Este elemento contiene la posición física del renglón indizado sobre la tabla, es el apuntador del índice.'

Página de referencia. Este elemento es la liga dentro del árbol B+ para localizar aquellas llaves que son mayores, en cuanto a valor, al campo llave del elemento.

Pagina. Esta unidad es la estructura (nodo) con la cual se forma el árbol B+, y está formada por los siguientesl elementos:

Un'arreglo. El cual contiene un número M de elementos. El número máximo de elementos contenido en éste, es exactamente dos veces el valor del orden del árbol; es decir, si se tiene un árbol de orden tres entonces el número máximo de elementos en el arreglo será seis. El número máximo de elementos que puede tener una página se conoce como "famalío de lapágina". Las valores de las llaves de cada elemento del arreglo se guardan en orden creciente de amba hacia abajo.

Contador. Este elemento contiene el número de elementos activos que existen en el arreglo. El valor de éste varia entre N y ZN, es decir, el valor mínimo que toma es el valor del orden del árbol y su valor máximo es dos veces el orden. Su valor indica cuál es la posición en el arreglo del último elemento activo en la página.

Página extra de referencia. Actúa como liga en el árbol B+ para indicar en qué página se encuentra el arreglo en el que están las ilaves más pequeñas, en cuanto a valor, a las llaves del arreglo de ésta. 'Por ejemplo, si en el arreglo de la página se encuentran los valores para las llaves de X,Y y 2, entonces el valor de la página de referencia es la página donde están las llaves más pequeñas que X. La Figura 3.3. muestra la estructura

-

una página. l

24

- . .

CAPITULO 3

. . c

CONCEPTOS Y TECNICAS PARA LA WDIZACION

I Figura 3.3. Estructura de UM Página

Existen tres tipos diferentes de páginas en el árbol B+: página raíz, páginas internas y páginas hoja. Tanto la página raiz como las páginas internas tienen UM página hija para cada elemento del arreglo. Las páginas hoja no tienen hijas.

La página raíz puede contener un solo elemento activo dentro del arreglo, mientras que todas las demás páginas deben de tener como mínimo la mitad de elementos activos. Las páginas internas siempre tendrán entre (tamaño de la página + 1) y (tamaño de la página + 1) apuntadores (página de referencia) a otras páginas. Esta característica permite que el árbol este balanceado. Las páginas' hoja se encuentran al final del árbol y no tienen apuntador (página de referencia) a una página. La Figura 3.4 muestra la estructura de un árbol B+.

25

_. .. . . 1;

CAPlTULO 3 CONCEPTOS Y TECNICAS PARA LA WDIZACION

j 0 0

Figdm 3.4. Estructura de un Arbol B+

3.4.2.2. Búsqueda, Inserción y Borrado sobre un Artmi B+

En esta sección se describe cómo se efectúan las operaciones de búsqueda, inserción y borrado sobre un árbol B+, así como algunos ejemplos ilustrativos para éstas.

En esta sección se hace referencia a la búsqueda binaria. Por lo tanto, es necesario recordar que ésta se realiza sobre una estructura, en la cual se conoce el número de elementos que la componen, y por ende se puede saber la posición de éstos. Por otra parte, el resultado obtenido al efectuar este proceso arroja dos valores: el primero indica si la búsqueda tuvo éxito o no, el otro nos indica un valor de posición; para el caso en que la búsqueda fue exitosa, éste indica la posición en la que está localizado ese valor en la estructura; en caso contrario indicará

26 I ~

CAPITULO 3 CONCEPTOS Y TECMCAS PARA LA INDIZACION

la posición en la que debe estar colocado el valor buscado sobre la estructura.

3.4.2.2.1. Búsqueda

Una búsqueda para un valor dado de una llave sobre el árbol B+, se inicia desde la página raíz, donde el valor de la llave se compara con el valor de cada una de las llaves de cada elemento del arreglo, mediante & búsqueda binaria (dado el orden en el que están guardadas

Si en la primera comparación que se realiza, el valor de la llave buscada es menor que el valor de la llave del elemento del arreglo, entonces significa que la llave que se está buscando tiene un valor menor a todos los valores de la llave para ese arreglo. Por lo tanto, la página en la que se continuará la búsqueda es la página indicada por la "página extra de referencia" de la página que se está examinando. De acuerdo a esto, observamos que para este caso no se realiza ninguna búsqueda binaria sobre el arreglo de esta página.

Por ejemplo, si la llave a ! buscar es C (ver Figura 3.4), cuando se efectúe la primera comparación con el elemento del keg lo de la página (en este caso la página raíz, página siete), el valor de C es menor que el valor de M, por lo tanto, la siguiente página en la que se continuará la búsqueda será la página número 2 (valor de la página extra de referencia de esa página). En esta página, al realizar la primera comparación, el valor de la llave buscada es mayor que el valor de la llave del arreglo; por lo tanto, se continúa la inspección binaria sobre el arreglo de esta página hasta que se encuentre el valor.

las llaves). i I

I

Para el caso contrario, donde el valor de búsqueda es mayor que el valor del elemento del arreglo en la primera comparación, entonces se procede a efectuar el proceso común para la búsqueda binaria. El resultado de,Ia búsqueda puede arrojar dos resultados:

Primero. La búsqueda del elemento buscado tuvo éxito, lo que significa que en la página donde se efectúa la inspección se encuentra el valor buscado; por la tanto, el valor de la llave buscada se encuentia en el elemento indicado por la posición resultante en el proceso de la búsqueda biiiaria.

Segundo. No se encontró'el valor de llave buscado, lo que significa que este valor se encuentra en otra página, la cual será determinada por el valor que contenga la página de referencia del elemento del arreglo indicado por la posición resultante del proceso de inspección de la búsqueda binaria.

~

Veamos el siguiente ejemplo. Supóngase que se desea buscar la llave W (ver Figura 3.4). Al efectuar la primera comparación se observa que el valor de M es menor que el valor de la

I 27

CAPITULO 3 CONCEPTOS Y TECNiCAS PARA LA WDIZAclON I

llave buscada. Por consiguiente, se efectúa el proceso de búsqueda binaria, para el cual no se tendrá éxito, lo que indica que en el arreglo de elementos de esta página 7 no se encuentra la llave de búsqueda. Sin embargo, la posición resultante del proceso de búsqueda (valor 1) indica que en la página de referencia del~elemento 1 se debe continuar la búsqueda (página número 8).

Al efectuarse la búsqueda de la llave W sobre la página 8, se tiene éxito en la búsqueda; por lo que el valor arrojado de posición durante la inspección de búsqueda binaria (valor de 2), contiene el valor de la llave buscada, es decir el elemento 2 del arreglo.

3.4.2.2.2. Inserción I

Cuando se desea insertar una llave se realiza una búsqueda, como se describió en la sección anterior, sobre el árbol para determinar si existe o no el valor que se quiere insertar. Si la llave se encuentra, se detiene el proceso de inserción; de lo contrario se indicará el número de la página donde debe colocarse dicho valor. Para este caso se tienen dos resultados:

Primero. Si la página en la que se debe insertar no está llena, entonces el valor se inserta en ésta y se hace un reordenamiento de los elementos del arreglo de esta página. El valor de Contador de la página se incrementa en uno. Caso a) de la Figura 3.5.

Segundo. Si la página está ilena (contiene 2N elementos), entonces la página se divide en dos (esto es se crea UM nueva página), en las cuales se distribuyen los elementos (2N+1). En donde los elementos N/Z- 1 a N del arreglo se colocan en la nueva página, y los demás (1 a N/2-1) se quedan en la página que se encontró llena. El valor de Contador de página para ambas será el mismo. El elemento N/2 (elemento del centro) se mueve a un nivel superior (página madre). Caso c) de la Figura 3.5.

La forma de realizar este proceso hace que se conserven todas las propiedades del árbol

I

I B+.

Si la página raíz está llena v se necesita insertar un nuevo elemento. se efectúa el uroceso anterior de crear una nueva pág que la altura del árbol crezca u

~

lil. Lo interesante de que la página raíz se divida, es que hace nivel más. Caso c) en la Figura 3.5.

28

CAPITULO 3 CONCEPTOS Y TECNlCAS PARALA INDlZAClON

I

a) JnseAión de M m ELI I

bi Inserción de J

e) Inserción de ,IT[ I

Figura 3.5. Inserción en un Artmi B+

3.4.2.2.3. Borrado I

Cuando se necesita e l i i h una llave, se realiza una búsqueda de ésta sobre el árbol, la cual indicará el número de página en la que se debe efectuar el borrado de la llave. Si la llave que se desea borrar se localiza en una página hoja, no existe tanto problema para su borrado. El problema se compiica cuando se e l i i n a una llave de cualquier otra página que no sea hoja, debido a que se necesita guardar de alguna forma la página a la cual se hace referencia en el valor del campo "página de referincia" de este elemento.

Para solucionar el probiev de la llave que se va a borrar, ésta se reemplaza por otra llave, la cual es uno de los dos valores de llave contiguos a la llave borrada que se encuentran en una página hoja, en donde el valor más pequeño de la página izquierda contigua a ésta es un valor mayor al valor borrado, y el valor mayor de la página derecha contigua tiene un valor menor a la llave borrada. Por io tanto, se conservará la propiedad de orden que debe guardar el arreglo de la página en la que se 1 efectuará el borrado.

29

CAPITULO 3 I CONCEPTOS Y TECMCAS PARA LA INDIZACION I

De la página elegida cuyoi valor será remplazado por la llave borrada, se disminuye en 1 el total de elementos del arreglo de ésta, por lo que se debe verificar que el número de elementos sobre la página cumplalla condición de que por lo menos debe tener N elementos. Si esta restricción no se cumple, entonces se toman elementos de la página vecina (una página que se encuentra en el mismo nivel, pero que tiene diferente padre), para lo cual se presentan los siguientes casos (suponiendo que la página E es la página elegida y la página vecina sea F):

Caso 1. Si el total de elementos entre las dos páginas es 2N, entonces los elementos de ambas se colocan en una sola página, agregando el elemento intermedio de la página madre sobre la página E. Por lo tanto se desecha la página F.

Caso 2. Si el total de elementos entre las dos páginas es mayor que 2N, entonces se distribuyen los valores de los elementos entre las dos, por lo que ambas quedan con el mismo número de elementos.

I I

3.4.2.3. Defmición de Indices sobre las Tablas

Existen dos formas de declarar índices sobre los archivos de las tablas. La primera de ellas se realiza de forma explícita, esto significa que el programador de aplicaciones es quien decide cuándo crear y borrar esta estructura adicional a la tabla; para ello utiliza las instrucciones de defición de datos de SQL. I - CREATE INDEX la cual ~ tiene la siguiente sintaxis:

CREATE INDEX <nombre-índice> ON <nombre-tablu> (<lista-columnas>) ~

donde <lista columnas> está formada por las columnas de la tabla que constituyen la clave de búsqueda para el índice.

DROP INDEX la cual presenta la siguiente defición: - ~

DROP INDEX <nombre-índice> I

Estas instrucciones son las Ünicas que proporciona SQL para hacer referencia directa sobre la los índices. Las demás instrucciones evitan hacer referencia a éstos, de tal forma que

explotación de los índices se deja al optimizador de consultas.

La segunda forma se realiza implícitamente: los archivos de índices se crean de forma transparente al programador de aplicaciones (en el nivel interno). La instrucción de definición de datos "CREATE TABLE" es #la que permite llevar a cabo esta tarea, cuando se establecen ciertas restricciones de integridad sobre la tabla creada, tal como "PRMARY'KEY" la cual sirve

!

30 I

. .

CAPITULO 3 I CONCEPTOS Y TECNICAS PARA LA WDlZACION

para deftnir una llave primaria sobre la tabla. I

Si partimos de que una llave primaria es un identificador único para una tabla; es decir, que no existen dos renglones en una tabla que tengan el mismo valor, entonces cada vez que se tenga que insertar un nuevo renglón en la tabla, se necesita realizar UM búsqueda sobre ésta del valor de la llave para ver que no exista. Una alternativa consiste en realizar un acceso secuencial sobre la tabla, pero se estarían efectuando una gran cantidad de accesos a disco. Como se ha mencionado anteriormente, el objetivo de un SMBDD es el de realizar el menor número de accesos, entonces una mejor alternativa consiste en construir una estructura de almacenamiento de índices para agilizar la búsqueda del renglón, evitando así demasiados accesos a disco.

I

Cuando declaramos una columna UNIQUE sobre la tabla, significa que los valores para esa columna no se repetirán. Como puede verse, se tiene un problema semejante ai de la declaración de UM llave primaria; por tanto para solucionar este problema, es necesario crear un índice al archivo de la tabla. I

De acuerdo con lo anterior, cada vez que se declaran estas restricciones en la instrucción CREATE TABLE, se asociará di estructura de índice a la tabla.

La existencia de estos índices, a diferencia de los índices definidos con CREATE INDEX (los cuales pueden ser borrados ed cualquier momento sin necesidad de borrar la tabla) dependen directamente de la existencia de ésta; es decir, al tiempo que se borra la tabla los índices dejan de existir, y no se pueden eliminar sin que se elimine la tabla.

31

1 PROCEDIMIENTO EvaluaSubcltas; 2 PARA j:=l A Totde- Subcltas HACER

16

4 SI Creaind ENTONCES 5 Cr&dTemp( TabMay or Card) 6 OpenFile(TabMenorCard) 7 PARA k=l A TotRgtos HACER

11 SI CumpCondAnd ENTONCES 12 AlmacenaRenglones(RengsActs) 13 FIN PARA 14 FiNPARA 15 FIN PROCEDIMIENTO

CAPITULO 4 PLANTEAMIENTO Y SOLUCION DEL PROBLEMA

de la tabla a la cual se le creará el índice, a la variable TabMenorCard se le da el nombre de la tabla de la cual se obtendrán los valores de columna que se buscarán sobre el índice creado y por Último a la variable TotRgtos se le asigna el número de renglones que tiene ésta.

En la línea 6 se activa el procedimiento OpenFile para abrir la tabla que no tiene índice definido, ya que de ésta se obtendrán los valores de llave a buscar sobre el índice. En la línea 8 el procedimiento Obtiene-valor obtiene el valor del operando izquierdo de la condición que se analiza. En la línea 11 el procedimiento RegisAbiertos se encarga de almacenar en la variable RengsActs el nombre de la tabla y la posición del renglón cuando éste no haya sido accesado anteriormente.

En la línea 12 el procedimiento CumpleCond realiza la evaluación de cada condición de la subconsulta. Si todas las condiciones se cumplieron la variable CumpCondAnd toma un valor verdadero. Las posiciones de los renglones que deben ser almacenados se obtienen de la estructura RengsActs.

En la línea 14 el procedimiento AlmacenaRenglones se activa cuando la variable CumpCondAnd tiene un valor verdadero, almacenando las posiciones de los renglones para los cuales alguna o algunas de sus columnas son solicitadas en la cláusula SELECT.


Una vez que se han determinado cuáles son los renglones de los que se deben obtener los valores de las columnas solicitadas en la cláusula SELECT, es posible obtener el contenido de la tabla derivada, mediante la ejecución del producto cartesiano entre los archivos que almacenan las posiciones de los renglones. Para ello se obtiene de cada archivo la posición del renglón, se accesa el renglón en la tabla correspondiente, se obtiene el valor de ia(s) columna(s) solicitadas en la cláusula SELECT y se almacena en un contenedor. Esto se repite tantas veces como archivos existan, del tal forma que ai final el contenedor almacena todos los valores de las columnas requeridas en la cláusula SELECT. La información almacenada en el contenedor se guarda en un archivo sin tipo (este archivo representa la tabla derivada). El tamaño del registro del archivo es igual a la suma del tamaño de cada columna de la cláusula SELECT. La Figura 4.11 muestra gráficamente la forma de obtener el contenido de la tabla derivada.

CAPITVLO 4

Tabla S

-

PLANTEAMIENTO Y SOLUCION DEL PROBLEMA

'-@ 3 AIshlvo 1

Archivo2

Tabla Derivada

Sosa

Figura 4.11. Procedimiento para Efectuar el Producto Cartesiano

A continuación se presenta el algoritmo para efectuar el producto cartesiano entre los archivos y para obtener la tabla derivada.

1 PROCEDIMIENTO ProduCarOptimo (NoArchiv0s:BYTFi); 2 Num-a-Car(NoArchivos,No); 3 4 Assign(NomArch,ArchRgtos); 5 NomTabla(NoArchivos,Tabla); 6 Tabla.Nombre:=Tabla.Nombre + '.BD1' 7 Opentile(F,Tabla.Nombre,Tabla.TamRgto); 8 9 LeeRgto( ArchRgtos,NoReg); 10 GetRec(Tabla.Nombre,NoReg ,Tabla.TamRgto,S qlBuf); 11 ObtenValCols( SqlBuf,BufferCols); 12 SI NoArchivos>l ENTONCES 13 Dec(NoArchivos,l); 14 ProduCarOptimoiJVo Archivos); 15 FIN SI

NomArch= 'indice' + No + '.TMP,

MIENTRAS NO(FiN DE ARCHIVO (ArchRgtos)) HACER

78


16 DE OTRO MODO 17 PutTablaDerivada(Buffer Cok); 18 FIN MIENTRAS 19 FIN PROCEDIMIENTO

En los siguientes párrafos se explican algunos aspectos importantes de este pseudocódigo.

En la línea 14 se indica que este pseudocódigo se ejecuta de manera recursiva. La razón de ello se debe a la forma que debe tomar un renglón de la tabla derivada. Considerando que es el producto cartesiano, entonces este renglón contendrá la concatenación de ia(s) columna(s) del renglón del primer archivo más el valor de la(s) columna(s) para el segundo archivo, y así sucesivamente hasta obtener el (los) valor(es) de ia(s) columna(s) para el renglón del último archivo. Este procedimiento se repetirá tantas veces como valores de posiciones de renglones existan para el primer archivo (ver Figura 4.11).

En la línea 11, el procedimiento ObtenValCois se encarga de obtener del renglón, el valor de la columna solicitada en la cláusula SELECT. el cual se almacena en la variable BufferCols.

La variable NoArchivos indica cuántos archivos se crearon para almacenar las posiciones de los renglones, y se utiliza como condición de salida en la recursividad. Su valor se modifica (línea 13) cada vez que se ha abierto un archivo. Cuando toma un valor de 1, significa que ya no existen más archivos por abrir. Entonces el contenido de la variable BufferCols tendrá los valores de todas las columnas solicitadas en la cláusula SELECT, y podrá ser guardado en el archivo creado para la tabla derivada (línea 17).

4.9. Proceso General de Optimización

Esta sección presenta de manera general el proceso que se realiza para seleccionar la estrategia de ejecución de la consulta. Para ello se utilizará el siguiente ejemplo:

Ejemplo O: SELECT S.SNo, P.PNo, SP.Cant FROM S, P, SP WHERE SP.CIUDAD=P.Ciudad

AND SP.PNo='SS' OR SP.SNo=S.SNo

1. Descomponer la consulta en varias subconsultas, con respecto ai operador lógico OR. Para la consulta C1 se generan las subconsultas S1 y S2.

S1: SP.Ciudad=P.Ciudad AND SP.PNo='SS' S2: SP.SNo=S.SNo

79

CAPlTVLO 4 PLANTEAMIENTO Y SOLUCION DEL PROBLEMA

En un árbol de consulta esta situación queda representada en la Figura 4.12

Arbol A

Proyectar [ S.SNo, P.PNo, SP.Cani ] I

Union

A2 A I

Restringir [ P.PNo = 'S5' AND SP.Ciudad = P.ciudad ] Juntar [ SP.SNo = SSNo ]

/ \ Juntar [ SP.Ciudad = P.ciudad ] SP S

SP P

Figura 4.12. Arbol de Consulta para el Ejemplo O

2. Para subconsultas en las que se presente la operación "Join", si existen:

2.1 Condiciones de la forma Atributo-Operador Relacional-Valor (Ver subconsulta S1) entonces, analizar si el atributo pertenece a un índice; si pertenece se busca el valor contra el cual se compara el atributo sobre el índice. Si no pertenece entonces se realiza un búsqueda secuencial de este valor sobre la tabla. Este tipo de condiciones hacen posible que no se requiera realizar el producto cartesiano entre las tablas completas.

2.2 Sólo condiciones con operaciones "JOIN" (ver S2), verificar si algunos de los atributos pertenece a un índice. Si no existe un índice se hace necesario la creación de un índice temporal. Se analizan este tipo de condiciones con el objetivo de evitar realizar el producto cartesiano entre las tablas completas. El tener un índice hace posible que la búsqueda de una columna de una de las tablas en el "JOIN" se realice sobre éste y no sobre la tabla.

Estos problemas se analizan en el algortimo Conds-padoin de Sección 4.3.5.5.2. De manera implicita este algoritmo permite analizar las diferentes estrategias que existen para poder ejecutar la consulta.

En la Figura 4.13. se representan las las situaciones anteriores.

80

CAPiTüLO 4 PLANTEAMIENTO Y SOLUClON DEL PROBLEMA

Arbol B Arbol C Juntar [ SP.Ciudad = P.ciudad] Juntar [ SP.SNo= SSNo ]

/ \ Restringir [ P.PNo=’S5’ ] SP Proyectar [ SPSNo ] S

P SP

Figura 4.13. Arbol de consulta para las Subconsultas Obtenidas

En estos árboles podemos notar que el orden de ejecución de S1 y S2 se modificó con respecto a la forma que en que realizaban en el árbol de consulta A. Por ejemplo en en A l del arbol A que representa a la subconsulta S1, se ejecutaba primero el producto cartesiano entre las tabla SP y S completas y después sobre este resultado se realizaba la proyeión P.PNo=’SS. En el árbol B esto se realiza de manera inversa; es decir, lo primero en realizar es la proyección P.PNo=’SS y después el producto cartesianó. En forma abstracta esto se realiza en el algoritmo EvaluaSubcltas de la Sección 4.3.5.5.2. Se puede concluir que lo que se busca es realizar lo antes posible las selecciones.

Para obtener el resultado final de la consulta, se realiza la operación Unión con los resultados obtenidos de cada subconsulta (ver algoritmo ProdCarOptimo). El árbol de consulta final para la consulta es el de la Figura 4.14.

3.

81

CAPITULO 4 PLANTEAMIENTO Y SOLUCION UEL PROBLEMA

I, Arbol C

Resultado Final

Proyectar [ SP.Cant. P.PNo] Proyectar [ SSNo, SP.Cant ]

I I Juntar [ P.ciudad = SP.Ciudad] Juntar [ SP.SNo= SSNo ]

Restringir [ P.PNo='C5'] SP Proyectar [ SP.SNo ] S

P SP

Figura 4.14. Arbol Final Para la Consulta

En el de la Figura 4.14. se puede observar que del resultado obtenido de la ejecución de cada subconsulta, se realiza la proyección de los atributos que se solicitan en la cláusula SELECT y finalmente se realiza la Union entre estos resultados. Esto significa que el resultado final, sólo estará formado por los valores de los atributos especificados en el SELECT.

82

CAPITULO 4


El presente capítulo describe de manera específica el proceso utilizado para efectuar la optimización de las consultas. Además, describe los principales problemas que se presentaron para su desarrollo y las soluciones que se dieron a éstos.

I 32

CAPITULO 4 PLANTEAMIENTO Y SOLUUON DEL PROBLEMA

4.1. Planteamiento del Problema

Una consulta puede expresarse de diferentes formas, en donde cada una de ellas sugiere una manera distinta de calcular su respuesta. Cada una de estas soluciones implica un tiempo de procesamiento que involucra un número diferente de accesos a disco y a la red, ya sea para almacenar o recuperar información; sin embargo una de estas representaciones tiene el menor tiempo de ejecución, que deriva en la disminución de la transmisión de datos entre la red y uso de memoria principal y secundaria, logrando así que su costo de acceso y ejecución sea el menor. Por lo tanto, la selección de una estrategia de operación que implemente la manera Óptima de ejecutar una consulta, independientemente de cuántas formas de representación se tengan, se hace indispensable para el buen desempeño de un SMBDD.

Para entender mejor el problema veamos el siguiente ejemplo, para el cual se usa la base de datos que se muestra en la Figura 4.1. Las cardinalidades de las tablas son las siguientes:

Tabla S 1000 renglones almacenada en el nodo A Tabla P 300 renglones almacenada en el nodo B Tabla SP 200 renglones almacenada en el nodo A

TABLA S

TABLA P I PNol PNombm I Color I Pero I Q u a d 1

TABLA SP

Figura 4.1. Base de datos de Proveedores y Partes

33

PLANTEAMIENTO Y SOLUCiON DEL PROBLEMA CAPIRJLO 4

Supongamos que en la tabla P existen 50 renglones para los cuales el color es Rojo, y que en el nodo A se desea realizar la consulta "obtener el número de proveedores que suministran partes rojas".

Una formulación en SQL para la consulta anterior podría ser la siguiente:

SELECT S.SNo FROM SP, P WHERE SP.SNo=P.PNo AND P.Color='Rojo'

Ahora se presenta una forma de ejecutar la consulta anterior:

Traerse completa la tabla P del nodo B ai nodo A. Realizar el producto cartesiano de SP y P. Restringir el resultado del paso 2 a lo especificado en la cláusula WHERE. Proyectar el resultado del paso 3 sobre S.SNo

Si el sistema ejecutara la consulta de acuerdo con el hipotético algoritmo anterior,

1. 2. 3. 4.

entonces la secuencia de eventos sena como sigue:

1. Realizar el producto cartesiano entre las tablas SP y P. Este paso involucra la lectura de 600 renglones y la construcción de una tabla cuyo contenido será de 200 *300 = 60,000 renglones, para los cuales se tendrían que efectuar accesos a disco para su almacenamiento.

El paso 3 del algoritmo anterior involucra la lectura de 600 renglones, de los cuales sólo 50 renglones satisfacen la condición; por lo tanto se realizarían 550 lecturas a disco innecesarias.

2.

De acuerdo con lo anterior se observa que se tendrían que realizar demasiadas operaciones sobre los renglones, provocando demasiados accesos a disco y utilizando una gran cantidad de memoria secundaria.

El siguiente algoritmo es equivalante al anterior en el sentido de que se produce el mismo resultado final, pero es obviamente más eficiente.

Descomponer la consulta en dos subconsultas. El propósito de ésto es que primero se realice la subconsulta que está más hacia adentro, lo que producirá una tabla más pequeña. Ahora, supóngase que existe un índice de la tabla P sobre la columna Color. Esto mejorará la ejecución de la consulta ai no ser necesario traerse toda la tabla P del nodo B, ya que sólo se traería el índice, el cual definirá la localización directa de aquellos renglones cuya columna Color sea Rojo. Por lo tanto, la tabla resultante será más pequeña y por consiguiente el producto

I ! 34


cartesiano entre esta tabla y la tabla SP se reducirá considerablemente, comparado con el obtenido del paso 2 del algoritmo anterior. De acuerdo a ésto, la formulación de la consulta anterior quedm'a finalmente de la siguiente forma:

SELECT SP.SNo FROM SP WHERE SP.PNo IN (SELECT P.PNo

FROM P WHERE P.Color='Rojo')

Este ejemplo es suficiente para darse cuenta de la importancia que tiene la optimización de consultas en UM base de datos distribuida.

Aunado a lo anterior, el problema se toma más complejo debido a la naturaleza del sistema con el cual se trabaja (BDD), por lo que se deben considerar los siguientes aspectos:

- La preservación de la transparencia de localización.

Los tiempos de acceso a través de la red, el tiempo de uso del procesador, y además el uso de recursos del sistema tales como memoria principal y espacio en disco.

El uso adecuado de los índices .

-

-

Como se mencionó en el Capítulo 3, existen estructuras de almacenamiento llamadas índices asociadas a un archivo de una tabla, las cuales permiten accesar de manera ordenada el contenido de la tabla con el fin de agilizar la recuperación de los datos. Con el uso de los índices se evita realizar una búsqueda secuencial sobre la tabla cuando se requiere accesar un renglón determinado debido a que el índice indica de forma directa la posición del renglón en la tabla dando como resultado le reducción de tiempo de búsqueda y accesos a disco.

Otra forma de hacer uso de los indices, es cuando se crean estas estructuras de manera temporal a un archivo de una tabla con el fin de reducir la búsqueda de los renglones de una tabla cuyos valores coinciden con los de los renglones de otra tabla. Por ejemplo, supongamos que tenemos la siguiente consulta sobre la base de datos de la Figura 4.1:

Ejemplo A: SELECT S.Nombre FROM S, SP WHERE S.SNo=SP.SNo

Si la tabla SP no tiene un índice definido sobre SNo, se necesita para cada valor de la columna SNo de la tabla S, leer secuencialmente cada uno de los renglones de SP hasta encontrar

¡I 35


este valor de columna. Si esta operación se realiza, entonces para los í000 renglones de la tabla S se necesitan 1000 x 200 accesos a la tabla SP.

¿Qué sucede si se le crea un índice temporal a la tabla SP sobre la columna SNo? entonces se necesita leer una vez los 200 renglones de SP para ser insertados en el índice. UM vez realizado ésto, la búsqueda de los renglones de la tabla S se hace sobre el índice, logrando con esto un ahorro de 200 lecturas sobre SP para la búsqueda de cada valor de la columna SNo de S. I

Dadas las ventajas anteriores, podemos deducir que los índices son elementos importantes para la recuperación más eficiente de los datos. Por ello dentro de este trabajo de tesis se concedió gran importancia ai uso' de los índices para llevar a cabo el proceso de optimización.

4.2. Antecedentes del Proyecto

El presente trabajo de tesis forma parte de un conjunto de trabajos que sobre BDDs se está desarrollando en el instituto de investigaciones Eléctricas @E), cuyo objetivo es obtener experiencia y conocimientos sobre estos sistemas. Para entender mejor la ubicación del trabajo de tesis dentro de este desarrollo a continuación se describen, en orden cronológico, los trabajos efectuados. I

4.2.1. Primitivas del SMBDD

Estas rutinas proporciond acceso transparente y concurrente a los archivos de la base de datos, con lo cual se logra que dos o más procesos pueden estar ejecutándose ai mismo tiempo en diferentes nodos de una red P, comunicaciones, y que no se necesite especificar en qué computadora de la red se encuentran almacenados físicamente los archivos (transparencia de localización). Estas rutinas fueron escritas en lenguaje ensamblador y en Turbo Pascal, para trabajar con el sistema operativo DOS versión 3.30.

Estas primitivas podían utilizarse en programas de aplicación escritos en Turbo Pascal, en los cuales se necesitaba tener acceso a los archivos de la base de datos.

La desventaja que se tenia de hacer uso directo de estas rutinas era que el programador de aplicaciones necesitaba estar familiarizado con los nombres y argumentos de estas primitivas.

I

36

I

CAPITULO 4 PLANTEAMIENTO Y SOLUCION DEL PROBLEMA 1 4.2.2. Precompiiador para un Lenguaje de Definición de Datos

Dado el problema que SA presentaba con el uso de las primitivas, el siguiente trabajo realizado consistió en desarrollar un precompilador del lenguaje de definición de datos (LDD) para las instrucciones CREATJZ TABLE y CREATE INDEX, basado en el estándar de SQL, las cuales podían intercalarse en Turbo Pascal, proporcionando con ésto una interfaz entre el programador de aplicaciones y el sistema.

I El precompilador toma como entrada un programa en Pascal con instrucciones de SQL

intercaladas y produce como resultado otro programa en Pascal, en el cual las instrucciones de SQL son traducidas a otras que Ison semánticamente equivalentes a estas y gue producen el mismo resultado. I

4.2.3 Lenguaje de Manipulación de Datos

Las instrucciones del LDD no eran suficientes para facilitar la explotación de las bases de datos, debido a que no se era posible realizar las operaciones básicas de borrado, consulta, inserción, y modificación sobre las tablas. Por lo tanto, el siguiente trabajo consistió en desarrollar un precompilador paka el lenguaje de manipulación de datos (LMD) para las instrucciones INSERT, DELETE, UPDATE, y SELECT de SQL.

4.3 Proceso General de Precompilación

Es importante conocer el proceso de precompilación realizado por el sistema, ya que en la ejecución del código generado por éste se llevará a cabo el proceso de optimización.

I

Para iniciar la explicaciónlde cómo se genera el código equivalente de las instrucciones de SQL, presentamos el proceso general que realiza el precompilador:

PROCEDIMIENTO Precopipilador; CONSTANTE OK=@ (indica si hubo éxito en la precompilación) VARIABLES I

FE, (archivo de entrada) FS: TEXT, (archivo de salida) E : INTEGER (condicion de error)

Asigna (FE,'Archentra.EP'); Asigna(FS,'Archentra.pas'); Abre(FE), Crearchivo(FS); E=OK,

COMIENZO

37

I CAPITULO 4 I PLANTEAMIENTO Y SOLUCION DEL PROBLEMA

MIENTRAS (NO EOF (FE)) Y (E=(OK)) HACER MIENTRAS (NO EOF (FE)) Y ( Getchar(Ch) <> ’$) HACER

WRITE (FS.0); SI a=’$; ENTONCES (Encontró una instrucción de SQL en el código)

(Comienza e1 proceso de precompilación para la instrucción SQL) ApInicioTexto:=NIL; SI RCBegin) ENTONCES E:=BeginDeclare DE OTRO MODO

DE OTRO MODO

DE OTRO MODO

DE OTRO MODO

DE OTRO MODO

DE OTRO MODO

DE OTRO MODO

DE OTRO MODO

DE OTRO MODO

DE OTRO MODO E=ErrorNo(lOO,’InstrucciÓn no conocida’);

SI SI R(1Create) ENTONCES E=CreateTable

SI RCDeciare) ENTONCES E=DeclareCursor

SI R(-elect) ENTONCES E=Select

SI RCInsert) ENTONCES E = Insert

SI R(-&en) ENTONCES E = Open

SI R(-Close) ENTONCES E = Close

SI RCFetch) ENTONCES E = Fetch

SI RCUpdate) ENTONCES E = Update

SI R(-Delete) ENTONCES E = Delete

SI E=OK ENTONCES Ganeracodigo I FIN SI;

FIN MIENTRAS; I

FIN MIENTRAS; I ~

Cierra (FS); Ciena(FE); FIN PROCEDIMIENTO i

!

En este pseudocódigo podemos observar el proceso de traducción del programa fuente, el cual se graba con la extensión’ ”.EP”. Antes de comenzar la traducción de la instrucción se inicializa la variable ApInicioTexto, que es una lista en la que se almacenará el código equivalente de la instrucción. !

I

Cuando se encuentra en el texto (programa fuente) el inicio de una instrucción de SQL ($), se determina de qué instrucciin se trata y se llama a la función correspondiente (CreateTable, Select, Insert, Update, Open, etc.)! la cual realiza Un análisis léxico, sintáctico y sernántico de la instrucción para verificar que estéiescrita correctamente y que las tablas y columnas paaicipantes

I 38


existan y pertenezcan a las tablas. El análisis se termina hasta que se encuentra el signo ";" que indica el fin de la instrucción. Si hubo éxito en el análisis, entonces se genera el código equivalente en Pascal, y para tal efecto se hace un recomdo de los nodos de la lista ApInicioTexto, los cuales se escriben en el archivo de salida FS (programa fuente en Pascal).

El código de las instrucciones que generan el código equivalente se encuentra en una unidad llamada "SQL"; por lo tanto, esta unidad debe ser incluida en el programa fuente.

I

Es importante señalar que para la instrucción CREATE INDEX, se crearon rutinas para el manejo de los índices tales como insertar, borrar, buscar una llave, pero éstas no se usaron en versiones anteriores a esta tesis.

4.4. El Problema de la Cláusula FROM de SQL ~

as instrucciones SE LE^ y DELETE tienen cierta semejanza en su sintaxis:

Para las instrucción DELETE, la cláusula FROM especifica el nombre de la tabla sobre la cual se operará. Esta cláusula es la primera que se ejecuta en cualquiera de las insirucciones, ya que en ella se determina sobre.cuál(es) tabla(s) se opera.

Para la instrucción S E a e x i s t e UM variante para esta cláusula ya que se puede especificar más de una tablaFPor lo tanto, no sólo se indica sobre qué tablas se desea operar, sino que además se produce una tabla resultante llamada tabla derivada que es el producto cartesiano extendido de las tablas especificadas en esta cláusula. Cada renglón de esta tabla es la concatenación de un renglón de c,ada una de las tablas en el orden en el cual se identifican en la cláusula FROM, por lo que su cardinalidad es el producto de las cardinalidades de las tablas y su grado es la suma de los grados de las tablas. De acuerdo a lo anterior, el problema que se presenta por la ejecución de esta cláusula es el tamaño tan grande de la tabla derivada. Ahora, considerando que de esta tabla sólo unos cuantos renglones satisfacen la condición WHERE y aún más que para cada renglón se requieren unos cuantos valores de columnas (las solicitadas en el SELECT), entonces vemos que esta tabla contiene información que no es necesaria. Esto significa que se pueden evitar muchos accesos a disco y transmisiones de datos en la red para obtener los datos de esta tabla. Por ejemplo, considérese la siguiente consulta:

particularmente incluyen la cláusula FROM. ~

Ejemplo B: ~

i SELECT S.SNo, P.PNombre FROMS,P 3 WHERE S.SNO=P.PNo AND P.Nombre='Zepeda'

OR P.Nombre='Lira'

39

, I

PLANTEAMIENTO Y SOLUCION DEL PROBLEMA CAPITüLO 4 I

Figura 4.2. I Al ejecutarse el Productoicartesiano de S y P se obtiene la tabla que se m u e m en la

I ,

: I 3 , I . , u o ' tn I

r a ' m !

. I . , . , I

. I Y~

* ¡

. , . I

a i

f i

m M , 2*AS ~

m s ' . !

* ¡

. I

-57 ~

- l

Figura 4.2. Producto Cartesiano de S y P !

De la tabla de la Figura 412 los renglones que satisfacen la condición WHERE son 600 renglones. Analizando el contenido de éstos, se observa que se componen por sólo 2 renglones de la tabla S y de 300 renglones + la tabla $P. Por lo tanto, si sólo se ocuparan estos renglones para realizar el producto cartesiano, entonces el tamaño de la tabla resultante sería de 2x300 renglones y no de 1000x300 renglones, dando lugar a una reducción considerable de la tabla derivada. I

i Ahora, si de esta tabla s i .eliinaran las columnas que no se solicitan en la cláusula

I

SELECT, entonces el grado de la, tabla disminuiría de 9 a 2, quedando reducida aún más.

Por lo expuesto anteriormente nos damos cuenta que es importante modificar la ejecución de la cláusula FROM, para evitar en lo más posible que el proceso para calcular la tabla derivada no se realice con el producto cartesiano de las tablas completas.

40

, I PLANTEAMIENTO Y SOLUCION DEL PROBLEM4 CAPiTU.0 4

4.5. Aspectos Generales del Prdpeso de Optimización

Durante el proceso para $#iseleccionar la mejor estrategia de ejecución de la consulta se genera un conjunto de estrategias; cada una de ellas es analizada en su momento y desechada en cuanto se encuentra que existe q mejor. Por lo tanto, al finalizar este proceso se tendrá la mejor de ellas. !

i Cada estrategia se generala partir de la información que se tenga en el dicciormio de

datos sobre las tablas participantes en la consulta, de la formulación de la consulta y de los elementos definidos para las tabl$s, en el momento del anáisis.

1

I La generación y análisis de cada estrategia se realiza de manera impiícita en cada paso

hecho por el optimizador para obtener la mejor de éstas. Esto significa que no existe o se genera una estructura física en la cual se !guarde la información sobre cada estrategia. La razón de ello es que debido a que puede existir 'm gran número de estrategias, podría ocasionar que el tiempo de procesamiento para almacenar^ y analizar la información que contuviera esta estructura sea demasiado, provocando que el proceso de selección de estrategia no sea conveniente. De acuerdo a lo anterior la e c i 5 de los algoritmos de selección de la estrategia del optimizador, deben permitir que en cada paso que se realice para obtener la mejor estrategia, el universo de éstas se vaya acotando hasta el p@o que sólo quede la mejor. Por ejemplo, supóngase que se

%

realiza la siguiente consulta: , !

Ejemplo A: I SELECT * FROM S WHERE SNombre='Zepeda'

~ AND Ciudad='Culiacán' ~ AND SNo='SS' ! $140 >= s5'

Y para la tabla S se han d e f i d o d los siguientes índices:

PCdNum Ciudad,SNo PNombre PNombre

~

Bajo estas condiciones son posibles las siguientes estrategias:

1. Realizar UM búsqueda secuencia1 sobre la tabla S para obtener los renglones de ésta que satisfagan la condición de ia cláusula WHERE. Ejecutar esta estrategia requiere la lectura de cada renglón de, la tabla S, por lo que se necesitan 1000 lecturas a disco.

41

CAPIlWLO 4 PLANTEAMIENTO Y SOLUCION DEL PROBLEMA

2.

3.

4.

Realizar la búsqueda de los renglones mediante el uso del índice PNúmero. Esto implica efectuar una búsqueda secuencia1 sobre el índice, debido a que puede existir más de un valor de llave de búsqueda (sNo=5, SNo=6,.., SNo=1000). Para cada valor de llave encontrado se requiera un acceso a disco para obtener el renglón asociado a la llave, con el objeto de verificar que satisfaga con las condiciones Ciudad='Culiacán' y SNombre='Zepeda'. Con respecto a la condición de WHERE, ésta se debe de modificar en cuanto al orden de ejecución, siendo SNo>='S5' la primera condición que se tiene que realizar. Por lo tanto la forma de la expresión de la cláusula WHERE se modifica de la siguiente manera:

SNo>='SS AND Ciudad='Culiacán' ANDWombre='Zepeda'

Comparando esta estrategia con la anterior en cuanto al número de acceso a disco, en esta Última se realizan un menor número de accesos (Aproximadamente 9995).

Realizar la búsqueda de los renglones mediante el uso del índi@Nombre. Ejecutar esta estrategia requiere la búsqueda de un sólo valor de llave sobre el indice ('Zepeda'), si ésta es endtrada se necesita realizar un acceso a disco para obtener el renglón asociado a la llave para verificar que satisfaga la condición SNo>='S5' AND Ciudad='Culiacán'. Como puede verse de todas las estrategias esta es la mejor, ya que únicamente se realiza un acceso a disco.

Realizar la búsqueda de los renglones mediante el uso del índice PCdNúm.De todos los valores de llaves existentes en el índice se requieren sólo unos cuantos, es decir, que se busca un conjunto de llaves. El conjunto es aquel cuyo atributo Ciudad sea'Culiacán' y que SNo>\Y: La búsqueda sobre el índice es secuencial, comenzando con la búsqueda de un valor de llave igual a 'Culiacán S5' y terminando hasta que se encuentra una llave cuyo valor Ciudad no es'Culiacán: esto es, que termina cuando comienzo otro conjunto (el siguiente conjunto sería aquel cuyo atributo Ciudad sea igual abachucáy SNo igual a 'Si'). Para cada valor encontrado se requiere un acceso a disco para obtener el renglón asociado a la llave para verificar que éste satisfaga la condición de que Nombre sea igual a 'Zepeda'. De acuerdo a lo anterior se puede aseverar que la ejecución de esta estrategia produce el mínimo de accesos a discos con respecto a las dos anteriores. La afirmación anterior se basa en que s,¡ se vemos al índice formado por conjuntos, entonces tenemos que el conjunto Ciudad= Culiacán'y Sno>$'no es el Único ya que también existen los conjuntos Ciudad='Acapulco*y SNo='S4', .., CiudadAVeracruz"y SNo='S2', y si no es el a significa que el $dice no esta compuesto Únicamente por llaves del conjunto C?dad&3diacán'y SNo>$f

Como se observa para esta consulta existen varias estrategias las cuales se obtuvieron por

W

una parte, con la inform&ión existentes sobre los índices y poi otra analizando la forma de la expresión de la cláusula WHERE. Ambas partes deben interactuar para obtener las estrategias

42

http://PCdNm.De

CAPITULO 4 PLANTEAMWTO Y SOLUCION DEL PROBLEMA

e ir decidiendo cuál es la mejor. De acuerdo a lo anterior, el optimizador debe contar con NtiMS que permitan realizar un manejo interno de la consulta para determinar qué elementos (columnas, operadores relacionales, operadores lógicos, etc.) de ésta son útiles para mejorar la recuperación de los renglones. También debe contar con rutinas que actúen en el nivel físico; es decir, que puedan accesar físicamente los datos de la base de datos.

4.6. Importancia de la Cláusula WHERE en el Proceso de Opthnización

La función de cláusula WHERE es especificar una condición de búsqueda sobre la tabla derivada resultante de la cláusula FROM. Entonces la tabla resultante final consiste de aquéllos renglones de la tabla derivada para los cuales el resultado de la condición de búsqueda es verdadero.

Supóngase que D es el resultado de una cláusula FROM y que la condición de búsqueda se aplica a cada renglón de D. El resultado de la cláusula WHERE es una tabla formada de aquellos renglones de D para los cuales la condición de búsqueda es verdadera.

La condición de búsqueda especifica un valor verdadero, falso o desconocido, que depende del resultado de aplicar operadores booleanos a condiciones específicas. La sintaxis de esta cláusula es la siguiente:

<condición de búsqueda> ::= <término booleano> OR <término booleano> 1 <término booleano> ::= <factor booleano> ( AND <factor booleano> 1 <factor booleano> ::= [NOT] <primario booleano> <primario booleano> ::= <predicado> <predicado> ::= <predicado de comparación> I <predicado BETWEEN> I

<predicado iN> I <predicado NULL>

Como se observa en esta especificación de sintaxis, una condición de búsqueda es básicamente UM colección de predicados que se combinan con el uso de los operadores AND, OR y NOT. Por ejemplo, considérese la consulta del siguiente ejemplo:

Ejemplo C: SELECT * FROM S WHERE S.Ciudad='Tampico'

OR S.Ciudad='Pacbuca' AND S.SNo='Sl'

La importancia de la cláusula WHERE para efectuar el proceso de optimimción, radica (como se observa en la consulta anterior) en la referencia que se hace a las columnas de la tabla

43

.-

PLANTEAMIENTO Y SOLUCION DEL PROBLEMA CAPITULO 4

o tablas especificadas en la cláusula FROM. Así que el resultado de un análisis de esta cláusula podría llevar a identificar lo siguiente:

- Columna(s) que pertenece(n) a los índices de las tablas.

Si existe un índice, entonces los valores contra los cuales se comparan las columnasse pueden utilizar para formar la llave de búsqueda.

Tipo de búsqueda sobre el índice.

Acotar el número de renglones de las tablas de tal manera que Únicamente se tengan los necesarios para realizar el producto cartesiano de las tablas en la cláusula FROM.

-

-

-

4.6.1. El Problema del Análisis de la Cláusula WHERE \

Antes de comenzar con la descripción de esta sección, mencionaremos que para resolver el problema de este trabajo de tesis se dividió el proceso de optimización en dos partes: la primera de ellas cuando se involucre una sola tabla, y la segunda cuando se tengan dos o más tablas declaradas en la cláusula FROM. La razones para ello son las siguientes:

1. Cuando se hace referencia a una sola tabla en la cláusula FROM, no es necesario crear una tabla derivada, puesto que ésta se considera como la tabla derivada. Por lo tanto, sólo se accesan los renglones de una sola tabla.

La condición de la cláusula WHERE varía de cuando se define un solo nombre de tabla a cuando se involucran dos o más, desde el punto de vista de los valores con los que se comparan las columnas de las tablas. En una condición WHERE para una sola tabla, las columnas se comparan con valores conocidos. Por ejemplo en la consulta del ejemplo anterior, la columna S.ciudad se compara con los valores 'Tampico' y 'Pachuca', por lo que para comprobar que se satisfaga esta condición sólo se necesita obtener el renglón de la tabla S y obtener el valor para esa columna. En cambio para el caso en donde se especifican dos o más nombres de tabla en la condición WHERE, se puede especificar la comparación de una columna de una tabla con el valor de otra columna de otra tabla; por ejemplo considérese la siguiente consulta:

2.

Ejemplo D:

SELECT S.ciudad FROM S,$P WHERE S.SNo=SP.SNo - _ OR?kut= 200

44

PLANTEAMIENTO Y SOLUCION DEL PROBLEMA i CAPiTVLO 4

En este caso se observa que el valor contra el cual se está comparando la columna S.SNo es un valor desconocido, de tal forma que para determinarlo se necesita accesar la tabla SP y obtener el valor para su columna SNo. El hecho de accesar otra tabla para conocer un valor de comparación, implica realizar & serie de operaciones que difieren de lo que se realiza cuando hay un solo nombre de tabla en la cláusula FROM. Por lo tanto, el análisis para ambos casos es diferente.

Para esta sección sólo se considera el caso en el que se hace referencia al nombre de una sola tabla en la cláusula FROM de una consulta.

4.6.1.1. Operadores Lógicos AND y OR

Cuando se presenta una expresión que involucra dos o más condiciones conectadas con operadores lógicos OR, se puede observar la siguiente situación: El resultado de una condición es independiente de los demás; es decir, que si un renglón cumple la condición (es verdadero) no se necesita que el renglón satisfaga las demás condiciones para que la expresión sea verdadera. Por lo tanto, conviene ver a cada operando de la expresión como si fuera una consulta independiente. En estas circunstancias se puede considerar que la expresión está formada por subconsultas, las cuales podrían ser procesadas (de manera separada, buscando para cada subconsulta los renglones de la tabla que cumplan la condición para ésta, en donde para cada renglón encontrado no se necesita evaluar la condición completa, ya que se da por hecho que la cumple.

La ventaja que se puede obtener de esta característica es que si existe un índice para cada subconsulta, entonces la búsqueda de los renglones que satisfagan la expresión se llevará a cabo por partes; es decir, para cada subconsulta se ocupará su índice, el cual encontrará de forma directa los renglones que satisfagan la condición. De ahi que los renglones que satisfagan la condición de búsqueda completa será la unión de los renglones obtenidos para cada subconsulta. Conviene destacar que este tipo de consultas s.olamente puede optimizarse dividiéndolas en subconsultas, ya que de lo contrario habría que hacer un recorrido total de la tabla para encontrar los renglones que satisfacen la expresión completa. Por ejemplo, la consulta del ejemplo C puede dividirse de la siguiente manera:

I

Subconsulta A: S.Ciudad='Tampico' Subconsulta B: S.Ciudad='Pakhuca' AND S.SNo='Sl'

Supongamos que la tabla S tiene un índice sobre la columna Ciudad. Entonces para la subconsulta A se encuentra un valor de llave con valor de 'Tampico', cuyo número de renglón en la tabla es el 4 (ver Figura 4.1); para la subconsulta B también hay un valor de llave en el indice Ciudad con valor de Pachuca y su número de renglón es el 3 (ver Figura 4.1). Por lo tanto el acceso a los renglones 3 y 4 de la tabla S es directo. Con este procedimiento únicamente se

45

CAPITULO 4

hicieron dos accesos a disco para recuperar los renglones.


Cuando una condición de búsqueda está formada con operadores lógicos AND, la expresión se considera verdadera si todos sus operandos son verdaderos. Si un operando toma el valor falso, la expresión será falsa. De acuerdo a lo anterior, una expresión de este tipo no se puede dividir en subconsultas, ya que cada renglón que se obtenga debe satisfacer cada una de las condiciones de la expresión.

4.6.1.2. Análisis de las Columnas para los Operadores Lógicos AND y OR

Si partimos de que la expresión de la condición de búsqueda puede dividirse en subconsultas, en donde una subconsulta será una expresión formada por una o varias condiciones conectadas por operadores lógicos AND; entonces lo primero que se debe realizar para iniciar el proceso de optimización es encontrar por lo menos una columna de cada subconsulta que pertenezca a un índice.

La razón de establecer la condición de que para cada subconsulta se pueda usar un índice es que, si una de ellas no tiene, obligará a leer toda la tabla secuencialmente. Por lo tanto, no se tendría ningún ahorro en tiempo y acceso a disco, resultando contraproducente la subdivisión, ya que además de efectuar el proceso de lectura secuencial de la tabla, se harían las búsquedas sobre los índices.

De acuerdo con lo anterior, para realizar el análisis de identificación de columnas se debe considerar lo siguiente:

1. Cuando se analice una expresión que involucre operadores lógicos OR en donde sus operandos sean la mínima expresión (columna-operador reiacional-valor), cada uno de éstos debe ser tal que la columna forme parte de un índice para poder continuar el examen de la expresión. Cuando se encuentre un operando que no tenga un índice asociado, se termina el análisis. En este caso, para esa expresión no se podrá hacer uso de índices, y por lo tanto no se puede optimizar.

Para realizar el análisis de una expresión formada por operadores lógicos AND, debemos terminar el análisis hasta encontrar por lo menos una columna de una condición de esta expresión que forme parte de un índice. Si esto sucede, entonces para recuperar los renglones que satisfagan esta condición, se podrá hacer uso de un índice, sin que por ello sea necesario que para cada operando exista un índice definido. Como se puede observar, las condiciones que se deben satisfacer para este caso son contrarias a las del punto anterior. La desventaja que se presenta es que para el renglón o renglones recuperados será necesario verificar que éstos cumplan las condiciones dadas por lo otros operandos cuyas columnas no sean columnas del índice; mientras que para un renglón recuperado

2.

46

- -


con el método del punto 1 no se necesita realizar ninguna evaluación adicional.

En cualquiera de los dos métodos, de las columnas que formen parte de un índice, por lo menos una de ellas debe ser la primera columna del índice, esto con el fm de poder formar el valor inicial de la llave que se buscará en el índice.

4.6.1.3. Análisis de la Condición WHERE

De acuerdo con lo descrito en la Sección 4.3.5.1, el objetivo que se busca en la primera parte del proceso de optimización, es determinar las posibles subconsultas y encontrar por lo mehos un indice asociado para cada una de éstas, mediante el cual se puedan recuperar los renglones. En esta sección se describen los problemas y soluciones que se presentaron para llevar a cabo este análisis.

Para evaluar la condición de búsqueda, se ha utilizado en los trabajos desarrollados anteriormente la forma postfija, debido a las ventajas que ofrece para determinar el orden de evaluación de una expresión booleana. Para nuestro propósito no es tan importante el orden, sino la forma en que se representa la expresión. Esta a f i c i ó n queda más clara observando las características que posee la forma postfija. Para tal efecto consideremos la condición de búsqueda para la siguiente consulta:

Ejemplo E SELECT * FROM P WHERE PNo= 'Pl'

AND Nombre='Tuerca' OR Peso=14

6 F N m \'-y 7 AND Ciudad='Monterrey'

L a representación postfija para la condición de la consulta del ejemplo E es la siguiente:

phi0 = 'DL' pa;nbw r ' TVaCh

Operando 1 c1 PNo='Pl' 0pvwb F

w ND Operando 2 c 3 Peso=14 Qpr'wdo 1 peso = ' q

c2 Nombre= 'Tuerca' Opl AND

Op2 OR

Op3 AND

OR

P N o = 'PLI ' Operando 3 C4 Ciudad='Monterrey' o p u b 3 : ' h l l C M / P 9 '

AUb 5%

Op4 OR

47

PLANTEAMWTO Y SOLUCION DEL PROBLEMA CAPITULO 4

En una expresión postfija los operandos se colocan antes que el operador. De manera sencilla esta forma tiene la siguiente representación:

operando derecho operando izquierdo

operador

En donde un operando puede ser a su vez una expresión booleana, y por lo tanto debe tener esta misma forma (Operando 3).

Se puede establecer precedencia entre los operadores, de tal forma que los operadores de mayor precedencia se ejecutan antes que los de menor precedencia. Como sabemos el operador AND tiene mayor precedencia que el operador OR. Por lo tanto, en la representación postfija aparecerá primero el operador AND y después el operador OR, como vemos en el Ejemplo E donde Opl que es un AND está primero que Op2, y Op3 está antes que Op4.

Para efectos de determinar las subconsultas, se puede observar lo siguiente a partir de la forma que toma la expresión postfija.

1. Es posible determinar con facilidad ia(s) columna(s) como unidad(es) mínima@) de un operando de cada operador.

Dado que un operando puede ser una expresión, entonces tcda la expresión que se forme hasta encontrar un operador lógico AND seguido de una columna es un operando del operador lógico OR. Por ejemplo, para el Ejemplo E la expresión formada por C1, C2 y Opl es operando de Op2 (operando derecho), y por lo tanto se considera como una subconsulta.

2.

3. Los operadores OR quedan colocados después de un operador AND, por lo que se puede establecer que una subconsulta empieza cuando se encuentra un operador OR y termina cuando se encuentra otro operador OR. Como vemos en el ejemplo E, se tendrían las dos subconsultas siguientes:

B: PNo='P4' Ciudad='Monterrey ' AND

C: Peso=14

4. Si inmediatamente después de un operador OR se encuentra un operador AND, la expresión que se forma hasta encontrar otro operador OR se considera una subconsulta (indica que es el operando izquierdo del operador).

48

PLANTEAMIENTO Y SOLUClON DEL PROBLEMA CAPITUIB 4

Para efectuar el análisis se consideraron las observaciones anteriores como condiciones para determinar las subconsultas. Pero antes de presentar el pseudocódigo que muestra la forma de llevar a cabo el análisis de la expresión de la condición de búsqueda, es necesario establecer cuál es la finalidad de efectuar este análisis.

A.

B.

C.

Determinar las subconsultas que se. pueden formar a partir de la condición de búsqueda.

Identificar para cada subconsulta si existe un índice que reduzca el acceso.

Indicar que la consulta analizada no se puede procesar mediante el uso de índices, en caso de que una subconsulta no tenga un índice asociado que reduzca el acceso.

43.5.3.L b

4,3.5,3.i --- k.6Clh.jli> Pseudocódigo para el Análisis de la Expresión WHERE

1 IR al último operador "OR" 2 REPETIR 3 Asignar a la variable Subclta-conIndice un valor de falso

4 SI operador "AND ENTONCES 5 REPETIR 6 7 8 ' Guardar la posición del índice 9

10 FIN SI 11 Ir al siguiente operando 12

13 FIN SI

Guardar el nombre de la columna del operando SI es la primera columna que pertenece a un índice ENTONCES

', Asignar a la variable Subclta-conIndice un valor de verdadero

HASTA encontrar el Último operando de la expresión O encontrar un operador " O R

14 15 16 17 18 19 20 21

SI operador "OR" ENTONCES Guardar el nombre de la columna del operando SI la columna pertenece a un índice ENTONCES

Guardar la posición del índice Asignar a la variable Subclta-conIndice un valor de verdadero

FIN SI Ir siguiente operador

FIN SI

22 SI operador, "AND-OR" ENTONCES 23 REPETIR

49


24 25 26 21 28 29 30 31

Guardar el nombre de la columna del operando SI es la primera columna que pertenece a un índice ENTONCES

Guardar la posición del índice Asignar a la variable Subclta-conIndice un valor verdadero

LlN SI ir al siguiente operando

HASTA encontrar un operador "OR FIN SI

32 HASTA analizar el Último operando de la expresión o que la variable Subclta-conindice sea igual a falso

De este pseudocódigo se puede observar lo siguiente:

En la línea 1 se indica que el análisis comienza sobre un operador OR. Recordando la precedencia de operadores, éstos se colocah más hacia abajo (ver la expresión del Ejemplo E); por lo tanto, ésto sugiere que el examen de la expresión se lleve a cabo de abajo hacia arriba de manera inversa a la de su evaluación (arriba-abajo). La razón para ello es la siguiente:

1. Considerando que el análisis se lleva a cabo recorriendo uno a uno cada elemento de la expresión (operador, operando, operando), entonces es posible determinar con facilidad los operandos de cada operador sobre el cual se lleva a cabo el análisis, ya que cada vez que se encuentre un operador se sabe que los elementos inmediatos son operandos y por ende pertenecen a éste. Si este análisis se efectuara de manera inversa (arriba-abajo), entonces lo primero que se encuentra son los operandos. Por lo tanto, será necesario recorrer la expresión hasta encontrar el operador al cual pertenecen éstos, lo que provoca la necesidad de tener que guardar los operandos para posteriormente asociarlos al operador analizado.

De acuerdo a la Sección 4.3.5.3, cada vez que se encuentre un operador OR significa que existe una subconsulta. Entonces al iniciar el análisis de esta forma, los primeros operadores en ser identificados son precisamente éstos, y por consiguiente se determinan con facilidad las subconsultas.

2.

Las líneas 4, 14 y 22 son las condiciones que definen las subconsultas. La línea 4 forma una subconsulta que se compone sólo por operadores AND; esta subconsulta representa el caso en el que un operando del operador OR es una expresión compuesta (tiene más de una condición). La línea 14 establece el caso en el que un operando de un OR es la expresión más simple; es decir, que hay una comparación (columna-operador relacional-valor). En la línea 22 se considera un tipo de operador al que se denomina AND-OR la razón de ésto es que permite identificar específicamente el caso en el que el operando izquierdo del OR, es UM expresión compuesta por más de un operando (Operando 3 del Ejemplo E).

50


El nombre de columna para cada uno de los operandos de cada subconsulta se guarda (líneas 6, 15 y 24) con el objeto de identificar cuáles de estas columnas pertenecen al (a los) índice(s) defddo(s) sobre la tabla.

La variable Subcita-conInd se utiliza para determinar si se continúa con el análisis de la expresión para seguir formando las subconsultas. Si en una subconsulta que se determina se encuentra que por lo menos una de sus columnas pertenece a un índice, esta variable toma un valor de verdadero; lo cual significa que se puede continuar con el análisis de la expresión para definir otra subconsulta. Esta variable se inicializa con un valor de falso (línea 3) cada vez que se comienza con la determinación de una subconsulta.

Cada vez que se encuentra que una columna pertenece a un índice, se guarda el número de éste. La razón de ésto es que a partir de ese índice se efectuará posteriormente un análisis sobre los demás índices de la tabla, para determinar cuál es el mejor para procesa esta subconsulta.

4.6.1.4. El Problema de Selección del Indice para Accesar una Subconsulta

De acuerdo a la Sección 3.6, con el uso de la instrucción CREATE INDEX o bien con la defdción de ciertas restricciones que se realizan sobre la tabla mediante las cláusulas UNIQUE y PRIMARY KEY, es posible asociar a una tabla varios índices. Por lo tanto, puede suceder que para una subconsulta, se disponga de varios índices para agilizar la recuperación de los renglones. Pero hablando en términos de búsquedas, generalmente con uno de ellos se realiza el menor número de búsquedas, y por consiguiente el tiempo para encontrar una llave se reduce. Entonces es necesario determinar cuál índice es el mejor para procesar la subconsulta.

Para entender mejor el problema, se presenta un ejemplo en el cual se muestra el efecto que resulta al hacer uso de varios índices para procesa la subconsulta del siguiente ejemplo.

Ejemplo F: Color='Rojo' AND PNombre='Torniilo'

Supóngase que a la tabla P de la base de datos de la Figura 4.1 se le han declarado los índices de la Figura 4.3.

51

CAPlTULO 4 PLANTEAMIENTO Y SOLUCION DEL PROBLEMA

NombreNum

Tichucls

Tanillo

TomiUo

ColorNombre

Tomillo

Tachuela

Rojo

Rojo TomiUo

Rojo T U a C i

I I

Figura 4.3. Indices Defhdos a la Tabla P

1. Uso del indice NombreNum. Este índice está formado por dos columnas @‘Nombre y PNo) de la tabla P, pero en la subconsulta del Ejemplo F sólo aparece una de ellas: PNombre. En este caso, el valor de la llave queda incompleto, provocando que se tenga que realizar UM búsqueda secuencial sobre el índice para encontrar todas aquellas llaves cuyo valor de PNombre sea Tomillo, y para cada llave encontrada se necesita obtener el renglón de la tabla asociado para verificar que satisfaga la condición de que el valor en su columna Color sea Rojo. De acuerdo a lo anterior, se llevan a cabo los siguientes eventos:

a. b. c.

Uso del indice ColorNombre. Este índice esta compuesto por dos columnas y para cada una de ellas se conoce su valor; por lo tanto, la búsqueda de la llave sobre el índice es directa. En este caso no se necesita accesar el renglón asociado a la llave para verificar que satisfaga la condición, ya que se da por hecho que la cumple debido a que todas las columnas involucradas en la condición pertenecen al índice. En tales circunstancias los eventos que se realizan son los siguientes:

a.

Considerando los eventos que se realizan con el uso de cada índice, se puede observar la diferencia del número de búsquedas y accesos a la tabla que se efectúa con cada uno de ellos para recuperar los renglones; lo cual se ve reflejado en el tiempo de respuesta y accesos a disco. De ésto se puede concluir que, entre mayor sea el número de búsquedas, será mayor el número

Búsqueda secuencial sobre el índice Obtención de los renglones de la tabla asociados a cada llave Verificación de que cada renglón satisfaga la condición

2.

Búsqueda directa sobre el índice

11 52


de accesos a disco y el tiempo de respuesta se incrementad. Por lo tanto, conviene elegir aquel índice en el que se lleven a cabo el menor número de búsquedas.

Con el uso del índice ColorNombre sólo se necesita realizar un paso para encontrar el renglón que cumple la condición de la subconsulta. Esto se debe a que todas las columnas de la condición pertenecen a la llave del índice, por lo que el valor de la llave de búsqueda es conocido y sólo se necesita buscar un valor sobre el índice. De acuerdo a ésto se puede concluir que el índice que se debe elegir para resolver una subconsulta es aquél cuyo mayor número de columnas estén contenidas en la condición.

En la subconsulta del Ejemplo F se puede observar que todas las columnas se están comparando bajo un operador relacionai de igualdad (=), lo que para efecto de formar la llave de búsqueda significa que existe un valor Único para ésta; es decir, que sólo se buscará un solo valor de llave sobre el índice. La pregunta que surge ahora es ¿qué condiciones se deben establecer para elegir un índice en el que sus columnas estén presentes en la subconsulta, y se comparen con operadores de desigualdad?

Para dar respuesta a esta pregunta, se ejemplificará lo que sucede cuando se usa un índice considerando el criterio del mayor número de columnas presentes en la condición. Para tal efecto. considere la subconsulta del siguiente ejemplo:

Ejemplo G: PNo= 'p3' AND PNombre= 'Birlo' AND Color>= 'Azul' AND Ciudad='Monterrey'

Para la cual han definido los índices de la Figura 4.4.

NombreNum ColorCd Ciudad

zacstecw

T d l o Rojo Guadahjari

T d l O W l a

Figura 4.4 Indices Defddos para la tabla P

53

PLANTEAMIENTO Y SOLUCiON DEL PROBLEMA CAPi”W.0 4

1. USO del índice ColorCd. Este índice está compuesto por dos C0hmas que aparecen en la condición de la subconsulta del Ejemplo G. El operador relaciona1 (>=) obliga a realizar una búsqueda de un conjunto de llaves sobre el índice: todas aquéllas cuyo valor de la columna Color sea Azul o un valor mayor a éste (Verde, Rojo, etc.). Para tal efecto, se necesita recorrer prácticamente todo el índice, y además, para cada valor encontrado de una llave, se necesita accesar el renglón de la tabla asociado a la llave para verificar que cumpla la condición de que PNo sea P3 y PNombre sea Birlo. Los eventos que ocurren son los siguientes:

a. b. c.

Uso del indice NombreNum. Cada uno de las columnas de este índice (PNombred,PNo) están contenidas en la subconsulta, y cada una ellas se compara con un operador de igualdad por lo que existe un valor único de llave (P3-Birio)?Esto significa que la búsqueda sobre el índice es directa. Para el renglón asociado a la iiave, es necesario verificar que cumpla la condición de que Color sea mayor o igual a ’Azul’ y que Ciudad sea ‘Monterrey’, para lo cual se debe accesar el renglón de la tabla. En este caso los eventos que ocurren son los siguientes:

a. Búsqueda directa sobre el índice c. Acceso al renglón de la tabla asociado a la llave d. Verificación de que el renglón satisfaga la condición

De acuerdo a los eventos realizados en cada punto, se puede observar que existe diferencia entre el uso de un índice y otro con respecto al número de búsquedas y accesos a la tabla, aunque para ambos casos se conozcan los valores de los atibutos de las llaves.

Búsqueda secuencial sobre el índice Acceso al renglón de la tabla para cada valor de llave encontrado Verificación que cada renglón obtenido cumpla la condición

2.

-

El hecho de realizar un número mayor de búsquedas sobre el índice ColorCd se debe a la presencia del operador relacional (>=), ya que puede existir más de una llave cuyo valor de columna Color sea mayor que el valor contra el cual se está comparando ésta en la condición. En cambio con el uso del índice NombreNum se realiza una soia búsqueda sobre el índice; ésto se debe a que el operador relacional que aparece en cada operando de la condición es de igualdad, por io que sólo puede existir un valor único de llave que satisfaga la condición de que el valor de cada columna de ésta sea igual al valor contra el que se compara. De acuerdo con este último caso, se puede concluir que el criterio para elegir el índice es seleccionar aquél cuyo mayor número de columnas de la iiave se comparen con un operador de igualdad en la condición.

Es necesario aclarar que el número de columnas útiles de un índice se determina en un orden de izquierda a derecha y contiguas a partir de la primera de acuerdo a su declaración en

54


el indice para efectos de formar el valor de la llave. De otra manera, aunque se conociera el valor de casi todas las columnas no sería posible formar la llave si se desconociera el valor de sus primeros columnas. Por ejemplo, considérese la siguiente subconsulta:

Ejemplo H Ciudad='Puebla' AND Peso=l7

De acuerdo con el criterio expresado anteriormente y sin considerar la aclaración precedente, el índice que se debe utilizar es Colorcd, puesto que es el índice cuyo mayor número de columnas se presentan en la subconsulta, y además se compara con un operador de igualdad. Sin embargo, en este caso no se puede formar el valor de la llave a buscar, ya que no se conoce el valor de la columna Color, y en consecuencia, no se puede llevar a cabo la búsqueda de la llave sobre el índice. Para resolver este problema podría pensarse en dar un valor a la columna cuyo valor se desconoce, para este caso el valor dado a la columna Color podría ser el valor de la columna Color de la primera llave del índice. Esto provoca tener que realizar una búsqueda secuencial sobre el índice, debido a que pueden existir varias llaves cuyos valores de columna sean iguales a los valores de las columnas para las cuales se conoce su valor. Lo anterior es exactamente lo mismo que realizar una búsqueda secuencia1 sobre la tabla, y aún más ya que el índice también se recomó.

4.6.1.4.1 Elección del indice para Procesar una Subconsulta

A continuación se presenta el pseudocódigo utilizado para determinar el índice adecuado para procesar las subconsultas.

1 Asignar a la variable Igualdad-ContiguaAnt un valor de O 2 Asignar a la variable TotalColsAnt un valor de O

3 REPETIR 4 Obtener el número de columnas del índicemurnInd] de la tabla

que puede usarse para la subconsulta 5 Asignar a la variable ColsdeInd un valor de O 6 PARA el total de columnas del índice HACER 7 8 9 10 11 FIN PARA

12 13

Incrementar en 1 la variable ColsdeInd SI la columna del índice se encuentra en la subconsulta ENTONCES

SI el operador relaciona1 contra el que se compara es de igualdad ENTONCES Incrementar en 1 la variable Igualdad-Contigua

SI Igualdad-ContiguaAnt = Igualdad-Contigua ENTONCES SI Colsdeind < TotalColsAnt ENTONCES

55


14 15 16 FIN SI

17 SI Igualdad-ContiguaAnt 4 Igualdad-Contigua ENTONCES 18 19 20 FIN SI 21 Incrementar en uno la variable NumInd 22 HASTA que NumInd sea igual al número de índices declarados para la tabla

Guardar el valor de igualdad-Contigua Guardar el valor de Numúid

Asignar a la variable Igualdad-ContiguaAnt el valor de la variable Igualdad-Contigua Guardar el valor de NumInd

La variable Numind es un parámetro que indica el número de índice sobre el cual se efectúa el análisis. El valor inicial de esta variable se toma de los resultados obtenidos del algoritmo de la Sección f&5:3,:iL, el cual indica a pariir de cuál número de índice de la tabla debe de comenzar el examen para determinar el mejor índice disponible que se tiene para procesar la subconsulta.

En la línea 10 se incrementa en 1 el valor de la variable Igualdad-Contigua cada vez que se encuentra que una columna de la llave del índice examinado está en la subconsulta y además, se compara con un operador de igualdad. La manera como se obtiene cada columna del índice es de acuerdo al orden en que fueron declaradas, y por lo tanto se asegura que las columnas encontradas en la subconsulta se&irán para poder crear la llave.

La variable Igualdad-ContiguaAnt se utiliza para determinar cuál de los índices analizados es el que tiene el mayor número de columnas presentes en la subconsulta que se comparan con un operador de igualdad. Su valor se modifica (línea 18) cada vez que el índice analizado tiene mayor número de igualdades que el índice examinado anteriormente. Por lo tanto, el último valor que tenga dicha variable es el número mayor de igualdades encontradas para un índice.

La variable TotalColsAnt se utiliza para escoger un índice en el caso en el que se encuentren dos índices que tengan el mismo número de columnas que se comparan con un operador de igualdad (linea 12). Para determinar el índice en estos cams, es necesario comparar el número total de columnas del índice examinado contra el número de columnas del índice anterior. Si aquél es menor (línea 13) entonces el índice examinado es el índice a utilizar, de otra forma el índice adecuado es el anterior. Supóngase que se tienen dos índices: el primero formado por 4 columnas y el segundo por 2. Para el primero sólo dos de sus columnas están presentes en la subconsulta; por lo tanto, el valor de la llave queda incompleto, obligando a realizar una búsqueda secuencial sobre el índice hasta encontrar una llave cuyo valor de estas dos columnas sean diferentes a los valores contra los cuales se están comparando en la subconsulta. En cambio en el segundo caso la búsqueda de la llave se realizará de manera directa, ya que se conocen todos los valores de las columnas de la llave.

56

CAPITULO 4 PLANTEAMIENTO Y SOLUClON DEL PROBLEMA

Al fmaiizar la ejecución de este algoritmo, los resultados que se obtienen son el número de índice que se utilizará para resolver la subconsulta (el cual queda indicado por la variable Numind) y el número de columnas de este índice que se encontraron en la subconsulta. Conocer el número de columnas es importante, ya que se sabe cuántos valores de columnas de la llave se tienen para formarla.

La identificación del índice para procesar la consulta no es suficiente para encontrar los valores de llaves, es necesario considerar los siguientes aspectos:

- Qué tipo de búsqueda se realizará sobre el índice. El hecho de que un índice esté ordenado permite que se puedan realizar diferentes tipos de búsqueda sobre él, las cuales pueden ser búsqueda secuencia] ascendente o secuencial descendente. Cuando se efectúa cualquiera de estas búsquedas, significa que se requiere más de un valor para la llave. Por ejemplo para la subconsulta del Ejemplo H, suponga que existe un índice defindo sobre la columna PNo de la tabla P.

Ejemplo H: 1 c)

PNo>='P3' AND Color='Azul'

Para esta subconsulta se requiere obtener todas aquellas piezas cuyo número sea P3 o un valor mayor. Por io tanto, se necesita realizar una búsqueda secuencial sobre el índice, la cual se iniciará con la búsqueda del valor de llave P3 y continuará hasta encontrar el último valor de llave del índice. Esto se debe al hecho de que el índice está ordenado de tal forma que todos los valores de llave subsecuentes a P3 son mayores a este valor. Debido a que los valores que se requieren son mayores a P3 y éstos se encuentran después que este valor, el tipo de búsqueda a efectuar es ascendente. Si se cambiara el operador relacional '>=' pÓr el operador 'e=' significa que la búsqueda sena ascendente hasta encontrar la primera llave del índice. Con este ejemplo se observa que el hecho de cambiar el operador por otro implicó el cambio del tipo de búsqueda, por lo que se puede establecer que los que determinan el tipo búsqueda son los operadores relacionales.

Defdr cuáles valores de llave se necesitan buscar. Sobre un índice se puede realizar una búsqueda de un conjunto específico de valores de llave, el cual puede ser un rango. Por ejemplo para la siguiente subconsulta:

-

PNo>='Pt' AND PNo<='PS'

Como se puede observar lo que se requiere es obtener aquellos valores que estén entre P2 y P5. Por lo tanto es posible determinar cuáles valores de llave se van a buscar en el índice, ya que se puede definir el primer y último valor que debe tomar la llave. Esto es posible debido a que los operadores relacionales '>=' y 'e=' acotan el número de llaves.

PLANTEAMiENTO Y SOLUCION DEL PROBLEMA c m m o 4

De acuerdo con los puntos anteriores, se aprecia la importancia de identificar con qué tipo de operador relacional se comparan las columnas de la llave en la subconsulta para determinar el tipo de búsqueda sobre el índice, el valor que debe tomar la llave, y el número de búsquedas.

Dependiendo del operador relacional que se presente, es posible definir el tipo de búsqueda. La siguiente tabla muestra el tipo de búsqueda de acuerdo con el tipo de operador:

<, <=

I < = y >= I secuencial descendente en rango I secuencia] descendente en rango

secuencial. ascendente en rango

secuencial ascendente en rango

>= y <=

'p 4.6.1.4.2 Algoritmo para la Defmción del Tipo de Búsqueda sobre el indice =

Mediante el siguiente algoritmo se define el tipo de búsqueda a realizar sobre el índice, valor o valores de las llaves a buscar; y además se obtienen los operandos en los cuales las columnas de éstos no están presentes en el índice.

1 PARA el número de columnas del índice en la subconsulta HACER 2 SI la columna aparece una vez en la subconsulta ENTONCES 3 4 5 6 7 8 9

10 FIN CASO 11 FIN SI

Analizar tipo de operador relacional EN CASO de que el operador sea:

= : Asignar a la variable Tipo-rango un valor de O >,>= : Asignar a la variable Tipo-rango un valor de 1

<,<= : Asignar a la variable Tipo-rango un valor de 3 Guardar el valor con el cual se está comparando la columna

Guardar el valor con el cual se esta comparando la columna

12 13 14 15 16

SI la columna se encontró dos veces en la subconsulta ENTONCES Asignar a la variable RangoLLave un valor de verdadero Analizar los operadores relacionales bajo los cuales se compara el columna

SI el primer operador es < o <= y el segundo operador es 7 o >= ENTONCES Asigna a la variable Tipo-rango un valor de 5

58

~ L , ~ T E A M I E N T O Y SOLVClON DEL PROBLEMA CAPITULO 4

17 18 19 FIN SI

20 21 22 23 24 FIN SI 25 FIN SI

26 Guardar el nombre de la columna, valor de comparación y operador relacional de aquellas columnas de la subconsulta que no sean columnas del índice

27 Guardar el valor de la variable Tipo-rango 28 FIN PARA

Guardar el primero valor encontrado para la columna Guardar el segundo valor encontrado para la columna

SI el primer operador es > o >= y el segundo operador es < o <= ENTONCES Asignar a la variable Tipo-rango un valor de 7 Guardar el primer valor encontrado para la columna Guardar el segundo valor encontrado para la columna

En las líneas 5, 6, 8, 16 y 21 se asigna un valor diferente a la variable Tipo-rango. Este valor depende del tipo de operador relacional contra el cual se compara la columna del índice, y se utiliza para identificar el tipo de búsqueda que se realizará sobre éste.

En las líneas 7 y 9, para cada columna del índice se guarda el valor contra el cual se compara, con el fin de poder formar la llave de búsqueda.

La variable RangoLlave se utiliza para identificar el caso en el se debe buscar un rango de valores para la llave. Para ello se necesita guardar el primer y segundo valores contra los cuales se compara la columna del índice encontrado dos veces en la subconsulta. Esto tiene por objeto saber cuál es el primer valor que tomará la llave y cuál el último.

En la línea 26, la columna de cada operando de la subconsulta que no esté presente en el índice, debe guardarse para verificar que el valor que tenga esta columna en el renglón asociado a la llave buscada satisfaga la condición del operando.

La siguiente estructura se utiliza para almacenar el operando cuya columna no es columna del índice:

Tprimary=RECORD ClaSeP: Tprimary Clase; NulopP BOOLEAN; DesdeP INTEGER NombreP STRING[12]; Longp: BYTE;

59

il il

' ' i ,

PLANTEAMIENTO Y SOLUCION DEL PROBLEMA CAPITWO 4 !I !!

CASE TipoP: BY'EOF 1: (CharP STRING); 2: (IntP: ! INTEGER 3: (LmtP LONGINT); 4: ( R e a p REAL); 10: (OperadorP 1 CHAR); 20: (OperRelP: ' BYTE); 30: (OperLogP: CHAR); 40: (PredicadoP ~ BYTE );

END; END;

Para almacenar los operandos cuyas columnas no están presentes en el índice, se crea una I¡

lista, en donde cada nodo es del tipo de la estructura anterior. i

Cada columna del índide que se encuentra, se almacena en un estructura como la siguiente:

I/ TipoColLLave= RECORD

TipoBusq TipoCol: CadA, CadB: Tint 1, Tint2 m i n t 1, RLint2: TReal 1 , Treal2: Tdatel, Tdate2:

END;

donde:

TipoBusq

T1poCol

CadA

BYTE, BYTE,

STRING[90];

INTEGER;

LONGINT;

REAL; II

LONGINT;

II

\

indica el tipo de búsqueda a realizar sobre el índice y si'existe un rango de valores de llaves a buscar.

Indica el tipo de dato (Char, real, Integer, date, etc.) de la columna de la llave.

Almacena el primer valor de la columna cuando es de tipo cadena I)

60

I/

CAPlTULO 4 PLANTEAMENTO Y SOLUCION DEL PROBLEMA

CadB

Tint 1 TInt2

TLmt 1 TLint2

Almacena el segundo valor de la columna cuando es tipo cadena

Almacena el primer valor de la columna cuando es de tipo entero Almacena el segundo valor de la columna cuando es de tipo entero

Almacena el primer valor de la columna cuando es de tipo longint Almacena el segundo valor de la columna cuando es de tipo longint

11

TReall TReal2

Tdatel Tdate2

Almacena el primer valor de la columna cuando es de tipo real Almacena el segundo valor de la columna cuando es de tipo real

Almacena el primer valor de la columna cuando es de tipo fecha. Almacena el segundo valor de la columna cuando es de tipo fecha.

Al terminar de efectuar el análisis se obtiene una lista como se ihstra en la Figura 4.5, donde cada nodo es del tipo TipoColLlave. Cada nodo representa una columna del índice.

I

TipoBuFp 1 TipoCol 1

i Figura 4.5. Lista Ltavalsllave para las Columnas del Indice

4.6.1.4.3 Algoritmo de Búsqueda de las Llaves

A continuación se presenta el pseudocódigo para realizar la búsqueda de la(s) llave(s) y almacenar los renglones asociados a las llaves buscadas.

I! 1 PROCEDIMIENTO Busca-llaves(CondRango:BOOLEAN;Ltavalsllave:TipoCol~ve;

2 COMIENZO Cond busq:Tprimary ;PosInd:BYTE;Indice:Tindice);

3 4 Forma-Llave(LtaLlave,Clave); 5 BuscaLlave(indice,Noreg,Clave,Encontro) ;

SI CondRango Y LtaLlave:.Tipobusq EN [3,4] ENTONCES

61

II PLANTEAMIENTO Y SOLUCION DEL PROBLEM

CAPITULO 4

6 MIENTRAS (Encontro) HACER 7 GetRec(Tabla,Noreg,SizeRecft,Sqlbuf) 8 SI RegcumpleWhere(Condbusq) ENTONCES 9 GuardaRegistro(N0reg); 10 SI LtaLlave^.TipoRango= 3 ENTONCES 11 12 DE OTRO MODO 13 AntLLave(indice,Noreg,Clave,Encontro) 14 FIN MIENTRAS 15 FIN SI 16 DEOTROMODO 1 17 REPETIR 18 Fonna-Llavel(LtaLLave,Clave,Clavel); 19 LtaLlave:=LtaLlave^,sig ; 20 HASTA (LtaLLave^.TipoBusq EN [7,10]); 21 TenninaRango:-False; 22 BuscaLlave(indice,Noreg,Clave,Encontro); 23 24 GetRec(Tabla,Noreg ,SizeRecft,Sqlbuf) 25 SI RegcumpleWhere(Condbusq) ENTONCES 26 GuardaRegistro(N0reg); 27 TerminaRango:=Comparacion(Clave,LiaLLave* .OperRel,Clavel); 28 SI LtaLiave^.TipoBusq= 7 ENTONCES 29 SigLiave(Indice,Noreg ,Clave,Encontro) 30 DE OTRO MODO 31 AntLLave(Indice,Noreg ,Clave,Encontro) 32 FIN MIENTRAS 33 FIN DE OTRO MODO 34 SI (NO(CondRang0)) ENTONCES 35 Forma-Liave(LtaLLave,Clave 1); 36 31 Clave:=Clavel ; 38 SI (Encontro) ENTONCES 39 REPETIR 40 GetRec(Tabla,Noreg,SizeRecft,Sqlbuf) 41 SI RegcumpleWhere(Condbusq) ENTONCES 42 GuardaRegistro( Noreg); 43 SigLlave(Indice,Noreg,clave,encontro) 44 45 FIN SI; I,

46 CloseIndex(Indice.NombreInd); 47 FIN PROCEDIMIENTO

SigLlave(Jndice,Noreg ,clave,Encontro) 1)

1

MIENTRAS (Encontro) Y (NO(TerminaRang0)) HACER

1

BuscaLLave(Tndice,Noreg,Clave,Encontro) ; I/

HASTA (NO (Encontro)) O (NO (Clavesiguales(Clave,Clavel)))

62

PLANTEAMENTO Y WLWION DEL PROBLEMA CAPITULO 4 ,I

~a vanable CondRango indica que existe una búsqueda de más de una llave Y que se va a realizar una búsqueda secuencial sobre el índice.

~a condición que se presenta en la línea 3, indica que se realizará una búsqueda secuencial sobre el índice, y ésta será ascendente (línea 11) si el valor del campo TipoRango tiene un valor de 3, y en caso contrario se realizará una búsqueda descendente (línea 13). La función SigLlave busca la siguiente llave de la llave que toma como parámetro de entrada en la variable Clave, y la función AntLlave busca la llave anterior.

En la línea 17 se consideran los casos en los que existe un rango de búsqueda sobre el índice, para lo cual se necesita tener dos variables para poder llevar a cabo la búsqueda: Clave y Clavel. La primera variable toma un valor inicial que indica el primer valor del rango de llaves a buscar; posteriormente su valor se modifica cada vez que se realiza una nueva búsqueda sobre el índice. La segunda variable to& el último valor del rango. Para efectuar las búsquedas sobre el índice, se ejecuta un ciclo (línea 23), dentro del cual el valor obtenido para la variable Clave en cada búsqueda se compara contra la variable Clavel para verificar que el valor de aquélla no esté fuera del rango solicitado; cuando ésto sucede se termina el ciclo.

En la línea 34 se considera el caso en que las columnas del índice se comparan bajo operadores de igualdad. Para este caso puede pensarse que sólo se necesita buscar un solo valor de llave sobre el índice; ésto es posible cuando se conocen todos los valores de las columnas de la llave. Pero no siempre es así, por lo que puede suceder que varias llaves del índice tengan iguales los valores de las columnas conocidas de la llave, por esta razón se ejecuta un ciclo (linea 39) para llevar a cabo la búsqueda de estas llaves. La variable Clavel toma un valor inicial con los valores de las columnas conocidos de la llave y su valor se moditica cada vez que se realiza una búsqueda en el índice. La variable Clave toma el valor de la variable Clavel, y se utiliza para veririficar que los valores de las columnas de la llave buscada sean iguales a los valores de los columnas conocidos para la llave.

4.7. El problema de los Renglones Duplicados

Cuando se divide una consulta en subconsultas, puede suceder que un renglón de la tabla satisfaga las condiciones de dos o más subconsultas; por lo tanto, cuando este renglón sea seleccionado para operar sobre él, ya sea para borrarlo, actualizarlo o bien para consultarlo, será accesado tantas veces como subconsultas satisfaga, ocasionando los siguientes problemas:

- s i la operación que se relaliza es un SELECT, íos resultados para ia(s) coiumna(s) que se solicite(n) en esta cláusula serán mostradas al usuario tantas veces como el renglón de la tabla satisfaga un número de subconsultas. Por ejemplo, si la consulta original se divide en las subconsultas A, B y C, y un renglón satisface las subconsultas A y C, entonces en el resultado aparecerán dos renglones repetidos.

63


si la operación a realizar es un UPDATE, el renglón se modificará el número de veces que cumpla las condiciones para las subconsultas. Considerando el ejemplo anterior, supóngase que un renglón satisface las subconsultas B Y A; por 10 tanto, el renglón se actualizará dos veces, io cual provoca que el tiempo de procesamiento se incremente.

Cuando la operación que se realiza es un DELETE, el renglón de la tabla se intentará borrar cuantas veces satisfaga un número de subconsultas. Continuando con el ejemplo supóngase que un renglón satisface la condición para las subconsultas B y C. Entonces para la primera vez que éste se borre no habrá ningún inconveniente ya que existirá en la tabla. El problema seipresenta para la segunda vez, cuando nuevamente se intente borrar el renglón, ya que éste no se encontrará. Supóngase que el programador despliega un mensaje cada vez que se borra un renglón, entonces el mensaje enviado para la segunda vez será incongruente, ya que se dirá que el renglón no existe y por lo tanto no

CAPITULO 4

11 -

-

puede ser borrado. I1

Las consideraciones anteriores son suficientes para darse cuenta que el problema es grave debido a los resultados que se presentan al usuario.

Antes de plantear la solución a este problema, se describirá la forma en que anteriormente se efectuaba el proceso de selección de renglones de la tabla que satisfacen la condición de búsqueda para las instrucciones SELECT, UPDATE y DELETE, con el fin de establecer, primero por qué no sucedía este problema y segundo entender los cambios que tuvieron que hacerse.

como se mencionó en la Sección 4.5, la cláusula WHERE tiene como función apiicar a cada uno de los renglones de la tabla una condición de búsqueda, produciendo UM tabla resultante formada por todos aquellos renglones que satisfacen la condición de búsqueda. El proceso conceptual utilizado para obtener los resultados de la ejecución de esta cláusula es el siguiente:

1. Para la tabla resultante se creaba un archivo en el cual sólo se guardaba la posición física (número) de los renglones que satisfacían con la condición de búsqueda. La ventaja de guardar sólo la posición y no el contenido del renglón es que no se duplicaba la información de cada renglón.

Para encontrar los renglones que satisfacían la condición, el archivo de la tabla se recom’a desde el primer registro hasta el Último, aplicando a cada renglón la condición de búsqueda, si el renglón la cumplía se guardaba la posición física de éste. El hecho de recorrer secuencialmente’el archivo, implicaba que sólo una vez se accesaba cada renglón; debido a ésto nunca sucedía que un renglón se accesara más de dos veces, y por lo tanto nunca se tenían renglones duplicados.

11 2.

11

64

PLANTEAMBNTO Y SOLUCION DEL PROBLEMA CAPITULO 4

I1 Dada la ventaja de crear un archivo en el cual sólo se guarden las posiciones físicas de

los renglones, se conservó esta estructura, y lo que se modificó es la forma de guardar las posiciones de los renglones.

I I

Puesto que se necesita que ningún valor que representa la posición del renglón se repita, es necesario que antes de que sea almacenado, se realice un búsqueda de este valor sobre el archivo. Si la búsqueda sobre el archivo se realizara de manera secuencial, consumiría un tiempo excesivamente grande, debido a que los valores se encuentran desordenados. Supóngase que se tuvieran lo00 valores en el archivo, y que se deseara guardar un nuevo valor para un número de renglón; en este caso se necesitm'an realizar lo00 comparaciones entre este número de renglón y cada valor que este en el archivo para determinar que no existe y decidir guardarlo. De acuerdo con lo anterior, es necesario ordenar el archivo y aplicar una técnica de búsqueda para que la inserción de un valor de número de renglón se realice de manera más eficiente.

L a ordenación del archivo se realizó en base a los valores de las posiciones de renglón, y la técnica utilizada para efectuar tanto la búsqueda como la inserción de un nuevo valor es la explicada en la Sección 3.4. La pstructura del archivo es la que se muestra en la Figura 4.6.

Contador PAg. Extra de Elern[ll . Elsm[Comdorl

I! Referencia

Contado,

Contador I I I I I I

"' E*ra de EIem[ll . . Els~Confador]

' "' E*ra de Elern[ll * Elem[Contador] 1 Referencia

Referencia

Figura 4.6. Estructuq del Archivo que guarda las Posiciones de Renglón

4.8. El problema de la Tabla Derivada de la Cláusula FROM II

A partir de esta sección se presentan los problemas y soluciones para efectuar el proceso

Como se describió en la Sección 3.2.3.1, la cláusula FROM especifica una tabla derivada.

Puesto que la tabla derivada es el resultado del producto cartesiano efectuado entre las tablas indicadas en la cláusula FROM, para obtenerla se realiza una gran cantidad de

de optimizacion cuando se especifican dos o más tablas en la cláusula FROM.

Dada la forma de obtener el contenido de esta tabla, se presentan los siguientes problemas:

1.

! 65

PLANTEAMIENTO Y SOLUCION DEL PROBLEMA CAPITUXO 4

accesos a los archivos de las tablas, provocando que el tiempo que se utiliza para SU procesamiento sea muy qande.

Otro problema, derivado de la ejecución del producto cartesiano, es que el tamaño del archivo para la tabla derivada es muy grande, por lo que para su almacenamiento se requiere una gran cantidad de espacio de memoria secundaria.

Para obtener los renglones de esta tabla que satisfagan la condición de búsqueda, es necesario recorrer todo el archivo de principio a fin, para verificar cuáles de éstos satisfacen la condición. Por lo tanto, se realiza un gran cantidad de accesos a disco, lo que provoca que el tiempo de brocesamiento y de respuesta aumenten considerablemente.

La existencia de los problemas anteriores es suficiente para darse cuenta de la importancia

2.

3.

de reducir el tamaño de esta tabla en lo más posible.

11 4.8.1 Uso de la Cláusula SELECT para Determinar el Grado de la Tabla Resultante

SELECT es la última cláusula@ que se ejecuta, y obtiene un conjunto de valores de columnas de cada renglón de la tabla generada en la anterior cláusula WHERE.

La sintaxis para el SELECT es la siguiente:

SELECT [ALLIDISTINTC] <lista del select> I

en donde clisca del seleet> es una lista de nombres de columnas cuyos valores se desean obtener. Cuando se define más de un nombre de tabla en la cláusula FROM, las columnas solicitadas de la tabla derivada el: la cláusula SELECT, deben tener especificado el nombre de la tabla a la cual pertenecen, con el fm de evitar confusiones en el caso de que el nombre de una columna se repita en dos o 'más tablas.

Siendo SELECT la Última cláusula en ejecutarse, es posible pensar que el contenido de la tabla resultante debe estar compuesto sólo por los valores de las columnas especificadas en esta cláusula, logrando que el tamaño de la tabla se reduzca.

Considerando lo anterior, es necesario cambiar el orden de ejecución para la instrucción SELECT, de tal forma que la primera instrucción en realizar sea precisamente ésta, con el objetivo de identificar el número y nombres de columnas especificadas en ella.

It

Para resolver este problema se aprovechó el código producido por el precompilador para la instrucción SELECT. Para entender mejor, a continuación se presenta el código producido para el ejemplo de la siguiente conshta.

li 66

CAPITULO 4

Ejemplo I:

I/ PLANTEAMIENTO Y SOLUCION DEL PROBLEMA

SELECT SP.PNo, S.sNo

WHERE SP.SNo=S.SNo

1 AND SP.PNo=P.PNo 11

~ FROM S,P, SP

AND P.PNombre='Tuerca'

USES SQL BEGIN I

1 -SET-DEFAULTT~NAME; 2 _SETLONG-REGTQUERY(258); 3 -MTOPSTATUS('SELECT AN); 4 MTOPC('SPSNo',1,5,3 1 ,FALSE);

6 -MTOPC('S.SNo', 1,7,30,FALSE); 7 -MTOPS; 8 -MTOPSTAT%('WHERE '); 9 -MTOPPRED(l); 1 10 MTOPC('SP.SNo', 1,5,31,FALSE); 11 MTOPS; 12 MTOPOR('='); 13 -MTOPC('S.SNo 1 7 30,FALSE);

15 -MTOPPRED(l); 16 MTOPC('P .PNombre',3,5,4,FALSE); 17 MTOPS; 18 -MTOPOR('='); I 19 -MTOPL 1 ('Tuerca'); 20 -MTOPS; 21 MTOPOL('@'); 22 -MTOPPRED(l); !I 23 -MTOPC('SP.PNo', 1,61,21,FALSE); 24 MTOPS; 25 -MTOPOR('='); 26 -MTOPC('P.PNo', 1,912 1 ,FALSE); 27 -MTOPS; 28 MTOPOL('@'); 29 MTOPS; 30 MTOPSTATUS('FR0M SP S Y); 31 -EXEC-SELECT,

5 MTOPS; II

14 -MTOPS; " ' I )

END.

67

PLANTEAMWTO Y SOLUCION DEL PROBLFMA

i CAPITULO 4

El procedimiento -MTOPSTATUS recibe como entrada UM cadena, la cual indica el nombre de la cláusula de la instrucción que se ejecutará. Para la cláusula FROM se indican las tablas sobre las cuales se realizará el producto cartesiano.

'I El procedimiento -MTOPC recibe como entrada los datos de la columna solicitada, ya

sea para la cláusula SELECT (líneas 4 y 6) o para la cláusula WHERE (líneas 10, 13, 16,23 y 26). Este procedimiento se llama tantas veces como columnas aparezcan en las cláusulas SELECT y WHERE.

Como se puede observar, en el código anterior los llamados al procedimiento -MTOPC se efectúan después de que se llaha al procedimiento -MTOPSTATUS; ésto es para identificar cuáles son las columnas que se solicitan para la cláusula especificada en el argumento de entrada para este procedimiento. Para nuestro objetivo de identificar las columnas de la tabla derivada, inmediatamente después de que se termina de ejecutar el procedimiento -MTOPSTATUS de la línea 3, para cada llamado al procedimiento -MTOPC, el nombre de la columna se almacena dentro de un contenedor (buffer).

I1 4.8.2. Análisis de la Condición WHERE cuando se Especifica Más de un Nombre de

tabla en la Cláusula FRPM

Cuando en una cláusula FROM se declara más de UM tabla, significa que se está buscando información de m á s de una tabla, en donde por medio de la cláusula WHERE se expresa la conexión entre las tablas para obtenerla, al efectuar comparaciones entre las columnas de las tablas. Por ejemplo, para la consulta "obtener todas las combinaciones de número de proveedor, número de parte tal que el proveedor y la parte estén localizados en la misma ciudad, puede formularse en SQL de la siguiente manera:

Ejemplo J: SELECT S.SNo, P.PNo @OM S, P WHERE S.Ciudad=P.Ciudad

De acuerdo con el enunciado es evidente que los datos requeridos provienen de las tablas S y P. En consecuencia en la formulación de SQL de la consulta, se nombran las dos tablas en la cláusula FROM, y en la cláusula WHERE se establece la relación entre las tablas al comparar las columnas Ciudad de ambas tablas.

I/

Dado que en la cláusula WHERE se hace referencia a las columnas de las tablas especificadas en la cláusula FROM, es posible efectuar un análisis sobre ésta mediante el cual es posible identificar situaciones como la existencia de índices asociados a las tablas o de índices temporales mediante los cuales kea posible recuperar los renglones de manera eficiente.

68

PLANTEAMIENTO Y SOLUCiON DEL PROBLEMA

Antes de explicar la forma de efectuar el análisis de la expresión de la condición WHERE, se presentan los siguienies ejemplos cuyo propósito es mostrar cómo el uso de índices permite recuperar los renglones, en forma eficiente, cuando en una condición se presenta la comparación de una columna contra otra. Considérese la subconsulta del ejemplo K obtenida de la consulta del ejemplo J, donde la cardmalidad de la tabla S es de 300 y la de la P es de 200.

CAPITULO 4

11

Ejemplo K: I’ S.Ciudad=P.Ciudad

1. Suponga que existe el índice Ciudad definido sobre la columna Ciudad para la tabla P en el que se puede efectuar /a búsqueda de cada valor de la columna Ciudad de la tabla S, de tal forma que no se necesita realizar UM búsqueda secuencial de este valor en la tabla P. Realizando ésto, el acceso al renglón de la tabla P en el cual el valor de la columna Ciudad es igual al valor de la columna Ciudad de la tabla S es directo. Si el índice no se utilizará, entonces para d d a valor de la columna Ciudad se tendría que realizar una búsqueda sobre la tabla P, por lo que para los 200 valores de esta columna se necesitarían aproximadamente 60,000 búsquedas sobre la tabla P.

Suponga que no existe ningún índice defmido para la tabla P ni para la tabla S, entonces conviene crear un índice temporal sobre la columna Ciudad a una de las dos tablas para evitar la búsqueda secuenkial de cada valor de la columna Ciudad de una tabla sobre la otra. Para obtener el contenido de este índice se necesita leer una vez todos los renglones de la tabla. Por ejemplo, si se crea el índice a la tabla P sobre la columna Ciudad se requieren 200 lecturas1 sobre esta tabla para obtener el contenido del índice. Posteriormente para realizar la búsqueda de cada valor de la columna Ciudad de la tabla S , ésta se hará sobre el índice, con lo cual se evita realizar 300 búsquedas de este valor sobre la tabla P. Respecto al tiempo se puede pensar en que se está consumiendo más debido a la creación del hdice; pero no es así, puesto que el tiempo utilizado para la creación de éste es aproximadamente igual al tiempo utilizado para la búsqueda secuencial sobre de un sólo valor sobre la tabla.

2.

Con estos ejemplos se &fiesta la importancia de aplicar el proceso de optimización mediante el uso de índices, para el caso en el que se especifica más de una tabla en la cláusula FROM. II

hes to que la expresión de la cláusula WHERE puede involucrar operadores OR, entonces es posible dividirla en subconsultas. Para lo cual se puede aplicar el algoritmo de la Sección 4.3.5.3.1, el cual realizalla descomposición de la condición de búsqueda en subconsultas. Debido a que en una condición se puede presentar la comparación de una columna contra otra (ver Ejemplo K) y que es posible def& un índice temporal sobre una tabla (ver ejemplo 2) entonces se deben tomar en cuenta las siguientes situaciones para llevar a cabo la determinación de las subconsultas:

69

PLANTEAMIENTO Y SOLUCION DEL PaOBLEMA

condición para terminar el proceso de determinación de 1% subconsultas cuando se define una sola tabla en lla cláusula FROM, se daba cuando ninguna columna de las condiciones de la subconsulta pertenecía a un índice. Para el caso en el que se d e f h n más de dos tablas es posible crear un índice temporal (ver ejemplo 2);entonces cuando se fomen las subconsultas'b suceda que ninguna columna de las condiciones sea columna de un índice, se podrá continuar el proceso de determinación de subconsultas.

Si la kbconsulta analizada es una expresión formada por operadores AND, y existe una condición en la que se efectúa una comparación de una columna contra otra donde ninguna de estas columnas,pertenece a un índice y en la otras condiciones de la expresión se presenta la comparación de una columna contra un valor conocido donde alguna(s) de la(s) columna(s) de las condiciones pertenecen a un índice; entonces para procesar la subconsulta no será necelrio crear un índice temporal a cualquiera de las dos tablas de la condición en la que se efectúa la comparación entre dos columnas puesto que ya existe. Por ejemplo supóngase, que para la siguiente subconsulta:

i CAPITW.0 4

-

7

-

li SP.PNO=P.PNo AND P.PNombre='Tuerca'

existe un índice declarad? sobre la columna PNombre, entonces al encontrar el valor de llave Tuerca en el índice, se podrá saber qué valor tiene la columna P.No al accesat el renglón asociado a la llave y obtener el valor de esta columna.

Si la subconsulta analizada es una expresión que tiene más de una condición, donde una de ellas consiste de una comparación de una columna contra otra y para las otras condiciones se da una domparación de una columna contra un valor conocido donde ninguna de las columnas pertenece a un indice; entonces para poder resolver la subconsulta se tiene que 1 crear un índice temporal, con el fin de evitar la búsqueda secuencial sobre una de 1:s tablas. El índice se definirá sobre alguna de las tablas de la condición en la que se compara una columna contra otra.

,A continuación se presenta el pseudocódigo del procedimiento creado para considerar los

1 -

i casos anteriores:

coilds- dpJcOls ,%tOl\*b 1 PROCEDIMIENTO Conds-pdraJOIN(Operando:Pointer~yList; Var TipoJoin:STRING) 2 ColenInd:=ColperteInd(OperandoA.ItemP.NombreP,Noind); 3 NoaCad(NoInd,StrNoInd); 4 TipoJoin:=OperandoA.ItemP.NombreP;

5 6 I TipoJoin:b?' + TipoJoin;

SI (Colenhd) Y (Operanho^ .SigP^.SigP^ .ItemP.clasep=ESPCOL) ENTONCES TipoJoin:= TipoJoin + OperanodA.SigPA .SigP^.NombreP;

8 FINSI !

70

II !

PLANTEAMIPíTO Y SOLUCION DEL PROBLEMA CAPITULO 4

9 10 11 12 TipoJoin:= ‘ A + TipoJoin, 13 DE OTRA FORMA ‘I

14 15 FIN SI

16 17 TipoJoin:=TipoJoin + Operando^.SigP^ .SigP*.ItemP.NombreP; 18 19 FINSI 20 FIN PROCEDIMIENTO

SI NO(Co1enlnd) Y (Opejando^.SigP” .SigP .ltemP.clasep=ESPCOL) ENTONCES TipoJoin:=TipoJoin + Operando^ .SigP* .SigP^ .ItemP.NombreP; SI Colperteind (Operando*. SigP” .SigP .ItemP.NombreP,Nohd) ENTONCES

TipoJoin:= ’S’ + StrNoind + TipoJoh

SI (ColenInd) Y ,(_oPrando^.SigP^ .SigP .ItemP.clasep<>ESPCOL) ENTONCES

TipoJoin:= ’I‘ + StrNoIpd + TipoJoin,

La variable Colenind se utiliza para saber cuándo el operando izquierdo de una condición en la que se efectúa la comparación entre dos columnas, es columna de un índice.

li En la línea 5 y 9 se considera el caso en el que en una condición se efectúa una comparación entre dos columnas. La línea 5 considera el caso especifico en que la columna izquierda de la condición pertenece a un indice, y la linea 1 1 considera cuando la columna derecha pertenece a un índice. 1

En la línea 16 se considera el caso en el que en un operando se realiza una comparación entre una columna y un valor constante; en donde la columna pertenece a un índice.

I! La variable TipoJoin se utiliza para guardar el nombre de la o las columnas de la

condición analizada. En las líneas 7, 12, 14 y 18 a esta variable se le concatena un valor que se utilizará para identificar que condición presenta la subconsulta para poder procesarla de acuerdo a las siguientes reglas:

1.

I

Cuando se concatena un +lor ‘P’ indica que existe una condición en la subconsulta en la que se efectúa una comparación de una columna contra otra, en donde la columna izquierda de la condición es columna de un índice.

Cuando se concatena valor ‘A’ indica que existe una condición en la subconsulta en la que se efectúa UM comparación de una columna contra otra, donde la columna derecha de la condición es columna de un índice.

Cuando se concatena un valor ‘S’ indica que ninguna de las columnas de la condición de la subconsulta es coltuya de un índice, y por lo tanto es necesario crear un índice temporal. I

2.

1 3.

71

PLANTEAMIENTO Y SOLUCION DEL PROBLEMA I CAPITULO 4

4. Cuando se concatena un ialor ’I’ indica que existe un índice en donde lab) columna(s) de éste se compara(n) contra un valor conocido.

Considerando el algoritmojantenor durante el análisis para definir las subconsultas, una vez que éste es terminado se creai!la estructura de la Figura 4.7 para cada subconsulta:

Verdadero P.PNombre

P.PNombre r,l SP CNo rq

1 Figura 4.7. Estructura para una Subcpnsulta

El campo CONiNDCE es una variable booleana que toma el valor verdadero cuando para la subconsulta existe un índice que pueda reducir su procesamiento. Cuando esta variable toma un valor falso significa que para esta subconsulta será necesario definir un índice temporal. El campo COLSIND es una variable de tipo cadena la cual almacena el valor que toma la variable TipoJoin al finalizar el análisis de la subconsulta. El campo APTCOND es UM variable que contiene la condición de la subconsulta.

4.8.3. Evaluación de las Subconsultas para Recuperar los Renglones

Cuando en una subconsulta se presentan varios operadores lógicos AND, no es muy sencilla su evaluación debido al akceso de múltiples renglones (los cuales pueden ser de la misma o de distintas tablas) con el fm de conocer los valores que satisfagan cada una de las condiciones que forman la subconsulta.

I Para aclarar la problemática planteada, se presentan los siguientes ejemplos:

Considérese la subconsulta del ejemplo M, para la cual se puede usar un índice definido sobre SNo. & ‘uo 7 sohn I& k&. 5P

Ejemplo M:

1. I/

S.SNO=SP.SNO AND SP.PN~=P.PN~

!I 12

I PLANTEAMIENTO Y SOLUCION DEL PROBLEMA

forma de la subconsulta indica que para resolver la condición S.SNo=SP.SNo, Para cada valor de la columna SNo de la tabla S, se necesita realizar una búsqueda de este valor sobre el índice. UM vez encontrado, para evaluar la condición SP.PNo=P.PNo se requiere accesar el renglón de la tabla SP asociado a la llave buscada para obtener el valor de la columna PNo, el que a su vez debe buscarse en la tabla P. Lo anterior se debe de ejecutar tantas veces como valores para la columna SNo existan en la tabla S.

Considérese la subconsulta del ejemplo N, en donde existe un índice (NúmProv) definido sobre la tabla SP sobre la columna SNo.

CAPITULO 4

2.

Ejemplo N: I1 S.SNo=SP.PNo AND S.Ciudad='Culiacán' AND SP.Cant=300

I

Para evaluar la condición S.SNo=SP.PNo, se accesa cada renglón de la tabla S y se obtiene el valor de la c o l h a SNo, el cual debe buscarse en el índice NúmProv de la tabla SP. Posteriormente para evaluar la condición S.Ciudad='Culiacán' se necesita accesar nuevamente el renglón de la tabla S; esta vez para obtener el valor de la columna Ciudad y verificar que satisfaga la condición de que sea igual a 'Culiacán'. Por último para determinar si se satisface la condición SP.Cant=300, se debe accesar el renglón de la tabla SP asociado a la llave bdcada para obtener el valor de la columna Cant y verificar que el valor obtenido para Cant sea igual a 300.

Para verificar que la se&nda condición del Ejemplo N (S.Ciudad='Culiacán') se cumpla, se necesita accesar por segunda' vez el renglón de la tabla S para obtener el valor de otra columna, en este caso de la c o l h a Ciudad; por lo tanto, se tiene que saber sobre qué renglón de la tabla se está operando, lo que sugiere guardar la posición del renglón de tal forma que se pueda accesar tantas veces comb valores de columnas de éste se requieran en la subconsulta.

Algo semejante se necesiia realizar para resolver la tercera condición del ejemplo 2 y la segunda condición del ejemplo 1. Para este caso se debe guardar la posición del renglón asociado a la llave buscada. l

I

Para dar solución a io expuesto anteriormente, se creó la siguiente estructura, con el objeto de guardar las posiciones ';de los renglones que se han accesado:

RengsAccesados= RECORD NomTab: STRING [12]; PosRenglón: LONGiNT;

END; 11

73

1

[ CAPITULO 4 PLANl?XMIENTO Y SOLUCiON DEL PROBLL'MA

donde: NomTab Guarda el nombre de la tabla a la que pertenece el renglón. PosRenglÓnl Guarda la posición física del renglón. 1

Para insertar un nombre de tabla y de posición de renglón en esta estructura, se debe verificar que el renglón de la tabla no haya sido accesado anteriormente. Por ejemplo, suponga que se examina la condición S.SNo=SP.SNo, donde el renglón de S del cual se obtendrá el valor de la columna SNo que se buscará en el índice es el 7. Siendo la primera vez que se accesa este renglón entonces se debe aimace& el nombre de la tabla S y la posición del renglón, quedando la estructura como se muestra en la Figura 4.8.

Fig-' 4.8. Inserción de los Valores S y 7

Después de efectuar la búsqueda de la columna SNo en el índice, imagine que el renglón de la tabla SP asociado a la llave buscada es el 10. Como no se ha accesado ni una vez este renglón, entonces se debe almacehar en la estructura el nombre de la tabla SP y la posición del renglón. Por io tanto, ai finalizar la evaluación de esta condición la estructura queda con los datos que se muestran en la Figura 4.9.

NomTab PosRenglon S I I

SP 10 I Figura 4.9. inserción de los Valores SP y 10

11 Cuando la condición que se analiza requiere saber el valor de una columna para un

renglón que ya fue accesado en otra condición, entonces se busca en la estructura de la Figura 4.9 el nombre de la tabla asocilo a la columna de la condición; si está se encuentra el campo Posrenglón indicará cuál es el renglón del cual se requiere conocer el valor para la columna.

Uno de los objetivos de aplicar el proceso de optimización, cuando se declara más de una tabla en la cláusula FROM, es el de reducir el tamaño de la tabla que resulta de aplicar el producto cartesiano entre las tablas declaradas en ésta, a tal grado que esta tabla contenga sólo aquellos valores de columnas que se solicitan en la cláusula SELECT. Esto se puede lograr de la siguiente manera:

Cada vez que se cumpla cada una de las condiciones de la subconsulta verificar en qué

I 74

CAPITULO 4

condiciones de ésta, la columna, se realiza una comparación enti SELECT, para almacenar las 1 columna(s) con el objeto de que , son los renglones de los que se cláusula.

De acuerdo a lo expuestc subconsulta que son las mismas de la estructura de la Figura 4.9 estas columnas.

4.8.4. Almacenamiento de los I; Cláusula SELECT

Cada vez que se haya determinado cuáles de los rengloi las columnas solicitadas en la cl éstos, para cuando se ejecute la obtener los valores de las colum diferentes tablas, es necesario CI subconsulta del Ejemplo$l, se tic

iJ\

€ Figura 4.10. I

Los valores de la tabla dc primer renglón, significa que el I tiene la columna SNo del rengló la columna PNo tiene el mismo suponga que en la cláusula SELI


columnas (cuando se tenga el caso en el que en la condición dos columnas) es la misma a la solicitada en la cláusula

siciones de los renglones a los cuales pertenece(n) la(s) iando se ejecute la cláusula SELECT sea posible saber cuáles :be obtener el valor para cada columna que se solicita en la

anteriormente, al determinar cuáles son las columnas de la las solicitadas en la cláusula SELECT, es posible hacer uso para saber de qué renglones se deben obtener los valores de

nglones para Obtener los Valores de Columnas de la

nnplido la condición de UM subconsulta que se haya contienen

isula SELECT, se hace necesario guardar las posiciones de áusula SELECT se pueda saber qué renglones accesu para as solicitadas en ésta. Dado que los renglones pertenecen a x una estructura que los almacene. Supóngase que para la Len los resultados que se muestran en la Figura 4.10.

bndiciones de la Subconsulta

's accesados durante la evaluación de la subco-ulta \

nglones que Satisfacen una Subconsulta

la Figura 4.10 se interpretan de la siguiente manera: para el iglón 1 de la tabla S en su columna SNo es igual al valor que 2 de la tabla SP, y que el renglón 2 de esta misma tabla en ilor que la columna PNo del renglón 7 de la tabla P. Ahora T se requieren conocer los siguientes valores de columnas:

ELECT S.Nombre, P.PNo

75

CAPITül,O 4 PLANTEAMWTO Y S O L W O N DEL PROBLEMA

Entonces se requiere guard& los renglones 1,3, y 5 de la tabla S y de la tabla P se deben almacenar los renglones 7, 9, 3 y’ 8, de tal forma que posteriormente, cuando se ejecuta la cláusula SELECT, se pueda saber cuáles son los renglones de la tabla S de los cuales se debe obtener el valor para la columna Nombre, y cuáles de los renglones de la tabla P se deben accesar para obtener el valor de la columna PNo.

I/

Como se puede observar, el valor que se debe guardar es la posición del renglón en la tabla. Entonces se puede utilizar la metodología de la Sección 4.3.5.5, la cual consiste en crear un archivo a la tabla para guardar las posiciones de los renglones. En este caso se crearán dos archivos: el primero almacenará iak posiciones de los renglones para la tabla S, y el segundo para la tabla SP.

I

De acuerdo a los resultadds de la tabla de la Figura 4.10, para la tabla S el renglón 1 aparece dos veces. Por lo tanto, cada vez que se quiera insertar un valor para la posición de un renglón, se debe verificar que no exista en el archivo. Para tal efecto se puede aplicar la técnica de inserción y búsqueda en un árbol B+.

I/ A continuación se presenta pl procedimiento para realizar la evaluación de la condición para cada subconsulta, en el cual se incluye el almacenamiento de las posiciones de los renglones, cuando alguna(s) de su(;) columna(s) se solicita(n) en la cláusula SELECT.

I1

1 PROCEDIMIENTO EvaluaSubcltas; 2 PARA j:=l A Totde- Subcltas HACER 3 TabCardinalidad(Subconlta[J1.ColsInd,TabMenorCardard,

4 SI CreaInd ENTONCES 1 5 CreaIndTemp( TabMay or Card) 6 OpenFile(TabMenorC) I 8 Obtiene-Valor(Subconltasfj].AptCond, ValComp); 9 RegisAbiertos(TabMayorCar,k,RengsActs); 10 CumpieCond(Subconltafj].AptCond,ValComp,

11 SI CumpCondAnd ENTONCES 12 AlmacenaRenglones(RengsActs) 13 FIN PARA 14 FINPARA 15 LlN PROCEDIMIENTO li

TabMa yoCard,TotRgtos,CreaInd)

PARA k=l A TotRgtos HACER

TabMenorCard,CumpCondAnd,RengsActs);

1 El procedimiento Tabcardinalidad (línea 3) se utiliza para determinar si es necesario crear

un índice temporal para procesar ,la subconsulta (ver Sección 4.3.5.5.2). En caso a f m t i v o la variable Creaind tomará un valor ;verdadero, a la variable TabMayorCard se le asigna el nombre

~ 76

CAPlTULO 4 PLANTEAMIENTO Y SOLUCION DEL PROBLEMA

de la tabla a la cual se le creará el índice, a la variable TabMenorCard se le da el nombre de la tabla de la cual se obtendrán los valores de columna que se buscarán sobre el índice creado y por último a la variable TotRgtos se le asigna el número de renglones que tiene ésta.

En la línea 6 se activa el procedimiento OpenFile para abrir la tabla que no tiene índice definido, ya que de ésta se obtendrán los valores de llave a buscar sobre el índice. En la línea 8 el procedimiento Obtiene-valor obtiene el valor del operando izquierdo de la condición que se analiza. En la líneaq$l'el procedimiento RegisAbiertos se encarga de almacenar en la variable RengsActs el nombre de la tabla y la posición del renglón cuando éste no haya sido accesado anteriormente.

16 En la linea &Z el procedimiento CumpleCond realiza la evaluación de cada condición de

la subconsulta. Si todas las condiciones se cumplieron la variable CumpCondAnd toma un valor verdadero. Las posiciones de los renglones que deben ser almacenados se obtienen de la estructura RengsActs.

la En la línea el procedimiento AlmacenaRenglones se activa cuando la variable

CumpCondAnd tiene un valor verdadero, almacenando las posiciones de los renglones para los cuales alguna o algunas de sus columnas son solicitadas en la cláusula SELECT.


Una vez que se han determinado cuáles son los renglones de los que se deben obtener los valores de las columnas solicitadas en la cláusula SELECT, es posible obtener el contenido de la tabla derivada, mediante la ejecución del producto cartesiano entre los archivos que almacenan las posiciones de los renglones. Para ello se obtiene de cada archivo la posición del renglón, se accesa el renglón en la tabla correspondiente, se obtiene el valor de la(s) columna(s) solicitadas en la cláusula SELECT y se almacena en un contenedor. Esto se repite tantas veces como archivos existan, del tal forma que al final el contenedor almacena todos los valores de las columnas requeridas en la cláusula SELECT. La información almacenada en el contenedor se guarda en un archivo sin tipo (este archivo representa la tabla derivada). El tamaño del registro del archivo es igual a la suma del tamaño de cada columna de la cláusula SELECT. La Figura 4.11 muestra gráficamente la forma de obtener el contenido de la tabla derivada.

77

CAPITULO 4

Tabla S

BuftwValCOls


Tabla P

Taüa Derivada

Figura 4.11. Procedimiento para Efectuar el Producto Cartesiano

A continuación se presenta el algoritmo para efectuar el producto cartesiano entre los archivos y para obtener la tabla derivada.

1 PROCEDIMIENTO ProduCarOptimo (NoArchiv0s:BYTE); 2 Num-a-Car(NoArchivos,No); 3 4 Assign(NomArch,ArchRgtos); 5 NomTabla(NoArchivos,Tabla); 6 Tabla.Nombre:=Tabla.Nombre + '.BD1' 7 Openfile(F,Tabla.Nombre,Tabla.TamRgto); 8 9 LeeRgto(ArchRgtos.NoReg); 10 GetRec(Tabla.Nombre,NoReg,Tabla.TamRgto,SqlBuf); 11 ObtenValCols(SqlBuf,BufferCols); 12 SI NoArchivos>l ENTONCES 13 Dec(NoArchivos,l); 14 ProduCarOptimopio Archivos); 15 FIN SI

NomArch= 'Indice' + No + '.TMP,

MIENTRAS NO(FIN DE ARCHIVO (ArchRgtos)) HACER

78


16 DE OTRO MODO 17 PutTablaDenvada(l3uffer Cols); 18 FIN MIENTRAS 19 FIN PROCEDIMIENTO

En los siguientes párrafos se explican algunos aspectos importantes de este pseudocódigo.

En la línea 14 se indica que este pseudocódigo se ejecuta de manera recursiva. La razón de ello se debe a la forma, que debe tomar un renglón de la tabla derivada. Considerando que es el producto cartesiano, entonces este renglón contendrá la concatenación de la($ columna(s) del renglón del primer archivo más el valor de la(s) columna(s) para el segundo archivo, y así sucesivamente hasta obtener el (los) valor(es) de la(@ columna(s) para el renglón del último archivo. Este procedimiento se repetirá tantas veces como valores de posiciones de renglones existan para el primer archivo (ver Figura 4.11).

En la línea 11, el procedimiento ObtenValCols se encarga de obtener del renglón, el valor de la columna solicitada en la cláusula SELECT, el cual se almacena en la variable BufferCols.

La variable NoArchivos indica cuántos archivos se crearon para almacenar las posiciones de los renglones, y se utiliza como condición de salida en la recursividad. Su valor se modifica (línea 13) cada vez que se ha abierto un archivo. Cuando toma un valor de 1, significa que ya no existen más archivos por abrir. Entonces el contenido de la variable BufferCols tendrá los valores de todas las columnas solicitadas en la cláusula SELECT, y podrá ser guardado en el archivo creado para la tabla derivada (línea 17).

4.9. Proceso General de Optimización

Esta sección presenta de manera general el proceso que se realiza para seleccionu la estrategia de ejecución de la consulta. Para ello se utilizará el siguiente ejemplo:

Ejemplo O: SELECT S.SNo, P.PNo, SP.Cant FROM S, P, SP WHERE SP.CIUDAD=P.Ciudad

AND SP.PNo='SS' OR SP.SNo=S.SNo

1. Descomponer la consulta en varias subconsultas, con respecto al operador lógico OR. Para la consulta C1 se generan las subconsultas S1 y S2.

S1: SP.Ciudad=P.Ciudad AND SP.PNo='SS' S2: SP.SNo=S.SNo

19

CAPITULO 4 PLANTEAMENTO Y SOLUClON DEL PROBLEMA

En un árbol de consulta esta situación queda representada en la Figura 4.12.

Arbol A

A I

Proyectar [ S.SNo, P.PNo, SP.Cant ]

I Union

Restringir [ P.PNo = 'SS AND SPCiudad = P.ciudad ] Juntar [ SPSNo = S.SNo ]

I / \ Juntar [ SP.Ciudad = P.ciudad ] SP S

/ \ SP P

Figura 4.12. Arbol de Consulta para el Ejemplo O

2. Para subconsultas en las que se presente la operación "Join", si existen:

2.1 Condiciones de la forma Atributo-Operador Relacional-Valor (Ver subconsulta S1) entonces, analizar si el atributo pertenece a un índice; si pertenece se busca el valor contra el cual se compara el atributo kbre el indice. Si no pertenece entonces se realiza un búsqueda secuencia1 de este valor sobre la tabla. Este tipo de condiciones hacen posible que no se requiera realizar el producto cartesiano entre las tablas completas.

2.2 Sólo condiciones con operaciones "JOIN" (ver SZ), veriticar si algunos de los atributos pertenece a un índice. Si no existe un indice se hace necesario la creación de un índice temporal. Se analizan este tipo de condiciones con el objetivo de evitar realizar el producto cartesiano entre las tablas completas. El tener un índice hace posible que la búsqueda de una columna de una de las tablas en el "JOIN se realice sobre éste y no sobre la tabla.

Estos problemas se analizan en el algortimo CondsgaraJoin de Sección 4.3.5.5.2. De manera implicita este algoritmo permite analizar las diferentes estrategias que existen para poder ejecutar la consulta.

En la Figura 4.13. se representan las las situaciones anteriores.

80

..


Arbol B Arbol C Juntar [ SP.Ciudad = P.ciudad ] Juntar [ SP.SNo= SSNo ]

/ \ Restringir [ P.PNo=’S5’ 1 SP Proyectar [ SPSNo ] S

P SP

Figura 4.13. Arb1 de consulta para las Subconsultas Obtenidas

En estos árboles podemos notar que el orden de ejecución de S1 y S2 se modificó con respecto a la forma que en que realizaban en el árbol de consulta A. Por ejemplo en éti A l del arbol A que representa a la subconsulta S1, se ejecutaba primero el producto cartesiano entre las tabla SP y 6’compietas y después sobre este resultado se realizaba la proy&ón P.PNo=’SS. En el árbol B esto se realiza de manera inversa; es decir, lo primero en r a i za r es la proyección P.PNo=’SS y después el producto cartesiano. En forma abstracta esto se realiza en el algoritmo EvaiuaSubcltas de la Sección 4!35:5:2. Se puede concluir que lo que se busca es realizar lo antes posible las selecciones. 4 , g y P” 76

Para obtener el resultado final de la consulta, se realiza la operación Unión con los resultados obtenidos de cada subconsulta (ver algoritmo ProdCarQtimo). El árbol de

-.

7 3.

consulta final para la consulta es el de la Figura 4.14. h j ’7g

81

... - -

CAPITULO 4

Arbol C

PL4NTEAhUENTO Y SOLUCION DEL PROBLEMA

Resultado Final

I Unión I

Proyectar [ SP.Cant. P.PNo] Proyectar [ SSNo, SP.Cant ]

Juntar [ P.ciudad = SP.Ciudad] Juntar [ SP.SNo= SSNo ]

Restringir [ P.PNo=’SS 1 SP Proyectar [ SPSNo ] S

P SP

Figura 4.14. Arbol Finai Para la Consulta

En el de la Figura 4.14. se puede observar que del resultado obtenido de la ejecución de cada subconsulta, se realiza la proyección de los atributos que se solicitan en la cláusula SELECT y fuialmente se realiza la Union entre estos resultados. Esto significa que el resultado final, sólo estará formado por los valores de los atributos especificados en el SELECT. I

82

CAPITULO 5

PRUEBAS AL OPTIMIZADOR

En este capítulo se predentan las pruebas realizadas al optimizador de estrategias de acceso con el propósito de verificar que los alcances planteados para el desarrollo de este trabajo de tesis se cumplieron.

83

CAPITULO 5

5.1. Objetivos de las Pruebas

Los objetivos de las pruebas realizadas son los siguientes:

PRmBAS

1. Comprobar la eficiencia del optimizador desarrollado contra un ,.VIBD comercial para seleccionar el mejor indice, cuando existan varios índices que puedan resolver la subconsulta.

2. Verificar la eficiencia del optimizador paia seleccionar el mejor índice, en el caso de que existan varios índices que puedan agilizar la recuperación de los renglones para una subconsulta. I1

Verificar que el tiempo de respuesta a una consulta disminuyó con respecto a la versión anterior del SMBDD.

3.

4. Verificar que el tamaño de la tabla que se obtiene cuando se especifican más de dos tablas en una cláusula FROM se redujo con respecto a la versión anterior del SMBDD.

Para lograr el objetivo del punto el SMBD que se eligió fue INFORMM Standard Engine para DOS con el cual se realizó la siguiente prueba:

Para esta prueba se utilizó la tabla Alumnos cuyo esquema es el siguiente:

Alumnos (Nombre, Especialidad, Nocontrol)

L a cardinalidad de la tabla Alumnos es de 10,OOO renglones y su contenido es el que se muestra en la Figura 5.1.

I/

Figura 5.1. Tabla Alumnos

84

PRUEBAS CAPiTUUJ 5

Se realizó la consulta del ejemplo A sobre la tabla Alumnos, para la cual se defineron los índices de la Figura 5.2, mediante los cuales se pcdía accesar más eficientemente los renglones de la tabla que satisfacen la condición de la cláusula WHERE. Cada vez que se defina un índice y se ejecutaba la consulta se registraba el tiempo empleado para dar respuesta a la consulta.

indice

NoControl NombEsp

NombEcp

ii

1 'ilempo de Kespuesta

8 mins. 38 segs. O mins. 5 segs.

'ilempo de respuesta por iteración

O mins. 51.8 segs. O m i n s O segs. 0.5 dec. segs.

NoControi

NoControi

. . 1 O000

Figura 5.2. Indices DeMdos a la Tabla Alumnos

Ejemplo A: SELECT * FROM Alumnos WHERE NoControl > 499

AND Nombre= '500aa' I) AND Especiaüdad='SOObb'

Los índices se defieron de tal forma que el último índice defindo era mejor que el anterior para recuperar los renglones de la tabla. Para verificar con mayor precisión si el tiempo disminuia entre el uso de un índice y otro, la consulta se repitió 10 veces seguidas. Los resultados obtenidos fueron los siguientes:

85

!! CAPITULO 5 I

indice

Nocontrol NombEsp

PRUEBAS

'I'iempo de Kespuesta

8 mins. 38 segs. 8 mins. 38 segs.

'I'iempo de respuesta por

O mins. 51.8 segs. O mins. 51.8 segs.

iteración 11

De acuerdo a los resultados obtenidos se pudo comprobar que INFORMIX, sí considera el mejor índice para resolver una consulta, siempre y cuando se cumpla la siguiente condición: las columnas de las condiciones que pertenecen a un índice deben presentarse exactamente en el mismo orden y consecutivamente a como fueron declaradas en el índice.

De acuerdo con la aseveración anterior para poder hacer uso del índice NombEsp, la primera columna que tiene que presentarse en la condición de la cláusula WHERE es la columna Nombre y después la columna Especialidad. Como puede verse en la tabla anterior, las columnas del índice en la condición están exactamente en el mismo orden que en el índice.

Para confirmar la aseveración anterior respecto al orden en que se deben presentar las columnas para que INFORMIX seleccione el mejor índice, se realizó la siguiente prueba: se cambió el orden de las condiciones de la cláusula WHERE para el ejemplo A, como se muestra en el siguiente ejemplo:

Ejemplo B: I!

Especialidad='bb500' AND NoControl>499 AND Nombre='aa500'

Para esta prueba se obtubieron los siguientes resultados:

Como puede verse en la tabla, el tiempo de respuesta no se modificó cuando el índice NombEsp ya existía. Esto se debió a que el orden de las columnas Especialidad y Nombre, no era igual al orden en que se presentan en el índice NombEsp (Nombre, Especialidad).

En el optimizador desarrollado en este trabajo de tesis, el orden en que aparecen las columnas del índice en la condición de la cláusula WHERE es irrelevante; por lo tanto para resolver la consulta del Ejemplo A, el índice que se utilim'a sería NombEsp aunque las columnas de éste estén como en el Ejemplo A o como en el Ejemplo B.

Para lograr el objetivo del punto 2 se defineron varios índices a una tabla, donde cada vez que se defm'a un índice se registraba el tiempo que se tardaba para dar respuesta a una consulta. Los índices se declarar& de tal forma que el último índice era mejor que el anterior para agilizar la recuperación de los renglones.

86

CAPITULO 5

5.2. Condiciones de las h e 1

Las pruebas se realizar< de datos:

PRUEBAS

5.3. Presentación de las h e

A continuación se PI instrucciones de SQL intercala

IS

I en una computador AT 80386, donde se creó la siguiente base

S (SNo, SName, Ciudad) P @“o, PName, Ciudad)

SP (SNo, PNO, Qty)

as

ienta los listados de los programas fuente en Pascal con w, junto con los resultados impresos cuando sea necesario.

87

SNo CHAR(8) SName CHAR(20) Ciudad CHAR(20)

$ CREATE TABLE P( PNo CHAR(7) PName CHAR(20) Peso INTEGER

END.

NOT NULL, NOT NULL, NOT NULL) ;

NOT NULL, NOT NULL, NOT NULL,

88

I CAPIl lLO 5 PRUEBAS

(------------------------------------------------------------- Prueba No. 2 Para el precompilador de SQL

Objetivo : Crear los indices sobre los que se efectuaran las pruebas.

Fecha : 7 de Abril de 1995.

I1

- - - - - - - - - - - - - - - - - - - - - L - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

USES SQL; BEGIN

$CREATE INDEX SNoName ON S ( CNo, CName) ;

I/

$CREATE INDEX SNamCd” ON S ( SName, Ciudad) ;

$CREATE INDEX CNo ON S(SNo) ;

END. I

89

CAPITIJLO 5 PRUEBAS

------------------------------------------------------------- Prueba No. 3 Para el Optimizador

Objetivo : Inserción de los valores de los renglones de la tabla S e inserción de los valores de llave para los Indices SNoName,SNomCity y SNo.

Fecha : 7 de Abrilt1995. .............................................................

$m 60000,0,600000

I USES SQL,CRT;

TYPE STRB:STRING[B];

VAR cont,longitud,m,k,j:INTEGER; CadNum :STRB; !I

.II

StrCd : STRB ; END DECLARE SECTION;^

$ BEGIN DECLARE SECTION StrNum : STRB ; StrNom : STR8 ;:

PROCEDURE ValAsignar (StrNum:STR8;VAR Va1or:STRB); Var 1 m,iongitud:INTEGER;

BEGIN longitud:=length(StrNum) ;

FOR m:=longitud Tcj 4 DO StrNum:='O'+StrNum;

IF longitud<5 THEN ,

Vaior:=Vaior+StrNum;' END;

BEGIN Clrscr;cont:=O; II FOR j:=i TO 100 DO

FOR k:=l TO 100 DO BEGIN

INC (cont, 1) ;iSTR (cont , CadNum) ; StrNum:=rS';8ValAsignar(CadNum,StrNum); StrNom:=pbbs;ValAsignar(CadNum,StrNom); StrCd:='cc';ValAsignar(CadNum,StrCd); WRITELN (StrNum:lO,StrNom:lO,StrCd);

VALUES(:StrNum,:StrNom,:StrCd); $ INSERT INTO S

END; END.

90

I PRUEBAS CAPlTVLO 5 I

(----------------------------------------------------------

Prueba No. 4 Para el Optimizador

Objetivo : Demostrar que el optimizador elige el mejor I/ ;I

índice cuando existen varios indices para resolver unaconsulta, en donde las columnas se comparan con operadores relaciones de igualdad y desigualdad.

! Condiciones de la prueba: Se definieron varios índices para

la tabla S .

Fecha : 7 de Abril 111995. .............................................................

$m 60000,0,600000 USES SQL,CRT;

TYPE ¡ I

STR8:STRING[8];

iJ VAR cont,longitud,m,k,j:INTEGER; CadNum :STR8;

$ BEGIN DECLARE SECTION StrNum : STR8 ;¡ StrNom : STR8 ;¡ StrCd : STR8 ;

END DECLARE SECTION;

li BEGIN $ SELECT * FROM S INTO WHERE SNo>'S777' AND AND SName='S9999'AND Ciudad='cc9999';

: StrNum, : &Nom, : StrCd

WRITELN('Resu1tado ide la prueba No. 4 ' ) ; WRITELN(LST,Resultado de la prueba No. 4');

IF SQLCODE=O THEN \ BEGIN ir WRITELN(StrNurn:4,StrNom:lO,StrCd:8); W R I T E L N ( L S T , N U ~ : ~ , S ~ ~ N O ~ : ~ O , S ~ ~ C ~ : ~ ) ;

END ;

END.

91

CAPITULO 5 I

Resultado de la prueba No. 4

Indice para resolver la Subconsulta 1: SNamCd.IDX

S9999 bb9999 cc9999 1)

PRüEBAS

!I

92

Prueba No. 5 Para el

Objetivo : Comprobar operadores cada opera proceso de

Fecha : 7 de Abril ..................... $m 60000,0,600000 USES SQL,CRT;

TYPE STR8:STRING[8];

VAR cont,longitud,m,k,j:l CadNum :STR8;

$ BEGIN DECLARE SECTIC

StrNom : STR8 ; StrNum : STR8 ;

StrCd : STR8 ; END DECLARE SECTION;

$ DECLARE CURSOR Tes BEGIN

$ SELECT * FROM S WHERE SNo='S777'

$OPEN TestCur; WRITELN('Resu1tado c WRITELN (LST, Resultac

REPEAT $FETCH TestCur IN1 :StrNum,:StrNom,: IF SQLCODE=O THEh

WRITELN ( StrNL BEGIN

WRITELN (LST, h END ;

UNTIL SQLCODEoO; $CLOSE TestCur;

END.

)pt imi zador

rue una expresión compuestas por OR debe tener asociado un indice para ido,para que sea posible aplicar el optimización.

1995. ____________________--------------------

(TEGER;

v

tCur FOR

3 la prueba No. 5') ; 3 de la prueba No. 5') ;

1 ;trCd;

n:4,StrNom:lO,StrCd:8); im: 4, StrNom: 10, StrCd: 8) ;

93

CAPITULO 5 I

Resultado de la Prueba No. 5

Indice para resolver la Subconsulta 1: Sno.IDX

Indice para resolver la Subconsulta 2: SNamCd.IDX

SJ77 bbJJJ ccJJ71 588887 bb8887 CC888iJ

I

PRUEBAS

94

I PRUEBAS CAPITULO 5

~---------------------------'-----------------------------------

Prueba No. 6 Para el optimizador

Objetivo : I1

Demostralr que el optimizador elige el mejor indicepara resolver una consulta. Para elegir el indice se basa en elegir aquel cuyo mayor número de columnas se presenten en la condicion y que SI. comparan sobre un operador relaciona1 de igualdad.

Fecha : 7 de Abril 1995. 1 .............................................................

$m 6 0 0 0 0 , 0 , 6 0 0 0 0 0 I USES SQL,CRT;


VAR cont,longitud,m,k,j:INTEGER; CadNum :STR8;

II $ BEGIN DECLARE SECTION

StrNum : STR8 ;

StrCd END DECLARE SECTION;

StrNom : STR8 ;

:STR8;l BEGIN

$ SELECT * FROM S INTO :StrNum,:StrNom,:StrCd WHERE SNo='S7777' AND SName=1bb7777'AND Ciudad='cc7777';

U

WRITELN('Resu1tado de la prueba No. 6'); WRITELN(LST,Resultado de la prueba No. 6');

IF SQLCODE=O THEN BEGIN WRITELN(StrN~m:4~,StrNom:10,StrCd:8); WRITELN(LST,Num:14,StrNom:10,StrCd:8);

END ; 11

END.

95

CAPITULO 5

Resultado de la pruek

Indice para resolver

s7777 bb7777 cc

DRUEBAS

NO. 6

Subconsulta 1: SNamCd.IDX

77

96

I PRUEBAS CAPITULO 5

(------------------------------------------------------------- Prueba No. 7 Para el Optimizador

Objetivo : Usar un indice para recuper un rango de valores de llave.

I

Fecha :7 de Abril h.995. ---------------------L---------------------------------------- 1 !

! $m 60000,0,600000 USES SQL,CRT;

TYPE li STR8:STRING[8]; ,i

VAR cont,longitud,m,k,j:INTEGER; CadNum :STR8;

$ BEGIN DECLARE SECTION StrNum : STR8 ; StrNom : STR8 ; ,j StrCd : STR8 ; :,


$ DECLARE CURSOR TedtCur FOR BEGIN

I $ SELECT * , FROM S

WHERE SNO BETWEEN '5777' AND 'S800';

I/ SOPEN Testcur; WRITELN('Recu1tado de la prueba No. 7'); WRITELN(LST,Resultado de la prueba No. 7 ) ;

REPEAT $FETCH Testcur INTO :StrNum,:StrNom,:'StrCd; IF SQLCODE=O THEN BEGIN WRITELN(StrNum:4,StrNom:lO,StrCd:8); WRITELN(LST,NÚm:4,StrNom:lO,StrCd:8);

1 t END ;

UNTIL SQLCODEoO; $CLOSE Testcur; I

END. I

97

II 'I CAPITULO 5

Resul tado de l a prueba N o . 7

Indice para resolver l a Subconculta 1: SNo.IDX i

5777

5779 5778

5780 5781 5782 5783 5784

5786 5787 5788

5785

5789 5790 5791 5792 5793 5794 5797 5798 5797

5799 5798

saoo

bb7 7 7 bb7 7 8 bb7 7 9 bb780 bb781 bb782 bb783 bb784 bb7 8 5 bb7 8 6 bb7 8 7 bb7 8 8 bb7 8 9 bb790 bb791 bb7 9 2 bb793 bb7 9 4 bb7 9 5 bb7 9 6 bb7 9 7 bb798 bb799 bb800

1 c c n a

cc780 c c 7 a i I I ~ ~ 7 8 2 CC783 ~ ~ 7 8 4 1 cc7a51 CC786 ~ ~ 7 8 7 cc7aa

cc777

cc779

cc789 CC790 I c c 7 9 1 cc792 cc793

cc795 cc796 c c 7 9 7 ~ ~ 7 9 8

cca o o

1

F'RUEBAS

98

I PRUEBAS CAPITULO 5 I1

(------------------------------------------------------------- Prueba No. 8 Para el bptimizador

Objetivo : Demostrar que el tiempo de respuesta para Una consulta disminuyó al aplicar el proceso de optimización.

11 Condiciones de la Prueba: La consulta se ejecutó diez veces consecutivamente, primero se realizó en el SMBDD sin hacer uso de optimizador después haciendo uso de este.

1 Fecha : 7 de ............................................................ $m 60000,0,600000 USES SQL,CRT;

TYPE 1

STR8:STRING[8];

VAR cont,longitud,m,k,j:INTEGER; CadNum : STR8 ; hr,min,seg,cseg : WORD ;

$ BEGIN DECLARE SECTION StrNum : STR8 ; StrNom : STRS ; 1 StrCd : STRS ;


BEGIN WRITELN('Resu1tado de la prueba No. 8 ' ) ; WRITELN(LST,Resultado de la prueba No. 8'); GETTIME(hr,min,seg,cseg); WRITELN ( Hora : WRITELN; FOR j:=l to 10 DO

Min:',min,' S e g s : r , s e g , ' s e g : r , c s e g ) ;

'fhr'Íl BEGIN

I $ SELECT * FROM S

WHERE SNO='S77[7'; INTO : StrNum,l: StrNom, : StrCd

IF SQLCODE=O THEN WRITELN(StrNum:4,StrNom:lO,StrCd:8);

I1

I 99

END ; WRITELN; WRITELN('H0ra: l,hr,( Min:',min,' Segs:',seg,' Cseg:',cseg); END.

PRLIEBAS CAPITCLO 5

t------------------------------------------------------------- Prueba No. 9 Para el Optimizador

Objetivo : Verificar Lue se hace uso de un indice para resolver una consulta en la que se presenta la operación de reunión.

Fecha :7 de Abril 4995. 1 __-----_________________________________---------------------

$m 60000,0,600000

I USES SQL, CRT;


VAR II cont,longitud,m,k,j:INTEGER; CadNum :STR8;

$ BEGIN DECLARE SECTION StrNum, StrNuml : STR8; StrNom, StrNom2 1 : STR8; StrCd,StrCdl : STR8 ; StrColor : STR8 ; Peso.Situacion. Cant' 11 :INTEGER;

END DECLARE SECTION; ,

BEGIN $ DECLARE CURSOR TestCur FOR

$ SELECT S.SNO,SP.PNo,SP.Qty FROM S,SP WHERE S.SNo=SP.SNo;

11 $ OPEN TestCur; WRITELN('Recu1tado die la prueba No. 9,); WRITELN(LST,Resultado de la prueba No. 9);

REPEAT $FETCH TestCur INTO : StrNum, : StrNum1,l:Cant; IF SQLCODE=O THEN( BEGIN

WRITELNiStrNum:4.StrNuml:lO,Cant:lO~: WRITELNiLST, StrNum: 4 , StrNumí: 10, Canti 10) ;

END : II UNTIL SQLCODEOO; 11 $CLOSE TestCur; END.

100

'! I

CAPllZnO 5 I

Resultado de la prueba No. 9 11 Indice para resolver la Subconsulta 1: SNo.IDX

SlOO

SlOO

SlOO

SlOO

SlOO

SlOO

s200

s200

S300

S400

5400

P10

P2 o P30

P4 O

P50

P60

P10

P2 o P30

P2 o P50

300

200

400

800

600

500

300

200

400

200

600

PRUEBAS

101

I PRUEBAS CAPITULO J

t-------------------,-------'------------------------------------ Prueba No. 10 Para el 'Optimizador

Objetivo : Verificar l;a creación de un índice temporal para 11

resolver una consulta en la que se presenta la operación de reunión.

I I

Condiciones de la prueba: No existen índices para las tablas.

Fecha : 7 de Abril'1995. 1 .............................................................

$m 60000,0,600000 'I USES SQL,CRT; ir

TYPE i I

STR8:STRING[8];

VAR cont,iongitud,m,k,j:INTEGER; CadNum :STR8;

I/ $ BEGIN DECLARE SECTION

StrNum, StrNuml ': : STR8 ; StrCd,StrCdl : STR8 ; Cant :INTEGER; ' END DECLARE SECTION;

BEGIN $ DECLARE CURSOR TestCur FOR

$ SELECT S.SNO,SP.Qty FROM S,SP WHERE S.SNo=P.PNo; ¡I

$ OPEN TestCur; WRITELN('Resu1tado de la prueba No. 10'); WRITELN(LST,Resultad'o de la prueba No. 10') ;

1 REPEAT $FETCH TestCur INTO :StrNum,:Cant; IF SQLCODE=O THEN1 BEGIN i!

WRITELN(StrNum:4,Cant:lO); WRITELN(LST,StrNum:4,Cant:lO);

END ;

$CLOSE TestCur; UNTIL SQLCODEoO; I

END.

102

CAPiTüi.0 5

Resultado de la prueba 'No. 10

Creacion del indice temporal INDTMP1.TMP

Indice para resolver la Subconsulta 1: INDTMP1.TMP

II

SlOO 300

SlOO 200

SlOO 400

SlOO 800

SlOO 600

2.100 500

5 2 0 0 300

5200 200

S300 400

S400 200

S400 600

PRUEBAS

103

WRITELN (LST, N END ;

UNTIL SQLCODEoO; $CLOSE TestCur;

FRUEBAS

ue el tamaño de la tabla derivada se

ba: La consulta se realizó primero en onsiderar el optimizador, después e este.Alterminar ambas pruebas se ntidad de memoria secundaria almacenar la tabla derivada.

1995. I ____________________-------------------

TEGER;

: STR8 ; : STR8 ;

Cur FOR o, S. SName

0;

la prueba No. 11') ; de la prueba No. 11') ;

StrNom: BEGIN :4,StrNum2:lO,StrNom:J);

104

CAPITULO 5

Prueba No. 12 Para el

PRUEBAS

------------------------------------------------------------- Optimizador

105

$m 60000,0,600000 USES SQL,CRT;


VAR cont,longitud,m,k,j:INTEGER; CadNum

.............................................................

: STR8 ;

$ SELECT P.PName FROM P WHERE PeSO<=l7 AND (SELECT PNo FROM SP WHERE SP.Qty<=400 (SELECT SNO FROM S WHERE SName='bb200'

$ OPEN TestCur;

WRITELN('Resultad0 de WRITELN(LST,Resultado

REPEAT $FETCH TestCur INTO : StrNom; IF SQLCODE=O THEN BEGIN WRITELN (StrNomf WRITELN(LST,StrNom:4);

END ; UNTIL SQLCODEoO;

$CLOSE TestCur; END.

PNo IN;

AND SNo IN

AND Ciudad='cc200'));

la prueba NO. 12'); de la prueba No. 12');

4) ;

CAPITVLO 5

Resultado de la prueba

Indice para resolver 1

PPlOO PP200

PRUEBAS

o. 12

Subconsulta 1: SNo.IDX

106

CAPITULO 6

~ ~~

COMENTARIOS FINAL

107

1 , CAPITULO 6 COMENTARIOS BEVALES

6.1. Comentarios Finales

El desarrollo de este trabajo permitió descubrir la manera en que posiblemente vanos de los SMBDs comerciales implementan el optimizador de consultas, logrando con esto adquirir el conocimiento y1 experiencia que puede ser compartida con el sector educativo y aplicada para el desarrollo de sistemas de información distribudos que no cuenten con un optimizador.

Conviene destacar que este trabajo de tesis es sólo uno más de una larga serie que tiene por objeto estudiar problerbas y desarrollar tecnología relacionados con manejadores de bases de datos distribuidd.

El SMBDD que se desarro!a en el IIE cuenta actualmente con un manejador de archivos y un precompilador para instrucciones del LMD y LDD de SQL. El manejador de archivos cuenta con funciones básicas que permiten tener acceso transparente a los archivos de una base de datos distribuida.

Recientemente se han desarrollado los siguientes trabajos para el SMBD del IIE 1) un manejador de transaccionds para mantener la integridad de la base de datos y controlar la concurrencia 2) un módulo que permite la transparencia de fragmentación 3) un servidor para bases de datos distribuidas con filosofía cliente-servidor.

62. Posibles Extensiones I - Procesamiento distribuido de consultas. Este consiste en identificar en cuál (es)

condición (es) de la cláusula WHERE se hace referencia a una tabla que físicamente reside en otra computadodi con el propósito de que esta condición sea enviada a aquella computadora para ser procesada; de tal forma que sólo se envie a la computadora en la que se realizó originalmente la consulta una tabla que contenga sólo aquellos renglones que satisfagan la condición. Con este se reduciría el tráfico de datos sobre la red.

Administrador de memoria principal. Este consiste en determinar de manera inteligente cuáles de las páginas que Se encuentran en memoria pueden ser utilizadas en consultas posteriores a una consulta realizada, de tal forma que se mantengan disponibles en la memoria. Con esto se evitaría que al resolver las consultas posteriores no sea necesario accesar a disco para bus& las páginas en donde se localizan los datos deseados, por consiguiente se realizarín +enos accesos a disco y el tiempo de respuesta disminuiría.

-

109

Date, C.J. "IntrcdwciOn a Wesley Iberoamericana,

Ah0 V. Sethi R., [r] Addison-Wesley Publishin

u 1

r21

r31

[41

PI

i61

[71

BIBLIOGRAFi A

10s Sistemas de Bases de Datos", Delaware, EUA: Addison- c1993, Vol I, 5a. Ed., 112 pp.

Ullman Jeffrey, "Compilers Principles, Techniques and Tool", Company, 1988, 796 pp.

r131

Horowitz, Ellis [y] Sahni 1990, 3a. Ed. 717 pp.

I 110

Sarts, "Data Structures in Pascal", Computers Science Press,

Koroth, Henry F. [r] A. McGraw-Hill, c1993,2a.

Silberschatz, "Fundamentos de Bases de Datos", Espaíia: Ed., 739 pp.

II I

[14] Pazos Range1 Rodolfo A. [y] J. Pérez O. "Arquitectura del Diccionario de Datos de un Manejador de Bases de Datos Distribuidas", [Cuemava,Mor] Memoria Técnica del II Congreso Nacional de InvehgaciÓn en Ciencias Comuutacionales.

Pérez Ortega Joaquín [y] Rodolfo Pazos R. "Manejador de Archivos Distribuidos con Acceso Concurrente en y a Red Local de PCs", Memoria de la XCII Reunión Internacional MEXICON del E E E México, Tomo I, México. D.F., 17-21 de Sept. de

[15]

1989,4pp. I

3a. Ed. 560 pp. 1

I

[16] Tanenbaum M. [y] Augensten J., "Estructura de Datos en Pascal", Rentice-Hall, 1981.

[17] Krasowky M. "Why Chook DistribuitedDatabase?", Database Programming & Design, Vol. 4, NO. 3, pp. 46-53, MU. 1991.

I1

CENTRODE~NFORMACION

C E N i C E T

· agradecimientos agradezco a mis queridas hermanas jacqueline y juanita todo cuanto hicieron y...

Documents