A busca em coleções de dados utilizando consultas por palavras-chave (KwS) é um
importante campo de estudo dentro da Ciência da Computação, que facilita e acelera a
obtenção de informações relevantes. Entretanto, se por um lado houve um grande avanço
nas buscas por palavras-chave em páginas web, que são bases heterogêneas e em sua
maioria semi-estruturadas, nos bancos de dados relacionais ainda predomina a consulta
estruturada elaborada com linguagens de consultas como a SQL. Tais bancos de dados
não permitem que sejam feitas consultas por palavras-chave de forma direta, pois é ne-
cessário conhecer o esquema que organiza as tabelas e ter conhecimento técnico em tais
linguagens, fatores que dificultam o processo de busca. Entretanto, já existem sistemas
que utilizam palavras-chave da consulta e, de modo transparente ao usuário, o esquema
do banco de dados relacional, para então montar internamente consultas SQL adequa-
das que retornem as respostas relevantes para os usuários (R-KwS). Tais consultas em
SQL geradas são chamadas de Redes Candidatas. O problema com tal abordagem é que
o enfoque de tais sistemas tem sido empírico e experimental, onde ressaltam uma difi-
culdade e demora na resolução do problema de Geração das Redes Candidatas (CNGP).
Dado esse contexto, propõe-se nesta pesquisa uma caracterização teórica de sistemas R-
KwS, modelando-os como uma combinação de dois problemas clássicos em teoria dos
grafos, que são o problema da Árvore de Steiner e o problema de Coloração de Arestas,
videnominado de problema da Árvore de Steiner com Arestas Coloridas (STCEP). É apre-
sentada uma prova de NP-completude para o caso geral onde se considera um número
arbitrário de palavras-chave na busca, fornecendo-se um algoritmo NP e realizando-se
uma redução polinomial do problema da Cobertura Exata por 3-Conjuntos (X3C) para
o STCEP. Adicionalmente, também foram determinados limites polinomiais assintóticos
para o caso prático quando se considera apenas um pequeno número fixo de palavras-
chave. Diferentemente do que a literatura até então assumia como verdade do caso geral,
é demonstrado que, na prática, a dificuldade em termos de complexidade computacional
não ocorre. Como resultados complementares, foi realizada a primeira implementação do
algoritmo de melhor razão de aproximação para o problema da geração de todas as árvores
geradoras mínimas, o algoritmo de Eppstein [12], seguida da primeira implementação do
algoritmo exato para o problema clássico da árvore de Steiner de atraso polinomial para
um número fixo de terminais, proposto por Dourado, Oliveira e Protti [8] e que usa o algo-
ritmo de Eppstein. Análises comparativas com os principais algoritmos implementados de
ambos problemas, separadamente, foram também realizadas. Por fim, foi elaborada uma
nova heurística para o problema clássico da árvore de Steiner, que apresenta desempenho
competitivo na prática e que elimina o passo exponencial do algoritmo de Dourado, Oli-
veira e Protti [8]. Esses resultados respondem perguntas em aberto em sistemas R-KwS,
bem como constituem contribuições para o problema da Árvore de Steiner em Teoria dos
Grafos.
|
