GUA III
MODELO ENTIDAD RELACIÓN
Entidad
Cualquier tipo de objeto o concepto sobre el que se recoge información: cosa, persona, concepto abstracto o suceso. Por ejemplo: coches, casas, empleados, clientes, empresas, oficios, diseños de productos, conciertos, excursiones, etc. Las entidades se representan gráficamente mediante rectángulos y su nombre aparece en el interior. Un nombre de entidad sólo puede aparecer una vez en el esquema conceptual.
Hay dos tipos de entidades: fuertes y débiles. Una entidad débil es una entidad cuya existencia depende de la existencia de otra entidad. Una entidad fuerte es una entidad que no es débil.
Relación (interrelación)
Es una correspondencia o asociación entre dos o más entidades. Cada relación tiene un nombre que describe su función. Las relaciones se representan gráficamente mediante rombos y su nombre aparece en el interior.
Las entidades que están involucradas en una determinada relación se denominan entidades participantes. El número de participantes en una relación es lo que se denomina grado de la relación. Por lo tanto, una relación en la que participan dos entidades es una relación binaria; si son tres las entidades participantes, la relación es ternaria; etc.
Una relación recursiva es una relación donde la misma entidad participa más de una vez en la relación con distintos papeles. El nombre de estos papeles es importante para determinar la función de cada participación.
La cardinalidad con la que una entidad participa en una relación especifica el número mínimo y el número máximo de correspondencias en las que puede tomar parte cada ocurrencia de dicha entidad. La participación de una entidad en una relación es obligatoria (total) si la existencia de cada una de sus ocurrencias requiere la existencia de, al menos, una ocurrencia de la otra entidad participante. Si no, la participación es opcional (parcial). Las reglas que definen la cardinalidad de las relaciones son las reglas de negocio.
A veces, surgen problemas cuando se está diseñado un esquema conceptual. Estos problemas, denominados trampas, suelen producirse a causa de una mala interpretación en el significado de alguna relación, por lo que es importante comprobar que el esquema conceptual carece de dichas trampas. En general, para encontrar las trampas, hay que asegurarse de que se entiende completamente el significado de cada relación. Si no se entienden las relaciones, se puede crear un esquema que no represente fielmente la realidad.
Una de las trampas que pueden encontrarse ocurre cuando el esquema representa una relación entre entidades, pero el camino entre algunas de sus ocurrencias es ambiguo. El modo de resolverla es reestructurando el esquema para representar la asociación entre las entidades correctamente.
Otra de las trampas sucede cuando un esquema sugiere la existencia de una relación entre entidades, pero el camino entre una y otra no existe para algunas de sus ocurrencias. En este caso, se produce una pérdida de información que se puede subsanar introduciendo la relación que sugería el esquema y que no estaba representada.
Atributo
Es una característica de interés o un hecho sobre una entidad o sobre una relación. Los atributos representan las propiedades básicas de las entidades y de las relaciones. Toda la información extensiva es portada por los atributos. Gráficamente, se representan mediante bolitas que cuelgan de las entidades o relaciones a las que pertenecen.
Cada atributo tiene un conjunto de valores asociados denominado dominio. El dominio define todos los valores posibles que puede tomar un atributo. Puede haber varios atributos definidos sobre un mismo dominio.
Los atributos pueden ser simples o compuestos. Un atributo simple es un atributo que tiene un solo componente, que no se puede dividir en partes más pequeñas que tengan un significado propio. Un atributo compuesto es un atributo con varios componentes, cada uno con un significado por sí mismo. Un grupo de atributos se representa mediante un atributo compuesto cuando tienen afinidad en cuanto a su significado, o en cuanto a su uso. Un atributo compuesto se representa gráficamente mediante un óvalo.
Los atributos también pueden clasificarse en monovalentes o polivalentes. Un atributo monovalente es aquel que tiene un solo valor para cada ocurrencia de la entidad o relación a la que pertenece. Un atributo polivalente es aquel que tiene varios valores para cada ocurrencia de la entidad o relación a la que pertenece. A estos atributos también se les denomina multivaluados, y pueden tener un número máximo y un número mínimo de valores. La cardinalidad de un atributo indica el número mínimo y el número máximo de valores que puede tomar para cada ocurrencia de la entidad o relación a la que pertenece. El valor por omisión es .
Por último, los atributos pueden ser derivados. Un atributo derivado es aquel que representa un valor que se puede obtener a partir del valor de uno o varios atributos, que no necesariamente deben pertenecer a la misma entidad o relación.
Identificador
Un identificador de una entidad es un atributo o conjunto de atributos que determina de modo único cada ocurrencia de esa entidad. Un identificador de una entidad debe cumplir dos condiciones:
No pueden existir dos ocurrencias de la entidad con el mismo valor del identificador.
Si se omite cualquier atributo del identificador, la condición anterior deja de cumplirse.
Toda entidad tiene al menos un identificador y puede tener varios identificadores alternativos. Las relaciones no tienen identificadores.
Jerarquía de generalización
Una entidad E es una generalización de un grupo de entidades E , E , ... E , si cada ocurrencia de cada una de esas entidades es también una ocurrencia de E. Todas las propiedades de la entidad genérica E son heredadas por las subentidades.
Cada jerarquía es total o parcial, y exclusiva o superpuesta. Una jerarquía es total si cada ocurrencia de la entidad genérica corresponde al menos con una ocurrencia de alguna subentidad. Es parcial si existe alguna ocurrencia de la entidad genérica que no corresponde con ninguna ocurrencia de ninguna subentidad. Una jerarquía es exclusiva si cada ocurrencia de la entidad genérica corresponde, como mucho, con una ocurrencia de una sola de las subentidades. Es superpuesta si existe alguna ocurrencia de la entidad genérica que corresponde a ocurrencias de dos o más subentidades diferentes.
Un subconjunto es un caso particular de generalización con una sola entidad como subentidad. Un subconjunto siempre es una jerarquía parcial y exclusiva.
NORMALIZACIÓN DE DATOS
Formas Normales
Las primeras tres formas normales son suficientes para cubrir las necesidades de la mayoría de las bases de datos. El creador de estas 3 primeras formas normales (o reglas) fue Edgar F. Codd, éste introdujo la normalización en un artículo llamado A Relational Model of Data for Large Shared Data Banks Communications of the ACM, Vol. 13, No. 6, June 1970, pp. 377-387[1].
Primera Forma Normal (1NF)
Una relación está en Primera Forma Normal si y sólo si todos los dominios son atómicos. Un dominio es atómico si los elementos del dominio son indivisibles.
Por ejemplo:
La Relación:
Cursos: nombre, código, vacantes, horario, bibliografía
Queda después de aplicar la Forma Normal 1 de la siguiente manera:
Cursos1: nombre, código, vacantes
Horario1: código, día, módulo
Bibliografia1: código, nombre, autor
Una columna no puede tener múltiples valores. Los datos están atómicos (Si a cada valor de X le pertenece un valor de Y, entonces a cada valor de Y le pertenece un valor de X).
La regla de la Primera Forma Normal establece que las columnas repetidas deben eliminarse y colocarse en tablas separadas
Segunda Forma Normal (2NF)
Dependencia completa. Esta en 2NF si esta en 1NF y si sus atributos no principales dependen de forma completa de la clave principal. Toda columna que no sea clave debe depender por completo de la clave primaria. Los atributos dependen de la clave. Varia la clave y varían los atributos. Dependencia completa. Sus atributos no principales dependen de forma completa de la clave principal.
Tercera Forma Normal (3NF)
Está en forma normal de Boyce-Codd y se eliminan las dependencias multivaluadas y se generan todas las relaciones externas con otras tablas u otras bases de datos. Esta se hace a base de claves
Cuarta Forma Normal (4NF)
Está en cuarta forma normal y toda dependencia-join viene implicada por claves candidatas.
Reglas de Codd
Codd se dio de cuenta que existían bases de datos en el mercado las cuales decían ser relacionales, pero lo único que hacían era guardar la información en las tablas, sin estas tablas estar literalmente normalizadas; entonces éste publicó 12 reglas que un verdadero sistema relacional debería de tener, en la práctica algunas de ellas son difíciles de realizar.Un sistema podrá considerarse "más relacional" cuanto más siga estas reglas.
Regla No. 1 - La Regla de la información
"Toda la información en un RDBMS está explícitamente representada de una sola manera por valores en una tabla".
Cualquier cosa que no exista en una tabla no existe del todo. Toda la información, incluyendo nombres de tablas, nombres de vistas, nombres de columnas, y los datos de las columnas deben estar almacenados en tablas dentro de las bases de datos. Las tablas que contienen tal información constituyen el Diccionario de Datos.
Regla No. 2 - La regla del acceso garantizado
"Cada ítem de datos debe ser lógicamente accesible al ejecutar una búsqueda que combine el nombre de la tabla, su clave primaria, y el nombre de la columna".
Esto significa que dado un nombre de tabla, dado el valor de la clave primaria, y dado el nombre de la columna requerida, deberá encontrarse uno y solamente un valor. Por esta razón la definición de claves primarias para todas las tablas es prácticamente obligatoria.
Regla No. 3 - Tratamiento sistemático de los valores nulos
"La información inaplicable o faltante puede ser representada a través de valores nulos".
Un RDBMS (Sistema Gestor de Bases de Datos Relacionales) debe ser capaz de soportar el uso de valores nulos en el lugar de columnas cuyos valores sean desconocidos o inaplicables.
Regla No. 4 - La regla de la descripción de la base de datos
"La descripción de la base de datos es almacenada de la misma manera que los datos ordinarios, esto es, en tablas y columnas, y debe ser accesible a los usuarios autorizados".
La información de tablas, vistas, permisos de acceso de usuarios autorizados, etc, debe ser almacenada exactamente de la misma manera: En tablas. Estas tablas deben ser accesibles igual que todas las tablas, a través de sentencias de SQL.
Regla No. 5 - La regla del sub-lenguaje Integral
"Debe haber al menos un lenguaje que sea integral para soportar la definición de datos, manipulación de datos, definición de vistas, restricciones de integridad, y control de autorizaciones y transacciones".
Esto significa que debe haber por lo menos un lenguaje con una sintaxis bien definida que pueda ser usado para administrar completamente la base de datos.
Regla No. 6 - La regla de la actualización de vistas
"Todas las vistas que son teóricamente actualizables, deben ser actualizables por el sistema mismo".
La mayoría de las RDBMS permiten actualizar vistas simples, pero deshabilitan los intentos de actualizar vistas complejas.
Regla No. 7 - La regla de insertar y actualizar
"La capacidad de manejar una base de datos con operandos simples aplica no solo para la recuperación o consulta de datos, sino también para la inserción, actualización y borrado de datos".
Esto significa que las cláusulas SELECT, UPDATE, DELETE e INSERT deben estar disponibles y operables sobre los registros, independientemente del tipo de relaciones y restricciones que haya entre las tablas.
Regla No. 8 - La regla de independencia física
"El acceso de usuarios a la base de datos a través de terminales o programas de aplicación, debe permanecer consistente lógicamente cuando quiera que haya cambios en los datos almacenados, o sean cambiados los métodos de acceso a los datos".
El comportamiento de los programas de aplicación y de la actividad de usuarios vía terminales debería ser predecible basados en la definición lógica de la base de datos, y éste comportamiento debería permanecer inalterado, independientemente de los cambios en la definición física de ésta.
Regla No. 9 - La regla de independencia lógica
"Los programas de aplicación y las actividades de acceso por terminal deben permanecer lógicamente inalteradas cuando quiera que se hagan cambios (según los permisos asignados) en las tablas de la base de datos".
La independencia lógica de los datos especifica que los programas de aplicación y las actividades de terminal deben ser independientes de la estructura lógica, por lo tanto los cambios en la estructura lógica no deben alterar o modificar estos programas de aplicación.
Regla No. 10 - La regla de la independencia de la integridad
"Todas las restricciones de integridad deben ser definibles en los datos, y almacenables en el catalogo, no en el programa de aplicación".
Las reglas de integridad son:
1. Ningún componente de una clave primaria puede tener valores en blanco o nulos. (Esta es la norma básica de integridad).
2. Para cada valor de clave foránea deberá existir un valor de clave primaria concordante. La combinación de estas reglas aseguran que haya Integridad referencial.
Regla No. 11 - La regla de la distribución
"El sistema debe poseer un lenguaje de datos que pueda soportar que la base de datos esté distribuida físicamente en distintos lugares sin que esto afecte o altere a los programas de aplicación".
El soporte para bases de datos distribuidas significa que una colección arbitraria de relaciones, bases de datos corriendo en una mezcla de distintas máquinas y distintos sistemas operativos y que este conectada por una variedad de redes, pueda funcionar como si estuviera disponible como en una única base de datos en una sola máquina.
Regla No. 12 - Regla de la no-subversión
"Si el sistema tiene lenguajes de bajo nivel, estos lenguajes de ninguna manera pueden ser usados para violar la integridad de las reglas y restricciones expresadas en un lenguaje de alto nivel (como SQL)".
Algunos productos solamente construyen una interfaz relacional para sus bases de datos No relacionales, lo que hace posible la subversión (violación) de las restricciones de integridad. Esto no debe ser permitido
FRAGMENTACION
Dado que una relación se corresponde esencialmente con una tabla y la cuestión consiste en dividirla en fragmentos menores, inmediatamente surgen dos alternativas lógicas para llevar a cabo el proceso: la división horizontal y la división vertical.
La división o fragmentación horizontal trabaja sobre las tuplas, dividiendo la relación en subrelaciones que contienen un subconjunto de las tuplas que alberga la primera.
La fragmentación vertical, en cambio, se basa en los atributos de la relación para efectuar la división. Estos dos tipos de partición podrían considerarse los fundamentales y básicos. Sin embargo, existen otras alternativas.
Fundamentalmente, se habla de fragmentación mixta o híbrida cuando el proceso de partición hace uso de los dos tipos anteriores. La fragmentación mixta puede llevarse a cabo de tres formas diferentes: desarrollando primero la fragmentación vertical y, posteriormente, aplicando la partición horizontal sobre los fragmentos verticales (denominada partición VH), o aplicando primero una división horizontal para luego, sobre los fragmentos generados, desarrollar una fragmentación vertical (llamada partición HV), o bien, de forma directa considerando la semántica de las transacciones. Otro enfoque distinto y relativamente nuevo [2], consiste en aplicar sobre una relación, de forma simultánea y no secuencial, la fragmentación horizontal y la fragmentación vertical; en este caso, se generara una rejilla y los fragmentos formaran las celdas de esa rejilla, cada celda será exactamente un fragmento vertical y un fragmento horizontal (nótese que en este caso el grado de fragmentación alcanzado es máximo, y no por ello la descomposición resultará más eficiente).
Volviendo a la figura 3, puede observarse como los casos C y D se basan en la mencionada generación de la rejilla, con la diferencia que en el primero de ellos se produce una fusión, una desfragmentación de las celdas, agrupándolas de la manera más adecuada para obtener mayor rendimiento, ya que los fragmentos generados son muy pequeños. En el segundo caso se asignan las celdas a los sitios y luego se realiza una rigurosa optimización de cada sitio. El caso E sería aquel en el que se utiliza la fragmentación VH o la fragmentación HV.
Grado de fragmentación. Cuando se va a fragmentar una base de datos deberíamos sopesar qué grado de fragmentación va a alcanzar, ya que éste será un factor que influirá notablemente en el desarrollo de la ejecución de las consultas. El grado de fragmentación puede variar desde una ausencia de la división, considerando a las relaciones unidades de fragmentación; o bien, fragmentar a un grado en el cada tupla o atributo forme un fragmento. Ante estos dos casos extremos, evidentemente se ha de buscar un compromiso intermedio, el cual debería establecerse sobre las características de las aplicaciones que hacen uso de la base de datos. Dichas características se podrán formalizar en una serie de parámetros. De acuerdo con sus valores, se podrá establecer el grado de fragmentación del banco de datos.
Grado de fragmentación.
Cuando se va a fragmentar una base de datos deberíamos sopesar qué grado de fragmentación va a alcanzar, ya que éste será un factor que influirá notablemente en el desarrollo de la ejecución de las consultas. El grado de fragmentación puede variar desde una ausencia de la división, considerando a las relaciones unidades de fragmentación; o bien, fragmentar a un grado en el cada tupla o atributo forme un fragmento. Ante estos dos casos extremos, evidentemente se ha de buscar un compromiso intermedio, el cual debería establecerse sobre las características de las aplicaciones que hacen uso de la base de datos. Dichas características se podrán formalizar en una serie de parámetros. De acuerdo con sus valores, se podrá establecer el grado de fragmentación del banco de datos.
Reglas de corrección de la fragmentación.
A continuación se enuncian las tres reglas que se han de cumplir durante el proceso de fragmentación, las cuales asegurarán la ausencia de cambios semánticos en la base de datos durante el proceso.
Compleción. Si una relación R se descompone en una serie de fragmentos R1, R2,..., Rn, cada elemento de datos que pueda encontrarse en R deberá poder encontrarse en uno o varios fragmentos Ri. Esta propiedad extremadamente importante asegura que los datos de la relación global se proyectan sobre los fragmentos sin pérdida alguna. Tenga en cuenta que en el caso horizontal el elemento de datos, normalmente, es una tupla, mientras que en el caso vertical es un atributo.
Reconstrucción. Si una relación R se descompone en una serie de fragmentos R1, R2, ..., Rn, puede definirse una operador relacional tal que
El operador será diferente dependiendo de las diferentes formas de fragmentación. La reconstrucción de la relación a partir de sus fragmentos asegura la preservación de las restricciones definidas sobre los datos en forma de dependencias.
Disyunción. Si una relación R se descompone horizontalmente en una serie de fragmentos R1, R2,..., Rn, y un elemento de datos di se encuentra en algún fragmento Rj, entonces no se encuentra en otro fragmento Rk (k j). Esta regla asegura que los fragmentos horizontales sean disjuntos. Si una relación R se descompone verticalmente, sus atributos primarios clave normalmente se repiten en todos sus fragmentos.
- Alternativas de asignación
Partiendo del supuesto que el banco de datos se haya fragmentado correctamente, habrá que decidir sobre la manera de asignar los fragmentos a los distintos sitios de la red. Cuando una serie de datos se asignan, éstos pueden replicarse para mantener una copia. Las razones para la réplica giran en torno a la seguridad y a la eficiencia de las consultas de lectura. Si existen muchas reproducciones de un elemento de datos, en caso de fallo en el sistema se podría acceder a esos datos ubicados en sitios distintos. Además, las consultas que acceden a los mismos datos pueden ejecutarse en paralelo, ya que habrá copias en diferentes sitios. Por otra parte, la ejecución de consultas de actualización, de escritura, implicaría la actualización de todas las copias que existan en la red, cuyo proceso puede resultar problemático y complicado. Por tanto, un buen parámetro para afrontar el grado de réplica consistiría en sopesar la cantidad de consultas de lectura que se efectuarán, así como el número de consultas de escritura que se llevarán a cabo.
En una red donde las consultas que se procesen sean mayoritariamente de lectura, se podría alcanzar un alto grado de réplica, no así en el caso contrario. Una base de datos fragmentada es aquella donde no existe réplica alguna. Los fragmentos se alojan en sitios donde únicamente existe una copia de cada uno de ellos a lo largo de toda la red. En caso de réplica, podemos considerar una base de datos totalmente replicada, donde existe una copia de todo el banco de datos en cada sitio, o considerar una base de datos parcialmente replicada donde existan copias de los fragmentos ubicados en diferentes sitios. El número de copias de un fragmento será una de las posibles entradas a los algoritmos de asignación, o una variable de decisión cuyo valor lo determine el algoritmo. La figura 5 compara las tres alternativas de réplica con respecto a distintas funciones de un sistema de base de datos distribuido.
----PUBLICAR CUADRO---
MODELO ENTIDAD RELACIÓN
Entidad
Cualquier tipo de objeto o concepto sobre el que se recoge información: cosa, persona, concepto abstracto o suceso. Por ejemplo: coches, casas, empleados, clientes, empresas, oficios, diseños de productos, conciertos, excursiones, etc. Las entidades se representan gráficamente mediante rectángulos y su nombre aparece en el interior. Un nombre de entidad sólo puede aparecer una vez en el esquema conceptual.
Hay dos tipos de entidades: fuertes y débiles. Una entidad débil es una entidad cuya existencia depende de la existencia de otra entidad. Una entidad fuerte es una entidad que no es débil.
Relación (interrelación)
Es una correspondencia o asociación entre dos o más entidades. Cada relación tiene un nombre que describe su función. Las relaciones se representan gráficamente mediante rombos y su nombre aparece en el interior.
Las entidades que están involucradas en una determinada relación se denominan entidades participantes. El número de participantes en una relación es lo que se denomina grado de la relación. Por lo tanto, una relación en la que participan dos entidades es una relación binaria; si son tres las entidades participantes, la relación es ternaria; etc.
Una relación recursiva es una relación donde la misma entidad participa más de una vez en la relación con distintos papeles. El nombre de estos papeles es importante para determinar la función de cada participación.
La cardinalidad con la que una entidad participa en una relación especifica el número mínimo y el número máximo de correspondencias en las que puede tomar parte cada ocurrencia de dicha entidad. La participación de una entidad en una relación es obligatoria (total) si la existencia de cada una de sus ocurrencias requiere la existencia de, al menos, una ocurrencia de la otra entidad participante. Si no, la participación es opcional (parcial). Las reglas que definen la cardinalidad de las relaciones son las reglas de negocio.
A veces, surgen problemas cuando se está diseñado un esquema conceptual. Estos problemas, denominados trampas, suelen producirse a causa de una mala interpretación en el significado de alguna relación, por lo que es importante comprobar que el esquema conceptual carece de dichas trampas. En general, para encontrar las trampas, hay que asegurarse de que se entiende completamente el significado de cada relación. Si no se entienden las relaciones, se puede crear un esquema que no represente fielmente la realidad.
Una de las trampas que pueden encontrarse ocurre cuando el esquema representa una relación entre entidades, pero el camino entre algunas de sus ocurrencias es ambiguo. El modo de resolverla es reestructurando el esquema para representar la asociación entre las entidades correctamente.
Otra de las trampas sucede cuando un esquema sugiere la existencia de una relación entre entidades, pero el camino entre una y otra no existe para algunas de sus ocurrencias. En este caso, se produce una pérdida de información que se puede subsanar introduciendo la relación que sugería el esquema y que no estaba representada.
Atributo
Es una característica de interés o un hecho sobre una entidad o sobre una relación. Los atributos representan las propiedades básicas de las entidades y de las relaciones. Toda la información extensiva es portada por los atributos. Gráficamente, se representan mediante bolitas que cuelgan de las entidades o relaciones a las que pertenecen.
Cada atributo tiene un conjunto de valores asociados denominado dominio. El dominio define todos los valores posibles que puede tomar un atributo. Puede haber varios atributos definidos sobre un mismo dominio.
Los atributos pueden ser simples o compuestos. Un atributo simple es un atributo que tiene un solo componente, que no se puede dividir en partes más pequeñas que tengan un significado propio. Un atributo compuesto es un atributo con varios componentes, cada uno con un significado por sí mismo. Un grupo de atributos se representa mediante un atributo compuesto cuando tienen afinidad en cuanto a su significado, o en cuanto a su uso. Un atributo compuesto se representa gráficamente mediante un óvalo.
Los atributos también pueden clasificarse en monovalentes o polivalentes. Un atributo monovalente es aquel que tiene un solo valor para cada ocurrencia de la entidad o relación a la que pertenece. Un atributo polivalente es aquel que tiene varios valores para cada ocurrencia de la entidad o relación a la que pertenece. A estos atributos también se les denomina multivaluados, y pueden tener un número máximo y un número mínimo de valores. La cardinalidad de un atributo indica el número mínimo y el número máximo de valores que puede tomar para cada ocurrencia de la entidad o relación a la que pertenece. El valor por omisión es .
Por último, los atributos pueden ser derivados. Un atributo derivado es aquel que representa un valor que se puede obtener a partir del valor de uno o varios atributos, que no necesariamente deben pertenecer a la misma entidad o relación.
Identificador
Un identificador de una entidad es un atributo o conjunto de atributos que determina de modo único cada ocurrencia de esa entidad. Un identificador de una entidad debe cumplir dos condiciones:
No pueden existir dos ocurrencias de la entidad con el mismo valor del identificador.
Si se omite cualquier atributo del identificador, la condición anterior deja de cumplirse.
Toda entidad tiene al menos un identificador y puede tener varios identificadores alternativos. Las relaciones no tienen identificadores.
Jerarquía de generalización
Una entidad E es una generalización de un grupo de entidades E , E , ... E , si cada ocurrencia de cada una de esas entidades es también una ocurrencia de E. Todas las propiedades de la entidad genérica E son heredadas por las subentidades.
Cada jerarquía es total o parcial, y exclusiva o superpuesta. Una jerarquía es total si cada ocurrencia de la entidad genérica corresponde al menos con una ocurrencia de alguna subentidad. Es parcial si existe alguna ocurrencia de la entidad genérica que no corresponde con ninguna ocurrencia de ninguna subentidad. Una jerarquía es exclusiva si cada ocurrencia de la entidad genérica corresponde, como mucho, con una ocurrencia de una sola de las subentidades. Es superpuesta si existe alguna ocurrencia de la entidad genérica que corresponde a ocurrencias de dos o más subentidades diferentes.
Un subconjunto es un caso particular de generalización con una sola entidad como subentidad. Un subconjunto siempre es una jerarquía parcial y exclusiva.
NORMALIZACIÓN DE DATOS
Formas Normales
Las primeras tres formas normales son suficientes para cubrir las necesidades de la mayoría de las bases de datos. El creador de estas 3 primeras formas normales (o reglas) fue Edgar F. Codd, éste introdujo la normalización en un artículo llamado A Relational Model of Data for Large Shared Data Banks Communications of the ACM, Vol. 13, No. 6, June 1970, pp. 377-387[1].
Primera Forma Normal (1NF)
Una relación está en Primera Forma Normal si y sólo si todos los dominios son atómicos. Un dominio es atómico si los elementos del dominio son indivisibles.
Por ejemplo:
La Relación:
Cursos: nombre, código, vacantes, horario, bibliografía
Queda después de aplicar la Forma Normal 1 de la siguiente manera:
Cursos1: nombre, código, vacantes
Horario1: código, día, módulo
Bibliografia1: código, nombre, autor
Una columna no puede tener múltiples valores. Los datos están atómicos (Si a cada valor de X le pertenece un valor de Y, entonces a cada valor de Y le pertenece un valor de X).
La regla de la Primera Forma Normal establece que las columnas repetidas deben eliminarse y colocarse en tablas separadas
Segunda Forma Normal (2NF)
Dependencia completa. Esta en 2NF si esta en 1NF y si sus atributos no principales dependen de forma completa de la clave principal. Toda columna que no sea clave debe depender por completo de la clave primaria. Los atributos dependen de la clave. Varia la clave y varían los atributos. Dependencia completa. Sus atributos no principales dependen de forma completa de la clave principal.
Tercera Forma Normal (3NF)
Está en forma normal de Boyce-Codd y se eliminan las dependencias multivaluadas y se generan todas las relaciones externas con otras tablas u otras bases de datos. Esta se hace a base de claves
Cuarta Forma Normal (4NF)
Está en cuarta forma normal y toda dependencia-join viene implicada por claves candidatas.
Reglas de Codd
Codd se dio de cuenta que existían bases de datos en el mercado las cuales decían ser relacionales, pero lo único que hacían era guardar la información en las tablas, sin estas tablas estar literalmente normalizadas; entonces éste publicó 12 reglas que un verdadero sistema relacional debería de tener, en la práctica algunas de ellas son difíciles de realizar.Un sistema podrá considerarse "más relacional" cuanto más siga estas reglas.
Regla No. 1 - La Regla de la información
"Toda la información en un RDBMS está explícitamente representada de una sola manera por valores en una tabla".
Cualquier cosa que no exista en una tabla no existe del todo. Toda la información, incluyendo nombres de tablas, nombres de vistas, nombres de columnas, y los datos de las columnas deben estar almacenados en tablas dentro de las bases de datos. Las tablas que contienen tal información constituyen el Diccionario de Datos.
Regla No. 2 - La regla del acceso garantizado
"Cada ítem de datos debe ser lógicamente accesible al ejecutar una búsqueda que combine el nombre de la tabla, su clave primaria, y el nombre de la columna".
Esto significa que dado un nombre de tabla, dado el valor de la clave primaria, y dado el nombre de la columna requerida, deberá encontrarse uno y solamente un valor. Por esta razón la definición de claves primarias para todas las tablas es prácticamente obligatoria.
Regla No. 3 - Tratamiento sistemático de los valores nulos
"La información inaplicable o faltante puede ser representada a través de valores nulos".
Un RDBMS (Sistema Gestor de Bases de Datos Relacionales) debe ser capaz de soportar el uso de valores nulos en el lugar de columnas cuyos valores sean desconocidos o inaplicables.
Regla No. 4 - La regla de la descripción de la base de datos
"La descripción de la base de datos es almacenada de la misma manera que los datos ordinarios, esto es, en tablas y columnas, y debe ser accesible a los usuarios autorizados".
La información de tablas, vistas, permisos de acceso de usuarios autorizados, etc, debe ser almacenada exactamente de la misma manera: En tablas. Estas tablas deben ser accesibles igual que todas las tablas, a través de sentencias de SQL.
Regla No. 5 - La regla del sub-lenguaje Integral
"Debe haber al menos un lenguaje que sea integral para soportar la definición de datos, manipulación de datos, definición de vistas, restricciones de integridad, y control de autorizaciones y transacciones".
Esto significa que debe haber por lo menos un lenguaje con una sintaxis bien definida que pueda ser usado para administrar completamente la base de datos.
Regla No. 6 - La regla de la actualización de vistas
"Todas las vistas que son teóricamente actualizables, deben ser actualizables por el sistema mismo".
La mayoría de las RDBMS permiten actualizar vistas simples, pero deshabilitan los intentos de actualizar vistas complejas.
Regla No. 7 - La regla de insertar y actualizar
"La capacidad de manejar una base de datos con operandos simples aplica no solo para la recuperación o consulta de datos, sino también para la inserción, actualización y borrado de datos".
Esto significa que las cláusulas SELECT, UPDATE, DELETE e INSERT deben estar disponibles y operables sobre los registros, independientemente del tipo de relaciones y restricciones que haya entre las tablas.
Regla No. 8 - La regla de independencia física
"El acceso de usuarios a la base de datos a través de terminales o programas de aplicación, debe permanecer consistente lógicamente cuando quiera que haya cambios en los datos almacenados, o sean cambiados los métodos de acceso a los datos".
El comportamiento de los programas de aplicación y de la actividad de usuarios vía terminales debería ser predecible basados en la definición lógica de la base de datos, y éste comportamiento debería permanecer inalterado, independientemente de los cambios en la definición física de ésta.
Regla No. 9 - La regla de independencia lógica
"Los programas de aplicación y las actividades de acceso por terminal deben permanecer lógicamente inalteradas cuando quiera que se hagan cambios (según los permisos asignados) en las tablas de la base de datos".
La independencia lógica de los datos especifica que los programas de aplicación y las actividades de terminal deben ser independientes de la estructura lógica, por lo tanto los cambios en la estructura lógica no deben alterar o modificar estos programas de aplicación.
Regla No. 10 - La regla de la independencia de la integridad
"Todas las restricciones de integridad deben ser definibles en los datos, y almacenables en el catalogo, no en el programa de aplicación".
Las reglas de integridad son:
1. Ningún componente de una clave primaria puede tener valores en blanco o nulos. (Esta es la norma básica de integridad).
2. Para cada valor de clave foránea deberá existir un valor de clave primaria concordante. La combinación de estas reglas aseguran que haya Integridad referencial.
Regla No. 11 - La regla de la distribución
"El sistema debe poseer un lenguaje de datos que pueda soportar que la base de datos esté distribuida físicamente en distintos lugares sin que esto afecte o altere a los programas de aplicación".
El soporte para bases de datos distribuidas significa que una colección arbitraria de relaciones, bases de datos corriendo en una mezcla de distintas máquinas y distintos sistemas operativos y que este conectada por una variedad de redes, pueda funcionar como si estuviera disponible como en una única base de datos en una sola máquina.
Regla No. 12 - Regla de la no-subversión
"Si el sistema tiene lenguajes de bajo nivel, estos lenguajes de ninguna manera pueden ser usados para violar la integridad de las reglas y restricciones expresadas en un lenguaje de alto nivel (como SQL)".
Algunos productos solamente construyen una interfaz relacional para sus bases de datos No relacionales, lo que hace posible la subversión (violación) de las restricciones de integridad. Esto no debe ser permitido
FRAGMENTACION
Dado que una relación se corresponde esencialmente con una tabla y la cuestión consiste en dividirla en fragmentos menores, inmediatamente surgen dos alternativas lógicas para llevar a cabo el proceso: la división horizontal y la división vertical.
La división o fragmentación horizontal trabaja sobre las tuplas, dividiendo la relación en subrelaciones que contienen un subconjunto de las tuplas que alberga la primera.
La fragmentación vertical, en cambio, se basa en los atributos de la relación para efectuar la división. Estos dos tipos de partición podrían considerarse los fundamentales y básicos. Sin embargo, existen otras alternativas.
Fundamentalmente, se habla de fragmentación mixta o híbrida cuando el proceso de partición hace uso de los dos tipos anteriores. La fragmentación mixta puede llevarse a cabo de tres formas diferentes: desarrollando primero la fragmentación vertical y, posteriormente, aplicando la partición horizontal sobre los fragmentos verticales (denominada partición VH), o aplicando primero una división horizontal para luego, sobre los fragmentos generados, desarrollar una fragmentación vertical (llamada partición HV), o bien, de forma directa considerando la semántica de las transacciones. Otro enfoque distinto y relativamente nuevo [2], consiste en aplicar sobre una relación, de forma simultánea y no secuencial, la fragmentación horizontal y la fragmentación vertical; en este caso, se generara una rejilla y los fragmentos formaran las celdas de esa rejilla, cada celda será exactamente un fragmento vertical y un fragmento horizontal (nótese que en este caso el grado de fragmentación alcanzado es máximo, y no por ello la descomposición resultará más eficiente).
Volviendo a la figura 3, puede observarse como los casos C y D se basan en la mencionada generación de la rejilla, con la diferencia que en el primero de ellos se produce una fusión, una desfragmentación de las celdas, agrupándolas de la manera más adecuada para obtener mayor rendimiento, ya que los fragmentos generados son muy pequeños. En el segundo caso se asignan las celdas a los sitios y luego se realiza una rigurosa optimización de cada sitio. El caso E sería aquel en el que se utiliza la fragmentación VH o la fragmentación HV.
Grado de fragmentación. Cuando se va a fragmentar una base de datos deberíamos sopesar qué grado de fragmentación va a alcanzar, ya que éste será un factor que influirá notablemente en el desarrollo de la ejecución de las consultas. El grado de fragmentación puede variar desde una ausencia de la división, considerando a las relaciones unidades de fragmentación; o bien, fragmentar a un grado en el cada tupla o atributo forme un fragmento. Ante estos dos casos extremos, evidentemente se ha de buscar un compromiso intermedio, el cual debería establecerse sobre las características de las aplicaciones que hacen uso de la base de datos. Dichas características se podrán formalizar en una serie de parámetros. De acuerdo con sus valores, se podrá establecer el grado de fragmentación del banco de datos.
Grado de fragmentación.
Cuando se va a fragmentar una base de datos deberíamos sopesar qué grado de fragmentación va a alcanzar, ya que éste será un factor que influirá notablemente en el desarrollo de la ejecución de las consultas. El grado de fragmentación puede variar desde una ausencia de la división, considerando a las relaciones unidades de fragmentación; o bien, fragmentar a un grado en el cada tupla o atributo forme un fragmento. Ante estos dos casos extremos, evidentemente se ha de buscar un compromiso intermedio, el cual debería establecerse sobre las características de las aplicaciones que hacen uso de la base de datos. Dichas características se podrán formalizar en una serie de parámetros. De acuerdo con sus valores, se podrá establecer el grado de fragmentación del banco de datos.
Reglas de corrección de la fragmentación.
A continuación se enuncian las tres reglas que se han de cumplir durante el proceso de fragmentación, las cuales asegurarán la ausencia de cambios semánticos en la base de datos durante el proceso.
Compleción. Si una relación R se descompone en una serie de fragmentos R1, R2,..., Rn, cada elemento de datos que pueda encontrarse en R deberá poder encontrarse en uno o varios fragmentos Ri. Esta propiedad extremadamente importante asegura que los datos de la relación global se proyectan sobre los fragmentos sin pérdida alguna. Tenga en cuenta que en el caso horizontal el elemento de datos, normalmente, es una tupla, mientras que en el caso vertical es un atributo.
Reconstrucción. Si una relación R se descompone en una serie de fragmentos R1, R2, ..., Rn, puede definirse una operador relacional tal que
El operador será diferente dependiendo de las diferentes formas de fragmentación. La reconstrucción de la relación a partir de sus fragmentos asegura la preservación de las restricciones definidas sobre los datos en forma de dependencias.
Disyunción. Si una relación R se descompone horizontalmente en una serie de fragmentos R1, R2,..., Rn, y un elemento de datos di se encuentra en algún fragmento Rj, entonces no se encuentra en otro fragmento Rk (k j). Esta regla asegura que los fragmentos horizontales sean disjuntos. Si una relación R se descompone verticalmente, sus atributos primarios clave normalmente se repiten en todos sus fragmentos.
- Alternativas de asignación
Partiendo del supuesto que el banco de datos se haya fragmentado correctamente, habrá que decidir sobre la manera de asignar los fragmentos a los distintos sitios de la red. Cuando una serie de datos se asignan, éstos pueden replicarse para mantener una copia. Las razones para la réplica giran en torno a la seguridad y a la eficiencia de las consultas de lectura. Si existen muchas reproducciones de un elemento de datos, en caso de fallo en el sistema se podría acceder a esos datos ubicados en sitios distintos. Además, las consultas que acceden a los mismos datos pueden ejecutarse en paralelo, ya que habrá copias en diferentes sitios. Por otra parte, la ejecución de consultas de actualización, de escritura, implicaría la actualización de todas las copias que existan en la red, cuyo proceso puede resultar problemático y complicado. Por tanto, un buen parámetro para afrontar el grado de réplica consistiría en sopesar la cantidad de consultas de lectura que se efectuarán, así como el número de consultas de escritura que se llevarán a cabo.
En una red donde las consultas que se procesen sean mayoritariamente de lectura, se podría alcanzar un alto grado de réplica, no así en el caso contrario. Una base de datos fragmentada es aquella donde no existe réplica alguna. Los fragmentos se alojan en sitios donde únicamente existe una copia de cada uno de ellos a lo largo de toda la red. En caso de réplica, podemos considerar una base de datos totalmente replicada, donde existe una copia de todo el banco de datos en cada sitio, o considerar una base de datos parcialmente replicada donde existan copias de los fragmentos ubicados en diferentes sitios. El número de copias de un fragmento será una de las posibles entradas a los algoritmos de asignación, o una variable de decisión cuyo valor lo determine el algoritmo. La figura 5 compara las tres alternativas de réplica con respecto a distintas funciones de un sistema de base de datos distribuido.
----PUBLICAR CUADRO---
INFORMACIÓN NECESARIA
Un aspecto importante en el diseño de la distribución es la cantidad de factores que contribuyen a un diseño óptimo. La organización lógica de la base de datos, la localización de las aplicaciones, las características de acceso de las aplicaciones a la base de datos y las características del sistema en cada sitio, tienen una decisiva influencia sobre la distribución. La información necesaria para el diseño de la distribución puede dividirse en cuatro categorías: la información del banco de datos, la información de la aplicación, la información sobre la red de ordenadores y la información sobre los ordenadores en sí. Las dos últimas son de carácter cuantitativo y servirán, principalmente, para desarrollar el proceso de asignación. Se entrará en detalle sobre la información empleada cuando se aborden los distintos algoritmos de fragmentación y asignación.
Como se ha explicada anteriormente, la fragmentación horizontal se realiza sobre las tuplas de la relación. Cada fragmento será un subconjunto de las tuplas de la relación. Existen dos variantes de la fragmentación horizontal: la primaria y la derivada. La fragmentación horizontal primaria de una relación se desarrolla empleando los predicados definidos en esa relación. Por el contrario, la fragmentación horizontal derivada consiste en dividir una relación partiendo de los predicados definidos sobre alguna otra.
INFORMACIÓN NECESARIA PARA LA FRAGMENTACIÓN HORIZONTAL:
Información sobre la base de datos. Esta información implica al esquema conceptual global. Es importante señalar cómo las relaciones de la base de datos se conectan con otras. En una conexión de relaciones normalmente se denomina relación propietaria a aquella situada en la cola del enlace, mientras que se llama relación miembro a la ubicada en la cabecera del vínculo. Dicho de otra forma podemos pensar en relaciones de origen cuando nos refiramos a las propietarias y relaciones destino cuando lo hagamos con las miembro. Definiremos dos funciones: propietaria y miembro, las cuales proyectarán un conjunto de enlaces sobre un conjunto de relaciones. Además, dado un enlace, devolverán el miembro y el propietario de la relación, respectivamente. La información cuantitativa necesaria gira en torno a la cardinalidad de cada relación, notada como card(R).
Información sobre la aplicación. Necesitaremos tanto información cualitativa como cuantitativa. La información cualitativa guiará la fragmentación, mientras que la cuantitativa se necesitará en los modelos de asignación. La principal información de carácter cualitativo son los predicados empleados en las consultas de usuario. Si no fuese posible investigar todas las aplicaciones para determinar estos predicados, al menos se deberían investigar las más importantes. Podemos pensar en la regla "80/20" para guiarnos en nuestro análisis, esta regla dice que el 20% de las consultas existentes acceden al 80% de los datos. Llegados a este punto, sería interesante determinar los predicados simples. Dada una relación R(A1, A2, ..., An), donde Ai es un atributo definido sobre el dominio Di, un predicado simple pj definido sobre R es de la forma
donde es un operador relacional y Valor se escoge de entre el dominio de Ai. Usaremos Pri para notar al conjunto de todos los predicados simples definidos sobre una relación Ri. Los miembros de Pri se notan por pij.
Ejemplo 1. Para la relación PROVINC de la base de datos ejemplo, un par de predicados simples serían los siguientes:
CNOMPROV = "Salamanca"
NCODPROV 25
A parte de los predicados simples, las consultas emplean predicados más complejos resultado de combinaciones lógicas de los simples. Una combinación especialmente interesante es la conjunción de predicados simples, al predicado resultante se le denomina predicado mintérmino. Partiendo de que siempre es posible transformar una expresión lógica en su forma normal conjuntiva, usaremos los predicados mintérmino en los algoritmos para no causar ninguna pérdida de generalidad.
Dado un conjunto de predicados simples de una relación R, Pri = {pi1, pi2,..., pim}, el conjunto de predicados mintérmino Mi = {mi1, mi2, ..., miz} se define como
donde p*ik = pik o p*ik = pik. Es decir, cada predicado mintérmino puede ser igual a la forma natural o a la forma negada del predicado simple. Es importante señalar que la referencia a la negación de un predicado es significativa para predicados de igualdad de la forma
Atributo = Valor
Para predicados de desigualdad, la negación debería tratarse como su complemento. Por ejemplo, la negación del predicado simple
Atributo Valor es Atributo > Valor
Pero existen casos en los que el complemento es difícil de definir. Por ejemplo, si dos predicados son de la forma
Límite_inferior Atributo_1 Atributo_1 Límite_superior
sus complementos son
(Límite_inferior Atributo_1) (Atributo_1 Límite_superior)
Sin embargo, si los dos predicados simples se escriben como
Límite_inferior Atributo_1 Límite_superior
con un complemento,
(Límite_inferior Atributo_1 Límite_superior),
éste no es fácil de definir.
Ejemplo 2. Considere la relación ALBCLIT. Los siguientes predicados son algunos de los posibles predicados simples que pueden definirse sobre la relación:
p1 : CCODCLI = "250104"
p2 : CCODCLI = "250102"
p3 : CCODCLI = "250103"
p4 : CCODCLI = "250108"
p5 : CCODCLI = "250107"
p6 : CCODCLI = "250109"
p7 : NNUMALB 980000
p8 : NNUMALB > 980000
Los siguientes son algunos de los predicados mintérmino basados en los predicados simples anteriores:
m1 : CCODCLI = "250104" NNUMALB 980000
m2 : CCODCLI = "250104" NNUMALB > 980000
m3 : (CCODCLI = "250104") NNUMALB 980000
m4 : (CCODCLI = "250104") NNUMALB > 980000
m5 : CCODCLI = "250102" NNUMALB 980000
m6 : CCODCLI = "250102" NNUMALB > 980000
m7 : (CCODCLI = "250102") NNUMALB 980000
m8 : (CCODCLI = "250102") NNUMALB > 980000
Tenga en cuenta que estos ocho predicados mintérmino no son todos los que se pueden definir, es sólo un ejemplo.
Sobre la información cuantitativa necesaria relativa a las aplicaciones, necesitaremos definir dos conjuntos de datos.
Selectividad mintérmino. Es el número de tuplas de una relación a las que accede una consulta de acuerdo a un predicado mintérmino dado. Por ejemplo, en el ejemplo anterior, la selectividad de m6 es 0 ya que no existe ninguna tupla que satisfaga las condiciones; en cambio, la selectividad de m1 es 2. Notaremos la selectividad de un mintérmino mi como sel(mi).
Frecuencia de acceso. Es la frecuencia con la que un usuario accede a los datos. Si Q = {q1, q2, ..., qq} es un conjunto de consultas de usuario, acc(qi) indica la frecuencia de acceso a la consulta qi en un periodo dado.
Observe, que las frecuencias de acceso mintérmino pueden establecerse a partir de las frecuencias de acceso de la consulta. Nos referiremos a las frecuencias de acceso de un mintérmino mi como acc(mi).
- Fragmentación horizontal primaria
Antes de presentar un algoritmo formal que lleve a cabo la fragmentación horizontal, intentaremos explicar de manera intuitiva los procesos de fragmentación horizontal primaria y derivada. La fragmentación horizontal primaria se define como una operación de selección de las relaciones propietarias del esquema de la base de datos. Por tanto, dada una relación Ri, sus fragmentos horizontales son
donde Fj es la fórmula de selección empleada para obtener el fragmento Rji. Observe que si Fj está en forma normal conjuntiva, es un predicado mintérmino (mij). El algoritmo expuesto más adelante, de hecho, necesita que Fj sea un predicado mintérmino.
Ejemplo 3. Podríamos descomponer la relación ALBCLIT del ejemplo en dos fragmentos horizontales ALBCLIT1 y ALBCLIT2 definidos de la manera siguiente:
ALBCLIT1 = NNUMALB 990001 (ALBCLIT)
ALBCLIT2 = NNUMALB > 990001 (ALBCLIT)
El ejemplo anterior ilustra uno de los problemas de la fragmentación horizontal. Si el dominio de los atributos implicados en la fórmula de selección son continuos e infinitos, resulta muy difícil definir un conjunto de fórmulas F = {F1, F2, ..., Fn} que fragmentasen la relación de forma adecuada. Una posible vía de solución consistiría en definir una serie de rangos, como se ha hecho en el ejemplo. Sin embargo, siempre aparecerá el problema de tratar los dos extremos. Es decir, supongamos que se añade una nueva tupla a ALBCLIT con un valor para el atributo NNUMALB de 20000001, entonces deberíamos revisar el punto de fragmentación para decidir si la nueva tupla se incluye en el segundo fragmento ALBCLIT2 o si se ha de realizar una nueva fragmentación modificando el criterio de selección, tal que
ALBCLIT1 = 990001 < albclit2 =" NNUMALB"> 10495001 (ALBCLIT)
En este caso resulta evidente que la mejor opción sería destinar directamente la nueva tupla al segundo fragmentos. Sin embargo, si entrasen 8 nuevas tuplas con un número de albarán (NNUMALB) relativo al año 2.000, es decir, 2000xxxx sería más adecuado elegir otro punto de fragmentación basándonos en la operación de selección.
Este problema, en la práctica, puede resolverse limitando el dominio de los atributos de acuerdo con los requisitos de la aplicación.
Ejemplo 4. Considere la relación PROVINC del ejemplo que venimos empleando. Podríamos definir una serie de fragmentos horizontales basándonos en el código de zona de la siguiente manera.
PROVINC1 = CCODZONA = "CYL" (PROVINC)
PROVINC2 = CCODZONA = "CLM" (PROVINC)
PROVINC3 = CCODZONA = "CAT" (PROVINC)
PROVINC4 = CCODZONA = "MAD" (PROVINC)
Cuyo resultado sería el que se muestra a continuación:
Ahora definiremos la fragmentación horizontal más formalmente. Un fragmento horizontal Ri de una relación R contiene todas las tuplas de R que satisfacen un predicado mintérmino mi. Por tanto, dado un conjunto de predicados mintérmino M, existen tantos fragmentos horizontales de la relación R como predicados mintérmino. Este conjunto de fragmentos horizontales también se conocen como conjuntos de fragmentos mintérmino. En los párrafos siguientes se asumirá que la definición de fragmentos horizontales se basa en los predicados mintérmino. Además, el primer paso para el algoritmo de fragmentación consiste en establecer un conjunto de predicados con ciertas propiedades.
Un aspecto importante de los predicados simples es su compleción, así como su minimalidad. Un conjunto de predicados simples Pr se dice que es completo si y solo si existe una probabilidad idéntica de acceder por cada aplicación a cualquier par de tuplas pertenecientes a cualquier fragmento mintérmino que se define de acuerdo con Pr. Se puede apreciar como la definición de compleción de un conjunto de predicados simples difiere de la regla de compleción de la fragmentación.
Ejemplo 5. Considere la fragmentación llevada a cabo anteriormente sobre la relación PROVINC. Si existiese únicamente una aplicación que accediese a las tuplas de acuerdo al código de zona, el conjunto sería completo ya que existe la misma probabilidad de acceder a cada tupla de los fragmentos. Sin embargo, si existe una segunda aplicación que accede a las tuplas que tienen un código provincial menor o igual que 25, entonces Pr no es completo. Algunas de las tuplas de un PROVINCi tienen mayor probabilidad de acceso por parte de esta segunda aplicación. Para hacer el conjunto de predicados completo, necesitaríamos añadir (NCODPROV 25, NCODPROV > 25) a Pr:
Pr = { CCODZONA = "CLM", CCODZONA = "CYL", CCODZONA = "CAT",
CCODZONA = "MAD",
NCODPROV 25, NCODPROV > 25 }
La segunda propiedad, la minimalidad, es muy intuitiva. Es sencillamente un estado que indica el grado de influencia de un predicado en el desarrollo de la fragmentación (es decir, provoca que un fragmento f se fragmente en fi y fj), siempre que al menos una aplicación acceda a fi y a fj de forma diferente. En otras palabras, el predicado simple debería ser relevante para provocar la fragmentación. Si todos los predicados de un conjunto Pr son relevantes, Pr es mínimo. Una definición formal de la relevancia podría ser la siguiente. Sean mi y mj dos predicados mintérmino idénticos en su definición, exceptuando que mi contiene el predicado simple pi en su forma natural, mientras que mj contiene a pi. Sean, además, fi y fj dos fragmentos definidos de acuerdo a mi y mj, respectivamente. Entonces pi es relevante si y sólo si
Ejemplo 6. Sea el conjunto Pr definido anteriormente. Este conjunto es completo y mínimo. Sin embargo, si le añadimos el predicado CNOMPROV = "Barcelona", el resultado no sería mínimo ya que el nuevo predicado no es relevante para Pr.
A continuación se presenta un algoritmo iterativo, llamado COM_MIN [1], que generará un conjunto de predicados completo y mínimo Pr' a partir de un conjunto de predicados simples Pr. Tenga en cuenta la notación siguiente:
Regla 1. Es la regla fundamental de la compleción y la minimalidad, que afirma que una relación o fragmento se divide "en al menos dos partes a las cuales se accede de forma diferente por al menos una aplicación."fi de Pr'. El fragmento fi se define de acuerdo a un predicado mintérmino especificado sobre los predicados de Pr'.
El algoritmo empieza encontrando un predicado relevante que parta la relación de entrada. El bucle hacer – hasta añade iterativamente predicados al conjunto, asegurando la minimalidad en cada paso. Además, al final, el conjunto Pr' es tanto mínimo como completo.
El segundo paso en el proceso de fragmentación primaria consiste en derivar el conjunto de predicados mintérmino que pueden definirse sobre los predicados del conjunto Pr'. Estos predicados mintérmino establecen los fragmentos candidatos para el proceso de asignación. El establecimiento de los predicados mintérmino es trivial; la dificultad radica en el tamaño del conjunto de predicados mintérmino, que puede ser muy grande (de hecho, exponencial respecto al número de predicados simples). En el paso siguiente se presentarán formas de reducir el número de predicados mintérmino necesarios para la fragmentación.
El tercer paso aborda, como ya se ha citado, la eliminación de algunos fragmentos mintérmino que puedan ser redundantes. Esta eliminación se desarrolla identificando aquellos mintérminos que puedan resultar contradictorios sobre un conjunto de implicaciones I. Por ejemplo, si Pr' = {p1, p2}, donde
p1 : atr = valor_1
p2 : atr = valor_2
y el dominio de atr es {valor_1, valor_2}, es obvio que I contiene las dos implicaciones siguientes
i1 : (atr = valor_1) (atr = valor_2)
i2 : (atr = valor_1) (atr = valor_2)
Los siguientes cuatro predicados mintérmino se definen de acuerdo a Pr':
m1 : (atr = valor_1) (atr = valor_2)
m2 : (atr = valor_1) (atr = valor_2)
m3 : (atr = valor_1) (atr = valor_2)
m4 : (atr = valor_1) (atr = valor_2)
En este caso los predicado mintérmino m1 y m4 resultan contradictorios respecto a las implicaciones I y pueden eliminarse de M.
El algoritmo de fragmentación horizontal primaria se presenta a continuación. La entrada al algoritmo HORIZONTALP[1] es una relación Ri sujeta a la fragmentación, y Pri, es decir, el conjunto de predicados simples que se establecieron de acuerdo a las aplicaciones definidas sobre la relación R.
No hay comentarios:
Publicar un comentario