Navarrete Marcos
Ibarra Milton
Esquema de fragmentación y Distribucion de BDD
El objetivo de la fragmentación
es encontrar un nivel de particionamiento adecuado en el rango que va desde
tuplas o atributos hasta relaciones completas.
Cada relación global puede ser
dividida en porciones que no se solapen llamados fragmentos. El mapa resultante
se denomina esquema de fragmentación. Una relación global puede
dividirse en n fragmentos y un fragmento sólo puede pertenecer a una relación
global.
El problema de fragmentación se
refiere al particionamiento de la información para distribuir cada parte a los
diferentes sitios de la red. Inmediatamente aparece la siguiente pregunta:
¿Cuál es la unidad razonable de distribución?. Se puede considerar que una
relación completa es lo adecuado ya que las vistas de usuario son subconjuntos
de las relaciones. Sin embargo, el uso completo de relaciones no favorece las
cuestiones de eficiencia sobre todo aquellas relacionadas con el procesamiento
de consultas.
Tipos de
fragmentación:
Vertical
Vertical
Horizontal
Mixta
Fragmentación
vertical
Una fragmentación vertical de una relación R
produce fragmentos R1, R2, ..., Rr,
cada uno de los cuales contiene un subconjunto de los atributos de R así
como la llave primaria de R. El objetivo de la fragmentación vertical es
particionar una relación en un conjunto de relaciones más pequeñas de manera
que varias de las aplicaciones de usuario se ejecutarán sobre un fragmento. En
este contexto, una fragmentación "óptima" es aquella que produce un esquema
de fragmentación que minimiza el tiempo de ejecución de las consultas de
usuario.
La fragmentación vertical ha sido estudiada
principalmente dentro del contexto de los sistemas de manejo de bases de datos
centralizados como una herramienta de diseño, la cual permite que las consultas
de usuario traten con relaciones más pequeñas haciendo, por tanto, un número
menor de accesos a páginas.
La fragmentación vertical es inherentemente más
complicada que particionamiento horizontal ya que existe un gran número de
alternativas para realizarla. Por lo tanto, se utilizan heurísticas para hacer
el particionamiento. Los dos enfoques básicos son:
- Agrupamiento. Inicia asignando cada atributo a un fragmento, y en cada paso, algunos de los fragmentos satisfaciendo algún criterio se unen para formar un solo fragmento.
- División. Inicia con una sola relación realizar un particionamiento basado en el comportamiento de acceso de las consultas sobre los atributos.
Nos concentraremos aquí al estudio del enfoque
divisional ya que, por un lado, su aplicación es más natural al enfoque de
diseño "top-down". Además, el enfoque divisional genera fragmentos
que no se traslapan mientras que el agrupamiento típicamente resulta en
fragmentos traslapados. Por supuesto, la no traslapación no incluye a las
llaves primarias.
Requerimientos de información para la fragmentación
vertical
Como en el caso de la fragmentación horizontal, es
necesario proporcionar información para poder realizar una adecuada
fragmentación vertical. Ya que el particionamiento vertical coloca en un
fragmento aquellos atributos que se accesan juntos, se presenta la necesidad de
una medida que relacione la afinidad de los atributos, la cual indica qué tan
relacionados están los atributos. Esta medida se obtiene por datos primitivos.
Dado un conjunto de consultas Q = { q1,
q2, ..., qq } que serán aplicadas a la
relación R[A1, A2, ..., An],
se define la función
Los vectores use( qi, · )
son fáciles de definir si el diseñador conoce las aplicaciones que serán
ejecutadas en la base de datos.
Fragmentación
horizontal
En las siguientes secciones revisaremos de manera
más formal la forma de construir los diferentes tipos de fragmentación.
La fragmentación horizontal primaria de una
relación se obtiene usando predicados que están definidos en esa relación. La
fragmentación horizontal derivada, por otra parte, es el particionamiento de
una relación como resultado de predicados que se definen en otra relación.
Para poder construir una fragmentación, es
necesario proporcionar información acerca de la base de datos y acerca de las
aplicaciones que las utilizan. En primer término, es necesario proporcionar la
información acerca del esquema conceptual global. En este sentido es importante
dar información acerca de las relaciones que componen a la base de datos, la
cardinalidad de cada relación y las dependencias entre relaciones. Por ejemplo,
en la Figura 3.4 se presenta un diagrama mostrando el esquema conceptual de la
base de datos de ejemplo del capítulo 2.
En segundo lugar se debe proporcionar información
acerca de la aplicación que utiliza la base de datos. Este tipo de información
es cuantitativa y consiste de los predicados usados en las consultas de
usuario.
Figura 3.4. Esquema conceptual de la base de datos
de ejemplo del capítulo 2.
Dada una relación R( A1, A2,
…, An), donde Ai es un atributo
definido sobre el dominio Di, un predicado simple
pj definido en R tiene la forma
pj: Ai q Valor
donde q Î { =, <, ¹ , £ , >, ³ } y Valor Î
Di. Para la relación R se define un conjunto de
predicados simples como Pr = { p1, p2,
…, pm }.
Ejemplo 3.7. Las siguientes expresiones se consideran como
predicados simples.
JNOMBRE =
"Mantenimiento"
PRESUPUESO < 200000
¨
Dado la relación R y el conjunto de
predicados simples Pr = { p1, p2, …,
pm }, se define el conjunto de predicados minitérmino
como M = { m1, m2, …, mr
} como
M = { mi | mi = Ù
pj Î Pr pj*}, 1 £ j
£ m, 1 £ i £ z
donde, pj* = pj
o pj* = Ø (pj).
Ejemplo 3.8. Los siguientes son minitérminos de la relación J.
m1: JNOMBRE ==
"Mantenimiento" Ù Presupuesto £ 200000
m2: NOT( JNOMBRE ==
"Mantenimiento") Ù Presupuesto £ 200000
m3: JNOMBRE ==
"Mantenimiento" Ù NOT (Presupuesto £ 200000)
m4: NOT( JNOMBRE ==
"Mantenimiento") Ù NOT(Presupuesto £ 200000)
En términos de la información cuantitativa acerca
de las aplicaciones de usuario, se necesita tener dos conjuntos de datos:
- La selectividad de los minitérminos: Denotada como sel( mi ), se refiere al número de tuplos de la relación que serán accesadas por una consulta de usuario especificada de acuerdo a un predicado minitérmino dado.
- La frecuencia de acceso: Denotada como acc( qi ), se refiere a la frecuencia con la cual una consulta de usuario qi es accesada en un periodo de tiempo. Note que las frecuencias de acceso de minitérminos se pueden determinar a partir de las frecuencias de consultas. La frecuencia de acceso de un minitérmino se denota como acc( mi ).
Una fragmentación horizontal primaria se define por
una operación de selección en las relaciones propietarias de un esquema de la
base de datos. Por tanto, dada una relación R, su fragmentación horizontal está
dada por
Rj = s Fj (R),
1 £ j £ w
donde, Fj es una fórmula de
selección, la cual es preferiblemente un predicado minitérmino. Por lo tanto,
un fragmento horizontal Ri de una relación R consiste
de todos los tuplos de R que satisfacen un predicado minitérmino mi.
Lo anterior implica que dado un conjunto de predicados minitérmino M,
existen tantos fragmentos horizontales de R como minitérminos existan.
El conjunto de fragmentos horizontales también se entiende como los fragmentos
minitérminos.
Es necesario desarrollar un algoritmo que tome como
entrada una relación R y el conjunto de predicados simples Pr y
proporcione como resultado el conjunto de fragmentos de R = { R1,
R2, …, Rm } el cual obedece las reglas de
fragmentación. Un aspecto importante del conjunto de predicados es que debe ser
completo y minimal.
Un conjunto de predicados simples Pr se dice
que es completo si y solo si los accesos a los tuplos de los
fragmentos minitérminos definidos en Pr requieren que dos tuplos del
mismo fragmento tengan la misma probabilidad de ser accesados por cualquier
aplicación.
Ejemplo 3.9 Considere que la relación J[JNO,
JNOMBRE, PRESUPUESTO, LUGAR] tiene dos consultas definidas en ella:
Encontrar proyectos con
presupuestos menores a $200000. (2)
De acuerdo a (1),
Pr = { LUGAR = "México",
LUGAR = "Puebla", LUGAR = "Guadalajara", LUGAR =
"Monterrrey" }
no es completa con respecto a (2)
dado que algunos de los tuplos dentro de cada Ji tienen una
probabilidad mayor de ser accesados por la segunda consulta. Si se modifica Pr
como
Pr = { LUGAR = "México",
LUGAR = "Puebla", LUGAR = "Guadalajara", LUGAR =
"Monterrrey",
PRESUPUESTO £ 2000000,
PRESUPUESTO > 200000 }
entonces, Pr es completo.
Fragmentación mixta o híbrida:
En muchos casos la fragmentación vertical u
horizontal del esquema de la base de datos no será suficiente para satisfacer
los requisitos de las aplicaciones. Como ya se citó al comienzo de este
documento podemos combinar ambas, utilizando por ello la denominada
fragmentación mixta. Cuando al proceso de fragmentación vertical le sigue una
horizontal, es decir, se fragmentan horizontalmente los fragmentos verticales
resultantes, se habla de la fragmentación mixta HV. En el caso contrario,
estaremos ante una fragmentación VH. Una característica común a ambas es la
generación de árboles que representan la estructura de fragmentación (vea la
figura 8).
Considere, por ejemplo, la relación PROVINC.
Recordará que se le aplicó una fragmentación horizontal de acuerdo al valor del
atributo CCODZONA resultando cuatro fragmentos horizontales. Podríamos pensar
en aplicarle una nueva fragmentación de carácter vertical. Entonces resultarían
cuatro fragmentos horizontales divididos, por ejemplo, en dos fragmentos
verticales. En este caso el número total de fragmentos ascendería, lógicamente,
a ocho.
Software Utilizado en Base de Datos Distribuidas
Los programas de bases de datos organizan y
almacenan los datos de manera tal que las tablas están indexadas y se
pueden contestar preguntas. Estas herramientas están disponibles en un
número de configuraciones diferentes y escalables para ser usadas por un
individuo o una corporación global. Algunos son fáciles de usar, con
bases de datos a manera de interfaz visual, mientras que otras, al final
del espectro empresarial, requieren entrenamiento y herramientas
especializadas para ser útiles.Access
Access es un sistema de base
de datos personal de Microsoft. Se trata de un producto de software
orientado hacia lo visual, lo que hace que quienes no sean programadores
puedan crear bases de datos útiles con facilidad. Si bien la estructura
de base de datos Access puede ampliarse para satisfacer las necesidades
empresariales, el uso más común de esta base de datos es para pequeñas
bases de datos individuales o en programas multiusuario de uso limitado.
Access integra el lenguaje Visual Basic para aplicaciones, por lo que
es un entorno de desarrollo completo.
Visual FoxPro
FoxPro es un sistema de base
de datos relacional, también producido por Microsoft, que está
estrechamente unido a su lenguaje de programación. FoxPro es menos
amigable que las bases de datos de usuario final, lo que requiere más
conocimientos técnicos que Access. Este sistema de base de datos es
conocido por su motor de procesamiento rápido y la capacidad de manejar
numerosas transacciones simultáneas.
MySQL Database
MySQL es una base de datos
basada en servidor que permite a varios usuarios acceder a múltiples
bases de datos. El software funciona en múltiples plataformas,
incluyendo la mayoría de las variedades de UNIX y Windows. Ofrece
usabilidad de primer plano limitada y está diseñado como un servidor de
base de datos back-end. MySQL se diferencia de otros productos de base
de datos por sus costos, la versión no empresarial se distribuye de
forma gratuita.
SQL Server
SQL Server es un servidor de base
de datos a nivel empresarial escalable. Este producto se diferencia de
la base de datos personal al no proporcionar las herramientas para el
usuario que proporciona un producto de base de datos individual. El
motor de base de datos se centra en responder rápidamente a las
solicitudes del cliente en el formulario de consultas SQL. Estas consultas
se pueden generar directamente en SQL Server, o por medio de una
interfaz de usuario independiente desarrollada en una variedad de
lenguajes de programación. SQL Server está diseñado para manejar bases
de datos con millones de registros.
Oracle
La base de datos Oracle
es otra base de datos escalable a nivel empresarial. La base de datos
de SQL soporta bases de datos corporativas distribuidas, que permiten al
usuario acceder a los datos de forma local o desde bases de datos
remotas en una transacción transparente. Las bases de datos distribuidas
ayudan a superar las limitaciones físicas de un entorno informático
físico. El tamaño máximo de base de datos para una base de datos Oracle
es de 8 millones de terabytes, lo que requiere un almacenamiento físico
más allá de la capacidad de la mayoría de las instalaciones
individuales.
Aplicaciones de bases de datos distribuidas
Los ambientes en los que se encuentra el uso
de las BDD son:
·
Cualquier organización que tiene
una estructura descentralizada: organismos gubernamentales y de servicios
públicos.
·
La industria de la manufactura,
particularmente aquella con plantas múltiples, y la industria automotriz.
·
Aplicaciones de control y comando
militar.
·
Cadenas hoteleras.
·
Líneas de transportación aérea.
·
Servicios bancarios y financieros.
Ejemplos de algunos DDBMS:
Prototipos
• SDD-1, que fue construido en la división de investigación de Computer Corporation of America.
–
Finales de los años 70 y
principios de los 80.
•
R*, una versión distribuida del
prototipo System R, construida en IBM Research
–
Principios de los años 80
•
Distributed Ingres, una versión
distribuida del prototipo Ingres, construida en la Universidad de California en
Berkeley
–
Principios de los 80
Implementaciones comerciales:
• La mayoría de los productos SQL actuales proporcionan algún tipo de soporte de BDD (con diversos grados de funcionalidad).
–
Ingres/Star, el componente de BDD
de Ingres
–
La opción de BDD de Oracle
–
La propiedad de datos distribuidos
de DB2
•
Tanto los DDBMS prototipos como
los productos, son relacionales (al menos todos soportan SQL).
•
Además, hay varias razones por las
cuales, para que un sistema distribuido sea exitoso, debe
ser relacional.
- La tecnología relacional es un requisito previo para tecnología distribuida.
