3 Semestre

1 INTRODUÇÃO

As propriedades ACID (atomicidade, consistência, isolamento e durabilidade) são fundamentais nos bancos de dados, sejam os relacionais ou os orientados a documentos. Então, também é valido tratarmos desse assunto referente aos bancos relacionais, em um contexto geral.

Atualmente os sistemas de informação suportam vários usuários. O banco de dados tem que garantir a confiabilidade nas transações, haja vista que muitas podem ocorrer concorrentemente.

Uma transação é um programa em execução que forma uma unidade lógica de processamento no banco de dados. Uma transação inclui uma ou mais operações de acesso ao banco de dados — englobam operações de inserção, exclusão, alteração ou recuperação.

O sistema deverá garantir que: (1) todas as operações na transação foram com¬pletadas com sucesso e seu efeito será gravado permanentemente no banco de dados ou (2) a transação não terá nenhum efeito sobre o banco de dados ou sobre quaisquer outras transações.

2 DESENVOLVIMENTO

2.1 ESTRUTURAS DE DADOS

Diferentes tipos de estrutura de dados são adequados a diferentes tipos de aplicação e algumas são altamente especializadas, destinando-se a algumas tarefas específicas. Estruturas de dados e algoritmos são temas fundamentais da ciência da computação, sendo utilizados nas mais diversas áreas do conhecimento e com os mais diferentes propósitos de aplicação. Sabe-se que algoritmos manipulam dados. Quando estes dados estão organizados (dispostos) de forma coerente, caracterizam uma estrutura de dados. A organização e os métodos para manipular essa estrutura é que lhe conferem singularidade. As estruturas de dados são chamadas tipos de dados compostos que se dividem em homogêneos (vetores e matrizes) e heterogêneos (registros).

2.2 FILA (FIFO)

Uma Fila é um conjunto ordenado de itens a partir do qual se podem eliminar itens numa extremidade (chamado início da fila) e no qual se podem inserir itens na outra extremidade (chamada final da fila). O primeiro elemento inserido numa fila é o primeiro a ser removido. Sendo assim, uma fila é ocasionalmente chamada de FIFO (first - in, first-out – o primeiro que entra é o primeiro que sai). Como exemplo de fila, no cotidiano, pode citar uma fila de banco. Uma fila possui duas funções básicas: ENQUEQUE, que adiciona um elemento ao final da fila, e DEQUEQUE, que remove o elemento no início da fila. Um exemplo desse tipo de estrutura de dados em computação é a implementação de uma fila de impressão. A interface do tipo abstrato que representa uma estrutura de fila pode ser composta pelas seguintes operações: criar uma estrutura de fila, inserir um elemento no fim, retirar o elemento do início, verificar se a fila está vazia e liberar a fila. Existem duas estratégias para a implementação de fila: uma usando um vetor para armazenar elementos, onde se deve fixar o número máximo n de elementos na fila; a outra é feita através de uma lista encadeada, em que cada nó guarda um ponteiro para o próximo nó da lista, assim são necessários dois ponteiros, início e fim, que apontam respectivamente para o primeiro e o último elemento da fila. Na implementação de filas por meio de arranjos, os itens são armazenados em posições contíguas de memória, a operação enfileira.

Faz a parte de trás da fila expandir-se, a operação desenfileira faz a parte da frente da fila contrair-se. Na implementação de filas por meio de apontadores há uma célula cabeça para facilitar a implementação das operações enfileira e desenfileira quando a fila está vazia. A fila é implementada por meio de células, cada célula contem um item da fila e um apontador para outra célula, a estrutura Tipo Fila contém um apontador para frente da fila (célula cabeça) e um apontador para a parte de trás da fila. Portanto as inserções são feitas sempre no final da fila, as remoções sempre no início e a operação de pesquisa é feita a partir do início.

Como exemplo de aplicação para filas, pode-se citar a fila de processos de um sistema operacional. Nela, é estabelecido um tempo t o ser usado por cada um dos processos. Se durante a execução de um processo o tempo passa de 0 a t, este é posto na fila e o processo seguinte é executado. Se o processo seguinte não terminar de ser executado no tempo t, ele é posto na fila e o processo subseqüente é executado, e assim por diante até todos os processos serem executados.

2.3 PILHA (LIFO)

Uma pilha é um conjunto ordenado de itens no quais novos itens podem ser inseridos e eliminados em uma única extremidade chamado topo da pilha. A pilha também é ocasionalmente conhecida como LIFO (last in, first out – último que entra é o primeiro que sai). Um exemplo no cotidiano é a uma pilha de pratos. No caso de pilha utiliza - se apenas um ponteiro, o ponteiro topo, pois as inserções e remoções são realizadas n mesma extremidade. A pilha é a estrutura de dados mais simples, e possivelmente por essa razão é a mais utilizada em programação. Existem duas operações básicas que devem ser implementadas numa estrutura pilha: a operação para empilhar um novo elemento, inserindo - o no topo (push), e a operação para desempilhar um elemento removendo - o do topo (pop). As pilhas podem ser implementadas usando um vetor ou uma lista encadeada. Quando sabe- se o número máximo de elementos que podem estar armazenados simultaneamente na pilha, a implementação pode ser feita usando um vetor. Quando o número máximo de elementos que serão armazenados na pilha é desconhecido, devemos programar a pilha empregando uma lista encadeada, os elementos são armazenados na lista e a pilha pode ser representada simplesmente por um ponteiro para o primeiro nó da lista. As operações de inserção, remoção e pesquisa são realizadas todas no topo da pilha.

2.4 ALOCAÇÃO SIMPLESMENTE ENCADEADA

Na alocação simplesmente encadeada, cada nó aponta para o próximo nó. Só pode ser percorrida em um único sentido. Possui necessariamente um variável ponteiro apontando para seu primeiro elemento. Essa variável será utilizada sempre, mesmo que a lista esteja vazia, e deverá apontar sempre para o início da lista. Um elemento da lista é composto de duas partes: a informação propriamente dita e uma conexão com o próximo elemento. São chamadas de simplesmente encadeadas por possuírem somente o endereço de seu próximo elemento. Ao incluir um nó, o último nó da lista passará a apontar para o novo nó. Em aplicações em que não existe visão sobre