@MASTERSTHESIS{ 2019:263881262,
 	title = {Caracterização teórica e limites assintóticos para o problema da geração de redes candidatas na busca por palavras-chave em bancos de dados relacionais},
 	year = {2019},
 	url = "https://tede.ufam.edu.br/handle/tede/7299",
 	abstract = "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.",
 	publisher = {Universidade Federal do Amazonas},
 	scholl = {Programa de Pós-graduação em Informática},
 	note = {Instituto de Computação}
}