sábado, 17 de septiembre de 2011

Ejemplos de diagrama de esquema jerárquico


La función de manipulación de datos en los modelos jerárquicos

La manipulación de datos jerárquicos necesita localizar(seleccionar) primero los datos sobre los que va a trabajar para realizar a continuación la acción de recuperación o actualización sobre dichos datos.
A) Localización o selección.
La función de selección jerárquica es de tipo navegacional, es decir, trabaja registro a registro. Dada la sencillez del modelo, la función de selección es también muy sencilla, existiendo únicamente las siguientes formas básicas de búsqueda:
- Seleccionar un determinado registro que cumpla una cierta condición. en el lenguajeDL/I se realizará este tipo de selección mediante una sentencia (GET UNIQUE -GU-) que activará el primer registro que cumpla la condición especificada en el predicado que acompaña a la sentencia.
- Seleccionar el siguiente registro, que se encuentra perfectamente definido al existir un único camino jerárquico. También en este caso se puede especificar una condición que habrá de cumplir el registro para ser seleccionado. En DL/I se utiliza una sentencia (GET NEXT -GN-) que selecciona y, al mismo tiempo recupera el siguiente registro en el pre orden.
- Seleccionar el siguiente registro dentro de un padre. Esta sentencia (GET NEXT PARENT -GNP-) es análoga a la anterior, pero la selección termina cuando no haya más descendientes de ese padre.
- Seleccionar el registro padre de otro dado (que ha sido activado previamente) se conoce como normalización jerárquica ascendente, mientras que la selección de descendientes se llama normalización jerárquica descendente.
B) Acción
Una vez seleccionado un registro, se tendrá que realizar sobre él una acción, sea de recuperación o de actualización.
La recuperación, que va asociada a la selección en el DL/I, consiste en llevar el registro marcado como activo en la selección realizada previamente al área de entrada/salida. Se utiliza la sentencia GET.
En cuanto a la actualización, es preciso distinguir entre:
Insertar un conjunto de datos (INSERT -ISRT-)
Borrar un conjunto de datos (DELETE -DLET-)
Reemplazar -modificar- uno o varios campos de un registro (REPLACE -REPL-)
Debido a la naturaleza jerárquica de las conexiones entre registros, las inserciones y borrados de registros requieren consideraciones especiales:
- Cuando un nuevo registro se inserta en una base de datos jerárquica, excepto para la raíz, tiene que ser conectado a un nodo padre previamente seleccionado mediante alguna sentencia de selección. El nuevo registro se inserta como hijo del registro padre seleccionado.
- Cuando un registro se borra en una base de datos jerárquica, excepto si se trata de una hoja, se han de borrar todos los registros descendientes de él.

El lenguaje de manipulación jerárquico

Una instrucción de un lenguaje de manipulación constará:
- Un operador que indica el tipo de operación a realizar.
- Los datos sobre los que se lleva a cabo la operación.
- Una condición, que servirá para seleccionar el conjunto de datos sobre el que se desea trabajar, y que es una expresión de tipo lógico, es decir, constantes y variables unidas por operadores de comparación y del álgebra de Boole.


Ejemplos:

Las representaciones según las cardinalidades son:
Consideremos la relación alumno-materia sin atributo descriptivo.


La transformación según las cardinalidades seria:
  • Cuando la relación es uno a uno.


  • Cuando la relación es uno a muchos.


  • Cuando la relación es muchos a uno.

  • Cuando la relación es muchos a muchos.

Cuando la relación tiene atributos descriptivos, la transformación de un diagrama E-R a estructura de árbol se lleva a cabo cubriendo los siguientes pasos:
  1. Crear un nuevo tipo de registro.
  2. Crear los enlaces correspondientes.
Consideremos que a la relación Alumno-Materia añadimos el atributo Cal a la relación que existe entre ambas, entonces nuestro modelo E-R resulta: Añadir el diagrama E-R.

Según las cardinalidades los diagramas de estructura de árbol pueden quedar de la siguiente manera:
  • Cuando la relación es uno a uno.

  • Cuando la relación es uno a muchos.

  • Cuando la relación es Muchos a uno.

  • Cuando la relación es Muchos a Muchos.
A continuación se describe la forma de transformar un diagrama E-R a estructura de árbol con relaciones muchos a muchos. Suponemos el ejemplo de la relación alumno-materia.
  1. Crear dos diagramas de estructura de árbol distintos T1 yT2, cada uno de los cuales incluye los tipos de registro alumno y materia, en el árbol T1 la raíz es alumno y en T2 la raíz es materia.
  2. Crear los siguientes enlaces:
  • Un enlace muchos a uno del registro cuenta al registro Alumno, en T1
  • Un enlace muchos a uno del tipo de registro cliente al tipo de registro materia en T2.
Como se muestra en el siguiente diagrama:



Bibliografía:



Para mayor información:
http://sistemas.itlp.edu.mx/tutoriales/basedat1Info/hseis6_3.htm

viernes, 16 de septiembre de 2011

Transformación Entidad Relación a modelo 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.


Se podría evitar la pérdida de simetrías introduciendo mucha mayor redundancia, como se muestra en la Figura 13, donde se presenta la transformación de un esquema E/R con dos entidades y una interrelación N:M es un esquema jerárquico en el que existen dos árboles, de modo que se conservan las simetrías naturales, ya que losalgoritmos para dos preguntas simétricas, como son recuperar los alumnos de un profesor y recuperar los 10 profesores de un alumno, serían también simétricos.


Soluciones de este tipo no son en absoluto eficientes.
A partir del modelo E/R, vamos a analizar la forma de transformar algún 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.




Bibliografía:







Restricciones de integridad en el modelo jerárquico

Siempre que especificamos un esquema jerárquico, habrá varias restricciones inherentes al modelo jerárquico. Entre ellas se cuentan:

  •  Ninguna ocurrencia de registro, con excepción de los registros raíz, puede existir si no esta relacionada con una ocurrencia de registro padre. Esto tiene las siguientes implicaciones
  • Ningún registro hijo puede insertarse si no esta enlazado a un registro padre
  • Un registro hijo se puede eliminar independientemente de su padre; pero la eliminación de un padre causa automáticamente la eliminación de todos sus registros hijos y descendientes
  • Las reglas anteriores no se aplican a los registros hijo y padre virtuales. Las regla en este caso es que un apuntador en un registro hijo virtual debe apuntar a una ocurrencia real de un registro padre virtual.
  • No debe permitirse la eliminación de un registro en tanto existan apuntadores a el en registros hijo virtuales, lo que lo convierte en un registro virtuales, lo que lo convierte en un registro padre virtual.
  • Si un registro hijo tiene dos o mas registros padre del mismo tipo de registros, el registro hijo debe duplicarse una vez bajo cada registro padre.
  • Un registro hijo que tengo dos o mas registros padre de diferentes tipos de registros solo puede tener un padre real; todos los demás deben representarse como padres virtuales
A continuación se mencionan los problemas típicos de las bases de datos jerárquicas y que no existen en las bases de datos relacionales. Todos estos problemas 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


Bibliografía:
















Vínculos virtuales padre - hijo


Los datos se almacenan en la forma de registros, el equivalente a las filas del modelo relacional. Cada registro consta de un conjunto de campos, el equivalente a las columnas del modelo relacional. Un conjunto de registros con los mismos campos se denomina fichero (record type, en inglés), el equivalente a las tablas del modelo relacional.
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.
Vínculos virtuales padre - hijo

El modelo jerárquico tiene problemas cuando se modelan ciertos tipos de vínculos. Entre ellos están los siguientes vínculos y situaciones:

·         Vínculos M:N
·         El caso en que un tipo de registro participa como hijo en mas de un tipo de VPH
·         Vínculos n-arios con mas de dos de registros participantes.



Bibliografía:









jueves, 15 de septiembre de 2011

Estructura de una base de datos de modelo jerárquico

Una base de datos jerárquica es un tipo de sistema de gestión de bases de datos que, como su nombre indica, almacenan la información en una estructura jerárquica que enlaza los registros en forma de estructura de árbol (similar a un árbol visto al revés), en donde un nodo padre de información puede tener varios nodos hijo.
Esta relación jerárquica no es estrictamente obligatoria, de manera que pueden establecerse relaciones entre nodos hermanos. En este caso la estructura en forma de árbol se convierte en una estructura en forma de grafo dirigido. Esta variante se denomina Bases de datos de red.

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.   5
- 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: 
A) Cada árbol debe tener un único segmento raíz. 
B) No puede definirse más de una relación entre dos segmentos dentro de un árbol. 
C) No se permiten las relaciones reflexivas de un segmento consigo mismo. 
D) No se permiten las relaciones N:M. 
E) No se permite que exista un hijo con más de un padre. 
F) 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. 
G) El árbol debe recorrer siempre de acuerdo a un orden prefijado: el camino jerárquico. 
H) 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, donde se muestra la interrelación entre DEPARTAMENTO y EMPLEADO.




-  Arborescente propiamente dicha: un tipo de registro padre puede tener varios tipos de registro descendientes.









Ejemplos de diagrama de esquema de red

A continuación, se presentara 3 ejemplos de diagrama de esquema de red, se presentara el modelo de relación y su respectivo diagrama de red.

Ejemplo 1:



Ejemplo 2:




Ejemplo 3:



Programación de una base de datos de red

La programación de una base de datos se puede dar en diferentes lenguajes como C++, Javascritp, entre otros como en diversos SGBD, a continuación algunos ejemplos.

Ejemplo 1: 


Vamos a suponer que tenemos una BD de red con datos de alumnos y asignaturas.


Entre ALUMNOS y ASIGNATURA existe la relación de  ALUMNO-CURSA-ASIGNATURA, que en el modelo E-R se representa como muestra la figura.


Ejemplo 2:

Considérese una base de datos que represente una relación cliente-cuenta en un sistema bancario. Hay dos tipos de registros, cliente cuenta. Como se ha visto anteriormente, se puede definir el tipo de registro cliente utilizando una notación parecida a la del Pascal, de la manera siguiente:



El tipo de registro cuenta puede definirse de la manera siguiente:



La base de datos de ejemplo de la figura muestra que López tiene la cuenta C-102, Gonzáles tiene las cuentas C-101 y C-201 y Abril tiene la cuenta C-305.


Ejemplo 3:

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):




Bibliografía:







Transformación Entidad Relación a Red para el diseño de bases de datos de red


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.

La forma de diagramado consta de dos componentes básicos:
  •      Celdas: representan a los campos del registro.
  •      Líneas: representan a los enlaces entre los registros. 
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.



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.

 

Caso 2. Cardinalidad Muchos a uno.


Caso 3. Cardinalidad Muchos a muchos.




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:





La forma de convertir a diagramas de estructura de datos consiste en realizar lo siguiente:
    1. Realizar la representación de los campos del registro agrupándolos
        en sus celdas correspondientes.
    2. Crear nuevo registro, denominado Calif, para este caso, con un
        solo campo, el de cal (calif).
    3. Crear los enlaces indicando la cardinalidad de :
        **AluCal, del registro Calif al registro Alumno.        ** MatCal, del registro Calif al registro Materia.

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


Caso 1. Cardinalidad uno a uno.

Caso 2. Cardinalidad Uno a muchos.


Caso 3. Cardinalidad Muchos a muchos.




Bibliografía:


Restricciones en el modelo de base de datos de red


RESTRICCIONES INHERENTES DEL MODELO CODASYL


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 a 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.



Bibliografía: