• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Tese de Doutorado
DOI
https://doi.org/10.11606/T.55.2005.tde-13112014-165634
Documento
Autor
Nome completo
Adriano Siqueira Arantes
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Carlos, 2005
Orientador
Banca examinadora
Traina Junior, Caetano (Presidente)
Biajiz, Mauro
Laender, Alberto Henrique Frade
Mattoso, Marta Lima de Queirós
Nonato, Luis Gustavo
Título em português
Consultas por similaridade complexas em gerenciadores relacionais
Palavras-chave em português
Não disponível
Resumo em português
Em domínios de dados complexos (tais como, dados multimídia, sequências genômicas, entre outros), a similaridade entre elementos surge naturalmente como a maneira mais adequada para consultar esses dados. Existem, basicamente, dois tipos de consulta por similaridade: por abrangência e aos k-vizinhos mais próximos. Com o aumento no volume de dados complexos armazenado em Sistemas de Gerenciamento de Bases de Dados (SGBD), também chamados neste trabalho de gerenciadores, torna-se necessário prover suporte a esses tipos de dados. Um modo de dar suporte a tipos de dados complexos nos gerenciadores atuais é incluir consultas por similaridade em seu processador de consultas, e consequentemente, na álgebra relacional. Este fato leva à produção de maneiras para expressar tais consultas na linguagem do gerenciador como predicados em operações de seleção. Como uma consequência, os principais tipos de consultas por similaridade podem ser compostos em expressões mais complexas por meio de conjunções e disjunções booleanas entre eles, isto é, consultas por similaridade complexas. Entretanto, para que um gerenciador processe consultas por similaridade complexas eficientemente, é necessário dar suporte as etapas de otimização e execução na arquitetura do processamento de consultas. Embora diversos trabalhos envolvam o desenvolvimento de algoritmos para responder a uma simples e específica consulta por similaridade, não há um algoritmo genérico apto a manipular eficientemente consultas por similaridade complexas. Além disso, a otimização de consultas por similaridade é um aspecto ainda pouco explorado na literatura. Esta tese propõe um método estruturado de como analisar consultas por similaridade complexas. Esse método é utilizado para estender a álgebra relacional por meio de regras algébricas e determinar um pequeno conjunto de algoritmos que podem ser utilizados para responder a qualquer consulta por similaridade complexa. O método proposto também permite formalizar regras para estimar a seletividade dessas consultas auxiliando na previsão de custo. Para validar os conceitos apresentados, experimentos são realizados com conjuntos de dados reais e sintéticos destacando os resultados obtidos. As regras algébricas, os algoritmos e as métricas para se estimar a seletividade podem ser utilizados por um gerenciador relacional na etapa de otimização, para derivar planos de execução eficientes para consultas por similaridade complexas. Portanto, os aspectos abordados nesta tese contribuem para permitir o uso prático de consultas por similaridade em gerenciadores relacionais.
Título em inglês
Complex similarity queries in relational database management systems
Palavras-chave em inglês
Not available
Resumo em inglês
The similarity among elemcnts emerges naturally as the most adequate to ask about complex data (such as, multimédia and genomic sequenees among others). There are two basic similarity queries: Range Query and k-Nearest Neighbor Query. The increasing volume of complex data stored in Database Management Systems (DBMS), makes it neeessary to provide support for these data tvpes. One way to support complex data types in current DBMS is to include similarity queries in its query processor, and consequently, in the relational algebra. This fact leads to produce ways to express such queries in the DBMS language as predicates in select operations. As a consequence, the two basic similarity queries can be combined in more complex expressions involving boolean conjunctions and disjunctions among them, i.e., complex similarity queries. However, for complex similarity queries to be processed efficiently in a DBMS, it is necessary to provide support in the optimization and runtime laycrs of the; query proeessing. There are many works involving the development, of algorithms to answer specific and simple similarity query whereas there is not a generic algorithm efficiently able to handle complex similarity queries. Furthermore, the similarity query optimization is a topic not frequently explored in the literature. This work establishes a structured rnethod 011 how to analyze complex similarity queries. This method is used to extend the relational algebra through algebraic rules and to determine a small set of algorithms that can be used to answer any complex similarity query. In addition, the proposed method makes it possible to formalize rules for selectivity estimation of these. queries thus assisting cost estimation. To validate the concepts presented, experiments are being performed on real and synthetic data sets that highlight meaningful results. The algebraic rules. algorithms and metrics to estimate the selectivity can be employed in the optimization process of a DBMS in order to derive efficient complex similarity query execution plans. Therefore, this work deals with essential poiuts that enable the practical use of similarity (jueries in Relational Database Management Systems.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2014-11-13
 
AVISO: O material descrito abaixo refere-se a trabalhos decorrentes desta tese ou dissertação. O conteúdo desses trabalhos é de inteira responsabilidade do autor da tese ou dissertação.
  • ARANTES, A. S., et al. Efficient Algorithms to Execute Complex Similarity Queries in RDBMS. Journal of the Brazilian Computer Society, 2004, vol. 3, nº 9, p. 5-24.
  • ARANTES, A. S., et al. Operadores de Seleção por Similaridade para Sistemas de Gerenciamento de Bases de Dados Relacionais. In Simpósio Brasileiro de Banco de Dados - SBBD, Manaus, AM, 2003. Anais do XVIII Simpósio Brasileiro de Bases de Dados (SBBD´03).Manaus, 2003.
  • ARANTES, A. S., et al. The Fractal Dimension Making Similarity Queries More Efficient. In Second Workshop on Fractals, Power Laws and Other Next Generation Data Mining Tools (in conjunction with 10th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining), Washington-DC, 2003. Second Workshop on Fractals,Power Laws and Other Next Generation Data Mining Tools. : ACM Press, 2003. Disponível em: http://www.isi.edu/~adibi/FractalKDD03/program.html.
  • Traina Jr., C.., et al. Efficient Processing of Complex Similarity Queries in RDBMS through Query Rewriting. In ACM 15th Conference on Information and Knowledge Management (CIKM06), Arlington - VA, 2006. Proceedings of the CIKM06.New York : ACM Press, 2006. Disponível em: http://portal.acm.org/citation.cfm?doid=1183614.1183620.
  • Vieira, M. R., et al. Boosting k-Nearest Neighbor Queries Estimating Suitable Query Radii [doi:10.1109/SSDBM.2007.5]. In 19th International Conference on Scientific and Statistical Database Management (SSDBM 2007), Banff, Alberta, 2007. Proceedings of the SSDBM 2007.Los Alamitos : IEEE Computer Society, 2007.
  • Prêmio José Mauro de Castilho - Melhor artigo do XIX Simpósio Brasileiro de Banco de Dados - Sociedade Brasileira de Computação
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2024. Todos os direitos reservados.