• 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
 
 
Tesis Doctoral
DOI
10.11606/T.55.2005.tde-13112014-165634
Documento
Autor
Nombre completo
Adriano Siqueira Arantes
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Carlos, 2005
Director
Tribunal
Traina Junior, Caetano (Presidente)
Biajiz, Mauro
Laender, Alberto Henrique Frade
Mattoso, Marta Lima de Queirós
Nonato, Luis Gustavo
Título en portugués
Consultas por similaridade complexas em gerenciadores relacionais
Palabras clave en portugués
Não disponível
Resumen en 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 en inglés
Complex similarity queries in relational database management systems
Palabras clave en inglés
Not available
Resumen en 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.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Fecha de Publicación
2014-11-13
 
ADVERTENCIA: El material descrito abajo se refiere a los trabajos derivados de esta tesis o disertación. El contenido de estos documentos es responsabilidad del autor de la tesis o disertación.
  • 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 los derechos de la tesis/disertación pertenecen a los autores
Centro de Informática de São Carlos
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2019. Todos los derechos reservados.