Complex similarity queries in relational database management systems

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.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