EL MODELO DE DATOS JERÁRQUICO

ESTRUCTURA

Un árbol o jerarquía como a veces se la llama es una estructura de datos en la cual sus elementos sólo tienen relaciones de muchos a muchos. Cada uno de los elementos tiene cuando mucho un padre. La imagen posterior es un ejemplo de un árbol. De acuerdo a esta terminología estándar, cada elemento se llama NODO, y las relaciones entre los elementos, ramas. El nodo en la parte superior del árbol se llama raíz.

Cada nodo de un árbol, excepto la raíz, tiene un padre, el nodo inmediato superior. Como ya se mencionó, los árboles se distinguen de otras estructuras de datos en que cada nodo tiene cuando mucho un padre. Decimos que máximo un padre porque el nodo raíz no tiene padre .Los descendientes de un nodo se llaman hijos. En general, no hay un límite en el número de hijos que puede tener un nodo. Los nodos que tienen el mismo padre se llaman gemelos, o hermanos.    

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.

Este tipo de diagrama está formado por dos componentes básicos:

• Rectángulos: que representan a los de registros.
• Líneas: que representan a los enlaces o ligas entre los registros.

Esta base de datos tiene como objetivo establecer una jerarquía de fichas, de manera que cada ficha puede contener a sus vez listas de otras fichas, y así sucesivamente. P.ej., una ficha de clientes puede contener una lista de fichas de facturas, cada una de las cuales puede contener a su vez una lista de fichas de líneas de detalle que describen los servicios facturados.

Una base de datos jerárquica está compuesta por una secuencia de bases de datos físicas, de

manera que cada base de datos física se compone de todas las ocurrencias de un tipo de registro o ficha determinada. Una ocurrencia de registro es una jerarquía de ocurrencias de segmento. Cada ocurrencia de segmento está formada por un conjunto de ocurrencias o instancias de los campos que componen el segmento

El tipo define la estructura general que debe poseer, o sea, los campos de cada uno de sus segmentos, y la estructura jerárquica entre ellos. Una instancia es un valor de un tipo de registro. Para que quede más claro, un tipo de registro es como un tipo de persona: blanco, negro, amarillo, aceitunado, etc., mientras que una instancia es una persona concreta perteneciente a uno de estos tipos: Pablo Picasso, Nelson Mandela, Mao Tse Tung, Toro Sentado, etc. De esta forma, al segmento que se halla a la cabeza de un registro, se le llama segmento padre, y se llama segmentos hijo a los que dependen de él. Para movernos por un registro de estructura jerárquica lo que se hace es posicionarse inicialmente en la raíz de una instancia, e ir navegando por sus hijos según nos convenga consultando o modificando los datos pertinentes.

Una base de datos de este tipo, no permite el acceso directo a las instancias de un segmento

hijo, si no es seleccionando previamente las instancias de los padres de los que depende.

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.

Limitaciones del modelo jerárquico

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

Ejemplo:
Proveedor (Nro_proveedor, calle, ciudad, cod_postal, descripción) La relación Proveedor esta desnormalizada, ya que para normalizarla deberíamos crear una tabla con ciudad y código postal.

la transformación ER- jerárquico para el diseño de bases de datos jerárquicas

Se podría evitar la pérdida de simetrías introduciendo mucha mayor redundancia, como se muestra en la Figura superior, 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 los algoritmos para dos preguntas simétricas, como son recuperar los alumnos de un profesor y recuperar los  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 algunos tipos, 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.

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.

 EJEMPLO DE LENGUAJE PARA EL MODELO JERÁRQUICO.

1 Data Definition Language.

Declaración de un esquema jerárquico:

SCHEMA NAME = <nombre del esquema>

<declaraciones de árboles>

Declaración de un árbol:

TREE <nombre> <lista de declaraciones de tipos de registros>

Declaración de tipo de registro:

RECORD <nombre> <información>

La información es de las siguientes clases:

a) Campos: <n1_nivel> <nombre> <tipo>

Ejemplo: 1 Cantidad integer

b) Posición:

ROOT │PARENT = <nombre>

c) Registro virtual (opcional):

VIRTUAL <nombre-registro> IN <nombre_árbol>

d) Punteros:

POINTER = [PARENT│<lista tipos de punteros>]

Ejemplo:

TREE Planes_de_Estudio

RECORD Centro ROOT

1 codigo char(3)

1 nombre char(30)

RECORD Estudio PARENT=Centro

1 codigo char(2)

1 nombre char(50)

1 duracion integer

RECORD Asignatura PARENT=Estudio

1 clave char(3)

1 nombre char(30)

2 Data Manipulation Language.

2.1 Consultas

Se realizan con la orden GET. Se realizan dos tareas:

1) Localiza un registro en la BD y hace que el puntero de dirección indique a él.

2) Copia dicho registro a la plantilla del área de trabajo

Clases de Consultas:

- GET FIRST <tipo_registro> [WHERE <condición>]

Localiza el primer registro del tipo indicado. si hay cláusula where, se localiza el primero que

cumple la condición. También se usa como GET UNIQUE.

- GET NEXT <tipo_registro> [WHERE <condición>]

Localiza el siguiente registro del tipo indicado. Si hay cláusula where, se localiza el siguiente que

cumple la condición.

GET NEXT WITHIN PARENT <tipo_registro> [WHERE <condición>]

Localiza el siguiente registro del tipo indicado, dentro de un subárbol cuya raíz es el último

registro localizado con GET FIRST o GET NEXT. Si hay cláusula where, se localiza el siguiente

que cumple la condición.

Consultas con retención del registro:

El usuario que hace la consulta retiene el registro hasta que lo libera. El registro está bloqueado y no pueden acceder a él los demás usuarios. Las órdenes con retención son equivalentes a las anteriores:

GET HOLD { FIRST │NEXT │NEXT WITH}

2.2. Actualizaciones.

Las operaciones se realizan a nivel de registro. Los registros se almacenan desde las plantillas del área de trabajo.

- INSERT <tipo_registro> [WHERE <condición>]

El registro se inserta en la primera posición de la base de datos donde se pueden colocar registros de ese tipo. Si hay cláusula where el sistema busca un registro que satisfaga la condición, y el registro recién creado se inserta como su hermano más a la izquierda.

- REPLACE

Sustituye el contenido de un registro con el de la plantilla del área de trabajo. Dicho registro debe haber sido recuperado previamente con un GET HOLD ... para que el puntero de dirección señale hacia él.

- DELETE

Elimina un registro. Dicho registro debe haber sido recuperado previamente con un GET HOLD... para que el puntero de dirección señale hacia él.

EJEMPLO: