Embed Size (px)
Citation preview
Universidad Central “Marta Abreu” de Las Villas
Facultad de Matemática, Física y Computación
TTRRAABBAAJJOO DDEE DDIIPPLLOOMMAA
Asistentes para el Diseño Lógico
de Bases de Datos Distribuidas
Autor
Lisbel Valdés Rodríguez.
Tutores
Dr. Abel Rodríguez Morffi.
MSc. Norma E. Cabrera González.
Dra. Luisa M. González González.
2009
Hago constar que el presente trabajo fue realizado en la Universidad Central “Marta
Abreu de Las Villas” como parte de la culminación de los estudios de la especialidad de
Ciencias de la Computación, autorizando a que el mismo sea utilizado por la institución,
para los fines que estime conveniente, tanto de forma parcial como total y que además
no podrá ser presentado en eventos ni publicado sin la autorización de la Universidad.
_________________
Firma del autor
Los abajo firmantes, certificamos que el presente trabajo ha sido realizado según
acuerdos de la dirección de nuestro centro y el mismo cumple con los requisitos que
debe tener un trabajo de esta envergadura referido a la temática señalada.
_________________ __________________________
Firma del tutor Firma del jefe del Seminario
"Cuanto más se dividen los obstáculos son más fáciles de vencer"
Concepción Arenal.
D E D I C A T O R I A
A mis padres, quienes han
vivido siempre para sus hijos.
A G R A D E C I M I E N T O S
A mi hermano, sin su ejemplo hace tiempo me hubiera rendido,
Al resto de mi familia que tanto siempre me ha apoyado,
A todos esos amigos que estuvieron ahí cuando los necesité,
A Isis por su comprensión y ayuda,
A mis tutores, en especial a Abel por soportarme todo este tiempo y confiarme este
trabajo,
A todos los que desde la primaria han tenido que ver en mi formación.
R E S U M E N
Resumen
La posibilidad de distribuir datos sobre diferentes sitios de una red de computadoras
promueve la difusión de los Sistemas de Bases de Datos Distribuidas, cuyo diseño
cuenta con las mismas fases que en los centralizados y se les añaden dos nuevos
problemas: la fragmentación y la asignación de los fragmentos a los sitios. El diseño de
la fragmentación tiene como propósito obtener porciones de la Base de Datos que sean
unidades lógicas de asignación.
No obstante los beneficios que reporta la distribución de datos, y de los resultados
teóricos que permiten su modelación, aún las técnicas, metodologías y herramientas
asociadas no alcanzan la madurez necesaria para ayudar a los desarrolladores de
software básico ni de aplicaciones. Como resultado de este trabajo se obtienen nuevas
versiones de dos asistentes para diseño de bases de datos distribuidas: AppWizard que
captura información sobre las aplicaciones del universo de discurso, y Fragmenter que
realiza la fragmentación de esquemas globales en esquemas lógicos.
A B S T R A C T
Abstract
The possibility of distributing data on different sites of a computer network promotes
the creation of distributed databases systems, which comprise two new problems: the
fragmentation and the allocation of the fragments to the sites. The design of the
fragmentation is intended to obtain portions of the database that are logical units of
allocation.
Nevertheless the profits that the distribution of data produces and the theoretical results
that allow its modeling; still the methods, methodologies and tools do not reach the
necessary maturity to help developers. As result of this work new version of two
assistants are obtained for design of distributed databases: AppWizard that captures
information about the applications of the universe of discourse, and Fragmenter that
carries out the fragmentation of global schemata in order to obtain logical schemata.
I N D I C E
ÍNDICE
INTRODUCCIÓN............................................................................................................ 1
CAPÍTULO 1. DISEÑO DE BASES DE DATOS DISTRIBUIDAS ............................. 6
1.1 Aspectos generales del diseño de BDD.................................................................. 6
1.2 El problema de distribución de datos ..................................................................... 8
1.3 El problema de fragmentación.............................................................................. 10
1.3.1 Fragmentación horizontal .............................................................................. 10
1.3.2 Fragmentación vertical .................................................................................. 14
1.3.3 Fragmentación mixta ..................................................................................... 19
1.4 El problema de caracterización de las aplicaciones.............................................. 20
1.5 Conclusiones parciales ......................................................................................... 21
CAPÍTULO 2. CARACTERIZACIÓN DE APLICACIONES EN EL DISEÑO DE BDD................................................................................................................................ 23
2.1 Características de la información sobre las aplicaciones...................................... 23
2.1.1 Información cualitativa.................................................................................. 23
2.1.2 Información cuantitativa................................................................................ 25
2.2 Diagramas de clases del asistente AppWizard ..................................................... 26
2.3 Interfaz del asistente AppWizard ......................................................................... 27
2.4 Conclusiones parciales ......................................................................................... 30
CAPÍTULO 3. ASISTENTE PARA LA FRAGMENTACIÓN .................................... 31
3.1 Fragmentación horizontal ..................................................................................... 31
3.1.1 Algoritmo para la fragmentación horizontal primaria................................... 31
3.1.2 Algoritmo para la fragmentación horizontal derivada................................... 39
3.2 Fragmentación Vertical ........................................................................................ 42
3.2.1 Algoritmo de Hoffer y Severance.................................................................. 43
3.2.2 Partición vertical binaria................................................................................ 45
3.2.3 Algoritmo basado en una función objetivo empírica..................................... 46
3.3 Diagrama de clases del asistente Fragmenter ................................................. 50
I N D I C E
3.4 Interfaz del asistente Fragmenter.......................................................................... 51
3.5 Conclusiones parciales ......................................................................................... 53
CONCLUSIONES.......................................................................................................... 54
RECOMENDACIONES ................................................................................................ 56
REFERENCIAS BIBLIOGRÁFICAS ........................................................................... 57
I N T R O D U C C I O N
1
INTRODUCCIÓN
En los últimos años han surgido gran cantidad de innovaciones tecnológicas que unidas
al descenso en los costos del hardware han estimulado el desarrollo de los Sistemas de
Bases de Datos Distribuidas (SBDD). Según Őzsu y Valduriez (Őzsu and Valduriez,
1999), una Base de Datos Distribuida (BDD) es una colección de múltiples Bases de
Datos (BD), lógicamente interrelacionadas distribuidas sobre una red de computadoras.
Así, el objetivo fundamental de los SBDD es integrar la manipulación de datos para que
sean presentados al usuario como una única colección de datos global y coherente. Por
tanto, la distribución involucra el hecho de que los datos no residen necesariamente en
el mismo sitio, pero poseen propiedades comunes que los vinculan, y se facilita su
acceso a través de una interfaz común. Es necesario destacar que los enlaces entre los
datos se llevan a cabo en una red de comunicación, lo que implica generalmente que los
sitios estén localizados en diferentes áreas geográficas y con capacidad de
procesamiento autónomo.
Existen varias razones técnicas para distribuir datos, en particular, los sistemas
distribuidos se adaptan mejor a las necesidades de las organizaciones descentralizadas
ya que reflejan más adecuadamente su estructura y tienen importantes ventajas con
respecto a los centralizados. La descentralización se justifica desde el punto de vista
tecnológico, ya que permite autonomía local y promueve la evolución de los sistemas y
los cambios en los requerimientos de los usuarios, proporciona una arquitectura de
sistemas simple, flexible y tolerante a fallos; además de ofrecer buenos rendimientos.
Estas razones a favor de la descentralización también añaden nuevas complejidades a su
diseño e implementación.
I N T R O D U C C I O N
2
Las diferentes técnicas de distribución de datos generalmente se basan en la semántica
de los datos, y se rigen por principios idénticos que las BD centralizadas, incorporando
otros detalles particulares, como la fragmentación de las entidades y su posterior
localización en los diferentes sitios de la red. La fragmentación es muy útil a los fines
de mejorar los tiempos de respuesta y garantizar el paralelismo de un sistema
(Johansson et al., 2000, Őzsu and Valduriez, 1999, Baião et al., 2004, Irún-Briz et al.,
2005, Lin and Veeravalli, 2006, Coulon et al., 2005). Para garantizar estas metas es
necesario desarrollar soluciones óptimas o con un grado aceptable de desempeño que
suponen la implementación de algoritmos sumamente engorrosos de una elevada
complejidad computacional. En el diseño de la distribución influyen muchos factores
relacionados con la BD, las aplicaciones que acceden a la misma, la comunicación de la
red, y sobre el sistema de computadoras que la soporta; lo que hace que sea muy
complicada la formulación de un problema de distribución. Por tanto es necesario
decidir cómo fragmentar y distribuir los datos sobre los diferentes sitios y cuáles de
estos datos deben ser replicados.
Como antecedentes a este trabajo se tienen los resultado de la tesis presentada por
(Cabrera et al., 2006) donde se obtuvieron dos asistentes de ayuda al diseño de BDD,
uno para la caracterización de las aplicaciones más relevantes que recopilaban los
parámetros de acceso y uso de estas aplicaciones a la base de datos y otro para guiar el
proceso de fragmentación, como respuesta al déficit de herramientas de apoyo al diseño
de tales bases de datos; entonces, este trabajo ayudaba a mitigar esa carencia. Ambas
herramientas presentaban algunas características que podían ser perfeccionadas y
algunos errores de ejecución que necesitaban ser corregidos; además, el asistente de
ayuda a la fragmentación necesitaba la inclusión de un nuevo método para llevar a cabo
la fragmentación horizontal derivada.
I N T R O D U C C I O N
3
La fragmentación de esquemas es una etapa del diseño de bases de datos distribuidas
donde se crean fragmentos de una relación de forma tal que se minimice el costo de
acceso a los datos durante el procesamiento de las transacciones, mejorando los tiempos
de respuesta y el paralelismo del sistema. Este proceso puede realizarse de varias
maneras; existen dos alternativas fundamentales y básicas: la fragmentación horizontal
y la vertical. Ambas necesitan tanto de información relativa a la base de datos como de
las aplicaciones que acceden a la misma. Un diseñador de bases de datos distribuidas
requiere de mucho tiempo para llevar a cabo todo este proceso, y debe tomar decisiones
de alta complejidad. Por su parte, los métodos involucrados en el diseño son, en su
mayoría, de alta complejidad computacional. Es por esto que una ayuda puede ser a
través del uso de herramientas computacionales. Consecuentemente, el problema de
investigación está dado por la existencia de características que necesitan ser
perfeccionadas en la versión anterior de las herramientas en forma de asistentes para la
caracterización de las aplicaciones y para la fragmentación, como por ejemplo: darle
más control al diseñador durante el proceso de caracterización de las aplicaciones,
ofrecer otros métodos para la fragmentación horizontal derivada, concentrar los accesos
al catálogo que mejore la gestión de los accesos al mismo.
Las preguntas de investigación son las siguientes:
1. ¿Qué características debe poseer el asistente para la caracterización de
aplicaciones que obtenga los datos relevantes para el proceso de diseño de forma
fácil y ágil?
2. ¿Qué aspectos del asistente para la fragmentación deben ser perfeccionados para
que resulte favorable para el diseñador?
I N T R O D U C C I O N
4
3. ¿Cómo adicionar otro criterio para realizar la fragmentación horizontal derivada
al fragmentador?
El objetivo general de este trabajo es obtener una nueva versión de los asistentes para
la caracterización de aplicaciones y la fragmentación que sean fáciles de usar y supere
las dificultades de las versiones anteriores.
Para lograr este objetivo se plantean los siguientes objetivos específicos de la
investigación:
1. Estudiar los principales aspectos relacionados con el diseño de fragmentación en
bases de datos distribuidas particularizando en el proceso de fragmentación.
2. Rediseñar el caracterizador de aplicaciones para que resulte fácil de usar con una
interfaz amigable.
3. Rediseñar el asistente para la fragmentación de modo que se corrijan los errores
en módulo de fragmentación vertical y se incluya un nuevo método de
fragmentación horizontal derivada.
4. Implementar los asistentes mencionados anteriormente.
Relacionado con los antecedentes antes planteados, se puede decir que este estudio se
justifica por su importancia desde el punto de vista práctico en la integración que
tendrán los resultados esperados en la herramienta SIADBDD de ayuda al diseño de
BDD. Desde el punto de vista metodológico se sistematiza en el proceso de diseño de
de BDD.
La tesis está estructurada en tres capítulos:
En el capítulo 1 se expone una panorámica de los aspectos que son particularmente
interesantes en el diseño de BDD. Se hace énfasis en el marco teórico y algunos
I N T R O D U C C I O N
5
enfoques que se le ha dado a este problema. Se realiza un análisis de los principales
trabajos reportados en la bibliografía.
En el capítulo 2 se presenta una solución práctica a la problemática de diseño
identificada para la tesis respecto a la caracterización de las aplicaciones.
En el capítulo 3 se proponen soluciones desde el punto de vista práctico a las
problemáticas de diseño de la fragmentación identificadas para la tesis.
Este trabajo de diploma culmina con las conclusiones, recomendaciones y referencias
bibliográficas.
C A P I T U L O 1
6
CAPÍTULO 1. DISEÑO DE BASES DE DATOS DISTRIBUIDAS
En este capítulo se profundiza en el marco teórico y algunos enfoques que se le ha dado
al problema de distribución de las BD. Además, se refieren los aspectos que son
particularmente interesantes en el diseño de BDD.
1.1 Aspectos generales del diseño de BDD
En muchas organizaciones geográficamente distribuidas las vías centralizadas no
representan una alternativa factible, y la migración hacia SBDD resulta natural. Muchos
autores recalcan el principio de que un sistema distribuido muestra la estructura de la
BD como un espejo de la estructura de la empresa, con lo cual se incrementa la
localidad de referencia y se reduce drásticamente el tráfico en la red (Date, 2000).
Se han ofrecido diferentes definiciones sobre qué es una BDD, una de las más
completas es la dada por (Őzsu and Valduriez, 1999), la cual aparece en la introducción
a este trabajo. La misma enfatiza los aspectos de la distribución y de la interrelación
lógica entre los datos.
El diseño de la BDD tiene como objetivo lograr un mejor desempeño; y requiere de su
propia teoría, metodología, y herramientas de apoyo. El diseño de distribución incluye
fragmentación y ubicación replicada o no de los fragmentos (Ceri and Pelagatti, 1984).
El término fragmentación se refiere a la división del esquema de una BDD de acuerdo
con algún criterio, mientras que la replicación está relacionada con la existencia de
copias de los fragmentos en varios sitios. Los dos principios básicos de las BDD (Ceri
et al., 1987, Ma et al., 2005, Őzsu and Valduriez, 1999) son reducir el intercambio de
datos entre los sitios y eliminar datos irrelevantes en la ejecución de solicitudes. Ambos
sirven de guía al proceso de diseño de BDD, el cual ha sido dividido en cuatro pasos
fundamentales (Baião et al., 2002, Bellatreche et al., 2000, Ceri et al., 1987, Hababeh et
C A P I T U L O 1
7
al., 2004, Huang and Chen, 2001, Navathe et al., 1995, Őzsu and Valduriez, 1999,
Schewe, 2002): (1) Diseño del esquema conceptual, (2) Diseño de la fragmentación, (3)
Diseño de la asignación, y (4) Diseño de la BD física. Los problemas 1 y 4 son comunes
a las Bases de Datos Centralizadas (BDC) y a las BDD, mientras que los problemas 2 y
3 caracterizan el diseño de BDD.
Este trabajo está incluido dentro de un grupo de labores donde se sigue un enfoque
descendente, en el que primero se caracterizan los esquemas globales, luego se dividen
en fragmentos; y por último estos fragmentos son ubicados en los diferentes sitios de
procesamiento. La modelación conceptual (Nelson et al., 2001) es el proceso de
creación de representaciones abstractas de un dominio de aplicación en términos de
conceptos familiares a los actores de ese dominio y no en términos técnicos. Esta
requiere de notaciones, herramientas y técnicas para representar procesos e información.
En la modelación conceptual el usuario necesita especificar información sobre los datos,
las aplicaciones, la red de comunicación y los sitios de procesamiento donde residirá la
BDD. Obtener o estimar toda la información requiere de esfuerzo y experiencia; así,
gran parte de las decisiones de diseño están fundamentadas en el buen juicio del
diseñador de la BDD.
El diseño de distribución se divide en lógico y físico. Durante el diseño lógico se
distribuyen los fragmentos en los sitios obteniéndose los Esquemas Conceptuales
Locales (ECL). En el diseño físico se llevan los ECL a los dispositivos de
almacenamiento físico. Como el diseño de la distribución de datos abarca una gran
cantidad de variables y diversidad de relaciones entre éstas, el problema del diseño se
hace complejo (Lin and Orlowska, 1995). Algunos intentos de solución separan la
fragmentación de la asignación (Huang and Chen, 2001, Őzsu and Valduriez, 1999),
mientras que otros las combinan usando diferentes enfoques (Ma et al., 2005, Ma et al.,
C A P I T U L O 1
8
2006). Una realización adecuada de estas fases se facilita a través de metodologías que
usen determinadas heurísticas y se apoyen en herramientas de ayuda al diseño (Őzsu
and Valduriez, 1999); motivación fundamental para un conjunto de trabajos que se han
venido realizando en el grupo de investigación en Bases de Datos del Centro de
Estudios de Informática de La Universidad Central de Las Villas (García et al., 2005,
Rodríguez et al., 2007a, Rodríguez et al., 2007b, Rodríguez and González, 2008,
Rodríguez et al., 2005, Rodríguez et al., 2002a, Rodríguez et al., 2007c, Rodríguez et
al., 2002b, Rodríguez et al., 2007d, Rodríguez et al., 2007e, Rodríguez et al., 2007f,
Águila, 2001, Artiles, 2001, Cabrera et al., 2006, Hernández, 2005, Morell et al., 2000b,
Morell et al., 2000a, Rosa, 2006).
El modelo lógico de las BDD fue formulado inicialmente por Ceri et al. en 1983 (Ceri et
al., 1983), actualmente considerado como un modelo clásico consolidado, incluye el
problema de cómo distribuir los datos óptimamente en los sitios de una red. Este
problema tiene como principio clave alcanzar máxima localidad de los datos,
ubicándolos tan cerca como sea posible de las aplicaciones que los utilizan, lo que
permite reducir el tráfico de comunicaciones en la red. En un sistema bien diseñado al
menos el 90 por ciento de los datos deben ser ubicados localmente y hasta el 10 por
ciento pueden ser accedidos remotamente (Ceri et al., 1987).
1.2 El problema de distribución de datos
El problema de distribución de datos abarca tanto la fragmentación como la asignación
de los fragmentos a los diferentes sitios de procesamiento de la red de comunicación. En
este trabajo se aborda solamente la fragmentación como se puede observar en el
capítulo 3.
C A P I T U L O 1
9
El diseño de la fragmentación refleja el criterio de mantener los datos locales en el sitio
donde frecuentemente son accedidos por las aplicaciones, es por ello que los fragmentos
constituyen una unidad apropiada de asignación. Un esquema no es una unidad de
asignación por un gran número de razones. Primero, las aplicaciones usualmente operan
sobre subconjuntos de esquemas. Por tanto, la localidad de accesos de aplicaciones no
es definida sobre esquemas completos sino sobre sus subconjuntos. De aquí que sea
natural considerar estos subconjuntos como las unidades de distribución. Segundo, si las
aplicaciones que manipulan un esquema están ubicadas en sitios diferentes, se pueden
seguir dos alternativas con todo el esquema como unidad de distribución. O bien el
esquema no está replicado y es asignado a un sólo sitio, o éste se encuentra replicado en
todos o en algunos de los sitios donde las aplicaciones residen.
Finalmente, se puede argumentar a favor de la fragmentación que al tratar la
descomposición de un esquema en fragmentos como unidades de asignación, se está
facilitando la ejecución concurrente de un gran número de aplicaciones y por lo tanto
mejora el desempeño de un sistema. También, la fragmentación facilita que la ejecución
de una sola solicitud se pueda dividir en un conjunto de subsolicitudes que operen sobre
los fragmentos, posibilitándose el paralelismo (Johansson et al., 2000, Gançarski et al.,
2002, Bhalla and Hasegawa, 2005).
Muchos de los problemas relacionados con la fragmentación y asignación en el diseño
de BDD tienen una modelación matemática compleja y los métodos que les dan
solución son considerados del tipo NP-Completo (Baião et al., 2003, Őzsu and
Valduriez, 1999, Lee and Baik, 2004, Pérez et al., 2005), donde no hay garantía de
encontrar una solución óptima con algoritmos determinísticos en un tiempo polinomial.
Así, su complejidad es tal que cualquier algoritmo que resuelve óptimamente cada uno
de sus casos requiere un esfuerzo computacional que crece exponencialmente en
C A P I T U L O 1
10
función del tamaño del problema; en dependencia de la cantidad de fragmentos y de
sitios. Intentando dar solución a estos problemas se han presentado propuestas (Baião et
al., 2004, Pérez et al., 2005, Savonnet et al., 1999, Tamhankar and Ram, 1998, Navathe
et al., 1995, Mei and Sheng, 1992, Ceri et al., 1987, Ceri and Pernici, 1985) que
sugieren el uso de heurísticas para algunos de ellos.
1.3 El problema de fragmentación
La mayoría de los autores coinciden en establecer dos vías básicas para fragmentar:
horizontal (FH) y vertical (FV) (Ma et al., 2006, Ezeife and Barker, 1995, Bellatreche et
al., 1996, Bellatreche et al., 1997, Pérez et al., 2000, Lim and Ng, 1997, Huang and
Chen, 2001, Navathe et al., 1995, Hababeh et al., 2004, Bellatreche and Simonet, 1996).
El proceso de fragmentación debe asegurar la ausencia de cambios semánticos en la BD
durante el proceso, logrando así una fragmentación correcta (Őzsu and Valduriez,
1999).
El grado de fragmentación va de un extremo, que es la no fragmentación, a otro
extremo, que es fragmentar hasta el nivel de tuplas individuales (en el caso de la FH) o
hasta el nivel de atributos individuales (en el caso de FV). Tener muy pocas, o
demasiadas unidades de fragmentación puede tener efectos adversos. Es necesario
encontrar un nivel apropiado de fragmentación que sea un término medio entre los dos
extremos. Tal nivel sólo puede ser definido con respecto a las aplicaciones que deben
ser soportadas sobre la BD, pero requiere decidir cómo hacerlo.
1.3.1 Fragmentación horizontal
La FH se divide en fragmentación horizontal primaria (FHP) y derivada (FHD). Bajo un
enfoque relacional, la FH divide la relación en conjuntos disjuntos aplicando el
operador de selección (Őzsu and Valduriez, 1999) y presumen que el diseñador tiene la
C A P I T U L O 1
11
capacidad de pronosticar las características de las aplicaciones con respecto a los datos
y la frecuencia de ejecución de estas aplicaciones desde cada uno de los sitios de
procesamiento (Bellatreche et al., 2000, Ceri et al., 1982, Ma and Schewe, 2004, Ezeife
and Dey, 2003). Comúnmente, la FHP de una relación se desarrolla empleando el
método clásico de uso de predicados simples definidos en un esquema (Ceri and
Pelagatti, 1984, Őzsu and Valduriez, 1999). Las aplicaciones generalmente emplean
predicados minterms, que son conjunciones de predicados simples con una cantidad
mínima de términos, como fórmula para realizar la selección de tuplas. Además, se
requiere información cuantitativa relativa a los patrones de acceso y uso de las
aplicaciones. La FHD identifica aquellas relaciones que se deben priorizar en el proceso
de fragmentación, ya sea por su llave primaria (esquemas propietarios) o por su llave
foránea (esquemas miembros) (Ceri and Pernici, 1985). La FHD se define sobre un
esquema miembro de acuerdo a una operación de semiacople (semijoin, denotado
simbólicamente por ⋉) con el esquema propietario. Cuando existe más de una
posibilidad de FHD, se elige la FHD con mejores características de acople (join,
denotado simbólicamente por ⋈), o la empleada en más aplicaciones (Őzsu and
Valduriez, 1999). Se han formalizado criterios para determinar las mejores
características de acople (Őzsu and Valduriez, 1999, Rodríguez and González, 2008).
Por tanto, la FHP favorece las operaciones de selección, y la FHD facilita el tratamiento
de las llaves foráneas.
Fragmentación horizontal primaria
Comúnmente, bajo un enfoque relacional, la FHP de una relación se desarrolla
empleando el método clásico de uso de predicados definidos en esa relación
(Bellatreche et al., 2000, Ma et al., 2006, Őzsu and Valduriez, 1999). Esta variante está
C A P I T U L O 1
12
orientada a maximizar localidad de procesamiento, y trata de lograr que los datos estén
lo más cerca posible de las aplicaciones que las usan. Para realizar la FH es necesario
proporcionar información acerca de las relaciones que componen la BD y de las
aplicaciones que las utilizan. No siempre es posible investigar y caracterizar todas las
aplicaciones que actuarán sobre la BD, pero al menos se pueden caracterizar las más
importantes. Para esto se utiliza la regla 20/80, o sea, se caracteriza el 20 por ciento de
las aplicaciones más frecuentes o que realizan las aplicaciones más críticas que son las
que realizan la mayor parte de los accesos a datos (Ceri et al., 1983, Őzsu and
Valduriez, 1999, Ma et al., 2006). En la caracterización de las aplicaciones es necesario
determinar los predicados simples (Őzsu and Valduriez, 1999) que favorecen la
localidad de distribución.
Las aplicaciones emplean predicados simples y predicados más complejos, resultado de
combinaciones lógicas de los predicados simples; una combinación especialmente
importante es la conjunción de predicados simples denominada predicado minterm
(Őzsu and Valduriez, 1999). Partiendo de que siempre es posible transformar una
expresión lógica en su forma normal conjuntiva, se usan los predicados minterms en los
algoritmos para no causar ninguna pérdida de generalidad. Cada predicado minterm
puede contener la forma natural o 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 (Őzsu and Valduriez, 1999).
La información cuantitativa relativa a las aplicaciones que es necesaria para la FHP
involucra la selectividad de cada predicado minterm y la frecuencia con la que la misma
accede a los datos.
C A P I T U L O 1
13
La FHP se define sobre un esquema de la BD aplicando una fórmula de selección para
obtener los fragmentos minterms que se corresponden con cada predicado minterm. El
algoritmo HORIZONTALP expuesto en (Őzsu and Valduriez, 1999) asume lo antes
mencionado y hace uso del método COM_MIN que establece un conjunto de
predicados con las propiedades de completitud y minimalidad. Para la completitud es
necesario y suficiente que exista una probabilidad idéntica de acceder por cada
aplicación a cualquier fragmento minterm. La minimalidad es un estado que indica el
grado de influencia de un predicado en el desarrollo de la fragmentación; es decir, el
predicado simple debe ser relevante para provocar la fragmentación. Si todos los
predicados de un conjunto de predicados simples son relevantes; el conjunto es mínimo.
Se puede apreciar como la definición de completitud de un conjunto de predicados
simples difiere de la regla de completitud de la fragmentación. Una definición formal de
la relevancia se da en (Ceri et al., 1983), aunque siempre es aconsejable acudir a la
habilidad y experiencia de los diseñadores antes de utilizar tal definición formal. En
(Őzsu and Valduriez, 1999) se hace un análisis de la corrección de la FHP realizada con
HORIZONTALP de acuerdo a las reglas de fragmentación antes planteadas.
Fragmentación horizontal derivada
Se realiza la FHD a un esquema con al menos una llave foránea que haga referencia a
otro esquema fragmentado mediante una FHP. Ceri y Pernici (Ceri and Pernici, 1985)
identifican aquellos esquemas que se deben priorizar en el proceso de fragmentación, ya
sea por su llave primaria (esquemas propietarios) o por su llave foránea (esquemas
miembros). La FHD se define sobre un esquema miembro de acuerdo a una operación
de semiacople con su esquema propietario y es por ello que el fragmento resultante se
define únicamente sobre los atributos del esquema miembro. Por tanto, si un esquema R
C A P I T U L O 1
14
tiene una llave foránea (miembro) que referencia al esquema S (propietario), los
fragmentos horizontales derivados de R se definen como (Őzsu and Valduriez, 1999):
Ri = R ⋉ Si, 1 ≤ i ≤ w,
donde w es el número de fragmentos definidos sobre R, y Si = σFi(S), Fi es la fórmula
según la cual se define el fragmento horizontal primario Si.
El algoritmo de FHD es similar a HORIZONTALP tomando como entradas el conjunto
de fragmentos del esquema propietario, el esquema miembro y el conjunto de
predicados de semiacople entre el propietario y el miembro. En un esquema de BD
resulta frecuente que existan más de dos enlaces sobre un esquema R. En este caso
existe más de una posibilidad de FHD. Para esto se elige la FHD con mejores
características de acople, o la empleada en más aplicaciones para facilitar el acceso a los
usuarios que hagan mayor uso de los datos, minimizando el impacto total en el
rendimiento de un sistema (Őzsu and Valduriez, 1999). No es tan sencillo elegir el
criterio relacionado con las mejores características de acople, que beneficia a las
aplicaciones que hagan operaciones de acople sobre dos esquemas. Al poder realizarlo
sobre fragmentos más pequeños y posibilitar la realización de acoples de manera
distribuida, se enfatiza la esencia de las BDD. Un sistema puede mejorar sus tiempos de
respuesta si, además de estar ejecutando un número de aplicaciones en diferentes sitios,
puede ejecutar una aplicación en paralelo.
1.3.2 Fragmentación vertical
La FV no es más que la división de una relación en fragmentos mediante una operación
de proyección, cada uno de los cuales contiene un subconjunto de los atributos de la
relación original. Su principal objetivo es mejorar el rendimiento de las transacciones;
para esto los fragmentos deben ser diseñados de tal manera que las aplicaciones accedan
C A P I T U L O 1
15
al menor número de atributos irrelevantes o innecesarios que incrementen los costos de
almacenamiento y procesamiento, especialmente cuando el número de tuplas
involucradas es muy grande. En una BDD, cuando los atributos relevantes están en
diferentes fragmentos de datos y localizados en diferentes sitios, se genera un costo
adicional debido al acceso de datos remotos. Por esto, una de las características
deseables de una BDD que se debe favorecer con la FV, es la accesibilidad local en
cualquier sitio.
Si cada aplicación accediera a un subconjunto diferente y disjunto de atributos, el diseño
de la fragmentación vertical sería obvio; sin embargo, en la práctica, lo más común es
que las aplicaciones accedan a conjuntos de atributos diferentes y solapados. Un aspecto
a decidir es si los fragmentos van a ser solapados o disjuntos. En el primer caso, los
fragmentos se adaptan mejor a los requerimientos de las aplicaciones al aumentar las
posibilidades de encontrar en un solo fragmento los datos requeridos. Esto aumenta la
complejidad de un sistema y los esfuerzos por mantener la consistencia de la BD. En el
segundo caso no hay redundancia, pero una determinada fragmentación puede afectar
aquellas aplicaciones que al ejecutarse usen atributos de más de un fragmento, siendo
necesaria la realización de un acople, operación que es costosa, en particular cuando los
fragmentos se encuentran en distintos sitios de la red.
Por tanto, no basta con maximizar el número de aplicaciones que acceden a un solo
fragmento y minimizar las que acceden a más de uno, sino que es necesario evaluar
cómo influye una determinada fragmentación en el rendimiento total de un sistema.
Para esto se debería tener en cuenta toda una serie de aspectos como son: la frecuencia
de activación de las transacciones, los métodos de acceso empleados, las estrategias de
procesamiento de transacciones, costos de transmisión y posibilidad de replicación,
entre otros.
C A P I T U L O 1
16
Una solución teórica simple al problema de la FV sería escoger un criterio o función
objetivo, evaluarlo para todas las posibles particiones y seleccionar aquella que optimiza
el criterio. Esta solución tiene dos grandes dificultades: Primero, la obtención de una
función objetivo que convierta todos los aspectos enumerados anteriormente en un
modelo matemático razonable; segundo, el número posible de particiones es muy
grande, incluso para un número moderado de atributos, de manera que incluso evaluar
el criterio más simple para todas las particiones no resulta factible. El número total de
particiones en una relación con n atributos está dado por el n-ésimo número de Bell
B(n) (Őzsu and Valduriez, 1999), donde n es el número de atributos de la relación. Para
valores grandes de n, B(n)≈ nn. Esto conduce a la idea, bastante aceptada, de que es
inútil buscar soluciones óptimas exactas al problema de la FV, y es necesario recurrir a
heurísticas que disminuyan el espacio de solución. Cuando éstas son usadas, se obtiene
una solución cercana a la óptima para la partición de los atributos, usando un proceso de
minimización paso a paso. En este caso se comienza con una partición y se intenta
derivar de ella una nueva partición que sea superior a la original por el hecho de que la
BD fragmentada de acuerdo a la nueva partición tendrá un menor costo de
procesamiento. Cuando esto es logrado, la heurística trata de obtener mejoras a partir de
la nueva partición derivada. Cada vez que tiene éxito mejorar una partición, mejora el
rendimiento de la BD. Este proceso continúa hasta que no se puedan hacer mejoras a la
última fragmentación obtenida; por tanto, ésta será el resultado de la heurística de
fragmentación de atributos. Desde este punto de vista existen dos alternativas:
agrupamiento y particionamiento. La primera considera inicialmente cada atributo como
un fragmento, y a partir de ahí va uniendo los fragmentos entre sí para obtener las
particiones candidatas. La segunda se inicia de un solo fragmento que abarca toda la
relación y va dividiéndolo para ir obteniendo los nuevos fragmentos candidatos. Esta
C A P I T U L O 1
17
última se considera la más apropiada pues la solución óptima debe estar más cerca de la
relación original y no de fragmentos compuestos por cada atributo independiente.
El concepto de usar la FV con el objetivo de mejorar el rendimiento de los Sistemas
Manejadores de BD (SMBD) ha aparecido con frecuencia en la literatura, y aparecen
trabajos que buscan una solución óptima del problema y otros que usan heurísticas para
hallar la solución. En general, la FV proyecta una relación en subconjuntos de sus
atributos conservando la llave en cada proyección, que puede ser recompuesta
posteriormente mediante el operador de acople.
Hoffer y Severance (Hoffer and Severance, 1975a) miden la afinidad entre cada par de
atributos construyendo una Matriz de Afinidad de Atributos (AA) que sirve de base para
agrupar los atributos en clusters usando el Algoritmo de Energía de Enlace (BEA,
acrónimo del inglés Bond Energy Algorithm) desarrollado en (McCormick et al.,
1972b). Esto permite reducir grandemente el número de fragmentos a evaluar en las
fases posteriores del diseño. Este algoritmo se considera apropiado ya que está diseñado
específicamente para determinar grupos de elementos similares y no una ordenación
lineal de estos, el agrupamiento final no depende del orden en que los elementos fueron
presentados al algoritmo, y la complejidad del algoritmo es razonable, del orden de O(n)
donde n es el número de atributos. Se puede decir que la simetría de la matriz AA
permite la permutación en parejas de filas y columnas, lo que reduce su complejidad. En
dicho trabajo se deja al criterio subjetivo del diseñador la selección de los grupos de
atributos que formarán los fragmentos. Además, la similitud entre un par de atributos
puede ser inadecuada si no se tiene en cuenta la similitud entre grupos mayores de
atributos. Este trabajo sirvió de motivación para la mayoría de los trabajos siguientes
sobre fragmentación vertical.
C A P I T U L O 1
18
Navathe et al. (Navathe et al., 1984b) dividen el problema en dos etapas. Primeramente
efectúan la fragmentación de las relaciones aplicando diferentes funciones objetivo
empíricas que agrupan los atributos extendiendo los trabajos de Hoffer y Severance
(Hoffer and Severance, 1975a) mediante el algoritmo BEA. Estos algoritmos
determinan grupos de atributos en fragmentos solapados y no solapados aplicando FV a
tres tipos de BD (distribuidas, sin jerarquía de memoria, y con jerarquía de memoria)
con el objetivo de minimizar el número de fragmentos que usa una aplicación, y refinar
los fragmentos usando factores de costo que reflejan el ambiente físico donde se
almacena la BD. Posteriormente se realiza la ubicación replicada o no de fragmentos a
sitios, de forma que se maximice el procesamiento local de aplicaciones aplicando un
algoritmo heurístico de tipo goloso (greedy). La metodología empleada es de
particionamiento en lugar de agrupamiento.
Cornell y Yu (Cornell and Yu, 1987) optimizaron el trabajo de Ceri (Ceri and Pernici,
1985) desarrollando un algoritmo para la FV, que obtiene una partición binaria óptima
para BD relacionales usando información de factores físicos para disminuir el número
de accesos a disco. Posteriores refinamientos son logrados aplicando un algoritmo de
partición binaria iterativamente.
Öszu y Valduriez (Őzsu and Valduriez, 1999) discuten este trabajo previo sobre FV en
BDD usando información de las frecuencias de acceso y aplican el algoritmo BEA. Los
grupos de atributos son clusterizados y se usan ecuaciones de costo para definir la mejor
posición a lo largo de la diagonal de la matriz clusterizada para dividir la relación en
fragmentos. Los factores de costo reflejan el ambiente físico en el que los fragmentos
van a estar almacenados.
Muthuraj et al. (Muthuraj et al., 1993) presentan un trabajo donde se argumenta que los
primeros algoritmos para la FV son ad hoc, por eso se propone una función objetivo
C A P I T U L O 1
19
llamada Evaluador de Particiones para determinar la calidad de las particiones
generadas por varios algoritmos. Dicho evaluador consta de dos términos: los costos por
accesos a atributos locales irrelevantes y los costos por acceder a atributos remotos
relevantes. El primero mide los costos del procesamiento local de las aplicaciones
debido a accesos a atributos irrelevantes, y el segundo mide los costos del
procesamiento remoto debido a las aplicaciones remotas que acceden a atributos
relevantes. Se estudia explícitamente el problema referente a la FV n-aria. Esta
fragmentación se efectúa con distintos propósitos, como por ejemplo en los SBDD, en
la cual se crean fragmentos para ubicarlos en los diferentes sitios de la red, o también en
los SBD centralizadas a fin de ubicar los fragmentos dentro de diferentes jerarquías de
memoria.
En resumen, la FV se usa durante el diseño de la BDD para mejorar el rendimiento de
las transacciones, incrementar el procesamiento local y minimizar el acceso a datos
remotos, aumentar el paralelismo durante la ejecución de las consultas, la concurrencia
y el rendimiento.
1.3.3 Fragmentación mixta
Existe otra estrategia de fragmentación denominada mixta (FM), donde
simultáneamente se aplican ambos tipos (FH y FV) al mismo esquema. Esta estrategia
no es considerada básica, pero es obvio que muchas particiones de la vida real pueden
ser mixtas. La FM es generada a través de la aplicación recursiva de operadores del
álgebra relacional en los fragmentos.
La fragmentación mixta puede ser convenientemente representada por un árbol de
fragmentación, en el cual la raíz corresponda a la relación global, las ramas
correspondan a los fragmentos y los nodos intermedios correspondan a resultados
C A P I T U L O 1
20
intermedios de las expresiones de fragmentación definidas (véase la figura 1.1). Los
nodos hijos de un nodo determinado representan la descomposición de este nodo por
una operación de fragmentación (Ceri and Pelagatti, 1984), (Őzsu and Patrick, 1999).
Figura 1.1 Árbol de Fragmentación Mixta
Como se ha podido observar, para el diseño de la fragmentación se necesita una gran
variedad de información difícil de obtener, y demanda experiencia en los diseñadores;
así como los métodos para dar solución a los problemas planteados son de una elevada
complejidad computacional, por lo que se sugiere el uso de heurísticas que permitan
obtener soluciones con menor esfuerzo.
1.4 El problema de caracterización de las aplicaciones
En la literatura aparecen dispersos los requerimientos del universo de discurso en varios
momentos del proceso de modelación. En el presente trabajo se aborda la
sistematización del proceso de caracterización de las aplicaciones. Así es necesario
captar la información sobre los patrones de acceso y uso de las aplicaciones sobre la
BD, de utilidad en el diseño de la distribución. El diseñador, bien por su experiencia o
estudios realizados, determina qué caracteriza a las aplicaciones activadas con mayor
C A P I T U L O 1
21
frecuencia. En realidad no siempre se pueden caracterizar todas las aplicaciones que
operan sobre la BD, pero al menos se caracteriza el 20 por ciento de las aplicaciones
más frecuentes o que realizan las aplicaciones más críticas en cuanto a volúmenes de
accesos a datos.
En el proceso de caracterización de las aplicaciones se solicita al diseñador la entrada de
la siguiente información:
Nombre o descriptor que identifique cada aplicación.
Esquemas que usa.
Para una potencial FV y su posterior asignación se hace necesario capturar:
Atributos de cada esquema usados por la aplicación así como el tipo de acceso de
lectura y/o escritura sobre cada atributo.
Selectividad de cada esquema que significa la cantidad estimada de tuplas a las que
accede la aplicación.
Sitios donde se activa cada aplicación y la frecuencia con que lo hace en cada sitio.
Para una potencial FHP y su posterior asignación se hace necesario capturar:
Predicados simples. Para sistematizar la modelación con la intención de favorecer la
localidad de procesamiento es útil adquirir los principios de localidad desde la
perspectiva de las aplicaciones mediante predicados simples y brindar al diseñador sólo
aquellos esquemas que sean usados por alguna aplicación.
1.5 Conclusiones parciales
El diseño de BDD requiere de mucho tiempo y los métodos involucrados en el mismo
son de alta complejidad computacional. Tanto la fragmentación como la asignación
requieren variada información acerca de los esquemas de la BD, las aplicaciones, los
C A P I T U L O 1
22
sitios y las redes de comunicación, pero cada cual ignora cómo la otra captura y usa esta
información. Cualquier metodología que lo intente puede ser muy compleja. Es por esto
que una ayuda puede ser a través del uso de herramientas computacionales. Como
antecedente se han desarrollado dos herramientas de ayuda, una para recopilar los
parámetros de acceso y uso de las aplicaciones, y otra para ayudar a la fragmentación
que aún poseen características objeto de perfección, adaptación y corrección.
Así, la hipótesis de esta investigación se formula de la forma siguiente:
Una versión mejorada de los asistentes para la caracterización de aplicaciones y la
fragmentación de esquemas utilizados en el diseño lógico de BDD permitirá realizar el
proceso de diseño de forma fácil, correcta y efectiva.
C A P I T U L O 2
23
CAPÍTULO 2. CARACTERIZACIÓN DE APLICACIONES EN EL
DISEÑO DE BDD
En este capítulo se hace énfasis en el funcionamiento de la herramienta para
caracterizar a las aplicaciones, así como al uso que recibe la información que a través de
ella se recepciona.
2.1 Características de la información sobre las aplicaciones
En la literatura aparecen dispersos los requerimientos del universo de discurso en varios
momentos del proceso de modelación. Antes de comenzar el proceso de fragmentación
el diseñador debe poseer información de la base de datos e información de las
aplicaciones (Ceri and Pelagatti, 1984), (Ceri et al., 1989), (Őzsu and Valduriez, 1999).
La información de la base de datos es la concerniente al esquema conceptual global, en
el cual es necesario representar las relaciones, sus atributos y la conexión entre
relaciones.
La información de las aplicaciones debe representarse en términos cualitativos y
cuantitativos. La cualitativa guía la actividad de fragmentación, mientras que la
información cuantitativa se incorpora fundamentalmente a los modelos de localización.
2.1.1 Información cualitativa
La principal información cualitativa describe los predicados que satisfacen las
aplicaciones de los usuarios. Dichos predicados deben guiar la localidad de las
aplicaciones, es por ello que se definen en base a predicados elementales o simples que
los usuarios suministran para indicar las agrupaciones físicas de los datos que se
presentan para las diferentes aplicaciones, y luego estos predicados simples se combinan
C A P I T U L O 2
24
adecuadamente para reflejar, por último, la localidad integrada del grupo de
aplicaciones.
Los predicados simples pj son expresiones formadas por las cláusulas:
pj : < Ai > <operador> <Valor>,
donde <Ai> es un atributo que pertenece a la relación R y debe estar definido sobre un
dominio Di, <operador> ∈ {=, <, ≤, >, ≥} y <valor> es seleccionado del dominio de Ai
(Valor ∈ Di).
Frecuentemente, las solicitudes de usuarios requieren predicados más complejos que
pueden expresarse como combinaciones booleanas de predicados simples. Los
predicados minterms son un tipo de combinación que puede definirse como la
conjunción de todos los predicados simples tanto en su forma natural como negada
(Őzsu and Valduriez, 1999).
Así, para un conjunto de predicados simples Pri = {pi1, pi2,..., pim}, el conjunto de
predicados minterm Mi = { mi1, mi2,..., miz } se define como:
Mi = { mij| mij = Λ pik*}, 1 ≤ k ≤ m, 1 ≤ j ≤ z donde pik
* = pik o pik*= ⎤ pik.
pik ∈ Pri
Los predicados de selección o predicados simples, a partir de los cuales se hallan los
predicados minterms, que determinan el proceso de fragmentación deben poseer dos
propiedades fundamentales para garantizar una fragmentación correcta y eficiente:
completitud y minimalidad.
Un conjunto de predicados Pr es completo si garantiza, para cada aplicación del
conjunto de aplicaciones, que dos tuplas cualesquiera de un mismo fragmento sean
accedidas con igual probabilidad. Esta propiedad permite que todos los elementos de un
C A P I T U L O 2
25
fragmento sean referenciados de forma homogénea por cada aplicación. Por su parte, la
minimalidad es una propiedad mucho más intuitiva y generalmente se apela a la
experiencia y sentido común del diseñador más que al empleo de técnicas formales. El
conjunto de predicados Pr es minimal si todos los predicados son relevantes en la
determinación de la fragmentación, o sea, si para cada predicado pj, que causa que la
relación R se fragmente en Ri y Rj, existe al menos una aplicación que accede de forma
diferente a ambos fragmentos. Se puede afirmar que un conjunto minimal es siempre
completo, sin embargo lo contrario no siempre es verdadero.
2.1.2 Información cuantitativa
Con respecto a la información cuantitativa acerca de las aplicaciones es necesario
conocer:
• Selectividad del minterm. Número de tuplas de la relación que pueden ser
accedidas por una solicitud especificada acorde a un predicado minterm dado.
• Frecuencia de acceso. Frecuencia con la que las aplicaciones acceden a los
datos, o sea, frecuencia de activación de la aplicación en cada sitio.
• El tipo de acceso (lectura o escritura) realizado por la aplicación a cada objeto de
datos.
Todos los datos de entrada a este asistente se encuentras en las tablas:
• Schemata
• GlobalAttributes
• Sites
Una vez introducida toda la información esta se almacena al catálogo en las tablas
siguientes:
C A P I T U L O 2
26
• Applications
• App_Schemata
• App_Attribute
• App_Site
• Predicates
2.2 Diagramas de clases del asistente AppWizard
La información que la herramienta permite captar puede dividirse en grupos o
categorías. Estas son: el acceso de la aplicación a los esquemas, a los atributos, la
definición de los predicados simples y los sitios donde se activa. Para manejar esta
información que difiere de una categoría a otra, se implementaron las clases TSchema,
TAttribute, TPredicate y TSites respectivamente, con el objetivo de independizar el
trabajo con el catálogo del diseño. La colaboración de las clases entre sí se realiza a
través de TCharacterizer. La figura 2.1 muestra la colaboración entre las clases
implementadas para la construcción del asistente, así como una vista de sus atributos y
métodos.
C A P I T U L O 2
27
Figura 2.1 Diagrama de clases del AppWizard.
2.3 Interfaz del asistente AppWizard
En este trabajo se sistematiza el proceso de caracterización de las aplicaciones más
relevantes mediante la herramienta AppWizard. Esta herramienta capta la información
sobre los patrones de acceso y uso de las aplicaciones sobre la BD, de utilidad en el
diseño de la distribución. Esta herramienta tiene forma de asistente capaz de introducir
en el catálogo, elemento integrador del diseño, los datos que el diseñador, bien por su
C A P I T U L O 2
28
experiencia o estudios realizados, determina que caracterizan a las aplicaciones
activadas con mayor frecuencia. Como se expresó en el capítulo 1, no siempre se
pueden caracterizar todas las aplicaciones que operan sobre la BD, pero al menos se
debe caracterizar el 20 por ciento de las aplicaciones más frecuentes o que realizan las
aplicaciones más críticas en cuanto a volúmenes de accesos a datos.
En el proceso de caracterización de las aplicaciones, esta herramienta solicita al
diseñador la entrada de la siguiente información: nombre o descriptor que identifique
cada aplicación, esquemas que usa.
Para una potencial FV y su posterior asignación se hace necesario capturar: atributos de
cada esquema usados por la aplicación así como el tipo de acceso de lectura y/o
escritura sobre cada atributo, selectividad de cada esquema que significa la cantidad
estimada de tuplas a las que accede la aplicación, sitios donde se activa cada aplicación
y la frecuencia con que lo hace en cada sitio. Para una potencial FHP y su posterior
asignación se hace necesario capturar: predicados simples. Para sistematizar la
modelación con la intención de favorecer la localidad de procesamiento se tomó la
decisión de adquirir los principios de localidad desde la perspectiva de las aplicaciones
mediante predicados simples y brindar al diseñador sólo aquellos esquemas que sean
usados por alguna aplicación. La captura de estos predicados simples se realiza
mediante un constructor de expresiones que, a la vez que permite su edición, realiza la
validación de los predicados (véase la figura 2.2).
C A P I T U L O 2
29
Figura 2.2 Edición de los predicados simples.
1- Eliminar los predicados simples que estén seleccionados.
2- Eliminar todos los predicados simples.
3- Seleccionar el operador (<, >, <=, >=, =).
4- Seleccionar o no para determinar si sobre él actuará 1.
5- Doble clic para seleccionar el atributo.
Los datos de entrada al asistente son obtenidos por ERECASE (Álvarez et al., 2006) y
NetWizard (Rodríguez et al., 2007b) y depositados en el catálogo compartido por las
aplicaciones desarrolladas en el Laboratorio de Bases de Datos del Centro de Estudios
de Informática de la Universidad Central de Las Villas (Rodríguez and González, 2008).
Las salidas se guardan en este catálogo, quedando disponibles para las herramientas que
continúan con el proceso de diseño, o ejecuciones posteriores de este asistente.
1 2
3
4
5
C A P I T U L O 2
30
2.4 Conclusiones parciales
El asistente AppWizard obtenido colabora con las otras herramientas referidas en el
acápite anterior como ayuda al diseño de BDD, aunque puede usarse de forma
independiente. Esta herramienta les permite a los diseñadores caracterizar las
principales aplicaciones en forma de asistente fácil de usar para capturar una gran
variedad de información sobre las aplicaciones más representativas en el universo de
discurso objeto de modelación.
C A P I T U L O 3
31
CAPÍTULO 3. ASISTENTE PARA LA FRAGMENTACIÓN
En este capítulo se describen las metodologías y los algoritmos que se utilizaron a la
hora de la creación del asistente para la guía del proceso de la fragmentación de BD.
3.1 Fragmentación horizontal
Para realizar la FH, como se vio en el Capítulo 1, es necesario tener información acerca
de la BD y de las aplicaciones que las utilizan. La información necesaria sobre la BD es
la referida al esquema conceptual global. En este sentido es importante tener las
relaciones que lo componen, la cardinalidad de cada relación y las dependencias entre
ellas. De aquí se tienen los esquemas candidatos a ser fragmentados. Como se expresó
en el capítulo 2, AppWizard caracteriza las aplicaciones más relevantes, en particular
obtiene los predicados simples definidos por el usuario.
3.1.1 Algoritmo para la fragmentación horizontal primaria
Un fragmento se define como el conjunto de todas las tuplas que satisfacen un
predicado minterm.
Rj = σFj (R), 1≤ j ≤ w (w representa la cantidad de predicados minterms).
Como se expuso en el Capítulo 2, para que los fragmentos minterms reflejen
correctamente la fragmentación, el conjunto de predicados simples que le sirve de base,
debe cumplir determinadas propiedades, como ser completo y minimal.
El primer paso para la FHP consiste en obtener un conjunto de predicados simples
mínimos y completos Pr’, a partir del conjunto de predicados simples Pr, definido por
el diseñador a través del caracterizador de aplicaciones.
El siguiente método permite construir P completo y minimal.
C A P I T U L O 3
32
Regla 1: Regla fundamental de completitud y minimalidad; dividir una relación o
fragmento en al menos dos partes que sean accedidas de forma diferente por al menos
una aplicación acorde a un predicado p1. Sea P= p1
Método:
Considerar un nuevo predicado pi que particione al menos a un fragmento en dos
partes que sean referenciadas en una forma diferente por al menor una
aplicación.
Sea P= P ∪ pi,
Eliminar predicados no relevantes de P.
Repetir este método hasta que P sea completo.
Para implementar éste método se puede seguir el algoritmo iterativo denominado
COM_MIN (Őzsu and Valduriez, 1999), donde se usa la siguiente notación.
Fi de PM: Fragmento fi respecto a un predicado minterm definido sobre lo predicados de
PM.
Algoritmo COM_MIN
Entrada:
R: relación
Pr: conjunto de predicados simples
Salida:
Pr’: conjunto de predicados simples
Declarar
F: conjunto de predicados minterms
C A P I T U L O 3
33
Inicio
encontrar un pi ∈ Pr tal que pi parta a R de acuerdo con la Regla 1;
Pr’←pi
Pr←Pr – pi
F←fi // fi es el fragmento minterm respecto a pi
hacer
inicio
encontrar un pj ∈ Pr tal que pj parta a un fk de Pr’ de acuerdo
con la Regla 1;
Pr’←Pr’∪pj
Pr←Pr – pj
F←F∪fj
si ∃pk∈Pr’ irrelevante entonces
inicio
Pr’←Pr’ – pk
F←F – fk
fin-si
fin-inicio
hasta que Pr’ esté completo
Fin. {COM_MIN}
C A P I T U L O 3
34
El segundo paso es derivar el conjunto de predicados minterms que pueden definirse
sobre los predicados del conjunto Pr’. Estos predicados minterms establecen los
fragmentos candidatos para el proceso de asignación.
El establecimiento de los predicados minterms es trivial; la dificultad radica en el
tamaño del conjunto, que puede ser muy grande (de hecho, exponencial respecto al
número de predicados simples).
El tercer paso aborda la eliminación de algunos fragmentos minterms que puedan ser
redundantes. Esta eliminación se desarrolla identificando aquellos minterms que puedan
resultar contradictorios sobre un conjunto de implicaciones I. Por ejemplo, si Pr’ = {p1,
p2}, donde
p1: atributo = valor_1
p2: atributo = valor_2
y el dominio de atributo es {valor_1, valor_2}, es obvio que I contiene las dos
implicaciones siguientes
i1: (atributo = valor_1) ⇒ ¬(atributo = valor_2)
i2: ¬(atributo = valor_1) ⇒ (atributo = valor_2)
Los siguientes cuatro predicados minterms se definen de acuerdo a Pr’:
m1: (atributo = valor_1) ∧ (atributo = valor_2)
m2: (atributo = valor_1) ∧ ¬(atributo = valor_2)
m3: ¬(atributo = valor_1) ∧ (atributo = valor_2)
m4: ¬(atributo = valor_1) ∧ ¬(atributo = valor_2)
C A P I T U L O 3
35
En este caso los predicados minterms m1 y m4 resultan contradictorios respecto a las
implicaciones I y pueden eliminarse de M.
La entrada al algoritmo HORIZONTALP (Őzsu and Valduriez, 1999) es una relación Ri
sujeta a la fragmentación, y Pri, el conjunto de predicados simples que se establecieron
de acuerdo a las aplicaciones definidas sobre la relación Ri.
Algoritmo HORIZONTALP
Entrada:
Ri: relación
Pri: conjunto de predicados simples
Salida:
Mi: conjunto de fragmentos minterms
Inicio
Pr’i←COM_MIN(Ri, Pri) // construir Pr’i completo y minimal
determinar el conjunto Mi de predicados minterms;
determinar el conjunto Ii de implicaciones de pi∈Pr’i;
para cada mi∈Mi hacer
si mi es contradictorio respecto a I
entonces
Mi←Mi – mi
fin-si
fin-para
Fin. {HORIZONTALP}
Conjunto de predicados simples mínimo y completo
La esencia del algoritmo COM_MIN es eliminar los predicados redundantes para
producir un conjunto mínimo y luego usar los complementos para hacer el conjunto
C A P I T U L O 3
36
completo cuando se necesite crear los minterms. Sin embargo, implementar la Regla 1
no es tan sencillo. Existe el algoritmo M-COM_MIN* que modifica COM_MIN para
encontrar el conjunto de predicados simples mínimo y completo, con resultado en
esencia igual al producido por el algoritmo COM_MIN y sencillo a la hora de
implementarlo (Rodríguez and González, 2008). Este algoritmo consta de los siguientes
pasos:
Método M-COM_MIN*
Entrada:
R: Esquema propietario de la BD, Pr: Conjunto de predicados simples
Salida:
Pr’: Conjunto de predicados simples mínimo y completo
Inicio:
Pr’← Pr
Paso 1: Agrupar Pr’ por atributo
Para cada grupo obtenido hacer los pasos del 2 al 6:
Paso 2: Ordenar los grupos obtenidos en Pr’ de acuerdo al valor del atributo
involucrado. Este paso es para lograr mayor eficiencia que la de COM_MIN a la
hora de eliminar los predicados redundantes. Si existen varios predicados con igual
significado, el valor debe ser el mismo. Por tanto después del proceso de
ordenamiento, ellos deben estar adyacentes.
Paso 3: Estandarizar los predicados en Pr’ y eliminar redundantes. En la
estandarización los operadores > y ≥ se cambian a su forma complementaria ya que
C A P I T U L O 3
37
un predicado simple es esencialmente el mismo que su forma complementaria.
Seguidamente se eliminan los redundantes.
Paso 4: Obtener un conjunto en el cual el mismo valor aparezca a lo sumo tres
veces. Bajo esta condición, basta con solo tener los operadores < e =. Luego, si
existen tres valores adyacentes iguales, se deben cambiar por dos predicados con
igual atributo y valor pero con los operadores < e =, eliminando el tercer predicado,
ya que en el paso siguiente se añaden los complementos.
Paso 5: Adicionar los complementos al conjunto Pr’. Para aquellos predicados con
operador = y que no tengan el mismo valor que su predecesor (se esta asumiendo
que siempre el < y ≤ estarán delante de = para un mismo atributo e igual valor,
obtenido en el paso 2) y no todos los predicados tengan como operador el =, insertar
el operador < delante.
Paso 6: Colocar el complemento en la posición final de Pr’. Cuando todos los
predicados sean de operadores =, insertar una condición al final que signifique la
negación de todos los predicados anteriores a esta posición; en caso contrario,
insertar en la posición final una condición complemento, en dependencia del
predicado predecesor. Al concluir este paso se tiene un conjunto de predicados
mínimo y completo.
Paso 7: Unir los grupos obtenidos en Pr’. Al final se obtienen varios conjuntos de
predicados basados en el mismo atributo. Si unen todos esos conjuntos se obtiene el
conjunto Pr’ de predicados simples mínimo y completo.
Fin M-COM_MIN*
En el método M-COM_MIN* se han ordenado los predicados según su valor y se han
eliminado los redundantes basado en sus atributos. Si existiesen predicados que no
C A P I T U L O 3
38
dividieran más un fragmento, al cambiarlos a forma estándar no sufrirán cambios. Por
tanto, no existen predicados no relevantes. Además, por la forma en que han sido
captados los predicados mediante un constructor de expresiones en AppWizard, se tiene
el predicado si no existe redundancia y si hay alguna aplicación que lo utiliza. De esta
forma nunca existirán dos o más fragmentos que sean siempre accedidos
simultáneamente por cualquier aplicación. En otras palabras, al menos una aplicación
accede a los dos fragmentos de forma diferente. Luego el conjunto de predicados que se
obtuvo es mínimo. Si existiese algún predicado usado por una aplicación, será insertado
en este conjunto de predicados. Luego de la fragmentación, se asegura que todas las
condiciones han sido incluidas en los predicados minterms. Si alguna aplicación
accediera a los fragmentos, podría acceder a todas las tuplas en el fragmento. Es decir,
las tuplas en los fragmentos son accedidos uniformemente y tienen igual probabilidad.
Entonces la completitud está garantizada.
En la obtención del conjunto de predicados minterms para realizar la FHP, se combinan
los predicados simples obtenidos mediante el método M-COM_MIN* de cada conjunto
usando la operación AND sin repetir predicados del mismo conjunto en cada
combinación. En este proceso se puede observar que no se obtendrán predicados
minterms contradictorios, debido a que se selecciona una sola condición de cada
atributo cada vez. Además se puede saber cuántos predicados minterms serán obtenidos,
es decir cuántos fragmentos se obtendrán con solo multiplicar la cantidad de elementos
de cada conjunto intermedio. La complejidad del algoritmo es de O(n4).
Como se garantiza que no existan minterms contradictorios no existen implicaciones
lógicas que no son necesarias tratar. Además se garantiza que el número de minterms a
generar sea menor que el conjunto total de combinaciones posibles, logrando así que se
generen sólo aquellos que estén correctos. Es preciso destacar que siempre quedan
C A P I T U L O 3
39
aquellas implicaciones lógicas que representan contradicciones de carácter semántico.
Estas implicaciones son muy específicas del sistema que se esté diseñado y por tanto es
muy difícil automatizar su eliminación. Así, el asistente para la fragmentación
denominado Fragmenter ofrece la posibilidad de eliminar aquellos que sean
contradictorios de acuerdo a la semántica del problema, lo que demanda un
conocimiento profundo del problema por parte del diseñador.
Corrección de la fragmentación horizontal primaria
Completitud. Se basa en la selección de los predicados a usar. En la medida en que los
predicados seleccionados sean completos, se garantizará que la fragmentación también
lo sea. Como el algoritmo antes mencionado parte de la base de obtener el conjunto de
predicados Pr’ completo y mínimo, se garantiza la completitud.
Reconstrucción. La reconstrucción de una relación global a partir de sus fragmentos se
desarrolla con el operador de unión. Si la relación R es fragmentada en FR = (R1, R2,...,
Rr), entonces, R = ∪Ri ∀RI ∈ FR
Disyunción. Se garantiza en la medida en que los predicados minterms que determinan
la fragmentación sean mutuamente exclusivos.
3.1.2 Algoritmo para la fragmentación horizontal derivada
La FHD se aplica a relaciones miembros (relaciones con llaves foráneas con referencias
a relaciones propietarias donde se definen llaves primarias) a través de llaves foráneas
que hacen referencia a esquemas con FHP. Una FHD se define sobre una relación
miembro de acuerdo a una operación de selección especificada sobre su propietaria. El
enlace entre las relaciones propietarias y miembros se define como un semiacople. Este
punto es especialmente importante, ya que se desea fraccionar una relación miembro
C A P I T U L O 3
40
según la fragmentación de su propietaria, además es necesario que el fragmento
resultante se defina únicamente sobre los atributos de la relación miembro.
El algoritmo de fragmentación derivada consta de varias entradas:
- El conjunto de particiones de la relación propietaria.
- La relación miembro.
- El conjunto de predicados de semiacople entre el propietario y el miembro.
Para realizar la FHD se usa dos criterios CFHD1 y CFHD2 siguiendo el método
Hacer_FHD (Rodríguez and González, 2008).
Método Hacer_FHD.
Si es aplicable CFHD1 Entonces
Aplicar CFHD1
En otro caso
Aplicar CFHD2
Fin Hacer_FHD
Los criterios en cuestión son:
CFHD1: Si el esquema a fragmentar fue obtenido como resultado de la transformación
realizada por ERECASE a una asociación con dependencia de existencia, se efectúa la
FHD a partir del esquema de mayor cardinalidad que tenga realizada una FHP.
CFHD2: Usar el criterio de la fragmentación usada en más aplicaciones. Su
implementación es muy directa, considerando la frecuencia con la cual las aplicaciones
acceden a los datos y que es capturada por AppWizard.
C A P I T U L O 3
41
Corrección de la fragmentación horizontal derivada
Completitud. Sea R la relación miembro de un enlace cuya propietaria es la relación S,
fragmentada como FS = {S1, S2, ..., Sw}. Además, sea A el atributo de acople entre R y S.
Entonces para cada tupla t de R, existirá una tupla t’ de S tal que t[A] = t’[A].
A esta regla se le conoce como integridad referencial y asegura que las tuplas de
cualquier fragmento de la relación miembro están también en la relación propietaria.
Reconstrucción. La reconstrucción de una relación global a partir de sus fragmentos se
desarrolla con el operador de unión. Si la relación R es fragmentada en FR = (R1, R2, ...,
Rr), entonces, R = ∪Ri ∀RI ∈ FR
Disyunción. Establecer esta condición para la fragmentación horizontal derivada no es
tan simple como lo es en la fragmentación horizontal primaria ya que existe una
operación de semiacoples que añade complejidad al asunto. Esta condición puede
garantizarse si el grafo de acople es simple. Si no es simple, será necesario investigar
los valores de las tuplas.
Por último, se deben destacar dos aspectos. Primeramente, la FHD puede seguir una
cadena donde una relación miembro se fragmenta como resultado del diseño de otra y
provoca la fragmentación de otra relación miembro. Esto se tuvo en cuenta a la hora de
diseñar el fragmentador vertical, que consiste en la llamada para cada propietario, al
algoritmo recursivo RecurFragmenter. Segundo, normalmente, existirá más de una
forma de fragmentar una relación y para ello se siguió el método Hacer_FHD.
C A P I T U L O 3
42
Algoritmo RecurFragmenter
Entrada:
Pi propietario
Mi miembro
Salida:
Fi Conjunto de Fragmentos derivados que se obtuvieron
Inicio:
Buscar todos los Pj Mi
Encontrar el Pj por el que se fragmenta Mi
Si j = i entonces
inicio
fragmento Mi por Pj
RecurFragmenter (Mi , con todos Mk miembros de Mi)
fin
Sino
Exit
End.
3.2 Fragmentación Vertical
Para la FV la información requerida, fundamentalmente está relacionada con las
aplicaciones y cómo estas acceden a los datos. Sea Q={q1, q2,…, qq} el conjunto de
consultas o aplicaciones que se ejecutan sobre la relación R(A1, A2, …, An). Se define:
C A P I T U L O 3
43
iku define la Matriz de Uso de atributos (AU) donde la entrada (k, i) denota uki.
jkFreq : frecuencia de activación de la apicación k en el sitio j.
kjn : número de tuplas de la relación R que la aplicación k trata en el sitio j.
kacc : número total de tuplas que la aplicación k trata en todos los sitios.
Por tanto:
kacc = ∑ kjn jkFreq 1 <= j <= número de sitios
A partir de la matriz AU se obtiene la matriz AA. La afinidad entre dos atributos se
define, siendo k todas las aplicaciones que utilizan los atributos ij, como:
∑= kij accaff
Esta es una medida del vínculo que existe entre dos atributos, y se calcula en función de
las aplicaciones que los acceden juntos. En la matriz AA la entrada (i, j) se corresponde
con aff ij. Esto produce una matriz cuadrada de orden n y simétrica. Los valores de la
diagonal son calculados aunque carecen de sentido.
3.2.1 Algoritmo de Hoffer y Severance
Hoffer y Severance (Hoffer and Severance, 1975b) miden la afinidad entre cada par de
atributos de la forma definida anteriormente, construyen la Matriz de Afinidad de
Atributos (AA) y sobre la base de esta agrupan los atributos usando el Algoritmo de
⎩⎨⎧
=.0
.1contrariocasoen
iatributoelusakntransacciólasiu ik
C A P I T U L O 3
44
Energía de Enlace (BEA) (McCormick et al., 1972a). Esto permite reducir el número de
fragmentos a evaluar en las fases posteriores del diseño.
Este algoritmo se considera apropiado por las siguientes razones:
• Está diseñado específicamente para determinar grupos de elementos similares y
no una ordenación lineal de estos. Por ejemplo, agrupa los valores con mayor
afinidad en un grupo y los de menor afinidad en otro.
• El agrupamiento final no depende del orden en que los elementos fueron
presentados al algoritmo.
La complejidad del algoritmo es razonable (O(n) donde n es el número de atributos).
AA es simétrica. Por tanto permite la permutación en parejas de filas y columnas lo que
reduce la complejidad.
El algoritmo toma como entrada la matriz de afinidad, permuta sus filas y columnas y
genera una Matriz de Afinidad Clusterizada (CA). La permutación se realiza
maximizando la siguiente medida de afinidad global (AM):
[ ]∑∑= =
+−+− +++=n
i
n
jjijijijiji affaffaffaffaffAM
1 1,1,11,1,,
Este último conjunto de condiciones tiene en cuenta el caso cuando se va a colocar un
atributo fuera de los límites de los ya colocados.
La función de maximización considera sólo la vecindad más cercana a una posición, lo
que resulta en una agrupación que tiende a unir los atributos de mayor y menor afinidad
entre ellos.
La generación de la matriz CA es hecha en tres pasos:
C A P I T U L O 3
45
Inicialización: Toma arbitrariamente dos de las columnas de la matriz AA y la sitúa en
la matriz CA.
Iteración: Toma cada una de las restantes n-i columnas (donde i es el número de
columnas ya situadas en la matriz CA) e intenta colocarlas en las restantes i+1
posiciones de la matriz CA. Se escoge aquella ubicación que haga la mayor
contribución a la medida de afinidad global. Se continúa este paso hasta que no queden
columnas por localizar.
Ordenamiento de filas: Una vez determinado el orden de las columnas debe cambiarse
el orden de las filas para que estas últimas se correspondan con las primeras.
Donde:
jijkkijki bondbondbondcont ∗−∗+∗= 222
es la contribución neta a la medida de afinidad global de situar el atributo k entre los
atributos i y j, siendo:
∑=
=n
zjzizji affaffbond
1,,
Después de determinada la matriz CA se deja a juicio del diseñador la selección de los
fragmentos, identificando en ella los grupos de atributos con valores similares de
afinidad. Sin embargo no siempre esta identificación es sencilla, sobre todo cuando
muchas aplicaciones se ejecutan sobre una misma relación y estas usan diferentes
grupos de atributos.
3.2.2 Partición vertical binaria
Como se mencionó anteriormente el algoritmo de Hoffer y Severance deja al criterio
subjetivo del diseñador la selección de los grupos de atributos que formarán los
C A P I T U L O 3
46
fragmentos. Además, la similitud entre un par de atributos puede ser inadecuada si no se
tiene en cuenta la similitud entre grupos mayores de atributos. Navathe et al (Navathe et
al., 1984a) extienden lo anterior dando algoritmos para la determinación automática de
los grupos de atributos que forman los fragmentos y teniendo en cuenta en ellos grupos
de atributos con propiedades semejantes. La metodología empleada es de
particionamiento en lugar de agrupamiento. Esto es debido a que la solución óptima
debe estar más cerca del grupo compuesto por todos los atributos tomados como punto
de partida, que de los grupos formados por atributos simples.
El diseño de la fragmentación consta de dos fases. En la primera, el particionamiento
vertical está guiado por una noción empírica, en la cual se minimiza la necesidad de una
aplicación de visitar varios fragmentos. Esta fase no requiere factores de costos
detallados. Durante la segunda fase el diseño de los fragmentos puede ser refinado con
la incorporación de factores de costo, los cuales reflejan el ambiente físico en el que los
fragmentos van a estar almacenados.
3.2.3 Algoritmo basado en una función objetivo empírica
En este caso el objetivo de la fragmentación es encontrar conjuntos de atributos que
sean accedidos solos o al menos por distintos conjuntos de aplicaciones. El algoritmo
parte de la matriz CA para dividir un objeto en dos subconjuntos disjuntos. Se asume
que un punto x es fijado a lo largo de la diagonal principal de la matriz CA como se
muestra en la figura 3.1
C A P I T U L O 3
47
A1 A2 … Aj Aj+1 … An
A1 A2 . .
Aj
Aj+1 . .
An
U
L
X
Figura 3.1 Localización del punto divisor
El punto x define dos bloques: U (upper) y L (lower). Cada bloque define un fragmento
vertical formado por los atributos en ese bloque.
Sea A(k) el conjunto de atributos usados por la aplicación k, calculados de la siguiente
forma:
A(k)= {i | u ki = 1}
Y se define:
T= (t | t es una aplicación)
LT= (t | At ⊆ L)
UT= (t | At ⊆ U)
IT= T – (LT ∪ UT)
donde T representa el conjunto de todas las aplicaciones; LT y UT representan el
conjunto de aplicaciones que sólo necesitan acceder a L o T, respectivamente; e IT
representa el conjunto de aplicaciones que tienen que acceder a ambos fragmentos.
Sobre la base de los conjuntos anteriores se definen los siguientes costos:
C A P I T U L O 3
48
∑
∑
∑
∑
∈
∈
∈
∈
=
=
=
=
LTkk
Tkk
ITkk
UTkk
accCL
accCT
accCI
accCU
donde CT determina el número total de accesos de las aplicaciones al objeto
considerado; CL y CU cuentan el número total de accesos de las aplicaciones que
necesitan un solo fragmento y CI el número total de accesos de las aplicaciones que
necesitan ambos fragmentos.
Se consideran un total de n-1 posibles localizaciones del punto x a lo largo de la
diagonal principal, donde n es el tamaño de la matriz. Una fragmentación no solapada es
obtenida seleccionando un punto x que maximice la siguiente función objetivo z:
z = CL*CU-CI
La partición que corresponde al máximo valor de z es aceptada si z es positiva.
La función anterior proviene de un juicio empírico de lo que debe ser una buena
fragmentación. La función incrementa CL y CU y disminuye CI. Para un valor dado de
CI se selecciona CL y CU de manera tal que CL * CU sea máxima. Como resultado de
esto se seleccionan valores de CL y CU que son lo más cercanos posible, por tanto se
producen fragmentos que están balanceados con respecto a la carga de las aplicaciones.
Este algoritmo tiene la desventaja de no poder producir particiones de un objeto
mediante la selección de un bloque interior en CA. Esta desventaja puede ser evitada si
se usa un procedimiento que mueva la columna que está más a la izquierda en la matriz
CA hacia el extremo derecho y la fila del extremo superior hacia el extremo inferior,
desplazando las demás. Este procedimiento se activa un total de n veces, de forma tal
C A P I T U L O 3
49
que cada bloque tenga la posibilidad de situarse en la esquina superior izquierda, donde
si puede ser reconocido. Después de cada movimiento se ejecuta el algoritmo de
partición binaria determinándose la partición que maximiza z. Esto incrementa la
complejidad del algoritmo en un factor de n, resultando ahora O(n2).
Es posible diseñar una partición n-aria, aunque computacionalmente es costoso. En el
caso de una fragmentación n-aria no solapada, en general un algoritmo debe probar 1, 2
o … n-1 puntos a lo largo de la diagonal principal como puntos candidatos para definir
la partición. La complejidad de este algoritmo sería O(2n). Una solución para evitar esta
complejidad es aplicar recursivamente el algoritmo de partición binaria. En cada
iteración los fragmentos producidos por el algoritmo son considerados como dos objetos
distintos y la partición binaria es aplicada para fragmentar cada uno de ellos. Esto
genera dos subproblemas distintos. En cada subproblema son consideradas sólo aquellas
aplicaciones que usan algún atributo del fragmento considerado. El proceso termina
cuando no se recomienda fragmentar porque z no sea positiva.
Corrección de la fragmentación vertical
Completitud. La completitud de una FV es garantizada por el algoritmo de
particionamiento, ya que cada atributo de la relación global se asigna a uno de los
fragmentos, siempre y cuando el conjunto de atributos A sobre los cuales se define una
relación R consista en LUA U= la completitud de la FV se asegura.
Reconstrucción. La reconstrucción de la relación global original se hace por medio de
la operación de unión. Así, para una relación R con fragmentación vertical Fr = {R1,
R2,..., Rr} y llave K, riik FRRR ∈∀=>< .
C A P I T U L O 3
50
Por lo tanto, siempre que Ri sea completo, la operación de unión reconstruirá
adecuadamente R. Otro punto importante es que cada Ri debe contener a la llave de R, o
debe contener los identificadores de tuplas asignados por el sistema.
Fragmentos Disjuntos. Existen dos casos:
Los identificadores de tuplas no se consideran que se traslapen ya que ellos son
mantenidos por el sistema. Las llaves duplicadas no se consideran que se traslapen.
3.3 Diagrama de clases del asistente Fragmenter
A la hora de efectuar una fragmentación hay que decidirse por una de las variantes,
Fragmentación Horizontal ó Fragmentación Vertical, ya que la Fragmentación Mixta no
constituye un punto de decisión, sino la unión de estas. Cada una tiene características
bien diferentes en cuanto a implementación se refiere, y es por eso que se crearon
distintas clases para cada una de ellas, además de las que se incluyen para propósitos
necesarios. En la figura 3.2 se muestra la interacción entre las que indudablemente son
las principales clases del asistente.
C A P I T U L O 3
51
Figura 3.2 Diagrama de clases del Fragmenter.
3.4 Interfaz del asistente Fragmenter
En la creación de la herramienta Fragmenter fueron implementados algoritmos usando
los referentes expuestos en los dos acápites anteriores. A pesar de que la literatura
recomienda comenzar con la FH, por la experiencia del diseñador y las características
de la BD que se esté fragmentando, se puede realizar sólo la FV o iniciar el proceso con
ella cuando sea mejor para aumentar el rendimiento de las transacciones, incrementar el
C A P I T U L O 3
52
procesamiento local y minimizar el acceso a datos remotos, aumentar el paralelismo
durante la ejecución de las consultas, la concurrencia y el rendimiento.
La herramienta Fragmenter permite que el diseñador elija qué tipos de fragmentación
aplicará a cada esquema. Después de concluida una alternativa de fragmentación, se
pueda realizar otra alternativa obteniendo una FM. Cuando se decida realizar la FV
primeramente se seleccionan los esquemas que serán fragmentados y luego se
visualizan los fragmentos resultantes; para terminar debe pasar a la siguiente etapa
donde se guardan los resultados en el catálogo y se le brinda la posibilidad de terminar o
volver al inicio para tomar otra decisión. De seleccionar la FH se visualizan los
minterms de cada relación primaria y debe eliminar aquellos que considere
semánticamente contradictorios (véase la figura 3.3).
Figura 3.3 Minterms de las relaciones propietarias.
1- Clic para ver los minterms de cada esquema.
1
2
3
4
C A P I T U L O 3
53
2- Seleccionar en caso de que desee que sobre él pueda actual la acción 3.
3- Eliminar minterms seleccionados.
4- Eliminar todos los minterms.
Al tener los minterms sobre los que se definen los fragmentos horizontales, se le
muestra al diseñador tanto los fragmentos horizontales primarios, como los derivados
(véase la figura 3.4).
Figura 3.4 Fragmentos horizontales primarios y derivados
3.5 Conclusiones parciales
Se ha obtenido una nueva versión de la herramienta Fragmenter que se integra con otras
herramientas de ayuda al diseño de BDD a través de un catálogo e implementa un
método específico para su uso en la FHD que no estaba contemplado en la versión
anterior. Además, mejora la gestión de acceso al catálogo a través de un Controlador
que optimiza las lecturas y escrituras al mismo.
C O N C L U S I O N E S
54
CONCLUSIONES
Las herramientas obtenidas colaboran en un ambiente integrado como ayuda al diseño
de BDD, y además pueden usarse de forma independiente. Estas herramientas les
permiten a los diseñadores caracterizar las aplicaciones y realizar la fragmentación de
esquemas lógicos dentro del proceso de diseño de BDD.
1. AppWizard es un asistente fácil de usar para capturar una gran variedad de
información sobre las aplicaciones más representativas en el universo de
discurso objeto de modelación. Sin embargo, se requiere que el diseñador posea
suficiente conocimiento del problema para poder estimar los parámetros de
cardinalidad, selectividad y frecuencia de accesos solicitados por este asistente.
2. Fragmenter realiza la fragmentación de esquemas globales para obtener un
conjunto de fragmentos lógicos que luego serán objeto de ubicación en los
diferentes sitios de procesamiento donde residirá la BDD. Esta herramienta
integra tres módulos independientes para los diferentes tipos de fragmentación:
FHP, FHD y FV. De estos sólo se pueden elegir la FH y la FV, porque la FHD
se realiza automáticamente a partir de los resultados de la FHP. La FHP se basa
en el método clásico reportado en (Őzsu and Valduriez, 1999) sustituyendo el
método COM_MIN por M-COM-MIN* de mayor eficiencia, que también
asegura completitud y minimalidad. La FHD emplea como criterios para
seleccionar las llaves foráneas, que se deben priorizar para favorecer los acoples
con las llaves primarias respectivas, aquellos que aparecen en la literatura, y se
adiciona el criterio que tiene en cuenta el concepto de dependencia de existencia
presente en algunas asociaciones. La FV se realiza siguiendo el enfoque clásico
C O N C L U S I O N E S
55
recogido en la literatura (Őzsu and Valduriez, 1999). Los resultados obtenidos
durante las pruebas fueron los esperados.
R E C O M E N D A C I O N E S
56
RECOMENDACIONES
1. Las herramientas obtenidas han sido probadas con ejemplos sencillos de diseño de
BDD reportados en la bibliografía por lo que se recomienda probarlas con casos de
prueba reales para continuar la validación de las mismas.
2. En la herramienta Fragmenter se realiza la Fragmentación Horizontal Derivada de
manera automática, es decir, sin la intervención directa del diseñador; por lo que se
sugiere sea considerada la posibilidad de ofrecerle el control al diseñador para que
pueda limitar el proceso de fragmentación en cadena.
R E F E R E N C I A S B I B L I O G R A F I C A S
57
REFERENCIAS BIBLIOGRÁFICAS
ÁGUILA, L. (2001) Aplicación de los algoritmos genéticos a la asignación de
fragmentos en bases de datos distribuidas. Departamento de Computación.
Santa Clara, Universidad Central de Las Villas.
ÁLVAREZ, W. A., RODRIGUEZ, A. & GARCÍA, C. E. (2006) ERECASE v.2.0. Una
herramienta para el diseño conceptual de bases de datos con validación
estructural. Departamento de Ciencia de la Computación. Santa Clara, Cuba,
Universidad Central "Marta Abreu" de Las Villas.
ARTILES, M. (2001) Herramienta para la ayuda a la fragmentación horizontal.
Departamento de Computación. Santa Clara, Universidad Central de Las Villas.
BAIÃO, F. A., MATTOSO, M., SHAVLIK, J. W. & ZAVERUCHA, G. (2003)
Applying Theory Revision to the Design of Distributed Databases. IN
HORVÁTH, T. & YAMAMOTO, A. (Eds.) Proceedings of the 13th
International Conference on Inductive Logic Programming ILP 2003, LNAI
2835. Szeged, Hungary, Springer.
BAIÃO, F. A., MATTOSO, M. & ZAVERUCHA, G. (2002) A Framework for the
Design of Distributed Databases. IN LITWIN, W. & LÉVY, G. (Eds.) Records
of the 4th International Meeting on Distributed Data & Structures 4 (WDAS
2002). Paris, France, Carleton Scientific.
BAIÃO, F. A., MATTOSO, M. & ZAVERUCHA, G. (2004) A Distribution Design
Methodology for Object DBMS. Distributed and Parallel Databases, 16, 45-90.
BELLATRECHE, L., KARLAPALEM, K. & SIMONET, A. (1997) Horizontal
Fragmentation in Distributed Object Database Systems. Proceedings of the 8th
R E F E R E N C I A S B I B L I O G R A F I C A S
58
International Conference on Database and Expert Systems Applications DEXA
'97. Toulouse, France, Springer.
BELLATRECHE, L., KARLAPALEM, K. & SIMONET, A. (2000) Algorithms and
support for horizontal class partitioning in object-oriented databases. Distributed
and Parallel Databases, 8, 155-179.
BELLATRECHE, L. & SIMONET, A. (1996) Horizontal Fragmentation in Distributed
Object Database Systems. IN BÖSZÖRMÉNYI, L. (Ed.) Proceedings of the
Third International ACPC Conference with Special Emphasis on Parallel
Databases and Parallel I/O. Klagenfurt, Austria, Springer.
BELLATRECHE, L., SIMONET, A. & SIMONET, M. (1996) Vertical Fragmentation
in Distributed Object Database Systems with Complex Attributes and Methods.
IN WAGNER, R. & THOMAS, H. (Eds.) Proceedings of the Seventh
International Workshop on Database and Expert Systems Applications DEXA
'96. Zurich, Switzerland, IEEE-CS Press.
BHALLA, S. & HASEGAWA, M. (2005) Parallelizing serializable transactions within
distributed real-time database systems Proceedings of the International
Conference on Embedded and Ubiquitous Computing (EUC 2005). Lecture
Notes in Computer Science. Springer.
CABRERA, N. E., RODRÍGUEZ, A. & GONZÁLEZ, L. M. (2006) Asistente para la
Caracterización de Aplicaciones y Fragmentación en un Sistema de Bases de
Datos Distribuidas. Ciencia de la Computación. Santa Clara, Universidad
Central "Marta Abreu" de Las Villas.
CERI, S., NAVATHE, S. B. & WIEDERHOLD, G. (1983) Distribution Design of
Logical Database Schemas. IEEE Trans. Software Eng., 9, 487-504.
R E F E R E N C I A S B I B L I O G R A F I C A S
59
CERI, S., NEGRI, M. & PELAGATTI, G. (1982) Horizontal Data Partitioning in
Database Design. Proceedings of the ACM SIGMOD International Conference
on Management of Data 1982. Orlando, Florida, ACM Press.
CERI, S. & PELAGATTI, G. (1984) Distributed Databases: Principles and Systems,
McGraw-Hill New York, NY, USA.
CERI, S. & PERNICI, B. (1985) DATAID-D: Methodology for Distributed Database
Design, North-Holland.
CERI, S., PERNICI, B. & WIEDERHOLD, G. (1987) Distributed Database Design
Methodologies. IEEE Database Eng. Bull., 75, 533-546.
CERI, S., PERNICI, B. & WIEDERHOLD, G. (1989) Optimization problems and
solution methods in the design of data distribution. Inf. Syst.
CORNELL, D. W. & YU, P. S. (1987) A Vertical Partitioning Algorithm for Relational
Databases. Proceedings of the Third International Conference on Data
Engineering. Los Angeles, CA, USA, IEEE Computer Society.
COULON, C., PACITTI, E. & VALDURIEZ, P. (2005) Consistency Management for
Partial Replication in a High Performance Database Cluster. IEEE International
Conference on Parallel and Distributed Systems (ICPADS2005). Fukuoka,
Japan.
DATE, C. J. (2000) Introducción a los Sistemas de Bases de Datos, Séptima edición,
México, Addison-Wesley.
EZEIFE, C. I. & BARKER, K. (1995) A Comprehensive Approach to Horizontal Class
Fragmentation in a Distributed Object Based System. Distributed and Parallel
Databases, 3, 247-272.
R E F E R E N C I A S B I B L I O G R A F I C A S
60
EZEIFE, C. I. & DEY, P. (2003) Incremental Horizontal Fragmentation of Database
Class Objects. Proceedings of the 5th International Conference on Enterprise
Information Systems ICEIS (1) 2003. Angers, France.
GANÇARSKI, S., NAACKE, H., PACITTI, E. & VALDURIEZ, P. (2002) Parallel
Processing with Autonomous Databases in a Cluster System. IN MEERSMAN,
R. & TARI, Z. (Eds.) Proceedings of the Confederated International
Conferences On the Move to Meaningful Internet Systems, 2002 -
DOA/CoopIS/ODBASE. Irvine, California, USA, Springer.
GARCÍA, C. E., RODRÍGUEZ, A., GONZÁLEZ, L. M. & ÁLVAREZ, W. A. (2005)
ERECASE, una herramienta con validación de diagramas entidad relación. 6to.
Simposium Iberoamericano de Computación e Informática SICI 2005. Instituto
Tecnológico de Nuevo León, Monterrey, NL, México, Instituto Tecnológico de
Nuevo León.
HABABEH, I. O., BOWRING, N. & RAMACHANDRAN, M. (2004) A Method for
Fragment Allocation in Distributed Object Oriented Database Systems.
Proceedings of the 5th Annual PostGraduate Symposium on The Convergence of
Telecommunications, Networking & Broadcasting (PGNet). Liverpool, UK.
HERNÁNDEZ, A. (2005) Agente de aprendizaje reforzado aplicado al problema de
asignación en bases de datos distribuidas. Ciencia de la Computación. Santa
Clara, Universidad Central "Marta Abreu" de Las Villas.
HOFFER, J. A. & SEVERANCE, D. G. (1975a) The Use of Cluster Analysis in
Physical Data Base Design. IN KERR, D. S. (Ed.) Proceedings of the
International Conference on Very Large Data Bases. Framingham, MA, USA,
ACM.
R E F E R E N C I A S B I B L I O G R A F I C A S
61
HOFFER, J. A. & SEVERANCE, D. G. (1975b) The use of cluster analysis in physical
database design. IN KERR, D. S. (Ed.) Proceedings of the 1st International
Conference on Very Large Databases. Framingham, Massachusetts, USA,
ACM.
HUANG, Y.-F. & CHEN, J.-H. (2001) Fragment Allocation in Distributed Database
Design. Journal of Information Science and Engineering, 17, 491-506.
IRÚN-BRIZ, L., DECKER, H., JUAN-MARIN, R., CASTRO-COMPANY, F.,
ARMENDÁRIZ-INIGO, J. E., BERNABÉU-AUBÁN, J. M. & MUÑOZ-
ESCOÍ, F. D. (2005) MADIS: A slim middleware for database replication.
Proceedings of the 11st International Conference on Parallel Processing
(EuroPar 2005). Lecture Notes in Computer Science. Springer.
JOHANSSON, J. M., MARCH, S. T. & NAUMANN, J. D. (2000) The effects of
parallel processing on update response time in distributed database design. IN
ANG, S., KRCMAR, H., ORLIKOWSKI, W. J., WEILL, P. & DEGROSS, J. I.
(Eds.) Proceedings of the Twenty-First International Conference on Information
Systems ICIS. Brisbane, Australia, ACM.
LEE, J. W. & BAIK, D. K. (2004) Database allocation modeling for optimal design of
distributed systems. IEICE Transactions on Information and Systems, E87D,
1795-1804.
LIM, S. J. & NG, Y.-K. (1997) Vertical Fragmentation and Allocation in Distributed
Deductive Database Systems. Inf. Syst., 22, 1-24.
LIN, W. J. & VEERAVALLI, B. (2006) An object replication algorithm for real-time
distributed databases. Distributed and Parallel Databases., 19, 125-146.
R E F E R E N C I A S B I B L I O G R A F I C A S
62
LIN, X. & ORLOWSKA, M. E. (1995) An Integer Linear Programming Approach to
Data Allocation with the Minimum Total Communication Cost in Distributed
Database Systems. Information Sciences, 85, 1-10.
MA, H. & SCHEWE, K.-D. (2004) A heuristic approach to horizontal fragmentation in
object oriented databases. IN BARZDINS, J. (Ed.) Proceedings of the 2004
Baltic Conference on Databases and Information Systems. Riga, Latvia, Faculty
of Computer Science and Information Technology, Riga Technical University.
MA, H., SCHEWE, K.-D. & WANG, Q. (2005) Distribution design for higher-order
data models. Palmerston North, New Zealand, Massey University, Department
of Information Systems.
MA, H., SCHEWE, K.-D. & WANG, Q. (2006) A Heuristic Approach to Cost-Efficient
Fragmentation and Allocation of Complex Value Databases. IN DOBBIE, G. &
BAILEY, J. (Eds.) The 17th Australasian Database Conference (ADC2006)
Hobart, Australia, ACM International Conference Archive Proceeding Series
vol. 170. Australian Computer Society Inc.
MCCORMICK, W. T., SCHWEITZER, P. J. & WHITE, T. W. (1972a) Problem
decomposition and data reorganization by a clustering technique, Operations
Research.
MCCORMICK, W. T., SCHWEITZER, P. J. & WHITE, T. W. (1972b) A Problem
Decomposition and Data Reorganization by a Clustering Techniques. Operation
Research, 20, 993-1009.
MEI, H. & SHENG, O. (1992) A Semantic Based Methodology for Integrated
Computer-Aided Distributed Database Design. The 25th Hawaii International
Conference on System Sciences.
R E F E R E N C I A S B I B L I O G R A F I C A S
63
MORELL, A., GONZÁLEZ, L. M. & RODRÍGUEZ, A. (2000a) Algoritmos para la
fragmentación vertical en bases de datos distribuidas. COMPUMAT 2000, 7mo.
Congreso de la Sociedad Cubana de Matemática y Computación. Manzanillo,
Cuba, SCMC.
MORELL, A., GONZÁLEZ, L. M. & RODRÍGUEZ, A. (2000b) Un enfoque a la
fragmentación vertical en bases de datos distribuidas. Congreso Internacional
Informática 2000, Nuevas Tecnologías Informáticas. La Habana, Cuba.
MUTHURAJ, J., CHAKRAVARTHY, S., VARADARAJAN, R. & NAVATHE, S. B.
(1993) A Formal Approach to the Vertical Partitioning Problem in Distributed
Database Design. Proceedings of the 2nd International Conference on Parallel
and Distributed Information Systems (PDIS 1993), Issues, Architectures, and
Algorithms. San Diego, CA, USA, IEEE Computer Society.
NAVATHE, S., CERI, S., WIEDERHOLD, G. & DOU, J. (1984a) Vertical partitioning
algorithms for database design. ACM Transactions on Database Systems.
NAVATHE, S. B., CERI, S., WIEDERHOLD, G. & DOU, J. (1984b) Vertical
Partitioning Algorithms for Database Design. ACM Trans. Database Syst., 9,
680-710.
NAVATHE, S. B., KARLAPALEM, K. & RA, M. (1995) A mixed fragmentation
methodology for initial distributed database design. Atlanta, GA, College of
Computing, Georgia Institute of Technology.
NELSON, H. J., MONARCHI, D. E. & NELSON, K. M. (2001) Ensuring the
'Goodness' of a Conceptual Representation. Proceedings of the 4th European
Conference on Software Measurement and ICT Control (FESMA'01). Germany.
R E F E R E N C I A S B I B L I O G R A F I C A S
64
ŐZSU, M. T. & PATRICK, V. (1999) Principles of Distributed Database Systems,
Second Edition, Prentice-Hall.
ŐZSU, M. T. & VALDURIEZ, P. (1999) Principles of Distributed Database Systems,
Second Edition, Upper Saddle River, New Jersey., Prentice-Hall.
PÉREZ, J., PAZOS, R. A., FRAUSTO-SOLIS, J., REYES, G., SANTAOLAYA, R.,
FRAIRE, H. J. & CRUZ, L. (2005) An approach for solving very large scale
instances of the design distribution problem for distributed database systems.
Proceedings of the 4th International School and Symposium on Advanced
Distributed Systems (ISSADS2005). Lecture Notes in Computer Science.
Springer.
PÉREZ, J., PAZOS, R. A., SOLÍS, J. F., ROMERO, D. & CRUZ, L. (2000) Vertical
Fragmentation and Allocation in Distributed Databases with Site Capacity
Restrictions Using the Threshold Accepting Algorithm. IN CAIRÓ
BATTISTUTTI, O., SUCAR, L. E. & CANTU, F. J. (Eds.) MICAI 2000:
Advances in Artificial Intelligence, Mexican International Conference on
Artificial Intelligence. Acapulco, Mexico, Springer.
RODRÍGUEZ, A., CÁRDENAS, A., CASTRO, M. T. & GONZÁLEZ, L. M. (2007a)
Caracterización de la red de comunicación y sitios en el Diseño de Bases de
Datos Distribuidas. Revista Ingeniería Electrónica, Automática y
Comunicaciones, enviado.
RODRÍGUEZ, A., CÁRDENAS, A., CASTRO, M. T. & GONZÁLEZ, L. M. (2007b)
Caracterización de la red de comunicación y sitios en el Diseño de Bases de
Datos Distribuidas. Convención de Ingeniería Eléctrica CIE’2007 Santa Clara,
Cuba, Universidad Central "Marta Abreu" de Las Villas.
R E F E R E N C I A S B I B L I O G R A F I C A S
65
RODRÍGUEZ, A. & GONZÁLEZ, L. M. (2008) Sistema integrado de herramientas de
ayuda al diseño de bases de datos en ambientes distribuidos. Ciencia de la
Computación. Santa Clara, Cuba, Universidad Central de Las Villas.
RODRÍGUEZ, A., GONZÁLEZ, L. M. & ÁGUILA, L. S. (2005) Asignación de
fragmentos en Bases de Datos Distribuidas mediante la aplicación de
Algoritmos Genéticos. Boletín de la Sociedad Cubana de Matemática y
Computación, 3.
RODRÍGUEZ, A., GONZÁLEZ, L. M., CABRERA, L. & MORELL, A. (2002a)
ERECASE:Una herramienta de ayuda a la modelación de esquemas
conceptuales globales. Actas I Workshop de Bases de Datos, Jornadas Chilenas
de Computación JCC 2002. 1 ed. Universidad de Atacama, Copiapó, Chile,
Cámara Chilena del Libro A.G.
RODRÍGUEZ, A., GONZÁLEZ, L. M., GARCÍA, C. E. & CASTRO, M. T. (2007c)
Bases de datos en ambientes distribuidos, Santa Clara, Editorial Feijóo,
Universidad Central de Las Villas.
RODRÍGUEZ, A., GONZÁLEZ, L. M., MORELL, A., CABRERA, L., ARTILES, M.,
ÁGUILA, L. S. & VALDÉS, Á. (2002b) Integración de herramientas de ayuda
al diseño de bases de datos distribuidas. Actas I Workshop de Bases de Datos,
Jornadas Chilenas de Computación JCC 2002. 1 ed. Universidad de Atacama,
Copiapó, Chile, Cámara Chilena del Libro A.G.
RODRÍGUEZ, A., ROSA, D., MAINEGRA, M. & GONZÁLEZ, L. M. (2007d) An
Intelligent Agent Using a Q-Learning Method to Allocate Replicated Data in a
Distributed Database. IN GELBUKH, A. & KURI, Á. F. (Eds.) Proceedings of
the 6th Mexican International Conference on Artificial Intelligence-MICAI2007.
R E F E R E N C I A S B I B L I O G R A F I C A S
66
Special Session - Revised Papers. Aguascalientes, México, IEEE Computer
Society.
RODRÍGUEZ, A., ROSA, D., MAINEGRA, M. & GONZÁLEZ, L. M. (2007e) A
Reinforcement Learning Solution for Allocating Replicated Fragments in a
Distributed Database. Revista Computación y Sistemas, 11, 10 p.
RODRÍGUEZ, A., ROSA, D., PÉREZ, W. & GONZÁLEZ, L. M. (2007f) Manejo
distribuido de datos para facilitar el control de calidad en la producción de
azúcar crudo de caña. CENTROAZUCAR, aceptado.
ROSA, D. (2006) Aplicación de técnicas de Inteligencia Artificial en la solución del
problema de ubicación en el diseño de bases de datos distribuidas.
Departamento de Ciencia de la Computación. Santa Clara, Universidad Central
"Marta Abreu" de Las Villas.
SAVONNET, M., TERRASSE, M.-N. & YÉTONGNON, K. (1999) FRAGTIQUE: An
OO Distribution Design Methodology. IN CHEN, A. L. P. & LOCHOVSKY, F.
H. (Eds.) Proceedings of the Sixth International Conference on Database
Systems for Advanced Applications (DASFAA). Hsinchu, Taiwan, IEEE
Computer Society.
SCHEWE, K.-D. (2002) Fragmentation of object oriented and semi-structured data. IN
HAAV, H.-M. & KALJA, A. (Eds.) Databases and Information Systems II.
Kluwer Academic Publishers.
TAMHANKAR, A. M. & RAM, S. (1998) Database fragmentation and allocation: an
integrated methodology and case study. IEEE Transactions on Systems, Man,
and Cybernetic Part A, 28, 288-305.
![[4] Diseño lógico de bases de datos - jorgesanchez.net · GBD-Unidad 4-Diseño lógico de bases de datos Jorge Sánchez, @jorgesancheznet Transformación de relaciones n a n •Si](https://img.pdfslide.es/doc/110x75/5baa48af09d3f221798c2414/4-diseno-logico-de-bases-de-datos-gbd-unidad-4-diseno-logico-de-bases.jpg)
