-PROLOG E BANCO DE DADOS
Vamos discutir métodos para melhorar o uso de uma base de dados num programa para aumentar eficiência e velocidade. Algumas dessas melhorias precisam ser feitas pelo próprio sistema Prolog. Outras podem ser feitas pelas aplicações de uso dos métodos de armazenamento e acesso .
Como uma aplicação se torna mais complexa, isso requer uma grande base de dados. Então, uma maneira óbvia de aumentar o poder de Prolog é aumentar ao máximo o tamanho do banco de dados. Quando escolhemos qual sistema Prolog usar, nós checamos se o banco de dados é grande o suficiente para nossas necessidades.
Um tipo de design de banco de dados, chamado de "virtual database", permite que a base de dados vá para o disco quando a memória está cheia. Outro chamdo "worlds", permite que a base de dados seja particionada em áreas separadas, cada qual pode ter no máximo o tamanho do banco de dados. Worlds precisam ser fornecidos pelo sistema Prolog.
Se o tempo para procurar um termo entre vinte e cinco é insignificante, a procura entre centenas de termos pode diminuir a perfomance. Quando você tem grandes bancos de dados,velocidade de acesso da informação se torna um item importante. Você pode usar métodos alternativos de busca e armazenamento para aumentar a perfomance do programa. Esses métodos como tabelas hash, árvores binárias e balanceadas fazem você acessar informação no banco de dados mais eficientemente.
MODELOS DE BANCO DE DADOS
As primeiras bases de dados em Prolog estão localizadas na memória. O tamanho da base de dados foi delimitada pelo tamanho da memória. Em grandes máquinas, onde há uma grande quantidade de memória , esse modelo é adequado. Quando Prolog migrou para pequenas máquinas, o tamanho da memória foi insuficiente. Foi necessário desenvolver outros modelos em que grandes bancos de dados pudessem ser manuseados. Um desses modelos é o "virtual database".
No "virtual data base", o espaço em disco suplementa a memória. Os termos em Prolog são armazenados em seções , chamadas páginas. Quando páginas em memórias se tornam cheias, Prolog troca páginas com o disco. Quando a informação é necessitada da página do disco, Prolog troca uma página da memória para o disco, então com isso pode-se trocar a página do disco para a memória. Termos com a mesma chave são armazenados na mesma página, se possível, para minimizar as trocas que ocorrem.
Num sistema de "virtual database", o tamanho do banco de dados é limitado pela quantidade de armazenamento em disco na máquina. Todo gerenciamento da memória virtual pode ser realizado pelo sistema Prolog , sem intervenção do programa ou do programador.
MÚLTIPLOS "WORLDS" E ESCOPO
O escopo de um objeto descreve duas características. Primeiro, define quando armazenamento é alocado e desalocado para o objeto. Segundo, define quais porções de programa podem referir ao objeto. O escopo pode ser global e local e é um conceito mais comum nas linguagens de programação convencionais que em Prolog. Por exemplo,na seguinte função em C, o inteiro i é local para a função que o define:
funct ()
{
int i ;
}
Nenhuma outra função pode referenciar o mesmo inteiro I a não ser que seu valor seja passado para a função como argumento.
Escopo permite manter a informação escondida das outras partes do programa. Nem todas as funções precisam ou deveriam conhecer todos os objetos de dados no programa. Escopo também permite o programa fazer bom uso dos recursos do sistema porque isso pode desalocar um objeto quando ele é não mais necessário ao programa.
De acordo com essas definições de objetos locais e globais, todos termos em banco de dados Prolog são globais porque eles podem ser acessados por todas as partes do programa. Todos os objetos que são definidos dentro de uma regra , mas não armazenados, são locais. Isso inclui variáveis e instanciações de variáveis que ocorrem no tempo de execução somente. Eles todos desaparecem quando a regra termina.
Ë fácil fazer um objeto global simplesmente o adicionando no banco de dados, não é tão fácil fazer um objeto que reside num banco de dados local. Contudo, uma extensão de Prolog conhecida como "Worlds"faz isso possível.
Um "World" é uma porção do banco de dados que é exclusiva de alguma outra porção do banco de dados. Termos armazenados no World são locais para esse world. Suponha que você queira ter duas definições de um predicado com o mesmo nome, mas comportando-se diferentemente em diferentes partes do programa. Você definiria dois worlds, cada um contendo sua própria definição do predicado.
A figura mostra dois worlds contendo diferentes definições do predicado chamado hello. Quando você está no world1, o predicado hello escreve a mensagem "hello world1". Quando você está no world2, o predicado escreve a mensagem "hello world2". O escopo de hello é o world em que é definido.Nenhuma versão do predicado é conhecida para o outro world.
Nem todas informações deveriam ser locais.Todas as partes do programa precisam acessar as definições de operador padrão, por exemplo.Um world default armazena todas as informações globais , worlds adicionais armazenam informações locais.
Worlds foram originados para criar redes de dados hierárquicos. Dividindo informação entre o world global e os worlds locais permite você construir a hierarquia. Imagine uma aplicação que é particionada em world1 até world4 e o world default . Cada world pode acessar os termos em suas bases de dados locais e no world default. O relacionamento entre o world default e os worlds locais pode ser representado pela árvore hierárquica:
World default
World1 World2 World3 World
Worlds permitem você construir aplicações que tem mais espaço que aplicações construídas com base de dados não particionadas. Cada world é uma base de dados separada. Assim, a quantia de espaço da base de dados que é avaliada para um programa é um múltiplo do número de worlds. Em particular, Prolog precisa fornecer predicados para criar ou apagar worlds e para salvar e restaurar os índices daqueles worlds.
A BASE DE DADOS SEQUENCIAL
Por definição, a base de dados Prolog armazena e acessa termos sequencialmente. Termos com o mesmo nome e número de argumentos são armazenados na ordem em que sÃo adicionados. Prolog também acessa termos sequencialmente. A unificação ocorre na mesma ordem em que termos aparecem no banco de dados .
Armazenamento e busca sequencial não é somente adequado para regras de Prolog, é essencial para resolver muitos problemas de programação. Regras frequentemente tomam vantagem na base de dados sequencial na ordem de executar apropriadamente. Porque regras são usualmente feitas de poucas cláusulas, o acesso sequencial não afeta a velocidade do programa. Por exemplo, dado o conjunto de números de 1 a 100, você pode gravá-los no banco de dados sequencialmente como:
recordz(num,1,_),
recordz(num,2,_),
.
.
.
recordz(num,100,_).
Prolog precisará acessar o banco de dados 100 vezes para encontrar o último número armazenado.
TABELAS HASH
Tabelas Hash fornecem um método par aumentar a velocidade de acesso no banco de dados. Uma tabela Hash armazena informações em grupos, chamados "buckets". A tabela Hash provém rápido acesso a um particular "bucket"dentro da mesma. Uma vez encontrado o "bucket"correto, a procura pelo objeto específico é feita sequencialmente. Por primeiro localizar um subconjunto de objetos na tabela, você reduz a quantia de busca que precisa ser feita.
Os números de 1 a 100 pode usar um simples esquema porque qualquer número dividido por 10 retorna um resto entre 0 e 9. Três métodos para lidar com tabelas Hash estarão presentes aqui baseados nesse sistema Hash.
PROGRAMA HASH "NAÏVE"
No programa Hash "naïve", a tabela hash é feita de 10 "buckets", numerados de 0 a 9. Esse exemplo de Hash irá armazenar os números na tabela Hash diretamente, como mostrado:
0 [10,20,...,100]
1 [1,11,...,91]
2 [2,12,...,92]
3 [3,13,...,93]
4 .
5 .
6 .
7
8
9 [9,19,...,99]
Essa tabela hash está definida como uma estrutura com dez argumentos, um para cada "bucket". Você pode facilmente localizar um "bucket específico usando um predicado chamado arg(). O predicado arg() localiza um argumento na estrutura onde argumentos são numerados do maior até zero. Por exemplo, o "goal" arg()(1,capital(ma,boston),X) determina que boston é argumento 1 da estrutura capital(ma,boston). Arg() pode localizar um bucket diretamente sem fazer busca repetidas no banco de dados.
Inicialmente, a tabela Hash contém dez listas vazias, definidas pelo predicado make_hash :
make_nhash:-
recorda(nhash,nhash([ ],[ ],[ ],[ ],[ ],[ ],[ ],[ ],[ ],[ ],),_).
Para adicionar um número na tabela Hash, o programa executa esses passos:
* Encontrar qual bucket o número pertence retornando o resto do nímero dividido por 10.
* Localizar a tabela Hash no banco de dados.
* Pegar o bucket correto na tabela, usando o predicado arg().
* Anexar o novo número no bucket.
* Reconstruir a nova tabela Hash com a mudança.
* Substituir a velha tabela pela nova.
Esses passos são feitos pelo predicado nhash:
nhash(H1):-
X is H1 mod 10,
recorded(nhash, OldHash,Ref),
arg()(X,OldHash,Y),
append(Y,[H1],NewY),
reconstruct(OldHash,NewHash,X,NewY),
replace(Ref,NewHash).
A tabela Hash "naïve" pode ser um método eficiente de armazenamento, mas é ineficiente no sentido de se reconstruir a tabela Hash cada vez que um número for adicionado.
O predicado reconstruct usa um predicado chamado functor para criar uma nova estrutura com o mesmo functor e número de argumentos que estão presentes na tabela Hash. Dada uma estrutura, functor retorna o functor da estrutura e o número de argumentos.Dado um functor e número de argumentos, ele retorna uma estrutura com aquele functor e o correto número de variáveis não instanciadas. O predicado reconstruct cria essa nova estrutura e passa a estrutura para um predicado chamado do_reconstruct.
Reconstruct(OldHash, NewHash,X,NewY):-
functor(OldHash,Func,N),functor(NewHash,Func,N),
do_reconstruct(OldHash,NewHash,X,NewY,0).
A nova estrutura é usada pelo predicado do_reconstruct, que vai através de cada argumento na tabela Hash, instanciando cada argumento com seu antigo valor e instanciando o argumento mudado com seu novo valor. A primeira cláusula do_reconstruct lida com o argumento modificado, a segunda com argumentos que não mudaram. A terceira cláusula lida com a condição de fim - quando não há mais argumentos para a estrutura. Por proceder argumento por argumento, reconstruir a tabela Hash é um processo demorado.
do_reconstruct(OldHash,NewHash,X,NewY,X) :-
X = Arg,
arg()(X,NewHash,NewY) , NewArg is Arg + 1,
do_reconstruct(OldHash, NewHash, X,NewY, NewArg).
do_reconstruct(OldHash,NewHash,X,NewY,Arg) :-
arg()(Arg,OldHash, Val),
arg()(Arg,NewHash,Val),
NewArg is Arg + 1,
do_reconstruct(OldHash,NewHash,X,NewY,NewArg).
do_reconstruct(_ ,_ ,_ ,_ ,_ ).
TABELA HASH USANDO REFS
Na próxima versão do programa Hash, a tabela Hash não armazena os números e sim ponteiros para listas de números, como na figura:
0 [10,20,...100]
1 [1,11,...91]
2 [2,12,...92]
3 .
4 .
5 .
6
7
8
9 [9,19,...99]
O predicado make_hash constroi essa tabela Hash gravando dez listas vazias no banco de dados e usando números de referência do banco de dados retornados pelo predicado recordz como argumento para a estrutura da tabela Hash:
make_rhash :-
recordz(lists, [ ],R0),
recordz(lists, [ ],R1),
recordz(lists, [ ],R2),
recordz(lists, [ ],R3),
recordz(lists, [ ],R4),
recordz(lists, [ ],R5),
recordz(lists, [ ],R6),
recordz(lists, [ ],R7),
recordz(lists, [ ],R8),
recordz(lists, [ ],R9),
recorda(rhash,rhash(R0,R1,R2,R3,R4,R5,R6,R7,R8,R9),_).
Adicionando um novo número nessa tabela Hash requer esses passos:
* Determinar qual bucket aponta para a apropriada lista para o número.
* Buscar a tabela Hash no banco de dados.
* Localizar o número de referência para a lista.
* Juntar o número à lista.
* Substituir a lista antiga pela nova.
* Reconstruir a tabela Hash que então aponta para a nova lista ao invés da antiga.
* Substituir a tabela Hash.
Apesar da tabela Hash poder simplesmente ser substituida, ela precisa ser reconstruida cada vez que um número é adicionado.
rhash(Num) :-
X is Num mod 10,
recorded(rhash, HashTable,Ref),
arg()(X,HashTable,LRef),
recorded(lists,List,LRef),
append(List,[Num],NewList),
replace(LRef,NewList),
reconstruct(HashTable,NewTable,X,NewRef),
replace(Ref,NewTable).
UMA TABELA HASH USANDO LISTAS ENCADEADAS
O último e melhor dos métodos discutidos cria uma lista encadeada de números para cada bucket. Uma lista encadeada não é para ser confundida com o tipo de dado "lista" em Prolog. Objetos em uma lista encadeada não são fisicamente armazenados juntos no banco de dados. Cada objeto é uma entidade separada armazenando tanto o número e o ponteiro para o próximo número na lista, como na figura:
0 Ref0 (10, ) (20, ) ... (null,0)
1 Ref1
2 Ref2
3 Ref3
4 Ref4
5 Ref5
6 Ref6
7 Ref7
8 Ref8
9 Ref9
Cada entrada na lista encadeada é um par de valores dados o número adicionado e um ponteiro para o próximo número da lista. Essa versão coloca a nova entrada no início da lista, diferentemente das anteriores. Então, quando um novo número é adicionado, somente a primeira entrada na lista e a referência para ela na tabela Hash precisam ser mudadas.O resto da lista permanece intacta. O final da lista contém a entrada(null,0). Para criar essa tabela Hash, você precisa criar a entrada inicial na lista encadeada, retornar a referência para essa entrada e armazenar os números de referência na tabela Hash.
make_hash :-
recordz(chain, (null,0), R0),
recordz(chain, (null,0), R1),
recordz(chain, (null,0), R2),
recordz(chain, (null,0), R3),
recordz(chain, (null,0), R4),
recordz(chain, (null,0), R5),
recordz(chain, (null,0), R6),
recordz(chain, (null,0), R7),
recordz(chain, (null,0), R8),
recordz(chain, (null,0), R9),
recorda(hash,hash(R0,R1,R2,R3,R4,R5,R6,R7,R8,R9),_).
Adicionar um número na lista encadeada é mais simples que nas versões anteriores de programa Hash:
* Encontrar o bucket o qual o número pertence.
* Recuperar a tabela Hash no banco de dados.
* Localizar o número de referência para a primeira entrada da lista.
* Pegar a primeira entrada, usando esse número de referência como um
argumento para o predicado instance.
* Copiar essa entrada para o novo local.
* Substituir a antiga entrada pela nova, que contém o novo número e um
ponteiro para a antiga entrada.
O predicado hash definido aqui faz esses passos:
hash(Num) :-
X is Num mod 10,
recorded(hash,Htable,_ ),
arg()(X,Htable,Ref),
recorded(chain, OldPr,Ref),
recordz(chain,OldPr,Ref1),
replace(Ref,(Num,Ref1)).
Você pode localizar um número com o predicado hash_get, definido abaixo. Ele encontra o bucket correto na tabela hash e então busca a lista encadeada para o número correto:
hash_get(Num) :-
X is Num mod 10,
recorded(hash,Table,_),
arg()(X,Table,Ref),
recorded(chain,NumPr,Ref),
walk(NumPr,Num).
walk((Num,_ ),Num).
walk((_ , Ref),Num) :-
instance(Ref,NewPr),
walk(NewPr,Num).
Esses mecanismos de Hash podem encontrar um número no banco de dados com menos acessos que no método sequencial. Usando o acesso sequencial, Prolog precisa fazer 100 acesssos para encontrar o último número numa série de 100 números. Uma tabela hash acessa o banco de dados no máximo 11 vezes, uma para buscar a tabela hash e 10 vezes para encontrar o último elemento na lista encadeada.
Tabelas hash são boas para aumentar a velocidade de acesso para informação no banco de dados. Elas, contudo,não armazenam informação no que seria considerado uma ordem hierárquica.Se a informação precisar ser ordenada de alguma maneira, precisam ser usadas árvores ao invés de tabelas hash.
ÁRVORES BINÁRIAS
Árvores binárias armazenam informação numa ordem hierárquica ,embora não necessariamente ordenadamente como alfabeticamente ou numericamente. Devido a informação estar numa hierarquia, você pode utilizar estratégias não sequenciais, que são mais eficientes que as buscas sequenciais de Prolog ou as tabelas hash.
Árvores binárias são feitas de nós e arestas. Um nó pega a informação para a localização corrente na árvore. O primeiro nó numa árvore binária é chamado de nó raiz. Arestas apontam para os nós que são subordinados ao nó corrente.
Numa árvore binária, cada nó tem exatamente duas arestas. Nós contém quatro pedaços de informação:
1. Os índices do nó.
2. A identificação do nó, que é usada com um ponteiro do nó predecessor.
3. Um ponteiro, ou aresta ,para o nó esquerdo que é sucessor para esse nó.
4. Um ponteiro para o nó direito, que também é sucessor para esse nó.
Suponha que um nó pegue um objeto chamado cheese e o resto dos nós um objeto chamado nut. Podemos representar então uma árvore com fatos Prolog. Cada nó é escrito como uma estrutura contendo quatro argumentos. O primeiro é o conteúdo do nó(ou nut ou cheese), o segundo é número corrente do nó, o terceiro é o número do nó esquerdo sucessor e o quarto é o número do nó direito sucessor. O átomo null indica que o nó não tem sucessores.
node (nut,1,2,3).
node(cheese,3,6,7).
node(nut,2,4,5).
node(nut,4,null,nulll).
node(nut,5,8,9).
node(nut,6,null,null).
node(nut,7,10,11).
node(nut,8,null,null).
node(nut,9,null,null).
node(nut,10,null,null).
node(nut,11,null,null).
BUSCA "DEPTH-FIRST"
A busca "depth-first" procura todas arestas da árvore da esquerda para a direita e de baixo para cima. Já estamos familiar com a busca depth-first dentro do contexto de como Prolog solouciona uma regra. Suponha A,B,C,D e E são goals em Prolog, então A está definido em termos de B e C, B está definido em termos de D, e C está definido em termos de E, como:
A :- B,C.
B :- D.
C :- E.
Para provar A, Prolog precisa provar goals B e C ,e para provar B e C precisa provar D e E. O relacionamento entre os goals pode ser ilustrado na árvore. Os goals que tem profundidade maior na árvore precisam ser provados primeiro.Além disso são provados da esquerda para a direita.
Para aplicar essa estratégia de busca no banco de dados, precisamos escrever rotinas para buscar na árvore em depth-first.
Procura em árvore é um procedimento recursivo. A primeira cláusula declara que "Se cheese é encontrado no nó corrente, então esse nó é a resposta. Essa cláusula determina a condição de fim para a regra.
findcheese(node(cheese,Answer,_, _ ),Answer).
Se cheese não é encontrado no nó corrente, então a próxima cláusula checa se o sucessor da esquerda é cheese.Chama findcheese com esse nó como o novo nó corrente. Dessa maneira, todos nós esquerdos sÃo examinados até o fim de um ramo.
findcheese(node(_, _, L,_), Answer) :-
node(A,L,C,D),
findcheese(node(A,L,C,D),Answer).
Se cheese não é encontrado nos nós esquerdos, então findcheese precisa checar os nós direitos.
findcheese(node(_, _, ,_,R), Answer) :-
node(A,R,C,D),
findcheese(node(A,R ,C,D),Answer).
A regra findcheese opera dentro do programa, que define o nó inicial o qual começa a procura. A regra é escrita como:
cheese(N,Ans) :-
node(A,N,C,D), findcheese(A,N,C,D),Ans).
cheese( _ , _) :- write('Não encontrado').
Para começar a busca no nó 1, chamamos cheese como abaixo:
?- cheese(1,Ans).
BUSCA "BREADTH-FIRST"
Uma busca "breadth-first" examina todos os nós no mesmo nível da esquerda para a direita e do nó raiz para baixo. Na árvore nut/cheese, uma busca "breath-first"olha os nós na ordem em que são numerados: 1,2,e 3.
Duas vantagens da busca breadth-first em relação à depth-first:
* Quando o objeto de procura no nó direito perto do topo,breadth-first localiza mais rapidamente.
* Quando infinitas estruturas estão envolvidas,breadth-fisrt é garantida encontrar uma solução se existir. Depth-first pode nunca encontrar um objeto em uma estrutura infinita.
Em Prolog, a regra para procura breadth-first descreve o relacionamento entre nós em termos de nós filhos e descendentes. A regra é escrita como:
child(node(_, _, L, _), node(A,L,C,D)) :-
node(A,L,C,D).
child(node(_, _, _, R), node(A,R,C,D)) :-
node(A,R,C,D).
descendant(node1, node2) :- child (node1,node2).
descendant(node1, node2) :-
descendant(node1,node3),
child(node3,node2).
Essas regras operam dentro de uma regra findcheese que afirma que "O cheese pode ser encontrado num nó descendente que tem cheese.
Findcheese(node,N) :-
descendant(node(nut,_ ,node,null), node(cheese,N,_ ,_)).
Podemos chamar esse programa pela cláusula:
?- findcheese(1,N).
ESTRATÉGIAS DE BUSCA USANDO LISTAS
Tanto estratégias de busca depth-first e breadth-first podem ser implementadas com listas que controlam a ordem em que os nós são buscados. Esse é o método mais comumente usado em programas Lisp. Como o programa busca um nó,ele adiciona os nós sucessores direito e esquerdo na lista de procura. Depth-first e breadth-first diferem somente em se os sucessores são localizados no início ou no fim da lista de procura.
Para implementar a estratégia de busca usando listas, precisamos ainda escrever uma cláusula para aceitar o número do nó inicial. Essa cláusula então passa o número como uma lista para um predicado chamado get_node.
find(node,N) :- get_node([Node],N).
Quando get_node localizar a lista vazia, significa que o cheese não foi encontrado e get_node falha. Um cut/fail lida com essa condição de exceção.
get_node([ ] ,_ ) :- !,fail.
A segunda cláusula get_node retorna o nó do banco de dados e passa o nó para o predicado chamado search.
get_node([H|T],N) :-
node(X,H,L,R),
search(node(X,H,L,R),T,N).
Há três cláusulas de procura. A primeira sucede quando cheese é encontrado no nó corrente. A segunda sucede quando o nó não tem sucessores. Essa cláusula simplesmente continua a busca chamando get_node com a calda da lista. A terceira cláusula sucede quando o nó tem sucessores. Ela adiciona os sucessores para a lista de procura.
search(node(cheese,H,_,_),_,H).
search(node(_, H, null,null),T,N) :-
get_node(T,N).
search(node(_,H,L,R),T,N) :-
append([L,R],T,A),
get_node(A,N).
A versão de busca mostrada define uma estratégia de busca depth-first. Para definir uma breadth-first, simplesmente muda-se a ordem dos argumentos para append:
append(T,[L,R],A).
ÁRVORES BALANCEADAS
Outro tipo de árvore, chamada de árvore balanceada também pode ser usada. Uma árvore é balanceada se todos seus ramos se estendem no mesmo nível. A árvore nut/cheese não é balanceada porque nós 5 e 7 estende-se um nível com mais profundidade que os nós 4 e 6..
Informação em uma árvore balanceada pode ser acessada mais diretamente. Criar e manter uma árvore balanceada requer esforço. Adicionar uma nova entrada pode afetar todas as partes da árvore. Algumas vezes uma nova raiz precisa ser criada.
Árvores balanceadas são feitas de nós, arestas e níveis. O mesmo número de arestas estendem de todo nó, apontando para os nós sucessores. Os nós no mais baixo nível apontam para os níveis que tem a informação. Para manter uma distribuição de informação através da árvore, cada folha pode ter somente um limitado número de objetos.
Cada nó também contém uma "chave". A chave ajuda determinar qual aresta seguir quando procuramos por um objeto. Ela pode ser de dois valores: ou o máximo valor contido nos ramos esquerdos desse nó, ou o mínimo valor contido nos ramos direitos desse nó.
A figura mostra uma árvore que armazena informação na ordem alfabética. O nó raiz contém a chave n, a mais baixa letra armazenada no lado direito e aponta para os nós imediatamente abaixo dele.
Os nós em cada nível contém dois ramos cada. Essa árvore é também uma árvore binária. Contudo não necessariamente uma árvore balanceada é binária.
No nível mais baixo da árvore os nós contém ponteiros para outros nós, que contém os dados. Por exemplo, o nó marcado por d contém ponteiros para as folhas contendo a,b,c e d,e,f,g. Nessa árvore, cada folha pode ter no máximo quatro objetos. Os objetos armazenados tem duas partes: a letra que se refere ao objeto (a chave) e a palavra que começa com essa letra.
Dentro do banco de dados Prolog, a árvore é representada como uma coleção de estruturas de nós e folhas. As estruturas da folha tem os objetos apontados pelos nós. As estruturas do nó armazena as chaves e os ponteiros para os nós sucessores. Nesse exemplo, uma chave é o mais baixo valor contido no ramo direito para aquele nó; os ponteiros são os números de referência retornados por recordz ou recorda. Os números de refererência dos nós de nível mais baixo são usados como argumentos para as estruturas de nó nos níveis mais altos. Então a árvore é construída de baixo para cima ao invés de cima para baixo.
Podemos ver como uma árvore é armazenada num banco de dados olhando as estruturas de todos os nós e folhas com o predicado recorded.
?- recorded(node,X,_).
X = node(n,~0100403E~01003C3E) ->;
.
.
.
X = node(d,~0100743E~0100703E) ->
(mostra todos os nós)
?- recorded(leaf,X,_).
X = leaf(a:apple, b:boy, c:cart,nil) ->;
.
.
.
X = leaf(w: wax,x:xray, y: yes, z: zoom) ->
Para localizar uma palavra, a primeira letra da palavra (a chave) é comparada com o valor contido no nó.Se a chave é menor que o valor da chave do nó, a procura é feita no lado esquerdo, se for maior ou igual, no lado direito. Essa estratégia de busca sempre encontra o menor caminho para o dado.
O predicado find, abaixo, inicializa a procura localizando o nó raiz e passando aquela estrutura para um predicado que seguirá o caminho para a folha.
find(X,Term) :-
recorded(node,Root,_),
btree(Root,X,Term).
O predicado btree determina que caminho seguir comparando recursivamente a chave que você está procurando com a chave do nó corrente. Quando chegamos no fim do ramo, a folha que contém a palavra foi encontrada. A palavra pode estar em uma de quatro posições dentro da folha.
O predicado btree é definido:
btree(node(Nkey,Left,_),Key,Term) :-
Key @
Para localizar a palavra que começa com a letra r, por exemplo, podemos executar assim:
?- find(r,X).
O predicado find localiza o nó raiz, que tem a chave n, e passa o nó raiz para o predicado btree. Btree compara a letra r com a chave n. Como r é maior que n, btree é chamado para executar o lado direito do nó raiz. Esse nó contem a chave t. A letra r é menor que t, então btree segue o lado esquerdo agora e encontrga o nó q. Quando faz a comparação vai para o lado direito e chega na folha. O termo é encontrado na segunda posição dentro da estrutura:
leaf(q:quiz,r:run,s:seen,null)
Então o predicado find sucede com a variável X instanciada com run.
Uma árvore balanceada é desejável por uma série de rasões. Primeiro, ela é capaz de buscar mais rápido as informações. Não gasta tempo seguindo um caminho que não irá para a folha correta. Segundo, ela mantem os dados ordenados.
Para buscar todos os dados na ordem alfabética, você pode chamar o predicado find assim:
?-find(X,Y).
X = a
Y = apple ->;
X = b
Y=boy ->
.
.
.
SUMÁRIO
A maioria da flexibilidade e poder de Prolog deriva do seu banco de dados. O poder de Prolog pode ser aumentado aplicando novas técnicas para o design e o gerenciamento do banco de dados.
O banco de dados virtual permite você construir grandes bases de dados Prolog em pequenos computadores. O tamanho do banco de dados virtual compara favoravelmente com os bancos de dados contruidos em grandes computadores.
Worlds são outra maneira de aumentar o tamanho do banco de dados que um sistema Prolog pode manusear. Worlds permitem você particionar seu programa de banco de dados. Como cada world é um banco de dados separado, você pode construir aplicações feitas de muitos grandes pedaços. Contudo, o programa precisa definir como particionar o banco de dados dentro dessas entidades separadas.
Tabelas Hash e árvores podem aumentar a velocidade em que Prolog localiza um termo no banco de dados. Usando um conjunto existente de predicados Prolog, podemos construir nosso próprio método de acesso para aplicações específicas. Não há como determinar qual é o melhor método de acesso e armazenamento para um particular tipo de aplicação. Contudo , se você está escrevendo um sistema sofisticado com uma grande quantidade de informação, você usaria um método de armazenamento e acesso mais sofisticado, como árvores balanceadas. Se você está escrevenmdo um sistema simples, pode usar o método sequencial de Prolog, por exemplo.