Bases De Datos Paralelas

´ Centro de Investigacion y de Estudios Avanzados del IPN ´ Departamento de Ingenier´ Electrica ıa ´ ´ Seccion Computacion

Procesamiento de consultas en bases de datos paralelas Tesis que presenta Jos´ Guadalupe Ruiz Carrete e Para obtener el grado de: Maestro en Ciencias en la Especialidad de Ingenier´ El´ctrica Opci´n Computaci´n ıa e o o Director de Tesis: Dr. Arturo D´ P´rez ıaz e
M´xico,DF e Diciembre del 2004.

Resumen
En a˜os recientes. se ha producido un incremento continuo en la n cantidad de datos manipulados por los sistemas manejadores de bases de datos (DBMS). M´s a´n, ya no resulta extra˜o para un DBMS a u n manipular bases de datos con tama˜os que van desde los cientos de n gigabytes hasta terabytes. Por otra parte, los sistemas con m´ltiples u procesadores soncada vez m´s accesibles, por lo que es posible aplicar a c´mputo paralelo para procesar grandes vol´menes de informaci´n en o u o las bases de datos. El procesamiento de juntas (joins) en bases de datos, es una operaci´n que demanda muchos recursos de c´mputo, sobre todo en bases o o de datos grandes. Para resolver este problema se hace necesario combinar t´cnicas de bases de datos -especialmentebases de datos distribuidase y procesamiento paralelo para reducir los tiempos de respuesta a los usuarios de una base de datos grande[1]. En el presente trabajo, se muestran algoritmos para realizar cada una de las etapas involucradas en la implementaci´n de una base de datos en paralelo. Los algoritmos o son 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 quantity of data manipulated by database management systems (DBMS). Even more, no it is not uncommon for a DBMS to handle a database that ranges from hundreds of gigabytes to terabytes. Also, systems with multiple processors are becoming more and more accessible, which is why it is possible to apply parallel computing to processgreat volumes of information in a database. The processing of joins in databases is an operation that demands a lot of computer resources, especially in databases of great size. To solve this problem it is necessary to combine techniques of databases -especially distributed databases- and parallel processing to reduce answer time for users of big databases[1]. In this framework, algorithms are shownto realize each of the stages necessary to implement a parallel database. The algorithms are developed in C making use of the message passing interface (MPI).

v

Dedicatoria
“A ti Mam´ por todo cuanto significaste y significas, por a tu inmenso amor y abnegaci´n.” o “En el otro extremo, a ti Azul por lo que significas y significar´s, con toda la alegr´ que emana de tu peque˜ o ser y a ıa ncontagia.”

vii

Agradecimientos
Gracias Mam´ y Pap´ por todos sus sacrificios y preocupaciones que a a pasaron en aras de lograr que sus hijos seamos hombres de bien. Lo lograron. Por todo tu amor, cuidados y consideraciones para conmigo. Gracias Martha mi amada esposa. A toda mi familia por su apoyo constante e incondicional en cada momento de mi vida. Gracias los quiero mucho. A todos losprofesores de la secci´n de computaci´n por comparo o tir sus conocimientos y otorgarnos tiempo valioso de su vida. Gracias, aprovechar´ al m´ximo cuanto ustedes me brindaron. e a Por las consideraciones especiales hacia mi. Gracias Dr. Arturo D´ ıaz, es grato saber que dentro de la frialdad de la tecnolog´ existen perıa, sonas como usted. Al personal de la secci´n de computaci´n, especialmente aSofi por o o todo su apoyo y palabras de aliento. Gracias, ya no les dar´ mas lata. e O, ¿Quiz´s si?. a Por supuesto no pueden faltar los amigos y los amigotes, que siempre est´n ah´ para animarte y desanimarte y con todo esto lograr crecer a ı como persona cada d´ mas. ıa Mis compa˜eros del CINVESTAV: Zorra, Cepill´ JuanK, Chirris, n ın,
ix

x

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