viernes, 16 de septiembre de 2011

Modelo de Datos Jerárquico: Transformación E/R - Jerárquico


Ya se han señalado los inconvenientes que presenta el modelado del mundo real según esquemas jerárquicos, y también hemos indicado una técnica de diseño jerárquico que consiste en introducir redundancias.


A partir del modelo E/R, vamos a analizar la forma de transformar algunos tipo, de interrelaciones al modelo jerárquico. 

A) Interrelaciones 1:N con cardinalidad mínima 1 en la entidad padre. 

En este caso no existe ningún problema y el esquema jerárquico resultante será prácticamente el mismo que en el ME/R.


B) Interrelaciones 1:N con cardinalidad mínima 0 en el registro propietario. 

El problema es que podrían existir hijos sin padre, por lo que o se crea un padre ficticio para estos casos o se crean dos estructuras arborescentes. 


La primera estructura arborescente tendrá como nodo padre el tipo de registro A y como nodo hijo los identificadores del tipo de registro B. De esta forma no se introducen redundancias, estando los atributos de la entidad B en la segunda arborescencia, en la cual sólo existiría un nodo raíz B sin descendientes. 

C) Interrelaciones N:M 

La solución es muy parecida, creándose también dos arborescencias. 


La solución es independiente de las cardinalidades mínimas. Se podría suprimir, en la primera arborescencia 
o en la segunda, el registro hijo, pero no se conservaría la simetría. 


D) Interrelaciones reflexivas 

La jerarquía a) se utilizaría siempre que se desee obtener la explosión. 

La aplicación de estas normas de diseño evita la introducción de redundancias, así como la pérdida de simetría, pero complica enormemente el esquema jerárquico resultante que estará constituido por más de un árbol, lo que no resulta fácilmente comprensible a los usuarios.








Modelo de Datos Jerárquico: Restricciones de Integridad


Estas restricciones derivan del hecho de que el sistema gestor de base de datos no implementa ningún control sobre los propios datos, sino que queda en manos de las aplicaciones garantizar que se cumplen las condiciones invariantes que se requieran (por ejemplo, evitar la duplicidad de registros). Dado que todas las aplicaciones están sujetas a errores y fallos, esto es imposible en la práctica. Además dichas condiciones suelen romperse ex profeso por motivos operativos (generalmente, ajustes debidos a cambios en el negocio) sin evaluarse sus consecuencias.

Duplicidad de registros

No se garantiza la inexistencia de registros duplicados. Esto también es cierto para los campos "clave". Es decir, no se garantiza que dos registros cualesquiera tengan diferentes valores en un subconjunto concreto de campos.

Integridad referencial

No existe garantía de que un registro hijo esté relacionado con un registro padre válido. Por ejemplo, es posible borrar un nodo padre sin eliminar antes los nodos hijo, de manera que éstos últimos están relacionados con un registro inválido o inexistente..

Desnormalización

Este no es tanto un problema del modelo jerárquico como del uso que se hace de él. Sin embargo, a diferencia del modelo relacional, las bases de datos jerárquicas no tienen controles que impidan la desnormalización de una base de datos. Por ejemplo, no existe el concepto de campos clave o campos únicos.
La desnormalización permite ingresar redundancia de una forma controlada, seguir a una serie de pasos conlleva a:
  • Combinar las relaciones
  • Duplicar los atributos no claves
  • Introducción de grupos repetitivos
  • Crear tablas de extracción
Cuando se debe desnormalizar:
  • Se debe desnormalizar para optimizar el esquema relacional
  • Para hacer referencia a la combinación de 2 relaciones que forman una sola relación

Fuente: http://es.wikipedia.org/wiki/Base_de_datos_jer%C3%A1rquica

Modelo de Datos Jerárquico: Vínculos Virtuales Padre - Hijo


El modelo jerárquico facilita relaciones padre-hijo, es decir, relaciones 1:N (de uno a varios) del modelo relacional. Pero a diferencia de éste último, las relaciones son unidireccionales. En justicia, dichas relaciones son hijo-padre, pero no padre-hijo. Por ejemplo, el registro de un empleado (nodo hijo) puede relacionarse con el registro de su departamento (nodo padre), pero no al contrario. Esto implica que solamente se puede consultar la base de datos desde los nodos hoja hacia el nodo raíz. La consulta en el sentido contrario requiere una búsqueda secuencial por todos los registros de la base de datos (por ejemplo, para consultar todos los empleados de un departamento). En las bases de datos jerárquicas no existen índices que faciliten esta tarea.




Obsérvese que, a priori, no existen relaciones N:M (de muchos a muchos) en el modelo jerárquico. Salvo que se simulen mediante varias relaciones 1:N. No obstante, esto puede provocar problemas de inconsistencia, ya que el gestor de base de datos no controla estas relaciones.
Como ya se ha mencionado, las relaciones se establecen mediante punteros entre registros. Es decir, un registro hijo contiene la dirección física en el medio de almacenamiento de su registro padre. Esto tiene una ventaja fundamental sobre las bases de datos relacionales: el rendimiento. El acceso de un registro a otro es prácticamente inmediato sin necesidad de consultar tablas de correspondencia.
Las relaciones jerárquicas entre diferentes tipos de datos pueden hacer que sea muy sencillo responder a determinadas preguntas, pero muy difícil el contestar a otras.

Fuente: http://es.wikipedia.org/wiki/Base_de_datos_jer%C3%A1rquica

Modelo de Datos Jerárquico: Estructura


Los segmentos, en función de su situación en el árbol y de sus características, pueden denominarse como: 

1) SEGMENTO PADRE: Es aquél que tiene descendientes, todos ellos localizados en el mismo nivel.



2) SEGMENTO HIJO: Es aquél que depende de un segmento de nivel superior. Todos los hijos de un 
mismo padre están en el mismo nivel del árbol. 



3) SEGMENTO RAÍZ: El segmento raíz de una base de datos jerárquica es Αel padre que no tiene padre. 
La raíz siempre es única y ocupa el nivel superior del árbol. 



Una Ocurrencia de un segmento de una base de datos jerárquica es el conjunto de valores particulares que toman todos los campos que lo componen en un momento determinado. 

Un Registro de la base de datos es el conjunto formado por una ocurrencia del segmento raíz y todas las ocurrencias del resto de los segmentos de la base de datos que dependen jerárquicamente de dicha ocurrencia raíz. 

La relación Padre/Hijo en la que se apoyan las bases de datos jerárquicas, determina que el camino de acceso a los datos sea único; este camino, denominado Camino Secuencia Jerárquica, comienza siempre en una ocurrencia del segmento raíz y recorre la base de datos de arriba a abajo, de izquierda a derecha y por último de adelante a atrás. 

El esquema es una estructura arborescente compuesta de nodos, que representan las entidades, enlazados por arcos, que representan las asociaciones o interrelaciones entre dichas entidades. 

La estructura del modelo de datos jerárquico es un caso particular de la del modelo en red, con fuertes restricciones adicionales derivadas de que las asociaciones del modelo jerárquico deben formar un árbol ordenado, es decir, un árbol en el que el orden de los nodos es importante. 

Una estructura jerárquica, tiene las siguientes características: 

  • El árbol se organiza en un conjunto de niveles. 
  • El nodo raíz, el más alto de la jerarquía, se corresponde con el nivel 0. 
  • Los arcos representan las asociaciones jerárquicas entre dos entidades y no tienen nombre, ya que no es necesario porque entre dos conjuntos de datos sólo puede haber una interrelación.
  • Mientras que un nodo de nivel superior (padre) puede tener un número ilimitado de nodos de nivel inferior (hijos), al nodo de nivel inferior sólo le puede corresponder un único nodo de nivel superior. en otras palabras, un progenitor o padre puede tener varios descendientes o hijos, pero un hijo sólo tiene un padre. 
  • Todo nodo, a excepción del nodo raíz, ha de tener obligatoriamente un padre. 
  • Se llaman hojas los nodos que no tienen descendientes. 
  • Se llama altura al número de niveles de la estructura jerárquica. 
  • Se denomina momento al número de nodos. 
  • El número de hojas del árbol se llama peso. 
  • Sólo están permitidas las interrelaciones 1:1 ó 1:N 
  • Cada nodo no terminal y sus descendientes forman un subárbol, de forma que un árbol es una estructura recursiva. 
  • El árbol se suele recorrer en preorden; es decir, raíz, subárbol izquierdo y subárbol derecho. 


Entre las restricciones propias de este modelo se pueden resaltar:

  • Cada árbol debe tener un único segmento raíz. 
  • No puede definirse más de una relación entre dos segmentos dentro de un árbol. 
  • No se permiten las relaciones reflexivas de un segmento consigo mismo. 
  • No se permiten las relaciones N:M. 
  • No se permite que exista un hijo con más de un padre. 
  • Para cualquier acceso a la información almacenada, es obligatorio el acceso por la raíz del árbol, excepto en el caso de utilizar un índice secundario. 
  • El árbol debe recorrer siempre de acuerdo a un orden prefijado: el camino jerárquico. 
  • La estructura del árbol, una vez creada, no se puede modificar. 


Las estructuras jerárquicas se clasifican también como: 

Lineales: Es un caso particular y simple en el que cada tipo de registro padre sólo puede tener un tipo de registro hijo.

Arborescente: Un tipo de registro padre puede tener varios tipos de registro descendiente.


Modelo de Datos Jerárquico: Conceptos Básicos

La implementación del modelo Jerárquico en los productos se lleva a cabo en base a punteros; estructura física que varía según los productos, e incluso un mismo producto proporciona distintas organizaciones físicas a fin de que el usuario pueda conseguir una mayor eficiencia en el diseño físico de la base de datos.

El producto comercial de tipo Jerárquico más extendido es el IMS de IBM con su lenguaje de datos DL/I^2. El System 2000 también fue bien aceptado y fue adquirido por el Instituto SAS.

Es un modelo muy rígido en el que las diferentes entidades de las que está compuesta una determinada situación, se organizan en niveles múltiples de acuerdo a una estricta relación Padre/Hijo, de manera que un padre puede tener más de un hijo, todos ellos localizados en el mismo nivel, y un hijo únicamente puede tener un padre situado en el nivel inmediatamente superior al suyo.


Esta estricta relación Padre/Hijo implica que no puedan establecerse relaciones entre segmentos dentro de un mismo nivel.


La representación gráfica de un modelo jerárquico se realiza mediante la estructura de Árbol Invertido, en la que el nivel superior está ocupado por una única entidad, bajo la cual se distribuyen el resto de las entidades en niveles que se van ramificando. Los diferentes niveles quedan unidos por medio de las relaciones.


Las entidades se denominan en el caso particular del modelo jerárquico Segmentos, mientras que lo atributos reciben el nombre de Campos.


Los segmentos, se organizan en niveles de manera que en un mismo nivel estén todos aquellos segmentos que depende de un segmento de nivel inmediatamente superior.


Fuente:http://alarcos.inf-cr.uclm.es/doc/bda/doc/trab/T0001_MAMoraga.pdf

jueves, 15 de septiembre de 2011

Modelo de Base de Datos de Red: Ejemplos

Diagramas de estructura de datos.

   Un diagrama de estructura de datos es un esquema que representa el diseño de una base de datos de red. Este modelo se basa en representaciones entre registros por medio de ligas, existen relaciones en las que participan solo dos entidades(binarias ) y relaciones en las que participan más de dos entidades (generales) ya sea con o sin atributo descriptivo en la relación.

    Un diagrama de estructura de datos de red, especifica la estructura lógica global de la base de datos; su representación gráfica se basa en el acomodo de los campos de un  registro en un conjunto de celdas que se ligan con otro(s) registro(s), ejemplificaremos esto de la siguiente manera:
Consideremos  la relación alumno-cursa-materia donde la relación cursa no tiene atributos descriptivos :

Bases de datos

Las estructuras de datos según la cardinalidad se representan en los siguientes casos:

Cuando el enlace no tiene atributos descriptivos

Caso 1. Cardinalidad Uno a Uno.

Bases de datos

Caso 2. Cardinalidad Muchos a uno.

Bases de datos

Caso 3. Cardinalidad Muchos a muchos.

Bases de datos

Cuando el enlace tiene atributos descriptivos.

   Consideremos que a la relación cursa le agregamos el atributo Cal (calificación), nuestro modelo E-R quedaría de la siguiente manera:

Bases de datos

Los diagramas de estructuras de datos según la cardinalidad se transforman en:

Caso 1. Cardinalidad uno a uno.

Bases de datos

Caso 2. Cardinalidad Uno a muchos.

Bases de datos

Caso 3. Cardinalidad Muchos a muchos.

Bases de datos

Fuente: http://html.rincondelvago.com/bases-de-datos_4.html

Modelo de Base de Datos de Red: Programación


Para ilustrar la estructura de los registros en una base de datos de red, mostraremos la base de datos alumno – materia, con los siguientes registros (en el Lenguaje de programación Pascal):
type materia = record
     clave: string[7]
     nombreM: string[25]
     cred: string[2];
     end;
type alumno = record
     nombre: string[30];
     control: string[8];
     materia: Materia; {Enlace a materia}
     end;

En síntesis una base de datos en red puede tener 1 o mas elementos padre.

Fuente: http://es.wikipedia.org/wiki/Base_de_datos_de_red

lunes, 12 de septiembre de 2011

Modelo de Base de Datos de Red: Uso de la Transformación Entidad-Relación (ER)

Los diagramas de estructura de datos son esquemas que representan el diseño de las bases de datos en red. Estos diagramas constan de dos componentes fundamentales: las cajas, que corresponden a tipos de registros, y las líneas, que corresponden a punteros. Los diagramas de estructuras de datos cumplen la misma finalidad que los diagramas E-R, es decir, especifican la estructura lógica global de la base de datos. Los diagramas E-R pueden transformarse en los diagramas de la estructura de datos correspondientes.     


 
Figura 7.2.

A modo de ejemplo, considérese el diagrama E-R de la Figura 7.2a, que consta de dos conjuntos de entidades, cliente y cuenta, relacionados mediante una relación binaria de varios a varios impositor, sin atributos descriptivos. El diagrama especifica que un cliente puede tener varias cuentas y que una cuenta puede pertenecer a varios clientes diferentes. El diagrama de la estructura de datos correspondiente se ilustra en la Figura 7.2b. El tipo de registro cliente corresponde al conjunto de entidades cliente. Incluye tres campos —nombre-cliente, calle-cliente y ciudad-cliente—, tal y como se ha definido anteriormente. De manera parecida, cuenta es el tipo de registro correspondiente al conjunto de entidades cuenta. Incluye los dos campos número-cuenta y saldo. Finalmente, la relación impositor ha sido sustituida por el puntero impositor. Si la relación impositor fuera de uno a varios de cliente cuenta, el puntero impositor tendria una flecha que apuntaría al tipo de registro cliente. De manera parecida, si la relación impositorfuera de uno a uno, el puntero impositor tendría dos flechas, una que apuntaría al tipo de registro cuenta y otra que apuntaría al tipo de registro cliente.

Considérese el diagrama E-R de la Figura 7.3a, que consta de tres conjuntos de entidades —cuenta, cliente y sucursal— relacionadas mediante la relación general CCS sin atributos descriptivos. El diagrama específica que un cliente puede tener varias cuentas, cada una de ellas abierta en una sucursal bancaria específica, y que una cuenta puede pertenecer a varios clientes diferentes.

Dado que los punteros pueden conectarse exactamente con dos tipos de registros diferentes, hay que conectar estos tres tipos de registros mediante un nuevo tipo de registro que se vincule directamente con cada uno de ellos.

Para transformar el diagrama E-R de la Figura 7.3a en un diagrama la estructura de datos de red hay que crear un nuevo tipo de registro Renlace que pueda no tener ningún campo o tener un solo campo que contenga un identificador único. Este identificador lo proporciona el tema y no lo utiliza directamente el programa de aplicación. Este nuevo tipo de registro se denomina a veces tipo de registro ficticio (o enlaceconexión). También hay que crear tres punteros de varios a uno, ClienRenl, CuenRenl y SucRenl, tal y como se muestra en la Figura 7.3b. Si la relación CCS tuviera atributos descriptivos, se transformarían en campos del tipo de registro Renlace.   



Modelo de Base de Datos de Red: Restricciones


Cuando hablábamos del modelo en red general, decíamos que era un modelo muy flexible a coste de no tener restricciones inherentes. Esta ausencia de restricciones hace que sea muy difícil de implementar, y a la larga suele reportar escaso rendimiento, por lo que como también decíamos no pasa de ser un modelo teórico.
El modelo Codasyl está basado en el modelo en red general, pero a diferencia de este, es un modelo utilizado. Esto es debido a que Codasyl ha incluido restricciones inherentes que hacen que sea posible su implementación y que se obtenga un alto rendimiento del sistema.
Las restricciones son las siguientes:
  • Solo se admiten tipos de interrelaciones jerárquicas de dos niveles (propietario y miembro). Si se admite la combinación de varios SET para generar jerarquías multinivel.
  • En el nivel propietario solo se permite un tipo de registro.
  • En el mismo SET no se permite que a un registro ser a la vez propietario y miembro, no está admitida la reflexividad. Aunque esta restricción se eliminó con el tiempo, los productos basados en Codasyl la siguen utilizando.
  • Una misma ocurrencia de miembro no puede pertenecer en un mismo tipo de SET a más de un propietario. Esto hace que se simplifique la implementación física de los SET, ya que sus ocurrencias se pueden organizar como una cadena.




Modelo de Base de Datos de Red: Su estructura

El modelo de datos en red general representa las entidades en en forma de nodos de un grafo,  y las interrelaciones entre estas mediante arcos que unen dichos nodos. En principio esta representación no impone restricción alguna acerca del tipo y el número de arcos que puede haber, con lo que se pueden modelar estructuras de datos tan complejas como sea necesario.




CODASYL (Conference on Data Systems Languages): Es un modelo de datos de tipo red que introduce restricciones inherentes. este modelo constituye una simplificación del modelo en red general, en la que se admiten solo determinados tipos de interrelaciones y se incluyen algunas restricciones adicionales, que, sin embargo, no limitan excesivamente la flexibilidad que proporciona el modelo en red, pero si que facilita una instrumentación eficiente.

Los elementos básicos de la estructura de datos propia del modelo CODASYL son:
  • Elemento de datos (Data item): Es la unidad de datos más pequeña a la que se puede hacer referencia en el modelo CODASYL. Un elemento de datos ha de tener un nombre, y una ocurrencia del mismo contiene un valor que puede ser de distintos tipos (booleano, numérico, tira de caracteres,...) además, un elemento de datos puede definirse como dependiente de los valores de otros elementos (datos derivados).
  • Agregado de datos (data aggregate): Puede ser un vector, con un numero fijo de elementos, o un grupo repetitivo. El elemento y le agregado de datos se corresponden con los campos de los ficheros clásicos o con los atributos de otros modelos, aunque a diferencia de algunos modelos, como el relacional, aquí si que se admiten estructuras no planas como son los agregados.
  • Registro (record): Colección nominada de elementos de datos. Es la unidad básica de acceso y manipulación de la base de datos y se corresponde con el concepto de registro (en los ficheros) y de entidad (en otros modelos como el E/R).
  • Conjunto (SET o COSET): Es una colección nominada de dos o mas tipos de registros que establece una vinculación entre ellos. Constituye el elemento clave y distintivo de este modelo de datos, siendo el origen de muchas de sus restricciones, tanto inherentes como opcionales. Las interrelaciones 1:N de otros modelos se representan en CODASYL como SET.
  • Área (area o realm): Es una subdivisión nominada del espacio de almacenamiento direccionable de la base de datos que contiene ocurrencias de registros. En un área puede haber ocurrencias de mas de un tipo de registro y las ocurrencias de un mismo tipo de registro pueden estar contenidas en distintas áreas, aunque una ocurrencia determinada se almacena solo en una área. En 1981 paso a formar parte del esquema de almacenamiento.
  • Clave de base de datos (Database Key): Es un identificador interno único para cada ocurrencia del registro, que proporciona su dirección en la base de datos. en principio, esta clave era permanente y se podía utilizar par acceder rápidamente a un registro de forma directa o para indicar donde almacenarlo, pero suponía un grave obstáculo para conseguir la independencia lógica / física por lo que las últimas versiones del modelo restringen mucho su uso, aunque se conservó. 




    Bibliografía: 


    http://alarcos.inf-cr.uclm.es/doc/bda/doc/trab/T0001_IGarcia.pdf
    http://html.rincondelvago.com/bases-de-datos-en-red.html
    http://es.wikipedia.org/wiki/CODASYL

Bienvenida

Hola!


En este blog vamos a tocar dos temas indispensables para continuar con el aprendizaje de elaboración de una Base de Datos: El modelo de base de datos de red y el modelo de datos jerárquico.


Ojalá les sea de gran ayuda.


Cesar.

Presentación

Alumno: Cesar Augusto Berríos Mesía
Ciclo: 2011-2
Curso: Base de Datos
Profesor: Luis Enrique Serna Jherry