Base de datos jerargica

Una base de datos jerárquica es un tipo de sistema de gestión de bases de datos que, como su nombre indica, almacena 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, y así sucesivamente.

Esta relación jerárquica no es estrictamente obligatoria, de manera que pueden establecerse relaciones entre nodos hermanos, y 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).

Cómo funcionan

Limitaciones del modelo jerárquico

Duplicidad de registros

Integridad referencia

Desmoralización

• Combinar las relaciones

• Duplicar los atributos no claves

• Introducción de grupos repetitivos

• Crear tablas de extracción

• Se debe desnormalizar para optimizar el esquema relacional

• Para hacer referencia a la combinación de 2 relaciones que forman una sola relación

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

Estructura de datos

• Alta, adicionar un nuevo valor a la estructura.

• Baja, borrar un valor de la estructura.

• Búsqueda, encontrar un determinado valor en la estructura para realizar una operación con este valor, en forma secuencial o binario (siempre y cuando los datos estén ordenados).

• Ordenamiento, de los elementos pertenecientes a la estructura.

• Apareo, dadas dos estructuras originar una nueva ordenada y que contenga a las apareadas.

Implementaciones

Soporte de lenguajes

Multiconjunto

Índice

Teoría básica de conjuntos

Artículo principal: Conjunto

Ejemplos.

• Los conjuntos numéricos usuales en matemáticas son: el conjunto de los números naturales N, el de los números enteros Z, el de los números racionales Q, el de los números reales R y el de los números complejos C. Cada uno es subconjunto del siguiente:

• El espacio tridimensional E₃ es un conjunto de objetos elementales denominados puntos p, p ∈ E₃. Las rectas r y planos α son conjuntos de puntos a su vez, y en particular son subconjuntos de E₃, r ⊆ E₃ y α ⊆ E₃.

Álgebra de conjuntos

Artículo principal: Álgebra de conjuntos

• Unión. La unión de dos conjuntos A y B es el conjunto A ∪ B que contiene cada elemento que está por lo menos en uno de ellos.

• Intersección. La intersección de dos conjuntos A y B es el conjunto A ∩ B que contiene todos los elementos comunes de A y B.

• Diferencia. La diferencia entre dos conjuntos A y B es el conjunto A \ B que contiene todos los elementos de A que no pertenecen a B.

• Complemento. El complemento de un conjunto A es el conjunto A^∁ que contiene todos los elementos (respecto de algún conjunto referencial) que no pertenecen a A.

• Diferencia simétrica La diferencia simétrica de dos conjuntos A y B es el conjunto A Δ B con todos los elementos que pertenecen, o bien a A, o bien a B, pero no a ambos a la vez.

• Producto cartesiano. El producto cartesiano de dos conjuntos A y B es el conjunto A × B que contiene todos los pares ordenados (a, b) cuyo primer elemento a pertenece a A y su segundo elemento b pertenece a B.

A diferencia del modelo relacional, el modelo jerárquico no diferencia una vista lógica de una vista física de la base de datos. De manera que las relaciones entre datos se establecen siempre a nivel físico, es decir, mediante referencia a direcciones físicas del medio de almacenamiento (sectores y pistas).

Los datos se almacenan en la forma de registros, el equivalente a las tuplas del modelo relacional. Cada registro consta de un conjunto de campos, el equivalente a los atributos del modelo relacional. Un conjunto de registros con los mismos campos se denomina fichero (record type, en inglés), el equivalente a las relaciones 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.

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.

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.

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

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:

Cuando se debe desnormalizar:

Ejemplo:

En programación, una estructura de datos es una forma de organizar un conjunto de datos elementales con el objetivo de facilitar su manipulación. Un dato elemental es la mínima información que se tiene en un sistema.

Una estructura de datos define la organización e interrelación de estos y un conjunto de operaciones que se pueden realizar sobre ellos. Las operaciones básicas son:

Otras operaciones que se pueden realizar son:

Cada estructura ofrece ventajas y desventajas en relación a la simplicidad y eficiencia para la realización de cada operación. De esta forma, la elección de la estructura de datos apropiada para cada problema depende de factores como la frecuencia y el orden en que se realiza cada operación sobre los datos.

En informática, un conjunto es una colección (contenedor) de ciertos valores, sin ningún orden concreto ni valores repetidos. Su correspondencia en las matemáticas sería el conjunto finito. Sin tener en cuenta la secuencia, ni el hecho de que no haya valores repetidos, se asemeja a una lista. Un conjunto puede verse como una cadena asociativa (array) (mapeado parcial) donde no se atiende al valor de cada par clave-valor.

Los conjuntos pueden implementarse usando diversas estructuras de datos. Con una estructura de datos ideal se comprueba si un objeto se encuentra en el conjunto, además de activarse otras operaciones útiles tales como la iteración sobre todos los objetos del conjunto, la realización de uniones o intersecciones entre dos conjuntos, o la toma del complemento de un conjunto en algún dominio limitado. Cualquier estructura de datos en cadena asociativa puede usarse para implementar un conjunto, dejando que los juegos de claves sean los elementos del conjunto, e ignorando los valores. Gracias a su parecido con las series asociativas, los conjuntos se implementan habitualmente por los mismos medios, es decir, un árbol binario de búsqueda auto-balanceable para conjuntos ordenados (con O (log n) para la mayoría de operaciones), o una tabla hash para conjuntos no ordenados (que tienen O(1) en el caso promedio, pero O (n) en el peor caso, para la mayoría de operaciones). Es posible usar una tabla de hash lineal ordenada para crear conjuntos deterministamente ordenados. Otros métodos generalizados incluyen las cadenas (array). En particular, un subconjunto de enteros 1..n puede ser implementado de manera eficaz como en una matriz de bits con n bits, que además ofrece operaciones de unión e intersección muy eficaces. El filtro Bloom implementa un conjunto por probabilidad, por medio de una muy compacta representación, pero arriesgando una pequeña probabilidad de falsos positivos en interrogantes. Sin embargo, casi ninguna de estas estructuras de datos ofrece operaciones de conjuntos como de unión o de intersección de manera fiable. Para dichas operaciones existen otras estructuras de datos de conjunto más especializadas.

Uno de los primeros lenguajes que soportaban conjuntos fue Pascal; muchos lenguajes lo incluyen ahora, ya sea en el núcleo del lenguaje o en una librería estándar. El Lenguaje de programación Java ofrece la interfaz Set para el soporte de conjuntos (donde lo implementa la clase HashSet usando una tabla hash), y la sub-interfaz SortedSet para dar soporte a conjuntos ordenados (implementado por la clase TreeSet por medio de un árbol de búsqueda binario). En C++, STL ofrece la clase "conjunto" para templates, que implementa a un conjunto ordenado usando un árbol de búsqueda binario; el STL de SGI ofrece la clase "hash_set", implementando conjuntos con una tabla de hash. Python tiene un tipo de conjunto incorporado, pero no un conjunto en sí.

Una variación del conjunto es el multiconjunto o bolsa, que es lo mismo que una estructura de datos de conjunto, pero que admite valores repetidos. Formalmente, un multiconjunto se puede considerar como una serie asociativa que mapea elementos únicos enenteros positivos, indicando la multiplicidad del elemento, aunque la implementación propiamente dicha pueda variar. En C++, la biblioteca de templates estándar (Standard Template Library) ofrece la clase "multiset" para los multiconjuntos ordenados, y la STL de SGI ofrece la clase "hash_multiset", que implementa conjuntos usando una tabla hash. Las colecciones de Apache Commons ofrecen la interfaz Bag y SortedBag para Java; además de implementar clases como HashBag y TreeBag, que son semejantes a otras implementaciones de conjuntos con nombres similares

La teoría de conjuntos es una rama de las matemáticas que estudia las propiedades de los conjuntos: colecciones abstractas de objetos, consideradas como objetos en sí mismas. Los conjuntos y sus operaciones más elementales son una herramienta básica en la formulación de cualquier teoría matemática.¹

Sin embargo, la teoría de los conjuntos es lo suficientemente rica como para construir el resto de objetos y estructuras de interés en matemáticas: números, funciones, figuras geométricas, ...; y junto con lalógica permite estudiar los fundamentos de esta. En la actualidad se acepta que el conjunto de axiomas de la teoría de Zermelo-Fraenkel es suficiente para desarrollar toda la matemática.

Además, la propia teoría de conjuntos es objeto de estudio per se, no sólo como herramienta auxiliar, en particular las propiedades y relaciones de los conjuntos infinitos. En esta disciplina es habitual que se presenten casos de propiedades indemostrables o contradictorias, como la hipótesis del continuo o la existencia de un cardinal inaccesible. Por esta razón, sus razonamientos y técnicas se apoyan en gran medida en la lógica matemática.

El desarrollo histórico de la teoría de conjuntos se atribuye a Georg Cantor, que comenzó a investigar cuestiones conjuntistas «puras» del infinito en la segunda mitad del siglo XIX, precedido por algunas ideas de Bernhard Bolzano e influenciado por Richard Dedekind. El descubrimiento de las paradojas de la teoría cantoriana, de conjuntos, formalizada por Gottlob Frege, propició los trabajos de Bertrand Russell,Ernst Zermelo, Abraham Fraenkel y otros a principios del siglo XX.

La teoría de conjuntos es una rama de las matemáticas que estudia las propiedades de los conjuntos: colecciones abstractas de objetos, consideradas como objetos en sí mismas. Los conjuntos y sus operaciones más elementales son una herramienta básica en la formulación de cualquier teoría matemática.

Sin embargo, la teoría de los conjuntos es lo suficientemente rica como para construir el resto de objetos y estructuras de interés en matemáticas: números, funciones, figuras geométricas, ...; y junto con la lógica permite estudiar los fundamentos de esta. En la actualidad se acepta que el conjunto de axiomas de la teoría de Zermelo-Fraenkel es suficiente para desarrollar toda la matemática.

Además, la propia teoría de conjuntos es objeto de estudio per se, no sólo como herramienta auxiliar, en particular las propiedades y relaciones de los conjuntos infinitos. En esta disciplina es habitual que se presenten casos de propiedades indemostrables o contradictorias, como la hipótesis del continuo o la existencia de un cardinal inaccesible. Por esta razón, sus razonamientos y técnicas se apoyan en gran medida en la lógica matemática.

El desarrollo histórico de la teoría de conjuntos se atribuye a Georg Cantor, que comenzó a investigar cuestiones conjuntistas «puras» del infinito en la segunda mitad del siglo XIX, precedido por algunas ideas de Bernhard Bolzano e influenciado por Richard Dedekind. El descubrimiento de las paradojas de la teoría cantoriana, de conjuntos, formalizada por Gottlob Frege, propició los trabajos de Bertrand Russell,Ernst Zermelo, Abraham Fraenkel y otros a principios del siglo XX.

La teoría de conjuntos más elemental es una de las herramientas básicas del lenguaje matemático. Dados unos elementos, unos objetos matemáticos como números o polígonos por ejemplo, puede imaginarse una colección determinada de estos objetos, un conjunto. Cada uno de estos elementos pertenecen al conjunto, y esta noción de pertenencia es la relación relativa a conjuntos más básica. Los propios conjuntos pueden imaginarse a su vez como elementos de otros conjuntos. La pertenencia de un elemento a a un conjunto A se indica como a ∈ A.

Una relación entre conjuntos derivada de la relación de pertenencia es la relación de inclusión. Una subcolección de elementos B de un conjunto dado A es un subconjunto de A, y se indica como B ⊆ A.

Existen unas operaciones básicas que permiten manipular los conjuntos y sus elementos, similares a las operaciones aritméticas, constituyendo el álgebra de conjuntos.