Arquivos Seqüenciais Inhaúma Neves Ferraz Departamento de Ciência da Computação Universidade...

Arquivos Seqüenciais

Inhaúma Neves FerrazDepartamento de Ciência da Computação

Universidade Federal Fluminense

ferraz@ic.uff.br

2

Sumário

GENERALIDADESATUALIZAÇÃO DO ARQUIVO MESTRE

("BALANCED LINE ")

Caracterização do Problema Transações Problemáticas

INTERCALAÇÃO

GeneralidadesAlgoritmo BásicoOtimização do algoritmo

3

Conceito

Arquivos em série são aqueles nos quais os registros só podem ser acessados em ordem linear, ou seja, o registro de ordem i só pode ser acessado depois do registro de ordem i 1Arquivos seqüenciais são aqueles nos quais os registros são armazenados em ordem ascendente ou descendente do valor de um ou mais de seus atributos (chave)

4

Utilização

Não há melhor organização do que a seqüencial para as situações que exijam varredura ou cobertura periódica de todos os registros de um dado arquivoExemplos Cobranças periódicas de serviços públicos Geração das listas de presença das escolas Confecção das folhas de pagamento de

empregados Extração dos talões de cobrança de clientes, etc.

5

ATUALIZAÇÃO DO ARQUIVO MESTRE (" BALANCED LINE ")

Caracterização do ProblemaUm problema comum no tratamento da

informação consiste na atualização de um arquivo (o arquivo mestre) por um conjunto de transações que podem ser : inclusão de registros exclusão de registros modificação de registros

6

Arquivo de Transações

Registros do arquivo de transações são compostos de : chave primária identificador do tipo de transação(" I ", "E ", " M ") identificador do atributo a atualizar, no caso de

modificação valores de todos os atributos, no caso de inclusão

 É interessante fazer um pré-processamento no arquivo de transações para validação de dados e verificação da consistência, reduzindo a complexidade do algoritmo principal

7

Esquema de Balance Line

8

Gerações de Balance Line

9

Processamento do Balance Line (1)

Os arquivos são classificados em ordem ascendente e terminados por um delimitador de fim de arquivo(" flag " ou " sentinela "), com valor de chave primária não inferior a qualquer outro ("high value")Na repetição principal, em cada laço, a variável chave_corrente recebe o valor da próxima chave a ser gravadaTudo se passa como se os arquivos principal e de transações fossem pilhas cujos topos fossem os registros correntes de cada arquivoOs topos destas pilhas são comparados e o de menor chave é excluído da pilha e incluído no arquivo de saídaSe a chave dos dois topos coincidirem, o registro do arquivo principal sofre as atualizações indicadas no registro do arquivo de transações e o resultado vai para o arquivo de saídaSe existir registro com chave igual a chave corrente no arquivo mestre, o " flag " alocado é ligado e o registro é movido para o " buffer " mestre

10

Processamento do Balance Line (2)

Transações com a mesma chave da chave corrente são tratadas da maneira que se segue : Inclusão - Cria-se novo registro no " buffer" mestre e liga-se o " flag " alocado Se este " flag " já estivesse ligado ocorreria erro por tentativa de

inclusão de registro com chave igual a de registro já existente.

Exclusão - O " flag" alocado é desligado Se este "flag " já estivesse desligado ocorreria erro por tentativa

de exclusão de registro já inexistente.

 Modificação - O " flag " alocado não é alterado Se estiver desligado ocorre erro por tentativa de modificação

de registro inexistente Caso contrário efetuam-se as modificações

11

Processamento do Balance Line (3)

Ao final do tratamento do registro de transações, caso o " flag " alocado esteja ligado, o " buffer " mestre é gravado no arquivo de saída.Após o processamento de todos os registros gravase no arquivo de saída um " flag " de final de arquivo.

12

Transações Problemáticas

Existem algumas transações que são problemáticas Não se trata de imperfeições no algoritmo Os problemas são oriundos de situações reais provocados por usuários, a saber: Inclusão de registro seguida de modificações

nesse registro quando o registro já existia Aproveita-se ou não as modificações ?

Alteração do atributo chave Uma possibilidade consiste em pré-processar o

arquivo de transações transformando essas modificações em uma exclusão seguida de inclusão

13

INTERCALAÇÃO

Generalidades  Intercalação é o processo através do qual diversos

arquivos seqüenciais classificados por um mesmo critério são mesclados gerando um único arquivo seqüencial  

 Algoritmo Básico De cada um dos arquivos a intercalar basta ter em

memória um registro. Considera-se cada arquivo como uma pilha e o registro em memória seu topo

Em cada iteração do algoritmo, o topo da pilha com menor chave é gravado no arquivo de saída e é substituído pelo seu sucessor. Pilhas vazias têm topo igual a " high value "

O algoritmo termina quando todos os topos da pilha tiverem " high value "

14

Busca Direta na IntercalaçãoQuando a ordem de intercalação (número de arquivos a serem intercalados) é grande, é interessante otimizar a busca da menor chaveBuffer é um " array " de registros topos de pilhasPodese fazer busca neste " array “ Busca direta para determinar o elemento de

menor chave Uso de árvores binárias de seleção, tais

como as árvores binárias de vencedores e de perdedores

15

Esquema Básico de Intercalação

16

Árvore binária de vencedores

Árvores binárias de seleção são aquelas nas quais cada nó representa o menor de seus dois filhos e assim a raiz representa o menor nó da árvoreNa árvore binária de vencedores os nós externos representam os elementos do “array” de registros “topos de pilha” dos arquivos a intercalar..Cada nó interno tem três componentes :

Cada nó interno contém informações um ponteiro para o menor de seus descendentes, esteja em que nível estiver (vencedor)Um nó vencedor em vários níveis aparece diversas vezes ao longo da árvore

17

Exemplo de árvore de vencedores

18

Árvore de Perdedores

Conceito : Nesta árvore cada nó interno tem dois

componentes :

Os nós externos ou de falha formam o " array " Buffer, de registro topos de pilha. Cada pilha é um arquivo seqüencial a intercalar

19

Nó da Árvore de Perdedores

20

Processamento da árvore de perdedores

Monta-se a árvore de perdedores representando apenas os nós internos Na árvore de perdedores figurarão todos os nós exceto o nó vencedor

Determina-se s o índice do menor valor em Buffer Grava-se Buffer[s] no arquivo de saída A " pilha " s sofre uma operação de POP Um ponteiro T percorre a árvore de perdedores de pai( Buffer[s] ) até a raiz Em cada momento faz-se o teste : Buffer[perdedor(T)] < Buffer[s] Se o teste for positivo, troca-se s por perdedor[T] e vice-versa

T vai para pai(T) Quando T chega a raiz grava-se Buffer[s] na saída e reinicia-se o processo O processo termina quando todas as pilhas estiverem vazias Os valores de chave não ficam armazenados na árvore e a saída não é pelo elemento da raiz

21

Exemplo

Considere-se a existência de 11 arquivos a intercalar, exibindo apenas as chaves dos registros

22

Derivação da Árvore de Perdedores

.

Como existe número ímpar de pilhas, será necessário considerar uma pilha isolada. Pode-se fazer , por exemplo, 3 comparações, uma pilha isolada e duas comparações

23

Desenvolvimento do exemplo

24

Situação Inicial

25

Evolução da Intercalação (1)

Situação após a exclusão do registro de chave 2

26

Evolução da Intercalação (2)

Situação após a exclusão do registro de chave 6

27

Evolução da Intercalação (3)

Situação após a exclusão do registro de chave 10

28

Evolução da Intercalação (4)

Situação após a exclusão do registro de chave 13

29

Evolução da Intercalação (5)

Situação após a exclusão do registro de chave 15

30

Evolução da Intercalação (6)

Situação após a exclusão do registro de chave 20

31

Evolução da Intercalação (7)

Situação após a exclusão do registro de chave 31

32

Evolução da Intercalação (8)

Situação após a exclusão do registro de chave 37