Tesis de Maestría - Departamento de Computación · Director de Tesis: Dr. Arturo D´ıaz P´erez M´exico, DF Diciembre del 2004. Resumen En anos˜ recientes. se ha producido un

Centro de Investigacion y de Estudios

Avanzados del IPN

Departamento de Ingenierıa ElectricaSeccion Computacion

Procesamiento de consultasen bases de datos paralelas

Tesis que presenta

Jose Guadalupe Ruiz Carrete

Para obtener el grado de:

Maestro en Cienciasen la Especialidad de

Ingenierıa Electrica Opcion Computacion

Director de Tesis:Dr. Arturo Dıaz Perez

Mexico, DF Diciembre del 2004.

Resumen

En anos recientes. se ha producido un incremento continuo en lacantidad de datos manipulados por los sistemas manejadores de basesde datos (DBMS). Mas aun, ya no resulta extrano para un DBMSmanipular bases de datos con tamanos que van desde los cientos degigabytes hasta terabytes. Por otra parte, los sistemas con multiplesprocesadores son cada vez mas accesibles, por lo que es posible aplicarcomputo paralelo para procesar grandes volumenes de informacion enlas bases de datos.

El procesamiento de juntas (joins) en bases de datos, es una op-eracion que demanda muchos recursos de computo, sobre todo en basesde datos grandes. Para resolver este problema se hace necesario combi-nar tecnicas de bases de datos -especialmente bases de datos distribuidas-y procesamiento paralelo para reducir los tiempos de respuesta a losusuarios de una base de datos grande[1]. En el presente trabajo, semuestran algoritmos para realizar cada una de las etapas involucradasen la implementacion de una base de datos en paralelo. Los algoritmosson desarrollados en C haciendo uso de la interfaz de paso de mensajes(MPI).

iii

Abstract

In recent years there has been a continuous increase in the quantityof data manipulated by database management systems (DBMS). Evenmore, no it is not uncommon for a DBMS to handle a database thatranges from hundreds of gigabytes to terabytes. Also, systems withmultiple processors are becoming more and more accessible, which iswhy it is possible to apply parallel computing to process great volumesof information in a database.

The processing of joins in databases is an operation that demandsa lot of computer resources, especially in databases of great size. Tosolve this problem it is necessary to combine techniques of databases-especially distributed databases- and parallel processing to reduce an-swer time for users of big databases[1]. In this framework, algorithmsare shown to realize each of the stages necessary to implement a par-allel database. The algorithms are developed in C making use of themessage passing interface (MPI).

v

Dedicatoria

“A ti Mama por todo cuanto significaste y significas, portu inmenso amor y abnegacion.”

“En el otro extremo, a ti Azul por lo que significas y sig-nificaras, con toda la alegrıa que emana de tu pequeno ser ycontagia.”

vii

Agradecimientos

Gracias Mama y Papa por todos sus sacrificios y preocupaciones quepasaron en aras de lograr que sus hijos seamos hombres de bien. Lo lo-graron.

Por todo tu amor, cuidados y consideraciones para conmigo. GraciasMartha mi amada esposa.

A toda mi familia por su apoyo constante e incondicional en cadamomento de mi vida. Gracias los quiero mucho.

A todos los profesores de la seccion de computacion por compar-tir sus conocimientos y otorgarnos tiempo valioso de su vida. Gracias,aprovechare al maximo cuanto ustedes me brindaron.

Por las consideraciones especiales hacia mi. Gracias Dr. Arturo Dıaz,es grato saber que dentro de la frialdad de la tecnologıa, existen per-sonas como usted.

Al personal de la seccion de computacion, especialmente a Sofi portodo su apoyo y palabras de aliento. Gracias, ya no les dare mas lata.O, ¿Quizas si?.

Por supuesto no pueden faltar los amigos y los amigotes, que siempreestan ahı para animarte y desanimarte y con todo esto lograr crecercomo persona cada dıa mas.

Mis companeros del CINVESTAV: Zorra, Cepillın, JuanK, Chirris,

ix

x

Goyo, Kike, York, Jimmy, Colombiano, Rodrigo.

Mis companeros de Trabajo: Gerry, Tigre, Quinones, Askel, Richter,Lau, Checo.

El bandon: Negrito, Vaquita, Calitos, Pingui, Richard.

Los del barrio: Cabezın, Marro, Enano.

“A la vida que me ha dado tanto a cambio de tan poco.”“A la Mano que hizo la Gran Obra.” [2]

Indice general

Resumen III

Abstract V

1. Introduccion 1

2. Bases de Datos Paralelas 92.1. Sistemas de Bases de Datos en Paralelo . . . . . . . . . . 11

2.1.1. Aspectos Importantes de los SBDP . . . . . . . . 122.2. Arquitectura de un SBDP . . . . . . . . . . . . . . . . . 132.3. Fragmentacion . . . . . . . . . . . . . . . . . . . . . . . 15

2.3.1. Alternativas de Fragmentacion . . . . . . . . . . . 162.3.2. Fragmentacion Horizontal . . . . . . . . . . . . . 172.3.3. Fragmentacion Vertical . . . . . . . . . . . . . . . 182.3.4. Ubicacion de los Datos . . . . . . . . . . . . . . . 19

2.4. Procesamiento de Consultas . . . . . . . . . . . . . . . . 212.4.1. Arquitectura del Procesamiento de Consultas . . 232.4.2. Optimizacion de Consultas . . . . . . . . . . . . . 252.4.3. Procesamiento de Datos en Paralelo . . . . . . . . 28

2.5. Trabajos Relacionados . . . . . . . . . . . . . . . . . . . 302.5.1. Efecto de la Distorsion y el Balance de Carga en

Mine-rıa de Datos en Paralelo. . . . . . . . . . . . . . . 30

2.5.2. Balance de Carga de Filtros de Informacion Pa-ralelizados. . . . . . . . . . . . . . . . . . . . . . 32

2.5.3. Algoritmos Optimos para el Problema de laConsulta Multiple en Mallas Reconfigurables,con Aplicaciones. . . . . . . . . . . . . . . . . . . 33

2.5.4. Analisis de Desempeno de Algoritmos Paralelospara la Consulta en Sistemas de Bases de DatosOrientadas a Objetos. . . . . . . . . . . . . . . . 34

2.5.5. Algoritmos para Range-Join Basados en Permutacio-nes sobre Mallas N Dimensionales. . . . . . . . . 35

xi

xii

3. Fragmentacion 373.1. Caso de Estudio . . . . . . . . . . . . . . . . . . . . . . . 413.2. Algoritmos de Fragmentacion . . . . . . . . . . . . . . . 47

3.2.1. Proceso Maestro . . . . . . . . . . . . . . . . . . 483.2.2. Procesos Esclavo . . . . . . . . . . . . . . . . . . 483.2.3. Resultados . . . . . . . . . . . . . . . . . . . . . . 50

3.3. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . 52

4. Procesamiento de Consultas 554.1. Paralelismo Intra-Operador . . . . . . . . . . . . . . . . 554.2. Paralelismo Inter-Operador . . . . . . . . . . . . . . . . . 564.3. Implementacion del Procesador de Consultas . . . . . . . 564.4. Sintaxis para el Lenguaje de Consultas . . . . . . . . . . 594.5. Construccion de la Instruccion SQL . . . . . . . . . . . . 634.6. Definicion de la Estrategia de Ejecucion . . . . . . . . . 644.7. Ejecucion de Estrategias . . . . . . . . . . . . . . . . . . 65

4.7.1. Estrategia Simple . . . . . . . . . . . . . . . . . . 664.7.2. Estrategia Simple con Lımite . . . . . . . . . . . 684.7.3. Estrategia Simple Ordenada . . . . . . . . . . . . 704.7.4. Estrategia Simple Ordenada con Lımite . . . . . . 704.7.5. Estrategia Agrupamiento Simple . . . . . . . . . 714.7.6. Estrategia Agrupamiento con Lımite . . . . . . . 724.7.7. Estrategia Agrupamiento Ordenado . . . . . . . . 724.7.8. Estrategia Agrupamiento Ordenado con Lımite . 734.7.9. Resultados . . . . . . . . . . . . . . . . . . . . . . 76

4.8. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . 78

Conclusiones 814.9. Extensiones y trabajos futuros . . . . . . . . . . . . . . . 83

A. Consultas Tıpicas a la Base de Datos 85

Bibliografıa 90

Indice de figuras

1.1. Implementacion de una base de datos paralela. . . . . . . 5

2.1. Tecnologıas en que se apoyan las bases de datos paralelas. 92.2. Esquema de bases de datos paralelas. . . . . . . . . . . . 112.3. Factores importantes en un SBDP . . . . . . . . . . . . . 132.4. Arquitectura ANSI SPARC . . . . . . . . . . . . . . . . 142.5. Arquitectura de un SBDP . . . . . . . . . . . . . . . . . 152.6. Fragmentacion horizontal. . . . . . . . . . . . . . . . . . 172.7. Expresion de inter-relaciones utilizando enlaces . . . . . 172.8. Fragmentacion vertical. . . . . . . . . . . . . . . . . . . . 192.9. Esquemas de particionado de bases de datos. . . . . . . . 212.10. Arbol de operadores en un esquema paralelo. . . . . . . . 222.11. Conversion del calculo relacional al algebra relacional. . . 252.12. Complejidad de las operaciones del algebra relacional. . . 272.13. Proceso de optimizacion de consultas. . . . . . . . . . . . 292.14. Estrategias para el procesamiento de los datos en paralelo. 30

3.1. Esquema general del trabajo . . . . . . . . . . . . . . . . 383.2. Algoritmo COM MIN para obtener un conjunto de pre-

dicados completo y mınimo. . . . . . . . . . . . . . . . . 403.3. Algoritmo para fragmentacion horizontal . . . . . . . . . 413.4. Esquema de la base de datos del caso de estudio. . . . . 423.5. Muestra del archivo original para las relaciones departa-

mento, extensiones y conmutador. . . . . . . . . . . . . . 463.6. Muestra del archivo original para la relacion telmex. . . . 463.7. Esquema de los fragmentos de la base de datos paralela. 473.8. Fragmentacion con: mpirun -np 5 Fragmentar BD2002. . 483.9. Algoritmo maestro para fragmentacion. . . . . . . . . . . 493.10. Algoritmo esclavo para fragmentacion. . . . . . . . . . . 503.11. Distribucion de datos obtenida por el algoritmo de frag-

mentacion. . . . . . . . . . . . . . . . . . . . . . . . . . . 513.12. Rendimiento del algoritmo de fragmentacion. . . . . . . . 52

4.1. Paralelismo intra-operador. . . . . . . . . . . . . . . . . . 56

xiii

xiv

4.2. Paralelismo inter-operador. . . . . . . . . . . . . . . . . . 574.3. Esquema del procesador de consultas. . . . . . . . . . . . 594.4. Sintaxis general para el lenguaje de consultas. . . . . . . 604.5. Sintaxis para la restriccion. . . . . . . . . . . . . . . . . . 604.6. Sintaxis para la proyeccion. . . . . . . . . . . . . . . . . 614.7. Generacion de la instruccion SQL. . . . . . . . . . . . . . 644.8. Proceso para estrategia simple. . . . . . . . . . . . . . . 674.9. Proceso para estrategia simple con lımite. . . . . . . . . . 694.10. Proceso para estrategia simple ordenada. . . . . . . . . . 704.11. Proceso para estrategia simple ordenada con lımite. . . . 714.12. Proceso para estrategia agrupamiento simple. . . . . . . . 714.13. Compaginacion de resultados de la funcion count. . . . . 724.14. Proceso para estrategia agrupamiento con lımite. . . . . . 734.15. Proceso para estrategia agrupamiento ordenado. . . . . . 734.16. Problema de compaginacion de resultados. . . . . . . . . 744.17. Estrategia agrupamiento con ordenamiento y lımite. . . . 764.18. Rendimiento de cada una de las estrategias. . . . . . . . 774.19. Tiempos de ejecucion de las estrategias con diferente

cantidad de procesadores. . . . . . . . . . . . . . . . . . 80

Indice de cuadros

3.1. Consultas tıpicas que se realizan a la base de datos. . . . 443.2. Analisis de frecuencia de los predicados en las consultas. 443.3. Miniterminos encontrados. . . . . . . . . . . . . . . . . . 45

4.1. Ejemplos de uso del lenguaje de consultas. . . . . . . . . 624.2. Sintaxis aplicada a los ejemplos de la tabla 4.1. . . . . . 63

xv

Capıtulo 1

Introduccion

Antecedentes

Tradicionalmente, las bases de datos se han considerado como unsistema centralizado para archivar informacion de manera electronica(generalmente en una sola computadora)[3]. Sin embargo, con la apari-cion de las redes de computadoras, esta concepcion ha evolucionado detal forma que en la actualidad han surgido dos nuevas clases de sis-temas de bases de datos: Bases de datos distribuidas y bases de datosparalelas.

Una Base de datos distribuida se puede definir como una colec-cion de multiples bases de datos logicamente interrelacionadasy distribuidas en una red de computadoras. Mientras que unabase de datos paralela (BDP) es una extension de la tecnologıade base de datos distribuidas aplicada a computadoras parale-las[4]. Ambas clases de bases de datos, comparten caracterısticas, peroinvolucran tambien, diferencias sustanciales. El proposito fundamentalde las BDP es, reducir los tiempos de respuesta al usuario que realizaconsultas a la base de datos.

Un sistema de bases de datos paralelas se puede definir librementecomo un sistema manejador de bases de datos (DBMS) im-plementado en sistemas con multiprocesadores fuertementeacoplados. Esta definicion incluye muchas alternativas que van de lamigracion directa de un DBMS existente, lo cual puede requerir lare-escritura de las rutinas de la interfase con el sistema operativo; a

1

2 INTRODUCCION

combinaciones sofisticadas de procesamiento en paralelo y funcionesdel sistema de bases de datos dentro de una nueva arquitectura dehardware y software.

Idealmente un sistema de bases de datos paralelas, deberıa propor-cionar un mejor balance costo-desempeno que otros tipos de sistemas.Los sistemas de bases de datos paralelas ofrecen alto desempeno, altadisponibilidad y extensibilidad. El incremento en el desempeno puedeobtenerse a traves de varias soluciones como pueden ser: soporte del sis-tema operativo orientado a bases de datos, optimizacion de consultasy acceso a la informacion.

El paralelismo en bases de datos se hereda de los principios de sumodelo de datos. Particularmente, el modelo de datos relacional presen-ta grandes posibilidades de paralelizacion. Debido a esto, los proyectosde investigacion en esta area, sean academicos o industriales se centrancasi exclusivamente en sistemas relacionales.

El incremento en los tamanos de las bases de datos actuales, seacompana de una necesidad creciente de proporcionar funcionalidadessofisticadas, como el soporte de sistemas orientados a objetos, y apli-caciones basadas en multimedia[5]. En consecuencia, esto ha generadouna demanda por alto desempeno de los sistemas manejadores de basesde datos existentes. Para alcanzar el desempeno requerido, los sistemasde bases de datos han requerido de manera gradual, hacer uso del par-alelismo.

Los sistemas de bases de datos paralelas, en general, dividen o frag-mentan la informacion a fin de que varios procesadores puedan concur-rentemente manipularla y ası obtener mejores medidas de rendimiento.Ası, se presentan dos problemas fundamentales cuyas soluciones estanestrechamente ligadas; como fragmentar la informacion y como mani-pular la informacion entre varios procesadores.

Planteamiento del Problema

En paralelismo, el objetivo es usar eficientemente los procesadoresdisponibles para mantenerlos ocupados el mayor tiempo posible. Ası,

INTRODUCCION 3

un primer objetivo a lograr mediante la fragmentacion de la informa-cion, es producir partes mas o menos del mismo tamano. Pero estono es suficiente, si al momento de manipular la informacion no se dis-tribuye tambien el trabajo de manera similar entre los procesadoresdisponibles, esto es, si al momento de producir una estrategia para re-solver una consulta a la base de datos, la consulta se descompone enpiezas heterogeneas de procesamiento.

Dado que no es posible producir fragmentos y estrategias paralelaseficientes para manipulacion de la informacion, sin tener idea acerca decomo va a manipular la informacion la aplicacion, es necesario partirde un conjunto de consultas tıpicas en la aplicacion.

Por lo tanto, los problemas de fragmentacion y procesamiento deconsultas no pueden ser resueltos de manera general, y sus solucionesestan estrechamente ligadas a la aplicacion.

Por lo anterior, la implementacion de una base de datos en paraleloinvolucra varias etapas a seguir como se muestra en la Figura 1.1. Antesque nada, es necesario realizar un estudio previo de la base de datos quese desea paralelizar. Este estudio sirve principalmente para poder definirlas particiones de la base de datos. En primer lugar se debe definirun conjunto de consultas que se han de realizar a la base de datos,para de ahı obtener un conjunto de predicados simples, los cuales seutilizan para obtener un conjunto de miniterminos. De este conjunto deminiterminos se seleccionan aquellos que permiten obtener un esquemade fragmentacion adecuado. Una vez fragmentada la base de datos, seintroduce una consulta al sistema, la cual se analiza para obtener unplan de ejecucion que sea eficiente.

En un sistema de bases de datos paralelas, existen tres problemasimportantes que se deben abordar y resolver:

1. Fragmentacion. El problema de la fragmentacion consiste en dis-tribuir la base de datos entre los diferentes nodos de la red enla cual, se implementa la base de datos paralela. Los aspectosclave del proceso de fragmentacion, consisten en, encontrar unaunidad de fragmentacion que permita distribuir de manera opti-ma los datos de las relaciones, y, decidir acerca de la manera en

4 INTRODUCCION

que se va a fragmentar la base de datos.

2. Distribucion de los datos. Una vez que se ha decidido acercadel esquema de fragmentacion, es necesario realizar la distribucionde los diferentes fragmentos a los nodos de la red. Ademas se debedecidir si se asignaran copias de los fragmentos, o si estos seranreplicados a los nodos. Cada enfoque tiene sus ventajas y desven-tajas. La distribucion de los datos es un aspecto que impacta di-rectamente al balance de carga en una base de datos paralela. Esteproblema se aborda con profundidad en el capıtulo 3.

3. Procesamiento de consultas. Las consultas que se realizan alas bases de datos, se expresan generalmente a traves de algunlenguaje no procedural como SQL. Esto implica que esta expre-sion sea convertida por el DBMS, en su correspondiente expresiondel algebra relacional con el inconveniente de que una expresionen un lenguaje no procedural puede ser convertida a diferentes ex-presiones del algebra relacional equivalente. El principal problemaes, entonces, seleccionar la expresion que minimice los costos delprocesamiento de las consultas. En un sistema tıpico, esto no re-presenta mayor problema, pero no ası en un sistema de bases dedatos paralelas, pues se deben contemplar tambien aspectos rela-cionados con la red, como pueden ser la latencia y la cantidad denodos participantes.

El procesamiento de los datos es otro aspecto a tomar en cuenta,pues normalmente esto involucra transferir datos entre los diferen-tes nodos antes de poder mostrar una respuesta de la consulta. Sedebe asumir entonces, una estrategia que reduzca la transferenciade informacion entre los nodos.

Caso de estudio

Para implementar una base de datos en paralelo, obviamente, esnecesario contar con una base de datos. En este caso se tomara unabase de datos que lleva un registro de las llamadas que se realizan en el

INTRODUCCION 5

Centro de Investigacion y de Estudios Avanzados -CINVESTAV- comocaso de estudio. Esta base de datos, es sometida a cada una de lasetapas descritas en la Figura 1.1.

Figura 1.1: Implementacion de una base de datos paralela.

El objetivo general de este trabajo de tesis es desarrollar algorit-mos que permitan implementar una base de datos en paralelo.

De manera especıfica, se plantea alcanzar los siguientes objetivosparticulares.

Plantear un esquema de particionamiento para optimizar la im-plantacion de los algoritmos que se proponen.

Desarrollar algoritmos para llevar a cabo la fragmentacion de labase de datos en un caso de estudio.

Desarrollar algoritmos para procesar las consultas que se definenen el caso de estudio seleccionado.

Metodologıa

La metodologıa que permite alcanzar los objetivos anteriores involu-cra una serie de pasos, los cuales se enumeran a continuacion:

6 INTRODUCCION

1. Identificar un caso de estudio en el cual sea evidente que el de-sarrollo de una base de datos paralela beneficia los parametros derendimiento.

2. Resolver el problema del particionamiento de la base de datos.

3. Definir la manera en que se van a ubicar los datos.

4. Definir la mejor estrategia de procesamiento de consultas en para-lelo. Haciendo especial enfasis en las consultas del tipo Seleccion -Proyeccion - Junta.

5. Aplicar 1, 2 y 3 a caso de estudio.

6. Desarrollar los algoritmos propuestos en los objetivos especıficos.

7. Implementar los algoritmos en utilizando las bibliotecas de MPIsobre una computadora paralela.

El caso de estudio seleccionado para la implementacion de la basede datos paralela consiste del registro de llamadas de los conmutadoresdel CINVESTAV por un lado, y por otro, los detalles de facturacion dela companıa telefonica. Acerca de esta informacion existe una serie deconsultas que se desean hacer. La informacion de llamadas es extensateniendo en promedio al mes mas de 100,000 registros. Por lo tanto,resulta idoneo que una base de datos que guarde los registros de todoano, sea implementada en paralelo.

En el capıtulo 2, se abordan los conceptos relacionados con las basesde datos paralelas.

Posteriormente, en el capıtulo 3, se aborda directamente el proble-ma de la fragmentacion, profundizando o mostrando de manera masdetallada los conceptos relacionados con el proceso de fragmentacion.En este capıtulo tambien, se realiza el analisis de la base de datos a im-plementar en paralelo y, los algoritmos que se desarrollaron para llevarcabo la fragmentacion de la base de datos. Se presenta con detalle elcaso de estudio, y al final de este capıtulo, se muestra el rendimientodel proceso de fragmentacion.

INTRODUCCION 7

En el capıtulo 4, se plantea el problema del procesamiento de con-sultas, sus objetivos y las diferentes etapas involucradas en el proce-samiento de consultas. En este trabajo se implementa una mecanismopara poder realizar consultas a la base de datos del caso de estudio.La principal caracterıstica del procesador de consultas es convertir unaconsulta expresada en algebra relacional sobre la base de datos del casode estudio, a su correspondiente expresion en calculo relacional sobrela base de datos en paralelo, para posteriormente seleccionar una es-trategia de ejecucion para dicha consulta.

Finalmente, se presentan las conclusiones del trabajo desarrollado.En el apendice A, se muestra una lista de consultas tıpicas que se lerealizan a la base de datos del caso de estudio, la cual fue necesariapara poder definir un esquema de fragmentacion apropiado.

Capıtulo 2

Bases de Datos Paralelas

El computo distribuido normalmente involucra computadoras conec-tadas en una red de area local o en una red de area amplia. Actualmenteel incremento en el uso de estaciones de trabajo y computadoras pa-ralelas poderosas en sistemas distribuidos tiene un alto impacto en latecnologıa de bases de datos distribuidas.

Una computadora paralela o multiprocesador es en sı mismo, unsistema distribuido compuesto por un numero determinado de nodos(procesadores y memorias) conectados en una red rapida dentro de ungabinete. Por supuesto, se puede revisar la tecnologıa de bases de datosdistribuidas y extenderla para implementar los sistemas de bases dedatos paralelas (SBDP en adelante). Un SBDP, explota el paralelismoen la manipulacion de los datos para producir alto desempeno y altadisponibilidad de los servidores de bases de datos. Las bases de datosparalelas (BDP) es una mezcla de otras tecnologıas como se puedeobservar en la Figura 2.1.

Figura 2.1: Tecnologıas en que se apoyan las bases de datos paralelas.

9

10 CAPITULO 2. BASES DE DATOS PARALELAS

Actualmente, se han desarrollado soluciones orientadas en software,que permiten explotar el hardware de los multiprocesadores. Los ob-jetivos de los sistemas de bases de datos paralelas se pueden alcanzarextendiendo la tecnologıa de las bases de datos distribuidas, por ejem-plo, particionando la base de datos a traves de multiples y pequenosdiscos, de tal forma que permita obtener consultas paralelas. Esto puedeconducir a mejoras considerables tanto en tiempo de respuesta como enel numero de transacciones por segundo (produccion). Un sistema debases de datos paralelas se puede definir libremente como un sistemamanejador de bases de datos (DBMS) implementado en sis-temas con multiprocesadores fuertemente acoplados [4] Estadefinicion incluye muchas alternativas que van de la migracion direc-ta de un DBMS existente, lo cual puede requerir la re-escritura de lasrutinas con el sistema operativo mediante combinaciones sofisticadasde procesamiento en paralelo y funciones del sistema de bases de datosdentro de una nueva arquitectura de hardware y software.

Se puede obtener una mejor idea observando el esquema de las basesde datos paralelas que se presenta en la Figura 2.2, la cual describeque una BDP se compone de una cantidad de nodos, cada uno de el-los cuenta con sus propios recursos como procesador, memoria y discoduro. La comunicacion dentro de una BDP debe apoyarse en una redde interconexion veloz. De ahı la ventaja de utilizar un sistema mul-tiprocesador como anfitrion de la BDP, pues estos, normalmente secomunican a traves de una red de interconexion interna y por endemuy veloz. En este ultimo caso, es necesario analizar el subsistema deentradas y salidas para prevenir posibles cuellos de botella. El entornoparalelo de la Figura 2.2, representa un entorno con arquitectura nadacompartido, cuya principal caracterıstica es que cada nodo dentro delentorno cuenta con sus propios recursos -cpu, memoria, discos duros-.Por otro lado, existen tambien los entornos paralelos compartidos, enlos cuales los recursos de memoria y almacenamiento son compartidosentre todos los nodos del entorno. Los entornos compartidos pueden serparcialmente compartidos o todo compartido.

La implementacion de bases de datos paralelas recae obviamente en

2.1. SISTEMAS DE BASES DE DATOS EN PARALELO 11

Figura 2.2: Esquema de bases de datos paralelas.

las tecnicas de bases de datos distribuidas. Sin embargo, los aspectoscrıticos de este enfoque son:

Fragmentacion y ubicacion de los datos. Su principal objetivo esincrementar el paralelismo.

Consultas en paralelo. Facilitar la mayor cantidad de consultasconcurrentes a la base de datos y reducir el tiempo de respuesta.

Procesamiento de datos en paralelo. Una vez que se obtiene unesquema de particionamiento, es necesario proporcionar los meca-nismos para un procesamiento eficiente de los operadores de basesde datos, por ejemplo, los operadores del algebra relacional.

Las bases de datos paralelas se pueden aplicar principalmente ensistemas que manejan volumenes enormes de informacion con consultascomplejas, entre los que se pueden citar: pronostico del tiempo, censos,oceanografıa, astronomıa.

2.1. Sistemas de Bases de Datos en Paralelo

Los sistemas de bases de datos paralelas combinan administracion debases de datos y procesamiento paralelo para incrementar el desempenoy la disponibilidad de la informacion.

El medio ambiente tıpico de un SBDP consiste de un conjunto desitios o nodos en los cuales se deben ejecutar los programas que procesen


los datos, cada nodo incluye tambien (y esto depende del esquema dedistribucion que se adopte), un fragmento de la base de datos original,un sistema de manejo de bases de datos y facilidades de comunicaciones.

2.1.1. Aspectos Importantes de los SBDP

Existen varios factores relacionados con la implementacion de basesde datos paralelas que no se presentan en bases de datos centralizadas.Entre los mas importantes se encuentran los siguientes(Fig. 2.3):

1. Diseno de la base de datos paralela. En el diseno de bases dedatos paralelas se debe considerar el problema de como distribuir lainformacion entre los diferentes nodos de la BDP. Los dos aspectosa tratar en el diseno de la BDP son fragmentacion y distribucion

2. Procesamiento de consultas. En el procesamiento de consultasen BDP se tiene que considerar el procesamiento de una consultay ademas el costo involucrado en la transmision de informacionentre los diferentes nodos para la obtencion de los resultados de laconsulta que se solicito.

3. Control de concurrencia. El control de concurrencia es la ac-tividad de coordinar accesos concurrentes a la base de datos. Unaspecto interesante del control de concurrencia es el manejo deinterbloqueos. El sistema no debe permitir que dos o mas transac-ciones se bloqueen entre ellas.

4. Confiabilidad. En cualquier sistema de bases de datos, centrali-zado o paralelo, se deben ofrecer garantıas de que la informaciones confiable. En sistemas paralelos, el manejo de la atomicidady durabilidad de las transacciones es aun mas complejo, pues unasola transaccion puede involucrar dos o mas fragmentos de la BDP.

Un SBDP debe proporcionar a los usuarios una vista transparentede la base de datos, es decir el usuario debe tener la impresion de queesta trabajando de manera local y solo con la informacion de su interes.Para alcanzar esto, la responsabilidad sobre el manejo de transparencia

2.2. ARQUITECTURA DE UN SBDP 13

Figura 2.3: Factores importantes en un SBDP

debe ser compartida por el sistema operativo, el sistema de manejo debases de datos y el lenguaje de acceso a la base de datos. Entre estos tresmodulos se deben resolver los aspectos sobre el procesamiento paralelode consultas.

El desarrollo de este trabajo esta relacionado solo con los aspectos delprocesamiento de consultas y el diseno de la distribucion; consideradoscomo los mas basicos y estrategicos de una BDP.

2.2. Arquitectura de un SBDP

La mayorıa de los sistemas de manejo de bases de datos actualmentedisponibles se basan en la arquitectura ANSI-SPARC, la cual divide aun sistema en tres niveles: interno, conceptual y externo (Fig. 2.4). Lavista conceptual representa la vision que tiene la comunidad de usuariosde la base de datos. La vista externa permite a los usuarios ver sololos datos de interes en la base de datos, proporcionando ası una vistapara las aplicaciones de los usuarios, las cuales pueden ser diferentes. Elesquema interno a su vez, es el nivel de descripcion mas bajo de la basede datos y tiene que ver directamente con la organizacion fısica de losdatos dentro de la computadora. Este esquema interactua directamentecon el sistema de archivos del sistema operativo.

Los sistemas centralizados se apegan perfectamente a la arquitecturade la Figura 2.4, sin embargo en los SBDP, intervienen otros aspectos


Figura 2.4: Arquitectura ANSI SPARC

importantes los cuales se presentan en la Figura 2.5. El esquema defragmentacion describe la forma en que las relaciones se fragmentanentre los distintos nodos de la BDP, y el esquema de asignamientoespecifica, la ubicacion de cada uno de los fragmentos de la base dedatos.

De acuerdo con la Figura 2.5, un usuario ejecuta su consulta sobre elesquema global de la base datos. El SBDP determina en que fragmentode la BDP se encuentra la informacion utilizando la informacion delesquema de fragmentacion. El SBDP toma entonces la consulta y conla informacion del esquema de fragmentacion, reconstruye la consultade manera que pueda ser ejecutada ya no sobre el esquema global, sinosobre el fragmento. El siguiente paso, es determinar en que nodo delentorno se encuentra la informacion, y para esto, el SBDP se apoya delesquema de asignamiento, esto le permite al SBDP indicarle a los nodoscon fragmentos involucrados en la consulta, que ejecuten la consultareconstruida. Una vez que llega la consulta al esquema local de cadafragmento, la consulta es procesada como una consulta centralizada.

2.3. FRAGMENTACION 15

Figura 2.5: Arquitectura de un SBDP

2.3. Fragmentacion

Una de las tecnicas preferidas para la solucion de los problemases dividirlo en partes. Ası mismo, uno de los principales problemasen bases de datos grandes, es el enorme espacio de busqueda para lainformacion de manera que se satisfagan las consultas que se soliciten.La fragmentacion ayuda a resolver este problema al dividir la base dedatos en fragmentos tales que, permitan segmentar el enorme espacio debusqueda de la base de datos original. Esto permite reducir los tiemposde respuesta a los usuarios, debido a que una base de datos fragmentadapermite realizar busquedas en paralelo.

¿Como debe fragmentarse una base de datos?, ¿Cual es la unidadrazonable de distribucion?, se puede considerar que una relacion com-pleta es lo adecuado ya que las vistas de usuario son subconjuntos delas relaciones. Sin embargo, el uso completo de las relaciones no fa-


vorece las cuestiones de eficiencia sobre todo aquellas relacionadas conel procesamiento de consultas por lo siguiente: normalmente una basede datos es enorme debido a que existen muchas instancias de las rela-ciones, esto ocasiona que existan tablas con gran cantidad de registros,con lo cual al asignar cada fragmento a procesadores diferentes se puedepromover la manipulacion concurrente de la informacion..

Por otro lado el uso de sub-relaciones tambien presenta inconve-nientes; por ejemplo, las aplicaciones que no queden definidas sobre unsolo fragmento necesitaran un procesamiento adicional a fin de localizartodos los fragmento de una vista.

2.3.1. Alternativas de Fragmentacion

Esencialmente, las relaciones son mapeadas a tablas, por lo tanto, esnecesario encontrar alternativas para dividir una tabla en tablas maspequenas. Se pueden distinguir claramente dos alternativas: dividirlashorizontalmente, o dividirlas verticalmente.

Existen tres reglas que deben aplicarse durante la fragmentacion,las cuales en conjunto, aseguran que la base de datos no experimentecambios de ninguna ındole durante la fragmentacion.

1. Completitud. Si una instancia de la relacion R es descompuesta enfragmentos R1,R2....Rn, cada elemento de informacion que puedaser encontrado en R puede ser encontrado tambien en uno o masRi’s.

2. Reconstruccion. Si una relacion R se descompone en fragmentosR1, R2 .... Rn, debe ser posible definir un operador relacional 5de tal forma que: R = 5Ri, ∀Ri ∈ FR.

3. Disjuncion. Si una relacion R se descompone de manera horizontalen fragmentos R1,R2....Rn y los datos di se encuentran en Rj,entonces los datos di no se encuentran en ningun otro fragmentoRk(k 6= j). Este criterio asegura que los fragmentos horizontalessean disjuntos.


2.3.2. Fragmentacion Horizontal

La fragmentacion horizontal particiona una relacion con base en sustuplas (Figura 2.6). De esta manera, cada fragmento consta de un sub-conjunto de tuplas de la relacion. En la fragmentacion horizontal, esimportante observar la manera en que las relaciones de la base de datosse conectan unas con otras, especialmente en lo que se refiere a lasjuntas.

Figura 2.6: Fragmentacion horizontal.

ENO,JNO,RESP,DURASG

ENO,ENAME,TITLE

@@

@RL2

EMPJNO,JNAME,BUDGET,LOC

��

�L3

PROJ

TITLE,SAL

@@@R

L1

PAY

Figura 2.7: Expresion de inter-relaciones utilizando enlaces

La Figura 2.7, muestra el esquema global de una base de datoshipotetica, en donde las relaciones al inicio de las flechas (enlaces) seconocen como fuente y las relaciones al final se conocen como destino.Se definen dos funciones: propietario y miembro, ambas proporcionanmapeos del conjunto de enlaces al conjunto de relaciones. Por lo tanto,


dado un enlace, estas funciones regresan la relacion fuente y la relaciondestino respectivamente. Por ejemplo en la Figura 2.7, tomando comoreferencia el enlace L1 tenemos:

propietario(L1) = PAYmiembro(L1) = EMP

En la Figura 2.7, la direccion de los enlaces muestra una inter-relacion de uno a muchos. Por ejemplo, para cada TITULO (TITLE)existen muchos empleados con ese tıtulo. Tambien muestra una inter-relacion de muchos a muchos entre EMP y PROJ a traves de la relacionASG.

Existe una clase especial de fragmentacion horizontal, llamada frag-mentacion horizontal derivada, la cual fragmenta una relacion miembrode un enlace con base a la fragmentacion de su relacion propietario,La fragmentacion de la relacion propietario se realiza a traves de unaoperacion de seleccion. De esta manera, dado un enlace L donde propie-tario(L) = S y miembro(L) = R, los fragmentos horizontales derivadosse definen por: Ri = R n Si, 1 ≤ i ≤ w, donde w es el numero maximode fragmentos que seran definidos sobre R y Si = σFi(S), donde Fi esla formula definida por la fragmentacion horizontal principal.

2.3.3. Fragmentacion Vertical

El objetivo de la fragmentacion vertical es particionar una relacionen un conjunto mas pequeno de relaciones de tal forma que muchasde las aplicaciones de los usuarios trabajen solamente con algun frag-mento (Figura 2.8). En este contexto, una fragmentacion “optima” esaquella que produzca un esquema de fragmentacion que minimice eltiempo de ejecucion de las aplicaciones de usuario que trabajan conesos fragmentos.

La fragmentacion vertical es inherentemente mas complicada que lafragmentacion horizontal. Esto se debe al total de alternativas que estandisponibles. Por ejemplo, en el particionado horizontal, si el numero to-tal de predicados simples en Pr es n, existen 2n posibles predicadosde termino mınimo (miniterminos) que se pueden definir. Esto indica


Figura 2.8: Fragmentacion vertical.

que resulta en vano intentar obtener soluciones optimas para el proble-ma del particionado vertical; se tiene que recurrir a heurısticas. Existendos tipos de enfoques heurısticos para la fragmentacion vertical de rela-ciones globales:

1. Agrupamiento. Inicia asignando cada atributo a un fragmento, yen cada paso unir algunos fragmentos hasta que se satisfaga alguncriterio.

2. Particionando. Inicia con una relacion y decide sobre particiona-mientos beneficiosos basandose en el comportamiento de los acce-sos a los atributos que realizan las aplicaciones.

2.3.4. Ubicacion de los Datos

La ubicacion de los datos en una BDP es similar a la fragmentacionde las bases de datos distribuidas. Una similitud muy obvia es fragmen-tar la base de datos para incrementar el paralelismo, ya sea utilizandofragmentacion horizontal o vertical. Otra similitud es que debido a quela cantidad de datos es mayor que el tamano de los programas, losprogramas deben ser ejecutados en la computadora donde residen losprogramas. Sin embargo existen dos diferencias muy importantes conel enfoque de bases de datos distribuidas. Primero, no existe la necesi-dad de maximizar el procesamiento local, debido a que los usuarios noestan ligados a un nodo especıfico; segundo, el balance de carga es mas


difıcil de lograr cuando existen muchos nodos. El principal problemaes prevenir la contencion del recurso, lo cual puede dar al traste contodo el sistema -por ejemplo: un nodo puede terminar por realizar todoel trabajo, mientras que otros se mantienen desocupados-.

Debido a que los programas se ejecutan en el lugar donde residenlos datos, la ubicacion de estos es un aspecto crıtico en el desempeno.Una alternativa para la ubicacion de los datos consiste en realizar unparticionado completo de la base de datos, intentando que cada relacionse fragmente de manera horizontal a traves de todos los nodos en elsistema. Existen 3 estrategias basicas de ubicacion de datos como seilustran en la Figura 2.9:

1. En round-robin. Figura 2.9.a. Es la estrategia mas simple, ase-gura que la distribucion de los datos sea uniforme. Con N par-ticiones, la tupla i -esima en orden de insercion es asignada a laparticion imodn. Esta estrategia posibilita que el acceso secuen-cial a una relacion, pueda realizarse en paralelo. Sin embargo, elacceso directo a una tupla individual, con base en un predicado,puede requerir que se acceda a la relacion completa.

2. Por dispersion. Figura 2.9.b. En este esquema de particionado,se aplica una funcion de dispersion a alguno de los atributos, yası se obtiene el numero de particion.

3. Por intervalo. Figura 2.9.c. En este esquema de particionadobasado en rangos, las tuplas se distribuyen en intervalos de valores(rangos) con base en alguno de sus atributos. Este esquema es idealpara consultas que dependen de un rango por ejemplo: A entre A1y A2 puede ser procesada unicamente por los nodos que contienenlas tuplas con un valor de A en el rango de A1 a A2.

Es necesario destacar que no existe un esquema o tecnica de par-ticionado general que se pueda aplicar a todo tipo de aplicacion. Elparticionado es un aspecto dependiente de la aplicacion, y porlo tanto para cada aplicacion el esquema sera diferente de otras.

2.4. PROCESAMIENTO DE CONSULTAS 21

Figura 2.9: Esquemas de particionado de bases de datos.

2.4. Procesamiento de Consultas

En el procesamiento de consultas dentro de un entorno paralelo seinvolucran los mismos aspectos que en un entorno centralizado con elcosto de comunicacion como componente adicional. Una consulta nor-malmente se expresa en alguna variante del calculo relacional, normal-mente se utiliza el lenguaje SQL ya que este es un lenguaje estandariza-do para consultas a bases de datos.

El procesamiento de consultas inicia con la descomposicion de laconsulta en SQL, en una consulta equivalente que se expresa en calcu-lo relacional, generando ası un arbol de operadores del algebra rela-cional, el cual en sı, representa un plan de ejecucion de la consulta. Parauna consulta determinada, pueden existir varios arboles de operadoresequivalentes en cuanto a que producen el mismo resultado. Durante estatransformacion, el procesador de consultas debe evaluar las diferentesestrategias (arboles) obtenidas y seleccionar aquella que minimice loscostos de ejecucion de la consulta.

En un esquema paralelo se realiza el mismo procedimiento que se


realiza en un esquema centralizado, pero ademas, se debe evaluar tam-bien el costo asociado con las comunicaciones de la red del entornoparalelo. Por lo cual, un procesador de consultas paralelo debe evaluarcuestiones como la cantidad de datos a transferir por la red y la ve-locidad de la misma. Al final debe obtener una estrategia de ejecucionpara la consulta que por un lado distribuya el trabajo a realizar enuna consulta global mediante la generacion de consultas locales y, porotro lado, minimice preferentemente el costo de comunicacion, ya queeste, representa un mayor costo que todos los asociados en el modelode costos presentado en la seccion 2.4.2. La Figura 2.10, muestra ladescomposicion de una consulta global en estrategias locales las cualesse ejecutaran en paralelo.

Figura 2.10: Arbol de operadores en un esquema paralelo.


2.4.1. Arquitectura del Procesamiento de Consultas

El problema del procesamiento de consultas puede por sı mismoser descompuesto en subproblemas cada uno correspondiendo a uno decuatro niveles diferentes para abordar el problema. Los cuatro niveles enconjunto, tienen la responsabilidad de mapear una consulta a una basede datos paralela en una secuencia optimizada de operaciones locales.Los primeros tres niveles se ejecutan en un nodo utilizando informacionglobal, mientras que el ultimo nivel, se procesa en cada nodo. Los nivelesson:

Descomposicion de Consultas. El primer nivel descomponeuna consulta expresada en calculo relacional, en una consulta ex-presada en algebra relacional que opera sobre relaciones globales.El nivel de descomposicion de consultas comprende cuatro pasos:

1. Normalizacion. Involucra la manipulacion de los cuantificado-res de la consulta y de los calificadores de la misma aplicandola prioridad de los operadores logicos.

2. Analisis semantico. Se aplica un analisis semantico de la con-sulta para eliminar de inmediato aquellas consultas incorrec-tas.

3. Simplificacion. La simplificacion de la consulta permite elimi-nar predicados redundantes.

4. Restructuracion. Se aplican reglas de transformacion para con-vertir una consulta en calculo relacional en una consulta enalgebra relacional. La restructuracion debe buscar obtener unatransformacion mejorada de la consulta original.

Localizacion de los datos. El objetivo de este nivel es localizarlos datos de la consulta utilizando informacion acerca de la ubi-cacion de los datos. Aquı se determina cuales fragmentos se in-volucran en la consulta, y transforma la consulta paralela en unaconsulta sobre fragmentos. En este nivel, es posible auxiliarse deinformacion adicional de la base de datos, por ejemplo un directo-rio global de los datos puede ayudar bastante.


Optimizacion global. En este nivel la estrategia de ejecucionse describe con operadores del algebra relacional y primitivas decomunicacion como operaciones de envıo y recepcion para trans-ferir informacion entre los diferentes nodos del entorno paralelo.Tambien aquı es posible utilizar paralelismo intra-operador 1 paraincrementar la concurrencia de la consulta en paralelo, o bien, uti-lizar paralelismo inter-operador 2 para ejecutar los operadores encadenas del tipo productor - consumidor, ver secciones 4.1 y 4.2.

Optimizacion local. En este nivel se realiza la optimizacion delas sub-consultas que se ejecutan de manera local en cada uno delos nodos. Esta optimizacion se realiza en todos los nodos donderesiden fragmentos que son involucrados en la consulta. La opti-mizacion local utiliza los mismos algoritmos utilizados en sistemascentralizados.

La principal funcion del procesador de consultas relacionales es trans-formar la consulta de alto nivel tıpicamente expresada en calculo rela-cional (Figura 2.11.a) en una consulta de bajo nivel equivalente, nor-malmente en alguna variacion del algebra relacional (Figura 2.11.b).La Figura 2.11, muestra la conversion de una consulta en la cual sedesea obtener el nombre de los empleados que estan trabajando en elproyecto ’CAD/CAM’ de una base de datos hipotetica. La consulta enbajo nivel realmente implementa una estrategia de ejecucion para laconsulta. La transformacion de alto nivel a bajo nivel debe ser correc-ta y eficiente. Una consulta en calculo relacional puede tener muchastransformaciones en algebra relacional equivalentes, y debido a que laejecucion de cada estrategia equivalente puede conducir a diferentesconsumos de recursos, entonces la principal dificultad radica en selec-cionar la estrategia de ejecucion que minimice el consumo de recursos.

A diferencia de un sistema centralizado, en un sistema paralelo, elalgebra relacional no es suficiente para expresar las estrategias de eje-

1El mismo operador del arbol de consulta es ejecutado por diversos procesadores cada uno tra-bajando en un subconjunto de los datos.

2Ejecucion en paralelo de diversos operadores del arbol de consulta sobre diversos procesadores


SELECT ENAMEFROM EMP, PROJ, ASGWHERE PROJ.PNAME = ’CAD/CAM’AND PROJ.PNO = ASG.PNOAND ASG.ENO = EMP.ENO

2.11.a

ΠENAME(((σPNAME =′ CAD/CAM ′PROJ)./PNOASG)./ENOEMP )

2.11.b

Figura 2.11: Conversion del calculo relacional al algebra relacional.

cucion. Debe complementarse con operaciones para el intercambio dedatos entre los diferentes nodos que componen el sistema. Ademas dedeterminar las operaciones del algebra relacional, el procesador de con-sultas paralelo debe tambien seleccionar los mejores nodos para proce-sar los datos y posiblemente la manera en que deben ser transformados.Esto incrementa el espacio de soluciones de donde se debe seleccionaruna estrategia para la ejecucion paralela de la consulta.

El objetivo final del procesamiento de consultas en un contexto pa-ralelo, es transformar una consulta de alto nivel para una base de datosparalela, la cual es vista como una base de datos sencilla por los usuar-ios, en una estrategia de ejecucion eficiente expresada en un lenguajede bajo nivel sobre bases de datos locales.

2.4.2. Optimizacion de Consultas

La optimizacion de consultas en paralelo se refiere al proceso deproducir un plan de ejecucion para una consulta determinada que mi-nimice la funcion de costo objetiva. El plan de ejecucion seleccionadoes el mejor de un conjunto de planes examinados por el optimizador,pero no es necesariamente el mas objetivo de todos los planes posi-bles. Un optimizador de consultas se muestra generalmente con tres


componentes:

1. Un espacio de busqueda: Es el conjunto de planes de ejecucionalternativos para representar la consulta en curso. Estos planes sonequivalentes en el sentido que producen el mismo resultado, perodifieren en el orden de ejecucion de los operadores, en la forma enque estos operadores son implementados, y por lo tanto, difierentambien en el desempeno.

2. Modelo de costos: predice el costo de un plan de ejecucion de-terminado. Para ser exactos, el modelo de costos debe tener buenconocimiento acerca del ambiente de ejecucion en paralelo.

3. Una estrategia de busqueda: Explora el espacio de busqueday selecciona el mejor plan. Define cuales planes son examinados yen que orden. Las estrategias de busqueda mas utilizadas por losoptimizadores de consulta son deterministas. La construccion delplan inicia en la relacion base juntando una o mas relaciones encada paso hasta que se obtienen planes completos. Otro tipo deestrategias que se estan utilizando son las estrategias aleatorias.Estas estrategias, cambian tiempo de optimizacion por tiempo deejecucion.

Modelo de Costos

La descomposicion de una consulta global en estrategias locales tieneun costo intrınseco, el cual se puede modelar mediante la ecuacion 2.1.Tcpu representa el costo asociado con el procesamiento de los datosen memoria, Tio es el costo relacionado con la transferencia desde yhacia los dispositivos de almacenamiento fısico, como los discos duros,y finalmente, Tcomm, es el costo involucrado en las transferencias dedatos entre los diferentes nodos del entorno paralelo.

T = Tcpu + Tio + Tcomm (2.1)


En la ecuacion 2.1, resulta clara la necesidad de balancear de ma-nera adecuada los tres factores entre todos los procesadores. El tiempode cpu, tiene que ver fundamentalmente con las estrategias locales ge-neradas al descomponer una consulta global. El tiempo de E/S, Tio,esta estrechamente relacionado al tamano y la ubicacion de los frag-mentos y el tiempo de comunicaciones, Tcomm, a la abstraccion de losfragmentos y a la naturaleza (complejidad) de la consulta global.

Complejidad del Algebra Relacional

El algebra relacional es la base para expresar la salida del proce-samiento de la consulta. Por lo tanto, la complejidad de las operacionesdel algebra relacional, las cuales directamente impactan su tiempo deejecucion marca algunos principios utiles para el procesador de con-sultas. Estos principios pueden ayudar a seleccionar la estrategia deejecucion final. La manera mas simple de definir la complejidad es enterminos de las cardinalidades de las relaciones independientemente delos detalles fısicos de su implementacion como fragmentacion y estruc-turas de almacenamiento. La Figura 2.12, muestra la complejidad delas operaciones del algebra relacional en orden creciente.

Operacion Complejidad

SelectProject (sin eliminacion duplicada) O(n)

Project (con eliminacion duplicada)

GroupJoinSemiJoinDivisionOperadores set

O(nlogn)

Producto Cartesiano O(n2)

Figura 2.12: Complejidad de las operaciones del algebra relacional.


Estrategia de Busqueda

La estrategia de busqueda no es necesariamente diferente para op-timizaciones de consultas centralizadas o paralelas. Sin embargo, el es-pacio de busqueda tiende a ser mas grande debido a la existencia demas planes de ejecucion en paralelo alternativos. Ası, las estrategiasaleatorias generalmente conducen a estrategias determinısticas en laoptimizacion de consultas en paralelo. El espacio de busqueda se ob-tiene de aplicar las reglas de transformacion como por ejemplo:

Conmutatividad y asociatividad de operadores binarios.

Idempotencia de operadores unarios.

Conmutacion de las operaciones:seleccion y proyeccion.

Conmutacion de seleccion con operadores binarios.

Conmutacion de proyeccion con operadores binarios

La Figura 2.13, muestra los diferentes componentes del proceso deoptimizacion de consultas y su relacion. Ilustra como una consulta deentrada expresada en calculo relacional se somete a un proceso de op-timizacion hasta obtener el mejor plan de ejecucion para la consulta(QEP).

2.4.3. Procesamiento de Datos en Paralelo

La ejecucion de una consulta en paralelo, implica que se lance unaconsulta en cada uno de los nodos que conforman el entorno paralelo,provocando con esto que en cada uno de los nodos exista un conjunto deresultados; los cuales al final, de alguna manera deben ser unidos en elresultado final de la consulta. De lo anterior se desprende la necesidadde contar con una forma de procesar los datos obtenidos en cada uno delos nodos. Se distinguen dos estrategias principales para el tratamientode los mismos.


Figura 2.13: Proceso de optimizacion de consultas.

Estrategias de Procesamiento

Las aplicaciones de bases de datos, sean del tipo que sean, requierende procesar los resultados obtenidos de las consultas, es decir, normal-mente no solo van a recuperar los datos y mostrarlos, sino que realizanalgun proceso con ellos. Por lo tanto, para realizar el procesamiento dedatos, se puede aplicar una estrategia de las mostradas en la Figura2.14. Donde A y B son los nodos que forman el entorno paralelo; alejecutarse una consulta en cada nodo, se obtiene un conjunto de datosen cada uno de ellos, por lo tanto y de acuerdo a lo antes menciona-do, estos datos deben ser procesados utilizando la estrategia 1 o 2 dela Figura 2.14. La estrategia 1 consiste en mover el conjunto de datosmas pequeno al nodo con el conjunto de datos mas grande y realizarahı el procesamiento de los datos. Esto involucra menos transferenciasde datos a traves de la red, disminuyendo ası el componente Tcomm dela ecuacion 2.1. La segunda estrategia, involucra que los conjuntos dedatos de ambos nodos, sea transmitido a otro nodo, el cual sera el res-


Figura 2.14: Estrategias para el procesamiento de los datos en paralelo.

ponsable de realizar el procesamiento de los datos. Este enfoque liberaa los dos nodos del procesamiento de los datos, permitiendo que losnodos puedan realizar alguna otra accion.

A continuacion se presentan algunas soluciones a esta problematicapara algunos casos de estudio.

2.5. Trabajos Relacionados

El trabajo en el campo del procesamiento de consultas es bastanteamplio y cubre una gama de posibilidades entre ellas tenemos las dis-tribuidas, paralelas y orientadas a objetos, mas aun, se cuenta concombinaciones de algunas de ellas. A continuacion se describen algunostrabajos relacionados con el procesamiento de consultas.

2.5.1. Efecto de la Distorsion y el Balance de Carga en Mine-rıa de Datos en Paralelo.

En este trabajo [6], se concentra en el estudio del comportamiento endesempeno de FPM(Fast Parallel Mining) y CD (count distribution).Primero se introducen dos metricas: distorsion y balance de carga, para

2.5. TRABAJOS RELACIONADOS 31

describir la distribucion de los datos. De manera intuitiva, una base dedatos particionada tiene alta distorsion de datos si la mayorıa de loselementos de datos globales grandes son grandes localmente en unaspocas particiones. Una base de datos particionada tiene alto balancede carga si todos los procesadores tienen un numero similar de elemen-tos de datos locales. Se proponen cuatro algoritmos para el particionadode la base de datos: K-means clustering proporciona buena distorsionpero destruye el balance; Particionado aleatorio, puede proporcionaralto balance pero poca distorsion; introduciendo una limitante de op-timizacion para controlar el factor balance en el k-means clustering.Esta modificacion se conoce como Bk y produce buen balance y altadistorsion. Este ultimo se considera el algoritmo de particionamientomas favorable de todos. Las contribuciones de los autores se resumenen:

1. Refinamiento de FDM en FPM para la extraccion de reglas deasociacion en sistemas paralelos nada compartido con pocas rondasde intercambio de mensajes.

2. El desempeno de las tecnicas de reduccion en FPM son muy sensi-bles al balance de carga y a la distorsion de la distribucion de losdatos.

3. Se implemento FPM en una maquina paralela SP2.

4. Se propusieron 4 algoritmos de particionado y empıricamente severi-fico que Bkµ es el mejor de todos en la obtencion de balancey distorsion dentro de las particiones de la base de datos.

Distorsion de Datos y Balance de Carga. En una base de datos parti-cionada, la distorsion de datos y el balance de carga son caracterısticasque afectan la efectividad de la reduccion y por lo tanto el desempeno deFPM. La distorsion y el balance de carga no son independientes una deotra, y algunas combinaciones de ellas no son admisibles. Por ejemplo,no es posible tener una base de datos particionada con bajo balancede carga y muy baja distorsion. Esto es debido a que una distorsionmuy baja, sera acompanada de un balance muy alto y viceversa. Los


resultados muestran claramente que si se tiene alto balance de carga,FPM supera en desempeno a CD de manera significativa si la distor-sion se mantiene en un rango de alta a moderada. Los valores altos debalance y distorsion, favorecen a FPM; se considera que el balance esun aspecto mas importante que la distorsion.

2.5.2. Balance de Carga de Filtros de Informacion Paraleli-zados.

En[7] se presenta el concepto de filtro de informacion el cual es uti-lizado para descartar datos no interesantes de una base de datos o unflujo de datos a traves de consultas. Los filtros son consultas que ensı forman un conjunto de restricciones sobre datos que se desean recu-perar de bases de datos o flujos de datos. Es posible tambien aplicardos o mas filtros consecutivos para obtener un mejor filtrado sobre losdatos, es decir, al subconjunto de datos que produce el primer filtro, sele aplica un segundo filtro y se obtiene un subconjunto mas pequeno delos mismos datos como resultado y ası consecutivamente.

Teorema de paralelismo en datos. Si el tiempo de ejecucion de dosfiltros de informacion en paralelo (paralelismo funcional) para unconjunto de datos es kR + max(c1/r1, c2/r2), donde k ≥ 0 es unaconstante, R es el numero de procesadores identicos disponibles, ri

es el numero de procesadores asignados al filtro i, y ci , es el costoen tiempo de ejecucion total para el filtro i. Entonces el paralelismofuncional siempre es mas lento que el paralelismo en datos de losprocesadores.

Es necesario modelar la falta de balance de carga (inbalance en ade-lante) despues de aplicar filtros en multiples procesadores identicos conparalelismo en datos, o grado en el cual algunos procesadores tendranmas elementos de informacion para procesar que otros, aun y cuandocomenzaron con la misma cantidad de elementos. Existen dos estadısti-cas que son utiles para analizar el inbalance; una es el exceso en la


cantidad de datos proporcionados a los procesadores mas sobrecarga-dos, y la otra es el numero mınimo de datos que deben transferirse entrelos R procesadores para ajustar el balance. Una manera para ajustarel balance es incremental: Tener un procesador de control o mantenerlistas de los datos que necesitan ser filtrados en memoria compartida.

Los experimentos muestran que las diferencias en trabajo es el para-metro que mas afecta el balance, mayores diferencias ocasionan mayoresinbalances, tambien se en- contro que:

1. Cuando se asignaron mas de 100 elementos a un procesador, elinbalance nunca alcanzo el 10 por ciento del tiempo optimo.

2. El re-balanceo no fue necesario si la diferencia de trabajo es menorde 1.5.

3. La necesidad de re-balancear no estuvo relacionada de manera sig-nificativa con el numero de filtros.

El trabajo, termina concluyendo que el paralelismo en datos es la mejormanera de sacar ventaja de multiprocesadores para el problema de fil-trado de informacion.

2.5.3. Algoritmos Optimos para el Problema de laConsulta Multiple en Mallas Reconfigurables,con Aplicaciones.

La principal contribucion de este trabajo[8] es mostrar que un numerofundamental de problemas aparentemente no relacionados en el disenode bases de datos, como el reconocimiento de patrones, robotica, geo-metrıa computacional y procesamiento de imagenes, pueden ser resuel-tos de manera simple y elegantemente si se consideran como instanciasde un sistema algorıtmico unificado conocido como problema de losmultiples consultas.El problema de consultas multiples consiste en una tupla de cinco partes(Q, A, D, φ,

⊕). Donde Q es un conjunto de consultas, A es un conjun-

to de elementos, D, es un conjunto de soluciones, φ:Q×A → D es una


funcion. y⊕

es un operador binario conmutativo y asociativo sobre D.La principal contribucion de este trabajo es presentar un sistema al-gorıtmico unificado para resolver un numero fundamental de problemasaparentemente no relacionados. La plataforma computacional adopta-da es una malla reconfigurable. Esencialmente, una malla reconfigurable(RM) es una maquina con multiprocesadores conectados en malla re-forzada con un bus del sistema cuya configuracion cambia en respuestaa las necesidades computacionales y de comunicacion.

Este trabajo propone un algoritmo generico que soluciona una grancantidad de clases de problemas Multi-consulta (MQ) involucrandom consultas y n elementos. (m ≤ n) en una malla reconfigurable detamano

√n×

√n.

2.5.4. Analisis de Desempeno de Algoritmos Paralelos parala Consulta en Sistemas de Bases de Datos Orientadasa Objetos.

En[9] se introducen 2 tipos de algoritmos: hybrid-hash pointer y mul-tiwavefront. Ambos se analizan de manera cuantitativa, y se estudia eldesempeno utilizando tres enfoques; en el primero la base de datoscuenta con muchas clases de objetos, que a su vez contienen grandescantidades de instancias de cada clase; en el segundo, la base de datoscuenta con muchas clases de objetos, las cuales tienen un numero rela-tivamente pequeno de instancias; y en la tercera, la base de datos tieneclases de objetos de tamano variable. Los resultados muestran que elalgoritmo multiwavefront tiene tres caracterısticas distintivas que con-tribuyen a su mejor desempeno. EL ambiente de computo es una redde estaciones de trabajo con arquitectura nada compartido.

Algunas diferencias entre los enfoques hybrid-hash pointer (HP) ymultiwavefront (MW) son: MW utiliza un procesamiento basado engrafos, y HP se basa en arboles; MW utiliza una estrategia basadaen el procesamiento de consultas en dos fases, en la primera, solo sepropagan los identificadores de las instancias entre los procesadores,y los valores de los objetos que satisfacen la busqueda se recuperan


en la segunda fase; por ultimo MW realiza una doble estrategia departicionado de las bases de datos cuando existen muchas instanciasde las clases, primero, las instancias se particionan horizontalmentey los segmentos horizontales son almacenados de manera distribuidaentre diferentes procesadores, despues cada segmento es particionado demanera vertical en columnas que contienen pares de identificadores deinstancias o pares de identificadores de instancias-valores de atributo.

De acuerdo con los experimentos realizados por los autores, el en-foque MW se desempena mejor que los otros enfoques. Incluso la dife-rencia en rendimiento es enorme. Debido principalmente a que la can-tidad de datos intermedios en HP es enorme.

2.5.5. Algoritmos para Range-Join Basados en Permutacio-nes sobre Mallas N Dimensionales.

En[10] se presentan cuatro algoritmos paralelos eficientes para proce-sar juntas no equivalentes (nonequijoin), llamada range-join”, de dosrelaciones sobre computadoras conectadas en malla N-dimensional. Ran-ge-join son una generalizacion importante de equijoins convencionalesy son resueltas con enfoques basados en permutaciones en todos losalgoritmos propuestos.El algoritmo Basic Shifting Join (BASHJ) puede minimizar el numerode subconjuntos almacenados temporalmente en un procesador, perorequiere una gran cantidad de transmision de datos, mientras que el al-goritmo Buffering Shifting Join (BUSHJ) puede alcanzar alto paralelis-mo y minimizar el numero de transmisiones de datos, pero requiereuna gran cantidad de subconjuntos almacenados en cada procesador.El algoritmo Recursive Hamiltonian Cycle Join (REHCJ) utiliza unprocesador para construir un ciclo Hamiltoniano de manera recursiva,mientras que el algoritmo Parallel Hamiltonian Cycle Join (PAHCJ)utiliza todos los procesadores para construir el ciclo Hamiltoniano.

Los algoritmos basados en permutaciones consisten de las siguientesfases:


1. Clasificacion de los subconjuntos locales.

2. Permutacion y junta.

Todos los algoritmos utilizan el enfoque basado en permutaciones enel cual todos los subconjuntos de ambas relaciones son clasificados ycada subconjunto de S es permutado a cada procesador en turno.

Este trabajo concluye tambien que: BUSHJ obtiene mejor desempenoen paralelismo que BASHJ almacenando un gran numero de subcon-juntos de S en cada procesador. El rendimiento del algoritmo PAHCJes obviamente mejor que REHCJ debido a que construye el ciclo Hamil-toniano en paralelo. Ambos algoritmos Hamiltonianos requieren menosalmacenamiento y menos operaciones locales de junta, pero requierenmayor movimiento de datos que BUSHJ. Ası que se recomienda el usodel enfoque Shifting solo si el tiempo de comunicacion para la transfe-rencia de un bloque de datos entre dos procesadores vecinos es mayorque el tiempo para las operaciones locales de junta. De otra manera serecomienda el ciclo Hamiltoniano para obtener un mayor rendimiento.

Conclusiones

El problema en las BDP tiene tres componentes: fragmentar las rela-ciones, ubicar los fragmentos en los nodos del entorno paralelo, y final-mente, procesar las consultas. No existe una solucion general, por quees necesario tratar cada caso de manera particular.

Para cada caso particular, se requiere contar con un conjunto deconsultas tıpicas que permita disenar un esquema de fragmentacionadecuado para las consultas que se le realizaran a la base de datos. Elprocesamiento de las consultas debe mostrar un rendimiento adecuadoen el caso promedio, aunque, se pueden presentar casos extremos en loscuales la consulta se vea desfavorecida por el esquema de fragmentacion,ya que la solucion a las consultas depende de la ubicacion de los datos.

Para el desarrollo del presente trabajo se tomo un caso de estudio,el cual es descrito en el capıtulo 3.

Capıtulo 3

Fragmentacion

En este trabajo se implementa una base de datos tomada de un casode estudio, el esquema general del trabajo se muestra en la Figura 3.En este trabajo se siguieron los siguientes pasos:

Se definio un conjunto de consultas tıpicas que se realizan a la basede datos.

Se obtuvo un conjunto de predicados que permitieran encontrarun conjunto de miniterminos.

Se obtuvo un conjunto de miniterminos de los cuales se esco-gieron aquellos que permitieran implementar un esquema de frag-mentacion adecuado.

Se definio un esquema de fragmentacion para la base de datos.

Se desarrollo un algoritmo que realiza la fragmentacion de la basede datos.

Para esto se implemento un algoritmo que se basa en el algoritmode fragmentacion horizontal tomado de [4] y mostrado en la siguienteseccion.

Fragmentacion Horizontal

El primer paso en todo algoritmo de fragmentacion es determinarun conjunto de predicados que permitan obtener los fragmentos de las

37

38 CAPITULO 3. FRAGMENTACION

- Definicion de consultas.

- Obtencion de predicados.

- Obtencion de miniterminos.

- Definicion de un esquema de fragmentacion.

- Algoritmo de fragmentacion.

- Obtencion de fragmentos.

- Definicion de estategias de ejecucion

para las consultas.

- Desarrollo del procesador de consultas.

Figura 3.1: Esquema general del trabajo

relaciones. De esta manera, dada una relacion R(A1, A2, . . . An) dondeAi es un atributo definido sobre un dominio Di, un predicado simplepj definido sobre R, tiene la forma: pj : Ai θ V alor. Donde θ ∈ (=, <, >,≤,≥, 6=) y Valor es tomado del dominio de Ai. Se utiliza Pr

para enmarcar todos los predicados definidos sobre una relacion R. Lanegacion de pj produce el complemento de pj.

Aunque es facil tratar con predicados simples, las consultas de losusuarios frecuentemente involucran predicados mas complejos, los cualesson combinaciones logicas de predicados simples. Aquellas combina-ciones que sean particularmente interesantes para las aplicaciones, sonllamadas miniterminos. Un minitermino es una conjuncion de predica-dos simples. Los predicados simples deben tener caracterısticas impor-tantes para ası, obtener los miniterminos que a su vez, permiten obtenerlos fragmentos de las relaciones, estas caracterısticas son:

Completitud. Un conjunto de predicados simples es completo si ysolo si una aplicacion tiene la misma probabilidad de acceder acualquier tupla perteneciente a algun fragmento definido sobre elmismo conjunto1.

Minimalidad. Establece que si un predicado influye en la mane-ra en que se ha de realizar la fragmentacion (obtener fragmentos

1Esta propiedad de completitud es diferente de la caracterıstica de completitud para la frag-mentacion.

39

fi, fj, . . .), debe existir al menos una aplicacion que acceda de ma-nera diferente a fi y fj.

Aquellos miniterminos que permitan definir un esquema de frag-mentacion son conocidos como miniterminos relevantes. La si-guiente es una definicion formal de relevancia:

Sean mi y mj dos miniterminos que son iguales en su definicion,excepto que mi contiene un predicado simple pi en su forma naturalmientras que mj contiene el predicado complemento de pi es decir,¬pi. Sean tambien, fi y fj dos fragmentos definidos con base enmi y mj respectivamente. Entonces pi es relevante si y solo si:

acc(mi)

card(fi)6= acc(mj)

card(fj)(3.1)

Donde acc(mi) es la frecuencia con que las aplicaciones acceden losdatos en mi en un periodo determinado. y card(fi) es la cardinali-dad de fi. La ecuacion 3.1, indica que si se usa un predicado simpleo su complemento en un minitermino, la frecuencia de acceso dedicho minitermino usando el predicado simple, normal o comple-mentado, es diferente en dos fragmentos. Esto implica en primertermino, que la frecuencia de acceso no puede ser ni cero ni unoen ambos casos (minitermino con el predicado simple o con el pre-dicado complementado). Necesariamente, la frecuencia de accesotiene que ser diferente.

La figura 3.2, muestra un algoritmo que toma como entrada unarelacion R y un conjunto de predicado simples Pr y genera unconjunto Pr’ de predicados simples que es completo y mınimo.Este algoritmo es el punto de partida para el algoritmo que semuestra tambien en la Figura 3.3.

El algoritmo COM MIN inicia encontrando un predicado que searelevante y que particione la relacion de entrada. EL ciclo do-untilagrega predicados al conjunto Pr’ de manera iterativa asegurando la


Figura 3.2: Algoritmo COM MIN para obtener un conjunto de predicados completoy mınimo.

minimalidad de los predicados en cada paso. Al final el conjunto PR’es mınimo y completo. El segundo paso en la fragmentacion horizontales derivar un conjunto de miniterminos M que puedan ser definidos apartir de Pr’. Aunque parece trivial, la obtencion de miniterminos esmuy difıcil ya que el conjunto de miniterminos puede ser demasiadoextenso.

El tercer paso en la fragmentacion, es eliminar algunos miniterminosque puedan carecer de significado. La eliminacion se realiza al identi-ficar aquellos miniterminos que sean contradictorios de acuerdo a unconjunto de implicaciones I. Por ejemplo, si Pr′ = p1, p2, donde:

p1 : atrib = valor1p2 : atrib = valor2

y el dominio de atrib es valor1, valor2, es obvio que I contiene dosimplicaciones, las cuales establecen:

i1 : (atrib = valor1) ⇒ ¬(atrib = valor2)i2 : ¬(atrib = valor1) ⇒ (atrib = valor2)

3.1. CASO DE ESTUDIO 41

Se pueden definir los siguientes cuatro miniterminos de acuerdo aPr’:

m1 : (atrib = valor1) ∧ (atrib = valor2)m2 : (atrib = valor1) ∧ ¬(atrib = valor2)m3 : ¬(atrib = valor1) ∧ (atrib = valor2)m4 : ¬(atrib = valor1) ∧ ¬(atrib = valor2)

En este caso los miniterminos m1 y m4 son contradictorios a lasimplicaciones I y por lo tanto se eliminan de M . El algoritmo de la figura3.3 se utiliza para obtener el conjunto de miniterminos M , su entradaes una relacion R y un conjunto de predicados simples determinado conbase a las aplicaciones de la relacion R.

Figura 3.3: Algoritmo para fragmentacion horizontal

3.1. Caso de Estudio

La base de datos implementada en paralelo fue tomada de un caso deestudio, el cual consiste, por un lado, del registro que realizan los con-mutadores del CINVESTAV de las llamadas telefonicas que se realizanen cada una de las extensiones, ası como tambien los telefonos directos


que existen en cada uno de los departamentos del Centro. Por otro la-do, tambien se cuenta con la informacion que proporciona la companıatelefonica acerca de las llamadas de larga distancia que se realizan enel Centro, normalmente, la base de datos consta de una gran cantidadde registros. En un mes, existen en promedio 70,000 llamadas, por loque multiplicado por 12 nos da un total de 840,000 registros en un ano.En el conjunto de consultas mostradas en el Apendice A, se observaque varias de ellas son del tipo seleccion - proyeccion - junta, y siendoesta, una operacion que demanda una gran cantidad de procesamiento,resulta ideal realizar una implementacion de la base de datos para quelas consultas se realicen en paralelo.

El esquema de esta base de datos se muestra en la Figura 3.4. La

Figura 3.4: Esquema de la base de datos del caso de estudio.

base de datos cuenta con 4 relaciones:

1. departamentos.- Guarda la informacion de los diferentes departa-mentos del Centro.

2. extensiones.- Guarda informacion de las extensiones asignadas acada uno de los departamentos.

3. conmutador.- Guarda informacion de todas las llamadas realizadasdesde el Centro.

4. telmex.- Guarda informacion acerca de la facturacion que realizala companıa telefonica sobre las llamadas de larga distancia que serealizan desde el Centro.


La mayorıa de las consultas que se realizan a esta base de datos son deltipo Seleccion-Proyeccion-Junta.

Como se puede observar en la Figura 1.1. La implementacion de unabase de datos en paralelo inicia definiendo un conjunto de consultas.De estas consultas es necesario obtener los predicados, es decir, lascondiciones que deben satisfacer la consulta, por ejemplo horas > 1.Estos predicados son utilizados para poder encontrar los miniterminos(conjuncion de predicados) que permitan crear fragmentos de la basede datos, por ejemplo:

horas > 1 ∧ departamento = Biomedicina

Una vez obtenidos los miniterminos es necesario definir y programarel esquema de fragmentacion que se aplicara a la base de datos, parafinalmente poder definir la estrategia de ejecucion para cada una de lasconsultas que se desean hacer a la base de datos.

Algunas de las consultas que se desean hacer a la base de datos semuestran en el Tabla 3.1 2. Se resaltan los predicados simples y algunosminiterminos encontrados.

Hay dos predicados que destacan mucho: did y departamento, que alfinal ambos representan lo mismo dentro de la relacion donde se handefinido, esto sugiere que este predicado se puede utilizar en el esquemade fragmentacion. Sin embargo dentro de los miniterminos se muestrauna igualdad entre estos dos predicados, por lo tanto, para involu-crar este predicado dentro de algun minitermino relevante se cambiadid=departamento por did=’X’ donde ’X’ es un valor que varıa pa-ra cada departamento que se encuentre en la relacion departamentos.Otros predicados que aparecen con frecuencia, son numero y extensionlos cuales se encuentran en la misma situacion que did y departamento,pero su minitermino correspondiente no es apto para llevar a cabo lafragmentacion, debido principalmente a que las extensiones pertenecen

2Todas las consultas se muestran en el Apendice A.


select extension, responsable, numero marcado,duracion from extensiones, conmutador, whe-re numero=extension and ubicacion like’%celular%’ order by duracion desc limit 10

Obtener las 10 lla-madas a celular maslargas.

select extension, responsable, numero marcado,duracion, ubicacion from conmutador, extensioneswhere numero = extension and ubicacion !=’LOCAL’ and ubicacion not like ’%celular%’ or-der by duracion desc limit 10

Obtener las 10 lla-madas de larga dis-tancia mas largas.

select extension, responsable, sum(importe) ascosto from extensiones, conmutador where nu-mero = extension group by numero order bycosto desc limit 10

Obtener las 10 ex-tensiones que incur-ren en mayores gas-tos.

select nombre as departamento, sum(importe) ascosto from extensiones, conmutador, departamen-tos where numero = extension and departa-mento = did group by did order by costo desclimit 10

Obtener los 10 depar-tamentos que incur-ren en mayores gas-tos.

Tabla 3.1: Consultas tıpicas que se realizan a la base de datos.

a un departamento, ademas existen mas extensiones que departamen-tos.

De acuerdo al conjunto completo de consultas definido en el ApendiceA, y al proceso descrito en la Figura 3, se realiza un analisis de los pre-dicados y miniterminos (Tablas 3.2 y 3.3) que permiten fragmentar labase de datos del caso de estudio. El principal analisis que se hace esacerca de la frecuencia de la aparicion de predicados en las consultas.En la Tabla 3.2, se presentan los predicados mas significativos. En la

Predicado Frecuenciaextensiones.numero 10extensiones.responsable 7conmutador.importe 7conmutador.extension 7departamentos.nombre 6departamentos.did 5extensiones.departamento 4

Tabla 3.2: Analisis de frecuencia de los predicados en las consultas.


Miniterminosextensiones.numero=conmutador.extension

∧conmutador.ubicacion like ’%celular%’

extensiones.numero=conmutador.extension∧

departamentos.did=extensiones.departamento∧

conmutador.ubicacion like ’%celular%’facturacion.tel origendepartmentos.did=’X’

∧departamentos.did=extensiones.departamento

∧extensiones.numero=conmutador.extension

Tabla 3.3: Miniterminos encontrados.

Tabla 3.3, se muestran algunos de los miniterminos encontrados. Losultimos dos miniterminos, son los seleccionados para llevar a cabo lafragmentacion. El primero de ellos tel origen se utiliza para fragmentarla relacion telmex. La fragmentacion de la relacion telmex es muy sen-cilla ya que interviene en solo una consulta del conjunto de consultasdefinido en el apendice A.

El ultimo minitermino de la Tabla 3.3, se utiliza para realizar lafragmentacion de la relacion conmutado. El proceso de fragmentacionse realiza tomando en cuenta los dos ultimos miniterminos mostradosen la Tabla 3.3. Los datos provienen originalmente de archivos de textoque se someten a un procesamiento para determinar ası la informacionque se ha de vaciar a la base de datos del caso de estudio. La Figura3.5, muestra un breve extracto del archivo de texto de donde se ex-trae la informacion para las relaciones: departamento, extensiones yconmutador.

Como se puede observar, es un archivo plano por lo cual es nece-sario procesar el texto para extraer la informacion y vaciarla a la basede datos. En la Figura 3.6, se muestra un extracto tambien breve delarchivo de donde se origina la informacion de la relacion telmex.


Figura 3.5: Muestra del archivo original para las relaciones departamento, extensionesy conmutador.

Figura 3.6: Muestra del archivo original para la relacion telmex.

La informacion de estos archivos es guardada en la base de datosde la Figura 3.4, la cual posteriormente sera fragmentada para obtenerfragmentos con el esquema mostrado en la Figura 3.7.

Un fragmento, esta formado por dos tablas las cuales son subrelacio-nes de las relaciones telmex y conmutador. Cada fragmento es distingui-do por el nombre de las tablas que lo componen de acuerdo a la Figura3.7, ’xx’ debe ser substituido por el identificador del fragmento. Las 2tablas de cada fragmento son guardadas en la misma base de datos quees fragmentada. En la figura 3.7, se observa que la estructura de losfragmentos de las relaciones telmex y conmutador, es identica que laestructura de las relaciones originales. De lo anterior se desprende que

3.2. ALGORITMOS DE FRAGMENTACION 47

FxxDeptos FxxTel

Figura 3.7: Esquema de los fragmentos de la base de datos paralela.

no toda la base de datos es fragmentada, solo se fragmentan telmex yconmutador. Las relaciones extensiones y departamentos no son frag-mentadas debido principalmente a que su cardinalidad es muy pequena.Estas relaciones se mantienen dentro de la base de datos por lo cual setiene una ”copia” de ambas en cada uno de los fragmentos.

3.2. Algoritmos de Fragmentacion

En esta seccion se muestra el algoritmo paralelo que se implemento pa-ra llevar a cabo la fragmentacion de la base de datos. El algoritmo secompone de dos partes, un proceso maestro que se encarga de recuper-ar los datos de la base de datos original y varios procesos esclavo querealizan la fragmentacion.

Este algoritmo se implementa en un programa que utiliza MPI parallevar a cabo la fragmentacion, un ejemplo de la lınea de comando paraejecutar el programa con 4 procesadores es:

$mpirun -np 4 Fragmentar -B BD2002

Al ejecutar el programa de acuerdo a la Figura 3.8, se crean dosclases de procesos: 1 Maestro y N − 1 Esclavo, el proceso Maestrodistribuye la carga de tal manera que el balance obtenido se acerqueal ideal3y los Esclavo realizan la fragmentacion. El balance de carga esuna propiedad que se debe buscar al maximo en la fragmentacion deuna base de datos[6].

3Idealmente los fragmentos deben ser del mismo tamano.


Figura 3.8: Fragmentacion con: mpirun -np 5 Fragmentar BD2002.

3.2.1. Proceso Maestro

El proceso maestro es el encargado de indicar a los esclavos los frag-mentos que deben crear, para esto el proceso maestro debe recuperar losidentificadores de los departamentos -de acuerdo al ultimo minitermi-no seleccionado- y despues enviar cada uno al proceso esclavo que enese momento tenga el fragmento mas pequeno. Despues de enviar to-dos los identificadores de los departamentos, debe enviar un mensajea los esclavos indicandoles que se ha terminado la primera etapa defragmentacion. Inicia entonces la segunda etapa de fragmentacion uti-lizando el primer minitermino seleccionado, y siguiendo un proceso si-milar al de la primera etapa, es decir, el proceso esclavo recupera todoslos tel origen de la relacion facturacion y asigna cada uno de ellos alproceso esclavo que tenga el fragmento mas pequeno en ese momento.Al terminar con todos los tel origen indica a los esclavos que debenterminar con la segunda etapa de la fragmentacion. De esta manera segarantiza que los fragmentos sean lo mas semejante en tamano posi-ble. En este momento el proceso maestro debe terminar. La Figura 3.9,muestra el pseudocodigo que ejecuta el proceso maestro.

3.2.2. Procesos Esclavo

Durante la ejecucion del programa, existiran np − 1 procesos es-clavos, cada uno de los cuales sera el responsable de crear un fragmento.


recuperar los id de los deptos.

para cada id

preguntar a esclavos cual es mas peque~no

pedir a esclavo mas peque~no que fragmente id

fin para

Enviar peticion de termino a esclavos

recuperar telefonos origen

para cada telefono origen

preguntar a esclavos cual es mas peque~no

pedir a esclavo mas peque~no fragmente tel orig.

fin para

enviar peticion de termino a esclavos

Figura 3.9: Algoritmo maestro para fragmentacion.

Los procesos esclavos inician haciendo un ciclo dentro del cual esperanrecibir un mensaje del proceso maestro. Existen tres clases de mensajeque un proceso esclavo puede recibir:

1. Pregunta.-El proceso maestro desea saber el tamano del frag-mento.

2. Fragmentar.-El proceso debe fragmentar.

3. Terminar.-El proceso debe terminar la etapa actual de fragmenta-cion.

Si el mensaje es una pregunta, entonces el proceso esclavo consulta eltamano de su fragmento y lo envıa al proceso maestro, si el mensaje esfragmentar, entonces el proceso esclavo debe continuar la fragmentacionde acuerdo con el identificador de departamento recibido en el cuerpodel mensaje, este ciclo lo realiza hasta que el mensaje recibido sea unaindicacion que debe terminar con la primera etapa de fragmentacion.Despues de esta etapa, el proceso esclavo vuelve a realizar un ciclo simi-lar al anterior con la diferencia de que cuando el mensaje sea fragmen-tar, el proceso esclavo recibira un tel origen de la relacion facturacion,e igualmente, el ciclo continua hasta que el mensaje sea una indicacionde termino de la segunda etapa de fragmentacion. En la Figura 3.10, semuestra el pseudocodigo que ejecuta cada uno de los procesos esclavo.


hacer

recibir id y peticion de maestro

si peticion es pregunta:

enviar tama~no de fragmento a maestro

si peticion es fragmentar

fragmentar de acuerdo a id

mientras peticion sea diferente a terminar

hacer

recibir telefono y peticion de maestro

si peticion es pregunta:

enviar tama~no de fragmento a maestro

si peticion es fragmentar

fragmentar de acuerdo a telefono

mientras peticion sea diferente a terminar

recuperar estadısticas del fragmento

Figura 3.10: Algoritmo esclavo para fragmentacion.

3.2.3. Resultados

La plataforma utilizada para llevar a cabo la fragmentacion, constade un sistema multiprocesador con 4 procesadores. En el sistema seinstalo un servidor de bases de datos MYSQL y se cargo la base dedatos creada a partir de archivos de texto. La base de datos consta de losregistros de las llamadas de todo un ano, lo cual, implica 534746 tuplas.Esta base de datos fue fragmentada utilizando diferentes cantidades deprocesadores, utilizando el modelo maestro - esclavo. El mınimo deprocesadores requeridos son 2, ya que debe existir al menos un maestroy un esclavo para realizar el proceso de fragmentacion.

El punto a resaltar del algoritmo de fragmentacion presentado, es elbalance de carga que se logra obtener. La Figura 3.11, muestra la dis-tribucion de los datos para diferente cantidad de fragmentos, ası comolos tiempos requeridos para realizar la fragmentacion. Es notorio obser-var que, conforme aumenta el numero de nodos y por ende el numerode fragmentos, el balance de carga se va perdiendo, esto se debe prin-cipalmente a la naturaleza de la informacion en la base de datos. Porcitar un ejemplo, en la relacion telmex, existe una instancia que por sisola, llega a ser mas grande que todas las demas instancias de dicha


relacion. Tambien se puede observar como se esperaba que, el algorit-mo cumple con la regla de completitud de la fragmentacion, pues entodos los casos, la suma de los tamanos de los fragmentos es identicoal tamano de la base de datos original.

Al iniciar la fragmentacion se crea 1 proceso maestro y N−1 procesosesclavo, donde N es el numero de procesadores que intervinieron en lafragmentacion. Cada procesador ejecutando un proceso esclavo, creo unfragmento de las relaciones telmex y conmutador. La manera de ubicarcada fragmento es por el nombre de las sub-relaciones como se muestraen la Figura 3.7.

F/N 2 3 4 5 6 7 8 91 534746 267373 177568 133687 106950 88864 81438 631052 267373 179611 133687 106949 88324 75347 658663 177567 133686 106949 88324 75347 631054 133686 106949 92587 75347 662615 106949 88324 76575 631056 88323 75346 808327 75346 637888 68684

Comp. 534746 534746 534746 534746 534746 534746 534746 534746T(segs) 153.11 150.91 150.65 152.60 154.15 187.27 225.16 275.14

Figura 3.11: Distribucion de datos obtenida por el algoritmo de fragmentacion.

La columna F/N de la Figura 3.12 muestra a lo horizontal los nodosque participan en el proceso de fragmentacion, y a lo vertical el numerode fragmentos obtenidos en el proceso. Se observa que al aumentar elnumero de procesadores que intervienen en la fragmentacion, el tiempose va reduciendo, hasta llegar a una cierta cantidad de procesadores apartir de la cual, los tiempos se vuelven a incrementar. Es necesariohacer notar en este punto, que la fragmentacion se realiza solo una vez,por lo cual el tiempo no es un factor determinante en este aspecto.


Figura 3.12: Rendimiento del algoritmo de fragmentacion.

3.3. Conclusiones

Fragmentar una base de datos, significa prepararla para mejorar eldesempeno de las consultas a las bases de datos. En esta etapa dela implementacion, se debe contar con un conjunto de consultas querealizan las aplicaciones, para poder encontrar el mejor esquema defragmentacion y ubicacion de los datos en el entorno paralelo.

El incremento en tiempo a partir de la fragmentacion con 5 proce-sadores como se muestra en la Figura 3.12, se debe principalmente aque solo existen 4 procesadores fısicamente, de ahı que al fragmentarcon 5 procesos, el sistema operativo tiene que realizar ahora mas cam-bios de contexto. Otro factor que impacta sobre el tiempo es el sistemade entradas y salidas, pues al existir una solo base de datos fısicamente,las operaciones de E/S tienen que ser realizadas de manera secuencial.Lo ideal serıa que el entorno paralelo estuviera compuesto por sistemasautonomos, es decir, cada procesador cuente con su propia memoria ysistema de entradas y salidas, aunque se sacrificara el tiempo de trans-mision de informacion entre los procesadores.

Despues de la fragmentacion, el siguiente paso consiste en desarrollar

3.3. CONCLUSIONES 53

el procesador de consultas que sera el encargado de tomar una consul-ta por parte del usuario, someterla a un proceso de transformacion yevaluacion para su ejecucion en paralelo, y, finalmente proporcionar losresultados de la consulta al usuario.

Los detalles del desarrollo del procesador de consultas realizado eneste trabajo, se presentan en el siguiente capıtulo.

Capıtulo 4

Procesamiento de Consultas

El procesamiento de consultas en paralelo en principio es similaral procesamiento de consultas distribuidas. No obstante, el paralelismoobservado en consultas intra e inter-operador presenta algunas ventajasque pueden ser explotadas para obtener mejoras en el rendimiento. elparalelismo intra-operador y el paralelismo inter-operador representanuna ventaja para el procesamiento de las consultas en paralelo.

4.1. Paralelismo Intra-Operador

Esta clase de paralelismo se basa en la descomposicion de operado-res en un conjunto de sub-operadores independientes, cada uno de loscuales se puede ejecutar de manera paralela e independiente en algunode los nodos que participen en la consulta. Cada sub-operador procesaentonces un fragmento de la relacion. Regularmente los sub-operadoressacan provecho de la fragmentacion inicial de los datos. Considerandouna operacion seleccion - junta, el operador select se puede descompon-er de manera directa en varios operadores select, cada uno actuandosobre una particion de la base de datos; en muchos casos, sin necesidadde realizar distribucion alguna, por ejemplo, en el caso de una seleccionde una coincidencia exacta , solo una instancia del operador de selec-cion sera ejecutada si la fragmentacion se realizo sobre el atributo deseleccion utilizando el esquema de fragmentacion por dispersion, o porrango. (ver Figura 4.1).

55

56 CAPITULO 4. PROCESAMIENTO DE CONSULTAS

Figura 4.1: Paralelismo intra-operador.

4.2. Paralelismo Inter-Operador

La forma de explotar el paralelismo Inter-Operador se puede reali-zar en una cadena productor-consumidor ejecutandose en paralelo. Eneste paralelismo, cada procesador procesa un operador y sus resultadospueden ser considerados de manera inmediata por otra operacion, sintener que esperar a que todos los procesadores terminen. Por ejemploel operador select de la Figura 4.2. Se ejecuta en paralelo y el opera-dor join se puede empezar a procesar tan pronto como se tengan losresultados de dos procesadores. Este tipo de paralelismo permite ahor-rar memoria y accesos a disco ya que no es necesario materializar losresultados intermedios.

Se puede obtener paralelismo independiente cuando no existen de-pendencias entre los operadores que se ejecutan en paralelo. Por ejemplolos operadores select de la Figura 4.2 se pueden ejecutar en paralelo.En este tipo de paralelismo no existen interferencias entre los diferentesprocesadores. Sin embargo, solo es posible si el arbol de operadores esbalanceado.

4.3. Implementacion del Procesador de Consultas

En este capıtulo se presenta el procesador de consultas desarrolladopara el caso de estudio de este trabajo. El procesador de consultas seadapta al modelo maestro - esclavo, su arquitectura se muestra en la

4.3. IMPLEMENTACION DEL PROCESADOR DE CONSULTAS 57

Figura 4.2: Paralelismo inter-operador.

Figura 4.3. En sı el proceso inicia cuando el usuario desea hacer unaconsulta tıpica a la base de datos, para esto, es necesario que la consultasea definida en una expresion utilizando el sub-lenguaje de SQL definidoen la seccion 4.4. La expresion se introduce al procesador de consultas atraves de la lınea de comando, el cual primero construye la instruccionen SQL que ha de ejecutarse sobre la base de datos paralela. Una vezobtenida la instruccion SQL paralela, se define el plan de ejecucion parala consulta. La obtencion de planes de ejecucion eficientes es una funcioncompleja ya que las posibilidades de consultas arbitrarias a las bases dedatos son infinitas. Por lo anterior una forma de enfrentar el problemaes desarrollar planes para algunos tipos de consultas. Las siguientesestrategias de ejecucion se han desarrollado para el caso de estudio deeste trabajo. Sin embargo, pueden aplicarse a otras aplicaciones conconsultas genericas similares.

1. Simple. Como su nombre lo indica, esta estrategia es la mas simplede todas pues no involucra operaciones especiales. Los esclavosejecutan la consulta y envıan los resultados al proceso maestro,este a su vez, recibe los resultados y los concentra para finalmentepresentarlos al usuario.

2. Simple con Lımite. Esta estrategia es similar a la anterior, perocon la diferencia de que se ha detectado un lımite en el numero derenglones que el usuario desea recuperar, por lo cual, el procesomaestro distribuye el lımite entre los diversos procesos esclavo.

3. Simple Ordenada Similar a la estrategia simple con la diferenciaque se ha detectado una solicitud de ordenamiento en los resulta-


dos, lo cual causa que el proceso maestro lance un proceso de or-denamiento para los resultados antes de presentarselos al usuario.

4. Simple Ordenada con Lımite. Esta es una combinacion de lasdos anteriores, por lo cual se reparte el lımite entre los esclavos yel maestro lanza el proceso de ordenamiento para los resultados.

5. Agrupamiento Simple. Esta estrategia esta definida por unaconsulta donde se involucran operaciones especiales sobre la basede datos, por ejemplo: obtencion de promedios, sumatorias, con-teos, maximos y mınimos.

6. Agrupamiento con Lımite Similar al procesamiento ordenadocon la diferencia de que se ha establecido un lımite. De manerasimilar a la estrategia Simple con lımite, el proceso maestro dis-tribuye el lımite entre los procesos esclavo.

7. Agrupamiento Ordenado Similar a la anterior con la diferenciade que se ha detectado una peticion de ordenamiento sobre losresultados. Esto involucra una mayor interaccion entre los procesosesclavo y proceso maestro.

8. Agrupamiento Ordenado con Lımite Esta es una combinacionde las dos anteriores, se distribuye el lımite y posteriormente el pro-ceso esclavo lanza un proceso de ordenamiento sobre los resultados.

La construccion de la instruccion SQL y la definicion de un plande ejecucion, son tareas que se realizan en paralelo en cada uno de losnodos que participan en la consulta.

El siguiente paso a realizar es la ejecucion de la instruccion SQL enlos procesos esclavo del procesador de consultas. Lo anterior, generaresultados de manera local en cada proceso esclavo, por lo que cadauno de ellos requiere de enviar estos resultados al proceso maestro.Dependiendo del plan de ejecucion de la consulta, los procesos escla-vo intercambian una cantidad determinada de mensajes con el procesomaestro para llevar a cabo de manera conjunta el procesamiento de la

4.4. SINTAXIS PARA EL LENGUAJE DE CONSULTAS 59

consulta. El proceso maestro, entonces, concentra y procesa los resul-tados para ası, producir los resultados esperados de la consulta tıpicarealizada por el usuario.

Figura 4.3: Esquema del procesador de consultas.

4.4. Sintaxis para el Lenguaje de Consultas

Como se menciona al inicio del presente capıtulo, el procesador deconsultas es alimentado desde la lınea de comandos con una expresiondel algebra relacional. Para esto, fue necesario definir la sintaxis quepermita escribir expresiones bien formadas de un sublenguaje de SQLrepresentar una expresion del algebra relacional. La forma general deesta sintaxis se muestra en la Figura 4.4.

En esta sintaxis, se utiliza el espacio en blanco como unico separadorde palabras, y se utiliza para obtener cada uno de los componentes dela sintaxis y ademas, para separar los elementos de una lista . Como sepuede apreciar en la Figura 4.4, existen cuatro componentes principalesen la sintaxis los cuales se detallan a continuacion.


RELACIONES [ WHERE Columna OPR valor [ OPL ColumnaOPR valor · · · ] ] [ Columna [ [ ALIAS nombre ] Columna · · · ] |∗ ] [ LIMIT n ] [ ORDER BY Columna ] [ SORT BY Columna ASC| DESC ]

Figura 4.4: Sintaxis general para el lenguaje de consultas.

1. RELACIONES. Esta es la parte inicial de una expresion e indicauna lista de una o mas relaciones que forman parte de la base dedatos del caso de estudio las cuales pueden ser:

departamentos

extensiones

conmutador

telmex

Es necesario que al menos exista una de estas relaciones en laexpresion pues de lo contrario se genera un error. Al igual que enel resto de las expresiones, si se desea indicar una lista en estecaso de relaciones, estas deberan ser separadas por un espacio enblanco.

2. RESTRICCION. Esta es una parte opcional de la expresion y per-mite indicar que condiciones deben cumplir los renglones de laconsulta a ejecutar. Esta parte de la expresion debe iniciar conla palabra (operador) WHERE seguida de una o mas condicionesque deberan cumplir los renglones recuperados. La sintaxis en estaparte de la expresion se muestra en la Figura 4.5. Donde WHE-

WHERE Columna OPR Valor ( OPL Columna OPR Valor · · · )

Figura 4.5: Sintaxis para la restriccion.

RE se considera como una palabra reservada, Columna representaun atributo de una relacion, Valor es el valor que se evaluara, pu-diendo ser tambien una columna en otra relacion; OPR representa

4.4. SINTAXIS PARA EL LENGUAJE DE CONSULTAS 61

un operador relacional por ejemplo =, >, etc., OPL representauna operacion logica ya sea Y, O, o NEGACION. Esta parte de laexpresion termina al encontrarse el caracter [ o bien, al terminarla expresion. Es importante resaltar que los parentesis no formanparte de la expresion.

3. PROYECCION. Esta seccion inicia con el corchete izquierdo ydebe terminar con un corchete derecho de lo contrario se gene-rara un error en la expresion. Es aquı donde se indica la operacionde proyeccion de los atributos deseados de las relaciones involu-cradas en RELACIONES. La proyeccion puede consistir de unasola columna o bien una lista de ellas separadas por espacio enblanco. En esta parte tambien es posible definir un ALIAS per-mite definir un nombre diferente para alguna columna y es muyutil en columnas donde se involucra una funcion de agrupamiento,por ejemplo: COUNT, SUM, etc. Si se desean recuperar todas lascolumnas, se utiliza un solo asterisco en la proyeccion. Es necesariohacer notar que debe existir un espacio en blanco a ambos ladosde los corchetes. La sintaxis para la proyeccion se muestra en laFigura 4.6.

[ Columna [, Columna ... ] [ ALIAS nombre ] | ∗ ]

Figura 4.6: Sintaxis para la proyeccion.

4. CLAUSULAS. En esta seccion se indican cuales son las clausulasespeciales que habran de integrarse a la consulta. Estas clausulasson las que en un momento determinado permiten definir la es-trategia de ejecucion para la consulta, ya que en estas se indica deuna manera implıcita como deben ser tratados los resultados de laconsulta. Las clausulas que pueden estar presentes en esta partede la expresion son:

LIMIT n. Donde n indica el numero de renglones que deberecuperar.


SORT BY columna ASC — DESC. Para ordenar los resulta-dos con base a una columna y puede ser ascendente o descen-dente.

GROUP BY columna. Para agrupar los resultados con base auna funcion de agrupamiento la cual puede ser COUNT, SUM,MAX, MIN.

Como sus nombres lo indican, la primera se utiliza para especi-ficar un numero lımite de renglones, la segunda para indicar unordenamiento de los resultados con base en algun elemento de lalista de proyeccion, y finalmente, la ultima, se usa para indicaruna operacion de agrupamiento de los datos, lo cual es necesariocuando se realizan operaciones sobre la proyeccion, por ejemplouna funcion COUNT que permite realizar conteos sobre los datos.

Ejemplos de Expresiones Utilizando el Lenguaje de

Consultas

Para ilustrar mejor la sintaxis definida en la seccion 4.4, se muestranalgunos ejemplos en la tabla 4.1.

Consulta Expresion en el Lenguaje de Consultas

Obtener numero de telefono des-de donde se origino la llamada,el numero al que se marco, lapoblacion, duracion, fecha y hora delas llamadas facturadas con una du-racion mayor a una hora y que sehayan hecho despues de las 22:00 ho-ras.

telmex WHERE duracion > 60 andhora > 22:00 [ tel origen tel destinopoblacion duracion fecha hora ]

Obtener el numero, nombre del res-ponsable, ubicacion, dia y hora delas llamadas realizadas a la ciudadde ZACATECAS.

conmutador extensiones WHEREnumero = extension and ubicacion =’ZACATECAS’ [ extension respon-sable ubicacion dia hora ]

Tabla 4.1: Ejemplos de uso del lenguaje de consultas.

4.5. CONSTRUCCION DE LA INSTRUCCION SQL 63

4.5. Construccion de la Instruccion SQL

El primer proceso que realiza el procesador de consultas es: construiruna instruccion en SQL a partir de la expresion suministrada en la lıneade comando. En este proceso se aplica la sintaxis definida en la seccion4.4. La funcion principal de este proceso es convertir una consulta a labase de datos del caso de estudio, a su correspondiente consulta a labase de datos paralela. Esta consulta a la base de datos paralela debeser expresada en lenguaje SQL.

Esta tarea del procesador de consultas es realizada en paralelo.Donde cada nodo obtiene una copia exacta de la instruccion en SQL. Laventaja de hacerlo ası, es que todos los procesos obtienen la instruccionSQL de manera concurrente sin tener que esperar a que algun procesose las envıe a traves de la red. En la Figura 4.7 se muestra de manerageneral el proceso que se realiza para la obtencion de la instruccion enSQL.

De acuerdo con la Figura 4.7, las instrucciones SQL para los ejemplosde la Tabla 4.1 se expresan en SQL y para la base de datos paralela,segun se muestra en la Tabla 4.2.

Consulta SQL

Obtener el numero de telefono des-de donde se origino la llamada,el numero al que se marco, lapoblacion, duracion, fecha y hora delas llamadas facturadas con una du-racion mayor a una hora y que sehayan hecho despues de las 22:00 ho-ras.

select tel origen, tel destino, pobla-cion, duracion, fecha, hora fromFxxTel where duracion > 60 and ho-ra > 22:00

Obtener el numero, nombre del res-ponsable, ubicacion, dia y hora delas llamadas realizadas a la ciudadde ZACATECAS.

select extension, responsable, ubica-cion, dia, hora from FxxDeptos, ex-tensiones where numero = extensionand ubicacion = ZACATECAS

Tabla 4.2: Sintaxis aplicada a los ejemplos de la tabla 4.1.

En la tabla 4.2, xx es substituido por el numero de fragmento cor-respondiente.


Obtener lista de palabras

Si la primera palabra no es relacion regresa ERROR

Recorrer lista de palabras

Si palabra[i] es relacion

Agregar palabra a RELACIONES

Si palabra[i] = ’WHERE’

Agregar ’WHERE’ a RESTRICCION

Recorrer

Agregar palabra[i] a RESTRICCION

Hasta que palabra[i]=’[’ o fin de palabras

Si palabra[i] = ’[’

Recorrer

Si palabra=’ALIAS’

Agregar ’AS’ , palabra[i+1] a PROYECCION

De lo contrario

Agregar palabra[i] a PROYECCION

Hasta palabra[i]=’]’

Si hay mas palabras

Recorrer

Agregar palabra[i] a CLAUSULAS

Hasta fin de palabras

Fin Recorrer

SQL=select PROYECCION from RELACIONES RESTRICCION CLAUSULAS

Figura 4.7: Generacion de la instruccion SQL.

4.6. Definicion de la Estrategia de Ejecucion

La eleccion de la estrategia de ejecucion de la lista presentada en laseccion 4.3, depende de la presencia o no, de algunas clausulas especialesen la expresion de entrada. Estas clausulas son:

LIMIT

ORDER BY

GROUP BY

Dentro de la sintaxis se contemplan algunos detalles correspondientes aestas clausulas como por ejemplo: Si se encuentra la clausula ORDER

4.7. EJECUCION DE ESTRATEGIAS 65

BY, entonces es obligatorio que exista la palabra ASC o DESC paraindicar el modo de ordenamiento. Tambien si se encuentra la clausulaGROUP BY, entonces es necesario que en la proyeccion exista algunafuncion de agrupamiento como puede ser COUNT o SUM.

Cada una de las estrategias involucra un modo diferente para reali-zar la ejecucion de la consulta, aunque se puede mencionar que algu-nas se ayudan de otras. Por decir algo, la estrategia Simple, que es lamas sencilla de todas y se distingue precisamente por la ausencia decualquier clausula especial, sirve de apoyo para la ejecucion de todaslas estrategias de la clase Simple. Lo mismo pasa con las estrategias deAgrupamiento.

4.7. Ejecucion de Estrategias

En esta seccion se describe el proceso de ejecucion de las diferentesestrategias que se implementan en el procesador de consultas. Todasellas se ejecutan utilizando el Modelo MAESTRO - ESCLAVO. Antesde pasar a describir cada una de las estrategias, es necesario abordardos objetos que se utilizan en todas las estrategias:

1. Info de la consulta. Es una estructura en C que permite guardarinformacion obtenida de las consultas que realizan los procesosesclavo. La informacion que se guarda de las consultas con esteobjeto es:

Columnas. Cuantas columnas se obtuvieron en la consulta.

Renglones. Cuantos renglones se obtuvieron en la consulta.

Longitud. Longitud de los resultados de la consulta.

Nodo. Identificador del proceso que ejecuto la consulta.

2. Espacio de resultados. Es una estructura en C que permite guardarlos resultados obtenidos de las consultas ejecutadas por cada unode los esclavos. Este objeto es utilizado en el proceso maestrounicamente. La descripcion de este objeto es la siguiente:


Ptr. Es el espacio en memoria donde se guardan los resultadosde las consultas a manera de arreglo tridimensional de cadenas.Aunque en realidad, solo es un doble apuntador a char.

TamP. Es un arreglo que guarda el tamano de los conjuntosde resultados de cada uno de los nodos.

NP. Numero de nodos.

Rens. Numero de renglones totales en el espacio.

Cols. Numero de columnas en el espacio.

NEle. Numero de elementos - cadenas - en el espacio.

Adicionalmente, se desarrollan operaciones especiales para ma-nipular este objeto que permitan al proceso maestro manipularlos resultados de las consultas, por ejemplo: GuardarCadena(),LeerCadena() e InterRen(). Esta ultima permite intercambiar ren-glones en el espacio, sobre todo para poder realizar los ordenamien-tos en algunas de las estrategias.

De todas las estrategias se destacan dos por encima del resto: Es-trategia Simple y Estrategia Simple con Lımite. Estas dos estrategiasson el verdadero soporte para todas las demas pues en sı, son las en-cargadas de ejecutar las consultas. Las demas estrategias se apoyan enestas dos, realizando procesamiento de datos extra -principalmente elproceso maestro- para la consecucion de su objetivo. Es posible imag-inarse a las ocho estrategias planteadas como una especie de arquitec-tura en niveles de los cuales, el nivel mas bajo es ocupado por estas dosestrategias y todas las demas solo hacen uso de ellas.

4.7.1. Estrategia Simple

Esta es la estrategia mas simple y se define por la ausencia de clausu-las especiales en la expresion de entrada, el proceso del maestro y losprocesos esclavo se muestran en la Figura 4.8.

La ejecucion de esta estrategia es muy simple, como se puede obser-var en la Figura 4.8, pues existe transferencia entre maestro y esclavo


Figura 4.8: Proceso para estrategia simple.

solo en dos ocasiones: 1) Transferir datos de la consulta y 2) Transferirlos resultados de la misma.

El proceso que aquı se describe, se refiere meramente a la ejecucion dela estrategia. Antes de llegar a esta etapa, ambos procesos ya realizaronlas tareas descritas en las secciones anteriores.

Proceso Maestro

En la ejecucion de la estrategia, el proceso maestro inicia reservandoespacio para guardar la informacion de las consultas que le sera enviadapor cada uno de los esclavos. La informacion de las consultas incluye:el numero de renglones y el numero de columnas principalmente. Estainformacion es importante ya que permite al maestro reservar el espaciopara guardar los resultados de las consultas enviadas por los esclavos.

La informacion de la consulta se envıa empacada por lo cual es nece-sario desempacarla para poder tener acceso a ella. Esto quiere decir,que los datos de la consulta transferidos en un mensaje, de acuerdo aMPI, son del tipo MPI PACKED, lo que se refiere a que varios datos


-normalmente una estructura en C-, que se agrupan en una region con-tigua de memoria para su transferencia.

Despues de recibir y desempacar la informacion de la consulta, el pro-ceso maestro llega a una barrera1 donde debe esperar a que todos losprocesos arriben para poder continuar, ası se garantiza que el procesoesclavo envıe la informacion hasta que el proceso maestro haya reserva-do espacio para guardar los resultados. Ya con el espacio reservado, elproceso maestro puede recibir los resultados de la consulta provenientede los esclavos y obtener ası una tabla de n renglones por m colum-nas con la informacion recibida. Finalmente, el proceso maestro debeimprimir los resultados recibidos de cada uno de los esclavos.

Proceso Esclavo

Por otra parte, el proceso esclavo inicia reservando el espacio parainformacion de la consulta que va a realizar, y completar despues lainstruccion en SQL reemplazando la parte xx de la instruccion, por elnumero de fragmento que le toco procesar, y enseguida, establecer laconexion con la base de datos que le permita ejecutar la consulta de lacual debe recuperar informacion, por ejemplo el numero de renglonesy de columnas. Esta informacion la empaca y envıa al proceso maestroy despues llega a la barrera para permitir ası una sincronizacion contodos los procesos -principalmente con el proceso maestro-. Al pasarla barrera, el proceso esclavo le envıa los resultados de la consulta alproceso maestro, y finalmente cierra la conexion a la base de datos.

4.7.2. Estrategia Simple con Lımite

Esta estrategia se define por la presencia de una clausula especial enla expresion de entrada: la clausula LIMIT. La ejecucion de esta estrate-gia es bastante similar a la estrategia simple, de hecho esta estrategiase apoya en la otra para la obtencion de los resultados. El proceso deejecucion de esta estrategia se describe en la Figura 4.9.

1Una barrera es un punto de sincronizacion global a partir del cual los procesos de aplicacionparalela, no pueden avanzar hasta que todos hayan alcanzado dicho punto.


Figura 4.9: Proceso para estrategia simple con lımite.

El proceso maestro inicia preguntado a los esclavos ¿Cuantos ren-glones tienes para la consulta?. Esto provoca que los esclavos ejecutenuna consulta de conteo para SQL con la clausula LIMIT previamenteeliminada para obtener y enviar la respuesta al proceso maestro, eneste momento los esclavos llegan a la barrera. Mientras tanto el pro-ceso maestro debe distribuir LIMIT entre los esclavos con base a lasrespuestas de estos.

Una vez obtenida la distribucion de los lımites, el proceso maestrole envıa a los esclavos el numero de renglones que deberan recuperarde la consulta. Este lımite le permite a los procesos esclavo construiruna nueva SQL incluyendo el valor recibido para utilizarlo dentro de laclausula LIMIT de SQL.

De aquı en adelante, tanto el proceso maestro como los procesosesclavo adoptan la estrategia simple correspondiente y descrita ante-riormente para la obtencion de los resultados.


4.7.3. Estrategia Simple Ordenada

Esta estrategia se define por la presencia de una clausula ORDERBY en la expresion de entrada. Aunque aumenta en complejidad, suimplementacion es relativamente sencilla pues basicamente utiliza laestrategia simple como punto de partida y el proceso maestro realizaun proceso de ordenamiento al espacio de resultados. En otras palabras,esta estrategia no difiere en nada de la estrategia simple en lo que aprocesos esclavo se refiere y en la parte del proceso maestro solo seagrega un proceso de ordenamiento del espacio de resultados. El procesoque se realiza en la ejecucion de esta estrategia se muestra en la Figura4.10.

Figura 4.10: Proceso para estrategia simple ordenada.

Algo muy importante que hay que resaltar en esta estrategia, es quedentro del proceso de ordenamiento debe obtenerse de SQL la columnapor la cual se desea ordenar, y el tipo de dato correspondiente a lacolumna. Este ultimo es importante pues el ordenamiento puede ser demanera numerica, alfanumerica, fecha u hora. En este proceso, no seconsidera mas que una columna para realizar el ordenamiento.

4.7.4. Estrategia Simple Ordenada con Lımite

Esta estrategia se define por la existencia de una clausula ORDERBY y una clausula LIMIT en la expresion de entrada. De manera similara la estrategia anterior, esta toma la estrategia simple con lımite comopunto de partida para desempenar su funcion. Esto se puede apreciaren la Figura 4.11.


Figura 4.11: Proceso para estrategia simple ordenada con lımite.

Al igual que en la estrategia anterior, el proceso maestro realiza unproceso de ordenamiento posterior.

4.7.5. Estrategia Agrupamiento Simple

La existencia de una clausula GROUP BY, ademas de una funcion deagrupamiento como puede ser COUNT o SUM, define a estrategia. Estan simple esta estrategia, que el proceso esclavo solo tiene que utilizarla estrategia simple. Sin embargo no sucede lo mismo en el procesomaestro, aun y cuando, este utiliza tambien la estrategia simple comopunto de partida. El proceso maestro realiza posteriormente un procesode compaginacion de resultados. El esquema general de esta estrategia,se observa en la Figura 4.12.

Figura 4.12: Proceso para estrategia agrupamiento simple.

Aquı, el punto distinguible es la compaginacion que se realiza des-pues de la ejecucion de la estrategia simple. Esta compaginacion con-siste basicamente en concentrar los diferentes conjuntos de resultados y


obtener un solo conjunto de resultados final. La obtencion de este con-junto, se realiza revisando los diferentes conjuntos de resultados para:

1. Totalizar los elementos que sean comunes en mas de un conjuntode resultados. Estos elementos ya totalizados se deben pasar alconjunto final.

2. Pasar los elementos que no sean comunes en los conjuntos de re-sultados al conjunto final.

Para ejemplificar lo anterior observemos la Figura 4.13, en la cual seasume que se aplica una funcion de agrupamiento COUNT sobre elnumero marcado.

numero count57863413 10055273974 12155434567 19855214365 13556246875 168

numero count57883411 14855273974 11255446789 11955214365 10356247878 190

−→

numero count57863413 10057883411 14855273974 23355434567 19855446789 11955214365 20856246875 16856247878 190

Figura 4.13: Compaginacion de resultados de la funcion count.

4.7.6. Estrategia Agrupamiento con Lımite

Esta estrategia tiene las mismas caracterısticas que la anterior, peroaquı, el proceso esclavo ejecuta la estrategia simple con lımite, igualque el proceso maestro, el proceso maestro realiza tambien una com-paginacion de los resultados de cada nodo para obtener un conjunto dedatos final. Esta estrategia se describe en la Figura 4.14.

4.7.7. Estrategia Agrupamiento Ordenado

El agrupamiento ordenado es una estrategia que se basa en la es-trategia de agrupamiento simple, pues en esta ultima se realiza todo el


Figura 4.14: Proceso para estrategia agrupamiento con lımite.

proceso necesario para alcanzar su objetivo. El ordenamiento del con-junto de resultados final es el proceso adicional que tiene que realizarel proceso maestro en esta estrategia. El esquema de esta estrategia semuestra en la Figura 4.15.

Figura 4.15: Proceso para estrategia agrupamiento ordenado.

4.7.8. Estrategia Agrupamiento Ordenado con Lımite

Esta estrategia es la mas compleja pues involucra ciertos aspectosque no son tan faciles de ver a primera vista. Se podrıa pensar quecon lanzar la estrategia simple con lımite, ordenar el conjunto de re-sultados final, y despues tomar del espacio solo los renglones definidosen la clausula LIMIT es suficiente. Sin embargo, hay que observar elsiguiente caso: Se quieren solicitar los primeros 3 renglones aplicandouna operacion SUM sobre el importe de la llamada. Esto indica que setiene que aplicar una funcion de agrupamiento sobre el numero marca-do utilizando la funcion SUM, lo que puede producir hasta 3 renglonesen cada nodo, debidamente ordenados. El problema se presenta en la


compaginacion, ya que puede darse el caso en que un elemento en unnodo no tenga cabida dentro de los primeros 3 elementos, pero su valordentro de este nodo pueda ser suficiente para que pueda ser admitidodentro de los primeros 3 elementos del conjunto de resultados final.Este problema se ilustra en la Figura 4.16 utilizando otros datos.

Figura 4.16: Problema de compaginacion de resultados.

Existen algunas alternativas para la solucion a este problema:

Realizar una operacion de UNION de un fragmento con otro frag-mento y luego otra union con otro fragmento hasta llegar a losN fragmentos y despues lanzar la consulta sobre la union final.Esto aunque efectivo y simple de implementar, no es recomen-dable pues involucra tomar las relaciones completas y unirlas; elproblema se encuentra en la cantidad de memoria requerida paraesta operacion.

Seleccionar de uno en uno cada valor mayor o menor segun el mo-do de ordenamiento indicado, hasta completar la cantidad de ren-glones indicados en la clausula LIMIT. El problema se presenta enque se realizan demasiadas consultas; lo cual involucra demasiadosaccesos a disco y transferencia por la red.

Seleccionar N renglones multiplicado por un factor, para incre-mentar el numero de renglones a recuperar en cada fragmento. Sinembargo, esto no garantiza que se obtenga una solucion efectiva,ademas, puede no ser necesario tomar tantos renglones.


Solucion

La ultima alternativa nos sugiere que en las consultas existira unmargen de error, lo cual parece ser inevitable de cualquier forma, amenos que se utilice la primer alternativa propuesta. Lo ideal es propor-cionar un mecanismo de ”aprendizaje” para tratar de realizar ajustesal margen de error, es decir que las consultas cada vez tengan unamayor acertividad. Entonces la solucion se encuentra en manejar unvalor heurıstico para el numero de renglones a recuperar en los nodosde acuerdo a lo especificado en la clausula LIMIT. De tal manera esnecesario proporcionar un valor heurıstico inicial que en este caso esdel 50% (0.5).

Uso del valor heurıstico

El valor heurıstico se aplica directamente a la cantidad de renglonesa recuperar en cada nodo y para utilizarlo, se guarda en un archivo parapoder conservarlo y realizar ajustes posteriores. El valor heurıstico seusa de la siguiente manera:

Sea N la cantidad de renglones a recuperar indicado en la clausulaLIMIT y H el valor heurıstico que de inicio es igual al 0.5. Entonces elnumero de renglones a recuperar en cada nodo se calcula con:

RI = N/(1−H).

Ajuste del valor heurıstico

Al ajustar el valor heurıstico existen dos posibilidades: 1) Aumen-tarlo o 2) Disminuirlo.

Aumenta cuando se presenta el problema de la compaginacion, y elajuste se realiza de la siguiente manera:

1. Se toma como base los datos del primer Nodo.

2. Dentro de los primeros N renglones del primer Nodo, obtener lacantidad de datos que no se repiten en los primeros N renglonesde los otros nodos (RN).


3. Calcular nuevo valor Heurıstico: H = H + RN/N .

El valor heurıstico disminuye cuando no se presenta el problema dela compaginacion, y se ajusta de manera fija en un 10%: H = H ∗ 0,9.

A esta clase de consultas pertenecen muchas de las consultas mos-tradas en A, y su implementacion se muestra en la Figura 4.17.

Figura 4.17: Estrategia agrupamiento con ordenamiento y lımite.

4.7.9. Resultados

En esta seccion se muestra el rendimiento de procesador de consultas.En el rendimiento del procesador de consultas se realizan dos medidas:

1. El rendimiento en el procesamiento de consultas para cada una delas estrategias.

2. El rendimiento de una misma consulta utilizando cantidades dife-rentes de procesadores.

La primer medida se refiere a la confrontacion de cada una de las es-trategias para el procesamiento de consultas en paralelo, con su corres-pondiente procesamiento de manera secuencial. Esta medida se muestraen la Figura 4.18. La prueba se realizo utilizando un sistema multiproce-sador con 4 procesadores, y la ejecucion de las pruebas se realizo con 4procesos esclavo y 1 proceso maestro.

Se puede observar que practicamente en todas las estrategias, hayganancia de tiempo en la ejecucion de la consulta paralela. La mejora


Figura 4.18: Rendimiento de cada una de las estrategias.

en tiempo corresponde a un 149% en promedio, en todas las consultascon respecto al tiempo de ejecucion secuencial.

Solo en un tipo de consultas, se obtuvo mejor rendimiento de manerasecuencial y esto se debe a que la implementacion de la estrategia sim-ple con lımite, se hace en realidad una doble consulta, con el objetivo defavorecer consultas mas complejas, como lo son las consultas de agru-pamiento, las cuales son bastante favorecidas por la implementacion enparalelo de la base de datos del caso de estudio de este trabajo. Sin em-bargo, hay que tomar en cuenta que esta consulta es demasiado simplecomo para sacar ventaja del paralelismo, pero si en vez de obtener 10llamadas se pretende obtener 100,000, entonces quiza se pueda obtenerventaja del procesamiento en paralelo de la consulta. El lımite utilizadoen la consulta procesada para la estrategia ordenada con lımite es de 10renglones, al igual que en la consulta para la estrategia procesamientoordenado con lımite. Las consultas de agrupamiento son las que maspredominan en el conjunto de consultas definido como punto de parti-da para la implementacion de la base de datos en paralelo. El entorno


paralelo que se adopto para la corrida de esta prueba es un sistemamultiprocesador con 4 procesadores, y una base de datos particionadaen 4 fragmentos.

Para clarificar un poco, en la Figura 4.18, el numero al inicio de lacolumna consulta, hace referencia al numero de consulta dentro del con-junto de consultas definido, que fue tomada como base para la prueba.La columna S indica el tiempo de ejecucion de la consulta de manerasecuencial, y la columna P representa el tiempo de la consulta en para-lelo. Finalmente, la columna Dif muestra la diferencia entre el tiemposecuencial y el tiempo paralelo.

La segunda medida de rendimiento, es sobre el tiempo de ejecu-cion de cada una de las consultas mostradas previamente en la Figura4.18. Consiste basicamente en ejecutar cada consulta con cantidadesdiferentes de procesadores, y poder observar como los tiempos van dis-minuyendo al ir incrementando procesadores. Esta prueba se realizo enun sistema multiprocesador con 4 procesadores y una base de datos con4 fragmentos. Los resultados de esta prueba se muestran en la Figura4.19.

Al incrementar la cantidad de procesadores, se observa en todas lasconsultas, una tendencia a la baja en la disminucion en el tiempo deejecucion de la consulta, lo cual cumple perfectamente con la expecta-tiva del presente trabajo para mejorar los tiempos en las consultas a labase de datos del caso de estudio.

El numero maximo de esclavos que se utilizo en esta prueba es elideal, pues de esta manera se garantiza que cada esclavo sea asignadoa un procesador, alternando esporadicamente con el proceso maestro,el cual interviene al inicio y al final de las consultas principalmente.

4.8. Conclusiones

Del trabajo presentado en este capıtulo podemos destacar lo siguien-te:

Para el procesamiento de las consultas, incluidas aquellas que in-

4.8. CONCLUSIONES 79

volucren una junta, se eligio la estrategia de enviar toda la infor-macion a un proceso maestro.

Las estrategias de ejecucion de consultas, dependen de la apli-cacion, para este trabajo se definieron un numero especıfico deestrategias -8 en total-, de las cuales destacan las estrategias sim-ple y simple con lımite. Cada aplicacion debe definir sus propiasestrategias de acuerdo a la naturaleza de la misma.

El rendimiento solo puede ser mejorado cuando la consulta requierepor sı misma de un gran volumen de datos, con lo que el uso devarios procesadores en este caso, compensa el trabajo adicionalrequerido por la administracion de procesos y las necesidades decomunicacion entre ellos.


4.19.a 4.19.b

4.19.c 4.19.d

4.19.e 4.19.f

4.19.g 4.19.h

Figura 4.19: Tiempos de ejecucion de las estrategias con diferente cantidad de proce-sadores.

Conclusiones

Implementar una base de datos en paralelo involucra una serie deactividades dependientes unas de otras. Es necesario iniciar con unconjunto de consultas que se realizan a la base de datos centralizadapara poder encontrar los predicados y miniterminos que permitiran laobtencion de un esquema de fragmentacion apropiado.

El primer paso para construir un esquema de fragmentacion adecua-da, es disponer de un conjunto de consultas tıpicas, de esta manera,una buena fragmentacion depende de la aplicacion misma, la cual debeconsiderar tanto el diseno de la base de datos como las consultas queseran aplicadas sobre ella. A partir de este conjunto de consultas esnecesario obtener un conjunto de predicados, para despues obtener unaserie de miniterminos de los cuales se habran de seleccionar aquellosque permitan fragmentar la base de datos de la manera mas adecuadapara la aplicacion.

Es necesario tambien definir la manera en que los diferentes frag-mentos se van a ubicar a traves de la red que forma el entorno paralelo.La ubicacion de los datos debe explotar al maximo, la topologıa de lared, y tambien, la capacidad de procesamiento de los nodos que formanel entorno.

El objetivo de la fragmentacion es dividir la informacion que seencuentra en la base de datos para reducir el costo de ejecucion delconjunto de consultas previamente definido. Sin embargo, es imposibleautomatizar el proceso de fragmentacion de manera generica, dado quela obtencion del esquema de fragmentacion ası como la distribucion delos datos se basan principalmente en la experiencia e intuicion de lagente que lleva a cabo la implementacion de la base de datos en para-

81

82 CONCLUSIONES

lelo. El algoritmo tomado como base para desarrollar el algoritmo defragmentacion desarrollado en el presente trabajo no es un algoritmoque se implemente en un programa, en realidad es un algoritmo quese debe seguir de manera manual y que ayuda a obtener un esquemade fragmentacion adecuado. Esto significa que aquel, debe considerarseseriamente para obtener un buen diseno del esquema de fragmentacion,y una vez obtenido dicho esquema, desarrollar el algoritmo que permitafragmentar la base de datos de la aplicacion.

La granularidad de los fragmentos, es un factor que se deberıa con-siderar al momento de disenar el esquema de fragmentacion. A mayorgranularidad, mayor balance de carga se obtiene. Pero tambien, es unfactor que determina la complejidad del procesamiento de consultas. Amayor granularidad, el procesamiento de algunas consultas, principal-mente las de agrupamiento se hace mas complejo y ademas es necesariorealizar un mayor procesamiento posterior de los datos e incluso latransferencia de mensajes entre nodos se puede incrementar.

Las estrategias definidas para el procesamiento de consultas, sonen cierta forma genericas, pues se disenaron principalmente toman-do en cuenta la instruccion de SQL, mas que cualquier otro aspecto.De ahı que se tengan estrategias como procesamiento ordenado, proce-samiento ordenado con lımite, etc. Esto ocasiona que algunas consultasde un tipo particular, no se vean beneficiadas por la paralelizacion dela base de datos. Esto podrıa representar un error de diseno, pero hayque recordar que el diseno del esquema paralelo de la base de datos,depende principalmente de la aplicacion, y en el caso de estudio par-ticular del presente trabajo, las estrategias definidas cumplen perfecta-mente con los objetivos deseados, reduccion del tiempo de ejecucion delas consultas. Otro tipo de estrategias que se podrıan considerar parael procesamiento de consultas son aquellas que tomen en cuenta losoperadores del algebra relacional. Pero claro, depende de la aplicacion.

El procesamiento de una consulta del tipo Seleccion Proyeccion Jun-ta, es rapido siempre y cuando el conjunto de resultados no sea muyextenso. Esto significa que entre mayor sea la cantidad de resulta-dos obtenidos en los fragmentos, es necesario realizar un mayor proce-

CONCLUSIONES 83

samiento de datos posterior para completar la operacion de SeleccionProyeccion Junta, lo que implica un mayor movimiento de datos entrelos diferentes nodos aumentando ası el tiempo de respuesta al usuario.

El modelo maestro - esclavo, no es muy escalable, funciona bien conpocos esclavos, pero cuando estos aumentan, el maestro se convierte enun verdadero ”cuello de botella”. Este modelo es ideal para el proce-samiento de consultas, siempre y cuando no se tengan muchos esclavosy que ademas la red de comunicacion sea muy rapida. En otros casos,quiza sea conveniente contemplar otro modelo.

De este trabajo ya se han generado y presentado en diferentes foroslos primeros artıculos especıficamente [1] y [11]. Estos artıculos abordanespecıficamente el problema de la fragmentacion, por lo que resultaatractivo ahora, generar y presentar artıculos que aborden el tema delprocesamiento de consultas.

4.9. Extensiones y trabajos futuros

Para el procesamiento de las consultas del tipo Seleccion ProyeccionJunta , se puede desprender un trabajo futuro debido a la necesidad deun procesamiento adicional y excesivo de los datos obtenidos en cadafragmento para que se pueda realizar la junta de cada tupla de cadafragmento con las tuplas de los otros fragmentos.

Otro trabajo futuro a manera de extension al presente es un sistemade acceso a la base de datos del caso de estudio, que de manera trans-parente para el usuario, ejecute en paralelo las consultas que el usuarioha solicitado a la base de datos centralizada, y le muestre al mismo sololos resultados de la consulta.

Tambien resulta interesante considerar un trabajo en el que se im-plemente la misma base de datos, pero que se apoye en otro modelodiferente al maestro - esclavo, quiza implementarlo a traves de un cicloo de una malla.

Apendice A

Consultas Tıpicas a la Base deDatos

En este apendice se muestra la lista completa del conjunto de con-sultas obtenido y que sirve de base para definir el esquema de frag-mentacion.

1. Numeros mas marcados.

select numero marcado, count(numero marcado) as llamadas fromconmutador group by numero marcado order by llamadas desc limit10;

2. Que numero realizan mas llamadas.

select tel origen , count(tel origen) as llamadas from telmex groupby tel origen order by llamadas desc limit 10;

3. Principales ciudades.

select ubicacion, count(ubicacion) as llamadas from conmutadorwhere ubicacion not in(’LOCAL’,’LADA 800 S/C’, ’QUEJAS’,’INFORMACION’) and ubicacion not like ’%celular%’ group byubicacion order by llamadas desc limit 10;

4. Por Hora

select hour(hora) as Hora, count(hora) as llamadas from conmu-tador group by Hora;

85

86 APENDICE A. CONSULTAS TIPICAS A LA BASE DE DATOS

5. Por dıa de la semana.

select dia,count(dia) as llamadas from conmutador group by diaorder by llamadas;

6. Por dıa del mes.

select dayofmonth(fecha) as dia, count(fecha) as llamadas fromconmutador group by dia order by dia;

7. Llamadas a celular.

select ubicacion,count(ubicacion) as llamadas from conmutador whe-re ubicacion like ’%celular%’ group by ubicacion order by llamadasdesc limit 10;

8. Celulares mas marcados.

select numero marcado, count(numero marcado) as llamadas, (sum(time to sec (duracion))) as tiempo from conmutador where ubica-cion like ’%celular%’ group by numero marcado order by llamadasdesc limit 10;

9. Que llamadas a celular consumen mas tiempo.

select t2.extension, t1.responsable, t2.numero marcado, t2.duracionfrom extensiones as t1, conmutador as t2 where t1.numero = t2.ex-tension and t2.ubicacion like ’%celular%’ order by t2.duracion de-sc limit 10;

10. A que numeros se realizan mas llamadas locales.

select numero marcado, count(numero marcado) as llamadas fromconmutador where ubicacion=’LOCAL’ group by numero marcadoorder by llamadas desc limit 10;

11. Llamadas locales mas largas.

select t2.extension,t1.responsable, t2.numero marcado, t2.duracionfrom conmutador as t2, extensiones as t1 where t1.numero = t2.ex-tension and t2.ubicacion = ’LOCAL’ order by t2.duracion desclimit 10;

87

12. Llamadas de larga distancia mas largas.

select t2.extension, t1.responsable, t2.numero marcado, t2.duracion,t2.ubicacion from conmutador as t2, extensiones as t1 where t1.nu-mero = t2.extension and t2.ubicacion != ’LOCAL’ and t2.ubicacionnot like ’%celular%’ order byt2.duracion desc limit 10;

13. Llamadas mas largas.

select t2.extension, t1.responsable, t2.numero marcado, t2.ubicacion,t2.duracion from extensiones as t1, conmutador as t2 where t1.nume-ro = t2.extension order by t2.duracion desc limit 10;

14. Costos X extension.

select t2.extension,t1.responsable,sum(t2.importe) as costo from ex-tensiones as t1, conmutador as t2 where t1.numero=t2.extensiongroup by t1.numero order by costo desc limit 10;

15. Costos X responsable.

select t1.responsable, sum(t2.importe) as costo from extensionesas t1, conmutador as t2 where t1.numero=t2.extension group byt1.responsable order by costo desc limit 10;

16. Costos X dıa.

select dia, sum(importe) as costo from conmutador group by diaorder by costo;

17. Costos X hora.

select hour(hora) as Hora,sum(importe) as costo from conmutadorgroup by Hora order by Hora;

18. Costos X dıa y departamento.

select t1.nombre as departamento, t2.dia, sum(t2.importe) as cos-to from departamentos as t1, conmutador as t2, extensiones ast3 where t3.departamento = t1.did and t2.extension = t3.numerogroup by t2.dia,t1.nombre;

88 APENDICE A. CONSULTAS TIPICAS A LA BASE DE DATOS

19. Costos X dıa y extension.

select t3.numero as extension, t3.responsable, t1.nombre as depar-tamento, t2.dia, sum(t2.importe) as costo from departamentos ast1, conmutador as t2, extensiones as t3 where t3.departamento =t1.did and t2.extension = t3.numero group by t2.dia, t3.numero;

20. Que departamentos generan mas costos.

select t1.nombre as departamento, sum(t2.importe) as costo fromextensiones as t3, conmutador as t2, departamentos as t1 wheret3.numero = t2.extension and t3.departamento = t1.did group byt1.did order by costo desc limit 10;

21. Que departamentos realizan mas llamadas.

select t1.nombre as departamento, count(t2.numero marcado) asllamadas from extensiones as t3, conmutador as t2, departamentosas t1 where t3.numero = t2.extension and t1.did = t3.departamentogroup by(t1.did) order by llamadas desc limit 10;

22. Que departamentos realizan mas llamadas a celular.

select t1.nombre as departamento, count(t2.numero marcado) asllamadas from extensiones as t3, conmutador as t2, departamentosas t1 where t3.numero = t2.extension and t1.did = t3.departamentoand t2.ubicacion like ’%celular%’ group by(t1.did) order by lla-madas desc limit 10;

23. De cual extension se realizan llamadas mayores a una hora.

select t1.numero, t1.responsable, t2.nombre as departamento, t3.dia,t3.fecha, t3.hora, hour(t3.duracion) as duracion from extensionesas t1, departamentos as t2, conmutador as t3 where t1.departamento= t2.did and t1.numero = t3.extension and hour(t3.duracion) > 1order by duracion desc limit 10;

Bibliografıa

[1] J. Gpe. Ruiz Carrete, Arturo Dıaz Perez. Fragmentacion de basesde datos para el procesamiento de juntas en paralelo. 9a. Confe-rencia de Ingenierıa Electrica, CINVESTAV., Septiembre 2003.

[2] Paulo Coelho. El alquimista. Ed. Grijalbo., 1988.

[3] Date C.J. Introduccion a los sistemas de bases de datos. Addison-Wesley Iberoamericana., 1990.

[4] M. Tamer Ozsu, Patrick Valduriez. Principles of distributeddatabase systems. Prentice-Hall, 1999.

[5] Abdelguerfi Mahdi, Wong Kam-Fai. Parallel database techniques.Willey-IEEE Press., 1998.

[6] Cheung David, Lee Sau D. Effect of data skewness and workloadbalance in parallel data mining. IEEE Transactions on Knowledgeand Data Engineering, 14(3):498–514, 2002.

[7] C. Zaky Amr, Rowe Bail. Load balancing of parallelized informa-tion filters. IEEE Transactions on Knowledge and Data Engineer-ing, 14(2):456–461, 2002.

[8] Bokka Venkatavasu, Nakano Koji. Optimal algorithms for themultiple query problem on reconfigurable meshes, with applica-tions. IEEE Transactions on Parallel and Distributed Systems,12(9):875–887, 2001.

[9] Su Stanley Y.W., Ranka Sanjay. Performance analysis of parallelquery processing algorithms for object-oriented databases. IEEE

89

90 BIBLIOGRAFIA

Transactions on Knowledge and Data Engineering, 12(6):979–997,2002.

[10] Chen Shao Dog, Shen Hong. Permutation-based range-join algo-rithms on n-dimensional meshes. IEEE Transactions on Paralleland Distributed Systems, 13(4):413–431, 2002.

[11] J. Gpe. Ruiz Carrete, Arturo Dıaz Perez. Fragmentacion de basesde datos para el procesamiento de juntas en paralelo. 1er. Con-greso Internacional de Computacion Paralela, Distribuida y Apli-caciones, Instituto Tecnologico de Linares N.L., Septiembre 2003.

[12] Quinn Michael J. Parallel computing theory and practice. McGraw-Hill., 1994.

Documents

Tesis de Maestría - Departamento de Computación · Director de Tesis: Dr. Arturo D´ıaz P´erez M´exico, DF Diciembre del 2004. Resumen En anos˜ recientes. se ha producido un