En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos




descargar 0.75 Mb.
títuloEn años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos
página12/36
fecha de publicación02.02.2016
tamaño0.75 Mb.
tipoDocumentos
b.se-todo.com > Economía > Documentos
1   ...   8   9   10   11   12   13   14   15   ...   36

3.5 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 Valor
donde { =, <, ,,>, } 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:


  1. La selectividad de los minitérminos: Denotada como sel( mi ), se refiere al número de tuplas de la relación que serán accesadas por una consulta de usuario especificada de acuerdo a un predicado minitérmino dado.

  2. 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 = 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 todos los presupuestos de los proyectos en cada lugar (1)

Encontrar proyectos con presupuestos menores a $200000. (2)

De acuerdo a (1),

Pr = { LUGAR = "México", LUGAR = "Puebla", LUGAR = "Guadalajara", LUGAR = "Monterrey" }
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.


De manera intuitiva se puede ver que si un predicado influye en la fragmentación, esto es, causa que un fragmento f se fragmente aún más digamos en fi y fj, entonces habría una consulta que accese fi y fj de manera diferente. En otras palabras, un predicado debe ser relevante en determinar una fragmentación. Si todos los predicados de un conjunto Pr son relevantes, entonces Pr es mínimo.
La definición formal de relevancia es la siguiente. Sean mi y mj dos predicados minitérminos definidos exactamente igual excepto que mi contiene a pi y mj contiene a pj. También, sean fi y fj los dos fragmentos definidos de acuerdo a mi y mj, respectivamente. Entonces, pi es relevante si y solo si
acc(mi)/card(fi) acc(mj)/card(fj)
Por ejemplo, el conjunto Pr definido arriba es mínimo y completo. Sin embargo, si se le agrega el predicado JNOMBRE = "Instrumentación", entonces, Pr no es mínimo.
El algoritmo siguiente llamado COM_MIN genera un conjunto completo y mínimo de predicados Pr’ dado un conjunto de predicados simple Pr. Por brevedad durante el algoritmo se utiliza la siguiente regla:
Regla 1: regla fundamental de completes y minimalidad, la cual afirma que una relación o fragmento es particionado en al menos dos partes las cuales se accesan en forma diferente por al menos una consulta de usuario.

 

Algoritmo 3.1 COM_MIN
Entrada: una relación R y un conjunto de predicados simples Pr

Salida: un conjunto completo y mínimo de predicados simples Pr’ para Pr.

  1. Iniciación:

    • Encontrar un pi Pr tal que pi particiona a R de acuerdo a la regla 1.

    • Hacer Pr’ = pi; Pr Prpi; F fi



  1. Iterativamente agregar predicados a Pr’ hasta que sea completo

    • Encontrar un pi Pr tal que pi particiona algún fk de Pr’ de acuerdo a la regla 1.

    • Hacer Pr’ = Pr pi; Pr Prpi; F F fi

    • Si pk Pr’ el cual es no relevante, entonces,

Hacer Pr’ = Pr’ - pk; F F - fk
El algoritmo empieza encontrando un predicado que es relevante y que particiona la relación de entrada. Después, agrega de manera iterativa predicados a este conjunto, asegurando minimalidad en cada paso. Por lo tanto, al final el conjunto Pr’ es tanto completo como mínimo.
El segundo paso en el proceso de diseño de fragmentación horizontal primaria es derivar el conjunto de predicados minitérminos que pueden ser definidos en los predicados del conjunto Pr’. Esos minitérminos definen los fragmentos que serán usados como candidatos en el paso de asignamiento.
El algoritmo de fragmentación horizontal primaria, llamado PHORIZONTAL, se presenta a continuación. La entrada al algoritmo es una relación Ri la cual es sometida a fragmentación horizontal primaria, y Pri, el cual es el conjunto de predicados simples que han sido determinados de acuerdo a las consultas definidas en la relación Ri.
Algoritmo 3.2 PHORIZONTAL
Entrada: Una relación R y un conjunto de predicados simples Pr.

Salida: Un conjunto de predicados minitérminos, M, de acuerdo a los cuales la relación R será fragmentada.

  1. Pr COM_MIN( R, Pr )

  2. determinar el conjunto M de predicados minitérminos

  3. determinar el conjunto I de implicaciones entre pi Pr

  4. eliminar minitérminos contradictorios a partir de M


 

Ejemplo 3.10. Para la relación S la consulta o aplicación es verificar la información del salario y determinar incrementos. Suponga además que los registros de empleados se mantienen en dos lugares y, por tanto, la aplicación o consulta se ejecuta en dos lugares.
Los predicados simples que serían usados para particionar la relación S son:
p1 : SAL 30000

p2 : SAL > 30000
Al aplicar el algoritmo COM_MIN se verifica que Pr = { P1, P2 } se completo y minimal, Pr’ = Pr. Se pueden formar los siguientes predicados minitérminos como miembros de M:
m1: (SAL 30000) (SAL > 30000)

m2: (SAL 30000) NOT (SAL > 30000)

m3: NOT (SAL 30000) (SAL > 30000)

m4: NOT (SAL 30000) NOT (SAL > 30000)
Asumiendo que el dominio de SALARIO se puede partir en dos, como se sugiere Pr p1 y p2, las siguientes implicaciones son obvias:
i1: (SAL 30000) NOT (SAL > 30000)

i2: NOT (SAL 30000) (SAL > 30000)

i3: (SAL > 30000) NOT (SAL 30000)

i4: NOT (SAL > 30000) (SAL 30000)
De acuerdo a i1, m1 es contradictorio; de acuerdo a i2, m4 es contradictorio. Por lo tanto, nos quedamos con M = { m2, m3 }. Por tanto, se definen los dos fragmentos Fs = { S1, S2 } de acuerdo a M.
S1

TITULO

SALARIO

Ingeniero Mecánico

27000

Programador

24000


S1

TITULO

SALARIO

Ingeniero Eléctrico

40000

Analista de Sistemas

34000



Ejemplo 3.11. Para la relación J la consulta es encontrar el nombre y presupuesto de proyectos dados por su número. Esta consulta es realizada en tres lugares. El acceso a la información de proyecto se realiza de acuerdo a su presupuesto; un lugar accesa presupuesto 200000 y el otro accesa presupuesto > 200000.
Los predicados simples para la primera consulta serían:
p1 : LUGAR = "México"

p2 : LUGAR = "Monterrey"

p3 : LUGAR = "Puebla"
Los predicados simples para la segunda consulta serían:
p4 : PRESUPUESTO 200000

p5 : PRESUPUESTO > 200000
Si el algoritmo COM_MIN es seguido, el conjunto Pr’ = {p1, p2, p3, p4, p5} es obviamente completo y mínimo. Basado en Pr’, los siguientes seis minitérminos que forman a M se pueden definir como:
m1: (LUGAR = "México") (PRESUPUESTO 200000)

m2: (LUGAR = "México") (PRESUPUESTO > 200000)

m3: (LUGAR = "Monterrey") (PRESUPUESTO 200000)

m4: (LUGAR = "Monterrey") (PRESUPUESTO > 200000)

m5: (LUGAR = "Puebla") (PRESUPUESTO 200000)

m6: (LUGAR = "Puebla") (PRESUPUESTO > 200000)
Estos no son los únicos minitérminos que se pueden generar. Por ejemplo, es posible especificar predicados de la forma:
p1 p2 p3 p4 p5
Sin embargo, las implicaciones obvias:
i1: p1 p2 p3

i2: p2 p1 p3

i3: p3 p1 p2

i4: p4 p5

i5: p5 p4

i6: p4 p5

i7: p5 p4
eliminan esos minitérminos y nos quedamos con m1 hasta m6. Observando la instancia de la base de datos del ejemplo, podríamos decir que las siguientes implicaciones se mantienen:
i1: (LUGAR = "México") NOT (PRESUPUESTO > 200000)

i2: (LUGAR = "Monterrey") NOT (PRESUPUESTO 200000)

i3: NOT (LUGAR = "México") (PRESUPUESTO 200000)

i4: NOT (LUGAR = "Monterrey") (PRESUPUESTO > 200000)
Sin embargo, recuerde que las implicaciones deben ser definidas de acuerdo a la semántica de la base de datos, no de acuerdo a los valores actuales. Algunos de los fragmentos definidos por M = { m1, m2, m3, m4, m5, m6 } pueden estar vacíos, pero ellos son, no obstante, fragmentos. No existe nada en la semántica de la base de datos que sugiera que las implicaciones i8 hasta i11 se satisfagan.
Los resultados de la fragmentación horizontal primaria de J forman seis fragmentos FJ = { J1, J2, J3, J4, J5, J6 } de acuerdo a los minitérminos de M. Algunos de esos están vacíos y por lo tanto no se presentan aquí.
J1


JNO

JNOMBRE

PRESUPUESTO

LUGAR

J1

Instrumentación

150000

Monterrey


J3


JNO

JNOMBRE

PRESUPUESTO

LUGAR

J2

Desarrollo de bases de datos

135000

México


J4


JNO

JNOMBRE

PRESUPUESTO

LUGAR

J5

CAD/CAM

250000

México


J6


JNO

JNOMBRE

PRESUPUESTO

LUGAR

J4

Mantenimiento

310000

México





Correctitud de la Fragmentación Horizontal Primaria





  • Completitud. Ya que Pr’ es completo y mínimo, los predicados de selección son completos.

  • Reconstrucción. Si la relación R es fragmentada en FR = (R1, R2, ..., Rr), entonces,

R = Ri FR Ri

  • Fragmentos disjuntos. Los predicados minitérminos que forman la base de la fragmentación deben ser mutuamente exclusivos.



1   ...   8   9   10   11   12   13   14   15   ...   36

similar:

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconBases de datos de secuencias de adn y proteínas

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconUna red de comunicaciones es la combinación de hardware, software...

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconResumen a lo largo de los años, la agricultura se ha mantenido como...

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconResumen El presente trabajo de investigación bibliográfica trata...

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconCientífico británico que sentó las bases de la moderna teoría evolutiva,...

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconRecibimos de las distintas sucursales de la empresa los datos correspondientes a las ventas en

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconEntre las herramientas utilizadas en la minería de datos (Data Mining)...

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconMinería de Datos aplicados a las ventas con Tarjeta de Crédito realizados...

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconBases moleculares de las acciones de la insulina

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconBases moleculares de las acciones de la insulina




Todos los derechos reservados. Copyright © 2019
contactos
b.se-todo.com