Relatório de MC326 - TP2

30 de abril de 2002

Grupo:

Gustavo Sverzut Barbieri RA: 008849
Ivens Prates Telles Alves RA: 008908
Walter Wong  RA: 010080

1 Introdução

No segundo Trabalho Prático da matéria de estrutura de arquivos, fizemos uma implementação da base de dados de um hospital, já criada no Trabalho Prático 1. Implementamos a função de inserção, remoção e busca por qualquer campo da base de dados, em qualquer combinação.

A função de inserção permite inserir novos pacientes na base de dados. A função de remoção complementa a função anterior e remove um paciente da base de dados. A função busca permite localizar um paciente específico a partir do número somente, ou da combinação de nome, idade, diagnóstico ou tratamento.

Para testar, usaremos uma base de dados com elementos aleatórios, a mesma usada no nosso Trabalho Prático 1.

2 Desenvolvimento

Dividimos o problema em 3 classes principais:

• Banco de Dados: A classe Banco de Dados manipula o arquivo com os dados e as classes de índice. Ela é responsável pela inserção, remoção e procura, sempre usando as classes auxiliares Índice e Índice Secundário.

Essa classe se utiliza de outras sub-classes menos importantes como, por exemplo, a classe registro, a qual é responsável por quebrar e montar os registros no arquivos de dados e na memória. Vide documentação em html fornecida junto com o pacote (diretório doc/html/).

A função Insere primeiramente confere se o número do paciente já existe na base de dados, pois ela é uma chave primária, não podendo ser repetida. Após esta conferência ela retorna caso a chave já exista ou prossegue. Prosseguindo ela chama as funções de inserção do índice e dos índices secundários.

A função Remove primeiramente confere se o número do paciente existe e então marca o registro como apagado na base de dados e também o retira do índice.

A função Procura pode receber nomes (junto com sobrenomes. Ex: João Alves), idade, diagnóstico e tratamentos (quantos quiser. Ex: Ácido Acetilsalicílico/Repouso por 3 dias). Ela pega os valores dados, monta na memória e em arquivos de índices secundários listas ligadas com índices ordenados (para isso, usa-se uma função chamada Insere_Ordenado), faz o “matching” entre essas listas, ou seja, cria uma lista de resultado com os índices que são comuns em todas as listas procuradas, e faz isso em listas ordenadas, encontrando rapidamente os índices iguais, e assim retorna para o programa principal uma lista com os registros buscados. Essa função faz mais do que foi pedido na “especificação” deste trabalho prático, pois faz uma busca completa no banco, ou seja, com qualquer combinação de informação dada pelo usuário.

• Índice: A classe Índice implementa uma estrutura Árvore Binária a qual é responsável por guardar os pares de chave e referência. Esta classe faz procuras nesta estrutura, grava e a restaura para a memória, insere elementos (pares de chave e referência), altera-os e também os remove.

Esta classe se utiliza de outras sub-classes como por exemplo a classe Árvore Binária, a qual se encarrega de inserir e remover elementos desta estrutura, além de outras, vide documentação para mais informações.

• Índice Secundario: Esta classe se utiliza de duas outras classes: a classe Índice(explicada acima) e a classe Lista Invertida, a qual se encarrega de manipular uma lista invertida no arquivo.

A classe Índice Secundário apenas manipula estas duas classes de forma conveniente, inserindo um par com chave e referência na estrutura de Índice, na qual chave é a chave primária e referência é a posição no arquivo com a Lista Invertida, e depois inserindo na Lista Invertida as chaves primárias as quais as chaves secundárias se referenciam. A procura nesta classe também segue os mesmo padrão: primeiro se faz a procura pela chave secundária na estrutura com o Índice, obtendo-se, assim, a posição do cabeça da lista invertida correspondente, assim pede-se à classe Lista Invertida que retorne a lista com cabeça naquela posição.

Nós separamos a parte de implementação do programa da parte da sua apresentação, tornando-o mais flexível, pois a parte da apresentação apenas chama a classe Banco de Dados, e essa parte desconhece o que está por trás do funcionamento desta (Índices, Procuras, Estrutura de Registros, Insere, Remove, etc).

Para maiores detalhes sobre os intrínsecos das classes, bem como as classes auxiliares que desenvolvemos(como String, Arvore_Binaria, Elemento_Indice), vide a documentação em html que esta no diretório “doc/html/”. Nesta documentação relata-se todos os métodos com seus respectivos parâmetros e retornos, bem como a herança das classes.

3 Conclusão

Pudemos observar que nosso programa, graças ao bom trabalho feito no Trabalho Prático 1 (que foi generalizado para qualquer caso, não só o pedido no enunciado dele) foi muito satisfatório. O programa consegue gerar os registros sem muita diferença de velocidade para o TP1, pois dessa vez são carregados na memória os índices secundários também. Se nós tivessemos feito o TP1 muito específico para o enunciado dele, teriamos tido muito trabalho agora, já que teriamos que fazer um TP completamente novo. Assim, repetimos a generalização feita no TP1 neste TP2, para que nos que se seguirem nós pudessemos reutilizá-los sem qualquer pavor.

Usando o sistema de buscas por arvore binária, conseguimos minimizar um pouco o tempo de busca. O ideal seria usarmos uma Árvore B+, que provavelmente será implementada em outra oportunidade. Mas o maior atraso foi causado pelo acesso ao disco na inserção, pois usamos tudo no formato texto (e não binário), e não fizemos nenhuma otimização de baixo nível para melhorar isso (leituras de “buffers” de tamanho ótimo, etc).

Nosso sistema de buscas por qualquer campo foi feito também sem muito trabalho adicional, pois nossas classes adicionais nos auxiliaram neste trabalho. O problema maior foi fazer uma lista ligada de lista ligada, e depois fazer o “matching” destas, já que teriamos n listas, de acordo com as opções preenchidas pelos usuários. Mas o fato de nós criamos essas listas de busca ordenadas nos auxiliaram bastante neste caso, e ainda optimizou a busca.

As funções Insere e Remove, do Bando de Dados, foram facilmente adaptadas às novas especificações devido ao seu desenvolvimento planejado no Trabalho Prático 1. Para a função Insere, a qual já existia, foi alterada para se inserir as chaves secundárias nos respectivos índices secundários. Para a funçõa Remove, a qual foi implementada para este trabalho prático, não obtivemos problemas, pois a parte de manipulação do arquivo foi fácil e o Índice, juntamente com a Árvore Binária, já disponibilizava a função Remove.

Um outro problema encontrado nesse trabalho foi o uso dos tipos em C++. Os tipos nesta linguagem não implementam uma maneira fácil de se trabalhar com texto. Para isso, elaboramos a classe String, a qual torna a manipulação de texto como qualquer outro tipo (int, float, etc). O uso da linguagem C++ ajuda nesse caso, pois podemos especificar os operadores para determinada classe.

4 Referências

Documentação das classes em html, a qual se encontra no diretório “doc/html”. O pacote com o código fonte e com esta documentação pode ser obtido no endereço “http://www.ic.unicamp.br/ ra008849/downloads/mc326/mc326_tp2.tar.gz” ou com qualquer integrante do grupo.