ads:
Leandro Rincon Costa
Roteamento de consultas em bancos de
dados peer-to-peer utilizando colˆonias de
formigas e ontologias
S˜ao Jos´e do Rio Preto - SP, Brasil
28 de Agosto de 2009
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
Leandro Rincon Costa
Roteamento de consultas em bancos de
dados peer-to-peer utilizando colˆonias de
formigas e ontologias
Disserta¸c˜ao apresentada para obten¸c˜ao do t´ı-
tulo de Mestre em Ciˆencia da Computa¸c˜ao,
´area de Banco de Dados junto ao Programa
de P´os-Gradua¸c˜ao em Ciˆencia da Computa-
¸c˜ao do Instituto de Biociˆencias, Letras e Ci-
ˆencias Exatas da Universidade Estadual Pau-
lista ”J´ulio de Mesquita Filho”, Campus de
S˜ao Jos´e do Rio Preto.
Orientador:
Prof. Dr. Carlos Roberto Valˆencio
Programa de P
´
os-Gradua¸c
˜
ao em Ci
ˆ
encia da Computa¸c
˜
ao
Departamento de Ci
ˆ
encias de Computa¸c
˜
ao e Estat
´
ıstica
Universidade Estadual Paulista ”J
´
ulio de Mesquita Filho”
S˜ao Jos´e do Rio Preto - SP, Brasil
28 de Agosto de 2009
ads:
Leandro Rincon Costa
Roteamento de consultas em bancos de
dados peer-to-peer utilizando colˆonias de
formigas e ontologias
Disserta¸c˜ao apresentada para obten¸c˜ao do t´ı-
tulo de Mestre em Ciˆencia da Computa¸c˜ao,
´area de Banco de Dados junto ao Programa
de P´os-Gradua¸c˜ao em Ciˆencia da Computa-
¸c˜ao do Instituto de Biociˆencias, Letras e Ci-
ˆencias Exatas da Universidade Estadual Pau-
lista ”J´ulio de Mesquita Filho”, Campus de
S˜ao Jos´e do Rio Preto.
BANCA EXAMINADORA
Prof. Dr. Carlos Roberto Valˆencio
UNESP - S˜ao Jos´e do Rio Preto
Orientador
Prof. Dr. Pedro Luiz Pizzigatti Corrˆea
Escola Polit´ecnica da Universidade de S˜ao
Paulo
Profa. Dra. Rog´eria Cristiane Grat˜ao de
Souza
UNESP - S˜ao Jos´e do Rio Preto
S˜ao Jos´e do Rio Preto, 28 de Agosto de 2009
”Quanto maior s˜ao as dificuldades a vencer, maior ser´a a satisfa¸c˜ao.”
C´ıcero
Dedico este trabalho ao meu pai S´ergio, minha m˜ae Angela e meus irm˜aos Eduardo e
Ana.
Agradecimentos
Antes de tudo agrade¸co a Deus pela sa´ude e for¸ca para superar os desafios em meu
caminho.
Em especial, agrade¸co muito aos meus pais, S´ergio e Angela, pelo carinho, amor e
apoio imprescind´ıveis para chegar at´e aqui. Por todos os momentos de compreens˜ao, os
conselhos e todo o apoio para que eu pudesse alcan¸car esta conquista. Sem o amor deles,
nada disso seria poss´ıvel.
Aos meus irm˜aos, Ana e Eduardo, pelos momentos de alegria, pela compreens˜ao em
todos os momentos, bons e ruins, e as intermin´aveis horas de silˆencio. Aos meus av´os,
tios e primos, que sempre estiveram torcendo por mim e me apoiando de alguma forma.
Ao meu orientador Valˆencio, por todo o tempo e apoio, sempre procurando me direci-
onar a caminho do sucesso.
`
A todos os professores que participaram do meu crescimento
pessoal e profissional durante todos esses anos. Aos professores Pedro e Rog´eria que muito
gentilmente aceitaram avaliar e dar sua importante contribui¸c˜ao para este trabalho.
Aos meus amigos Rafael e Fernando e minha amiga Graziela por toda a for¸ca e torcida.
Aos amigos e colegas que estiveram comigo durante todos esses anos, pelo companhei-
rismo em momentos de alegria e de preocupa¸c˜ao. Em especial, tentando n˜ao esquecer de
ningu´em: Andr´e, Geraldo, Jorge, Willian Lima, Toni Jardini, Evandro e todos os ”Amigos
do Chuck”. Aos colegas do Grupo de Banco de Dados que sempre acompanharam meu
trabalho e contribu´ıram de alguma forma.
`
A todos aqueles que, de alguma forma, contribu´ıram para esta conquista.
Resumo
Sistemas baseados em redes peer-to-peer come¸caram a se popularizar nos anos 90 e,
desde ent˜ao, grandes avan¸cos e novas aplica¸c˜oes tˆem sido desenvolvidas aproveitando as
caracter´ısticas deste tipo de rede de computadores. Inicialmente, tais redes eram utili-
zadas apenas em aplica¸c˜oes simples como o compartilhamento de arquivos, hoje, por´em,
encontram-se em aplica¸c˜oes com grau de complexidade cada vez maior. Dentre estes siste-
mas mais recentes, destaca-se o compartilhamento de informa¸c˜oes armazenadas em ban-
cos de dados, um segmento em franco desenvolvimento. Em bancos de dados peer-to-peer,
cria-se uma base de conhecimento rica e amplamente distribu´ıda, baseada no compartilha-
mento de informa¸c˜oes semanticamente relacionadas, por´em sintaticamente heterogˆeneas.
Um dos desafios desta categoria de aplica¸c˜oes ´e garantir uma forma eficiente para
a busca de informa¸c˜oes sem comprometer a autonomia de cada n´o e a flexibilidade da
rede. Neste trabalho explora-se este desafio e apresenta-se uma proposta de suporte `as
buscas por meio da otimiza¸c˜ao dos caminhos, buscando reduzir o n´umero de mensagens
enviadas na rede sem afetar significativamente o n´umero de respostas obtidas por consulta.
Para tal tarefa prop˜oe-se uma estrat´egia baseada em conceitos do algoritmo de colˆonia
de formigas e classifica¸c˜ao das informa¸c˜oes utilizando ontologias. Com isso foi poss´ıvel
adicionar o suporte semˆantico como facilidade na execu¸c˜ao do processo de busca em bancos
de dados peer-to-peer, al´em de reduzir o tr´afego de mensagens e permitir inclusive que
mais resultados sejam alcan¸cados sem comprometer o desempenho da rede.
Abstract
In the 90s, peer-to-peer systems became more popular and, since then, major advances
and new applications have been developed based on the features of this kind of computer
network. Initially they were used only in simple applications as file sharing, but now they
have been implemented in increasingly more complex applications. Among these novel
systems, it pointed out the database information sharing, which is developing rapidly. In
peer-to-peer database, a very rich and widely distributed knowledge base is created, based
on the sharing of semantically related but syntactically heterogeneous information.
One of the challenges of such an application is to ensure an efficient way to search for
information with no jeopardy either to the individual nodes autonomy or to the network
flexibility. The work herein explores this challenge aiming at a proposal to support the
searches through paths optimization, looking for reducing the number of messages sent in
network without affecting the number of each query’s answers. To do this work, it proposes
a strategy based both on ant colony algorithm concepts and information classification by
ontologies. This way, it has been possible to add the semantic support in order to ease the
search process in peer-to-peer database, while reducing the message traffic and allowing
even to reach more results without compromising the network performance.
Sum´ario
Lista de Figuras
Lista de Tabelas
Lista de Abreviaturas
1 Introdu¸c˜ao 1
1.1 Considera¸c˜oes Iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Motiva¸c˜ao e escopo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 Materiais e M´etodos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.5 Organiza¸c˜ao dos Cap´ıtulos . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Fundamenta¸c˜ao Te´orica 5
2.1 Gerenciamento de Dados em Peer-to-Peer . . . . . . . . . . . . . . . . . 5
2.1.1 Redes Peer-to-Peer . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.2 Sistemas de gerenciamento de dados peer-to-peer . . . . . . . . . 10
2.1.3 Mapeamento entre esquemas . . . . . . . . . . . . . . . . . . . . . 14
2.1.4 Processamento de consultas . . . . . . . . . . . . . . . . . . . . . 17
2.1.5 Consistˆencia dos dados . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1.6 Localiza¸c˜ao dos dados . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.7 Bancos de dados peer-to-peer existentes . . . . . . . . . . . . . . . 19
2.2 Estrat´egias de busca em redes peer-to-peer . . . . . . . . . . . . . . . . . 21
2.2.1 Tabela Hash Distribu´ıda - DHT . . . . . . . . . . . . . . . . . . . 22
2.2.2 Rede Semˆantica Overlay - SON . . . . . . . . . . . . . . . . . . . 23
2.2.3 Inunda¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.4 Colˆonia de formigas em peer-to-peer . . . . . . . . . . . . . . . . . 25
2.3 Ontologias na Computa¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4 Considera¸c˜oes Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3 Banco de dados peer-to-peer e a estrat´egia de consulta 31
3.1 Considera¸c˜oes Iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 Semˆantica dos dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3 Material e M´etodo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3.1 Interface com o usu´ario . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3.2 Gerenciador de acesso aos dados . . . . . . . . . . . . . . . . . . . 35
3.3.3 Gerenciador de Ontologias . . . . . . . . . . . . . . . . . . . . . . 36
3.3.4 Interpretador SQL / Ontologias . . . . . . . . . . . . . . . . . . . 37
3.3.5 Gerenciador Peer-to-Peer . . . . . . . . . . . . . . . . . . . . . . 38
3.3.6 Agentes de busca e roteamento . . . . . . . . . . . . . . . . . . . 39
3.3.7 Recebendo e encaminhando formigas exploradoras . . . . . . . . . 40
3.3.8 Busca de novos caminhos . . . . . . . . . . . . . . . . . . . . . . . 42
3.3.9 Atualiza¸c˜ao da tabela de roteamento . . . . . . . . . . . . . . . . 43
3.3.10 Processo de uma consulta . . . . . . . . . . . . . . . . . . . . . . 44
3.3.11 Exemplo de funcionamento . . . . . . . . . . . . . . . . . . . . . . 45
4 Experimentos e Avalia¸c˜ao 49
4.1 Estrutura dos experimentos . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.2 Ontologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3 An´alise de Desempenho . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.3.1 Desempenho sem tempo de vida . . . . . . . . . . . . . . . . . . . 52
4.3.2 Desempenho com tempo de vida definido . . . . . . . . . . . . . . 54
5 Conclus˜oes 61
5.1 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Referˆencias 64
Apˆendice 1 68
Lista de Figuras
1 Rede peer-to-peer pura. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Rede peer-to-peer h´ıbrida com servidor de descoberta e consulta. . . . . . 8
3 Rede peer-to-peer hier´arquica. . . . . . . . . . . . . . . . . . . . . . . . . 9
4 Representa¸c˜ao de um banco de dados P2P e a indica¸c˜ao de uma consulta. 12
5 Esquema poss´ıvel para cada n´o da rede [1]. . . . . . . . . . . . . . . . . . 13
6 Mapeamentos armazenados no n´o A. . . . . . . . . . . . . . . . . . . . . 15
7 Mapeamento transitivo entre A e F. . . . . . . . . . . . . . . . . . . . . . 17
8 Esquema de um n´o no sistema PeerDB [16]. . . . . . . . . . . . . . . . . 20
9 Exemplo de distribui¸c˜ao dos valores da fun¸c˜ao hash entre n´os [12]. . . . . 22
10 Redes semˆanticas em uma divis˜ao para o roteamento [3]. . . . . . . . . . 23
11 Inunda¸c˜ao com tempo de vida 3 [23]. . . . . . . . . . . . . . . . . . . . . 24
12 Comportamento das Formigas. . . . . . . . . . . . . . . . . . . . . . . . . 26
13 M´odulos do sistema proposto. . . . . . . . . . . . . . . . . . . . . . . . . 33
14 Configura¸c˜ao de acesso ao SGBD. . . . . . . . . . . . . . . . . . . . . . . 35
15 Interface de consulta. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
16 Alguns resultados da consulta. . . . . . . . . . . . . . . . . . . . . . . . . 36
17 Tabela de roteamento (Vizinhos x Ontologias). . . . . . . . . . . . . . . . 40
18 Caminho P1 at´e P11 com informa¸c˜oes relevantes. . . . . . . . . . . . . . 42
19 Novo n´o com bons resultados. . . . . . . . . . . . . . . . . . . . . . . . . 42
20 Desenhos representativos das formigas. . . . . . . . . . . . . . . . . . . . 45
21 Exemplo de formigas caminhando - Parte 1. . . . . . . . . . . . . . . . . 47
22 Exemplo de formigas caminhando - Parte 2. . . . . . . . . . . . . . . . . 48
23 Rede peer-to-peer com 16 n´os. . . . . . . . . . . . . . . . . . . . . . . . . 50
24 N´ıveis de feromˆonio das classes da ontologia para caminhos saindo do n´o
T3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
25 Tr´afego na rede de 16 n´os sem TTL. . . . . . . . . . . . . . . . . . . . . 53
26 N´umero m´edio de respostas por consulta na rede de 16 n´os sem TTL. . . 53
27 Tr´afego na rede de 32 n´os sem TTL. . . . . . . . . . . . . . . . . . . . . 54
28 N´umero m´edio de respostas por consulta na rede de 32 n´os sem TTL. . . 54
29 Tr´afego na rede de 16 n´os com TTL 3. . . . . . . . . . . . . . . . . . . . 55
30 N´umero m´edio de respostas por consulta na rede de 16 n´os com TTL 3. . 56
31 Tr´afego na rede de 32 n´os com TTL 5. . . . . . . . . . . . . . . . . . . . 56
32 N´umero m´edio de respostas por consulta na rede de 32 n´os com TTL 5. . 57
33 Comparativo de tr´afego na rede de 16 n´os. . . . . . . . . . . . . . . . . . 58
34 Comparativo de respostas na rede de 16 n´os. . . . . . . . . . . . . . . . . 58
35 Comparativo de tr´afego na rede de 32 n´os. . . . . . . . . . . . . . . . . . 59
36 Comparativo de respostas na rede de 32 n´os. . . . . . . . . . . . . . . . . 60
Lista de Tabelas
1 Compara¸c˜ao entre bancos de dados distribu´ıdos e peer-to-peer . . . . . . 12
2 Tabela de ontologias rote´aveis dos experimentos. . . . . . . . . . . . . . . 51
3 Classes da Ontologia da Anatomia Humana . . . . . . . . . . . . . . . . 68
3 Classes da Ontologia da Anatomia Humana . . . . . . . . . . . . . . . . 69
3 Classes da Ontologia da Anatomia Humana . . . . . . . . . . . . . . . . 70
3 Classes da Ontologia da Anatomia Humana . . . . . . . . . . . . . . . . 71
Lista de Abreviaturas
P2P Peer-to-Peer
SGBD Sistema Gerenciador de Banco de Dados
BDP2P Banco de Dados Peer-to-Peer
LAV Local-As-View
GAV Global-As-View
XML eXtensible Markup Language
DHT Distributed Hash Table - Tabela Hash Distribu´ıda
SON Semantic Overlay Network - Rede Semˆantica Overlay
TTL Time-To-Live - Tempo de Vida
ACO Ant Colony Optimization - Colˆonia de Formigas
SQL Structured Query Language
OWL Web Ontology Language
W3C World Wide Web Consortium
OIL Ontology Inference Layer
DAML DARPA Agent Markup Language
JDBC Java Database Connectivity
UNESP Universidade Estadual Paulista
FMA Foundational Model of Anatomy
1
1 Introdu¸c˜ao
1.1 Considera¸c˜oes Iniciais
A quantidade de informa¸c˜ao espalhada em diversas bases de dados ao redor do mundo
cresce em um ritmo intenso. Empresas, institui¸c˜oes, governo e particulares contribuem
para este crescimento com informa¸c˜oes dos mais diversos tipos, armazenadas em bancos de
dados sintaticamente heterogˆeneos. Ao mesmo tempo, aplica¸c˜oes desenvolvidas utilizando
redes peer-to-peer para proporcionar comunica¸c˜ao entre computadores surgem de diversas
fontes, com usos, vantagens e desvantagens variadas. Uma classe dessas aplica¸c˜oes visa
integrar bases de dados em redes peer-to-peer de modo a manter a autonomia local e buscar
o maior grau de flexibilidade poss´ıvel, criando os chamados bancos de dados peer-to-peer.
1.2 Motiva¸c˜ao e escopo
Em um sistema peer-to-peer, os n´os conectados `a rede interagem entre si compar-
tilhando recursos, servi¸cos e informa¸c˜ao. Muitos sistemas j´a foram desenvolvidos neste
dom´ınio de redes peer-to-peer, por´em a maioria trata de dados n˜ao-estruturados ou semi-
estruturados, como arquivos de m´usicas, filmes e documentos [1]. Pesquisas recentes tˆem
apontado na dire¸c˜ao do desenvolvimento de aplica¸c˜oes que levam em conta a semˆantica
associada aos dados ao permitir que informa¸c˜oes mais ricas sejam compartilhadas em tais
redes.
Neste ambiente surgem os bancos de dados peer-to-peer. Estes sistemas permitem que
os dados armazenados em bases autˆonomas e heterogˆeneas sejam compartilhados em uma
1.3 Objetivos 2
rede geograficamente distribu´ıda. Essa possibilidade de compartilhar dados entre bancos
diferentes permite vislumbrar aplica¸c˜oes integrando dados de diversas fontes, criando uma
base de conhecimento de grande porte, sem a necessidade de grandes investimentos, pois
s˜ao utilizados bancos de dados j´a existentes, bem como a infra-estrutura em funcionamento
[2].
Outro aspecto importante e que diferencia tal classe de aplica¸c˜oes dos sistemas dis-
tribu´ıdos convencionais ´e a manuten¸c˜ao da liberdade e autonomia dos usu´arios destes
sistemas. Ao permitir que os usu´arios entrem e saiam da rede no momento que mais
lhes interessa e que sejam os ´unicos respons´aveis pelos dados que decidem compartilhar,
cria-se um sistema atraente para empresas e institui¸c˜oes que podem compartilhar parte de
suas informa¸c˜oes sem ter que permanecer atrelados `a sistemas com r´ıgido controle sobre
a estrutura ou conte´udo dos bancos de dados, garantindo a seguran¸ca e privacidade das
informa¸c˜oes.
A alta flexibilidade e dinamicidade das redes peer-to-peer, bem como a falta de um
gerenciamento centralizado cria um ambiente em que torna-se complexo o processo de lo-
caliza¸c˜ao da informa¸c˜ao entre os diversos participantes da rede [3]. Algumas solu¸c˜oes tem
sido propostas e aplicadas durante os anos, cada uma com suas vantagens e desvantagens
[1], tais como solu¸c˜oes baseadas em agrupamentos, chamadas redes semˆanticas overlay,
ou solu¸c˜oes que mant´em um controle sobre a localiza¸c˜ao dos dados atrav´es da utiliza¸c˜ao
de tabelas hash distribu´ıdas. Uma solu¸c˜ao mais simples e flex´ıvel ´e atrav´es da t´ecnica da
inunda¸c˜ao, a qual envia mensagens de busca por toda a rede tentando descobrir onde est´a
a informa¸c˜ao que necessita. Esta t´ecnica, apesar de mais flex´ıvel, causa grande tr´afego de
mensagens na rede, ocasionando atrasos e congestionamentos.
1.3 Objetivos
A uni˜ao do problema da localiza¸c˜ao das informa¸c˜oes com a rica semˆantica intr´ınseca
aos dados compartilhados configura um panorama de um desafio no desenvolvimento de
1.4 Materiais e M´etodos 3
sistemas de bancos de dados peer-to-peer. A tentativa de prever onde ser´a poss´ıvel encon-
trar a informa¸c˜ao requisitada ´e de essencial importˆancia para alcan¸car uma performance
aceit´avel nestes sistemas.
O objetivo deste trabalho ´e apresentar uma proposta de de estrat´egia de roteamento
que permite contornar o problema de localiza¸c˜ao da informa¸c˜ao em um sistema de banco
de dados peer-to-peer. Para evitar atrasos e congestionamentos que podem afetar o de-
sempenho do sistema, ´e apresentada uma estrat´egia de roteamento de buscas que visa
diminuir o tr´afego de mensagens na rede ao mesmo tempo em que o n´umero de respostas
obtidas por consulta ´e mantido.
1.4 Materiais e M´etodos
Para alcan¸car o objetivo de diminuir o tr´afego na rede, prop˜oe-se a aplica¸c˜ao do al-
goritmo de otimiza¸c˜ao por colˆonias de formigas para encontrar boas rotas [4], buscando
enviar as mensagens somente aos caminhos com maior probabilidade de encontrar resul-
tados. Juntamente com a aplica¸c˜ao deste algoritmo, utiliza-se ontologias para representar
a semˆantica intr´ınseca ao dados e, assim, permitir a integra¸c˜ao entre bases de dados
heterogˆeneas.
Portanto, atrav´es do algoritmo de colˆonia de formigas e da categoriza¸c˜ao dos dados
por ontologias, a estrat´egia de roteamento de consultas apresentada neste trabalho utiliza
informa¸c˜oes de buscas passadas para indicar qual caminho tem maior chance de levar a
n´os com informa¸c˜oes relevantes a cada processo de busca no sistema.
1.5 Organiza¸c˜ao dos Cap´ıtulos
Neste cap´ıtulo foi apresentada uma breve introdu¸c˜ao ao conte´udo do trabalho. No
cap´ıtulo 2 ´e apresentado o estado da arte das tecnologias relacionadas ao desenvolvimento
do trabalho, a saber: redes peer-to-peer, otimiza¸c˜ao pelo algoritmo de colˆonia de formigas
1.5 Organiza¸c˜ao dos Cap´ıtulos 4
e ontologias. O cap´ıtulo 3 traz todo o desenvolvimento do trabalho e o sistema criado.
No cap´ıtulo 4 s˜ao apresentados os resultados de alguns testes realizados para a an´alise do
desempenho da estrat´egia de roteamento proposta. Por fim, no cap´ıtulo 5 s˜ao discorridas
algumas conclus˜oes sobre o trabalho e apresentadas propostas de trabalhos futuros.
5
2 Fundamenta¸c˜ao Te´orica
A popularidade que sistemas de compartilhamento de arquivos atingiram nos ´ultimos
anos incentivou in´umeras pesquisas com sistemas que utilizam redes peer-to-peer para a
comunica¸c˜ao entre computadores. Dentre estes sistemas, o gerenciamento de dados em
redes peer-to-peer ´e apresentado como um grande avan¸co no compartilhamento de infor-
ma¸c˜oes estruturadas e semanticamente relacionadas. Em outra frente s˜ao apresentados
trabalhos relacionados a ontologias, visando atribuir semˆantica atrav´es da categoriza¸c˜ao
padronizada da informa¸c˜ao. Neste cap´ıtulo s˜ao apresentados os principais aspectos e
caracter´ısticas destas tecnologias.
2.1 Gerenciamento de Dados em Peer-to-Peer
Nesta se¸c˜ao ser˜ao apresentadas as principais caracter´ısticas e funcionalidades dos sis-
temas de gerenciamento de dados em peer-to-peer. Estes sistemas proporcionam meios
de compartilhar informa¸c˜oes armazenadas em bancos de dados heterogˆeneos e geografica-
mente distribu´ıdos, mas com alguma liga¸c˜ao semˆantica. Apesar de tratar-se de sistemas
que integram bancos de dados j´a estabelecidos, pode-se referir a tal classe de sistemas
como bancos de dados peer-to-peer.
Para o correto entendimento deste tipo de sistema de gerenciamento de dados, primeiro
s˜ao apresentadas as principais caracter´ısticas de redes peer-to-peer e seus modelos na
se¸c˜ao 2.1.1. Na se¸c˜ao 2.1.2 s˜ao abordados os sistemas de gerenciamento de dados em
peer-to-peer. As se¸c˜oes seguintes apresentam aspectos importantes destes sistemas, como
2.1 Gerenciamento de Dados em Peer-to-Peer 6
mapeamento, processamento de consultas, consistˆencia e localiza¸c˜ao dos dados. Exemplos
de sistemas existentes s˜ao apresentados na se¸c˜ao 2.1.7.
2.1.1 Redes Peer-to-Peer
Redes peer-to-peer s˜ao redes massivamente distribu´ıdas para o compartilhamento de
informa¸c˜oes ou servi¸cos [1]. Ao utilizar este tipo de rede, as aplica¸c˜oes aproveitam os
recursos - armazenamento, conte´udo, coordena¸c˜ao e presen¸ca humana - dispon´ıveis nos
n´os da extremidade da Internet [5]. Redes peer-to-peer, ou simplesmente P2P, baseiam-se
no preceito de que cada participante da rede, tamb´em chamado de n´o, ponto ou par,
possui direitos e deveres iguais. Em alguns momentos um computador pode estar requisi-
tando algum tipo de servi¸co, enquanto em outro pode estar servindo outros participantes
com seus servi¸cos. Portanto, todos os n´os s˜ao equivalentes em termos de funcionalida-
des e tarefas que desempenham e a no¸c˜ao de administra¸c˜ao ou mesmo de propriedade
da rede ´e distribu´ıda entre os participantes [6]. Em um sistema P2P cada par requisi-
tante/fornecedor comunica-se diretamente, sem a interven¸c˜ao direta de nenhum servidor
ou mediador entre os n´os. Este esquema cria uma rede overlay sobre a estrutura f´ısica da
Internet, ligando apenas os n´os participantes da rede.
Os sistemas P2P inicialmente foram constru´ıdos para a distribui¸c˜ao de dados n˜ao
estruturados, como arquivos e m´usicas. O Napster [7] foi o pioneiro em compartilhamento
massivo de arquivos, no caso arquivos de m´usica, e popularizou este tipo de sistema.
Depois dele surgiram muitos outros, como o KaZaA [7] e o BitTorrent [8]. As mais recentes
pesquisas em sistemas P2P apresentam novas abordagens que permitem compartilhar
dados estruturados, bem como realizar buscas baseadas em seu conte´udo. Estes s˜ao os
chamados sistemas de gerenciamento de dados em redes peer-to-peer, que s˜ao o alvo deste
trabalho.
Algumas caracter´ısticas das redes peer-to-peer as tornam de grande interesse para
diversas aplica¸c˜oes. Dentre estas caracter´ısticas, descentraliza¸c˜ao, escalabilidade e auto-
2.1 Gerenciamento de Dados em Peer-to-Peer 7
nomia s˜ao as que mais atraem aten¸c˜ao [9], a saber:
∙ Descentraliza¸c˜ao - Processamento e armazenamento de dados s˜ao distribu´ıdos entre
os n´os. N˜ao h´a a necessidade de servidores centrais com alto poder de processamento,
alta capacidade de armazenamento ou grande largura de banda, pois cada n´o ´e
respons´avel por si pr´oprio nestes aspectos. Por n˜ao haver este servidor, o custo de
implanta¸c˜ao tende a ser reduzido, al´em de n˜ao haver um ponto de falha cr´ıtico;
∙ Escalabilidade - A rede peer-to-peer cresce sem a necessidade de grandes mudan¸cas.
Ao contr´ario, em um sistema cliente-servidor, para suportar o crescimento da rede,
os servidores devem ser atualizados, estendidos ou rebalanceados. Nas redes peer-to-
peer, o pr´oprio crescimento da rede agrega mais recursos, mais poder computacional,
mais fontes de servi¸cos, sem a necessidade de mudan¸cas ou investimentos;
∙ Autonomia - Pode-se definir quatro tipos de autonomia dos n´os - armazenamento,
execu¸c˜ao, tempo de vida e conex˜ao. Cada n´o possui autonomia de armazenamento,
pois pode armazenar apenas dados que lhe s˜ao de interesse, diferentemente de sis-
temas distribu´ıdos onde a administra¸c˜ao do sistema for¸ca os n´os a gravar dados ou
´ındices. Tamb´em possui autonomia na execu¸c˜ao das consultas que lhe s˜ao requisita-
das e de atualiza¸c˜ao de seus pr´oprios dados. A autonomia de tempo de vida deve-se
ao fato de que os n´os podem entrar e sair da rede quando lhes for conveniente. E a
autonomia de conex˜ao permite que os n´os escolham os outros n´os ao quais desejam
se conectar. Estas autonomias criam um problema quando existem n´os ego´ıstas,
que s˜ao aqueles que se conectam a rede e escolhem n˜ao fornecer nada `a comunidade,
apenas usufruem dos recursos compartilhados [10].
Basicamente existem trˆes modelos topol´ogicos para utiliza¸c˜ao em redes peer-to-peer:
puro, h´ıbrido ou hier´arquico [11]. Cada modelo apresenta vantagens e desvantagens que
os indicam para diferentes aplica¸c˜oes, como ´e descrito nos itens seguintes.
a) Rede peer-to-peer pura
2.1 Gerenciamento de Dados em Peer-to-Peer 8
Todos os n´os participantes de uma rede com topologia pura s˜ao iguais, sem nenhuma
diferencia¸c˜ao de deveres ou direitos, conforme ilustrado na Figura 1 modelo de rede
garante imunidade a qualquer falha local, pois nenhum n´o ´e crucial para o funciona-
mento da rede. Um dos grandes problemas encontrados nessa topologia ´e o processo
de entrada, pois n˜ao existe nenhum controle central, dificultando a descoberta de quais
n´os est˜ao conectados `a rede quando um novo integrante deseja juntar-se `a esta.
Figura 1: Rede peer-to-peer pura.
b) Rede peer-to-peer h´ıbrida
Figura 2: Rede peer-to-peer h´ıbrida com servidor de descoberta e consulta.
No modelo P2P h´ıbrido existe a figura de um ou mais servidores respons´aveis pela co-
2.1 Gerenciamento de Dados em Peer-to-Peer 9
ordena¸c˜ao central de alguns aspectos da rede, como mostrado na Figura 2. O servidor
pode administrar uma lista dos usu´arios atualmente conectados `a rede e gerenciar o
processo de uni˜ao ou sa´ıda da rede. Redes com servidores apenas para este tipo de
tarefa s˜ao chamadas de ”h´ıbridas com servidor de descoberta”. Entretanto, alguns ser-
vidores podem tamb´em ser respons´aveis por indexar o conte´udo disponibilizado pelos
n´os, e assim ser˜ao acessados pelos n´os toda vez que uma consulta deve ser realizada
no sistema. Neste caso pode-se dizer que a rede peer-to-peer h´ıbrida possui ”servidores
de descoberta e consulta”.
A utiliza¸c˜ao deste modelo de rede resolve os problemas de ponto de entrada na rede,
pois um n´o que deseja conectar-se sabe sempre como encontrar o servidor para tal
tarefa. No caso de um servidor de consulta, a quest˜ao de roteamento entre os n´os
tamb´em ´e simplificada, j´a que todas as consultas ser˜ao direcionadas ao servidor. Uma
desvantagem ´e o surgimento de um ponto cr´ıtico de falha, justamente o servidor, o
qual tamb´em deve possuir alto poder de processamento e grande largura de banda
para suportar todos os acessos dos n´os.
c) Rede peer-to-peer hier´arquica
Figura 3: Rede peer-to-peer hier´arquica.
Neste modelo n˜ao existem servidores como na rede h´ıbrida, por´em alguns n´os possuem
responsabilidades extras, sendo chamados de super-n´os e representados na Figura 3.
2.1 Gerenciamento de Dados em Peer-to-Peer 10
Um super-n´o pode indexar o conte´udo dos n´os comuns ligados a sua sub-rede e manter
controle sobre a mesma, al´em da possibilidade de associar semˆantica aos agrupamentos
criados. A busca por conte´udo nesta rede pode ser feita entre os super-n´os, j´a que estes
devem possuir ´ındices de todo o conte´udo compartilhado. Uma varia¸c˜ao deste tipo de
rede ´e chamada de K-redundante, onde existem K super-n´os para cada grupo, evitando
problemas no caso de falha em algum dos super-n´os e dividindo as responsabilidades.
2.1.2 Sistemas de gerenciamento de dados peer-to-peer
Um sistema de gerenciamento de dados peer-to-peer pode ser descrito como uma
cole¸c˜ao de bancos de dados locais, cada um com autonomia de coordena¸c˜ao, que interagem
entre si trocando informa¸c˜oes, consultas e permitindo acesso aos dados remotamente [2].
O gerenciamento de dados nesses sistemas re´une algumas das principais caracter´ısticas
dos sistemas de integra¸c˜ao de dados, al´em de herdar as vantagens e, consequentemente,
os desafios de redes peer-to-peer [12], sendo as principais: autonomia, escalabilidade e
descentraliza¸c˜ao, conforme visto na se¸c˜ao 2.1.1. Al´em disso, estes sistemas possibilitam
atribuir semˆantica aos dados de cada n´o, al´em do mapeamento dessa semˆantica de acordo
com as regras do sistema constru´ıdo.
Pode-se definir um sistema de gerenciamento de dados ponto-a-ponto como: ”Sistema
de gerenciamento de dados com arquitetura descentralizada, facilmente extens´ıvel, na qual
qualquer usu´ario pode contribuir com novos dados, novos esquemas, ou mapeamentos
entre os esquemas dos pontos”[12].
Para exemplificar a utiliza¸c˜ao de um banco de dados peer-to-peer, pode-se citar o com-
partilhamento de informa¸c˜oes entre unidades de sa´ude e entre m´edicos. Cada hospital e
cl´ınica m´edica possui seu pr´oprio banco de dados, com informa¸c˜oes de pacientes, diagn´os-
ticos, tratamentos, entre outros. Estes bancos de dados muitas vezes foram implantados
h´a anos e modific´a-los para conseguir integr´a-los torna-se invi´avel. Por´em este compar-
tilhamento de informa¸c˜oes desperta interesse na comunidade m´edica ao possibilitar que
2.1 Gerenciamento de Dados em Peer-to-Peer 11
m´edicos tenham acesso de qualquer lugar `a informa¸c˜oes como o hist´orico completo de
um paciente ou informa¸c˜oes de bancos de sangue e medula de hospitais do mundo todo.
Utilizando um banco de dados peer-to-peer ´e poss´ıvel realizar esta integra¸c˜ao sem que seja
necess´aria nenhuma altera¸c˜ao nos sistemas j´a existentes al´em de manter a total autonomia
de cada institui¸c˜ao sobre seu banco de dados.
Alguns pontos positivos podem ser ressaltados nestes sistemas:
∙ Facilidade de manuten¸c˜ao e administra¸c˜ao pela ausˆencia de um esquema de media¸c˜ao
´unico e pela autonomia dos n´os;
∙ As consultas s˜ao criadas nos n´os, seguindo o esquema local e os resultados podem
vir de qualquer lugar do sistema;
∙ Dependendo da topologia peer-to-peer escolhida, pode-se construir um sistema sem
nenhum ponto de falha cr´ıtico;
∙ A quantidade de dados de diferentes tipos e fontes tende a ser bem grande;
∙ A replica¸c˜ao pode ser conseguida com cache dos resultados das consultas.
Os sistemas para gerenciamento de dados peer-to-peer s˜ao baseados na ideia de flexi-
bilidade e liberdade dos seus componentes, portanto os dados e resultados tendem a ser
incompletos [2]. Quando comparados aos bancos de dados distribu´ıdos, apresentam algu-
mas caracter´ısticas diferentes, principalmente relacionadas `a flexibilidade. As principais
diferen¸cas s˜ao apresentadas na Tabela 1 [12].
Um banco de dados peer-to-peer ´e constitu´ıdo de v´arios n´os autˆonomos, cada um com
um ou mais bancos de dados locais. Cada n´o deve compartilhar as informa¸c˜oes contidas em
seus bancos de dados, bem como s˜ao habilitados a acessar as informa¸c˜oes compartilhadas
por outros n´os. Nestes sistemas um dos principais aspectos ´e a heterogeneidade dos
esquemas adotados: cada n´o adota o seu pr´oprio esquema.
´
E invi´avel a utiliza¸c˜ao de um
2.1 Gerenciamento de Dados em Peer-to-Peer 12
Bancos de Dados Distribu´ıdos Bancos de dados peer-to-peer
Poucas fontes Muitas fontes
N´umero fixo de n´os N´os entram e saem a toda hora
Dados consistentes (coordena¸c˜ao central) Dados n˜ao-confi´aveis (autonomia)
Consultas complexas Consultas simples
Esquemas criados pelo administrador Esquemas definidos pelos usu´arios
Rede fixa Rede imprevis´ıvel
Todas as fontes s˜ao conhecidas Um n´o pode n˜ao conhecer toda a rede
Resultados completos Resultados possivelmente incompletos
Tabela 1: Compara¸c˜ao entre bancos de dados distribu´ıdos e peer-to-peer
esquema ´unico devido `as pr´oprias caracter´ısticas de sistemas peer-to-peer. Al´em disso,
podem-se citar alguns motivos que impedem a utiliza¸c˜ao de um esquema ´unico, a saber:
∙ Os n´os podem possuir informa¸c˜oes que n˜ao desejam compartilhar;
∙ O alto n´umero de entradas e sa´ıdas da rede obrigaria que o esquema de media¸c˜ao
fosse atualizado constantemente;
∙ A falta de controle central dificultaria a manuten¸c˜ao do esquema ´unico.
Figura 4: Representa¸c˜ao de um banco de dados P2P e a indica¸c˜ao de uma consulta.
Na Figura 4 ´e apresentado um esquema de um banco de dados peer-to-peer, onde cada
n´o possui seus bancos locais e est´a ligado a diversos outros n´os. Quando uma consulta ´e
realizada, esta ´e processada nos bancos locais e tamb´em enviada para os outros n´os, para
que estes retornem os resultados que possam eventualmente possuir.
2.1 Gerenciamento de Dados em Peer-to-Peer 13
Um sistema de banco de dados peer-to-peer de qualidade deve possuir as seguintes
funcionalidades e caracter´ısticas principais [1]:
∙ Localiza¸c˜ao dos dados - os n´os devem estar habilitados a localizar os dados presentes
nos outros n´os da rede;
∙ Processamento de consultas - o sistema deve ser capaz de processar cada consulta e
encontrar os n´os com informa¸c˜oes relevantes;
∙ Integra¸c˜ao dos dados - o sistema deve permitir que dados com diferentes esquemas
sejam integrados e apresentados segundo o esquema individual de cada n´o;
∙ Consistˆencia - T´ecnicas de replica¸c˜ao e cache de dados s˜ao utilizadas e devem ga-
rantir a consistˆencia dos dados em cada c´opia.
Figura 5: Esquema poss´ıvel para cada n´o da rede [1].
Na Figura 5 ´e apresentado um poss´ıvel esquema de referˆencia para um n´o em um
sistema de banco de dados peer-to-peer. Cada n´o deve possuir uma interface para intera¸c˜ao
com o usu´ario, uma camada para processamento das opera¸c˜oes sobre os bancos de dados
e uma camada para a comunica¸c˜ao com a rede peer-to-peer.
2.1 Gerenciamento de Dados em Peer-to-Peer 14
Atrav´es da interface o usu´ario pode definir consultas nos dados locais ou nos dados
globais. O gerenciador de consultas ent˜ao ´e respons´avel por realizar os mapeamentos
necess´arios para que os n´os recebam, entendam e respondam corretamente a consulta em
quest˜ao. As informa¸c˜oes de mapeamento semˆantico armazenadas permitem ao gerenciador
definir quais n´os devem receber a consulta, pois nem todos possuem informa¸c˜oes relevantes
e enviar a consulta para estes seria um desperd´ıcio de banda e processamento [1].
Ap´os o mapeamento, o gerenciador de consultas envia as consultas reformuladas `a
camada P2P, que ser´a respons´avel por comunicar-se com os outros pares. Para o retorno
dos resultados podem ser adotadas duas estrat´egias: na primeira os resultados s˜ao en-
viados diretamente ao n´o que iniciou a consulta, onde ser˜ao tratados e apresentados ao
usu´ario; na segunda, podem existir n´os especiais respons´aveis por coordenar as consultas,
unir os resultados e enviar tudo j´a pronto ao n´o de in´ıcio da consulta.
Os resultados das consultas podem ser temporariamente armazenados pelo gerenciador
de cache, para acelerar consultas futuras que utilizem os mesmos dados, bem como fornecer
estes dados ao sistema em ocasi˜oes que podem n˜ao estar acess´ıveis, devido ao desligamento
dos n´os que possuem originalmente tais informa¸c˜oes.
Para as consultas nos dados locais pode-se utilizar uma camada que esconde os deta-
lhes do banco de dados utilizado, e, assim, deixa o sistema de gerenciamento independente
do SGBD - Sistema Gerenciador de Banco de Dados - escolhido. As atualiza¸c˜oes nos da-
dos locais devem ser propagadas para todos os n´os que possuam c´opias de tais dados em
cache para manter a consistˆencia dos dados. O gerenciador de atualiza¸c˜oes ´e respons´avel
por manter essa consistˆencia tanto dos dados locais armazenados em outros n´os, como
dos dados de outros n´os armazenados em cache.
2.1.3 Mapeamento entre esquemas
Devido `a heterogeneidade das bases de dados utilizadas em cada n´o e seus respectivos
esquemas, ´e necess´aria a realiza¸c˜ao de mapeamentos para que uma consulta escrita de
2.1 Gerenciamento de Dados em Peer-to-Peer 15
acordo apenas com um esquema local possa ser interpretada e processada por outros n´os
da rede [1]. Este mapeamento ´e estabelecido entre os n´os que est˜ao diretamente ligados
entre si na rede peer-to-peer. Por´em o mapeamento deve possibilitar aos pares buscar
a informa¸c˜ao desejada onde quer que esteja, sendo ent˜ao necess´ario criar caminhos de
mapeamentos ligando semanticamente n´os que n˜ao est˜ao diretamente conectados [13].
Os resultados das consultas s˜ao altamente dependentes da qualidade dos mapeamentos
criados.
Cada n´o possui mapeamento entre seus esquemas locais e os esquemas dos outros n´os
a que est´a ligado. Na Figura 6 pode-se observar que o n´o A est´a ligado diretamente a B,
C e D e, portanto, possui mapeamentos entre seu esquema e os esquemas desses n´os.
Figura 6: Mapeamentos armazenados no n´o A.
Um mapeamento estabelece um relacionamento semˆantico entre as tabelas e atribu-
tos de dois n´os. O processo de mapeamento ´e geralmente manual, sendo que os mais
tradicionais [14] utilizam um esquema mediador para integrar os dados. Os esquemas
locais s˜ao descritos como vis˜oes desse esquema mediador - LAV: local-as-view - ou ent˜ao o
esquema mediador ´e definido como uma vis˜ao dos esquemas locais - GAV: global-as-view.
As consultas s˜ao realizadas mapeando o esquema local para o mediador e do mediador
para os outros esquemas [12].
O uso de um esquema mediador em sistemas peer-to-peer ´e impratic´avel devido `as pr´o-
prias caracter´ısticas deste tipo de sistema. A entrada e sa´ıda constante de n´os necessitaria
2.1 Gerenciamento de Dados em Peer-to-Peer 16
que o esquema mediador fosse atualizado sempre que uma dessas a¸c˜oes ocorresse. Al´em
disso, o esquema mediador deveria ficar armazenado em algum n´o espec´ıfico, criando um
poss´ıvel ponto de falha. Devido a estes e outros problemas, sistemas de gerenciamento
de dados em peer-to-peer costumam abordar o mapeamento seguindo uma das trˆes t´ecni-
cas a seguir [1]. Em qualquer uma das trˆes abordagens pode-se notar que as rela¸c˜oes de
transitividade entre os mapeamentos s˜ao essenciais, a saber:
∙ Mapeamento em pares - Os mapeamentos s˜ao definidos entre cada dois n´os conec-
tados entre si. Sendo assim, um n´o possui todos os mapeamentos para os n´os a que
est´a diretamente ligado. Para alcan¸car os outros n´os ´e utilizada a regra da transiti-
vidade, ou seja, se um n´o A est´a ligado a D, mas n˜ao a F e o n´o D est´a ligado ao
F, ent˜ao A alcan¸ca F passando por D, como ´e apresentado na Figura 7.
∙ Mapeamento mediado por pares - Um n´o pode definir um mapeamento que englobe
os dados de dois ou mais pares. Por exemplo, na Figura 7, A pode possuir um
mapeamento englobando os esquemas de A, B e C. Quando o n´o D precisar acessar
os dados de C, ele pode usar o mapeamento de A para isso. Os sistemas Piazza [15]
e PeerDB [16] utilizam esta abordagem em seus mapeamentos.
∙ Mapeamento mediado por super-n´os - Nesta abordagem ´e criado um esquema medi-
ador dos mapeamentos em cada super-n´o contendo as informa¸c˜oes de mapeamento
de todos os n´os comuns que fazem parte da sua sub-rede. Al´em disso, s˜ao definidos
mapeamentos entre os esquemas mediadores de cada super-n´o, permitindo que n´os
associados a diferentes super-n´os tamb´em compartilhem dados.
O trabalho [10] relaciona o uso de documentos XML para a representa¸c˜ao de dados
compartilhados em redes peer-to-peer, permitindo trabalhar com dados incompletos e sem
esquema conhecido, por´em mantendo a semˆantica a eles atribu´ıda.
2.1 Gerenciamento de Dados em Peer-to-Peer 17
Figura 7: Mapeamento transitivo entre A e F.
2.1.4 Processamento de consultas
O processamento de consultas em um sistema de banco de dados peer-to-peer consiste
em preparar e executar uma consulta em v´arios n´os, os quais provavelmente possuem
caracter´ısticas e modelos de dados variados. Os primeiros sistemas P2P, que eram usados
apenas para compartilhamento de arquivos, requeriam apenas consultas simples, muitas
vezes baseada somente no nome do arquivo. Mas com o r´apido avan¸co destes sistemas e o
surgimento de novas aplica¸c˜oes est´a se tornando necess´aria a realiza¸c˜ao de consultas mais
complexas, como no caso de bancos de dados peer-to-peer em que as consultas podem
envolver diversos atributos e rela¸c˜oes [1].
Como visto, os n´os possuem mapeamentos associados a cada um de seus vizinhos. Du-
rante uma consulta s˜ao criados os caminhos de mapeamentos, que s˜ao caminhos utilizados
pelos mapeamentos para reformular a consulta at´e um determinado n´o. Por exemplo, uma
consulta realizada por um n´o A ser´a processada localmente e, em seguida, reformulada
de acordo com os mapeamentos dos vizinhos de A. Ao chegar a cada vizinho a consulta
reformulada de A, estes vizinhos repetem o processo, ou seja, realizam a consulta local e a
reformula¸c˜ao para os vizinhos. Na Figura 7, apresentada anteriormente, pode-se observar
um caminho de mapeamento entre A e F.
2.1 Gerenciamento de Dados em Peer-to-Peer 18
O caminho que uma consulta segue tem grande influˆencia nos seus resultados. A
cada n´o que a consulta percorre, o mapeamento realizado pode resultar em perda de
informa¸c˜ao da consulta, fazendo com que o resultado obtido no final seja incompleto.
Sendo assim, uma mesma consulta que seguir dois caminhos diferentes at´e chegar a um
n´o que possui dados de interesse pode obter resultados diferentes neste n´o, devido `as
diferen¸cas de mapeamento no caminho at´e o n´o destino [17].
Para realizar consultas mais complexas, como consultas por faixa de valores, m´aximos
e m´ınimos, ´e preciso que a estrutura da rede suporte tais consultas. Algumas estruturas
especiais tˆem sido propostas para resolver este problema. Algumas t´ecnicas adaptam o
modelo de tabela hash distribu´ıda - DHT - para permitir a realiza¸c˜ao de consultas por
faixas de valores [18].
Submeter uma consulta a todos os n´os e caminhos de mapeamento poss´ıveis ´e um pro-
cesso custoso e ineficiente. S˜ao criadas consultas redundantes, o que leva a processamento
desnecess´ario nos n´os e desperd´ıcio de banda. Al´em disso, o processo de reformula¸c˜ao das
consultas atrav´es do mapeamento tamb´em ´e custoso. Para tentar melhorar o desempenho
das consultas e a qualidade dos resultados, podem ser utilizadas t´ecnicas como o agru-
pamento semˆantico, que coloca pr´oximos pares com conte´udo de semˆantica semelhante,
criando grupos semˆanticos que facilitam o mapeamento entre os n´os [13]. Por´em esta
estrat´egia de agrupamento torna o processo de entrada na rede mais complexo e custoso.
2.1.5 Consistˆencia dos dados
Os principais problemas com a consistˆencia dos dados surgem devido ao uso de cache
e a replica¸c˜ao. No uso de cache o problema surge com a necessidade de manter os dados
que s˜ao armazenados temporariamente nos n´os consistentes com os dados das fontes. J´a
na replica¸c˜ao, a propaga¸c˜ao das atualiza¸c˜oes ´e dificultada pelo grande n´umero de n´os e
pela constante entrada e sa´ıda de n´os na rede.
2.1 Gerenciamento de Dados em Peer-to-Peer 19
2.1.6 Localiza¸c˜ao dos dados
As pr´oprias caracter´ısticas de redes peer-to-peer dificultam a localiza¸c˜ao dos dados
neste tipo de sistema. Como os n´os conhecem apenas uma pequena parte da rede, ´e dif´ıcil
prever onde estar˜ao as informa¸c˜oes desejadas, al´em do aspecto dinˆamico da rede tamb´em
dificultar o conhecimento da rede toda. A utiliza¸c˜ao da topologia h´ıbrida pode facilitar
tal localiza¸c˜ao, pois um reposit´orio central pode armazenar as informa¸c˜oes referentes aos
dados compartilhados. A cada conex˜ao, o n´o que est´a se integrando `a rede enviaria
meta-dados descrevendo os dados que disponibiliza. A topologia hier´arquica permite
que os super-n´os possuam alguma semˆantica, criando ent˜ao comunidades de n´os com
relacionamentos semˆanticos. Tamb´em pode ser utilizado um ´ındice das comunidades para
facilitar a localiza¸c˜ao dos dados.
Em uma rede de topologia pura, podem ser utilizadas duas t´ecnicas para a descoberta
de informa¸c˜oes: a n˜ao-estruturada, atrav´es de alguma t´ecnica que ajude a predizer onde
´e mais prov´avel encontrar a informa¸c˜ao desejada, ou a estruturada, pela cria¸c˜ao de redes
semˆanticas sobre a rede peer-to-peer. As t´ecnicas estruturadas concentram os esfor¸cos na
manuten¸c˜ao da posi¸c˜ao dos n´os, trabalhando principalmente na escolha do n´o de uni˜ao e
vizinhos de cada novo usu´ario da rede. As t´ecnicas n˜ao-estruturadas deixam o processo de
entrada mais livre e flex´ıvel, agindo principalmente atrav´es de estrat´egias de localiza¸c˜ao
das informa¸c˜oes baseado no hist´orico de resultados obtidos anteriormente.
2.1.7 Bancos de dados peer-to-peer existentes
Alguns sistemas de banco de dados peer-to-peer j´a foram propostos na literatura,
sendo os principais o Piazza [15], XPeer [19], Hyperion [20] e PeerDB [16].
O Piazza utiliza uma rede pura n˜ao-estruturada e permite que os n´os compartilhem
seus dados atrav´es de vis˜oes disponibilizadas para o acesso dos pares [15]. Somente os
dados acess´ıveis pelas vis˜oes compartilhadas est˜ao dispon´ıveis e as consultas s˜ao reescritas
a cada n´o por onde passa. O XPeer permite mapeamentos entre os dados tanto na forma
2.1 Gerenciamento de Dados em Peer-to-Peer 20
LAV quanto GAV [19]. Utilizando o modelo hier´arquico, cria agrupamentos de pares
que compartilham seus dados atrav´es de um esquema mediador armazenado no super-n´o.
As consultas s˜ao reescritas somente entre os super-n´os, os quais s˜ao respons´aveis pela
coordena¸c˜ao dos n´os em seu agrupamento e seus respectivos mapeamentos.
O sistema Hyperion utiliza uma rede do modelo puro n˜ao-estruturado, utilizando
tabelas e express˜oes de mapeamento no tratamento das consultas. Estas tabelas de ma-
peamento s˜ao definidas entre cada par de n´os e entre cada banco de dados que integra o
sistema [20].
O PeerDB utiliza a plataforma BestPeer [21], que cria uma rede com topologia pura
n˜ao-estruturada. O mapeamento entre os esquemas ´e realizado atrav´es de palavras-chave
e fun¸c˜oes de similaridade, permitindo compartilhar os dados sem a necessidade de com-
partilhar nenhuma informa¸c˜ao do esquema. O processamento de consultas ´e dependente
da intera¸c˜ao com o usu´ario, assim como a atribui¸c˜ao de palavras-chave. A qualidade dos
resultados obtidos nas consultas varia conforme a qualidade das anota¸c˜oes de palavras-
chaves realizadas e decis˜oes tomadas durante a consulta [16].
Figura 8: Esquema de um n´o no sistema PeerDB [16].
Na Figura 8 pode-se observar o esquema de cada n´o deste sistema. O Dicion´ario Lo-
cal armazena os meta-dados associados a cada banco de dados local. Desses meta-dados,
apenas aqueles referentes aos itens que podem ser acessados pelos outros pares s˜ao expor-
2.2 Estrat´egias de busca em redes peer-to-peer 21
tados para o Dicion´ario de Exporta¸c˜ao. PeerDB adota uma estrat´egia de agentes m´oveis
respons´aveis pelo processamento das consultas localmente, em cada n´o da rede. O ma-
peamento entre esquemas ´e realizado atrav´es da associa¸c˜ao das palavras-chave atribu´ıdas
`as rela¸c˜oes origens da consulta com as palavras-chaves atribu´ıdas `as rela¸c˜oes nos outros
n´os, ficando a cargo do usu´ario selecionar quais os relacionamentos entre palavras-chave
semelhantes realmente s˜ao interessantes ao sistema [16].
O processo de busca ´e realizado em dois passos. Primeiramente s˜ao retornadas ao
usu´ario as tabelas candidatas, encontradas atrav´es de associa¸c˜oes das suas palavras-chave,
bem como das palavras-chave de seus atributos. Ap´os selecionar as tabelas relevantes, a
consulta ´e ent˜ao processada em cada tabela escolhida, ap´os o devido mapeamento. As
respostas s˜ao retornadas, exibidas e armazenadas em cache.
2.2 Estrat´egias de busca em redes peer-to-peer
Um dos principais desafios dos sistemas peer-to-peer ´e a busca por informa¸c˜ao. Dada
a falta de coordena¸c˜ao central e o alto grau de distribui¸c˜ao da informa¸c˜ao, encontrar o
local correto com a maior eficiˆencia poss´ıvel ´e essencial. Este processo ´e fundamental e
define a viabilidade do uso deste tipo de sistema [3].
O modelo de rede h´ıbrido com servidor de consulta n˜ao apresenta grandes dificuldades,
pois todo o conte´udo est´a indexado em um s´o lugar. Por´em surgem problemas como um
ponto cr´ıtico de falha, um gargalo de processamento e de banda para o sistema. No
modelo hier´arquico, o ´ındice de conte´udo fica distribu´ıdo nos super-n´os, diminuindo os
efeitos dos problemas apresentados, por´em n˜ao os elimina. No caso de um dos super-n´os
falhar, uma parte do conte´udo disponibilizado na rede pode ficar inacess´ıvel.
Sem um controle central, o que ocorre nas redes peer-to-peer puras, s˜ao necess´arias
t´ecnicas eficientes para encontrar as informa¸c˜oes nos n´os da rede. Algumas t´ecnicas man-
t´em um controle r´ıgido sobre a estrutura da rede e, atrav´es de busca por identificadores
´unicos, garantem sempre encontrar o conte´udo desejado, como, por exemplo, tabelas hash
2.2 Estrat´egias de busca em redes peer-to-peer 22
distribu´ıdas [22]. Para redes sem nenhuma estrutura fixa, a estrat´egia adotada ´e a uti-
liza¸c˜ao de t´ecnicas baseadas em inunda¸c˜ao
1
, mais simples e mais flex´ıveis que t´ecnicas
estruturadas, por´em podem apresentar um desempenho inferior na quest˜ao de consumo
de banda e tempo de resposta [2].
Nas se¸c˜oes 2.2.1 e 2.2.2 s˜ao explicadas duas principais estrat´egias que baseiam-se
no controle da estrutura da rede: tabelas hash distribu´ıdas e redes semˆanticas overlay,
respectivamente. Na se¸c˜ao 2.2.3 ´e detalhada a t´ecnica da inunda¸c˜ao, que n˜ao realiza
nenhum controle fixo sobre a estrutura da rede. Um algoritmo baseado em colˆonias de
formigas que pode ser usado para encontrar caminhos em grafos e redes peer-to-peer ´e
descrito na se¸c˜ao 2.2.4.
2.2.1 Tabela Hash Distribu´ıda - DHT
Os recursos da rede s˜ao divididos entre os n´os. Em uma aplica¸c˜ao de compartilha-
mento de arquivos, por exemplo, uma fun¸c˜ao hash mapeia n´os e arquivos com identifica-
dores ´unicos. A cada n´o ´e atribu´ıda uma faixa de identificadores, e este fica respons´avel
pelos itens que possuem identificadores dentro desta faixa.
´
E utilizada sobreposi¸c˜ao de
faixas para possibilitar a replica¸c˜ao e garantir a disponibilidade dos itens.
Figura 9: Exemplo de distribui¸c˜ao dos valores da fun¸c˜ao hash entre n´os [12].
Na Figura 9 pode-se observar um esquema-exemplo de uma rede peer-to-peer com as
faixas de identificadores de cada n´o, indicando onde pode ser encontrado o recurso com
1
Encontrada na literatura como flooding.
2.2 Estrat´egias de busca em redes peer-to-peer 23
hash 8045.
2.2.2 Rede Semˆantica Overlay - SON
Figura 10: Redes semˆanticas em uma divis˜ao para o roteamento [3].
Cria uma rede virtual agrupando n´os com liga¸c˜oes semˆanticas. Cada ”mini-rede”criada
possui uma semˆantica associada, podendo estas mini-redes se sobreporem. Na Figura 10 ´e
mostrado um exemplo deste tipo de rede peer-to-peer. Neste exemplo ´e criada uma divis˜ao
semˆantica baseada nos estilos musicais que cada n´o possui. Quando um n´o possui m´usicas
de mais de um estilo, este n´o entra em diversas mini-redes semˆanticas. As consultas
realizadas s˜ao enviadas somente aos grupos semˆanticos relacionados, ignorando aqueles
que n˜ao possuem qualquer rela¸c˜ao `a semˆantica estabelecida na consulta.
2.2.3 Inunda¸c˜ao
As mensagens s˜ao enviadas a todos os n´os em cadeia, ou seja, um n´o envia a todos
seus vizinhos, que por sua vez enviam aos seus respectivos vizinhos, e assim por diante [1].
Ocorre uma verdadeira inunda¸c˜ao de mensagens na rede, muitas sendo enviadas diversas
vezes a um mesmo n´o. Para evitar que as mensagens fiquem navegando indefinidamente
na rede, ´e definido um tempo de vida - time-to-live ou simplesmente TTL - medido em
saltos, ou seja, quantidade de vezes que a mensagem foi enviada.
2.2 Estrat´egias de busca em redes peer-to-peer 24
A total falta de controle sobre o roteamento das mensagens nesta t´ecnica causa pro-
blemas como o congestionamento da rede, devido ao excesso de mensagens, e o problema
de que definindo um tempo de vida inadequado pode-se impossibilitar a consulta alcan¸car
n´os que possuem informa¸c˜oes de interesse. A defini¸c˜ao de um tempo de vida ideal ´e um
grande desafio nesta t´ecnica.
Figura 11: Inunda¸c˜ao com tempo de vida 3 [23].
Um tempo de vida muito alto pode causar uma sobrecarga de mensagens na rede,
enquanto um muito pequeno ocasionaria poucos ou at´e mesmo nenhum resultado para as
buscas [24]. Na Figura 11 ´e mostrado um exemplo onde o TTL definido, neste caso trˆes,
n˜ao foi suficiente para que a consulta chegasse ao n´o que possui o arquivo procurado pelo
n´o de in´ıcio da consulta.
Uma varia¸c˜ao da t´ecnica de inunda¸c˜ao utiliza um agente que caminha de n´o em n´o
realizando a busca [25]. Este agente possui um tempo de vida que somente ´e decrementado
quando algum resultado ´e encontrado. Essa adapta¸c˜ao reduz o tr´afego na rede, por´em o
tempo de resposta cresce.
Geralmente apenas buscas exatas s˜ao poss´ıveis de ser realizadas em redes utilizando a
t´ecnica de inunda¸c˜ao. Mas em alguns casos ´e necess´ario realizar buscas que considerem a
uni˜ao de todos os resultados, como em buscas do tipo ”retorne as 10 imagens mais seme-
lhantes ao exemplo”. Buscas desse tipo podem ser custosas, pois, em um sistema comum,
cada par retornaria ao n´o que iniciou a pesquisa seus resultados e caberia a este n´o organi-
zar todos os resultados. Uma t´ecnica de busca proposta, chamada FuzzyPeer [9], permite
2.2 Estrat´egias de busca em redes peer-to-peer 25
que o controle dos resultados seja realizado ao longo da busca, nos n´os intermedi´arios,
diminuindo assim o consumo de banda e o n´umero de mensagens descartadas.
Em outro trabalho ´e descrita uma proposta em que os n´os guardam informa¸c˜oes esta-
t´ısticas sobre seus vizinhos, permitindo que o primeiro passo da t´ecnica de inunda¸c˜ao seja
direcionado `aqueles n´os com maior probabilidade de bons resultados [3]. Por´em, a partir
do segundo passo n˜ao h´a mudan¸ca, seguindo a inunda¸c˜ao de mensagens caracter´ıstica
desta t´ecnica.
Outros trabalhos prop˜oem a utiliza¸c˜ao da chamada ”aprendizagem por reputa¸c˜ao”[26]
[27], que visa predizer em todos os passos quais os n´os que devem receber a busca, dada
a qualidade dos resultados retornados em processos anteriores.
2.2.4 Colˆonia de formigas em peer-to-peer
Visando melhorar o desempenho da t´ecnica de localiza¸c˜ao da informa¸c˜ao por inun-
da¸c˜ao, algumas pesquisas tˆem indicado o uso do algoritmo de colˆonia de formigas na
otimiza¸c˜ao dos caminhos que devem receber a consulta [28] [4]. Colˆonia de formigas,
tamb´em conhecido como ACO - Ant Colony Optimization System, ´e um algoritmo de oti-
miza¸c˜ao baseado no comportamento de formigas e suas colˆonias na natureza. Resultados
de pesquisas e experimentos mostraram que formigas utilizam uma forma de comunica-
¸c˜ao indireta para transmitir a informa¸c˜ao aos outros indiv´ıduos da colˆonia, conseguindo,
assim, encontrar boas rotas at´e a fonte de alimento, mesmo sendo seres quase cegos. Li-
berando uma substˆancia, chamada feromˆonio, as formigas marcam o caminho por onde
passam e podem informar `as outras qual caminho leva at´e o alimento.
Utilizando trilhas com diferentes intensidades de feromˆonio, as formigas marcam o
caminho, configurando um sistema em que o melhor caminho possui um n´ıvel maior de
feromˆonio, sendo, portanto, escolhido pelas outras formigas [29]. Na Figura 12 ´e mostrado
um experimento que comprova a ideia de escolha do menor caminho, ilustrando que em
um mesmo intervalo de tempo ser´a poss´ıvel uma maior quantidade de formigas seguir pelo
2.2 Estrat´egias de busca em redes peer-to-peer 26
menor caminho, obtendo assim uma trilha com maior concentra¸c˜ao de feromˆonio [30].
Figura 12: Comportamento das Formigas.
Levando em conta todas as an´alises de comportamento e experimentos realizados com
as formigas no mundo real, um trabalho apresentou um algoritmo baseado em tal compor-
tamento que pode ser usado para a resolu¸c˜ao de problemas de otimiza¸c˜ao, principalmente
na descoberta de rotas eficientes em alguns tipos de grafos [30]. Exemplos de problemas
que podem ser resolvidos com colˆonia de formigas s˜ao o problema do caixeiro viajante [31]
e a otimiza¸c˜ao de algoritmos para alinhamento m´ultiplo de sequˆencias em bioinform´atica
[32].
Uma caracter´ıstica importante deste algoritmo ´e a capacidade de absorver mudan¸cas
no grafo dinamicamente. Tal caracter´ıstica habilita esta t´ecnica para o uso em sistemas
de roteamento em redes de computadores dinˆamicas, como as redes peer-to-peer. Uma
avalia¸c˜ao de desempenho deste tipo de t´ecnica de roteamento levou em conta a dinami-
cidade da rede e confirmou a capacidade de sistemas utilizando tal classe de algoritmo
absorverem as mudan¸cas constantes na rede de forma satisfat´oria [28].
Utilizando colˆonia de formigas para melhorar o roteamento em redes que utilizam
a t´ecnica da inunda¸c˜ao, ´e poss´ıvel predizer caminhos que tem maior probabilidade de
retornar bons resultados. Um dos principais trabalhos na utiliza¸c˜ao do algoritmo de
colˆonia de formigas para cria¸c˜ao de tabelas de roteamento ´e chamado de AntNet [33], o
qual foi utilizado para definir uma estrat´egia de roteamento em redes peer-to-peer baseado
em colˆonia de formigas [4]. Utilizando palavras-chave definidas para cada n´o, s˜ao criados
m´ultiplos tipos de feromˆonio, os quais resultam em diferentes caminhos para cada palavra-
2.3 Ontologias na Computa¸c˜ao 27
chave escolhida na busca realizada.
2.3 Ontologias na Computa¸c˜ao
Em 1993, Gruber [34] definiu uma ontologia como uma ”especifica¸c˜ao expl´ıcita de uma
conceitualiza¸c˜ao”. Tal defini¸c˜ao foi atualizada posteriormente [35], tornando-se a defini¸c˜ao
mais comumente aceita para ontologia em computa¸c˜ao: ”Uma ontologia ´e definida como
uma especifica¸c˜ao expl´ıcita e formal de uma conceitualiza¸c˜ao compartilhada”[36].
Apesar de aplic´avel em v´arias ´areas, ontologia tem sido estudada em aplica¸c˜oes com-
putacionais para a defini¸c˜ao de vocabul´arios representando o conhecimento [37], o que per-
mite criar uma linguagem comum para a integra¸c˜ao entre sistemas heterogˆeneos, como,
por exemplo, integra¸c˜ao das informa¸c˜oes de bancos de dados com esquemas diferentes,
por´em mesma semˆantica.
Para o desenvolvimento de uma ontologia deve-se considerar as seguintes caracter´ıs-
ticas [38]:
∙ Clareza e objetividade - as defini¸c˜oes devem ser claras e objetivas e acompanhadas
de documenta¸c˜ao em linguagem natural;
∙ Completeza - cada defini¸c˜ao deve contemplar todas as condi¸c˜oes necess´arias e su-
ficientes para expressar um termo, indo al´em das necessidades espec´ıficas de uma
aplica¸c˜ao;
∙ Coerˆencia para permitir derivar inferˆencias que sejam consistentes com as defini¸c˜oes;
∙ Extensibilidade monotˆonica - para incluir novos termos n˜ao deve ser necess´aria ne-
nhuma revis˜ao dos termos e defini¸c˜oes j´a existentes;
∙ M´ınimo compromisso ontol´ogico para permitir que sejam definidas t˜ao poucas su-
posi¸c˜oes quanto poss´ıveis sobre o mundo a ser modelado, permitindo que as especi-
aliza¸c˜oes e instancia¸c˜oes da ontologia sejam definidas com liberdade;
2.3 Ontologias na Computa¸c˜ao 28
∙ Princ´ıpio da distin¸c˜ao ontol´ogica - nenhum conceito pode sobrepor outro, ou seja,
as classes da ontologia devem ser disjuntas;
∙ Diversifica¸c˜ao das hierarquias para aproveitar todo potencial dos mecanismos de
heran¸ca m´ultipla;
∙ Modularidade visando reduzir ao m´aximo o acoplamento entre os m´odulos;
∙ Minimiza¸c˜ao da distˆancia semˆantica entre conceitos similares buscando agrup´a-los
para representar utilizando as mesmas primitivas;
∙ Padroniza¸c˜ao dos nomes sempre que poss´ıvel.
Na computa¸c˜ao, a ontologia foi inicialmente empregada na ´area de Inteligˆencia Artifi-
cial pelo fato de descrever o conhecimento. Hoje, ela pode ser encontrada em trabalhos e
aplica¸c˜oes de diversas ´areas. O uso de ontologia ganhou destaque com o advento da Web
Semˆantica, a qual utiliza ontologia na sua constitui¸c˜ao central [39]. No estado atual da
Web, as informa¸c˜oes dispon´ıveis s˜ao normalmente dispersas e sem padr˜ao. Assim, encon-
trar informa¸c˜ao apenas baseado no contexto semˆantico torna-se uma tarefa ´ardua. Com
a associa¸c˜ao de ontologias `as informa¸c˜oes, permite-se que agentes de software encontrem
mais facilmente as informa¸c˜oes dispersas de um mesmo contexto semˆantico, tornando a
experiˆencia do usu´ario na Internet mais rica e interessante.
Na ´area de banco de dados, o uso de ontologias mostra-se de grande interesse em
trabalhos de integra¸c˜ao de dados [37] [40] [41]. Problemas relacionados `a heterogenei-
dade dos esquemas e dados armazenados podem ser contornados com a correta atribui¸c˜ao
de ontologias. Mesmo bases de dados de um mesmo dom´ınio s˜ao criadas por analistas
diferentes, em momentos diferentes, por raz˜oes diferentes e, consequentemente, possuem
esquemas bem diferentes, necessitando de um mapeamento entre tais bases.
No processo de integra¸c˜ao de bases de dados ´e preciso garantir que as opera¸c˜oes reali-
zadas n˜ao comprometam o modo como os dados est˜ao armazenados e a semˆantica atrelada
a eles. Um erro ou um mapeamento mal feito pode levar `a perda do real significado das
2.3 Ontologias na Computa¸c˜ao 29
informa¸c˜oes e comprometer todo o resultado alcan¸cado [42]. Uma abordagem simples ´e
a cria¸c˜ao de vis˜oes dentro dos pr´oprios bancos de dados para o compartilhamento das
informa¸c˜oes [43], por´em este m´etodo restringe as op¸c˜oes `as possibilidades oferecidas pela
linguagem SQL e ainda necessita de um bom algoritmo de reescrita das consultas para
garantir a eficiˆencia e qualidade das respostas. Da´ı o uso de ontologias surge como uma
boa op¸c˜ao [42].
O uso de ontologias no compartilhamento de informa¸c˜oes armazenadas em bases de da-
dos permite a defini¸c˜ao formal de uma linguagem ´unica a ser entendida por qualquer base
de dados do dom´ınio desta ontologia, desde que cada elemento do banco de dados tenha
sido corretamente classificado. Com isso, ´e criada uma liga¸c˜ao semˆantica entre os elemen-
tos de diferentes esquemas, permitindo a interoperabilidade entre eles [42]. Uma solu¸c˜ao
para a integra¸c˜ao de bases de dados heterogˆeneas utilizando ontologias foi apresentada
em [37], na qual uma ontologia do dom´ınio das informa¸c˜oes ´e definida e compartilhada
entre cada uma das bases de dados.
Outro trabalho envolvendo ontologias na integra¸c˜ao de bases de dados ´e o sistema
”DISFOQuE”[40], um sistema de integra¸c˜ao de dados baseado em ontologias. Neste tra-
balho foi mostrada a viabilidade da constru¸c˜ao de um sistema de integra¸c˜ao utilizando
uma ontologia de um dom´ınio espec´ıfico, que neste caso trata de dados de an´alises de
bacias hidrogr´aficas. Utilizando a linguagem OWL (Web Ontology Language) para a de-
fini¸c˜ao das ontologias, foi constru´ıdo um sistema espec´ıfico para a integra¸c˜ao de algumas
bases do dom´ınio apresentado.
Ao dizer que uma ontologia ´e uma especifica¸c˜ao formal, tˆem-se em vista que tal ontolo-
gia deve ser formalmente descrita para que seja process´avel por um computador, evitando
o uso de linguagem natural em tais descri¸c˜oes. Uma ontologia depois de definida deve ser
implementada seguindo uma linguagem que permita que os softwares compreendam seu
significado. A linguagem com maior destaque tem sido a OWL (Web Ontology Language)
[44], proposta pelo grupo W3C (World Wide Web Consortium) [45] para ser usada como
2.4 Considera¸c˜oes Finais 30
a linguagem da Web Semˆantica. Ela foi proposta tendo como base a OIL (Ontology In-
ference Layer) e a DAML (DARPA Agent Markup Language). A OWL ´e uma linguagem
que tem sido amplamente difundida, facilitando o reuso e a comunica¸c˜ao entre diferentes
aplica¸c˜oes.
2.4 Considera¸c˜oes Finais
Neste cap´ıtulo foram abordados os principais aspectos dos conceitos e tecnologias
envolvidas em sistemas de gerenciamento de dados em redes peer-to-peer. Foram apre-
sentadas as topologias e estrat´egias de roteamento neste tipo de rede para um melhor
entendimento do funcionamento dos bancos de dados peer-to-peer. Posteriormente foi de-
talhado todo o funcionamento e t´ecnicas envolvidas no compartilhamento de informa¸c˜oes
de bancos de dados nestes sistemas. Por ´ultimo foi apresentado o conte´udo b´asico de
ontologias no contexto de integra¸c˜ao de dados atrav´es da categoriza¸c˜ao padronizada das
informa¸c˜oes.
31
3 Banco de dados peer-to-peer e a
estrat´egia de consulta
3.1 Considera¸c˜oes Iniciais
O desenvolvimento de um sistema de gerenciamento de dados em rede peer-to-peer
envolve v´arios fatores, conceitos e tecnologias que devem ser integradas para possibilitar
o melhor aproveitamento deste tipo de sistema. Um dos primeiros aspectos que devem
ser observados neste desenvolvimento e que influencia diretamente no desempenho obtido
´e a quest˜ao do roteamento das consultas na rede peer-to-peer.
Neste trabalho prop˜oe-se a utiliza¸c˜ao dos princ´ıpios do algoritmo de otimiza¸c˜ao ba-
seado em colˆonias de formigas para melhorar o roteamento das consultas em um banco
de dados peer-to-peer. O principal objetivo foi contribuir para que as consultas sejam
enviadas sempre para os n´os com maiores chances de retornar bons resultados, tornando
o sistema mais objetivo e eficiente. Ao direcionar de forma eficiente as consultas, o tr´afego
de mensagens na rede pode ser reduzido e, consequentemente, permite-se a redu¸c˜ao do
tempo de espera por respostas de interesse.
Para desenvolver uma estrat´egia que permita direcionar eficientemente as consultas, ´e
necess´ario o conhecimento dos dados que podem ser obtidos em cada caminho poss´ıvel a
ser seguido. Para obter tal conhecimento ´e proposta a categoriza¸c˜ao dos dados utilizando
ontologias, permitindo-se ao sistema criar caminhos variados baseados na ontologia e
levando-se em conta, de forma padronizada, o conte´udo de cada n´o conectado `a rede.
3.2 Semˆantica dos dados 32
3.2 Semˆantica dos dados
Uma das principais caracter´ısticas que tornam a utiliza¸c˜ao de bancos de dados peer-
to-peer interessante ´e a capacidade de inter-relacionar bases de dados com esquemas he-
terogˆeneos, de forma transparente e dinˆamica. Um bom sistema de BDP2P deve permitir
que o usu´ario acesse as informa¸c˜oes das bases de dados espalhadas pela rede e receba as
informa¸c˜oes realmente relacionadas ao seu assunto de interesse.
Para possibilitar o relacionamento semˆantico entre as diversas bases de dados, ´e ne-
cess´ario que seja estabelecido um sistema de comunica¸c˜ao entre as bases, permitindo
que estruturas diferentes sintaticamente, mas com mesma semˆantica, sejam integradas e
acessadas como uma s´o. Esta proposta sugere que esta via de liga¸c˜ao seja criada com
a utiliza¸c˜ao de ontologias para definir os elementos de cada banco de dados. Para tal
tarefa, ´e necess´ario que cada elemento das bases de dados dos n´os que ir˜ao unir-se `a rede
seja interpretado e associado a uma defini¸c˜ao ontol´ogica. Este processo deve ser realizado
atrav´es da intera¸c˜ao do usu´ario, ou do administrador de banco de dados, para que seus
dados sejam disponibilizados `a rede e tamb´em para que suas consultas sejam corretamente
interpretadas pelos outros n´os que comp˜oem o sistema.
Ao definir a semˆantica dos dados armazenados localmente cria-se tamb´em uma defi-
ni¸c˜ao da semˆantica de cada n´o, ou seja, define-se quais as classes da ontologia utilizada
podem ser encontradas naquele n´o. Portanto, isto estabelecido, pode-se tratar cada n´o
como um ponto semˆantico, relacionado a uma ou mais classes da ontologia definida no
sistema.
3.3 Material e M´etodo
Para apresentar o funcionamento da estrat´egia de roteamento proposta, criou-se um
sistema peer-to-peer de gerenciamento de dados com as seguintes caracter´ısticas:
∙ Arquitetura da rede - foi criado um ambiente peer-to-peer puro, ou seja, sem servi-
3.3 Material e M´etodo 33
dores dedicados ou super-n´os;
∙ Conex˜ao com a rede - para que o usu´ario seja inserido na rede, este deve conectar-se
a outros usu´arios da sua lista de n´os de entrada;
∙ Sistema de busca - para a busca foi utilizada a t´ecnica de inunda¸c˜ao modificada pela
aplica¸c˜ao dos conceitos do algoritmo de colˆonia de formigas. Esta ´e a etapa mais
importante do trabalho desenvolvido e ser´a detalhada na se¸c˜ao 3.3.6;
∙ Classifica¸c˜ao dos dados - para agregar semˆantica aos dados com uma linguagem
padr˜ao, utiliza-se uma classifica¸c˜ao baseada em ontologias pr´e-definidas. Esta clas-
sifica¸c˜ao possibilita a utiliza¸c˜ao da estrat´egia de roteamento proposta para a cria¸c˜ao
de caminhos semˆanticos baseados em tais ontologias.
Cada computador conectado `a rede ´e autˆonomo e independe de qualquer outro, pos-
suindo uma c´opia completa do sistema. Ou seja, os dados locais podem ser acessados
independente da conex˜ao com outros n´os da rede. Na Figura 13 s˜ao apresentados os
m´odulos que comp˜oem o sistema e a intera¸c˜ao entre eles.
Figura 13: M´odulos do sistema proposto.
3.3 Material e M´etodo 34
∙ Interface com o Usu´ario - Respons´avel pela intera¸c˜ao direta com o usu´ario. Por
meio da interface, o usu´ario pode realizar suas consultas e obter as informa¸c˜oes dos
resultados;
∙ Gerenciador de Acesso aos Dados - Controla a comunica¸c˜ao do sistema com os
bancos de dados, atrav´es dos SGBDs. Esta camada permite ao sistema trabalhar
com diferentes bancos de dados em diferentes SGBDs de forma que o acesso seja
transparente `as outras camadas;
∙ Gerenciador de Ontologias - Esta camada ´e respons´avel pelo armazenamento e ge-
renciamento da ontologia utilizada no sistema;
∙ Interpretador SQL ⇔ Ontologias - Esta camada, como o pr´oprio nome sugere, tem
a fun¸c˜ao de interpretar as consultas SQL, associando as ontologias corretas a cada
item envolvido. Quando a consulta recebida foi originada em outro par, o interpre-
tador analisa a consulta SQL, juntamente com as ontologias recebidas, efetuando o
mapeamento para o esquema de dados local;
∙ Gerenciador Peer-to-Peer - Esta camada ´e respons´avel pela comunica¸c˜ao com os
outros n´os da rede. Aqui s˜ao realizados os processos de sele¸c˜ao de rotas com o
algoritmo de colˆonia de formigas, envio e recebimento de dados e resultados, al´em
das atualiza¸c˜oes nas tabelas de roteamento.
O gerenciador peer-to-peer concentrou a maior parte dos esfor¸cos deste trabalho. Os
detalhes de cada camada, bem como seu modo de a¸c˜ao s˜ao descritos nas se¸c˜oes que seguem.
3.3.1 Interface com o usu´ario
A interface com o usu´ario foi definida para ser o mais simples poss´ıvel. Atrav´es desta
interface o usu´ario pode configurar as conex˜oes com os bancos de dados e manter registro
de conex˜oes com mais de um SGBD no sistema. Ap´os configurar o acesso ao SGBD,
como ´e mostrado na Figura 14, o usu´ario pode realizar uma consulta, selecionando uma
3.3 Material e M´etodo 35
configura¸c˜ao de SGBD cadastrada. Ao selecionar o SGBD, uma lista dos bancos de dados
acess´ıveis ´e exibida para a sele¸c˜ao do usu´ario. A partir da´ı basta digitar a consulta
utilizando a linguagem SQL para que esta seja executada localmente e enviada aos outros
n´os. A interface para realizar a consulta SQL ´e ilustrada na Figura 15.
Figura 14: Configura¸c˜ao de acesso ao SGBD.
Figura 15: Interface de consulta.
Os resultados, tanto locais quanto remotos, s˜ao exibidos em uma tela separada, con-
forme pode ser visto na Figura 16. Esta janela de resultados ´e atualizada a cada resposta
recebida de outros n´os da rede.
3.3.2 Gerenciador de acesso aos dados
Este m´odulo ´e respons´avel pelo gerenciamento da comunica¸c˜ao com os bancos de
dados, os quais podem estar implementados em diferentes SGBDs. Esta camada permite
3.3 Material e M´etodo 36
Figura 16: Alguns resultados da consulta.
que os outros m´odulos do sistema tratem os dados de forma transparente, independente
do SGBD utilizado.
Utilizando a linguagem padr˜ao de acesso, o SQL, as outras camadas solicitam os
dados, que s˜ao retornados utilizando recursos da linguagem Java. Desta forma, as camadas
superiores n˜ao precisam obter informa¸c˜oes da implementa¸c˜ao dos bancos de dados. Este
esquema permite tamb´em que seja incorporado suporte a outros SGBDs sem altera¸c˜oes
nos demais m´odulos do sistema.
A conex˜ao com os bancos de dados ´e feita utilizando o JDBC - Java Database Connec-
tivity - um componente da linguagem Java que possui suporte para os principais SGBDs
relacionais encontrados no mercado.
3.3.3 Gerenciador de Ontologias
As ontologias utilizadas para classificar os dados do sistema s˜ao gerenciadas neste
m´odulo. Este m´odulo tem a tarefa de carregar as ontologias, as quais s˜ao armazenadas
em um arquivo OWL [44] e responder as solicita¸c˜oes do m´odulo Interpretador, retornando
as ontologias e suas rela¸c˜oes. Utilizando ontologias pr´e-definidas - as quais podem ser
encontradas em diversas fontes, como por exemplo, [46] - o sistema deve armazenar e
fornecer as ontologias quando requisitadas por outra camada.
Como as ontologias tendem a ser muito especializadas e em grande n´umero, utiliz´a-
las todas pode diminuir o desempenho do sistema, j´a que os bons caminhos encontrados
3.3 Material e M´etodo 37
seriam limitados e muito especializados. Para contornar este problema, s˜ao utilizadas
apenas algumas classes da ontologia, aquelas mais gerais e que permitem um melhor
aproveitamento da estrat´egia de roteamento. A este grupo de classes selecionadas na
ontologia nomeou-se de ontologias rote´aveis. Para ilustrar este processo pode-se utilizar,
por exemplo, uma ontologia relacionada ao cˆancer. No processo de classifica¸c˜ao do banco
de dados, poderiam obter-se classifica¸c˜oes espec´ıficas de tabelas e atributos espec´ıficos.
Por exemplo, localmente ter-se-ia uma tabela somente com casos de cˆancer de estˆomago,
classificada com a ontologia espec´ıfica ’Cancer de Estomago’. Mas em outro n´o do sistema,
todos os casos de cˆancer do sistema digest´orio estariam em uma mesma tabela, sendo esta
classificada com a ontologia mais geral ’Cancer Sistema Digestorio’. Utilizando as classes
mais espec´ıficas da ontologia, n˜ao seria configurado um caminho entre os n´os que possuem
as classes citadas. Utilizando o processo proposto, ser˜ao utilizadas apenas as classes mais
superiores, que s˜ao mais gerais e possuem uma abrangˆencia maior. Sendo assim, se em
ambos os casos for listada a classe ’Cancer Sistema Digestorio’, ser´a criada uma rela¸c˜ao
semˆantica e um caminho no sistema de roteamento entre os dois n´os. Neste m´odulo ´e
realizada esta substitui¸c˜ao das ontologias listadas pelas ontologias rote´aveis equivalentes.
3.3.4 Interpretador SQL / Ontologias
O m´odulo interpretador ´e respons´avel pela liga¸c˜ao semˆantica entre as consultas SQL
e as ontologias. Este m´odulo deve interpretar tanto consultas SQL, obtendo as ontologias
referentes, quanto mapear as consultas e ontologias recebidas de outros n´os para analisar
se possuir informa¸c˜oes relevantes `a consulta localmente. As informa¸c˜oes das ontologias
s˜ao obtidas atrav´es do gerenciador de ontologias, no qual est˜ao as associa¸c˜oes dos bancos
de dados com as ontologias.
Neste m´odulo prevˆe-se a implementa¸c˜ao da etapa de mapeamento das consultas, ou
seja, associa¸c˜ao e convers˜ao da consulta recebida de outro n´o em uma consulta relacionada
aos dados locais. Este processo n˜ao foi implementado por tratar-se de uma etapa de grande
complexidade, a qual n˜ao ´e foco do trabalho atual. Sendo assim, quando ´e recebida uma
3.3 Material e M´etodo 38
consulta de outro n´o, neste m´odulo ´e efetuada apenas a verifica¸c˜ao da existˆencia ou n˜ao
de dados semanticamente relacionados aos da consulta em quest˜ao, atrav´es da ontologia
associada.
Quando uma consulta est´a sendo originada no computador local, este m´odulo recebe
a consulta SQL e associa a cada elemento uma ou mais ontologias, de acordo com as
regras de associa¸c˜ao que foram definidas. Um simples mapeamento das ontologias de uma
consulta pode ser visto no exemplo a seguir:
SELECT campo FROM tabela;
campo -> relacionado `a classe ”onto9284 -> Ontologia rote´avel ”Onto92 ”
tabela -> relacionada `a classe ”onto928 -> Ontologia rote´avel ”Onto92 ”
No caso do uso do ”*”para indicar todos os atributos de uma tabela, o interpretador
deve listar as ontologias relacionadas a cada um dos atributos da tabela em quest˜ao.
SELECT * FROM tabela;
tabela (campo1, campo2, campo3)
campo1 -> relacionado `a classe ”onto8475 -> Ontologia rote´avel ”Onto84 ”
campo2 -> relacionado `a classe ”onto8433 -> Ontologia rote´avel ”Onto84 ”
campo3 -> relacionado `a classe ”onto8543 -> Ontologia rote´avel ”Onto85 ”
tabela -> relacionada `a classe ”onto845 -> Ontologia rote´avel ”Onto84 ”
Ap´os criar a lista de ontologias, o interpretador dispara o processo de busca no m´odulo
de gerenciamento da rede peer-to-peer, passando a consulta SQL e as ontologias listadas
como parˆametro.
3.3.5 Gerenciador Peer-to-Peer
O foco principal deste trabalho foi nesta camada do sistema, especificamente na etapa
de roteamento. Toda comunica¸c˜ao com outros integrantes da rede ´e realizada atrav´es
deste m´odulo. As tarefas desempenhadas s˜ao:
3.3 Material e M´etodo 39
∙ Uni˜ao `a rede - para iniciar suas atividades junto `a rede, um n´o deve estabelecer
conex˜ao com alguns outros n´os, que passar˜ao a ser seus vizinhos;
∙ Envio de nova consulta - Ap´os conectar-se `a rede, o usu´ario est´a apto a submeter
suas pr´oprias consultas ao sistema;
∙ Envio de resposta para consultas recebidas - As consultas enviadas por outros usu´a-
rios s˜ao recebidas nesta camada e repassadas aos m´odulos respons´aveis. As respostas
obtidas no sistema s˜ao ent˜ao enviadas ao n´o que solicitou a busca;
∙ Encaminhamento de consultas recebidas - Quando recebe uma consulta, al´em de
respondˆe-la quando poss´ıvel, o par deve repass´a-la aos seus vizinhos, seguindo a
estrat´egia de roteamento adotada;
∙ Atualiza¸c˜ao das informa¸c˜oes de roteamento - Esta tarefa ´e essencial para manter a
eficiˆencia da estrat´egia de roteamento adotada. Toda vez que uma resposta positiva
´e encontrada nas bases locais, ou quando o n´o faz parte de um caminho at´e um
local com respostas positivas, a tabela de roteamento deve ser atualizada, atrav´es
dos n´ıveis de feromˆonio estabelecidos para cada par caminho/ontologia.
3.3.6 Agentes de busca e roteamento
Ao utilizar os conceitos b´asicos do algoritmo de colˆonia de formigas, propˆos-se um sis-
tema de roteamento que define, ao longo do tempo, rotas boas para as consultas, baseado
nas ontologias envolvidas em cada consulta. Como o sistema de roteamento ´e baseado nos
conceitos do algoritmo de colˆonia de formigas, cada agente de descoberta utilizado ser´a
chamado de ”formiga”. Sendo assim, no sistema existem dois tipos de formiga:
∙ Formiga Exploradora - agente de descoberta, ou seja, a formiga que carrega consul-
tas.
∙ Formiga Oper´aria - agente de atualiza¸c˜ao, ou seja, a formiga que retorna ao n´o de
origem atualizando as informa¸c˜oes de roteamento.
3.3 Material e M´etodo 40
Uma formiga exploradora carrega informa¸c˜oes para identificar o n´o que iniciou a
busca, a lista de ontologias e a consulta selecionada, a lista de n´os pelos quais passou at´e
o momento atual e um identificador geral do processo de busca. J´a a formiga oper´aria
deve carregar apenas uma lista com as ontologias que obtiveram respostas positivas para
a atualiza¸c˜ao das tabelas de feromˆonio e o caminho que deve percorrer para retornar ao
n´o inicial da consulta.
3.3.7 Recebendo e encaminhando formigas exploradoras
Encaminhar as formigas exploradoras para o que se classifica como melhores vizinhos
´e essencial para que a consulta chegue aos n´os de maior interesse, com informa¸c˜oes im-
portantes para a busca. Tanto em processos de consulta iniciados localmente quanto na
tarefa de encaminhar as formigas exploradoras, o sistema segue a mesma estrat´egia de
roteamento.
Cada n´o da rede possui certo n´umero de vizinhos aos quais est´a ligado diretamente.
Para obter informa¸c˜oes de roteamento o n´o armazena uma tabela em que cada linha ´e
relacionada a um vizinho e cada coluna representa uma das ontologias rote´aveis. Nesta
tabela, exemplificada na Figura 17, s˜ao guardadas as informa¸c˜oes referentes ao feromˆonio
depositado no caminho entre o n´o em quest˜ao e cada um de seus vizinhos, para cada uma
das ontologias poss´ıveis de roteamento.
Figura 17: Tabela de roteamento (Vizinhos x Ontologias).
O sistema envia as consultas apenas para uma parte dos vizinhos. A defini¸c˜ao de
quais dever˜ao receber a consulta ´e baseada nos seguintes passos:
1. Para cada n´o ´e verificado o n´ıvel de feromˆonio das ontologias selecionadas. Inici-
3.3 Material e M´etodo 41
almente ´e criada uma lista dos vizinhos que possuem algum n´ıvel de feromˆonio da
ontologia em quest˜ao, a qual chamou-se de lista A e que cont´em n elementos. Os
vizinhos restantes s˜ao colocados em uma lista B;
2.
´
E definido que, em um primeiro passo, apenas uma quantidade pr´e-definida, K, de
vizinhos receber˜ao a consulta. Este parˆametro K deve ser escolhido com cuidado
pois tal escolha influencia diretamente na rela¸c˜ao entre o alcance das buscas e o
n´umero de resultados. Inicialmente o sistema define o valor de K como sendo a
metade da quantidade de vizinhos do n´o, por´em este parˆametro pode ser ajustado.
S˜ao selecionados ent˜ao os K vizinhos com maior n´ıvel de feromˆonio da lista A;
3. Os vizinhos que n˜ao possuem nenhuma indica¸c˜ao de feromˆonio, que est˜ao na lista
B, ser˜ao utilizados para a descoberta de caminhos ainda n˜ao explorados, conforme
detalhado na se¸c˜ao 3.3.8.
Cada formiga enviada a um n´o carrega consigo a lista das ontologias que deve buscar
no seu caminho. Quando um n´o recebe uma formiga exploradora, este deve criar um
processo de busca local, o qual recebe como parˆametros a lista de ontologias e a consulta
enviada, conforme descrito na se¸c˜ao 3.3.10. Este processo retorna se no n´o atual existem
informa¸c˜oes relevantes `a consulta. Caso este retorno seja positivo, ´e criada uma formiga
oper´aria para retornar ao n´o que originou a consulta. Para evitar que as formigas ex-
ploradoras caminhem indefinidamente pelo sistema, ´e definido um tempo de vida - TTL
- limitado, o qual deve ser balanceado com base no tamanho da rede, alcance desejado,
tempo e n´umero de respostas obtidas. Como a estrat´egia de roteamento apresentada visa
enviar as formigas apenas para caminhos com bom hist´orico de resultados, o tempo de
vida utilizado pode ser alto que mesmo assim n˜ao dever´a haver o excesso de mensagens
trafegando na rede.
3.3 Material e M´etodo 42
3.3.8 Busca de novos caminhos
A cada consulta realizada n˜ao apenas os caminhos j´a definidos como bons devem ser
utilizados, mas tamb´em deve ser poss´ıvel encontrar novos caminhos para n´os ainda n˜ao
descobertos. Devido ao aspecto dinˆamico da rede, esta op¸c˜ao de descobrir novos caminhos
´e ´util, pois entre uma consulta e outra, muitos n´os podem ter entrado e muitos podem
ter sa´ıdo da rede. Assim, ´e poss´ıvel que bons caminhos da primeira consulta j´a n˜ao levem
a n´os com informa¸c˜oes relevantes e caminhos antes vistos como n˜ao interessantes para
determinada ontologia podem conter novos n´os com dados de interesse.
Figura 18: Caminho P1 at´e P11 com informa¸c˜oes relevantes.
Por exemplo, analisando a rede apresentada na Figura 18, suponha que o n´o P1 inicia
uma consulta, que obt´em bons resultados em P11. Portanto, o caminho P1>P3>P6>P11
ser´a preenchido com um n´ıvel inicial de feromˆonio. Agora considere que, ap´os esta con-
sulta, o n´o P11 desligou-se e outro n´o, P8, entrou na rede.
Figura 19: Novo n´o com bons resultados.
3.3 Material e M´etodo 43
Ao realizar novamente uma consulta com a mesma base de ontologias da primeira,
seguir o caminho com um bom n´ıvel de feromˆonio apresentado anteriormente j´a n˜ao ´e
interessante, enquanto outro caminho, P1>P4>P7>P8, apresentado na Figura 19, ainda
n˜ao foi verificado e pode obter bons resultados em P8.
Para garantir que exista a possibilidade de explorar novos caminhos, dever´a sempre
ser criada no m´ınimo uma formiga exploradora que ser´a enviada a um vizinho da lista B.
Entretanto este n´umero pode ser maior, como nos casos onde a lista A n˜ao cont´em vizinhos
suficientes para atingir a quantidade m´ınima (K ) determinada no sistema. A escolha dos
n´os na lista B que receber˜ao a consulta ´e realizada aleatoriamente, garantindo que todos
os n´os tˆem a mesma probabilidade de receber tal consulta. Este comportamento aleat´orio
faz parte dos conceitos do algoritmo de otimiza¸c˜ao por colˆonia de formigas [28], pois segue
o princ´ıpio do comportamento das formigas em que estas saem sem nenhuma informa-
¸c˜ao pr´evia neste processo de busca de novos caminhos. Portanto ser˜ao aleatoriamente
escolhidos, na lista B:
-> 1 vizinho, se n >= K
-> (1+(K-n)) vizinhos, se n < K
3.3.9 Atualiza¸c˜ao da tabela de roteamento
Uma formiga oper´aria ir´a carregar a lista das ontologias que obtiveram retorno positivo
no n´o que a criou e o caminho completo que a formiga exploradora percorreu desde o n´o
inicial da consulta at´e ali. Percorrendo o caminho reverso, tal formiga ir´a informar aos
n´os que devem atualizar os n´ıveis de feromˆonio para determinado vizinho. Por exemplo,
suponha que uma formiga exploradora seguiu o caminho P1>P3>P6 e encontrou bons
resultados em P6. Ali ser´a criada uma formiga oper´aria que percorrer´a o caminho reverso
e informar´a ao n´o P3 que deve atualizar os n´ıveis de feromˆonio do vizinho P6 para as
ontologias que obtiveram sucesso. E, do mesmo modo, avisar´a que P1 deve atualizar o
n´ıvel de feromˆonio do vizinho P3 referente a cada uma das referidas ontologias.
3.3 Material e M´etodo 44
3.3.10 Processo de uma consulta
O processo de consulta aos dados ´e a principal tarefa desempenhada no sistema.
Ap´os conectar-se `a rede, o usu´ario pode realizar consultas tanto localmente quanto nos
bancos compartilhados pelos outros usu´arios. Quando uma consulta SQL ´e criada, esta
´e enviada ao m´odulo gerenciador de acesso aos dados e ao m´odulo interpretador. No
m´odulo de acesso aos dados a consulta ser´a processada na base de dados local, retornando
os resultados ao usu´ario.
No m´odulo interpretador, ser´a realizada a obten¸c˜ao das ontologias relacionadas `a
base de dados, tabelas e atributos envolvidos. Como foi visto, ´e criada uma lista com
as ontologias utilizadas para categorizar tais itens. Estas ontologias ser˜ao utilizadas no
processo de escolha dos caminhos que a consulta seguir´a na rede. A lista de ontologias e a
consulta original em SQL s˜ao enviadas ao m´odulo de gerenciamento da rede peer-to-peer
para serem encaminhadas aos outros n´os.
Quando ´e solicitado ao m´odulo de gerenciamento da rede peer-to-peer para iniciar
uma consulta, este deve empacotar todas as informa¸c˜oes e criar a primeira formiga explo-
radora, a qual ser´a copiada para cada vizinho escolhido para receber a consulta. Seguindo
a estrat´egia adotada, baseada no algoritmo de colˆonia de formigas, as c´opias da formiga
exploradora s˜ao enviadas aos vizinhos selecionados pelo algoritmo. Ao receber um pedido
de consulta de outro n´o, o sistema local verifica se possui informa¸c˜oes ligadas semantica-
mente `a consulta enviada. Caso possua, cria uma formiga oper´aria para retornar ao n´o
inicial da consulta seguindo o mesmo caminho percorrido at´e o n´o atual, conforme j´a foi
visto. Independente de possuir informa¸c˜oes relevantes `a consulta, o n´o deve repass´a-la
aos seus vizinhos, seguindo a mesma estrat´egia de roteamento adotada no n´o inicial da
consulta.
3.3 Material e M´etodo 45
3.3.11 Exemplo de funcionamento
Para compreender melhor o funcionamento desta estrat´egia de roteamento, ser´a apre-
sentado um exemplo de uma busca passo a passo. Para ilustrar os dois tipos diferentes
de formigas ser˜ao usados os desenhos da Figura 20(a) para a formiga exploradora e da
Figura 20(b) para a formiga oper´aria. Considere um sistema com a configura¸c˜ao apresen-
tada na Figura 21(a). As linhas representam que um n´o ´e vizinho do outro. A linha em
vermelho indica que ali existe certo n´ıvel de feromˆonio para uma classe-exemplo de uma
ontologia, nomeada aqui de ”ontoA”. Quanto mais grossa a linha vermelha, maior o n´ıvel
de feromˆonio. Para este exemplo definiu-se o K como um, portanto a formiga exploradora
sempre ´e enviada para no m´aximo dois vizinhos: um da lista A e um da lista B. Como
esta rede est´a em seu estado inicial e n˜ao possui nenhuma informa¸c˜ao de feromˆonio, todos
vizinhos fazem parte da lista B. Neste exemplo o n´o P1 inicia uma busca. Como ainda n˜ao
possui nenhuma informa¸c˜ao de feromˆonio, seleciona aleatoriamente dois de seus vizinhos,
enviando formigas exploradoras com a ontologia ”ontoA” aos n´os P2 e P4.
(a) (b)
Figura 20: Desenhos representativos das formigas.
Em P4 s˜ao encontradas informa¸c˜oes relacionadas `a ontologia ”ontoA”. Sendo assim
P4 cria uma formiga oper´aria que ir´a retornar a P1 e atualizar o n´ıvel de feromˆonio para
a ontologia e o vizinho em quest˜ao, processo ilustrado na Figura 21(b). Ao mesmo tempo,
P4 e P2 est˜ao replicando as formigas exploradoras recebidas para repass´a-las aos seus vi-
zinhos. Este processo segue repetindo-se a cada n´o, como pode ser observado nas Figuras
21(c) e 21(d). Mesmo ap´os o t´ermino da replica¸c˜ao das formigas exploradoras, algumas
formigas oper´arias continuam retornando e atualizando as tabelas de roteamento, con-
forme demonstrado nas Figuras 22(a) a 22(d) Quando uma formiga oper´aria retorna por
3.3 Material e M´etodo 46
um caminho que j´a possui algum n´ıvel de feromˆonio para a ontologia ”ontoA”, esta refor¸ca
esta quantidade de feromˆonio, o que ´e representado na figura com linhas mais grossas.
Na configura¸c˜ao final, exibida na Figura 22(d), obtem-se uma rede com informa¸c˜oes de
poss´ıveis boas rotas para a ontologia ”ontoA”. Se, por exemplo, P2 iniciar uma busca
tamb´em com a ontologia em quest˜ao, ele saber´a que existe uma maior probabilidade de
encontrar bons resultados em P9 do que em P5.
Este exemplo mostra apenas uma rede limitada com onze n´os e apenas uma ontologia
no processo. Em uma rede real, com milhares de n´os e centenas de buscas ocorrendo
simultaneamente, espera-se obter uma rede com in´umeras informa¸c˜oes de bons caminhos
a seguir, possibilitando melhorias no desempenho das consultas conforme o tempo de vida
da rede cresce.
3.3 Material e M´etodo 47
(a)
(b)
(c)
(d)
Figura 21: Exemplo de formigas caminhando - Parte 1.
3.3 Material e M´etodo 48
(a)
(b)
(c)
(d)
Figura 22: Exemplo de formigas caminhando - Parte 2.
49
4 Experimentos e Avalia¸c˜ao
Neste cap´ıtulo s˜ao apresentados alguns resultados de experimentos realizados com
o sistema, bem como compara¸c˜oes entre os resultados obtidos para averiguar o desem-
penho da estrat´egia de roteamento proposta neste trabalho. Para avaliar as diferen¸cas
de desempenho, cada experimento foi realizado duas vezes, sendo uma sem a utiliza¸c˜ao
da estrat´egia de roteamento e outra utilizando tal proposta. Nas se¸c˜oes seguintes s˜ao
apresentados os resultados.
4.1 Estrutura dos experimentos
Para os experimentos no sistema foram criadas duas redes peer-to-peer utilizando
os computadores dispon´ıveis no laborat´orio de pesquisas do Grupo de Banco de Dados
da UNESP de S˜ao Jos´e do Rio Preto. A primeira rede, com dezesseis n´os, possui a
estrutura apresentada na Figura 23. Uma segunda rede, com trinta e dois n´os, tamb´em
foi constru´ıda para os testes. Cada n´o executou uma c´opia idˆentica do sistema, apenas
com modifica¸c˜oes nos dados e configura¸c˜oes locais.
4.2 Ontologia
Para a a execu¸c˜ao dos experimentos no sistema foi utilizada uma ontologia da ana-
tomia humana denominada Modelo Fundamental da Anatomia - Foundational Model of
Anatomy [47] -, definida pelo Structural Informatics Group da Universidade de Washing-
ton. Para simplificar e facilitar o controle da execu¸c˜ao dos experimentos foi utilizado
4.2 Ontologia 50
Figura 23: Rede peer-to-peer com 16 n´os.
apenas um subconjunto desta ontologia, o qual realiza uma categoriza¸c˜ao da anatomia
humana baseada nos diversos sistemas - respirat´orio, circulat´orio, entre outros.
Cada termo desta ontologia possui um identificador ´unico, o qual foi utilizado como
referˆencia para cada elemento. Nesta ontologia foi definido que apenas as classes dire-
tamente filhas da classe principal ”20394 - Human Body” na hierarquia seriam parte das
ontologias rote´aveis. A lista das ontologias rote´aveis com seus respectivos identificadores
´e apresentada na Tabela 2. Tanto o subconjunto completo da ontologia quanto a especifi-
ca¸c˜ao das ontologias rote´aveis est˜ao no Apˆendice 1. Para os experimentos foi definido um
subconjunto destas classes da ontologia para cada n´o, simulando o resultado do processo
de categoriza¸c˜ao das bases locais.
Ap´os a execu¸c˜ao do primeiro experimentos com a rede de dezesseis n´os, foram anali-
sadas as tabelas de roteamento obtidas para verificar a atribui¸c˜ao dos n´ıveis de feromˆonio
aos caminhos. Na Figura 24 ´e apresentado um exemplo de todos os n´ıveis de feromˆonio
maiores que zero presentes na tabela de roteamento do n´o T3, obtidos ap´os a execu¸c˜ao do
primeiro experimentos. Nesta Figura est´a ilustrado o resultado da cria¸c˜ao de caminhos
4.3 An´alise de Desempenho 51
ID Nome da classe
7482 Musculoskeletal system
7157 Nervous system
7158 Respiratory system
7152 Alimentary system
7159 Urinary system
7160 Genital system
9668 Endocrine system
78499 Sense organ system
79063 Deep Fascial system
79644 Stomatognathic system
74562 Hemolymphoid system
7161 Cardiovascular system
72979 Integumentary system
Tabela 2: Tabela de ontologias rote´aveis dos experimentos.
diferentes para cada ontologia. Uma figura ´unica indicando todos os caminhos tornou-se
ileg´ıvel e, portanto, foi omitida.
Figura 24: N´ıveis de feromˆonio das classes da ontologia para caminhos saindo do n´o T3.
4.3 An´alise de Desempenho
Para a an´alise dos experimentos foram contabilizadas as m´etricas referentes `a quan-
tidade de mensagens de busca enviadas e a quantidade m´edia de respostas obtidas por
consulta. As mensagens de buscas ainda foram separadas em in´editas, que s˜ao as que
4.3 An´alise de Desempenho 52
carregam uma busca ainda n˜ao processada pelo n´o, e duplicadas, as quais s˜ao descartadas
assim que s˜ao recebidas por tratarem de buscas j´a processadas.
Cada consulta executada no sistema consiste na simula¸c˜ao de um comando ”SELECT”
no n´o que a iniciou, envolvendo uma ou mais classes diferentes da ontologia. As classes
envolvidas s˜ao analisadas e convertidas, quando necess´ario, `as ontologias rote´aveis. Cada
etapa dos experimentos consistiu em enviar um determinado n´umero de consultas na rede,
com intervalos de tempo diversos, sendo os mesmos passos executados tanto para o sistema
sem a estrat´egia de otimiza¸c˜ao como ap´os a inser¸c˜ao de tal estrat´egia.
4.3.1 Desempenho sem tempo de vida
Uma primeira etapa de experimentos consistiu em v´arias execu¸c˜oes sem a defini¸c˜ao de
um tempo de vida para as mensagens na rede. Com isso, nos experimentos executando a
t´ecnica da inunda¸c˜ao sem a estrat´egia de roteamento cada consulta alcan¸ca todos os n´os
da rede. Para os casos em que a otimiza¸c˜ao por colˆonia de formigas (ACO) ´e utilizada,
foi definido que deve ser escolhido um vizinho da lista A - lista de vizinhos com algum
n´ıvel de feromˆonio - e um vizinho da lista de desconhecidos. No gr´afico da Figura 25
s˜ao apresentados os n´umeros de mensagem enviadas na rede, tanto no total quanto as
in´editas, para os experimentos com 40, 80, 160, 480 e 640 consultas sendo executadas
em uma rede com dezesseis n´os. Neste gr´afico torna-se vis´ıvel a diferen¸ca entre a curva
de crescimento do n´umero de mensagens trafegando na rede com e sem a estrat´egia de
colˆonia de formigas, bem como a diferen¸ca entre essa quantidade total e a quantidade de
mensagens in´editas.
Ao mesmo tempo em que o n´umero de mensagens ´e reduzido ´e desej´avel que a quan-
tidade de resultados obtidos permane¸ca semelhante `a quantidade obtida sem otimiza¸c˜ao.
No gr´afico da Figura 26 ´e mostrado que em todos os casos o n´umero m´edio de respostas
obtidas por consulta permaneceu bem pr´oximo.
Para a rede com trinta e dois n´os o desempenho foi semelhante. Na execu¸c˜ao dos ex-
4.3 An´alise de Desempenho 53
Figura 25: Tr´afego na rede de 16 n´os sem TTL.
Figura 26: N´umero m´edio de respostas por consulta na rede de 16 n´os sem TTL.
perimentos utilizando a estrat´egia de roteamento por colˆonia de formigas foi definido que
seriam escolhidos dois vizinhos da lista A e um vizinho da lista B de caminhos desconheci-
dos. Acompanhando o gr´afico da Figura 27 pode-se notar a diferen¸ca entre a quantidade
de mensagens enviadas com e sem o algoritmo de colˆonia de formigas, bem como pode-se
observar a manuten¸c˜ao da proximidade na m´edia de resultados obtidos em ambos os casos
na Figura 28.
4.3 An´alise de Desempenho 54
Figura 27: Tr´afego na rede de 32 n´os sem TTL.
Figura 28: N´umero m´edio de respostas por consulta na rede de 32 n´os sem TTL.
4.3.2 Desempenho com tempo de vida definido
Como ´e conhecido, em uma rede peer-to-peer real, com milhares de n´os, torna-se
impratic´avel a utiliza¸c˜ao do algoritmo de inunda¸c˜ao sem a defini¸c˜ao de um tempo de
vida para as mensagens. Sendo assim, nesta etapa foram executados testes seguindo os
mesmos passos da etapa anterior, inclusive mantendo as consultas, as classes da ontologia
4.3 An´alise de Desempenho 55
envolvidas em cada consulta e a configura¸c˜ao da rede, por´em com o tempo de vida das
mensagens definido.
Para os experimentos da rede com dezesseis n´os foi estabelecido o tempo de vida com
o valor trˆes. Ap´os a execu¸c˜ao dos experimentos notou-se que houve uma redu¸c˜ao de cerca
de 50 % das mensagens trafegadas na rede quando comparada aos testes sem tempo de
vida definido, por´em mantendo-se a devida propor¸c˜ao, as diferen¸cas entre o desempenho
com e sem a estrat´egia de roteamento se manteve, como pode ser observado na Figura 29.
Figura 29: Tr´afego na rede de 16 n´os com TTL 3.
Com a redu¸c˜ao do alcance das mensagens de busca ocorre tamb´em a redu¸c˜ao na m´edia
de respostas obtidas por consulta. Como pode ser observado na Figura 30, as m´edias
ca´ıram para cerca de duas respostas por consulta, por´em manteve-se a proximidade entre
os casos com e sem a estrat´egia de roteamento.
Os experimentos com a rede de trinta e dois n´os foram executados seguindo o mesmo
processo dos testes anteriores, por´em o tempo de vida foi definido como sendo cinco
”saltos”. Assim como nos testes com a rede de dezesseis n´os, nesta etapa de testes tamb´em
ocorreu uma redu¸c˜ao no n´umero de mensagens trafegando, por´em essa redu¸c˜ao foi um
pouco menor, cerca de 35 %, como pode ser observado na Figura 31. O n´umero m´edio
de respostas obtidas tamb´em foi reduzido, ficando entre 3,5 e 5 para todos os testes,
4.3 An´alise de Desempenho 56
Figura 30: N´umero m´edio de respostas por consulta na rede de 16 n´os com TTL 3.
conforme ´e demonstrado na Figura 32.
Figura 31: Tr´afego na rede de 32 n´os com TTL 5.
Para demonstrar o ganho obtido com a inser¸c˜ao da estrat´egia de roteamento proposta
neste trabalho foi realizada mais uma etapa de experimentos. O objetivo desta etapa foi
verificar a possibilidade de utilizar a estrat´egia de roteamento com colˆonia de formigas
para diminuir o tr´afego na rede ao mesmo tempo em que obt´em um maior n´umero de
4.3 An´alise de Desempenho 57
Figura 32: N´umero m´edio de respostas por consulta na rede de 32 n´os com TTL 5.
resultados para as consultas do banco de dados peer-to-peer ao alcan¸car um n´umero maior
de n´os. Para tal avalia¸c˜ao foi comparado o desempenho da execu¸c˜ao dos experimentos
nas seguintes configura¸c˜oes do sistema:
∙ Sem a utiliza¸c˜ao da estrat´egia de roteamento e com um tempo de vida pequeno;
∙ Com a utiliza¸c˜ao da estrat´egia de roteamento e o dobro do tempo de vida para as
mensagens.
Nos experimentos da rede com dezesseis n´os foram utilizados os resultados obtidos
previamente na execu¸c˜ao sem a utiliza¸c˜ao de colˆonia de formigas e com tempo de vida
igual a trˆes, al´em de novos experimentos executados utilizando colˆonia de formigas e
tempo de vida igual a seis. Acompanhando o gr´afico da Figura 33 ´e poss´ıvel observar que
o n´umero de mensagens trafegando na rede em ambos os casos permaneceu semelhante,
mesmo que o tempo de vida das mensagens nos testes com a utiliza¸c˜ao de colˆonia de
formigas seja o dobro dos testes sem a inser¸c˜ao desta otimiza¸c˜ao.
Por´em ao analisar a compara¸c˜ao entre a m´edia de resultados obtidos por consulta,
apresentada na Figura 34, pode-se observar que os experimentos com a inser¸c˜ao da otimi-
4.3 An´alise de Desempenho 58
Figura 33: Comparativo de tr´afego na rede de 16 n´os.
za¸c˜ao por colˆonia de formigas obtiverem valores maiores em todos os casos. Este aumento
representa um ganho m´edio de 18% na quantidade de resultados obtidos por consulta.
Figura 34: Comparativo de respostas na rede de 16 n´os.
A mesma estrutura de experimentos foi utilizada na rede com trinta e dois n´os.
Aproveitou-se os resultados dos experimentos anteriores sem a estrat´egia de roteamento
com colˆonia de formigas e com tempo de vida cinco. Novos experimentos foram executa-
dos com o sistema utilizando a otimiza¸c˜ao por colˆonia de formigas e tempo de vida dez.
4.3 An´alise de Desempenho 59
Conforme observado nos resultados apresentados na Figura 35, os dois casos seguiram
uma mesma tendˆencia de crescimento no n´umero de mensagens trafegando na rede.
Figura 35: Comparativo de tr´afego na rede de 32 n´os.
Assim como nos experimentos da rede com dezesseis n´os, os resultados dos experi-
mentos mostram que nesta rede tamb´em obteve-se um ganho na quantidade de respostas
obtidas por consulta executado no banco de dados peer-to-peer, conforme ´e apresentado
na Figura 36. Neste experimentos o aumento m´edio na quantidade de respostas obtidas
por consulta foi ainda maior, de 22,5%.
Os resultados apresentados neste cap´ıtulo demonstraram que, para os experimentos
realizados, a inser¸c˜ao da otimiza¸c˜ao no roteamento utilizando colˆonia de formigas e on-
tologias para localiza¸c˜ao dos dados permite localizar eficientemente n´os com poss´ıveis
respostas para as consultas realizadas sem a necessidade de inundar a rede com um n´u-
mero grande de mensagens.
4.3 An´alise de Desempenho 60
Figura 36: Comparativo de respostas na rede de 32 n´os.
61
5 Conclus˜oes
Neste trabalho foi apresentada uma proposta de estrat´egia de roteamento em sistemas
de gerenciamento de dados em redes peer-to-peer, bem como toda a teoria envolvida no
desenvolvimento deste tipo de sistema.
Ao utilizar uma t´ecnica de roteamento baseada nos conceitos principais do algoritmo
de colˆonias de formigas para otimiza¸c˜ao de caminhos em redes atrelada `a classifica¸c˜ao
das informa¸c˜oes utilizando ontologias, buscou-se criar, ao longo do tempo, rotas para os
melhores n´os de cada ontologia relacionada. Com esta estrat´egia objetivou-se diminuir o
tr´afego de mensagens trafegando na rede sem ocasionar perdas na quantidade de respostas
obtidas.
Ap´os realizar os experimentos apresentados no Cap´ıtulo 4 mostrou-se que a intro-
du¸c˜ao da estrat´egia de roteamento utilizando colˆonia de formigas realmente melhorou o
desempenho do sistema, reduzindo o n´umero de mensagens enviadas na rede e mantendo
a quantidade de respostas obtidas nos experimentos sem a estrat´egia proposta. Al´em
disso mostrou-se que a utiliza¸c˜ao da estrat´egia de roteamento por colˆonia de formigas
e ontologias permitiu que as consultas sejam executadas com um tempo de vida maior.
Ao estabelecer um tempo de vida maior para as mensagens e encaminhar estas para os
caminhos com maior possibilidade de retornar bons resultados foi poss´ıvel aumentar o
alcance das buscas e permitir que um n´umero maior de resultados fosse encontrado sem
comprometer a rede na quest˜ao do tr´afego de mensagens.
Portanto, incorporar uma estrat´egia para otimiza¸c˜ao de roteamento das consultas
como o algoritmo de colˆonia de formigas e a categoriza¸c˜ao de dados por ontologias repre-
5.1 Trabalhos Futuros 62
senta uma contribui¸c˜ao no desenvolvimento de sistemas de bancos de dados peer-to-peer,
agregando t´ecnicas e tecnologias bem desenvolvidas para viabilizar a utiliza¸c˜ao deste tipo
de sistema.
5.1 Trabalhos Futuros
Para trabalhos futuros a primeira sugest˜ao ´e o desenvolvimento e incorpora¸c˜ao do
m´odulo de mapeamento das consultas utilizando ontologias, permitindo que as consultas
sejam efetivamente executadas e respondidas em qualquer n´o da rede. Este trabalho, junto
ao esquema de roteamento apresentado nesta disserta¸c˜ao, comp˜oe o n´ucleo principal de
um banco de dados peer-to-peer eficiente e vi´avel de ser implantado em um ambiente real.
Um aspecto importante que pode ser avaliado em um trabalho futuro ´e o tempo de
envio das consultas e obten¸c˜ao das respostas. A avalia¸c˜ao de tal aspecto do sistema pode
permitir uma melhor percep¸c˜ao da contribui¸c˜ao obtida com a estrat´egia de roteamento,
pois, com a redu¸c˜ao do tr´afego, o tempo de resposta tamb´em deve diminuir. Al´em disso,
analisando o tempo de respostas juntamente com a quantidade de respostas ´e poss´ıvel
trabalhar no balanceamento autom´atico dos parˆametros K - n´umero de vizinhos que
devem receber uma consulta - e TTL - tempo de vida. Um ajuste autom´atico destes
parˆametros poderia resultar em um melhor desempenho do sistema quanto ao tr´afego na
rede, tempo e quantidade de respostas.
Um ambiente para edi¸c˜ao e manuten¸c˜ao da ontologia utilizada no sistema ´e outro
trabalho futuro importante que pode ser proposto. Permitir que o usu´ario edite a ontologia
e que estas altera¸c˜oes sejam automaticamente propagadas `a rede toda, bem como seja feita
a atualiza¸c˜ao das rela¸c˜oes criadas entre a base de dados e a ontologia possibilitaria uma
maior flexibilidade no uso do sistema, tornando-o mais interessante ao usu´ario final.
Outra possibilidade de continua¸c˜ao deste trabalho ´e o desenvolvimento da interface
gr´afica, criando ambientes para a classifica¸c˜ao dos bancos de dados, bem como a imple-
menta¸c˜ao de melhorias nas telas de intera¸c˜ao com o usu´ario j´a presentes neste sistema.
5.1 Trabalhos Futuros 63
Uma interface amig´avel para a associa¸c˜ao o banco de dados com a ontologia, para a execu-
¸c˜ao de consultas e visualiza¸c˜ao dos resultados permitiria que mesmo usu´arios sem grande
conhecimento t´ecnico utilizassem o sistema e obtivessem resultados de grande valor.
64
Referˆencias
[1] SUNG, L. G. A. et al. A survey of data management in peer-to-peer systems. CS856
- Web Data Management, p. 1 – 50, 2005.
[2] BONIFATI, A. et al. Distributed databases and peer-to-peer databases: past and
present. ACM SIGMOD Record, ACM, New York, NY, USA, v. 37, n. 1, p. 5–11, 2008.
ISSN 0163-5808.
[3] YANG, B.; GARCIA-MOLINA, H. Improving search in peer-to-peer networks. In:
ICDCS ’02: Proceedings of the 22 nd International Conference on Distributed Com-
puting Systems (ICDCS’02). Washington, DC, USA: IEEE Computer Society, 2002.
p. 5.
[4] MICHLMAYR, E. Ant algorithms for search in unstructured peer-to-peer networks.
In: ICDEW ’06: Proceedings of the 22nd International Conference on Data Engineering
Workshops. Washington, DC, USA: IEEE Computer Society, 2006. p. 142–146.
[5] SHIRKY, C. What is p2p... and what isnt’t. Acessado em: 08 Agosto 2009. Dispon´ıvel
em: <http://www.oreillynet.com/pub/a/p2p/2000/11/24/shirky1-whatisp2p.html>.
[6] ANDROUTSELLIS-THEOTOKIS, S.; SPINELLIS, D. A survey of peer-to-peer con-
tent distribution technologies. ACM Computer Survey, ACM, New York, NY, USA,
v. 36, n. 4, p. 335–371, 2004.
[7] ABERER, K.; HAUSWIRTH, M. Tutorial: Peer-to-peer information systems: con-
cepts and models, state-of-the-art, end future systems. In: Proceedings of the 18th
International Conference on Data Engineering. San Jose: [s.n.], 2002.
[8] LEGOUT, A. et al. Clustering and sharing incentives in bittorrent systems. In: SIG-
METRICS ’07: Proceedings of the 2007 ACM SIGMETRICS international conference
on Measurement and modeling of computer systems. New York, NY, USA: ACM, 2007.
p. 301–312.
[9] KALNIS, P. et al. Answering similarity queries in peer-to-peer networks. Information
Systems, Elsevier Science Ltd., Oxford, UK, UK, v. 31, n. 1, p. 57–72, 2006.
[10] KOLONIARI, G.; PITOURA, E. Peer-to-peer management of xml data: issues and
research challenges. ACM SIGMOD Record, ACM, New York, NY, USA, v. 34, n. 2, p.
6–17, 2005.
[11] DREAMTECH, S. T. Peer-to-Peer Application Development: Cracking the code. New
York: Hungry Minds, 2001.
Referˆencias 65
[12] SALGADO, A. C.; PIRES, C. E. S.; L´oSCIO, B. F. Tutorial: Gerenciamento de
dados em sistemas p2p. In: XXI Simp´osio Brasileiro de Banco de Dados. Florian´opolis,
SC, Brasil: [s.n.], 2006.
[13] PENZO, W. et al. Semantic peer, here are the neighbors you want! In: EDBT ’08:
Proceedings of the 11th international conference on Extending database technology. New
York, NY, USA: ACM, 2008. p. 26–37.
[14] WIEDERHOLD, G. Mediators in the architecture of future information systems.
Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, p. 185–196, 1998.
[15] TATARINOV, I. et al. The piazza peer data management project. ACM SIGMOD
Record, ACM, New York, NY, USA, v. 32, n. 3, p. 47–52, 2003.
[16] NG, W. S. et al. Peerdb: A p2p-based system for distributed data sharing. In: Pro-
ceedings of the 19th International Conference on Data Engineering. [S.l.: s.n.], 2003. p.
633–644.
[17] TATARINOV, I.; HALEVY, A. Efficient query reformulation in peer data manage-
ment systems. In: SIGMOD ’04: Proceedings of the 2004 ACM SIGMOD international
conference on Management of data. New York, NY, USA: ACM, 2004. p. 539–550.
[18] GUPTA, A.; AGRAWAL, D.; ABBADI, A. E. Approximate range selection queries
in peer-to-peer systems. In: Proceedings of the First Biennial Conference on Innovative
Data Systems Research. Asilomar, California, USA: [s.n.], 2003.
[19] BELLAHS`eNE, Z.; ROANTREE, M. Querying distributed data in a super-peer based
architecture. In: Proceedings of the 15th International Conference on Database and
Expert Systems Applications. Zaragoza, Espanha: [s.n.], 2004. v. 15, p. 296–305.
[20] ARENAS, M. et al. The hyperion project: from data integration to data coordination.
ACM SIGMOD Record - Special Issue on Peer-to-Peer Data, ACM, New York, NY,
USA, v. 32, n. 3, p. 53–58, 2003.
[21] NG, W. S.; OOI, B. C.; TAN, K. lee. Bestpeer: A self-configurable peer-to-peer
system. In: ICDE ’02: Proceedings of the 18th International Conference on Data En-
gineering. Washington, DC, USA: IEEE Computer Society, 2002. p. 272.
[22] STOICA, I. et al. Chord: A scalable peer-to-peer lookup service for internet appli-
cations. In: SIGCOMM ’01: Proceedings of the 2001 conference on Applications, te-
chnologies, architectures, and protocols for computer communications. New York, NY,
USA: ACM, 2001. p. 149–160.
[23] MICHEL, S.; PARREIRA, J. X. Tutorial: Peer-to-peer information search. In: XXII
Simp´osio Brasileiro de Banco de Dados. Jo˜ao Pessoa, Para´ıba, Brasil: [s.n.], 2007.
[24] O’REILLY, T. et al. Peer-to-Peer: Harnessing the Power of Disruptive Technologies.
[S.l.]: O’Reilly Media, Fev. 2001.
[25] LV, Q. et al. Search and replication in unstructured peer-to-peer networks. In: ICS
’02: Proceedings of the 16th international conference on Supercomputing. New York,
NY, USA: ACM, 2002. p. 84–95.
Referˆencias 66
[26] COHEN, E.; FIAT, A.; KAPLAN, H. A case for associative peer to peer overlays.
ACM SIGCOMM Computer Communication Review, ACM, New York, NY, USA, v. 33,
n. 1, p. 95–100, 2003.
[27] JOSEPH, S.; HOSHIAI, T. Decentralized meta-data strategies: Effective peer-to-peer
search. IEICE Transactions on Communications, E86-B, n. 6, p. 1740–1753, 2003.
[28] CIGLARIC, M.; VIDMAR, T. Ant-inspired query routing performance in dynamic
peer-to-peer networks. Parallel and Distributed Processing Symposium, 20th Internati-
onal, IEEE Computer Society, Los Alamitos, CA, USA, v. 0, p. 287, 2006.
[29] DORIGO, M.; BLUM, C. Ant colony optimization theory: a survey. Theoretical
Computer Science, Elsevier Science Publishers Ltd., Essex, UK, v. 344, n. 2-3, p. 243–
278, 2005.
[30] DORIGO, M.; MANIEZZO, V.; COLORNI, A. The ant system: Optimization by a
colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics-
Part B, v. 26, p. 29–41, 1996.
[31] DORIGO, M.; GAMBARDELLA, L. M. Ant colony system: A cooperative lear-
ning approach to the traveling salesman problem. IEEE Transactions on Evolutionary
Computation, v. 1, p. 53–66, 1997.
[32] ZAFALON, G. F. D. Algoritmos de alinhamento m´ultiplo e t´ecnicas de otimiza¸c˜ao
para esses algoritmos utilizando Ant Colony. Disserta¸c˜ao (Mestrado - Ciˆencias da Com-
puta¸c˜ao) — Unesp - Universidade Estadual Paulista ”J´ulio Mesquita Filho”, S˜ao Jos´e
do Rio Preto, SP, Brasil, 2009.
[33] CARO, G. D.; DORIGO, M. Antnet: Distributed stigmergetic control for communi-
cations networks. Journal of Artificial Intelligence Research, v. 9, p. 317–365, 1998.
[34] GRUBER, T. R. A translation approach to portable ontology specifications. Kno-
wledge Acquisition, Academic Press Ltd., London, UK, UK, v. 5, n. 2, p. 199–220,
1993.
[35] BORST, W. N. Construction of engineering ontologies for knowledge sharing and
reuse. Tese (Doutorado) — Universidade de Tweenty, Enschede, Setembro 1997.
[36] STUDER, R.; BENJAMINS, V. R.; FENSEL, D. Knowledge engineering: Principles
and methods. Data and Knowledge Engineering, v. 25, p. 161–167, 1998.
[37] APAR
´
ICIO, A. S.; FARIAS, O. L. M.; SANTOS, N. dos. Applying ontologies in the
integration of heterogeneous relational databases. In: AOW ’05: Proceedings of the
2005 Australasian Ontology Workshop. Darlinghurst, Australia, Australia: Australian
Computer Society, Inc., 2005. p. 11–16.
[38] PEREZ, A. G.; BENJAMINS, V. R. Overview of knowledge sharing and reuse com-
ponents: Ontologies and problem-solving methods. In: Proceedings of the IJCAI-99
Workshop on Ontologies and Problem-Solving Methods. [S.l.: s.n.], 1999.
[39] HUANG, Y. Ontology-based Land Use Information Service on
the Semantic Web. Acessado em: 08 Agosto 2009. Dispon´ıvel em:
<http://www.ucgis.org/summer03/studentpapers/yuxiahuang.pdf>.
Referˆencias 67
[40] AFONSO, G. F. Integra¸c˜ao de dados baseada em ontologia. Disserta¸c˜ao (Mestrado -
Ciˆencias da Computa¸c˜ao) — Centro de Ciˆencias Exatas e de Tecnologia, Universidade
Federal de S˜ao Carlos, S˜ao Carlos, SP, Brasil, 2008.
[41] DOU, D.; LEPENDU, P. Ontology-based integration for relational databases. In:
SAC ’06: Proceedings of the 2006 ACM symposium on Applied computing. New York,
NY, USA: ACM, 2006. p. 461–466.
[42] CASANOVA, M. et al. Bancos de Dados Geogr´aficos. Cap 9 - Integra¸c˜ao e interope-
rabilidade entre fontes de dados geogr´aficos. MundoGEO, 2005. Acessado em: 08 Agosto
2009. Dispon´ıvel em: <http://www.dpi.inpe.br/gilberto/livro/bdados/cap9.pdf>.
[43] POTTINGER, R.; LEVY, A. Y. A scalable algorithm for answering queries using
views. In: VLDB ’00: Proceedings of the 26th International Conference on Very Large
Data Bases. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2000. p.
484–495.
[44] W3C, W. W. W. C. OWL Web Ontology Language. Acessado em: 08 Agosto 2009.
Dispon´ıvel em: <http://www.w3.org/TR/owl-guide/>.
[45] W3C, W. W. W. C. World Wide Web Consortium. Acessado em: 08 Agosto 2009.
Dispon´ıvel em: <http://www.w3.org>.
[46] PROT
´
EG
´
E. Prot´eg´e Ontologies. Acessado em: 08 Agosto 2009. Dispon´ıvel em:
<http://protege.stanford.edu/download/ontologies.html>.
[47] FMA, S. I. G. Foundational Model of Anatomy. Acessado em: 08 Agosto 2009. Dis-
pon´ıvel em: <http://sig.biostr.washington.edu/projects/fm/index.html>.
68
Apˆendice 1
Ontologia utilizada:
ID Nome da classe
20394 Human Body
7482 Musculoskeletal system
23881 Skeletal system
23878 Articular system
7484 Appendicular skeletal system
7483 Axial skeletal system
23875 Skeleton
46565 Skull
72954 Muscular system
7157 Nervous system
7158 Respiratory system
45662 Lower respiratoty tract
7393 Tracheobronchial tree
7195 Lung
9690 Pleural sac
7152 Alimentary system
54879 Oropharynx
71132 Gastrointestinal
7197 Liver
Tabela 3: Classes da Ontologia da Anatomia Humana
Apˆendice 1 69
ID Nome da classe
7202 Gallbladder
14665 Biliary tree
49177 Upper gastrointestinal tract
49179 Lower gastrointestinal tract
54879 Oropharynx
7131 Esophagus
7148 Stomach
7206 Duodenum
7207 Jejunum
7208 Ileum
14542 Appendix
14541 Cecum
14545 Ascending colon
14546 Transverse colon
14547 Descending colon
14548 Sigmoid colon
14544 Rectum
15703 Anal Canal
9908 Peritoneal sac
7198 Pancreas
15703 Anal canal
49184 Mouth
59399 Maxillary part of mouth
59398 Mandibular part of mouth
54640 Tongue
59992 Faucial part of mouth
Tabela 3: Classes da Ontologia da Anatomia Humana
Apˆendice 1 70
ID Nome da classe
55021 Soft palate
9597 Salivary gland
20292 Oral cavity
59815 Labial part of mouth
7159 Urinary system
45658 Upper urinary tract
7203 Kidney
9704 Ureter
71102 Right upper urinary tract
7204 Right kidney
15571 Right ureter
71103 Left upper urinary tract
7205 Left kidney
15572 Left ureter
45659 Lower urinary tract
15900 Urinary bladder
19667 Urethra
7160 Genital system
9668 Endocrine system
16018 Endocrine pˆancreas
62033 Pineal body
15648 Paraganglion
15647 Paraaortic body
13890 Parathyroid gland
55567 Accessory parathyroid gland
55559 Inferior pararthyroid gland
Tabela 3: Classes da Ontologia da Anatomia Humana
Apˆendice 1 71
ID Nome da classe
55563 Left inferior pararthyroid gland
55562 Right inferior pararthyroid gland
55558 Superior pararthyroid gland
55561 Left superior pararthyroid gland
55560 Right superior pararthyroid gland
7209 Ovary
7214 Left ovary
7213 Right ovary
9604 Adrenal gland
15630 Left adrenal gland
15629 Right adrenal gland
13889 Pituitary gland
9603 Thyroid gland
7210 Testis
7198 Pancreas
78499 Sense organ system
79063 Deep Fascial system
79644 Stomatognathic system
74562 Hemolymphoid system
74594 Lymphoid system
7162 Lymphatic system
74623 Non-lymphatic lymphoid system
9667 Hematopoietic system
7161 Cardiovascular system
7088 Heart
49894 Systemic arterial tree
Tabela 3: Classes da Ontologia da Anatomia Humana
Apˆendice 1 72
ID Nome da classe
45842 Pulmonary arterial tree
49895 Systemic venous tree organ
49907 Pulmonary venous tree organ
45847 Portal venous tree
65896 Right lymphatic duct tree
69050 Vasculature
45632 Capillary bed
69052 Venous tree cluster
69053 Lymphatic tree cluster
69051 Arterial tree cluster
72979 Integumentary system
74657 Integument
7163 Skin
9630 Superficial fascia
9598 Greater vestibular gland
20011 Right greater vestibular gland
20012 Left greater vestibular gland
Tabela 3: Classes da Ontologia da Anatomia Humana
Arquivo de defini¸c˜ao das ontologias rote´aveis:
<INICIO>
<ONTO>20394 <ROT>20394 </ONTO>
<ONTO>7482 <ROT>7482 </ONTO>
<ONTO>23881 <ROT>7482 </ONTO>
Apˆendice 1 73
<ONTO>23878 <ROT>7482 </ONTO>
<ONTO>7484 <ROT>7482 </ONTO>
<ONTO>7483 <ROT>7482 </ONTO>
<ONTO>23875 <ROT>7482 </ONTO>
<ONTO>46565 <ROT>7482 </ONTO>
<ONTO>72954 <ROT>7482 </ONTO>
<ONTO>7157 <ROT>7157 </ONTO>
<ONTO>7158 <ROT>7158 </ONTO>
<ONTO>45662 <ROT>7158 </ONTO>
<ONTO>7393 <ROT>7158 </ONTO>
<ONTO>7195 <ROT>7158 </ONTO>
<ONTO>9690 <ROT>7158 </ONTO>
<ONTO>7152 <ROT>7152 </ONTO>
<ONTO>71132 <ROT>7152 </ONTO>
<ONTO>7197 <ROT>7152 </ONTO>
<ONTO>7202 <ROT>7152 </ONTO>
<ONTO>14665 <ROT>7152 </ONTO>
<ONTO>49177 <ROT>7152 </ONTO>
<ONTO>49179 <ROT>7152 </ONTO>
<ONTO>7131 <ROT>7152 </ONTO>
<ONTO>7148 <ROT>7152 </ONTO>
<ONTO>7206 <ROT>7152 </ONTO>
<ONTO>7207 <ROT>7152 </ONTO>
<ONTO>7208 <ROT>7152 </ONTO>
<ONTO>14542 <ROT>7152 </ONTO>
<ONTO>14541 <ROT>7152 </ONTO>
<ONTO>14545 <ROT>7152 </ONTO>
<ONTO>14546 <ROT>7152 </ONTO>
Apˆendice 1 74
<ONTO>14547 <ROT>7152 </ONTO>
<ONTO>14548 <ROT>7152 </ONTO>
<ONTO>14544 <ROT>7152 </ONTO>
<ONTO>15703 <ROT>7152 </ONTO>
<ONTO>9908 <ROT>7152 </ONTO>
<ONTO>7198 <ROT>7152 </ONTO>
<ONTO>15703 <ROT>7152 </ONTO>
<ONTO>49184 <ROT>7152 </ONTO>
<ONTO>59399 <ROT>7152 </ONTO>
<ONTO>59398 <ROT>7152 </ONTO>
<ONTO>54640 <ROT>7152 </ONTO>
<ONTO>59992 <ROT>7152 </ONTO>
<ONTO>55021 <ROT>7152 </ONTO>
<ONTO>9597 <ROT>7152 </ONTO>
<ONTO>20292 <ROT>7152 </ONTO>
<ONTO>59815 <ROT>7152 </ONTO>
<ONTO>7159 <ROT>7159 </ONTO>
<ONTO>45658 <ROT>7159 </ONTO>
<ONTO>7203 <ROT>7159 </ONTO>
<ONTO>9704 <ROT>7159 </ONTO>
<ONTO>71102 <ROT>7159 </ONTO>
<ONTO>7204 <ROT>7159 </ONTO>
<ONTO>15571 <ROT>7159 </ONTO>
<ONTO>71103 <ROT>7159 </ONTO>
<ONTO>7205 <ROT>7159 </ONTO>
<ONTO>15572 <ROT>7159 </ONTO>
<ONTO>45659 <ROT>7159 </ONTO>
<ONTO>15900 <ROT>7159 </ONTO>
Apˆendice 1 75
<ONTO>19667 <ROT>7159 </ONTO>
<ONTO>7160 <ROT>7160 </ONTO>
<ONTO>9668 <ROT>9668 </ONTO>
<ONTO>16018 <ROT>9668 </ONTO>
<ONTO>62033 <ROT>9668 </ONTO>
<ONTO>15648 <ROT>9668 </ONTO>
<ONTO>15647 <ROT>9668 </ONTO>
<ONTO>13890 <ROT>9668 </ONTO>
<ONTO>55567 <ROT>9668 </ONTO>
<ONTO>55559 <ROT>9668 </ONTO>
<ONTO>55563 <ROT>9668 </ONTO>
<ONTO>55562 <ROT>9668 </ONTO>
<ONTO>55558 <ROT>9668 </ONTO>
<ONTO>55561 <ROT>9668 </ONTO>
<ONTO>55560 <ROT>9668 </ONTO>
<ONTO>7209 <ROT>9668 </ONTO>
<ONTO>7214 <ROT>9668 </ONTO>
<ONTO>7213 <ROT>9668 </ONTO>
<ONTO>9604 <ROT>9668 </ONTO>
<ONTO>15630 <ROT>9668 </ONTO>
<ONTO>15629 <ROT>9668 </ONTO>
<ONTO>13889 <ROT>9668 </ONTO>
<ONTO>9603 <ROT>9668 </ONTO>
<ONTO>7210 <ROT>9668 </ONTO>
<ONTO>7198 <ROT>9668 </ONTO>
<ONTO>78499 <ROT>78499 </ONTO>
<ONTO>79063 <ROT>79063 </ONTO>
<ONTO>79644 <ROT>79644 </ONTO>
Apˆendice 1 76
<ONTO>74562 <ROT>74562 </ONTO>
<ONTO>74594 <ROT>74562 </ONTO>
<ONTO>7162 <ROT>74562 </ONTO>
<ONTO>74623 <ROT>74562 </ONTO>
<ONTO>9667 <ROT>74562 </ONTO>
<ONTO>7161 <ROT>7161 </ONTO>
<ONTO>7088 <ROT>7161 </ONTO>
<ONTO>49894 <ROT>7161 </ONTO>
<ONTO>45842 <ROT>7161 </ONTO>
<ONTO>49895 <ROT>7161 </ONTO>
<ONTO>49907 <ROT>7161 </ONTO>
<ONTO>45847 <ROT>7161 </ONTO>
<ONTO>65896 <ROT>7161 </ONTO>
<ONTO>69050 <ROT>7161 </ONTO>
<ONTO>45632 <ROT>7161 </ONTO>
<ONTO>69052 <ROT>7161 </ONTO>
<ONTO>69053 <ROT>7161 </ONTO>
<ONTO>69051 <ROT>7161 </ONTO>
<ONTO>72979 <ROT>72979 </ONTO>
<ONTO>74657 <ROT>72979 </ONTO>
<ONTO>7163 <ROT>72979 </ONTO>
<ONTO>9630 <ROT>72979 </ONTO>
<ONTO>9598 <ROT>72979 </ONTO>
<ONTO>20011 <ROT>72979 </ONTO>
<ONTO>20012 <ROT>72979 </ONTO>
<FIM>
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
