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
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,...
| Autor principal: | Martinez, João Guilherme Alves |
|---|---|
| Outros Autores: | http://lattes.cnpq.br/1912876531070606 |
| Grau: | Dissertação |
| Idioma: | por |
| Publicado em: |
Universidade Federal do Amazonas
2019
|
| Assuntos: | |
| Acesso em linha: |
https://tede.ufam.edu.br/handle/tede/7299 |
| id |
oai:https:--tede.ufam.edu.br-handle-:tede-7299 |
|---|---|
| recordtype |
dspace |
| spelling |
oai:https:--tede.ufam.edu.br-handle-:tede-72992019-08-09T05:03:42Z 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 Theoretical characterization and asymptotic bounds for the candidate network generation problem in keyword search over relational databases Martinez, João Guilherme Alves Rodrigues, Rosiane de Freitas http://lattes.cnpq.br/1912876531070606 http://lattes.cnpq.br/8358219976594707 Moura, Edleno Silva de http://lattes.cnpq.br/4737852130924504 Protti, Fábio http://lattes.cnpq.br/5898801580033554 Banco de dados relacionais Sistemas de recuperação da informação Teoria dos grafos CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO Redes candidatas Busca por palavras-chave Banco de dados Complexidade computacional Teoria dos grafos 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. The search in collections of data using keyword queries (KwS) is an important field of study within Computer Science, which facilitates and accelerates the obtaining of rele- vant information. However, if on the one hand there was a great advance in the keywords search in web pages, which are heterogeneous bases mostly semi-structured, in relational databases still dominates the structured query elaborated with query languages such as SQL. Such databases do not allow queries for keywords directly, because it is necessary to know the schema that organizes the tables and to have technical knowledge in such lan- guages, factors that make the search process difficult. However, there are already systems that use query keywords and, transparently to the user, the relational database schema, to then internally mount appropriate SQL queries that return relevant responses to users (R-KwS). Such generated SQL queries are called Candidate Networks. The problem with such an approach is that the focus of such systems has been empirical and experimen- tal, highlighting a difficulty and high processing time in solving the Candidate Network Generation problem. Given this context, it is being proposed in this research a theoret- ical characterization of an R-KwS system, modeling it as a combination of two classic problems in graph theory, which are the Steiner Tree problem and the Edge Coloring problem, called the Steiner Tree with Colored Edges problem (STCEP). In this way, the viiiNP-completeness proof is presented for the general case where an arbitrary number of keywords is considered in the search, providing an NP algorithm and performing the polynomial reduction from the Exact Cover by 3-Sets problem (X3C) to the STCEP. Ad- ditionally, asymptotic polynomial boundaries were also determined for the practical case, when only a small fixed number of keywords were considered. Contrary to what the liter- ature up till now assumed to be true of the general case, it is demonstrated that in practice, the difficulty in terms of computational complexity does not occur. As a complementary result, the first implementation of the best approximation ratio algorithm for the problem of generation of all minimum spanning trees, the Eppstein [12] algorithm, was carried out, followed by the first implementation of the exact algorithm for the classical prob- lem of the Steiner tree in graphs, of polynomial delay for a fixed number of terminals, proposed by Dourado, Oliveira and Protti [8], and that uses the algorithm of Eppstein. Comparative analysis with the main algorithms of both problems, separately, were also performed. Finally, a new heuristic was developed for the classic problem of the Steiner tree in graphs, which presented a competitive performance in practice and that eliminates the exponential step of the algorithm of Dourado, Oliveira and Protti [8]. These results answer open questions in R-KwS systems, as well as contributions to the Steiner Tree problem in Graph Theory. 2019-08-08T13:17:07Z 2019-07-10 Dissertação MARTINEZ, João Guilherme Alves. 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. 2019. 77 f. Dissertação (Mestrado em Informática) - Universidade Federal do Amazonas, Manaus, 2019. https://tede.ufam.edu.br/handle/tede/7299 por Acesso Aberto application/pdf Universidade Federal do Amazonas Instituto de Computação Brasil UFAM Programa de Pós-graduação em Informática |
| institution |
TEDE - Universidade Federal do Amazonas |
| collection |
TEDE-UFAM |
| language |
por |
| topic |
Banco de dados relacionais Sistemas de recuperação da informação Teoria dos grafos CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO Redes candidatas Busca por palavras-chave Banco de dados Complexidade computacional Teoria dos grafos |
| spellingShingle |
Banco de dados relacionais Sistemas de recuperação da informação Teoria dos grafos CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO Redes candidatas Busca por palavras-chave Banco de dados Complexidade computacional Teoria dos grafos Martinez, João Guilherme Alves 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 |
| topic_facet |
Banco de dados relacionais Sistemas de recuperação da informação Teoria dos grafos CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO Redes candidatas Busca por palavras-chave Banco de dados Complexidade computacional Teoria dos grafos |
| description |
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. |
| author_additional |
Rodrigues, Rosiane de Freitas |
| author_additionalStr |
Rodrigues, Rosiane de Freitas |
| format |
Dissertação |
| author |
Martinez, João Guilherme Alves |
| author2 |
http://lattes.cnpq.br/1912876531070606 |
| author2Str |
http://lattes.cnpq.br/1912876531070606 |
| 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 |
| title_short |
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 |
| title_full |
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 |
| title_fullStr |
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 |
| title_full_unstemmed |
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 |
| title_sort |
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 |
| publisher |
Universidade Federal do Amazonas |
| publishDate |
2019 |
| url |
https://tede.ufam.edu.br/handle/tede/7299 |
| _version_ |
1831969785843286016 |
| score |
11.753735 |