No modelo hierárquico de banco de dados, os dados são representados como coleções de registros e são organizados usando a estrutura de dados de árvore. O tipo de um registro é definido por uma coleção de campos (atributos) e, graças à estrutura de árvore, é possível usar o relacionamento pai/filho para relacionar registros, onde um registro pai pode possuir um ou mais registros filhos, mas um registro só poder ter um registro pai (também conhecido como relacionamento 1:N).
História
O modelo foi um dos primeiros a serem usados pois era bastante apropriado em mídias de armazenamento de tipo linear, como fitas magnéticas que eram usadas na época. Foi criado pela IBM na década de 1960. Sua primeira implementação foi feita pela própria empresa, o IMS. O IMS possui uma extensiva capacidade de transações e continua sendo um produto forte no mercado, mesmo depois de mais de quarenta anos após sua criação. O sistema recebeu diversas melhorias ao longo do tempo e atualmente suporta tecnologias como Java, JDBC, XML, etc.
Conceitos Básicos
Um banco de dados hierárquico consiste de uma coleção de registros que estão conectados através de links. Cada link é uma associação entre precisamente dois registros. Em geral, este modelo é similar ao modelo de Rede, sendo que o que torna os dois modelos diferentes é a estrutura de dados usada para organização do registro.
Para melhor visualização dos conceitos, considere um banco de dados que representa um relacionamento conta-cliente em um sistem bancário. Portanto, existem dois tipos de registros: conta e cliente. O tipo de registro cliente consiste de três campos: customer_name, customer_street e customer_city. Da mesma maneira, o tipo de registro conta possui dois campos: account_number e balance.
Uma instância desse banco de dados aparece na figura H.1. Cada retângulo representa um registro e cada linha representa um link que liga os dois registros. O registro no topo de hierárquia é apenas a raiz da árvore (nível 0), chamado de dummy node. É possível observar que os registros do tipo cliente estão no nível 1 da árvore, enquanto os regitros do tipo conta estão no nível 2. Se um registro cliente está associado a um ou mais registros do tipo conta, então aquele cliente específico possui aquela(s) conta(s). Um banco de dados baseado no modelo hierárquico é uma coleção de tais árvores, portanto formando uma floresta. Uma árvore deste tipo é chamada de database tree.
No caso da figura, o cliente Hayes possui a conta A-102, enquanto o cliente Johnson possui as contas A-101 e A-201 e o cliente Turner possui a conta A-305.
O conteúdo de um determinado registro pode ser repetido em diferentes localizações. Por exemplo, neste sistema bancário do exemplo da figura, uma conta pode pertencer a vários clientes. Portanto, a informação referente a esta determinada conta ou a informação dos vários clientes que possuem esta conta terá de ser repetida. Esta repetição pode ocorrer na mesma árvore ou em diferentes árvores e apresenta duas desvantagens:
- 1. Inconsistência pode surgir com atualizações nos dados do banco
- 2. Desperdício de espaço é inevitável
Diagrama de topologia em árvore
O diagrama de topologia em árvore é um esboço do banco de dados. O diagrama consiste em dois componentes:
- 1. Caixas, que correspodem aos tipos dos registros
- 2. Linhas, que correspodem aos links
Este diagrama serve o mesmo propósito do digrama entidade-relacionamento (E-R). Os relacionamentos formados no diagrama devem ser tais que apenas relacionamentos 1:1 e 1:N existam entre o pai e o filho. A forma genérica de como o digrama deve parecer está na figura H.2. Na figura aparece que a seta aponta do filho para o pai. Um pai pode ter uma seta apontando para um filho, mas um filho deve ter uma seta apontando para o pai.
Definição (árvore enraizada): por ser uma ávore, não pode haver nenhum ciclo. Além disso, há um tipo de registro que é designado como raiz da árvore. Os relacionamentos formados no diagrama entre pais e filhos devem ser apenas 1:N ou 1:1.
O esquema do banco de dados é representado como uma coleção desses diagramas. Para cada diagrama, existe uma única instância de uma database tree. A raiz dessa árvore é um dummy node, e os filhos deste são instâncias de registros do tipo da raiz do digrama especificado. Cada uma destas instâncias pode ter vários filhos, que são instâncias de vários tipos de registros que estão especificados no diagrama correspondente.
Relacionamento Simples
Considere o diagrama da figura H.3a que consiste de duas entidades cliente (customer) e conta (account) associados por um relacionamento binário, 1:N, denominado depositante, sem atributos. Este diagrama especifíca que um cliente pode ter várias contas, mas uma conta só pode pertencer a um cliente. O diagrama de topologia em árvore aparece na figura H.3b.
O relacionamento depositante é representado pelo link com seta de conta para cliente. Caso o relacionamento fosse 1:1, então o link tem duas setas, uma apontando para o registro do tipo cliente e outra apontando para o registro do tipo conta como na figura H.4. Uma instância que corresponde ao diagrama da figura H.3b pode ser vista na figura H.5.
Caso o relacionamento depositante fosse N:M (figura H.6a), então a transformação seria um pouco mais complicada. Apenas relacionamentos 1:1 e 1:N podem ser diretamente representados no modelo hierárquico. Há diferentes maneiras de transformar esse diagrama E:R, porém, todas elas farão com que as árvores tenham informação repetida.
A escolha de qual transformação usar neste caso depende de alguns fatores, principalmente do tipo de cosulta que é esperado no banco. A figura H.7 mostra um exemplo de instância do banco correspondente ao digrama da figura H.6. Nota-se que todos os registros ficaram repetidos na base, e, além disso, a conta A-201 aparece duas vezes na primeira árvore, assim como os clientes Johnson e Smith aparecem duas vezes na segunda árvore.
Se o relacionamento inclui atributos, então a transformação seria mais complicada. Como um link não pode conter nenhum dado, seria necessário criar um novo tipo de registro para comportar estes atributos e, então esse registro seria incluido na relação. Maiores detalhes sobre esta transformação e relacionamentos que envolvem mais de duas entidades se encontram em [1].
Vários relacionamentos
O esquema descrito para transformar um diagrama E-R em um diagrama de topologia em árvore garante que, para cada relacionamento único, a transformação irá resultar em diagrama que é da forma de árvores enraizadas. Infelizmente, a aplicação de tal transformação individualmente em cada relacionamento de um diagrama E-R não necessariamente resulta em diagramas que são ávores enraizadas. A técnica usada para resolver este problema é dividir o diagrama em questão em vários diagramas, sendo que cada um é uma árvore enraizada. A seguir estão descritos dois exemplos gerais de como lidar neste tipo de situação. (A grande quantidade de diferentes possibilidades torna difícil apresentar um algoritmo genérico de transformação que cobre todos os casos).
Considere o diagrama E-R da figura H.8a, aplicando a transformação proposta na seção 3.1, ou seja, separadamente para relacionamentos conta-agência ou depositor, obtemos como resultado o diagrama da figura H.8b. Este diagrama não é uma árvore enraizada, pois mesmo que o tipo de registro conta pareça ser a raiz, não o é pois este tipo de registro tem relação N:1 com ambos seus filhos, o que viola a definição de árvore enraizada apresentada na seção 3. Para transformar o diagrama em um que seja da forma de uma árvore enraizada, duas árvores com a raiz sendo do tipo conta como mostra a figura H.9.
Funcionamento
Um sistema hierárquico é um DBMS que prove mecanismos de inserção, modificação, deleção e recuperação de registros em um banco de dados hierárquico. Graças aos princípios do modelo hierárquico, cada novo registro que é inserido (exceto para um ocorrência do registro raiz) precisa ser conectado a uma ocorrência do tipo de registro pai.
A busca é feita usando caminhamento pré-ordem na árvore. Para que a busca seja eficiente, a query deve estar bem especificada, pois evita que sub-árvores que não contém a informação desejada sejam vasculhadas em vão. Quanto mais complexa é a estrutura da árvore, mais complexa será a query.
Quando um registro é apagado, todos os seus registros descendentes também devem ser apagados. O modelo hierárquico não permite que registros que não são raízes existirem sem antecessores. Para manter os registros descendentes sem um registro pai, como em algumas vezes é necessário, alguns sistemas provêm comandos que apaga os valores do registro pai, mas não o registro em si. Desta maneira, é possível que registros vazios (null) existam na base.
Além dos problemas de complexidade e inflexibilidade, há o problema de redundância que foi apresentado nas seções anteriores. Para contornar este problema, retira-se o requerimento de que a estrutura deve ser uma árvore, mas assim o modelo se assemelha muito ao modelo de rede.
Referências
[1] KORTH, H. F.; SILBERSCHATZ, A. Database System Concepts. New York:McGraw-Hill, 2005. p.1168
[2] D.C.; TSICHRITZIS; F.H. LOCHOVSKY Hierarchical Database Management: A Survey. Computing Surveys, Toronto, Vol. 8, n.1, p. 105-126, 1976