O operador de agrupamento e as funções de agregação são as principais ferramentas utilizadas para sumarizar dados em um Sistema de Gerenciamento de Base de Dados Relacionais (SGBDR). O operador de agrupamento funciona criando partições nos dados utilizando comparações por identidade, e permite que sejam aplicadas funções de agregação que retornam um único valor representando o grupo como um todo. Entretanto, para dados métricos, agrupamento utilizando identidade tem pouca utilidade. Neste caso, adotar o conceito de similaridade é frequentemente uma abordagem mais promissora. A literatura apresenta alguns operadores que podem agrupar os dados utilizando similaridade. Todos eles utilizam um limiar de valor de distância para atribuir os elementos aos grupos. No entanto, estes operadores não obtêm resultados satisfatórios quando a distribuição dos dados apresenta variações significativas na densidade de objetos em diferentes regiões do espaço. Para alcançar melhores resultados nestas situações, propusemos um novo operador que atribui os grupos utilizando uma eleição envolvendo grupos já atribuídos. Também propusemos generalizações, para os operadores existentes e propostos, para trabalhar com uma quantidade de vizinhos mais próximos e aproximação dos vizinhos mais próximos ao invés de um limiar de distância. Para possibilitar a inclusão destes operadores em SGBDR, propusemos uma extensão à Structured Query Language (SQL) e novas funções de agregação. Implementamos estes operadores em nosso framework em C++ usando a biblioteca Arboretum. Para avaliar os métodos propostos, analisamos tanto qualidade dos resultados quanto tempo de execução, utilizando conjuntos de dados reais e sintéticos. Os operadores propostos alcançaram melhores resultados quanto à qualidade de resultados, e mantiveram os tempos de execução similares. Os operadores que utilizam aproximação aos vizinhos mais próximos produziram resultados de qualidade similar quando comparados aos operadores que utilizando os vizinhos mais próximos, podendo ser executados em menor tempo que estes. / The grouping operator and aggregation functions are the primary tools used to summarize data inside a Relational Database Management Systems (RDBMS). The grouping operator works creating partitions in data using identity comparisons, and allow applying aggregation functions that return a single value that represent the entire group. However, for metric data, grouping by identity is seldom useful. In this case, adopting the concept of the similarity is often a better approach. The literature presents few operators that can group data using similarity. All of them use a distance threshold value to assign the elements in groups. However, these operators do not achieve satisfactory results when the data distribution present a significant variation in the density of objects in different regions of the space. To achieve better results in these situations, we have proposed a novel operator that assign groups using an election involving already assigned groups. We also proposed generalizations to existing and proposed operators to work with an amount of nearest neighbors and approximate neighbors instead of a distance threshold. To support these operators in RDBMS, we propose an extension to Structured Query Language (SQL) and new aggregation functions. Our proposed algorithms can run the proposed and existing operators. We implemented these operators in our framework in C++ using Arboretum library. To evaluate the proposed methods, we assess both results quality and the execution time, using both real and synthetic datasets. The proposed operators achieved better results comparing the quality and maintained similar executing time. The operators that use the approximate nearest neighbors produced similar quality results comparing with the operators that use the exact neighbors and can execute faster than that.

Os Sistemas de Gerenciamento de Bases de Dados Relacionais (SGBDR) foram concebidos para o armazenamento e recuperação de grandes volumes de dados. Tradicionalmente, estes sistemas suportam números, pequenas cadeias de caracteres e datas (que podem ser comparados por identidade ou por relações de ordem { RO), porém vem se tornando necessário organizar, armazenar e recuperar dados mais complexos, como por exemplo dados multimídia (imagens, áudio e vídeo), séries temporais etc. Quando se trata de dados complexos há uma mudança de paradigma, pois as comparações entre elementos são feitas por similaridade em vez das RO utilizadas tradicionalmente, tendo como mais frequentemente utilizados os operadores de comparação por abrangência (Rq) e por k-vizinhos mais próximos (k-NN). Embora muitos estudos estejam sendo feitos nessa área, quando lidando com consultas por similaridade grande parte do esforço é direcionado para criar as estruturas de indexação e dar suporte às operações necessárias para executar apenas o aspecto da consulta que trata da similaridade, sem focar em realizar uma integração homogênea das consultas que envolvam ambos os tipos de operadores simultaneamente nos ambientes dos SGDBRs. Um dos principais problemas nessa integração é lidar com as peculiaridades do operador de busca por k-NN. Todos os operadores de comparação por identidade e por RO são comutativos e associativos entre si. No entanto o operador de busca por k-NN não atende a nenhuma dessas propriedades. Com isso, a expressão de consultas em SQL, que usualmente pode ser feita sem que a expressão da ordem entre os predicados seja importante, precisa passar a considerar a ordem. Além disso, consultas que utilizam comparações por k-NN podem gerar múltiplos empates, e a falta de uma metodologia para resolvê-los pode levar a um processo de desempate arbitrário ou insensível ao contexto da consulta, onde usuários não tem poder para intervir de maneira significativa. Em alguns casos, isso pode levar a uma mesma consulta a retornar resultados distintos em casos onde a estrutura interna dos dados estiver sujeita a modificações, como por exemplo em casos de transações concorrentes em um SGBDR. Este trabalho aborda os problemas gerados pela inserção de operadores de busca por similaridade nos SGBDR, mais especificamente o k-NN, e propõe novas maneiras de representação de consultas com múltiplos predicados, por similaridade ou RO, assim como novos operadores derivados do k-NN que são mais adequados para um ambiente relacional que permita consultas híbridas, e permitem também controle sobre o tratamento de empates. / The Relational Database Management Systems (RDBMS) were originally conceived to store and retrieve large volumes of data. Traditionally, these systems support only numbers, small strings of characters and dates (which could be compared by identity and a Order Relationship { OR). However it has been increasingly necessary to organize, store and retrieve more complex data, such as multimedia (images, audio and video), time series etc. Dealing with those data types requires a paradigm shift, as the comparisons between each element are made by similarity, and not by the traditionally used identity or OR, with the most common similarity operators used being the range (Rq) and k-Nearest Neighbors (k-NN). Despite many studies in the field, when dealing with similarity queries a large part of the effort has been directed towards the data structures and the necessary operations to execute only the similarity side of the query, not paying attention to a more homogenous integration of queries that involve both operator types simultaneously in RDBMS environments. One of the main problems for such integration is the peculiarities of the k-NN operator. Both identity and OR operators possess the commutative and associative properties amongst themselves, but the k-NN operator does not. As such, expressing SQL queries, that usually can disregard the order in which predicates appear, now needs to be aware of the ordering. Furthermore, queries that use k-NN might generate multiple ties, and the lack of a methodology to solve them might lead to an arbitrary or context-detached untying process, where users have little or no control to intervene. In some applications, the lack of a controlled untying process may even lead to each query yielding distinct results if the underlying structures ought be subject to change, as it is be the case of the concurrent transactions in a relational database management system (RDBMS). This work focuses on the problems that arise from the integration of similarity based operators into RDBMS, more specifically the k-NN, and proposes new ways to represent queries with multiple predicates, including similarity, identity or OR, as well as new operators derived from k-NN that are better suited for a RDBMS environment containing hybrid queries, and also enable control over the untying process.

.

Os Sistemas de Gerenciamento de Bases de Dados Relacionais (SGBDR) foram concebidos para o armazenamento e recuperação de grandes volumes de dados. Tradicionalmente, estes sistemas suportam números, pequenas cadeias de caracteres e datas (que podem ser comparados por identidade ou por relações de ordem { RO), porém vem se tornando necessário organizar, armazenar e recuperar dados mais complexos, como por exemplo dados multimídia (imagens, áudio e vídeo), séries temporais etc. Quando se trata de dados complexos há uma mudança de paradigma, pois as comparações entre elementos são feitas por similaridade em vez das RO utilizadas tradicionalmente, tendo como mais frequentemente utilizados os operadores de comparação por abrangência (Rq) e por k-vizinhos mais próximos (k-NN). Embora muitos estudos estejam sendo feitos nessa área, quando lidando com consultas por similaridade grande parte do esforço é direcionado para criar as estruturas de indexação e dar suporte às operações necessárias para executar apenas o aspecto da consulta que trata da similaridade, sem focar em realizar uma integração homogênea das consultas que envolvam ambos os tipos de operadores simultaneamente nos ambientes dos SGDBRs. Um dos principais problemas nessa integração é lidar com as peculiaridades do operador de busca por k-NN. Todos os operadores de comparação por identidade e por RO são comutativos e associativos entre si. No entanto o operador de busca por k-NN não atende a nenhuma dessas propriedades. Com isso, a expressão de consultas em SQL, que usualmente pode ser feita sem que a expressão da ordem entre os predicados seja importante, precisa passar a considerar a ordem. Além disso, consultas que utilizam comparações por k-NN podem gerar múltiplos empates, e a falta de uma metodologia para resolvê-los pode levar a um processo de desempate arbitrário ou insensível ao contexto da consulta, onde usuários não tem poder para intervir de maneira significativa. Em alguns casos, isso pode levar a uma mesma consulta a retornar resultados distintos em casos onde a estrutura interna dos dados estiver sujeita a modificações, como por exemplo em casos de transações concorrentes em um SGBDR. Este trabalho aborda os problemas gerados pela inserção de operadores de busca por similaridade nos SGBDR, mais especificamente o k-NN, e propõe novas maneiras de representação de consultas com múltiplos predicados, por similaridade ou RO, assim como novos operadores derivados do k-NN que são mais adequados para um ambiente relacional que permita consultas híbridas, e permitem também controle sobre o tratamento de empates. / The Relational Database Management Systems (RDBMS) were originally conceived to store and retrieve large volumes of data. Traditionally, these systems support only numbers, small strings of characters and dates (which could be compared by identity and a Order Relationship { OR). However it has been increasingly necessary to organize, store and retrieve more complex data, such as multimedia (images, audio and video), time series etc. Dealing with those data types requires a paradigm shift, as the comparisons between each element are made by similarity, and not by the traditionally used identity or OR, with the most common similarity operators used being the range (Rq) and k-Nearest Neighbors (k-NN). Despite many studies in the field, when dealing with similarity queries a large part of the effort has been directed towards the data structures and the necessary operations to execute only the similarity side of the query, not paying attention to a more homogenous integration of queries that involve both operator types simultaneously in RDBMS environments. One of the main problems for such integration is the peculiarities of the k-NN operator. Both identity and OR operators possess the commutative and associative properties amongst themselves, but the k-NN operator does not. As such, expressing SQL queries, that usually can disregard the order in which predicates appear, now needs to be aware of the ordering. Furthermore, queries that use k-NN might generate multiple ties, and the lack of a methodology to solve them might lead to an arbitrary or context-detached untying process, where users have little or no control to intervene. In some applications, the lack of a controlled untying process may even lead to each query yielding distinct results if the underlying structures ought be subject to change, as it is be the case of the concurrent transactions in a relational database management system (RDBMS). This work focuses on the problems that arise from the integration of similarity based operators into RDBMS, more specifically the k-NN, and proposes new ways to represent queries with multiple predicates, including similarity, identity or OR, as well as new operators derived from k-NN that are better suited for a RDBMS environment containing hybrid queries, and also enable control over the untying process.

O operador de agrupamento e as funções de agregação são as principais ferramentas utilizadas para sumarizar dados em um Sistema de Gerenciamento de Base de Dados Relacionais (SGBDR). O operador de agrupamento funciona criando partições nos dados utilizando comparações por identidade, e permite que sejam aplicadas funções de agregação que retornam um único valor representando o grupo como um todo. Entretanto, para dados métricos, agrupamento utilizando identidade tem pouca utilidade. Neste caso, adotar o conceito de similaridade é frequentemente uma abordagem mais promissora. A literatura apresenta alguns operadores que podem agrupar os dados utilizando similaridade. Todos eles utilizam um limiar de valor de distância para atribuir os elementos aos grupos. No entanto, estes operadores não obtêm resultados satisfatórios quando a distribuição dos dados apresenta variações significativas na densidade de objetos em diferentes regiões do espaço. Para alcançar melhores resultados nestas situações, propusemos um novo operador que atribui os grupos utilizando uma eleição envolvendo grupos já atribuídos. Também propusemos generalizações, para os operadores existentes e propostos, para trabalhar com uma quantidade de vizinhos mais próximos e aproximação dos vizinhos mais próximos ao invés de um limiar de distância. Para possibilitar a inclusão destes operadores em SGBDR, propusemos uma extensão à Structured Query Language (SQL) e novas funções de agregação. Implementamos estes operadores em nosso framework em C++ usando a biblioteca Arboretum. Para avaliar os métodos propostos, analisamos tanto qualidade dos resultados quanto tempo de execução, utilizando conjuntos de dados reais e sintéticos. Os operadores propostos alcançaram melhores resultados quanto à qualidade de resultados, e mantiveram os tempos de execução similares. Os operadores que utilizam aproximação aos vizinhos mais próximos produziram resultados de qualidade similar quando comparados aos operadores que utilizando os vizinhos mais próximos, podendo ser executados em menor tempo que estes. / The grouping operator and aggregation functions are the primary tools used to summarize data inside a Relational Database Management Systems (RDBMS). The grouping operator works creating partitions in data using identity comparisons, and allow applying aggregation functions that return a single value that represent the entire group. However, for metric data, grouping by identity is seldom useful. In this case, adopting the concept of the similarity is often a better approach. The literature presents few operators that can group data using similarity. All of them use a distance threshold value to assign the elements in groups. However, these operators do not achieve satisfactory results when the data distribution present a significant variation in the density of objects in different regions of the space. To achieve better results in these situations, we have proposed a novel operator that assign groups using an election involving already assigned groups. We also proposed generalizations to existing and proposed operators to work with an amount of nearest neighbors and approximate neighbors instead of a distance threshold. To support these operators in RDBMS, we propose an extension to Structured Query Language (SQL) and new aggregation functions. Our proposed algorithms can run the proposed and existing operators. We implemented these operators in our framework in C++ using Arboretum library. To evaluate the proposed methods, we assess both results quality and the execution time, using both real and synthetic datasets. The proposed operators achieved better results comparing the quality and maintained similar executing time. The operators that use the approximate nearest neighbors produced similar quality results comparing with the operators that use the exact neighbors and can execute faster than that.