Return to search

Generation and Ranking of Candidate Networks of Relations for Keyword Search over Relational Databases

Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-08-22T19:40:10Z
No. of bitstreams: 2
Tese - Péricles Silva de Oliveira.pdf: 1875380 bytes, checksum: 014ba89b7fe1929a1461c9d8d3959416 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-08-22T19:40:26Z (GMT) No. of bitstreams: 2
Tese - Péricles Silva de Oliveira.pdf: 1875380 bytes, checksum: 014ba89b7fe1929a1461c9d8d3959416 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-08-22T19:40:44Z (GMT) No. of bitstreams: 2
Tese - Péricles Silva de Oliveira.pdf: 1875380 bytes, checksum: 014ba89b7fe1929a1461c9d8d3959416 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-08-22T19:40:44Z (GMT). No. of bitstreams: 2
Tese - Péricles Silva de Oliveira.pdf: 1875380 bytes, checksum: 014ba89b7fe1929a1461c9d8d3959416 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Previous issue date: 2017-04-28 / Several systems proposed for processing keyword queries over relational databases rely on the
generation and evaluation of Candidate Networks (CNs), i.e., networks of joined database relations
that, when processed as SQL queries, provide a relevant answer to the input keyword
query. Although the evaluation of CNs has been extensively addressed in the literature, problems
related to efficiently generating meaningful CNs have received much less attention. To
generate useful CNs is necessary to automatically locating, given a handful of keywords, relations
in the database that may contain relevant pieces of information, and determining suitable
ways of joining these relations to satisfy the implicit information need expressed by a user when
formulating her query. In this thesis, we present two main contributions related to the processing
of Candidate Networks. As our first contribution, we present a novel approach for generating
CNs, in which possible matchings of the query in database are efficiently enumerated at first.
These query matches are then used to guide the CN generation process, avoiding the exhaustive
search procedure used by current state-of-art approaches. We show that our approach allows
the generation of a compact set of CNs that leads to superior quality answers, and that demands
less resources in terms of processing time and memory. As our second contribution, we initially
argue that the number of possible Candidate Networks that can be generated by any algorithm
is usually very high, but that, in fact, only very few of them produce answers relevant to the
user and are indeed worth processing. Thus, there is no point in wasting resources processing
useless CNs. Then, based on such an argument, we present an algorithm for ranking CNs, based
on their probability of producing relevant answers to the user. This relevance is estimated based
on the current state of the underlying database using a probabilistic Bayesian model we have
developed. By doing so we are able do discard a large number of CNs, ultimately leading to
better results in terms of quality and performance. Our claims and proposals are supported by a
comprehensive set of experiments we carried out using several query sets and datasets used in
previous related work and whose results we report and analyse here. / Sem resumo.

Identiferoai:union.ndltd.org:IBICT/oai:http://localhost:tede/5806
Date28 April 2017
CreatorsOliveira, Péricles Silva de, 21-98498-9543
Contributorssecretaria@icomp.ufam.edu.br, Silva, Altigran Soares da
PublisherUniversidade Federal do Amazonas, Programa de Pós-graduação em Informática, UFAM, Brasil, Instituto de Computação
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis
Formatapplication/pdf
Sourcereponame:Biblioteca Digital de Teses e Dissertações da UFAM, instname:Universidade Federal do Amazonas, instacron:UFAM
Rightshttp://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess
Relation-312656415484870643, 600, 500, 1052477850274827528

Page generated in 0.0024 seconds