UNIVERSIDAD AUTÓNOMA DE BAJA CALIFORNIA SUR
ÁREA DE CONOCIMIENTO DE CIENCIAS DEL MAR
DEPARTAMENTO ACADÉMICO DE SISTEMAS COMPUITACIONALES
TESIS
ANALISIS Y DISEÑO DE BASES DE DATOS DISTRUIBUIDAS ENFOCADAS A TRAVES DE LA TRAMA DE OPCIONES
QUE COMO REQUISITO PARA OBTENER EL TÍTULO DE:
INGENIERO EN TECNOLOGIA COMPUTACIONAL
PRESENTA:
GERMAN ALEJANDRO ESPINOZA MONTEVERDE
DIRECTOR:
M.S.C. JESUS ANDRES SANDOVAL BRINGAS
LA PAZ, BAJA CALIFORNIA SUR, OCTUBRE DE 2014
3
4
5
CAPÍTULO 1. INTRODUCCIÓN
1.1 ANTECEDENTES
Al comienzo del proceso de datos, durante los años cincuenta y el comienzo de
los sesenta, la regla era el tratamiento de archivos secuenciales. Todos los datos
se almacenaban en archivos secuenciales, que exigían el tratamiento de archivos
completos por los programas de aplicación. Durante los sesenta, debido a que el
almacenamiento en disco utilizando el acceso directo llegó a estar ampliamente
disponible, el procesamiento de archivos de acceso aleatorio llegó a ser factible y
popular. Este método permitió el acceso directo a datos específicos en un archivo.
En la medida en que los sistemas computacionales de procesamiento de datos se
hicieron más importantes, las empresas comenzaron a reconocer que la
información era un recurso corporativo de valor considerable. Estas percibieron
más y más que los datos necesarios para contestar numerosas preguntas
estaban disponibles en sus archivos de procesamiento de datos. Como
consecuencia, comenzaron a presionar a los sistemas de información para la
gestión en cuanto a la utilización de la potencia de la computadora para producir
información a partir de los datos corporativos. Esto inició la demanda de los
sistemas de bases de datos, los que garantizarían más efectivamente el acceso a
los datos y su manipulación.
A mediados de los sesenta se introdujeron los primeros sistemas de bases de
datos, cuyo fundamento era una estructura jerárquica de los datos. Estos
sistemas permitieron la recuperación de múltiples registros asociados con un
registro único de otro archivo. Inmediatamente después, se desarrollaron los
sistemas de base de datos en redes que soportaron interrelaciones entre registros
de archivos diferentes mucho más complejas. Ambos modelos de base de datos,
6
el jerárquico y el de red, requirieron el uso de punteros físicos predefinidos para
enlazar los registros relacionados.
En 1970, Codd revolucionó el pensamiento en la industria de las bases de datos.
El enfoque de Codd proponía el acceso y la manipulación de los datos
únicamente desde el punto de vista de sus características lógicas. Durante los
años setenta y ochenta se desarrollaron numerosos sistemas de bases de datos
relacionales y, en la actualidad, éstos dominan el mercado comercial.
En años recientes han proliferado las computadoras personales en los puestos de
trabajo, por lo que se han desarrollado las redes de computadoras, permitiendo a
los usuarios de estas computadoras compartir recursos. Una computadora, que
funciona como servidor de una red, garantiza el acceso a la base de datos desde
las estaciones de trabajo en estos puestos, permitiendo una división poderosa y
eficiente de la tarea: El servidor recupera los datos, los que la máquina cliente
solicitante procesa y presenta en pantalla para su manipulación por parte del
usuario final. Las redes de computadoras en ambiente cliente/servidor han
desarrollado un grado alto de sofisticación y se encuentran cada vez con más
frecuencia en las empresas comerciales.
Desde el punto de vista conceptual, un sistema de base de datos en una
organización grande está formado por el hardware, el software, los datos y las
personas. La configuración del hardware comprende una o más computadoras,
unidades de disco, terminales, impresoras, conexiones de red y otros dispositivos
físicos. El software incluye un Sistema Manejador de Bases de Datos (SMBD) y
los programas de aplicación utilizan el SMBD para tener acceso y manipular la
base de datos. Los datos, que representan los hechos importantes para la
organización, radican físicamente en el disco, pero se estructuran lógicamente de
forma que se logre un acceso fácil y eficiente.
Por otro lado, las bases de datos han sido consideradas como un sistema para
almacenar información. Sin embargo, con la aparición de las redes de
computadoras, esta concepción ha evolucionado de tal forma que en la actualidad
7
han surgido, además de las bases de datos cliente/servidor, arquitecturas de
bases de datos distribuidas.
Por otro lado y, considerando que tradicionalmente las bases de datos son
sistemas que almacenan información, el diseño de un sistema de base de datos
distribuido implica la toma de decisiones sobre la ubicación de los programas que
accederán a la base de datos y sobre los propios datos que constituyen esta
última, a lo largo de los diferentes puestos que configuren una red de
computadoras.
Una base de datos distribuida es un conjunto de múltiples bases de datos
lógicamente relacionadas las cuales se encuentran distribuidas en diferentes
espacios lógicos e interconectados por una red de comunicaciones.
Tradicionalmente se ha clasificado la organización de los sistemas de bases de
datos distribuidos sobre tres dimensiones: el nivel de compartición, las
características de acceso a los datos y el nivel de conocimiento de esas
características de acceso (fig. 1). El nivel de compartición presenta tres
alternativas: inexistencia, es decir, cada aplicación y sus datos se ejecutan en una
computadora con ausencia total de comunicación con otros programas u otros
datos; se comparten sólo los datos y no los programas, en tal caso existe una
réplica de las aplicaciones en cada máquina y los datos viajan por la red; y, se
reparten datos y programas, dado un programa ubicado en un determinado sitio,
éste puede solicitar un servicio a otro programa localizado en un segundo lugar, el
cual podrá acceder a los datos situados en un tercer emplazamiento. Como se
comentó líneas atrás, en este caso se optará por el punto intermedio de
compartición.
8
Fig.1 Nivel de compartición, las características de acceso a los datos y el nivel de conocimiento de esas características de acceso.
Respecto a las características de acceso a los datos existen dos alternativas
principalmente: el modo de acceso a los datos que solicitan los usuarios puede ser
estático, es decir, no cambiará a lo largo del tiempo, o bien, dinámico. Se podrá
comprender fácilmente la dificultad de encontrar sistemas distribuidos reales que
puedan clasificarse como estáticos. Sin embargo, lo realmente importante radica,
estableciendo el dinamismo como base, cómo de dinámico es, cuántas
variaciones sufre a lo largo del tiempo. Esta dimensión establece la relación entre
el diseño de bases de datos distribuidas y el procesamiento de consultas.
La tercera clasificación es el nivel de conocimiento de las características de
acceso. Una posibilidad es, evidentemente, que los diseñadores carezcan de
información alguna sobre cómo los usuarios acceden a la base de datos. Es una
posibilidad teórica, pero sería muy laborioso abordar el diseño de la base de datos
con tal ausencia de información. Lo más práctico sería conocer con detenimiento
la forma de acceso de los usuarios o, en el caso de su imposibilidad,
conformarnos con una información parcial de ésta.
9
1.2 DESCRIPCIÓN DEL PROBLEMA
El problema del diseño de bases de datos distribuidas, podría enfocarse a través
de esta trama de opciones. En todos los casos, excepto aquel en el que no existe
compartición, aparecerán una serie de nuevos problemas que son irrelevantes en
el caso centralizado.
A la hora de abordar el diseño de una base de datos distribuida podremos optar
principalmente por dos tipos de estrategias: la estrategia ascendente y la
estrategia descendente. Ambos tipos no son excluyentes, y no resultaría extraño a
la hora de abordar un trabajo real de diseño de una base de datos que se
pudiesen emplear en diferentes etapas del proyecto una u otra estrategia. La
estrategia ascendente podría aplicarse en aquel caso donde haya que proceder a
un diseño a partir de un número de pequeñas bases de datos existentes, con el
fin de integrarlas en una sola. En este caso se partiría de los esquemas
conceptuales locales y se trabajaría para llegar a conseguir el esquema
conceptual global. Aunque este caso se pueda presentar con facilidad en la vida
real, se prefiere pensar en el caso donde se parte de cero y se avanza en el
desarrollo del trabajo siguiendo la estrategia descendente. La estrategia
descendente debería resultar familiar a la persona que posea conocimientos sobre
el diseño de bases de datos, exceptuando la fase del diseño de la distribución.
Pese a todo, se resumirán brevemente las etapas por las que se transcurre. Todo
comienza con un análisis de los requisitos que definirán el entorno del sistema en
aras a obtener tanto los datos como las necesidades de procesamiento de todos
los posibles usuarios del banco de datos. Igualmente, se deberán fijar los
requisitos del sistema, los objetivos que debe cumplir respecto a unos grados de
rendimiento, seguridad, disponibilidad y flexibilidad, sin olvidar el importante
aspecto económico.
Como puede observarse, los resultados de este último paso sirven de entrada
para dos actividades que se realizan de forma paralela. El diseño de las vistas
10
trata de definir las interfaces para el usuario final y, por otro lado, el diseño
conceptual se encarga de examinar la empresa para determinar los tipos de
entidades y establecer la relación entre ellas. Existe un vínculo entre el diseño de
las vistas y el diseño conceptual. El diseño conceptual puede interpretarse como la
integración de las vistas del usuario, este aspecto es de vital importancia ya que el
modelo conceptual debería soportar no sólo las aplicaciones existentes, sino que
debería estar preparado para futuras aplicaciones. En el diseño conceptual y de
las vistas del usuario se especificarán las entidades de datos y se determinarán
las aplicaciones que funcionarán sobre la base de datos, así mismo, se
recopilarán datos estadísticos o estimaciones sobre la actividad de estas
aplicaciones. Dichas estimaciones deberían girar en torno a la frecuencia de
acceso, por parte de una aplicación, a las distintas relaciones de las que hace uso,
podría afinarse más anotando los atributos de la relación a la que accede.
Desarrollado el trabajo hasta aquí, se puede abordar la confección del esquema
conceptual global. Este esquema y la información relativa al acceso a los datos
sirven de entrada al paso distintivo: el diseño de la distribución. El objetivo de esta
etapa consiste en diseñar los esquemas conceptuales locales que se distribuirán a
lo largo de todos los puestos del sistema distribuido. Sería posible tratar cada
entidad como una unidad de distribución; en el caso del modelo relacional, cada
entidad se corresponde con una relación. Resulta bastante frecuente dividir cada
relación en subrelaciones menores denominadas fragmentos que luego se ubican
en uno u otro sitio. De ahí, que el proceso del diseño de la distribución conste de
dos actividades fundamentales: la fragmentación y la asignación. El último paso
del diseño de la distribución es el diseño físico, el cual proyecta los esquemas
conceptuales locales sobre los dispositivos de almacenamiento físico disponibles
en los distintos sitios. Las entradas para este paso son los esquemas
conceptuales locales y la información de acceso a los fragmentos. Por último, se
sabe que la actividad de desarrollo y diseño es un tipo de proceso que necesita de
una monitorización y un ajuste periódicos, para que si se llegan a producir
desviaciones, se pueda retornar a alguna de las fases anteriores.
11
1.3 PROPUESTA DE SOLUCIÓN
Existen diversas formas de afrontar el problema del diseño de la distribución. Las
más usuales se muestran en la figura 2.
Fig. 2 Diversas formas de afrontar el problema del diseño de distribución
En el primer caso, caso A, los dos procesos fundamentales, la fragmentación y la
asignación, se abordan de forma simultánea. Esta metodología se encuentra en
desuso, sustituida por el enfoque en dos fases, caso B: la realización
primeramente de la partición para luego asignar los fragmentos generados.
1.4 OBJETIVO GENERAL
Analizar y diseñar de manera eficiente y eficaz bases de datos distribuidas
enfocadas a través de trama de opciones.
1.5 BENFICIOS Y ALCANCES
Los beneficios de analizar y diseñar de manera eficiente y eficaz bases de datos
distribuidas enfocadas a través de trama de opciones, son los costos de
12
comunicación y la confiabilidad de los dato. Por lo general es menor el costo con
bases de datos distribuidas, ya que el procesamiento se puede hacer a nivel local.
Por ejemplo, con los registros de clientes alojados localmente, una sucursal no
incurre en costos de telecomunicaciones para comunicarse con una computadora
que alberga los datos de la sucursal. Si hay un problema de hardware y software
en un centro de computadora que almacena toda la información y los procesos de
la sucursal, todas las sucursales pueden verse afectadas. Con bases de datos
distribuidas, muchas sucursales pueden continuar el procesamiento por
computadora sin esperar a que la ubicación central funcione de nuevo.
13
1.6 CRONOGRAMA DE ACTIVIDADES
Actividades junio julio agosto septiembre octubre noviembre
Análisis de
información
Documentación
requerida
Análisis de las
arquitecturas
Diseño de Base de
datos distribuida
Programación del
diseño
Ejecución de
algoritmos
14
CAPÍTULO 2. MARCO TEÓRICO
2.1 INTRODUCCIÓN A LAS BASES DE DATOS
Los predecesores de los sistemas de bases de datos fueron los sistemas de
ficheros. Un sistema de ficheros está formado por un conjunto de ficheros de datos
y los programas de aplicación que permiten a los usuarios finales trabajar sobre
los mismos. No hay un momento concreto en el que los sistemas de ficheros
hayan cesado y hayan dado comienzo los sistemas de bases de datos. De hecho,
todavía existen sistemas de ficheros en uso.
Se dice que los sistemas de bases de datos tienen sus raíces en el proyecto
estadounidense de mandar al hombre a la luna en los años sesenta, el proyecto
Apolo. En aquella época, no había ningún sistema que permitiera gestionar la
inmensa cantidad de información que requería el proyecto. La primera empresa
encargada del proyecto, la North American Aviation (NAA), desarrolló una
aplicación denominada GUAM (General Update Access Method ) que estaba
basada en el concepto de que varias piezas pequeñas se unen para formar una
pieza más grande, y así sucesivamente hasta que el producto final está
ensamblado. Esta estructura, que tiene la forma de un árbol, es lo que se
denomina una estructura jerárquica. A mediados de los sesenta, IBM se unió a
NAA para desarrollar GUAM en lo que después fue IMS (Information Management
System). El motivo por el cual IBM restringió IMS al manejo de jerarquías de
registros fue el de permitir el uso de dispositivos de almacenamiento serie, más
exactamente las cintas magnéticas, ya que era un requisito del mercado por
aquella época.
A mitad de los sesenta, General Electric desarrolló IDS (Integrated Data Store).
Este trabajo fue dirigido por uno de los pioneros en los sistemas de bases de
15
datos, Charles Bachmann. IDS era un nuevo tipo de sistema de bases de datos
conocido como sistema de red, que produjo un gran efecto sobre los sistemas de
información de aquella generación. El sistema de red se desarrolló, en parte, para
satisfacer la necesidad de representar relaciones entre datos más complejos que
las que se podían modelar con los sistemas jerárquicos y, en parte, para imponer
un estándar de bases de datos. Para ayudar a establecer dicho estándar, el grupo
CODASYL (Conference on Data Systems Languages), formado por
representantes del gobierno de Estados Unidos y representantes del mundo
empresarial, fundaron un grupo denominado DBTG (Data Base Task Group), cuyo
objetivo era definir unas especificaciones estándar que permitieran la creación de
bases de datos y el manejo de los datos. El DBTG presentó su informe final en
1971 y aunque éste no fue formalmente aceptado por ANSI (American National
Standards Institute), muchos sistemas se desarrollaron siguiendo la propuesta del
DBTG. Estos sistemas son los que se conocen como sistemas de red, sistemas
CODASYL o DBTG.
Los sistemas jerárquico y de red constituyen la primera generación de los
Sistemas Manejadores de Bases de Datos (SMBD). Estos sistemas presentan
algunos inconvenientes:
Es necesario escribir complejos programas de aplicación para responder a
cualquier tipo de consulta de datos, por simple que ésta sea.
La independencia de datos es mínima.
No tienen un fundamento teórico.
En 1970, Edgar Frank Codd de los laboratorios de investigación de IBM, escribió
un artículo presentando el modelo relacional. En este artículo presentaba también
los inconvenientes de los sistemas previos, el jerárquico y el de red.
16
Pasó casi una década hasta que se desarrollaron los primeros sistemas
relacionales. Uno de los primeros es System R, de IBM, que se desarrolló para
probar la funcionalidad del modelo relacional, proporcionando una implementación
de sus estructuras de datos y sus operaciones. Esto condujo a dos grandes
desarrollos:
El desarrollo de un lenguaje de consultas estructurado denominado SQL,
que se ha convertido en el lenguaje estándar de los sistemas relacionales.
La producción de varios SMBD relacionales durante los años ochenta,
como DB2 y SLQ/DS, de IBM, y Oracle, de Oracle Corporation.
Actualmente, existen varios de SMBD relacionales para sistemas multiusuario,
aunque muchos no son completamente fieles al modelo relacional. Los SMBD
relacionales constituyen la segunda generación de los SMBD.
Sin embargo, el modelo relacional también tiene sus debilidades, siendo una de
ellas su limitada capacidad al modelar los datos. Se ha desarrollado mucha
investigación desde entonces tratando de resolver este problema. En 1976, Peter
Chen presentó el modelo entidad-relación, que es la técnica más utilizada en el
diseño de bases de datos. En 1979, Codd intentó subsanar algunas de las
deficiencias de su modelo relacional con una versión extendida denominada RM/T
(1979) y más recientemente RM/V2 (1990). Los intentos de proporcionar un
modelo de datos que represente al mundo real de un modo más fiel han dado
lugar a los modelos de datos semánticos.
La evolución reciente de la tecnología de bases de datos viene marcada por una
mayor solidez en las bases de datos orientadas a objetos, la extensión de las
bases de datos relacionales y el procesamiento distribuido. Esta evolución
representa la tercera generación de los SMBD. Por su parte, los sistemas
manejadores de bases de datos relacionales han ido evolucionando estos últimos
17
años para soportar objetos y reglas, y para ampliar el lenguaje SQL y hacerlo más
extensible y computacionalmente completo, dando lugar a lo que se conoce como
sistemas objeto-relacionales.
Durante la última década, el impacto de los avances en la tecnología de las
comunicaciones ha sido muy importante. Esto ha contribuido a que en las
empresas se haya producido una mayor distribución de la gestión automática de la
información, en contraste con la filosofía centralizadora predominante en la
tecnología inicial de bases de datos.
Las bases de datos distribuidas posibilitan el procesamiento de datos
pertenecientes a distintas bases de datos conectadas entre sí. El emplazamiento
lógico de cada una de las bases de datos se denomina nodo, conteniendo cada
uno su sistema de gestión de bases de datos, junto con las utilidades y facilidades
propias del soporte distribuido. Los nodos, por lo general, están ubicados en
emplazamientos físicos distantes geográficamente, y se encuentran conectados
por una red de comunicación de datos.
Por otra parte, los sistemas de bases de datos activas han sido propuestos como
otro paradigma de gestión de datos que satisface las necesidades de aquellas
aplicaciones que requieren una respuesta puntual ante situaciones críticas. Como
ejemplos se puede citar el control del tráfico aéreo o las aplicaciones de control de
plantas industriales. Este paradigma también puede ser utilizado para soportar
varias de las funciones del propio sistema de gestión de bases de datos, como
son: el control de accesos, el control de la integridad, el mantenimiento de vistas o
el mantenimiento de atributos derivados. El factor común en todas estas
aplicaciones es la necesidad de responder a sucesos, tanto externos como
internos al propio sistema. A diferencia de los sistemas pasivos, un sistema de
manejador de bases de datos activas responde automáticamente ante
determinadas circunstancias descritas por el diseñador. La mayoría de los
18
sistemas manejadores de bases de datos comerciales incorporan la posibilidad de
definir reglas, por lo que son, en cierto modo, sistemas activos.
Las investigaciones sobre la relación entre la teoría de las bases de datos y la
lógica se remontan a finales de la década de los setenta. Estas investigaciones
han dado lugar a las bases de datos deductivas, que permiten derivar nuevas
informaciones a partir de las introducidas explícitamente por el usuario. Esta
función deductiva se realiza mediante la adecuada explotación de ciertas reglas de
conocimiento relativas al dominio de la aplicación, utilizando para ello técnicas de
programación lógica y de inteligencia artificial.
Los sistemas de múltiples bases de datos permiten realizar operaciones que
implican a varios sistemas de bases de datos, cada uno de los cuales puede ser
centralizado o distribuido. Cada sistema de bases de datos que participa es
denominado componente. Si todos los sistemas manejadores de bases de datos
de los diferentes componentes son iguales, el sistema de múltiples bases de datos
es homogéneo; en caso contrario, es heterogéneo. Un sistema de múltiples bases
de datos es un sistema federado de bases de datos si permite una doble gestión:
una de carácter global, realizada por el sistema de gestión de bases de datos
federadas y otra en modo autónomo e independiente del sistema federado,
realizada por parte de los sistemas componentes.
La influencia de la Web lo abarca todo. En su desarrollo se han ignorado las
técnicas de bases de datos, por lo que se han repetido los errores cometidos en
las primeras generaciones de los sistemas maneadores de bases de datos. La
Web se puede ver como una nueva interfaz de acceso a bases de datos, y
muchos sistemas manejadores de bases de datos ya proporcionan
almacenamiento y acceso a datos a través de XML. Pero la Web puede también
ser considerada como una inmensa base de datos, siendo éste un tema de
investigación en pleno auge.
19
Por otra parte, los grandes almacenes de datos (data warehouses) ya han
demostrado que si son implementados convenientemente, pueden ser de gran
ayuda en la toma de decisiones y en el procesamiento analítico en tiempo real
OLAP (On-Line Analytical Processing ). Los datos son extraídos periódicamente
de otras fuentes y son integrados en el almacén. Estos datos, relevantes para la
empresa, son no-volátiles y se agrupan según diversas granularidades en el
tiempo y en otras dimensiones. En la actualidad, existe una gran competencia
entre las extensiones de los sistemas de gestión de bases de datos comerciales
para incorporar las características de este tipo de sistemas, y la creación de
productos específicos.
La explotación de datos (data mining o knowledge discovery in databases) trata de
escubrir conocimientos útiles y previamente no conocidos a partir de grandes
volúmenes de datos, por lo que no sólo integra técnicas de bases de datos, sino
también de estadística y de inteligencia artificial. Las investigaciones se han
plasmado rápidamente en productos comerciales, con un desarrollo reciente
bastante importante.
Existen también muchos trabajos de investigación en temas tales como las bases
de datos temporales y las bases de datos multimedia. Las bases de datos
temporales intentan, en primer lugar, definir un modelo de datos que capture la
semántica del tiempo en el mundo real, y, en segundo lugar, realizar una
implementación eficiente de tal modelo. Los recientes avances en el
almacenamiento de distintos tipos de información, como voz, imágenes o sonido,
han tenido su influencia en las bases de datos, dando lugar a las bases de datos
multimedia.
La rápida evolución que la tecnología de bases de datos ha experimentado en la
última década, así como la variedad de nuevos caminos abiertos, han conducido a
investigadores y asociaciones interesadas, a reflexionar sobre el futuro de esta
20
tecnología. Estas reflexiones quedan recogidas en numerosos debates y
manifiestos que intentan poner orden en un campo en continua expansión.
2.2 BASES DE DATOS
“La información puede ser cualquier cosa que sea de importancia para el individuo
o la organización; en otras palabras, todo lo que sea necesario para auxiliarle en el
proceso general de su administración [C.J. Date]”. Hoy en día las organizaciones
se han dado cuenta de lo importante y valioso que representa la información en su
forma de funcionar ya que esto permite evaluar sus procesos de desarrollo y
operación en la administración de la organización.
Una base de datos es un conjunto de datos almacenados en memoria externa que
están organizados mediante una estructura de datos. Cada base de datos ha sido
diseñada para satisfacer los requisitos de información de una empresa u otro tipo
de organización, como por ejemplo, una universidad o un hospital.
Antes de existir las bases de datos se trabajaba con sistemas de ficheros. Los
sistemas de ficheros surgieron al informatizar el manejo de los archivos manuales
para proporcionar un acceso más eficiente a los datos almacenados en los
mismos. Un sistema de ficheros sigue un modelo descentralizado, en el que cada
departamento de la empresa almacena y gestiona sus propios datos mediante una
serie de programas de aplicación escritos especialmente para él. Estos programas
son totalmente independientes entre un departamento y otro, y se utilizan para
introducir datos, mantener los ficheros y generar los informes que cada
departamento necesita. Es importante destacar que en los sistemas de ficheros,
tanto la estructura física de los ficheros de datos como la de sus registros, están
definidas dentro de los programas de aplicación.
21
Cuando en una empresa se trabaja con un sistema de ficheros, los departamentos
no comparten información ni aplicaciones, por lo que los datos comunes deben
estar duplicados en cada uno de ellos. Esto puede originar inconsistencias en los
datos. Se produce una inconsistencia cuando copias de los mismos datos no
coinciden: dos copias del domicilio de un cliente pueden no coincidir si sólo uno de
los departamentos que lo almacenan ha sido informado de que el domicilio ha
cambiado.
Otro inconveniente que plantean los sistemas de ficheros es que cuando los datos
se separan en distintos ficheros, es más complicado acceder a ellos, ya que el
programador de aplicaciones debe sincronizar el procesamiento de los distintos
ficheros implicados para garantizar que se extraen los datos correctos. Además,
ya que la estructura física de los datos se encuentra especificada en los
programas de aplicación, cualquier cambio en dicha estructura es difícil de
realizar. El programador debe identificar todos los programas afectados por el
cambio, modificarlos y volverlos a probar, lo que cuesta mucho tiempo y está
sujeto a que se produzcan errores. A este problema, tan característico de los
sistemas de ficheros, se le denomina también falta de independencia de datos
lógica-física.
Una base de datos se puede percibir como un gran almacén de datos que se
define y se crea una sola vez, y que se utiliza al mismo tiempo por distintos
usuarios. En una base de datos todos los datos se integran con una mínima
cantidad de duplicidad. De este modo, la base de datos no pertenece a un solo
departamento sino que se comparte por toda la organización. Además, la base de
datos no sólo contiene los datos de la organización, también almacena una
descripción de dichos datos. Esta descripción es lo que se denomina metadatos,
se almacena en el diccionario de datos o catálogo y es lo que permite que exista
independencia de datos lógica-física.
22
2.3 SISTEMA MANEJADOR DE BASES DE DATOS
El SMBD es una aplicación que permite a los usuarios definir, crear y mantener la
base de datos, además de proporcionar un acceso controlado a la misma. Se
denomina sistema de bases de datos al conjunto formado por la base de datos, el
SMBD y los programas de aplicación que dan servicio a la empresa u
organización. El modelo seguido con los sistemas de bases de datos es muy
similar al modelo que se sigue en la actualidad para el desarrollo de programas
con lenguajes orientados a objetos, en donde se da una implementación interna
de un objeto y una especificación externa separada. Los usuarios del objeto sólo
ven la especificación externa y no se deben preocupar de cómo se implementa
internamente el objeto.
Una ventaja de este modelo, conocido como abstracción de datos, es que se
puede cambiar la implementación interna de un objeto sin afectar a sus usuarios
ya que la especificación externa no se ve alterada. Del mismo modo, los sistemas
de bases de datos separan la definición de la estructura física de los datos de su
estructura lógica, y almacenan esta definición en la base de datos. Todo esto es
gracias a la existencia del SMBD, que se sitúa entre la base de datos y los
programas de aplicación.
Generalmente, un SMBD proporciona los servicios que se citan a continuación: El
SMBD permite la definición de la base de datos mediante un lenguaje de definición
de datos. Este lenguaje permite especificar la estructura y el tipo de los datos, así
como las restricciones sobre los datos.
El SMBD permite la inserción, actualización, eliminación y consulta de datos
mediante un lenguaje de manejo de datos. El hecho de disponer de un lenguaje
para realizar consultas reduce el problema de los sistemas de ficheros, en los que
el usuario tiene que trabajar con un conjunto fijo de consultas, o bien, dispone de
un gran número de programas de aplicación costosos de gestionar. Hay dos tipos
23
de lenguajes de manejo de datos: los procedurales y los no procedurales. Estos
dos tipos se distinguen por el modo en que acceden a los datos. Los lenguajes
procedurales manipulan la base de datos registro a registro, mientras que los no
procedurales operan sobre conjuntos de registros.
En los lenguajes procedurales se especifica qué operaciones se debe realizar para
obtener los datos resultado, mientras que en los lenguajes no procedurales se
especifica qué datos deben obtenerse sin decir cómo hacerlo. El lenguaje no
procedural más utilizado es el SQL (Structured Query Language) que, de hecho,
es un estándar y es el lenguaje de los SMBD relacionales.
El SMBD proporciona un acceso controlado a la base de datos mediante:
Un sistema de seguridad, de modo que los usuarios no autorizados no
puedan acceder a la base de datos.
Un sistema de integridad que mantiene la integridad y la consistencia de los
datos.
Un sistema de control de concurrencia que permite el acceso compartido a
la base de datos.
Un sistema de control de recuperación que restablece la base de datos
después de que se produzca un fallo del hardware o del software.
Un diccionario de datos o catálogo, accesible por el usuario, que contiene la
descripción de los datos de la base de datos.
A diferencia de los sistemas de ficheros, en los que los programas de aplicación
trabajan directamente sobre los ficheros de datos, el SMBD se ocupa de la
estructura física de los datos y de su almacenamiento. Con esta funcionalidad, el
24
SMBD se convierte en una herramienta de gran utilidad. Sin embargo, desde el
punto de vista del usuario, se podría discutir que los SMBD han hecho las cosas
más complicadas, ya que ahora los usuarios ven más datos de los que realmente
quieren o necesitan, puesto que ven la base de datos completa. Conscientes de
este problema, los SMBD proporcionan un mecanismo de vistas que permite que
cada usuario tenga su propia vista o visión de la base de datos. El lenguaje de
definición de datos permite definir vistas como subconjuntos de la base de datos.
Todos los SMBD no presentan la misma funcionalidad, depende de cada producto.
En general, los grandes SMBD multiusuario ofrecen todas las funciones que se
acaban de citar e incluso más. Los sistemas modernos son conjuntos de
programas extremadamente complejos y sofisticados, con millones de líneas de
código y con una documentación consistente en varios volúmenes. Lo que se
pretende es proporcionar un sistema que permita gestionar cualquier tipo de
requisitos y que tenga un 100 % de fiabilidad ante cualquier tipo de fallo. Los
SMBD están en continua evolución, tratando de satisfacer los requisitos de todo
tipo de usuarios. Por ejemplo, muchas aplicaciones de hoy en día necesitan
almacenar imágenes, vídeo, sonido, etc. Para satisfacer a este mercado, los
SMBD deben evolucionar. Conforme vaya pasando el tiempo, irán surgiendo
nuevos requisitos, por lo que los SMBD nunca permanecerán estáticos
2.4 MODELOS DE BASES DE DATOS
Al igual que cuando se habla, por ejemplo, de coches no existe un único modelo,
ni una sola marca, ni siquiera una sola tecnología sobre su funcionamiento,
cuando se trabaja con bases de datos ocurre una cosa parecida: no existe una
sola marca, sino varias, y además cada marca puede tener diferentes productos
cada uno de ellos apropiado a un tipo de necesidades.
Sin embargo, la división de las bases de datos son en función de tecnología
empleada en su funcionamiento. Hablando de coches tenemos los tradicionales de
25
motor a gasolina, los de gasóleo, los turbodiesel, los que funcionaban con
gasógeno, y mucho menos frecuentes los coches solares o incluso los de
propulsión a chorro; pues bien, hablando de bases de datos las más utilizadas son
la bases de datos relacionales, las más antiguas son las jerárquicas y en red, y las
más avanzadas son las orientadas a objetos, y las declarativas. Estas se
diferencian como hemos dicho, en la forma de trabajar con los datos y en la
concepción o mentalidad que el usuario debe adoptar para interactuar con el
sistema.
Al igual que en el caso de los coches, unos sistemas consumen más recursos que
otros, por ejemplo, los sistemas declarativos consumen tanta memoria y tiempo de
funcionamiento como queroseno un coche de propulsión a chorro; una base de
datos en red puede resultar tan penosa de manejar como un coche antiguo con
gasógeno. En el término medio podemos decir que lo más empleado actualmente
(aunque algunos pueden decir que lo más contaminante) es el sistema relacional,
al igual que los coches de gasolina o gasóleo.
Para describir cada uno de los modelos o paradigmas en que se basan las bases
de datos, se sigue un criterio histórico, estudiando primero los sistemas más
antiguos para pasar por último a los sistemas mas avanzados.
2.4.1 MODELO JERÁRQUICO
El sistema jerárquico más comúnmente conocido es el sistema IMS de IBM. Esta
base de datos tiene como objetivo establecer una jerarquía de tablas, de manera
que cada tabla puede contener a su vez listas de otras tablas, y así
sucesivamente. Por ejemplo una tabla de clientes puede contener una lista de
tablas de facturas, cada una de las cuales puede contener a su vez una lista de
tablas de líneas de detalle que describen los servicios facturados.
26
Una base de datos jerárquica está compuesta por una secuencia de bases de
datos físicas, de manera que cada base de datos física se compone de todas las
ocurrencias de un tipo de registro o tabla determinada. Una ocurrencia de registro
es una jerarquía de ocurrencias de segmento. Cada ocurrencia de segmento está
formada por un conjunto de ocurrencias o instancias de los campos que
componen el segmento.
La figura 4 se muestra una ocurrencia del tipo de registro Curso, de manera que
como cabeza principal se tiene una instancia del segmento curso, de la cual
dependen una o varias instancias de los segmentos Requisito y Oferta; a su vez,
de Oferta dependen otros que son Profesor y Estudiante.
Fig. 4 Ejemplo de tipo de registro, los tipos de segmento son CURSO, REQUISITO, OFERTA, PROFESOR, y ESTUDIANTE. curso es el tipo de segmento raíz.
Cabe distinguir en este punto entre el concepto de tipo de registro, y ocurrencia o
instancia de registro. El tipo define la estructura general que debe poseer, o sea,
los campos de cada uno de sus segmentos, y la estructura jerárquica entre ellos.
Una instancia es un valor de un tipo de registro.
De esta forma, al segmento que se halla a la cabeza de un registro, se le llama
segmento padre, y se llama segmentos hijo a los que dependen de él.
Para moverse por un registro de estructura jerárquica lo que se hace es
posicionarse inicialmente en la raíz de una instancia, e ir navegando por sus hijos
según nos convenga consultando o modificando los datos pertinentes.
27
Una base de datos de este tipo, no permite el acceso directo a las instancias de un
segmento hijo, si no es seleccionando previamente las instancias de los padres de
los que depende. Por ejemplo, no se puede seleccionar un estudiante si no es
previa selección de una oferta y de un curso.
Las instancias de un mismo segmento que dependen de una misma instancia
padre se llaman instancias gemelas.
Algunos de los problemas que se presentan en este modelo son :
La jerarquía existente entre los tipos de objetos que se manipulan (Cursos,
Estudiantes, Profesores, etc.), y las dependencias existentes, hacen que
sea imposible el acceso directo a instancias de cada una de ellos, con lo
que se pierde en independencia y facilidad de uso.
Si un mismo segmento debe participar en varios tipos de registro, deben
incluirse mecanismos que eviten la repetición de datos. Es más, en el
ejemplo anterior se ve que una instancia del segmento Profesor: 1 S.G.R.
aparece dependiendo de la oferta de la UNED, y de la UMA. Está claro que
los datos no se deben repetir, ya que ello puede provocar que
posteriormente se modifique una de las instancias pero no la otra, con la
consiguiente inconsistencia entre ambas copias de los mismos datos.
2.4.2 MODELO DE RED
Se puede considerar al modelo de bases de datos en red como de una potencia
intermedia entre el jerárquico y el relacional que se mencionara más adelante. Su
estructura es parecida a la jerárquica aunque bastante más compleja, con lo que
se consiguen evitar, al menos en parte, los problemas de aquél.
28
Los conceptos fundamentales que debe conocer el administrador para definir el
esquema de una base de datos jerárquica, son los siguientes:
Registro: Viene a ser como cada una de las fichas almacenadas en un
fichero convencional.
Campos o elementos de datos. Son cada uno de los apartados de que se
compone una ficha.
Conjunto: Es el concepto que permite relacionar entre sí tipos de registro
distintos.
Se puede imaginar los registros simplemente como fichas de un fichero. Para
ilustrar el concepto de conjunto, suponga que se tiene un tipo de registro de
clientes, y un tipo de registro de vuelos de avión, y supóngase que se quiere
asociar ambas informaciones, de manera que para cada vuelo se quiere saber
cuáles son los pasajeros que viajan en él. La forma de hacerlo es a través de un
conjunto. Un conjunto relaciona dos tipos de registro. Uno de ellos es el registro
propietario del conjunto, y el otro es el miembro. Véase el diagrama de la figura 5
siguiente que aclara las cosas un poco más. Son los diagramas de Bachman.
Una restricción bastante importante de este modelo, es que una ocurrencia de
registro miembro puede pertenecer como máximo a una sola instancia de un
determinado conjunto, aunque puede participar en varios tipos de conjuntos
distintos.
Este modelo en red es más potente que el modelo jerárquico, ya que aquél puede
simularse, aplicando una jerarquía de conjuntos en varios niveles.
29
Fig. 5 A la izquierda se puede observar el formato general de un conjunto, y a la derecha, el conjunto concreto que nos soluciona saber la lista de embarque de cada vuelo.
Por otro lado, en un conjunto concreto, el tipo de registro propietario no puede ser,
a su vez, el mismo que el tipo de registro miembro, o sea, un mismo tipo de
registro no puede intervenir en el mismo conjunto como propietario y como
miembro a la vez.
Para ilustrar por qué el modelo en red es más potente que el modelo jerárquico,
basta con observar un conjunto de la figura 5.
Fig. 5 Cómo simular el ejemplo jerárquico mediante el modelo en red.
Aquí, un elemento de A puede poseer varios de B, mediante el conjunto A-B; a su
vez, los de B pueden poseer a los de A, mediante B-A, y así sucesivamente
cuantas veces se quiera. Este ejemplo no se puede hacer en el modelo jerárquico,
pues el número de niveles varía dinámicamente.
30
Que una misma instancia de registro miembro no pueda aparecer en más de una
instancia de conjunto, hace que sea difícil de expresar algunas situaciones. Por
ejemplo, en el caso de las lista de embarque, está claro que no sólo cada vuelo lo
componen varios pasajeros, sino que, además, un mismo pasajero ha podido
embarcar en varios vuelos a lo largo de su vida. ¿Cómo representar esta
situación?
La solución a este problema es algo artificiosa, y pasa por la creación de tipos de
registro llamados enlaces. La figura 6 ilustra la solución.
Fig. 6 creación de tipos de registro llamados enlaces
Así, cada pasajero se relaciona con una lista de vuelos, que viene dada por una
serie de códigos, y cada vuelo se relaciona con una lista de pasajeros que vendrá
dada por otra serie de códigos.
2.4.3 MODELO RELACIONAL
Este modelo intenta representar la base de datos como un conjunto de tablas.
Aunque las tablas son un concepto simple e intuitivo, existe una correspondencia
directa entre el concepto informático de una tabla, y el concepto matemático de
relación, lo cual es una gran ventaja, pues permite efectuar formalizaciones de una
forma estricta mediante las herramientas matemáticas asociadas, como pueda ser
el álgebra relacional en el ámbito de las consultas.
31
Afortunadamente, no será necesario enfrentarse con todos estos formalismos
propios de los matemáticos, sino que se dispone de unas herramientas fáciles de
manejar que nos permitirán interactuar con la base de datos.
Los conceptos básicos del modelo relacional son:
Registro: Es algo así como cada ficha de un fichero convencional.
Tabla: Es un conjunto de fichas de un mismo tipo.
Con estos dos conceptos es posible crear cualquier tipo de datos, y asociarlos
entre sí, sin las restricciones propias del modelo jerárquico o en red. Por ejemplo,
si se necesita diseñar una base de datos para una agencia de alquiler de coches,
se necesitará una tabla en la que se guarde información sobre los coches, como
puede observarse en la figura 7.
Fig. 7 Ejemplo de tabla relacional.
De esta forma, se observa que cada tabla está compuesta por filas, también
llamadas tuplas o registros, cada uno de los cuales posee una serie de campos en
los que se almacenan los datos básicos. El esquema de una tabla nos indica los
nombres de cada uno de los campos que contiene, así como el tipo de información
32
que debe contener. Una tabla es un conjunto de registros; por tanto, los registros
no pueden repetirse.
Para poder acceder a un registro concreto, es necesario hacer una consulta a
través de algún campo que identifique a dicho registro, como puede ser, por
ejemplo, el número de la matrícula. A este campo especial que identifica cada
registro se le llama clave del registro. La figura 8 se ilustra una tabla de clientes.
Fig 8. Tabla de clientes de la agencia de alquiler de coches.
En el modelo anterior se disponía de los conjuntos para asociar información entre
sí; ¿cómo resolver para indicar ahora qué cliente se hace responsable de cada
coche alquilado? Fácilmente, a través de una nueva tabla que relaciona los
clientes con los coches. Para ello dado que cada registro queda identificado por su
clave, basta con incluir en esta nueva tabla a las claves de ambas tablas, en lugar
de todos sus campos. Así, se puede obtener una nueva tabla de alquileres que
contenga la matrícula del coche, y el Identificador del cliente.
Por otro lado, además de los modelos propios de base de datos existentes en la
realidad, existen los llamados modelos semánticos, que permiten expresar
relaciones entre los datos, independientemente del tipo de base de datos que se
emplee finalmente. Uno de estos modelos, el modelo Entidad-Relación tiene
grandes similitudes con el modelo relacional, siendo esta otra gran ventaja del
modelo relacional, esto es, se pueden expresar las relaciones entre los datos a
33
través de diagramas fáciles de comprender y de modificar, y, posteriormente,
pasar el resultado a un esquema relacional.
2.4.4. MODELOS AVANZADOS
Las bases de datos relacionales han sido y siguen siendo ampliamente utilizadas
para una extensa gama de aplicaciones. Sin embargo, el aumento de potencia de
las computadoras personales, ha hecho aparecer nuevas aplicaciones potentes
que requieren la utilización de datos complejamente relacionados o con
necesidades de consultas muy particulares, como puedan ser los sistemas de
información geográficos, el diseño de circuitos electrónicos por computadora, entre
otros.
Otro de los problemas que poseen los sistemas relacionales es el uso de los
lenguajes de manipulación y definición de datos, que, aunque son muy simples de
manejar directamente por un usuario, son difíciles de insertar en un lenguaje de
programación convencional, lo que da lugar a un problema de impedancia o
resistencia de un lenguaje a ser utilizado junto con otro.
Otros problemas se refieren a la inclusión del concepto de orden en los registros
almacenados. Dado que una tabla es un conjunto de registros, y un conjunto no
permite ni repeticiones de sus elementos, ni establece un orden entre ellos, es
imposible representar ciertas características de datos muy particulares.
Todos estos problemas han hecho que los investigadores estén buscando
alternativas fiables a las bases de datos relacionales, como puedan ser las
deductivas, las persistentes, las funcionales, o las orientadas a objetos, pasando
por una gama de bases de datos históricas, espaciales, entre otras.
Dos de ellas son las que están sufriendo mayor empuje por parte de la comunidad
informática. A continuación se describen.
34
2.4.4.1 MODELO ORIENTADO A OBJETOS
Actualmente, la creación de programas más grandes y complejos, ha hecho
avanzar los métodos de programación hacia nuevas formas que permiten el
trabajo en equipo de una forma más eficaz y en la que se disminuyen los
problemas de coordinación. Uno de estos métodos consiste en la Programación
Orientada a Objetos (POO), que trata los problemas desde un punto de vista
realista, y modelando cada uno de ellos como si se tratase de un conjunto de
elementos u objetos que interrelacionan entre sí para solucionar el problema.
Para entender mejor esta filosofía, se puede pensar en ella como en el
funcionamiento de un reloj de cuerda. Un reloj de cuerda posee numerosos
elementos que interactúan entre sí para obtener como resultado final una
determinada posición de las manecillas, que son interpretadas por una persona
como la hora actual. Cada uno de estos objetos es un elemento. Cuando un
engranaje, por ejemplo, gira, no lo hace por capricho, sino para obtener como
resultado el movimiento de otro engranaje, de una cremallera, o de la propia
manecilla. De esta forma, cuando el usuario da cuerda a la maquinaria, lo que está
haciendo realmente es modificar el estado de un objeto del reloj, normalmente la
espiral de la cuerda cuya energía potencial mueve la corona haciendo que un
oscilador avance el segundero. A su vez el movimiento del segundero hace
avanzar el del minutero, que hace avanzar el de la hora. Si el reloj es de cuco,
cada hora se activará la portezuela del cuco que saldrá un número determinado de
veces según la hora. De esta manera, una modificación del estado de un objeto
por parte de un usuario, desencadena una serie de acciones cuyo objetivo final es
solucionar un problema al usuario: darle a conocer la hora exacta. Así, la
programación orientada a objetos pretende ser una simulación de los procesos de
la realidad.
De este ejemplo se obtienen varios conceptos útiles:
35
Clase. Cuando hay varios objetos semejantes, pueden agruparse en una
clase. De hecho, todo objeto debe pertenecer a una clase, que define sus
características generales, por ejemplo el reloj posee varios engranajes.
Serán diferentes, puesto que cada uno de ellos posee un diámetro y un
número de dientes distinto, además de poder ser o no helicoidal. Pero al fin
y al cabo todos son engranajes. De esta manera cada engranaje pertenece
a la misma clase, a pesar de tener unas características particulares que lo
diferencian de los demás.
Estado. Son las características propias de cada objeto. Siguiendo con el
caso de los engranajes, su estado puede ser el número de dientes, el
tamaño, y algunos otros. El estado se utiliza especialmente para guardar la
situación del objeto que varía con el tiempo. En este caso se almacena la
situación en un espacio tridimensional, y la posición o postura en que se
encuentra.
Encapsulación. Cada objeto es consciente de sus propias características.
El engranaje «sabe» que si recibe una fuerza en uno de sus dientes, debe
girar, y lo sabe porque obedece a unas leyes físicas. En el caso de un
programa, es el programador el que debe indicarle al objeto cómo
comportarse ante cada estímulo del exterior o de otro objeto. Los demás
objetos simplemente se limitan a indicarle al engranaje las fuerzas que le
hacen, y ya sabrá el engranaje para dónde se ha de mover, y a qué otros
objetos modificar.
Mensaje. Es cada uno de los estímulos que se envían a un objeto.
Herencia. Para facilitar la programación, se puede establecer toda una
jerarquía de tipos o clases. Por ejemplo, podemos declarar una clase
Engranaje con las características básicas de los engranajes. De ella se
puede derivar otras tres: Eng. fijo, Cremallera, y Eng. helicoidal. Cada una
36
de estas clases especializa la clase general, con la ventaja de que las
características comunes a los tres tipos de engranajes sólo hay que decirlas
una vez.
El avance de la programación orientada a objetos ha llegado hasta los programas
de gestión y que requieren el uso de bases de datos. El problema surge en el
momento en que dos filosofías entran en conflicto: la filosofía orientada a objetos,
y la de la base de datos que se pretende usar, fundamentalmente relacional. El
conflicto principal es el problema de la impedancia, es decir, es difícil hacer
encajar una programación orientada a objetos con las consultas y accesos propios
de la base de datos, realizados en un lenguaje de manipulación y acceso a los
datos, lenguaje que suele ser de otro tipo, normalmente no procedural. Asimismo,
los datos retornados por la base de datos están en un formato incomprensible
para el lenguaje orientado a objetos, por lo que es necesario un paso de
conversión que haga inteligibles esos datos.
Una solución factible a este problema consiste en hacer bases de datos cuyo
sistema manejador tenga una interfaz orientada a objetos. Cuando se habla de
interfaz se refiere a que tenga una capacidad tal que los programas sean capaces
de interactuar con él según la filosofía orientada a objetos. Esta solución puede
ser aproximada, a su vez, según varios métodos:
Extender el modelo relacional. Consiste en añadir a una base de datos
relacional la posibilidad de hacer cosas orientadas a objeto.
Modelo de objetos persistentes. Consiste en declarar cierto tipo de objetos
com persistentes. Un objeto es persistente si queremos que se guarde en la
base de datos.
Modelo integrado semántico. Añade también ciertas capacidades de
consulta sin necesidad de programación externa
37
Fig. 9. Esquema de clases para almacenar información sobre coches.
De estos métodos el más empleado actualmente es el de objetos persistentes, ya
que es el que mejor se adecúa a la metodología de programación orientada a
objetos.
El esquema de la figura ilustra la estructura que podría tener la clase Coche. De
esta forma, cada objeto de tipo Coche que se maneja, será almacenado
automáticamente en la base de datos si se declara como objeto persistente. Se
observa que un objeto Coche puede ser, a su vez, un Turismo, un Camión o un
Remolque; un Turismo puede ser Monovolumen o Deportivo. Dependiendo del
lenguaje que se emplee, podremos tener objetos que sean simplemente Turismos
sin necesidad de pertenecer a Monovolumen o a Deportivo, o sea, se pueden
tener tanto objetos de clases finales como de clases intermedias. Nótese que con
esta metodología, se va describiendo un objeto como integrado por otros más
pequeños, llegando al nivel de refinamiento que la solución de del problema
requiera. Aquí se indica que un Turismo o un Camión posee un Motor, y a
continuación se describen las características de un motor. Nótese que el campo
38
Motor no se especifica en la clase Coche, ya que también consideramos que un
Remolque es un Coche y éstos carecen de Motor.
Este tipo de esquemas define una jerarquía desde dos puntos de vista. Por un
lado especifica un refinamiento en cuanto a conceptos: Un Deportivo es un
refinamiento de un Turismo, que a su vez es un refinamiento de un Coche. Así,
podemos decir que todo Turismo es un Coche, y que todo Deportivo es un
Turismo, pero en ningún caso que todo Coche es un Deportivo, ya que hay casos
de Coches, como por ejemplo, Remolques, que no son Deportivos, ni siquiera
Turismos. Así, existe una jerarquía en base a la especialización o generalización
(según se vea) de los objetos del problema. Hay casos, como el de las Ruedas, en
los que no es necesaria especialización alguna.
La otra jerarquía es la jerarquía de composición. Cada objeto está compuesto de
campos, que pueden ser, a su vez, otros objetos. Por ejemplo, se aprecia que un
Deportivo posee campos que indican sus características particulares: su número
de plazas, si viene con maletas especialmente diseñadas a la forma del maletero,
y el nivel de ruido del motor. Pero, además, por el hecho de ser un Turismo,
también posee otra información, tal como el color y si dispone de airbag o no; por
otro lado los campos Rueda y Motor, son, a su vez, objetos, cada uno de ellos con
sus características propias. Esta jerarquía supone un refinamiento en cuanto a las
características de cada objeto.
Estas dos jerarquías conjuntas dan una gran potencia a la programación orientada
a objetos. Desde el punto de vista de una base de datos, los datos se almacenan
de una forma parecida al sistema relacional, de manera que existirá una tabla por
cada clase o subclase de nuestro esquema. Quizás la única diferencia sustancial
es que cada objeto tiene asignado automáticamente un número (OID- Object
Identifier) que sirve para poder ser referenciado por los objetos de los que forma
parte. El concepto de OID sustituye, en parte, al de clave en el sistema relacional.
39
2.4.4.2 MODELO DECLARATIVO El enfoque de las bases de datos declarativas es sumamente intuitivo para el
usuario, y le permite abstraerse de los problemas de programación inherentes a
otros métodos. Este modelo suele usarse para bases de conocimiento, que no son
más que bases de datos con mecanismos de consulta en los que el trabajo de
extracción de información a partir de los datos recae en realidad sobre la
computadora, en lugar de sobre el usuario. Estos mecanismos de consulta exigen
que la información se halle distribuida de manera que haga eficiente las
búsquedas de los datos, ya que normalmente las consultas de este tipo requieren
acceder una y otra vez a los datos en busca de patrones que se adecúen a las
características de los datos que ha solicitado el usuario. Sin embargo, no se
hablará de la organización de los datos, sino sólo de las formas de las consultas.
Antes de comenzar, se aclara que, cuando se vea el lenguaje SQL sobre las
bases de datos relacionales, se dirá que este es un lenguaje no procedural, en el
sentido de que el usuario especifica qué es lo que quiere, pero no cómo. No se
debe confundir este aspecto del SQL con un lenguaje puramente declarativo, ya
que éstos, amplían la filosofía de la base de datos, de manera que el usuario no
es consciente de los métodos de búsqueda que se realizan internamente, y la
forma en que se manejan los datos también es muy distinta; además, en el caso
de las funcionales, es necesario complicar soberanamente los métodos utilizados
si se quiere mantener la pureza de la metodología funcional. Además, la teoría
que subyace en ambos modelos difiere radicalmente.
Entre las bases de datos declarativas se puede citar fundamentalmente dos: las
deductivas, y las funcionales. Ambas extienden paradigmas o métodos de
programación (al igual que ocurre con la programación orientada a objetos) a las
bases de datos, de manera que ambos, programa y base de datos puedan
cooperar más eficientemente en la resolución del problema.
40
Las bases de datos funcionales extienden el modelo de programación funcional,
que se basa especialmente en el concepto de transparencia referencial. Este
concepto viene a indicar que todo objeto computacional se debe comportar como
una función, de manera que ante las mismas entradas responde siempre con la
misma salida. Este hecho, puede no ser cierto en otros paradigmas,
especialmente el orientado a objetos, en el que la salida de un objeto no depende
sólo de sus entradas, sino también del estado interno en el que se hallaba. Así, el
modelo funcional elimina el concepto de estado.
Sin embargo, una base de datos, identifica precisamente el estado de los datos
que la empresa necesita o posee en un momento determinado. Dado que bases
de datos y estados tienen una relación bastante directa, es difícil hacerla encajar
con el modelo funcional. Por ello, no se mencionará en este trabajo de tesis, y se
continuará con el siguiente modelo: las bases de datos deductivas.
Una base de datos deductiva puede ser considerada también como integrada por
un conjunto de tablas. Sin embargo, desde un punto de vista dado, varía
esencialmente. A veces es necesario ver una misma cosa (un problema, una
situación, etc.) desde distintos puntos de vista, ya que ello ayuda a compararlo con
distintas cosas que ya conocemos y permite adoptar soluciones que, de otra
forma, serían difíciles de comprender. Algo así ocurre con las bases de datos
deductivas. Aquí una tabla no se considera como un conjunto de tuplas, sino como
un conjunto de hechos de un tipo concreto. De hecho, una base de datos
deductiva, pretende deducir qué hechos son ciertos o no, y en qué circunstancias.
Toda la base de datos gira en torno a esa filosofía.
2.5 ARQUITECTURA DE BASES DE DATOS
Las bases de datos en la actualidad son muy importantes debido a que en ellas se
almacena gran información de suma importancia. La evolución a pasos
agigantados de los sistemas de cómputo, también ha permitido el gran desarrollo
41
en diferentes arquitecturas de las bases de datos, algunas con mas ventajas que
otras de acuerdo al uso que se les da, de acuerdo a la solución de diferentes
problemas que se desean resolver, en el entendido que, debe de existir una
relación directa entre el sistema de cómputo y la arquitectura de base de datos.
A continuación se describen las arquitecturas de bases de datos existentes.
2.5.1 ARQUITECTURA CENTRALIZADA
Una base de datos centralizada es aquella que está totalmente en un solo lugar
físico, es decir, está almacenada en una sola máquina y en una sola CPU, en la
cual los usuarios trabajan en terminales que solo muestran resultados.
Los sistemas de bases de datos centralizadas son aquellos que se ejecutan en un
único sistema informático sin interactuar con ninguna otra computadora. Tales
sistemas van desde los sistemas de bases de datos mono usuarios ejecutándose
en computadoras personales hasta los sistemas de bases de datos de alto
rendimiento encuitándose en grandes sistemas. En la figura 11 se muestra la
arquitectura típica de las bases de datos centralizadas.
Fig. 10. Arquitectura típica de una base de datos centralizada.
42
2.5.1.1 CARACTERÍSTICAS DE LAS BASES DE DATOS
CENTRALIZADAS.
Se almacena completamente en una localidad central.
No posee múltiples elementos de procesamiento ni mecanismos de
intercomunicación como las bases de datos distribuidas.
Los componentes de las bases de datos centralizadas son: los datos, el
software de gestión de bases de datos y los dispositivos de
almacenamiento secundario asociados.
El problema de seguridad es fácil de manejar en estos sistemas de bases
de datos.
2.5.1.2 VENTAJAS DE LAS BASES DE DATOS CENTRALIZADAS
Se evita la redundancia.
Se evita la inconsistencia.
Pueden aplicarse restricciones de seguridad.
Puede conservarse la integridad.
El procesamiento de los datos ofrece un mejor rendimiento y resulta más
confiable que los sistemas distribuidos.
2.5.1.3 DESVENTAJAS DE LAS BASES DE DATOS CENTRALIZADAS
Si el sistema de base de datos falla, se pierde la disponibilidad y
procesamiento de la información que posee el sistema.
Difícil sincronización para su recuperación.
Las cargas de trabajo no se pueden difundir entre varias computadoras.
2.5.2 ARQUITECTURA CLIENTE / SERVIDOR
Un servidor es una aplicación que ofrece un servicio a los usuarios de Internet; un
cliente es el que solicita ese servicio.
43
Una aplicación está compuesta por dos partes: una de servidor y la otra de cliente,
estos se pueden ejecutar en el mismo sistema o en diferentes. Los usuarios
utilizan la parte del cliente y envían su solicitud al servidor de la aplicación.
El servidor recibe una solicitud, realiza el servicio requerido y devuelve los
resultados en forma de una respuesta. Generalmente un servidor puede tratar
múltiples peticiones al mismo tiempo.
Algunos servidores esperan las solicitudes en puertos bien conocidos de modo
que sus clientes saben a dónde deben dirigir sus peticiones. Los clientes que se
quieren comunicar con un servidor que no usa un puerto bien conocido tienen otro
mecanismo para saber a qué puerto dirigirse.
Los sistemas Cliente/Servidor se desarrollaron inicialmente para conseguir un
rendimiento considerablemente superior con un aumento moderado del precio,
pasando parte del procesamiento de la parte del cliente al servidor. De esta forma
puede mejorar el rendimiento, pero apenas afecta al costo. En la figura 12 se
muestra la arquitectura cliente / servidor.
Fig. 11. Arquitectura típica de una base de datos cliente / servidor
44
2.5.2.1 DESVENTAJAS DE LAS BASES DE DATOS CLIENTE /
SERVIDOR
Alojan los costos por función en lugar de hacerlo por las actividades que lo
generan.
Los costos en los que se incurren durante la planeación, diseño y prototipos
que se deben realizar son muy caros.
2.5.2.2 VENTAJAS DE LAS BASES DE DATOS CLIENTE / SERVIDOR
Costos. Utilizar la arquitectura cliente/servidor es económico.
Fácil acceso a la información.
Buena interfaz gráfica.
Buena tecnología en el lugar adecuado.
Permite separar módulos específicos
2.5.3. ARQUITECTURA PARALELA
De forma general el concepto de paralelismo en las bases de datos se podría
definir como la partición de la base de datos (normalmente a nivel de relaciones)
para poder procesar de forma paralela en distintos discos y con distintos
procesadores una sola operación sobre la base de datos.
El paralelismo se usa para mejorar la velocidad en la ejecución de consultas.
Además el paralelismo se usa para proporcionar dimensionabilidad ya que la
creciente carga de trabajo se trata sin incrementar el tiempo de respuesta pero
incrementando el grado de paralelismo.
Existen cuatro arquitecturas de sistemas paralelos:
45
De memoria compartida: Todos los procesadores comparten una memoria
común.
De discos compartidos: Todos los procesadores comparten un conjunto de
discos común.
Sin compartimiento: Los procesadores no comparten ni memoria ni disco.
Jerárquica: Este modelo es un híbrido de las arquitecturas anteriores.
Un SMBD que se ejecuta sobre múltiples procesadores y discos que han sido
diseñados para ejecutar operaciones en paralelo, cuando sea posible, con el
propósito de mejorar el rendimiento.
Los sistemas paralelos mejoran la velocidad de procesamiento y de E/S mediante
la utilización de UCP y discos en paralelo. La fuerza que ha impulsado a los
sistemas paralelos de bases de datos ha sido la demanda de aplicaciones que han
de manejar bases de datos extremadamente grandes (del orden de terabytes, esto
es, 1012 bytes) o que tienen que procesar un número enorme de transacciones
por segundo (del orden de miles de transacciones por segundo).
Los sistemas paralelos de base de datos constan de varios procesadores y varios
discos conectados a través de una red de interconexión de alta velocidad. Para
medir el rendimiento de los sistemas de base de datos existen 2 medidas
principales:
La productividad (throughput) que se entiende como el número de tareas
que pueden completarse en un intervalo de tiempo determinado.
El tiempo de respuesta (response time) que es la cantidad de tiempo que
necesita para completar una única tarea a partir del momento en que se
envíe. Un sistema que procese un gran número de pequeñas transacciones
puede mejorar su productividad realizando muchas transacciones en
paralelo. Un sistema que procese transacciones más largas puede mejorar
46
tanto su productividad como sus tiempos de respuesta realizando en
paralelo cada una de las subtareas de cada transacción.
De forma general se puede hablar de paralelismo de E/S cuando se habla de
divisiones en las relaciones entre varios discos para reducir el tiempo necesario de
su recuperación.
Normalmente la división más común en un entorno de bases de datos paralelas es
la división horizontal. En este tipo de división las tuplas de cada relación se dividen
entre varios discos de modo que cada tupla resida en un disco distinto.
Suponiendo que tenemos n discos (D0,D1,…,Dn) entre los que se van a dividir los
datos, existen varias estrategias de división:
Turno rotatorio: Se recorre la relación y la i-ésima tupla se envía al disco Di
quedando una distribución homogénea de las tuplas en los discos.
División por asociación: Se escogen varios atributos del esquema de la
relación y se designan como atributos de división. Se escoge una función
de asociación cuyo rango es {0,1,…,n-1}. Cada tupla de la relación original
se asocia en términos de los atributos de división. Si la función de
asociación devuelve i, la tupla de ubica en el disco DI.
División por rangos: Se distribuye rangos contiguos de valores de los
atributos a cada disco. Para ello se escoge un atributo de división, AD,
como vector de división y la relación se divide de la siguiente manera:
Sea [vo, v1, …, vn-2] el vector de división con i<j y vi<vj.
Considérese una tupla t
tal que t[A]=x.
47
Si x< vo entonces t se ubica en el disco Do.
Si x≥vn-2 entonces t se ubica en el disco Dn-1.
Si vi≤x < vi+1 entonces t se ubica en el disco DI+1
Cuando ya se ha dividido una relación en varios discos se puede recuperar en
paralelo utilizándolos todos de la misma manera que se puede escribir en paralelo
cuando se está dividiendo una relación. Por lo tanto, cuando se quiera leer (o
escribir) la relación completa se ganrá tiempo gracias al paralelismo. Además de
leer de forma completa una relación existen otro tipo de lecturas o consultas:
Exploración de la relación completa: Ya mencionada
Consultas concretas: Buscan tuplas con un determinado valor para un
atributo concreto.
Consultas de rango: Buscan tuplas con un valor que esté dentro de un
rango para un atributo concreto.
Las técnicas de división explicadas permiten estos tipos de acceso pero con
diferentes niveles de eficacia:
Turno rotatorio: Se adapta bien a la exploración completa pero no es
eficiente para consultas concretas y de rango ya que tiene que buscar en
todos los discos.
División por asociación: Este esquema se adapta bien a las consultas
concretas basadas en el atributo de división ya que dirigimos la consulta al
disco que se nos indica la función de asociación para el atributo y el valor
del mismo. También se adapta bien a una exploración completa si la
48
función de asociación reparte bien las tuplas en los discos. Sin embargo no
es adecuada esta técnica para consultas concretas cuando el atributo de
búsqueda no coincide con el atributo de división.
División por rangos: Se adapta bien a las consultas concretas y de rango
basadas en el atributo de división. Para consultas concretas se debe
analizar el vector de división para ver en que disco está la tupla al igual que
para una consulta de rango se consulta el vector de división para ver en
que rango de discos están las tuplas.
2.5.3.1 PARALELISMO ENTRE CONSULTAS
Los sistemas de bases de datos con arquitectura paralela deben asegurar de que
dos procesadores no actualicen simultáneamente los mismos datos de manera
independiente.
Cuando un procesador accede a los datos o los actualiza, el sistema de bases de
datos debe garantizar que tenga su última versión en la memoria intermedia. El
problema de asegurar que la versión sea la última disponible se denomina
problema de coherencia de cache.
Existen una serie de protocolos para garantizar la coherencia de cache, que
normalmente se integran con los de control de concurrencia para reducir la
sobrecarga.
Los protocolos de este tipo de sistemas de disco compartido son los siguientes:
Antes de cualquier acceso de lectura o escritura de una página, la
transacción la bloquea en modo compartido o excluso, según corresponda.
Inmediatamente después de obtener el bloqueo compartido o exclusivo de
49
la página, la transacción lee también su copia más reciente del disco
compartido.
Antes de que una transacción libere el bloqueo exclusivo de una página, la
traslada al disco compartido, posteriormente libera el bloqueo.
Con este protocolo se garantiza que cuando una transacción establece un bloqueo
compartido o exclusivo sobre una página, obtenga la copia correcta de la página.
2.5.3.2 PARALELISMO EN CONSULTAS
Es la ejecución en paralelo de una única consulta entre varios procesadores y
discos, cuyo objetivo es acelerar las consultas de ejecución prologada. Por tanto
se puede hacer paralelas las consultas haciendo paralelas las operaciones que las
forman. Existen dos maneras de ejecutar en paralelo una sola consulta:
Paralelismo en operaciones. Se puede acelerar el procesamiento de las
consulta haciendo paralela la ejecución de cada una de sus operaciones
individuales ordenación, selección, proyección y reunión.
Paralelismo entre Operaciones. Se puede acelerar el procesamiento de la
consulta ejecutando en paralelo las diferentes operaciones de las
expresiones de las consultas.
Por lo tanto el objetivo que se persigue es dividir la relación que interviene en la
consulta por medio de técnicas de división de relaciones, guardar dichas
relaciones en discos que van a ser gestionados cada uno de ellos por un
procesador, a su vez, cada procesador ejecuta su consulta local y cada uno de
estos resultados parciales se unen para formar la respuesta a la consulta.
2.5.3.2 PARALELISMO EN OPERACIONES
50
Ya que las operaciones relacionales trabajan con relaciones que contienen
grandes conjuntos de tuplas, las operaciones se pueden paralelizar ejecutándolas
sobre subconjuntos diferentes de las relaciones en paralelo. Según el tipo de
operación se siguen distintos criterios en el tratamiento que son:
Ordenación Paralela
Reunión Paralela.
2.5.3.2.1 ORDENACIÓN PARALELA
Dependiendo del criterio en la división de la relación se pueden distinguir dos tipos
de ordenación:
Ordenación división de Rangos. Esta forma de división por rangos posee dos
etapas diferenciadas:
1. Redistribuir las tuplas de la relación utilizando una estrategia de división por
rangos, de manera que todas las tuplas que se hallen dentro del rango i-
ésimo se envíen al procesador Pi, que almacena temporalmente la relación
en el disco Di. Para implementar en paralelo la división por rangos cada
procesador lee las tuplas de su disco y las envía al procesador de destino.
Cada procesador P0,P1…Pn también recibe las tuplas correspondientes a
su partición y las almacena localmente.
2. Cada uno de los procesadores ordena localmente su partición de la relación
sin interactuar con los demás. La operación final de mezcla es trivial ya que
la división por rangos de la primera etapa asegura que los valores de la
clave del procesador Pi sean menores que los procesador Pj
51
Ordenación y mezcla externa paralela. Este tipo de ordenación es una alternativa
a la efectuada por la división por rangos. Las etapas que se definen una vez que la
relación se ha divida entre los diferentes discos D1,D2…Dn-a son las siguientes:
Cada procesador Pi ordena localmente los datos del disco Di
El sistema mezcla las partes ordenadas por cada procesador para obtener
el resultado ordenado final.
A su vez el paso en el que el sistema realiza la mezcla puede ser también
paralelizado mediante la siguiente secuencia de acciones.
1. El sistema divide en rangos las particiones ordenadas encada procesador
Pi entre los procesadores P0,P1…Pn-1. Envía las tuplas de acuerdo con el
orden establecido por lo que cada procesador recibe las tuplas en
corrientes ordenadas.
2. Cada procesador Pi, realiza una mezcla de las corrientes según las recibe
para obtener una sola parte ordenada.
3. Las partes ordenadas de los procesadores P0,P1… Pn-1 se concatenan
para obtener el resultado final.
2.5.3.2.2 REUNIÓN PARALELA
La operación reunión exige que el sistema compare pares de tuplas para ver si
satisface la condición de reunión, si la cumple añade el par al resultado de la
reunión. Los algoritmos de reunión paralela intentan repartir entre varios
procesadores los pares que hay que comparar.
52
Cada procesador procesa luego localmente parte de la reunión. Después, el
sistema reúne los resultados de cada procesador para producir el resultado final.
Reunión por División, Válida para reuniones de tipo equirreuniones y reuniones
naturales, en la cual existen n procesadores y las relaciones que hay que reunir
son r y s. La reunión por división funciona de esta forma:
El sistema divide las relaciones r y s en n particiones r0,r1,…rn-1 y
s0,s1,…sn-1
Envía las particiones ri y si al procesador Pi, donde la reunión se procesa
localmente.
Reunión con fragmentos y replicas, Proporcionan una alternativa para las
reuniones que no puede ser procesada por la técnica de reunión por división,
como por ejemplo si la condición de reunión es una desigualdad. En este tipo de
reuniones pueden paralelizarse utilizando una técnica denominada fragmentos y
replicas, cuyo funcionamiento es el siguiente.
1. El sistema divide una de las relaciones (por ejemplo s) mediante cualquier
técnica de división, incluida por turno rotatorio.
2. El sistema replica la otra relación r en todos los procesadores
3. El procesador Pi procesa localmente la reunión de ri con todos, utilizando
cualquier técnica de reunión.
Reunión por asociación dividida en paralelo, es la reunión por asociación realizada
en cada procesador es independiente de las realizadas en otros procesadores, y
recibir las tuplas de ri y de si es parecido a leerlas del disco. En concreto, se
puede utilizar el algoritmo híbrido de reunión por asociación para guardar en caché
53
algunas de las tuplas de entrada, y evitar así los costos de escribirlas y volver a
leerlas.
2.5.3.2 FACTORES NEGATIVOS DEL PARALELISMO
Estos pueden atenuar tanto la ganancia de velocidad como la ampliabilidad:
Costos de inicio. El inicio de un único proceso lleva asociado un costo de
inicio.
Interferencia. Como los procesos que se ejecutan en un sistema paralelo
acceden con frecuencia a recursos compartidos, pueden sufrir un cierto
retardo como consecuencia de esta.
Sesgo. Al dividir cada tarea en un cierto número de pasos paralelos se
reduce el tamaño del paso medio. Normalmente es difícil dividir una tarea
en partes exactamente iguales, entonces se dice que la forma de
distribución de los tamaños es sesgada.
2.5.4. ARQUITECTURA DISTRIBUIDA
La arquitectura de base de datos distribuida es otra de las arquitecturas. Solo se
menciona en esta apartado, ya que, se ahondará más en ellas, pues es el tema
central de este proyecto de tesis.
CAPÍTULO 3. BASES DE DATOS DISTRIBUIDAS
En el presente capítulo se mostrará la arquitectura general de un sistema de
bases de datos distribuida, así como, una descripción acerca de los componentes
de las bases de datos distribuidas.
54
La arquitectura define la estructura de un sistema. Al definir la arquitectura se
deben identificar las componentes de un sistema, las funciones que realiza cada
una de los componentes y las interrelaciones e interacciones entre cada
componente.
3.1 INTRODUCCIÓN
Los sistemas de información empezaron a utilizar las bases de datos distribuidas
aproximadamente a mediados de la década de los 70’s, pero no fue sino hasta
1980 cuando la distribución de la información empezó a tomar auge.
Originalmente se había pensado en almacenar la información de manera
centralizada utilizando un conjunto de herramientas que facilitarán este tipo de
almacenamiento. Pero con el paso del tiempo esto produjo ciertos inconvenientes
que no eran posibles solucionar. Estos problemas impulsaron la creación de
almacenamiento distribuido, los cuales hoy en día proveen características
indispensables en el manejo de información; es decir, la combinación de las redes
de comunicación y las bases de datos.
En años más recientes se ha observado una marcada tendencia hacia la
distribución de los sistemas de cómputo en múltiples sitios que se interconectan a
través de una red de comunicaciones. La cantidad de innovaciones tecnológicas
que ha habido ha promovido un cambio en la forma de observar a los sistemas de
información y, en general, a las aplicaciones computacionales.
Existen avances tecnológicos que se realizan continuamente en circuitos,
dispositivos de almacenamiento, programas y metodologías. Sin embargo, los
cambios tecnológicos van de la mano con la demanda de los usuarios y
programas para la explotación exhaustiva de tales dispositivos mejorados. Por
tanto, existe un continuo desarrollo de nuevos productos los cuales incorporan
ideas nuevas desarrolladas por compañías e instituciones académicas.
55
Aun cuando es posible que un usuario común no perciba los desarrollos
relevantes de nuevos productos, para las aplicaciones existe una demanda
permanente por mayor funcionalidad, mayor número de servicios, más flexibilidad
y mejor rendimiento. Así, al diseñar un nuevo sistema de información o al
prolongar la vida de uno ya existente, se debe buscar siempre formas para enlazar
las soluciones ofrecidas por la tecnología disponible a las necesidades de las
aplicaciones de los usuarios.
Un área en la cual las soluciones están integrando tecnología con nuevas
arquitecturas o formas de hacer las cosas es, sin lugar a dudas, el área de los
sistemas distribuidos de información. Ellos se refieren al manejo de datos
almacenados en facilidades de cómputo localizadas en muchos sitios ligados a
través de una red de comunicaciones. Un caso específico de estos sistemas
distribuidos es lo que se conoce como bases de datos distribuidas.
3.2 CONCEPTOS BÁSICOS
Una Base de Datos Distribuida (BDD) es un conjunto de múltiples bases de datos
lógicamente relacionadas las cuales se encuentran distribuidas entre diferentes
sitios interconectados por una red de comunicaciones, los cuales tienen la
capacidad de procesamiento autónomo lo cual indica que puede realizar
operaciones locales o distribuidas.
Un sistema de Bases de Datos Distribuida (SBDD) es un sistema en el cual
múltiples sitios de bases de datos están ligados por un sistema de comunicaciones
de tal forma que, un usuario en cualquier sitio puede acceder los datos en
cualquier parte de la red exactamente como si los datos estuvieran.
En un sistema distribuido de bases de datos se almacenan en varias
computadoras. Los principales factores que distinguen un SBDD de un sistema
centralizado son los siguientes:
56
Hay múltiples computadoras, llamados sitios o nodos.
Estos sitios deben de estar comunicados por medio de algún tipo de red de
comunicaciones para transmitir datos y órdenes entre los sitios.
3.2.1 CARACTERÍSTICAS DE LAS BASES DE DATOS DISTRIBUIDAS
Las características de las bases de las bases de datos son las siguientes:
1. Autonomía Local: Los sitios distribuidos deben ser autónomos, es decir que
todas las operaciones en un sitio dado se controlan en ese sitio.
2. No dependencia de un sitio central: No debe de haber dependencia de un
sitio central para obtener un servicio.
3. Operación Continua: Nunca debería apagarse para que se pueda realizar
alguna función, como añadir un nuevo sitio.
4. Independencia con respecto a la localización: No debe de ser necesario
que los usuarios sepan dónde están almacenados físicamente los datos,
sino que más el usuario lo debe de ver como si solo existiera un sitio local.
5. Independencia con respecto a la fragmentación: La fragmentación es
deseable por razones de desempeño, los datos, pueden almacenarse en la
localidad donde se utilizan con mayor frecuencia de manera que la mayor
parte de las operaciones sean sólo locales y se reduzca el tráfico en la red.
6. Independencia de réplica: Si una relación dada (es decir, un fragmento
dado de una relación) se puede presentar en el nivel físico mediante varias
copias almacenadas o réplicas, en muchos sitios distintos.
57
7. Procesamiento Distribuido de Consultas: El objetivo es convertir
transacciones de usuario en instrucciones para manipulación de datos, y
así reducir el tráfico en la red implica que el proceso mismo de optimización
de consultas debe ser distribuido.
8. Manejo Distribuido de Transacciones: Tiene dos aspectos principales, el
control de recuperación y el control de concurrencia, cada uno de los cuales
requiere un tratamiento más amplio en el ambiente distribuido.
3.3 SISTEMAS DE BASES DE DATOS DISTRIBUIDAS
Una base de datos distribuida es una colección de múltiples bases de datos
lógicamente interrelacionadas sobre una red de computadoras. Un Sistema
Manejador de Bases de Datos Distribuidas se define como el sistema de software
que permite la gestión de una base de datos distribuida y hace transparente la
distribución. Frecuentemente el término Sistema de Bases de Datos Distribuidas
(SBDD) es utilizado para referirse a los Sistemas Manejadores de Bases de Datos
Distribuidas. Para ambos términos, los conceptos de interrelación lógica y de
distribución sobre una red de computadoras juegan un papel importante que
ayuda a definir los Sistemas de Bases de Datos Distribuidas y descartar algunos
casos donde se aceptan algunas propuestas como tales.
Fig. 12. Ejemplo de base de datos distribuida.
58
Un SBDD es una colección de archivos almacenados individualmente en cada
nodo de la red. Estos archivos, además de tener una relación lógica, deben contar
con una estructura y proveer un acceso mediante una interfaz común. Existen en
la actualidad muchos sistemas que poseen funcionalidades de los SMBD y
trabajan sobre datos semi-estructurados, almacenados en archivos sobre el
internet. Es importante distinguir entre un SBDD que cumple con las restricciones
mencionadas y los sistemas distribuidos de manejo de datos que proveen acceso
a datos de la misma tratando de emular los SMBD. También se asume que la
distribución física de los datos no es el problema más importante en estos
enfoques, tomando como una Base de Datos Distribuida a un conjunto de bases
de datos relacionadas que residen en un computador. Sin embargo, la distribución
de los datos en los distintos nodos trae como consecuencia problemas que no se
encuentran al tener múltiples bases de datos en un sólo computador. Por ejemplo,
los datos pueden estar duplicados en un ambiente distribuido, por lo que la BDD
debe estar diseñada de manera que la base de datos entera o partes de esta sean
fragmentadas y distribuidas a través de una red de computadoras, trayendo como
consecuencia que deba tomarse en cuenta cuál es la versión de los datos que
debe accederse en cada lectura y cómo deben realizarse los cambios en los
distintos nodos al momento de una modificación. Este inconveniente, entre otros
como los relacionados a las fallas de la red de computadoras y la sincronización
de transacciones entre los distintos nodos, presentan una complejidad y retos que
sólo se encuentran en los sistemas de bases de datos distribuidos.
El hecho de que exista una distribución física entre los nodos no implica
necesariamente que estos estén geográficamente distantes, es decir, que pueden
estar en el mismo cuarto. La distribución implica simplemente que la comunicación
entre estos nodos deba hacerse por medio de una red de computadoras como
único recurso compartido, en vez de realizarse a través de sistemas de memoria o
disco compartido (como los vistos en sistemas multiprocesadores). Esto sugiere
que los sistemas de bases de datos multiprocesadores no sean considerados
SBDDs. La diferencia entre estos reside en el modo de operación. El diseño de un
59
sistema multiprocesador, consiste comúnmente de un conjunto de procesadores y
elementos de memoria idénticos, controlado por una o más copias del mismo
sistema operativo, que lleva un control estricto de las tareas asignadas. Esto es
totalmente distinto en los sistemas distribuidos, donde la heterogeneidad del
sistema operativo así como de los componentes de hardware es bastante común.
Los sistemas de bases de datos que corren sobre sistemas multiprocesadores son
llamados bases de datos paralelas.
A pesar de la presencia de una red, en los sistemas de bases de datos
distribuidas, las bases de datos no residen sólo en un nodo de la red. En este
caso, los problemas de gestión de datos no son distintos a los vistos en los
ambientes de bases de datos centralizados (las bases de datos cliente/servidor
son un ejemplo de estos sistemas, donde existe un nodo que gestiona la base de
datos de manera centralizada).
En resumen, la existencia de redes computadoras o de una colección de archivos
no es suficiente para formar un sistema de bases de datos distribuidas.
Fundamentalmente, el interés se enfoca a un ambiente donde los datos están
distribuidos en distintos nodos de una red.
3.4 VENTAJAS DE LAS BASES DE DATOS DISTRIBUIDAS
La administración de bases de datos distribuidas ha sido propuesta por varias
razones que van desde la centralización organizativa y el procesamiento
económico y autónomo. A continuación, se describen algunas de las ventajas de
estos sistemas.
3.4.1 ADMINISTRACIÓN DE DATOS DISTRIBUIDOS CON DISTINTOS
NIVELES DE TRANSPARENCIA
60
De manera ideal, un DBMS debe ser una distribución transparente en el sentido
de abstraer al usuario de detalles de localización física de los archivos dentro del
sistema. Por ejemplo, una tabla puede estar fragmentada en conjunto de filas y
replicada en distintos nodos ubicados en lugares geográficamente distintos. En
este caso, son posibles los siguientes tipos de transparencias:
Transparencia de distribución o red: hace referencia a la autonomía del
usuario de los detalles operacionales de la red. Puede dividirse en
transparencia de localización y de denominación. La transparencia de
localización menciona el hecho de que un comando usado para llevar a
cabo una tarea es independiente de la ubicación de los datos y del sistema
desde el que se ejecutó dicho comando. La transparencia de denominación
implica que una vez especificado un nombre, puede accederse a los
objetos nombrados sin ambigüedad y sin necesidad de ninguna
especificación adicional.
Transparencia de replicación: pueden almacenarse copias de los datos en
distintos lugares para disponer de una mayor disponibilidad, rendimiento y
fiabilidad. La transparencia de replicación permite al usuario abstraerse de
las réplicas existentes.
Transparencia de Fragmentación: existen dos tipos de fragmentación, la
fragmentación horizontal que distribuye una relación en conjuntos de tuplas,
mientras que la vertical lo hace en subrelaciones, donde cada relación está
definida por un subconjunto de las columnas de la relación individual.
Debido a esto, una consulta podría ser transformada en distintas
subconsultas fragmentadas. La transparencia de fragmentación abstrae al
usuario de la existencia de los fragmentos.
61
Transparencia de diseño y ejecución: hacen referencia a la abstracción del usuario
de saber cómo está diseñada la base de datos distribuida y dónde ejecuta una
transacción.
Todas estas formas de transparencia proveen un acceso fácil y eficiente a los
distintos usuarios (especialmente a los usuarios inexpertos). Sin embargo, cumplir
con un completo nivel de transparencia representa un conflicto entre la facilidad de
uso y la dificultad y costo de procesamiento inherente. Se discute que la
transparencia total en un SMBDD hace la gestión de las bases de datos
distribuidas pobres en los aspectos de manejabilidad, modularidad y desempeño
en el envío de mensajes [Gray89]. Estas discusiones han llevado a la
implementación de enfoques como los descritos en las arquitecturas cliente
servidor y a la identificación de capas correspondiente a los distintos servicios de
transparencia que pueden proveerse.
La primera capa provee acceso transparente a los recursos de datos y se conoce
como capa de acceso. Las características de transparencia se construyen en un
lenguaje de usuario, quien traduce los servicios requeridos en operaciones. En
otras palabras, el compilador o intérprete toma la tarea sin que el implementador
sea provisto por algún servicio de transparencia. La segunda capa de
transparencia se conoce como capa de nivel de sistema operativo, implementando
la misma transparencia conocida en la definición de sistemas operativos,
permitiendo acceder a recursos de hardware y software abstrayendo al usuario de
la complejidad inherente a estas operaciones. Este nivel puede extenderse a los
ambientes distribuidos, donde la gestión de la red puede ser llevada a cabo por el
sistema operativo distribuido o el middleware, si el SMBDD está implementado
sobre uno. Este enfoque conlleva problemas como la posibilidad de que el sistema
distribuido no posea un nivel de transparencia frente al uso de la red razonable y
la necesidad de las aplicaciones de conocer los elementos que son encapsulados
para su uso en tareas de optimización y desempeño. Finalmente se tienen la capa
del SMBD y la capa de lenguaje. En la capa de SMBD se proveen algunas
62
primitivas del SMBD para realizar ciertas tareas, dejando al SMBD como
responsable de la traducción desde el sistema operativo a interfaces de usuario de
alto nivel. La capa de transparencia del lenguaje permite el acceso a datos
mediante distintos lenguajes de alto nivel como lenguaje.
3.4.2 INCREMENTO DE LA FIABILIDAD Y LA DISPONIBILIDAD
Consideradas las más importantes de las ventajas de las bases de datos
distribuidas. La fiabilidad está definida ampliamente como la probabilidad de que
un sistema esté funcionando en un instante de tiempo cualquiera, mientras que la
disponibilidad es la probabilidad de que el sistema esté continuamente disponible
durante un intervalo de tiempo. Cuando un nodo del SMBD falla, sólo no estarán
disponibles los datos y el software almacenado en ese nodo, mientras que el resto
del sistema continúa operativo. Se logra una mejora en estas dos características al
mantener réplicas de datos en más de una ubicación. En un sistema centralizado,
el fallo de la ubicación provoca la caída del sistema para todos. En una base de
datos distribuida, parte de la información puede estar inaccesible, pero sí se
podría acceder a la parte de la base de datos almacenada en los demás nodos.
3.4.3 MEJORAS EN EL RENDIMIENTO
Un SMBDD fragmenta la base de datos manteniendo la información lo más cerca
posible del punto donde es más necesaria. La localización de datos reduce el
enfrentamiento en la asignación de CPU y los dispositivos de E/S.
3.4.4 FACILIDAD EN LA ESCALABILIDAD
En un entorno distribuido, la escalabilidad en términos de manejo de una mayor
cantidad de datos, el incremento de las bases de datos o la adición de más
procesadores es mucho más sencilla.
63
Junto a estas ventajas, Date propone 12 reglas fundamentales [Dat01] que deben
cumplir los SBDD, que exponen características de transparencia, fiabilidad,
disponibilidad y escalabilidad. Estas reglas, en su mayoría no son independientes
entre sí y tampoco son igualmente importantes para el conjunto total de usuarios
finales de un Sistema de Bases de Datos Distribuidas.
3.5 VENTAJAS DE LAS BASES DE DATOS DISTRIBUIDAS
Como cualquier arquitectura e inclusive tipo de base de datos y, evidentemente,
dependiendo a la problemática que se le quiera dar solución, ofrecen ventajas
significativas. A continuación se mencionar y describen algunas de las ventajas
más significativas de las bases de datos distribuidas.
3.5.1 PROCESAMIENTO DE CONSULTAS
Se trata de diseñar algoritmos que analizan las consultas y las convierten en
operación de manipulación de datos. El problema es cómo decidir qué estrategia
utilizar al ejecutar cualquier consulta sobre la red de la manera menos costosa y
efectiva.
Los factores a considerar son la distribución de los datos, los costos de
comunicación y la falta de información suficiente que esté localmente disponible.
El objetivo es optimizar el paralelismo implícito para mejorar el desempeño de la
ejecución de la transacción, tomando en cuenta los factores mencionados. Este
problema es de naturaleza NP-Completo y los enfoques utilizados normalmente
utilizan técnicas heurísticas.
3.5.2 ADMINISTRACIÓN DEL CATÁLOGO
El catálogo contiene información como la descripción y localización de los
elementos de la base de datos. Los problemas relacionados a la gestión del
64
catálogo se basan en cómo las bases de datos y las aplicaciones se ejecutan y
cómo deben colocarse a través de los sitios. Un directorio puede ser:
1. Centralizado: el catálogo total es almacenado exactamente una vez en un
sitio central.
2. Completamente replicado: el catálogo es almacenado por completo en cada
uno de los sitios.
3. Dividido: cada sitio mantiene su propio catálogo de los objetos que están
almacenados en ese sitio. El catálogo total es la unión de todos los
catálogos locales disjuntos.
4. Centralizado y dividido: cada sitio mantiene su propio catálogo local,
además, un único sitio central mantiene una copia unificada de todos esos
catálogos locales.
3.5.3 PROPAGACIÓN DE ACTUALIZACIÓN
Un problema básico que existe con la replicación de datos es que una
actualización a cualquier objeto lógico dado debe ser propagada a todas las
copias almacenadas a ese objeto.
Una dificultad inmediata es que un sitio que mantiene una copia del objeto podría
no estar disponible (debido a una falla del sitio o de la red) en el momento de la
actualización. Un esquema común para atacar este problema (aunque no es el
único posible) es el llamado esquema de copia primaria que funciona de la
siguiente manera:
1. A una copia de cada objeto replicado se le designa como copia primaria.
Todas las demás son copias secundarias.
65
2. Las copias primarias de diferentes objetos están en diferentes sitios (por lo
tanto, este es nuevamente un esquema distribuido).
3. Decimos que las operaciones de actualización quedaron lógicamente
terminadas tan pronto como se actualizó la copia primaria. Entonces, el sitio
que mantiene esa copia es responsable de la propagación de la
actualización hacia las copias secundarias en algún tiempo subsecuente
(Ese tiempo subsecuente, debe ser previo al COMMIT, si es que se van a
conservar las propiedades ACID de la transacción).
3.5.4 CONTROL DE CONCURRENCIA
En la mayoría de los sistemas distribuidos (al igual que en la mayoría de los
sistemas centralizados) el control de concurrencia se basa en el bloqueo [Dat01].
Sin embargo, en un sistema distribuido, las solicitudes para probar, colocar y
liberal bloqueos se convierten en mensajes (suponiendo que el objeto en
consideración está en un sitio remoto) y los mensajes significan una sobrecarga.
Por ejemplo, si una transacción T que necesita actualizar un objeto para el cual
existen réplicas en n sitios remotos. Si cada sitio es responsable de los bloqueos
por los objetos que están almacenados en ese sitio (como sucedería si existe
autonomía local), entonces una implementación directa requerirá al menos 5n
mensajes (n solicitudes de bloqueo, n otorgamientos de bloqueo, n mensajes de
actualización, n notificaciones, n solicitudes de desbloqueo). Por supuesto,
podemos resolver esto fácilmente si solapamos los mensajes (por ejemplo, es
posible cambiar los mensajes de solicitud de bloqueo y los de actualización, así
como los mensajes de garantía de bloqueo y los de notificación), pero aun así se
tendría un tiempo total varias veces mayor en comparación con un sistema
centralizado. El enfoque usual es el de adoptar la estrategia de copia primaria,
utilizada al abordar el problema de propagación de actualización. Para un objeto
dado A, el sitio que mantiene la copia primaria manejará todas las operaciones de
bloqueo que involucren a ese A. Bajo esta estrategia, el conjunto de todas las
66
copias de un objeto puede ser considerado como un sólo objeto para efectos de
bloqueo, y la cantidad total de mensajes se reduce de 5n a 2n + 3 (una solicitud de
bloqueo, una garantía de bloqueo, n actualizaciones, n notificaciones y una
solicitud de desbloqueo). Observemos que esta solución implica una perdida
valiosa de la autonomía; si una copia no está disponible, la transacción puede
fallar aun cuando sea de sólo lectura. Por lo tanto, un efecto colateral del uso de
esta técnica es la reducción del rendimiento y de la disponibilidad para las
recuperaciones y actualizaciones. Otro problema con el bloqueo en un sistema
distribuido es el que puede conducir a un abrazo mortal global. Un abrazo o
bloqueo mortal global es aquél que involucra a dos o más sitios. Por ejemplo:
El agente de una transacción T2 en un sitio X está esperando al agente de
la transacción T1 del sitio X para que libere el bloqueo.
El agente de una transacción T1 en el sitio X está esperando a que termine
el agente de una transacción T1 en el sitio Y.
El agente de la transacción T1 en el sitio Y está esperando que el agente
de la transacción T2 en el sitio Y libere un bloqueo.
El agente de la transacción T2 en el sitio Y está esperando que termine el
agente de la transacción T2 en el sitio X. Aquí sucede el abrazo mortal.
La especificación de la arquitectura R* [WDH+82] cuenta con soluciones elegantes
y distribuidas para detectar abrazos mortales globales. En esta arquitectura
también se implementan soluciones basadas en temporizadores para la
prevención de estas situaciones.
3.6 ARQUITECTURA DE UNA BASE DE DATOS DISTRIBUIDA
67
La arquitectura de un sistema define su estructura, tomando en cuenta
componentes identificados, la función de cada uno de estos, su interrelación e
interacción entre sí. La especificación de la arquitectura de un sistema, requiere
identificación de los modelos, interfaces y relaciones, tomando en cuenta los datos
y el flujo de control a través de este.
A continuación, se presenta (ver figura 14) el conocido modelo de arquitectura
ANSI-SPARC y las posibles alternativas para su implementación en un SBDD.
Esto nos permitirá establecer relaciones entre este y los distintos modelos de
arquitectura.
Fig 13. Arquitectura ANSI/SPARC
En 1972, un grupo de estudios establecido por el Comité de Computadoras y
Procesamiento de Información (X3) del ANSI, patrocinado por el Comité de
Panificación de Estándares y Requerimientos (SPARC) estudió la factibilidad de
establecer estándares en el área de la gestión de bases de datos, así como
determinar cuáles aspectos era conveniente establecer dichos estándares. Así
surgió en 1977 el reporte final con un marco de trabajo propuesto que luego se
conoció como la “Arquitectura ANSI/SPARC”. Una versión simplificada de la
arquitectura es ampliamente estudiada en el área y consiste de tres capas o
niveles de datos: la capa externa o el nivel de vistas, que interactúa con el usuario,
la capa interna relacionada con el nivel físico y la interacción con el computador y
un nivel conceptual o empresarial.
68
En la arquitectura ANSI/SPARC (Fig 14), el nivel más bajo es la capa interna, que
maneja la definición física y la organización de los datos: localización de los datos
en los distintos dispositivos de almacenamiento y los mecanismos de acceso
utilizados para acceder y manipular datos.
Por otro lado, el nivel externo se encarga de cómo son presentados los datos y
cómo el usuario ve la base de datos; el uso de vistas individuales que representan
la porción de la base de datos que pueda ser accedida por un usuario en
particular. Estas vistas pueden ser compartidas por distintos grupos de usuarios,
conformando así un esquema externo. Entre estos dos niveles se encuentra el
esquema conceptual, el cual es una abstracción de la definición de la base de
datos, viene siendo la vista o el concepto que se tiene de la base de datos, el
modelo de la base de datos enfocada a un contexto o empresa en particular. En
teoría, el nivel conceptual permite suponer algunos aspectos de la representación
y las relaciones entre los datos sin considerar los requerimientos de aplicaciones
en particular o las restricciones del medio de almacenamiento físico. Sin embargo,
estos aspectos son importantes en la práctica y deben ser considerados para
evitar problemas de desempeño. La definición de uno de estos esquemas puede
ser descrito a partir de un mapeo de la especificación del esquema anterior.
Este enfoque es importante, ya que nos permite evidenciar los conceptos básicos
de la independencia de datos. La separación entre los esquemas externos y el
nivel conceptual provee una independencia lógica de los datos, mientras que la
separación entre el nivel conceptual y físico permiten mantener la independencia
física de datos.
3.7 DISEÑO DE LA DISTRIBUCIÓN
Existen diversas formas de afrontar el problema del diseño de la distribución. Las
más usuales se muestran en la figura 15. En el primer caso, caso A, los dos
procesos fundamentales, la fragmentación y la asignación, se abordan de forma
69
simultánea. Esta metodología se encuentra en desuso, sustituida por el enfoque
en dos fases, caso B: la realización primeramente de la partición para luego
asignar los fragmentos generados. El resto de los casos se comentan en el punto
3.
Antes de exponer las alternativas existentes de fragmentación, se desean
presentar las ventajas e inconvenientes de esta técnica. Se ha comentado en la
introducción la conveniencia de descomponer las relaciones de la base de datos
en pequeños fragmentos, pero no se ha justificado el hecho ni se han aportado
razones para efectuarlo. Por ello, desde este punto se va a intentar aportar las
razones necesarias para llevar a cabo esa descomposición, esa fragmentación.
Fig. 14. Distintos enfoques para diseñar la distribución
70
El principal problema de la fragmentación radica en encontrar la unidad apropiada
de distribución. Una relación no es una buena unidad por muchas razones.
Primero, las vistas de la aplicación normalmente son subconjuntos de relaciones.
Además, la localidad de los accesos de las aplicaciones no está definida sobre
relaciones enteras pero sí sobre subconjuntos de las mismas. Por ello, sería
normal considerar como unidad de distribución a estos subconjuntos de
relaciones.
Segundo, si las aplicaciones tienen vistas definidas sobre una determinada
relación (considerándola ahora una unidad de distribución) que reside en varios
sitios de la red, se puede optar por dos alternativas. Por un lado, la relación no
estará replicada y se almacena en un único sitio, o existe réplica en todos o
algunos de los sitios en los cuales reside la aplicación. Las consecuencias de esta
estrategia son la generación de un volumen de accesos remotos innecesario.
Además, se pueden realizar réplicas innecesarias que causen problemas en la
ejecución de las actualizaciones y puede no ser deseable si el espacio de
almacenamiento está limitado.
Tercero, la descomposición de una relación en fragmentos, tratados cada uno de
ellos como una unidad de distribución, permite el proceso concurrente de las
transacciones. También la relación de estas relaciones, normalmente, provocará la
ejecución paralela de una consulta al dividirla en una serie de subconsultas que
operará sobre los fragmentos.
Pero la fragmentación también acarrea inconvenientes. Si las aplicaciones tienen
requisitos tales que prevengan la descomposición de la relación en fragmentos
mutuamente exclusivos, estas aplicaciones cuyas vistas estén definidas sobre
más de un fragmento pueden sufrir una degradación en el rendimiento. Por tanto,
puede ser necesario recuperar los datos de dos fragmentos y llevar a cabo sobre
ellos operación de unión y yunto , lo cual es costoso.
71
Un segundo problema se refiere al control semántico. Como resultado de la
fragmentación los atributos implicados en una dependencia se descomponen en
diferentes fragmentos los cuales pueden destinarse a sitios diferentes. En este
caso, la sencilla tarea de verificar las dependencias puede resultar una tarea de
búsqueda de los datos implicados en un gran número de sitios.
CAPÍTULO 4. FRAGMENTACIÓN
Fragmentación es la descomposición o partición de una tabla en pedazos
llamados fragmentos. El problema de fragmentación se refiere al particionamiento
de la información para distribuir cada parte a los diferentes sitios de la red.
El objetivo de la fragmentación consiste en dividir la relación en un conjunto de
relaciones más pequeñas tal que algunas de las aplicaciones de usuario sólo
hagan uso de un fragmento. Sobre este marco, una fragmentación óptima es
aquella que produce un esquema de división que minimiza el tiempo de ejecución
de las aplicaciones que emplean esos fragmentos. La unidad de fragmentación
ideal no es la tabla sino una subdivisión de ésta.
4.1. TIPOS DE FRAGMENTACIÓN
Dado que una relación se corresponde esencialmente con una tabla y la cuestión
consiste en dividirla en fragmentos menores, inmediatamente surgen dos
alternativas lógicas para llevar a cabo el proceso: la división horizontal y la división
vertical. La división o fragmentación horizontal trabaja sobre las tuplas, dividiendo
la relación en subrelaciones que contienen un subconjunto de las tuplas que
alberga la primera. La fragmentación vertical, en cambio, se basa en los atributos
de la relación para efectuar la división. Estos dos tipos de partición podrían
considerarse los fundamentales y básicos. Sin embargo, existen otras alternativas.
Fundamentalmente, se habla de fragmentación mixta o híbrida cuando el proceso
de partición hace uso de los dos tipos anteriores. La fragmentación mixta puede
72
llevarse a cabo de tres formas diferentes: desarrollando primero la fragmentación
vertical y, posteriormente, aplicando la partición horizontal sobre los fragmentos
verticales (denominada partición VH), o aplicando primero una división horizontal
para luego, sobre los fragmentos generados, desarrollar una fragmentación
vertical (llamada partición HV), o bien, de forma directa considerando la semántica
de las transacciones. Otro enfoque distinto y relativamente nuevo, consiste en
aplicar sobre una relación, de forma simultánea y no secuencial, la fragmentación
horizontal y la fragmentación vertical; en este caso, se generara una rejilla y los
fragmentos formaran las celdas de esa rejilla, cada celda será exactamente un
fragmento vertical y un fragmento horizontal.
En la figura 3, puede observarse como los casos C y D se basan en la
mencionada generación de la rejilla, con la diferencia que en el primero de ellos se
produce una fusión, una desfragmentación de las celdas, agrupándolas de la
manera más adecuada para obtener mayor rendimiento, ya que los fragmentos
generados son muy pequeños. En el segundo caso se asignan las celdas a los
sitios y luego se realiza una rigurosa optimización de cada sitio. El caso E sería
aquel en el que se utiliza la fragmentación VH o la fragmentación HV.
4.1.2 GRADO DE FRAGMENTACIÓN
Cuando se va a fragmentar una base de datos se debería de considerar qué grado
de fragmentación va a alcanzar, ya que éste será un factor que influirá
notablemente en el desarrollo de la ejecución de las consultas. El grado de
fragmentación puede variar desde una ausencia de la división, considerando a las
relaciones unidades de fragmentación; o bien, fragmentar a un grado en cada
tupla o atributo forme un fragmento. Ante estos dos casos extremos,
evidentemente se ha de buscar un compromiso intermedio, el cual debería
establecerse sobre las características de las aplicaciones que hacen uso de la
base de datos. Dichas características se podrán formalizar en una serie de
73
parámetros. De acuerdo con sus valores, se podrá establecer el grado de
fragmentación del banco de datos.
Fig. 15. Distintos tipos de fragmentación
4.1.3 REGLAS DE CORRECCIÓN DE LA FRAGMENTACIÓN
A continuación se enuncian las tres reglas que se han de cumplir durante el
proceso de fragmentación, las cuales asegurarán la ausencia de cambios
semánticos en la base de datos durante el proceso.
1. Compleción. Si una relación R se descompone en una serie de fragmentos
R1, R R2,..., Rn, cada elemento de datos que pueda encontrarse en R
deberá poder encontrarse en uno o varios fragmentos Ri. Esta propiedad
extremadamente importante asegura que los datos de la relación global se
proyectan sobre los fragmentos sin pérdida alguna. Tenga en cuenta que
en el caso horizontal el elemento de datos, normalmente, es una tupla,
mientras que en el caso vertical es un atributo.
74
2. Reconstrucción. Si una relación R se descompone en una serie de
fragmentos R1, R2, ..., Rn, puede definirse una operador relacional tal que
R = Ri, Ri FR
El operador será diferente dependiendo de las diferentes formas de
fragmentación. La reconstrucción de la relación a partir de sus fragmentos
asegura la preservación de las restricciones definidas sobre los datos en
forma de dependencias.
3. Disyunción. Si una relación R se descompone horizontalmente en una
serie de fragmentos R1, R2,..., Rn, y un elemento de datos di se encuentra
en algún fragmento Rj, entonces no se encuentra en otro fragmento Rk (k
j). Esta regla asegura que los fragmentos horizontales sean disjuntos. Si
una relación R se descompone verticalmente, sus atributos primarios clave
normalmente se repiten en todos sus fragmentos.
4.1.4 ALTERNATIVAS DE ASIGNACIÓN
Partiendo del supuesto que el banco de datos se haya fragmentado
correctamente, habrá que decidir sobre la manera de asignar los fragmentos a los
distintos sitios de la red. Cuando una serie de datos se asignan, éstos pueden
replicarse para mantener una copia. Las razones para la réplica giran en torno a la
seguridad y a la eficiencia de las consultas de lectura. Si existen muchas
reproducciones de un elemento de datos, en caso de fallo en el sistema se podría
acceder a esos datos ubicados en sitios distintos. Además, las consultas que
acceden a los mismos datos pueden ejecutarse en paralelo, ya que habrá copias
en diferentes sitios. Por otra parte, la ejecución de consultas de actualización, de
escritura, implicaría la actualización de todas las copias que existan en la red,
cuyo proceso puede resultar problemático y complicado. Por tanto, un buen
parámetro para afrontar el grado de réplica consistiría en sopesar la cantidad de
75
consultas de lectura que se efectuarán, así como el número de consultas de
escritura que se llevarán a cabo. En una red donde las consultas que se procesen
sean mayoritariamente de lectura, se podría alcanzar un alto grado de réplica, no
así en el caso contrario. Una base de datos fragmentada es aquella donde no
existe réplica alguna. Los fragmentos se alojan en sitios donde únicamente existe
una copia de cada uno de ellos a lo largo de toda la red. En caso de réplica,
podemos considerar una base de datos totalmente replicada, donde existe una
copia de todo el banco de datos en cada sitio, o considerar una base de datos
parcialmente replicada donde existan copias de los fragmentos ubicados en
diferentes sitios. El número de copias de un fragmento será una de las posibles
entradas a los algoritmos de asignación, o una variable de decisión cuyo valor lo
determine el algoritmo. La figura 17 compara las tres alternativas de réplica con
respecto a distintas funciones de un sistema de base de datos distribuido.
RÉPLICA
TOTAL
RÉPLICA
PARCIAL PARTICIÓN
PROCESAMIENTO
DE CONSULTAS fácil dificultad similar
GESTIÓN DEL
DIRECTORIO
fácil o
inexistente dificultad similar
CONTROL DE
CONCURRENCIA moderado difícil fácil
SEGURIDAD
muy alta alta baja
REALIDAD posible
aplicación realista
posible
aplicación
Fig. 16. Comparación de las alternativas de réplica
4.1.5 INFORMACIÓN NECESARIA
Un aspecto importante en el diseño de la distribución es la cantidad de factores
que contribuyen a un diseño óptimo. La organización lógica de la base de datos, la
localización de las aplicaciones, las características de acceso de las aplicaciones
a la base de datos y las características del sistema en cada sitio, tienen una
decisiva influencia sobre la distribución. La información necesaria para el diseño
76
de la distribución puede dividirse en cuatro categorías: la información del banco de
datos, la información de la aplicación, la información sobre la red de computadoras
y la información sobre las computadoras en sí. Las dos últimas son de carácter
cuantitativo y servirán, principalmente, para desarrollar el proceso de asignación.
Se entrará en detalle sobre la información empleada cuando se aborden los
distintos algoritmos de fragmentación y asignación.
4.2. FRAGMENTACIÓN
A continuación se procederá a la descripción detallada de las dos estrategias de
fragmentación fundamentales: la horizontal y la vertical, y en este mismo sentido
la fragmentación mixta.
4.2.1 FRAGMENTACIÓN HORIZONTAL
Como se ha explicada anteriormente, la fragmentación horizontal se realiza sobre
las tuplas de la relación. Cada fragmento será un subconjunto de las tuplas de la
relación. Existen dos variantes de la fragmentación horizontal: la primaria y la
derivada. La fragmentación horizontal primaria de una relación se desarrolla
empleando los predicados definidos en esa relación. Por el contrario, la
fragmentación horizontal derivada consiste en dividir una relación partiendo de los
predicados definidos sobre alguna otra.
INFORMACIÓN NECESARIA PARA LA FRAGMENTACIÓN HORIZONTAL
Esta información implica al esquema conceptual global. Es importante
señalar cómo las relaciones de la base de datos se conectan con otras. En
una conexión de relaciones normalmente se denomina relación propietaria
a aquella situada en la cola del enlace, mientras que se llama relación
miembro a la ubicada en la cabecera del vínculo. Dicho de otra forma se
puede pensar en relaciones de Información sobre la base de datos. Origen
77
cuando se refiera a las propietarias y relaciones destino cuando se haga
con las miembro. Se definirán dos funciones: propietaria y miembro, las
cuales proyectarán un conjunto de enlaces sobre un conjunto de relaciones.
Además, dado un enlace, devolverán el miembro y el propietario de la
relación, respectivamente. La información cuantitativa necesaria gira en
torno a la cardinalidad de cada relación, notada como card(R).
Información sobre la aplicación. Se necesitará tanto información cualitativa
como cuantitativa. La información cualitativa guiará la fragmentación,
mientras que la cuantitativa se necesitará en los modelos de asignación. La
principal información de carácter cualitativo son los predicados empleados
en las consultas de usuario. Si no fuese posible investigar todas las
aplicaciones para determinar estos predicados, al menos se deberían
investigar las más importantes. Se pudiera pensar en la regla “80/20” para
guiarse en este análisis, esta regla dice que el 20% de las consultas
existentes acceden al 80% de los datos. Llegados a este punto, sería
interesante determinar los predicados simples. Dada una relación R(A1, A2,
..., An), donde Ai es un atributo definido sobre el dominio Di, un predicado
simple pj definido sobre R es de la forma
pj : Ai Valor
donde es un operador relacional y Valor se escoge de entre el dominio de
Ai. Se usará Pri para notar al conjunto de todos los predicados simples
definidos sobre una relación Ri. Los miembros de Pri se notan por pij.
Ejemplo 1. Para la relación ESTADO de la figura 18, un par de predicados simples
serían los siguientes:
CNOMPROV = “Sinaloa”
NCODED0 25
78
CLIENTES CCODCLI CNOMCLI CDIRCLI CPOBCLI NCODEDO CPTLCLI ID_UNICO 1 250101 Jorge Rodríguez C/ Castillo 56 Navojoa 13 13300 52904214-H 2 250102 José López C/ Angosta 123 Culiacán 37 37210 46737436-E 3 250103 Antonio Amigo C/ Colombia 4 Tepic 37 37007 54375933-U 4 250104 Juan Hernández Avda. Europa 3 Puebla 24 24001 78908942-I 5 250105 Joan Pujals C/ Espanya 34 Oaxtepec 08 08010 43251852-L 6 250106 Carmen Adrián C/ Castilla 59 Tuxpán 45 45002 76337464-D 7 250107 Susana García C/ Fillol 97 Mérida 49 49005 43563578-O 8 250108 Julián Anguita C/ América 34 Parral 5 05006 93265927-R 9 250109 José Aznar C/ Moncloa 14 Hermosillo 28 28001 74358737-A
Relación CLIENTES
ESTADO NCODEDO CNOMEDO CCODZONA ALBCLIT NNUMALB DFECALB CCODCLI 1 13 Sonora SON 1 980003 23/05/1998 250104 2 37 Sinaloa SIN 2 980004 14/09/1998 250104 3 24 Nayarit NAY 3 980002 09/04/1998 250102 4 08 Puebla PUE 4 980001 01/02/1998 250103 5 45 Morelos MOR 5 990001 20/03/1999 250108 6 49 Veracruz VER 6 990002 26/03/1999 250108 7 5 Yucatán YUC 7 990003 29/03/1999 250108 8 28 Chihuahua CHIH 8 990004 04/03/1999 250108
Relación ESTADO 9 990005 21/03/1999 250107 10 990006 10/04/1999 250109
Relación ALBCLIT
ALBCLIL NNUMALB CREF CDETALLE NPREUNID NIVA 1 980003 960 Cortina Estampada 2x3 3500 16 2 980004 990 Cortina Lisa Blanca 2x3 3300 16 3 980002 450 Edredón 1,80 Azul 5600 16 4 980001 460 Edredón 1,80 Rosa 5600 16 5 990001 120 Almohada 1,20 1500 16 6 990002 160 Almohada 1,60 1800 16 7 990003 450 Edredón 1,80 Azul 5600 16 8 990004 420 Edredón 1,80 Blanco 5600 16 9 990005 960 Cortina Estampada 2x3 3500 16
10 990006 980 Cortina Lisa Azul 2x3 3300 16 Relación ALBCLIL
Fig. 17. Las relaciones de la base de datos empleadas para el desarrollo de los ejemplos
A parte de los predicados simples, las consultas emplean predicados más
complejos resultado de combinaciones booleanas de los simples. Una
combinación especialmente interesante es la conjunción de predicados simples, al
predicado resultante se le denomina predicado mintérmino. Partiendo de que
siempre es posible transformar una expresión lógica en su forma normal
conjuntiva, usaremos los predicados mintérmino en los algoritmos para no causar
ninguna pérdida de generalidad.
Dado un conjunto de predicados simples de una relación R, Pri = {pi1, pi2, ..., pim},
el conjunto de predicados mintérmino Mi = {mi1, mi2, ..., miz} se define como
79
donde p*ik = pik o p*
ik = pik. Es decir, cada predicado mintérmino puede ser igual
a la forma natural o a la forma negada del predicado simple. Es importante señalar
que la referencia a la negación de un predicado es significativa para predicados de
igualdad de la forma
Atributo = Valor
Para predicados de desigualdad, la negación debería tratarse como su
complemento. Por ejemplo, la negación del predicado simple
Atributo Valor es Atributo > Valor
Pero existen casos en los que el complemento es difícil de definir. Por ejemplo, si
dos predicados son de la forma
Límite_inferior Atributo_1
Atributo_1 Límite_superior
sus complementos son
(Límite_inferior Atributo_1)
(Atributo_1 Límite_superior)
Sin embargo, si los dos predicados simples se escriben como
Límite_inferior Atributo_1 Límite_superior
con un complemento,
zjmkpmmM ik
pijiji
iik
1,1},|{ *
Pr
80
( Límite_inferior Atributo_1 Límite_superior)
este no es fácil de definir.
Ejemplo 2. Considerando la relación ALBCLIT de la figura 18, los siguientes
predicados son algunos de los posibles predicados simples que pueden definirse
sobre la relación:
p1 : CCODCLI = “250104” p2 : CCODCLI = “250102” p3 : CCODCLI = “250103” p4 : CCODCLI = “250108” p5 : CCODCLI = “250107” p6 : CCODCLI = “250109” p7 : NNUMALB 980000 p8 : NNUMALB > 980000
Los siguientes son algunos de los predicados mintérmino basados en los
predicados simples anteriores:
m1 : CCODCLI = “250104” NNUMALB 980000 m2 : CCODCLI = “250104” NNUMALB > 980000 m3 : (CCODCLI = “250104”) NNUMALB 980000 m4 : (CCODCLI = “250104”) NNUMALB > 980000 m5 : CCODCLI = “250102” NNUMALB 980000 m6 : CCODCLI = “250102” NNUMALB > 980000 m7 : (CCODCLI = “250102”) NNUMALB 980000 m8 : (CCODCLI = “250102”) NNUMALB > 980000
Habrá que tener en cuenta que estos ocho predicados mintérmino no son todos
los que se pueden definir, es sólo un ejemplo.
Sobre la información cuantitativa necesaria relativa a las aplicaciones, se
necesitará definir dos conjuntos de datos.
81
1. Selectividad mintérmino. Es el número de tuplas de una relación a las que
accede una consulta de acuerdo a un predicado mintérmino dado. Por
ejemplo, volviendo al ejemplo anterior, la selectividad de m6 es 0 ya que no
existe ninguna tupla que satisfaga las condiciones; en cambio, la
selectividad de m1 es 2. Se aprecia la selectividad de un mintérmino mi
como sel(mi).
2. Frecuencia de acceso. Es la frecuencia con la que un usuario accede a los
datos. Si Q = {q1, q2, ..., qq} es un conjunto de consultas de usuario, acc(qi)
indica la frecuencia de acceso a la consulta qi en un periodo dado.
Se observa, que las frecuencias de acceso mintérmino pueden establecerse a
partir de las frecuencias de acceso de la consulta. Se refiere a las frecuencias de
acceso de un mintérmino mi como acc(mi).
4.2.2 FRAGMENTACIÓN VERTICAL
Habría que recordar que, la fragmentación vertical de una relación R produce una
serie de fragmentos R1, R2,..., Rr, cada uno de los cuales contiene un subconjunto
de los atributos de R así como la clave primaria de R. El objetivo de la
fragmentación vertical consiste en dividir la relación en un conjunto de relaciones
más pequeñas tal que algunas de las aplicaciones de usuario sólo hagan uso de
un fragmento. Sobre este marco, una fragmentación óptima es aquella que
produce un esquema de división que minimiza el tiempo de ejecución de las
aplicaciones que emplean esos fragmentos.
La partición vertical resulta más complicada que la horizontal. Esto se debe al
aumento del número total de alternativas que tenemos disponibles. Por ejemplo,
en la partición horizontal, si el número total de predicados simples de Pr es n,
existen 2n predicados mintérminos posibles que puedan definirse. Además, se
sabe que, algunos de estos predicados resultarán contradictorios con algunas de
82
las aplicaciones existentes, por lo que se podrá reducir el número inicial. En el
caso vertical, si una relación tiene m atributos clave no primarios, el número de
posibles fragmentos es igual a B(m), es decir el m-ésimo número de Bell [3]. Para
valores grandes de m, B(m) mm; por ejemplo, para m = 10, B(m) 115.000, para
m = 15, B(m) 109, para m = 30, B(m) = 1023.
Estos valores indican que la obtención de una solución óptima de la fragmentación
vertical resultará una tarea inútil, sino nos apoyamos en el uso de heurísticos.
Existen dos enfoques heurísticos para la fragmentación vertical de relaciones:
Agrupación. Comienza asignando cada atributo a un fragmento, y en cada
paso, junta algunos de los fragmentos hasta que satisface un determinado
criterio. La agrupación sugirió en principio para bases de datos
centralizadas y se usó posteriormente para las bases de datos distribuidas.
Escisión. A partir de la relación se deciden que fragmentos resultan
mejores, basándose en las características de acceso de las aplicaciones a
los atributos. Esta técnica se presentó, también, para bases de datos
centralizadas. Posteriormente, se extendió al entorno distribuido.
Antes de comenzar, se aclara un problema: la réplica de las claves de la relación
en los fragmentos. Esta es una característica de la fragmentación vertical que
permite la reconstrucción de la relación global. Por tanto, la escisión considera
únicamente aquellos atributos que no son parte de la clave primaria.
La réplica de los atributos clave supone una gran ventaja, a pesar de los
problemas que pueda causar. La ventaja está relacionada con el esfuerzo para
mantener la integridad semántica. Tenga en cuenta que cada dependencia
(funcional, multivaluada ...) es, de hecho, una restricción que influye sobre el valor
de los atributos de las respectivas relaciones en todo momento. También muchas
de estas dependencias implican a los atributos clave de una relación. Si se quiere
diseñar una base de datos tal que los atributos clave sean parte de una fragmento
83
que está ubicado en un sitio, y los atributos relacionados sean parte de otro
fragmento asignado a un segundo sitio, cada petición de actualización provocará
la verificación de integridad que necesitará de una comunicación entre esos sitios.
La réplica de los atributos clave de cada fragmento reduce esta problemática, pero
no elimina toda su complejidad, ya que la comunicación puede ser necesaria para
las restricciones de integridad que implican a las claves primarias, así como para
el control de concurrencia.
En este proyecto de tesis se tratará únicamente la técnica de escisión, ya que es
más apropiada para la estrategia descendente y porque resulta más probable
encontrar la solución para la relación entera que a partir de un conjunto de
fragmentos con un único atributo. Además, la escisión genera fragmentos no
solapados mientras que la agrupación normalmente produce fragmentos
solapados. Dentro del contexto de los sistemas de bases de datos distribuidos,
son preferibles los fragmentos no solapados por razones obvias. Evidentemente,
los fragmentos no solapados se refieren únicamente a atributos clave no
primarios.
Una posible alternativa a la réplica de los atributos clave es el empleo de
identificadores de tuplas, que son valores únicos asignados por el sistema a las
tuplas de una relación. Mientras el sistema mantenga los identificadores, los
fragmentos permanecerán disjuntos.
INFORMACIÓN NECESARIA PARA LA FRAGMENTACIÓN VERTICAL.
La principal información que se necesitará, se referirá a las aplicaciones. Por
tanto, este punto tratará de especificar la información que de una aplicación que
funciona sobre la base de datos que se pueda extraer. Teniendo en cuenta que la
fragmentación vertical coloca en un fragmento aquellos atributos a los que se
accede de manera simultánea, se necesitará alguna medida que defina con más
84
precisión el concepto de simultaneidad. Esta medida es la afinidad de los
atributos, que indica la relación estrecha existente entre los atributos.
El principal dato necesario relativo a las aplicaciones es la frecuencia de acceso.
Sea Q = {q1, q2, ..., qq} el conjunto de consultas de usuario (aplicaciones) que
funcionan sobre una relación R(A1, A2, ..., An). Entonces, para cada consulta qi y
cada atributo Aj, asociaremos un valor de uso de atributos, representado por
uso(qi, Aj) y definido como sigue:
uso(qi, Aj) = 1 si la consulta qi hace referencia a Aj
uso(qi, Aj) = 0 en cualquier otro caso
Los vectores uso(qi, ) pueden definirse muy fácilmente para cada aplicación
siempre que el diseñador conozca las aplicaciones existentes en el sistema. La
regla 80/20 expuesta páginas atrás podría resultar útil para el desarrollo de esta
tarea.
Ejemplo 3. Sea la relación CLIENTES de la base de datos. Se asume que las
siguientes aplicaciones van a hacer uso de ella. Se indica, también, la
especificación SQL.
q1 : Encuéntrese el nombre y la dirección del cliente a partir de su código. SELECT CNOMCLI, CDIRCLI FROM CLIENTES WHERE CCODCLI = Valor q2 : Encuéntrese el nombre y DNI de todos los clientes residentes en una determinada provincia. SELECT CNOMCLI, ID_UNICO FROM CLIENTES WHERE NCODEDO = Valor q3 : Encuéntrese el nombre de todos los clientes. SELECT CNOMCLI FROM CLIENTES q4 : Encuéntrese la población el código postal de un cliente a partir de su número. SELECT CPOBCLI, CPTLCLI FROM CLIENTES
85
WHERE CLIENTES = Valor De acuerdo a estas cuatro aplicaciones, se pueden especificar los valores de uso
de los atributos. Como convenio de notación, denominaremos A1 = CLIENTES, A2
= CCODCLI, A3 = CNOMCLI, A4 = CDIRCLI, A5 = CPOBCLI, A6 = NCODPROV, A7
= CPTLCLI y A8 = CDNICIF. Los valores de uso se definen en la matriz de uso de
atributos siguiente. Cada entrada (i, j) corresponde a uso(qi, Aj).
Los valores del uso de los atributos en general no son suficientes para desarrollar
la base de la escisión y la fragmentación de los atributos, ya que estos valores no
representan el peso de las frecuencias de la aplicación. La dimensión de esta
frecuencia puede incluirse en la definición de la medida de los atributos afines
afd(Ai, Aj), la cual mide el límite entre dos atributos de una relación de acuerdo a
cómo las aplicaciones acceden a ellos.
La medida de los atributos afines entre los dos atributos Ai y Aj de una relación
R(A1, A2, ..., An) con respecto a un conjunto de aplicaciones Q = {q1, q2, ..., qq} se
define como
donde refl(qk) es el número de accesos a los atributos (Ai, Aj) por cada ejecución
de la aplicación qk en el sitio Sl y acc(qk) es la medida de la frecuencia de acceso
de una aplicación definida anteriormente, pero modificada para incluir las
frecuencias en los distintos sitios. El resultado de este cálculo es una matriz de n
n, donde cada elemento es una de las medidas definidas antes. Denominaremos a
01010001
00000100
10100100
00001110
4
3
2
1
87654321
q
q
q
q
AAAAAAAA
1),(1),(|
)()(),(jkik lAqusoAqusok S
klklji qaccqrefAAafd
86
esta matriz la matriz de atributos afines o MAA. Dicha matriz se empleará en el
resto de este punto para mostrar el proceso de fragmentación. El proceso implica
una agrupación de los atributos con alta afinidad, para luego realizar la escisión de
los mismos
ALGORITMO DE AGRUPACIÓN
No confundir la agrupación de atributos con la técnica heurística del mismo
nombre presentada al principio, no tiene nada que ver. La tarea fundamental
consiste en diseñar un algoritmo de fragmentación vertical que encuentre un
término medio de agrupación de los atributos de una relación basándose en los
valores de afinidad de atributos contenidos en MAA. Se ha sugerido por parte de
muchos autores que el algoritmo de energía límite o BEA (acrónimo inglés
procedente de las palabras Bond Energy Algorithm) resulta muy apropiado para tal
propósito. Se considera adecuado por las siguientes razones:
1. Se diseñó específicamente para determinar grupos de elementos similares
frente a una ordenación lineal de los elementos (es decir, grupos de
atributos con gran afinidad frente a grupos de atributos con valores
pequeños de la misma).
2. Los grupos resultantes no eran sensibles al orden en el cual los elementos
se dispusiesen por el algoritmo.
3. El tiempo de cálculo del algoritmo es razonable, O(n2), donde n es el
número de atributos.
4. La interrelación secundaria entre grupos de atributos es identificable.
El algoritmo de energía límite toma como entrada la matriz de atributos afines,
permuta filas y columnas y genera una matriz de grupos afines (MGA). La
87
permutación se hace de tal manera, que se maximice la siguiente medida de
afinidad global (AG):
donde CV son los cuatro vecinos de un elemento de la matriz, es decir
A su vez,
El último conjunto de condiciones toma en consideración los casos en los que los
atributos se sitúan en la MGA a la izquierda del atributo extremo izquierdo o a la
derecha del atributo extremo derecho durante la permutación de columnas, e
igualmente respecto a la fila que se sitúa en la parte superior durante la
permutación de filas. En estos casos, tomaremos el cero como valor de afinidad
entre los atributos considerados para su ubicación y sus vecinos izquierdos o
derechos (superiores o inferiores), que no existen en la MGA.
La función de maximización considera sólo los vecinos más próximos, resultando
en el grupo de valores grandes solo éstos, y en el grupo de valores pequeños solo
éstos. Además, la matriz de atributos afines es simétrica, lo cual reduce la función
objetiva de la formulación a
El algoritmo se presenta a continuación. Para la generación de la matriz de
grupos afines se siguen tres pasos:
n
i
n
jji CVAAafdAG
1 1
·),(
),(),(
),(),(
11
11
jiji
jiji
AAafdAAafd
AAafdAAafdCV
0),(),(),(),( 1100 nijnij AAafdAAafdAAafdAAafd
n
i
n
jjijiji AAafdAAafdAAafdAG
1 111 )],(),()[,(
88
1. Iniciación. Sitúa y fija una de las columnas de MAA arbitrariamente dentro
de MGA. En el algoritmo se escoge la columna 1.
2. Iteración. Se toma cada una de las columnas restantes n-i (donde i es el
número de columnas que ya se han situado en MGA) y se intenta situarlas
en las n-i posiciones restantes de la matriz MGA. Se escoge como lugar de
emplazamiento aquel que proporciones una mayor contribución a la medida
de afinidad global descrita anteriormente. Se continúa con este paso hasta
que se agote el número de columnas a situar.
3. Ordenación de las filas. Una vez que la ordenación de las columnas ha
finalizado, se debe proceder a ordenar las filas de tal modo que su posición
relativa coincida con la de las columnas. Por ejemplo, si la columna 3 se ha
situado en la primera posición, la fila número 3 también debería pasar a
ocupar la primera posición.
Algoritmo BEA
entrada:
MAA: matriz de atributos afines
salida:
MGA: matriz de grupos afines
inicio
{iniciación; recuerde que MAA es una matriz
de n n}
MGA(, 1)MAA(, 1)
MGA(, 2)MAA(, 2)
índice3
mientras índice n hacer
{escoger la mejor ubicación para el
89
atributo MAAíndice}
inicio
para i=1 hasta índice–1 por 1 hacer
calcular cont(Ai-1, Aíndice, Ai)
fin-para
calcular cont(Aíndice-1, Aíndice, Aíndice+1)
{condición de inmovilidad}
posubicación dada por el máximo valor
de cont
para j=índice hasta pos por –1 hacer
{cambiar la posición de las columnas}
MGA(, j)MGA(, j-1)
fin-para
MGA(, pos)MAA(, índice)
índiceíndice + 1
fin-mientras
ordenar las filas según la ordenación
relativa de las columnas
fin. {BEA}
Para la segunda parte del algoritmo, se necesitaría definir qué significa la
contribución de un atributo a la medida de afinidad. Esta contribución puede
derivarse como se expondrá ahora. Se parte de la definición dada de la medida de
afinidad global que se escribió como
n
i
n
jjijiji AAafdAAafdAAafdAG
1 111 )],(),()[,(
la cual puede rescribirse como
n
i
n
jjijijiji AAafdAAafdAAafdAAafdAG
1 111 )],(),(),(),([
90
Se define el límite lím entre dos atributos Ax y Ay como
n
zyzxzyx AAafdAAafdAA
1
),(),(),lím(
Entonces se puede escribir AG como
n
jjjjj AAAAAG
111 )],lím(),[lím(
Considerese ahora los siguientes n atributos
La medida de afinidad global para estos atributos puede escribirse como
),lím(2
)],lím(),[lím(
)],lím(),[lím(
),lím(),lím('''
211
111
ji
n
illlll
n
lllll
ijjiant
AA
AAAA
AAAA
AAAAAGAGAG
Considerese ahora que entre los atributos Ai y Aj de la matriz de grupos afines se
sitúa un nuevo atributo Ak. La nueva medida de afinidad global sería entonces
),lím(2),lím(2'''
),lím(),lím(
),lím(),lím('''
jkki
kjjk
ikkinueva
AAAAAGAG
AAAA
AAAAAGAGAG
n
j
n
i
n
ijijijiji AAafdAAafdAAafdAAafdAG
1 1 111 ),(),(),(),(
''
1
'
121 ......
AG
njji
AG
i AAAAAAA
91
Por tanto, la contribución a la red de la medida de afinidad global al situar el
atributo Ak entre Ai y Aj es
),lím(2),lím(2),lím(2),,(
),,(
jijkkijki
antnuevajki
AAAAAAAAAcont
AGAGAAAcont
4.2.3 FRAGMENTACIÓN MIXTA O HÍBRIDA
En muchos casos la fragmentación vertical u horizontal del esquema de la base de
datos no será suficiente para satisfacer los requisitos de las aplicaciones. Como ya
se citó al comienzo de este documento se puede combinar ambas, utilizando por
ello la denominada fragmentación mixta. Cuando al proceso de fragmentación
vertical le sigue una horizontal, es decir, se fragmentan horizontalmente los
fragmentos verticales resultantes, se habla de la fragmentación mixta HV. En el
caso contrario, estaremos ante una fragmentación VH. Una característica común a
ambas es la generación de árboles que representan la estructura de
fragmentación (figura 19).
Considere, por ejemplo, la relación ESTADO. Habría que recordar que se le aplicó
una fragmentación horizontal de acuerdo al valor del atributo CCODZONA
resultando cuatro fragmentos horizontales. Se podría pensar en aplicar una nueva
fragmentación de carácter vertical. Entonces resultarían cuatro fragmentos
horizontales divididos, por ejemplo, en dos fragmentos verticales. En este caso el
número total de fragmentos ascendería, lógicamente, a ocho.
No se desea entrar en excesivos detalles sobre las reglas y condiciones para
efectuar la fragmentación mixta. Entre otras razones porque, tanto a la
fragmentación HV como la fragmentación VH, se le pueden aplicar los mismos
criterios y reglas que a la fragmentación horizontal y vertical. Es decir, volviendo al
ejemplo anterior, al cual le practicamos la fragmentación HV, al realizar la
fragmentación horizontal tal como se ha expuesto, lo que se obtienen no son más
92
que subrelaciones, la unión de las cuales da lugar a la relación ESTADO. Por
tanto, para fragmentar cada subrelación sería perfectamente viable aplicarle el
método de fragmentación vertical que se ha desarrollado. Como, en este caso, se
han querido generar dos fragmentos verticales por cada uno horizontal,
simplemente se debería confeccionar la matriz de grupos afines (a través del
algoritmo BEA) para cada fragmento horizontal y aplicarle, posteriormente, el
algoritmo de fragmentación binaria PARTICIÓN.
Fig. 18. Estructura arbórea de fragmentación mixta
También debe tenerse en cuenta el número de niveles arbóreos que se generen,
es decir, nadie impide que tras realizar una fragmentación VH, puede aplicar a los
fragmentos resultantes una nueva fragmentación vertical, y a estos última una
nueva fragmentación horizontal. Dicho número puede ser grande, pero también
será ciertamente finito. En el caso horizontal, el nivel máximo de profundidad se
alcanzará cuando cada fragmento albergue una única tupla, mientras que en el
caso vertical el final llegará cuando cada fragmento contenga un único atributo.
Sin embargo, aunque no deba tomarse como dogma, el número de niveles no
debería superar el par (VH y HV). El porqué de esta afirmación es bien sencillo,
piense, por ejemplo, en el costo que supondría realizar la unión o el yunto de una
93
relación con fragmentación nivel 7. Evidentemente, el costo sería muy elevado y
ese aumento de rendimiento que se persigue al aplicar estas técnicas, quizás, no
se produzca.
Antes de pasar a explicar el problema de la asignación se desea comentar la
técnica de fragmentación mixta basada en celdas. Esta técnica se basa en la
generación de celdas de rejilla. ¿Qué es una celda de rejilla?, se podría definir
como un fragmento horizontal y vertical simultáneo. La técnica aplica un algoritmo
de fragmentación vertical y otro horizontal de manera concurrente sobre la
relación. Los algoritmos realizan una fragmentación máxima, es decir, se persigue
que en cada celda únicamente haya un atributo y una tupla. Quizá el usuario
pueda encontrar el método contradictorio con lo citado anteriormente respecto a la
eficiencia, dada la gran cantidad de fragmentos generados, el número es,
efectivamente, el máximo. Sin embargo, este sólo es el primer paso del proceso.
Una vez generadas las celdas se aplica un método para optimizar la rejilla
mediante fusión o desfragmentación, de acuerdo, fundamentalmente, a las
aplicaciones que actúen sobre esos fragmentos. El método, por tanto, persigue
una fragmentación lo más específica posible acorde con las aplicaciones y los
sitios existentes en la red.
4.2.3.1 ASIGNACIÓN
Se define un problema donde sean un conjunto de fragmentos F = {F1, F2, ..., Fn} y
una red formada por el conjunto de sitios S = {S1, S2, ..., Sm} en la cual un conjunto
de aplicaciones Q = {q1, q2, ..., qq} se ejecutan. El problema de la asignación
implica encontrar la distribución óptima de F sobre S.
Uno de los problemas más importantes que necesita discusión es el significado de
distribución óptima. La distribución óptima puede definirse con respecto a dos
medidas:
94
1. Costo mínimo. La función de costo consiste en el costo de
almacenamiento de cada Fi en un sitio Sj, el costo de practicar una consulta
en Fi en el sitio Sj, el costo de actualizar Fi en todos los sitios donde se
almacene y el costo de las comunicaciones de datos. El problema de la
asignación, entonces, intenta encontrar un esquema de asignación tal que
minimice esta función de costo combinado.
2. Rendimiento. La estrategia de asignación se diseña para mantener una
medida del rendimiento. Dos medidas habituales de este rendimiento son el
tiempo de respuesta y la salida del sistema en cada sitio. Evidentemente,
se debe intentar minimizar la primera y maximizar la segunda.
Se han propuesto modelos de asignación que enfocan el concepto de distribución
óptima desde diferentes puntos de vista. Sin embargo, no resulta descabellado
pensar en la inclusión, tanto del rendimiento como de los factores de costo, dentro
del concepto. En otras palabras, se debería buscar un esquema de asignación tal
que, por ejemplo, la respuesta a las consultas de los usuarios se realizase en el
menor tiempo posible mientras que el costo de procesamiento fuese mínimo. Una
afirmación similar podría hacerse respecto a la maximización de la salida del
sistema.
Considerendo ahora una formulación del problema muy simple. Se define F y S
como se hizo anteriormente. Por el momento, se considera únicamente un
fragmento sencillo, Fk. Se dará un número de definiciones que permitan modelar el
problema de la asignación.
1. Se asume que Q puede modificarse de tal manera que sea posible
identificar las consultas de actualización de las de lectura, y definiremos lo
siguiente para ese fragmento simple Fk:
T = {t1, t2, ..., tm}
95
donde ti es el tráfico de lectura que se genera en el sitio Si para Fk, y
U = {u1, u2, ..., um}
donde ui es el tráfico de actualización que se genera en el sitio Si para Fk.
2. Se asume que el costo de comunicaciones entre un par de sitios Si y Sj es
fijo para una unidad de transmisión. Además, también se asume que este
es diferente para actualizaciones y para lecturas, por lo que se define:
C(T) = {c12, c13, ..., c1m, ..., cm-1,m}
C’(T) = {c’12, c’13, ..., c’1m, ..., c’m-1,m}
donde cij es el costo de la unidad de comunicación para las peticiones de
lectura entre los sitios Si y Sj y c’ij es el costo de la unidad de comunicación
para las peticiones de lectura entre los sitios Si y Sj.
3. Sea di el costo de almacenar el fragmento en el sitio Si. Entonces definimos
D = {d1, d2, ..., dm} como el costo de almacenar Fk en todos los sitios.
4. Se asume que no existen restricciones de capacidad en los sitios o en los
enlaces de comunicaciones.
Entonces el problema de asignación puede especificarse como un problema de
minimización de costos por el cual se intenta encontrar el conjunto I S que
especifique el lugar donde han de ubicarse las copias de los fragmentos. La
expresión matemática hace uso de la variable de decisión para la ubicación xj es,
96
xj = 1 si el fragmento Fk se asigna al sitio Sj
xj = 0 en otro caso
entonces, definida xj,
m
i ISjjj
ISjij
ISjjijjj
jjj
dxctcux1 ||
|mín'mín
El segundo término de la función calcula el costo total de almacenar todas las
copias duplicadas del fragmento. El primer término corresponde al costo de
transmisión de las actualizaciones a todos los sitios que mantienen réplicas de un
fragmento y al costo de ejecución de las peticiones de lectura en el sitio, lo cual
resultará un costo mínimo de transmisión de datos.
Esta es una formulación muy simple que no es válida para el diseño de bases de
datos distribuidas. Pero en el caso que lo fuera, existiría un problema. Para un
gran número de fragmentos y de sitios, obtener soluciones óptimas resultaría
probablemente totalmente inviable. Las investigaciones, por tanto, deben girar en
torno a la búsqueda de buenos heurísticos que proporciones soluciones
parcialmente óptimas.
Hay un número de razones del porqué de formulaciones tan simples que no sirven
para el diseño de bases de datos distribuidas. Generalmente, se heredan de los
modelos de asignación de archivos para redes, pero:
1. No se pueden tratar los fragmentos como archivos individuales que se
asignen aisladamente. La ubicación de un fragmento generalmente tiene
influencia sobre las decisiones de asignación de los otros fragmentos, a los
cuales se acceden a la vez, puesto que el costo de acceso de los
97
fragmentos restantes puede variar. Por tanto, las relaciones entre
fragmentos deben tenerse en consideración.
2. El acceso de las aplicaciones a los datos se modela muy sencillamente.
Una petición de usuario se resuelve en un sitio y todos los datos necesarios
se transfieren a ese sitio. En los sistemas de bases de datos distribuidos, el
acceso a los datos es más complicado que el simple acceso a archivos
remotos. Por tanto, la relación entre la asignación y el procesamiento de
consultas debería también tenerse en cuenta.
3. Estos modelos no tienen en cuenta el costo de mantenimiento de la
integridad, aún localizando dos fragmentos implicados con las mismas
restricciones de integridad en dos sitios diferentes podría resultar costoso
dicho mantenimiento.
4. Igualmente, el costo derivado del control de concurrencia debería tenerse
en cuenta.
En resumen, se debe distinguir entre el problema tradicional de asignación de
archivos de la asignación de fragmentos en los sistemas de bases de datos
distribuidos.
No existen modelos heurísticos generales que tomen como entrada un conjunto de
fragmentos y produzcan una asignación cercana a lo óptimo que además esté
influenciada por los tipos de restricciones descritas antes. Los modelos
desarrollados realizan una serie de simples suposiciones y pueden aplicarse a
ciertas formulaciones específicas. Por tanto, se presentará un modelo general y se
discutirá una serie de posibles heurísticos que puedan emplearse para resolver el
problema. Posteriormente, se describirá un algoritmo concreto de asignación.
4.2.3.2 INFORMACIÓN NECESARIA
98
En esta etapa de la asignación, se necesitará datos cuantitativos sobre la base de
datos, las aplicaciones que funcionan sobre ella, la red de comunicaciones, las
características de proceso, y el límite de almacenamiento de cada sitio de la red.
Información de la base de datos. Para desarrollar la fragmentación horizontal, se
define la selectividad de los mintérminos. Ahora, se necesita extender esta
definición a los fragmentos y definir la selectividad de un fragmento Fj con
respecto a una consulta qi. Es el número de tuplas de Fj a las que se necesita
acceder para procesar qi. Este valor se notará como seli(Fj). Otro elemento
informativo de los fragmentos de la base de datos es su tamaño. El tamaño de un
fragmento Fj viene dado por
)()·()( jjj FlongFcardFtamaño
donde long(Fj) es la longitud (en octetos) de una tupla del fragmento Fj.
Información de las aplicaciones. Mucha de la información relativa a las
aplicaciones se recoge durante el proceso de fragmentación, pero se
necesita un poco más para el modelo de asignación. Las dos medidas más
importantes son el número de accesos de lectura que una consulta qi
realiza sobre un fragmento Fj durante su ejecución (llamada RRij), y el
número de accesos de actualización que una consulta qi realiza sobre un
fragmento Fj durante su ejecución (llamada URij). También necesitamos
definir dos matrices UM y RM, con elementos uij y rij, respectivamente, que
se especifican como sigue:
uij = 1 si la consulta qi actualiza el fragmento Fj
uij = 0 en otro caso
rij = 1 si la consulta qi lee del fragmento Fj
99
rij = 0 en otro caso
También debe definirse un vector O de valores o(i), donde o(i) especifica el
sitio origen de la consulta qi. Finalmente, especificaremos las restricciones
impuestas por el tiempo de respuesta, asignando a cada aplicación el
máximo tiempo de respuesta permitido.
Información de los sitios. Sobre cada computadora necesitamos conocer
sus capacidades de procesamiento y almacenamiento. Obviamente, estos
valores pueden calcularse a través de funciones elaboradas o por simples
estimaciones. La unidad de costo de almacenar datos en el sitio Sk será
denotada como UCAk. Así mismo, especificaremos como medida de costo
UPTk al costo de procesar una unidad de trabajo en el sitio Sk. La unidad de
trabajo debería ser idéntica a aquella utilizada en las medidas RR y UR.
Información sobre la red. En nuestro modelo asumiremos la existencia de
una red simple donde el costo de comunicaciones se define respecto a una
trama de datos. Entonces gij nota el costo de comunicación por trama entre
los sitios Si y Sj. Para permitir el cálculo del número de mensajes, usaremos
ftamaño como el tamaño (en octetos) de una trama. Es evidente que existen
modelos de red mucho más elaborados que toman en cuenta las
capacidades del canal, las distancias entre sitios, las características del
protocolo, etc. Sin embargo, se cree que la derivación de estas ecuaciones
se sale fuera de este documento.
4.2.3.3 MODELO DE ASIGNACIÓN
Se discutirá un modelo de asignación que intente minimizar el costo total de
procesamiento y almacenamiento a la vez que intenta reunir ciertas restricciones
en el tiempo de respuesta. El modelo que se empleará tiene la forma mín(Costo
Total), la cual está sujeta a restricciones del tiempo de respuesta, restricciones de
almacenamiento y restricciones de procesamiento.
100
En el resto de este punto se desarrollará los componentes de este modelo
basándose en la información necesaria presentada anteriormente. La variable de
decisión es xij, la cual se define como
xij = 1 si el fragmento Fi se almacena en el sitio Sj
xij = 0 en otro caso
Costo total. La función de costo total tiene dos componentes: el procesamiento de
la consulta y el almacenamiento. Entonces podría expresar como
SS FF
jkQq
i
k ji
CAFCPQCTO
donde CPQi es el costo de procesar una consulta de la aplicación qi, y CAFjk es el
costo de almacenar el fragmento Fj en el sitio Sk.
Considerarse primero el costo de almacenamiento. Su fórmula viene dada por
jkjkjk xFtamañoUCACAF *)(*
donde se representa el costo total de almacenamiento en todos los sitios y para
todos los fragmentos.
El costo de procesamiento de consultas es más difícil de especificar. Muchos
modelos de asignación de archivos se dividen en dos componentes: el costo de
procesar las lecturas y el costo de procesar las actualizaciones. Se escogerá un
enfoque diferente para el problema de asignación en las bases de datos y lo se
especificará a partir del costo de procesamiento (CP) y el costo de transmisión
(CT). El costo de procesamiento de una consulta (CPQ) para una aplicación qi es
101
iii CTCPCPQ
De acuerdo con las líneas presentadas anteriormente, el componente de
procesamiento CP se basa en tres factores: el costo de acceso (CA), el costo de
mantenimiento de la integridad (MI) y el costo de control de la concurrencia (CC):
iiii CCMICACP
La especificación detallada de cada uno de estos factores depende del algoritmo
que se emplee para desarrollar estas tareas. Sin embargo, se especificará CA
detalladamente:
SS FF
kjkijijijiji
k j
UPTxRRrURuCA )(
El primero de los términos de la fórmula calcula el número de accesos de la
consulta qi al fragmento Fj. Advierta que (URij + RRij) da el número total de
accesos de lectura y actualización. Se asumirá que los costos locales de
procesamiento de ambos son idénticos. El sumatorio proporciona el número total
de accesos para todos los fragmentos a los que accede qi. El producto por UPTk
da el costo de este acceso al sitio Sk. Se usará de nuevo, xjk para seleccionar
únicamente los valores de costo para los sitios donde se almacenan los
fragmentos.
Se debe tener en cuenta que la función de costo de acceso asume que el
procesamiento de una consulta implica su descomposición en una serie de
subconsultas, cada una de las cuales trabaja sobre un fragmento almacenado en
un sitio, seguido de una transmisión de los resultados al sitio del cual partió la
consulta. Se vió, anteriormente, que es un enfoque muy simplista no tener en
102
cuenta la complejidad del procesamiento de la base de datos. Por ejemplo, la
función de costo no tiene en cuenta el costo de desarrollar yuntos (si fuese
necesario), lo cual puede ejecutarse de varias formas. En un modelo más realista,
que el modelo genérico considerado, esto problemas no deberían omitirse.
El factor de costo del esfuerzo de integridad puede especificarse como el
componente de procesamiento, excepto que la unidad de costo de procesamiento
local, probablemente, cambiaría para reflejar el costo real del esfuerzo de
integridad.
La función del costo de transmisión puede formularse sobre las líneas de la
función del costo de acceso. Sin embargo, los gastos de la transmisión de datos
para actualizaciones y para lecturas no es el mismo. En las consultas de
actualización, es necesario informar a todos los sitios donde existen réplicas,
mientras que en las consultas de lectura, es suficiente con acceder al sitio que
alberga las copias. En suma, al final de una petición de actualización, no existe
una transmisión de datos al sitio origen de ésta, sino un mensaje de confirmación,
mientras que en las consultas de lectura, los datos a transmitir al origen son
significativos.
El componente de actualización de la función de transmisión es
SS SS FF
iokjkijFF
kiojkiji
k k jj
gxugxuCTA )(,),( ····
El primer término es para el envío del mensaje de actualización de qi desde el sitio
origen o(i) a todas las réplicas de los fragmentos que necesiten actualizarse. El
segundo término hace referencia a la confirmación.
El costo de lectura puede especificarse como
103
FFiok
tamaño
ji
jkijkiojkijSS
i
jk
gf
FselxrgxuCTL )
)(···(mín )(,),(
El primer término de CTL representa el costo de transmitir la petición de lectura a
los sitios que contienen copias de los fragmentos a los que se necesita acceder. El
segundo término cuenta para la transmisión de los resultados desde estos sitios al
sitio origen. La ecuación afirma que para todos los sitios con copias del mismo
fragmento, sólo el sitio que produzca el costo total de transmisión más pequeño
debería seleccionarse para la ejecución de la operación.
Ahora, la función del costo de la transmisión para la consulta qi puede
especificarse como
iii CTLCTACT
que indica la función de costo total.
Restricciones. Las funciones restrictivas pueden especificarse de forma similar.
Sin embargo, en lugar de describir estas funciones con detalle, simplemente se
indicará el aspecto que deberían tener. El tiempo de respuesta debería
especificarse como
tiempo de ejecución de qi máximo tiempo de respuesta de qi, qiQ
Preferiblemente, la medida de costo en la función objetiva debería especificarse
en términos de tiempo, para hacer la especificación del tiempo de ejecución
relativamente sencilla.
La restricción de almacenamiento es
104
SSSRAL kkFF
jk
j
, sitio del entoalmacenami de capacidad la
Así misma, la restricción de procesamiento es
SSS
Sq
kk
Qqki
i
, de proceso de capacidad
sitio elen de ntoprocesamie de carga
Esto completa el desarrollo del modelo de asignación.
DESARROLLO PRÁCTICO
Se presenta ahora dos alternativas prácticas de desarrollo de la asignación. Una
primera consistiría en el cálculo de todos los costos y, a partir de sus resultados y
con el mejor esquema de partición determinado por el Examinador de Particiones,
decidir los fragmentos que deberían asignarse a cada sitio. Este método manual
evidentemente implica la realización de muchos cálculos muy engorrosos, y se
debería partir de una serie de datos que no siempre es fácil obtener. Una segunda
alternativa, es el uso de algún algoritmo de asignación desarrollado a partir de los
distintos parámetros del modelo de asignación. Existen varios de estos algoritmos,
pero se ha decidido exponer el algoritmo divide y vencerás [Shepherd J.A] porque
hace uso del esquema de fragmentación que genera el algoritmo de
fragmentación n-formas presentado en la correspondiente sección.
4.2.3.4 MÉTODO DE ASIGNACIÓN “Divide y vencerás”
Se paretirá del conjunto de esquemas de asignación que produce el algoritmo n-
formas. Un aspecto importante de este algoritmo es que, como ya se comentó,
produce esquemas de fragmentación jerárquicos, es decir, partiendo de k
fragmentos obtiene k+1 fragmentos para el siguiente esquema.
105
Seguidamente, se describirá el funcionamiento del algoritmo. En la primera parte
del mismo (antes del primer bucle para), se intenta encontrar la mejor asignación
del fragmento único (el esquema número 1) y el costo de esta operación. Una vez
que se tiene el fragmento en el mejor sitio, se calcula el costo de mantenerlo en
este sitio invocando a la función CostoConsulta. Una llamada a esta función
devuelve el costo para una determinada consulta basada en su plan de ejecución.
La segunda parte del algoritmo va desde el paso 2 hasta el final del mismo. Dado
un esquema de fragmentación, esta parte calcula el mejor costo de mover los dos
nuevos fragmentos a los diferentes sitios de la red, dejando el resto de los
fragmentos quietos en los sitios que se determinaron mejores para ellos. Se repite
el bucle para del paso 2 para todos los esquemas de fragmentación de tal manera
que el algoritmo termina proporcionando el mejor esquema de partición y los sitios
en donde se debería ubicar cada fragmento. Advierta que este algoritmo lleva
implícita la tarea realizada por el Examinador de Particiones, por lo que no es
necesario emplearlo en este enfoque. Por último, se desea señalar que la
complejidad del algoritmo es de O(ns2qx) donde n, s y q son el número de
fragmentos, sitios y consultas, respectivamente, y O(x) el costo de llamar a la
función CostoConsulta.
Algoritmo ASIGNACIÓN-DYV entrada: EEFn: esquemas de fragmentación salida: esquema: el mejor esquema de fragmentación {cada EEFi es un esquema de fragmentación} {cada Pi es un par fragmento – sitio para el esquema de fragmentación actual i} {EEF1 es el único esquema de fragmentación que contiene un único fragmento con todos los atributos} declarar P1: el mejor lugar de ubicación del esquema
EEF1 resultado de moverlo como un único elemento alrededor de toda la red;
mejorcosto: el costo de ubicar P1 inicio
esquema1
i2 para cada fragmento de EEFi hacer inicio sean cj y ck dos nuevos grupos de
106
fragmentos de NGFi;
PiPi-1 – {(cj ck, s(cjck))} {costocjck es el costo de mover
únicamente dos nuevos grupos de fragmentos alrededor de la red manteniendo el resto de los grupos de fragmentos fijos en sus mejores sitios, calculado en iteraciones previas}
costocjck para cada posible sj del grupo cj
hacer para cada posible sk del grupo ck
hacer inicio {Pi ahora contiene la ubicación de
cada grupo de fragmentos en EEF excepto los dos nuevos grupos cj y ck}
zsuma para toda consulta q de
CostoConsulta(q, Pi{(cj, sj), (ck, sk)}, OQD);
si z < costocjck entonces inicio
costocjckz
sjmejorsj
skmejorsk fin-si fin-para
PiPi{(cj, sjmejor), (ck, skmejor)} si costocjck < mejorcosto entonces inicio
mejorcostocostocjck {el EEF actual i debe ser el mejor
que conduzca al menor costo de procesamiento de la consulta}
esquemai fin-si
ii+1 fin-para fin. {ASIGNACIÓN-DYV}
CAPÍTULO 5. CONCLUSIONES
A lo largo de este proyecto de tesis se ha intentado dar una visión global y
genérica de los problemas y características que contiene el diseño de una base de
datos distribuida. Se ha hecho especial hincapié en las técnicas de fragmentación
horizontal y vertical a través de métodos y algoritmos muy frecuentes en la
literatura referida al tema. Las técnicas son sencillas y se ha procurado incluir
distintos ejemplos para facilitar el entendimiento. Igualmente, la puesta en práctica
de los algoritmos, es decir, su codificación, no es un proceso complicado si se
poseen nociones en el desarrollo de algoritmos. Por ejemplo, que los dos
107
algoritmos de partición vertical presentados, no hacen más que manipular
matrices.
También debería tenerse presente la existencia de enfoques de fragmentación
distintos y, posiblemente, más complejos, pero se debe pensar que más eficientes.
Sean, por ejemplo, las técnicas de fragmentación vertical basadas en grafos,
como el algoritmo de Navathe y Ra que genera en un solo paso fragmentos
verticales. Además, están apareciendo métodos de fragmentación mixta como el
que se ha comentado. Si bien, estos métodos son enfoques formales más que
prácticos, desarrollados por insignes investigadores en universidades, por tanto,
lejos todavía de su desarrollo comercial.
Pese a la aparición de los métodos de bases de datos distribuidas hace ya años,
parece que el salto de lo centralizado a lo distribuido a escala comercial está por
venir. Todavía no se ha extendido suficientemente el esquema distribuido, pero se
espera que próximamente se produzca el avance definitivo. Considere los dos
componentes básicos de los sistemas de bases de datos distribuidos (la propia
base de datos y la red de computadoras) y piense en la situación actual de la
informática. Si las bases de datos es una de las ramas más antiguas e importantes
de la informática, muchas empresas compran computadoras para dedicarlos
exclusivamente a la gestión de sus datos.
108
BIBLIOGRAFÍA
1. Mark Gillenson, Fundamentals of Database Management Systems, 2nd Edition, Wily & Son 2011.
2. Saeed K. Rahimi, Frank S. Haug, Distributed Database Management Systems: A Practical Approach, Wiley, 2012.
3. Michael J. Hernandez, Database Design for Mere Mortals: A Hands-On Guide to Relational Database Design, 3rd Edition, 2013.
4. C. J. Date, Database Design and Relational Theory: Normal Forms and All That Jazz (Theory in Practice), Editorial O´reilly, 2012.
5. Date, C.J., Introducción a los Sistemas de Bases de Datos, 7ª Edicíon, Ed. Pearson Addison-Wesley, 2001
6. Stephane Faroult, Peter Robson, The Art of SQL, 1ra. Edición, Editorial O´reilly, 2006.
7. Richard T. Watson, Data Management, database and organization, Editorial Jhon Wiley & Son, Inc., 2008.
8. A. Silberschatz & H.F. Korth, Fundamentos de Bases de Datos, Editorial Mc Graw Hill, 2009.
9. Price W.T., Fundamento de Sistemas de Bases de Datos, Editorial Pearson – Addison Wisley, 2008.
10. James R. Groff, Paul N. Weinberg, Manual de Referencia SQL, Editorial Mc
Graw Hill, 2002.
11. Gary W. Hansen, Diseño y Administración de bases de datos, Editorial Prentice Hall, 2002.
12. Piñeiro Gómez José Manuel, Base de Datos Relacionales y Modelado de
Datos, Ediciones Paraninfo S.A, 2013.
13. Ramez Elmasri, Shamkant B. Navathe, Fundamentals of Database Systems, sexta edición, Editorial Pearson Education, USA, 2012.
14. Toby Teorey, Sam Lightstone, Tom Nadeau, Database Modeling & Design: Logical Design. cuarta edición, Dditorial Elsevier, San Francisco, Ca., USA, 2006.