Fragmentacion horizontal
Páginas: 34 (8385 palabras)
Publicado: 5 de febrero de 2011
Universidad Autónoma del Estado de México
Unidad Académica Profesional “Nezahualcoyotl”
“Base de Datos Distribuidas”
M.C José Carlos Alcántara
Raquel Montes San Agustín
Alejandra Palma Romero
Roberto Daniel Rosas Barrón
Fragmentación Horizontal
Resumen
La tecnología actual favorece el uso y aplicación de las bases de datos distribuidos (BDD): aquellas bases de datos en lasque la información se encuentra en sitios geográficamente separados.
El diseño de la distribución (la fragmentación de las relaciones y su asignación a los sitios de la red) es una de las tareas más complejas involucradas en el diseño de una BDD y, típicamente, no se hace de manera automática.
En este trabajo se presenta un Algoritmo Genético (AG) que se aplica a tal diseño. El AG ataca,simultáneamente, el problema de fragmentar verticalmente y asignar los fragmentos a los sitios de manera óptima. La naturaleza evolutiva del AG permite resolver en paralelo la fragmentación y la asignación: problemas que guardan una relación no lineal entre ellos.
Palabras clave: Bases de Datos, Distribución, Fragmentación, Algoritmos Genéticos.
Introducción
El diseño de BDDs incluye, ademásde los problemas de diseño clásicos de bases de datos centralizadas, el problema del diseño de la distribución, cuyo propósito es mejorar el rendimiento global del sistema. El diseño de la distribución, a su vez, está compuesto de la fragmentación y de la asignación de los fragmentos a los diversos sitios de la red. La fragmentación es el proceso mediante el cual una relación global esdescompuesta en fragmentos horizontales y/o verticales. Un fragmento vertical atiende al agrupamiento de datos en función de atributos o conjuntos de ellos, mientras que la fragmentación horizontal atiende a dicho agrupamiento en función de tuplas o conjuntos de tuplas. La asignación, por su parte, se refiere al problema de ubicar los fragmentos (ya sean verticales u horizontales) de manera que el acceso ala información se haga de la “mejor” manera posible.
Típicamente, los criterios que determinan si la fragmentación y la asignación son óptimas se establecen de manera independiente. Por ello, es frecuente que se trate de optimizar en dos pasos. En el primero se busca la “mejor” fragmentación y, en el segundo, se busca la “mejor” ubicación de los fragmentos obtenidos en el paso anterior.
Lapartición vertical es el paso en el cual una relación es dividida en grupos de atributos llamados fragmentos verticales. La fragmentación vertical de las relaciones, tradicionalmente, se puede hacer desde dos perspectivas diferentes. Una de ellas parte de considerar que todos los atributos están ubicados en un fragmento único y éste se va dividiendo sucesivamente de acuerdo con algún criterio(típicamente heurístico). La otra, supone que cada atributo es un fragmento y a éstos los va agrupando de manera sucesiva de acuerdo también con algún heurístico. Formulado de esta manera, el problema parece ser bastante sencillo.
Sin embargo, la metodología propuesta tiene dos limitantes fundamentales. En primer lugar, que el número de posibles soluciones crece exponencialmente con el número deatributos. Por ejemplo, en una relación con 10 atributos, el número de subconjuntos disjuntos que se pueden tener, esto es, el número de fragmentos verticales posibles es de 115, 975. (En una relación de m atributos el número de formas en que pueden éstos ser agrupados está definido por el número de Bell B(m). B(m), se acerca a mm para una m suficientemente grande). En segundo lugar los algoritmos deeste estilo usados en la práctica (genéricamente llamados algoritmos best-first) asumen independencia de los eventos considerados. Esta suposición es, en general, inválida; se apela a ella a falta de mejores alternativas.
El propósito de la distribución es mejorar el rendimiento global del sistema por lo que tanto la fragmentación como la ubicación de los fragmentos en la red deben estar...
Unidad Académica Profesional “Nezahualcoyotl”
“Base de Datos Distribuidas”
M.C José Carlos Alcántara
Raquel Montes San Agustín
Alejandra Palma Romero
Roberto Daniel Rosas Barrón
Fragmentación Horizontal
Resumen
La tecnología actual favorece el uso y aplicación de las bases de datos distribuidos (BDD): aquellas bases de datos en lasque la información se encuentra en sitios geográficamente separados.
El diseño de la distribución (la fragmentación de las relaciones y su asignación a los sitios de la red) es una de las tareas más complejas involucradas en el diseño de una BDD y, típicamente, no se hace de manera automática.
En este trabajo se presenta un Algoritmo Genético (AG) que se aplica a tal diseño. El AG ataca,simultáneamente, el problema de fragmentar verticalmente y asignar los fragmentos a los sitios de manera óptima. La naturaleza evolutiva del AG permite resolver en paralelo la fragmentación y la asignación: problemas que guardan una relación no lineal entre ellos.
Palabras clave: Bases de Datos, Distribución, Fragmentación, Algoritmos Genéticos.
Introducción
El diseño de BDDs incluye, ademásde los problemas de diseño clásicos de bases de datos centralizadas, el problema del diseño de la distribución, cuyo propósito es mejorar el rendimiento global del sistema. El diseño de la distribución, a su vez, está compuesto de la fragmentación y de la asignación de los fragmentos a los diversos sitios de la red. La fragmentación es el proceso mediante el cual una relación global esdescompuesta en fragmentos horizontales y/o verticales. Un fragmento vertical atiende al agrupamiento de datos en función de atributos o conjuntos de ellos, mientras que la fragmentación horizontal atiende a dicho agrupamiento en función de tuplas o conjuntos de tuplas. La asignación, por su parte, se refiere al problema de ubicar los fragmentos (ya sean verticales u horizontales) de manera que el acceso ala información se haga de la “mejor” manera posible.
Típicamente, los criterios que determinan si la fragmentación y la asignación son óptimas se establecen de manera independiente. Por ello, es frecuente que se trate de optimizar en dos pasos. En el primero se busca la “mejor” fragmentación y, en el segundo, se busca la “mejor” ubicación de los fragmentos obtenidos en el paso anterior.
Lapartición vertical es el paso en el cual una relación es dividida en grupos de atributos llamados fragmentos verticales. La fragmentación vertical de las relaciones, tradicionalmente, se puede hacer desde dos perspectivas diferentes. Una de ellas parte de considerar que todos los atributos están ubicados en un fragmento único y éste se va dividiendo sucesivamente de acuerdo con algún criterio(típicamente heurístico). La otra, supone que cada atributo es un fragmento y a éstos los va agrupando de manera sucesiva de acuerdo también con algún heurístico. Formulado de esta manera, el problema parece ser bastante sencillo.
Sin embargo, la metodología propuesta tiene dos limitantes fundamentales. En primer lugar, que el número de posibles soluciones crece exponencialmente con el número deatributos. Por ejemplo, en una relación con 10 atributos, el número de subconjuntos disjuntos que se pueden tener, esto es, el número de fragmentos verticales posibles es de 115, 975. (En una relación de m atributos el número de formas en que pueden éstos ser agrupados está definido por el número de Bell B(m). B(m), se acerca a mm para una m suficientemente grande). En segundo lugar los algoritmos deeste estilo usados en la práctica (genéricamente llamados algoritmos best-first) asumen independencia de los eventos considerados. Esta suposición es, en general, inválida; se apela a ella a falta de mejores alternativas.
El propósito de la distribución es mejorar el rendimiento global del sistema por lo que tanto la fragmentación como la ubicación de los fragmentos en la red deben estar...
Leer documento completo
Regístrate para leer el documento completo.