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 - Martinez, João Guilherme Alves (Universidade Federal do Amazonas, 2019)
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.