Otimização de operações de busca por similaridade em espaços métricos atendendo à expectativa do usuário

The complexity of data stored in large databases has increased at very fast paces. Hence, operations more elaborated than traditional queries are essential in order to extract all required information from the database. Therefore, the interest of the database community in similarity search has increased significantly. Two of the well-known types of similarity search are the Range (Rq) and the k-Nearest Neighbor (kNNq) queries, which, as any of the traditional ones, can be sped up by indexing structures of the Database Management System (DBMS). Another way of speeding up queries is to perform query optimization. In this process, metrics about data are collected and employed to adjust the parameters of the search algorithms in each query execution. However, although the integration of similarity search into DBMS has begun to be deeply studied more recently, the query optimization has been developed and employed just to answer traditional queries.The execution of similarity queries, even using efficient indexing structures, tends to present higher computational cost than the execution of traditional ones. Two strategies can be applied to speed up the execution of any query, and thus they are worth to employ to answer also similarity queries. The first strategy is query rewriting based on algebraic properties and cost functions. The second technique is when external query factors are applied, such as employing the semantic expected by the user, to prune the answer space. This thesis aims at contributing to the development of novel techniques to improve the similarity-based query optimization processing, exploiting both algebraic properties and semantic restrictions as query refinements.La complexité des données contenues dans les grandes bases de données a augmenté considérablement. Par conséquent, des opérations plus élaborées que les requêtes traditionnelles sont indispensable pour extraire toutes les informations requises de la base de données. L'intérêt de la communauté de base de données a particulièrement augmenté dans les recherches basées sur la similarité. Deux sortes de recherche de similarité bien connues sont la requête par intervalle (Rq) et par k-plus proches voisins (kNNq). Ces deux techniques, comme les requêtes traditionnelles, peuvent être accélérées par des structures d'indexation des Systèmes de Gestion de Base de Données (SGBDs).Une autre façon d'accélérer les requêtes est d'exécuter le procédé d'optimisation des requêtes. Dans ce procédé les données métriques sont recueillies et utilisées afin d'ajuster les paramètres des algorithmes de recherche lors de chaque exécution de la requête. Cependant, bien que l'intégration de la recherche de similarités dans le SGBD ait commencé à être étudiée en profondeur récemment, le procédé d'optimisation des requêtes a été développé et utilisé pour répondre à des requêtes traditionnelles. L'exécution des requêtes de similarité a tendance à présenter un coût informatique plus important que l'exécution des requêtes traditionnelles et ce même en utilisant des structures d'indexation efficaces. Deux stratégies peuvent être appliquées pour accélérer l'execution de quelques requêtes, et peuvent également être employées pour répondre aux requêtes de similarité. La première stratégie est la réécriture de requêtes basées sur les propriétés algébriques et les fonctions de coût. La deuxième stratégie est l'utilisation des facteurs externes de la requête, tels que la sémantique attendue par les usagers, pour réduire le nombre des résultats potentiels. Cette thèse vise à contribuer au développement des techniques afin d'améliorer le procédé d'optimisation des requêtes de similarité, tout en exploitant les propriétés algébriques et les restrictions sémantiques pour affiner les requêtes.A complexidade dos dados armazenados em grandes bases de dados tem aumentadosempre, criando a necessidade de novas operaoes de consulta. Uma classe de operações de crescente interesse são as consultas por similaridade, das quais as mais conhecidas sãoas consultas por abrangência (Rq) e por k-vizinhos mais próximos (kNNq). Qualquerconsulta é agilizada pelas estruturas de indexaçãodos Sistemas de Gerenciamento deBases de Dados (SGBDs). Outro modo de agilizar as operações de busca é a manutençãode métricas sobre os dados, que são utilizadas para ajustar parâmetros dos algoritmos debusca em cada consulta, num processo conhecido como otimização de consultas. Comoas buscas por similaridade começaram a ser estudadas seriamente para integração emSGBDs muito mais recentemente do que as buscas tradicionais, a otimização de consultas,por enquanto, é um recurso que tem sido utilizado para responder apenas a consultastradicionais.Mesmo utilizando as melhores estruturas existentes, a execução de consultas por similaridadetende a ser mais custosa do que as operações tradicionais. Assim, duas estratégiaspodem ser utilizadas para agilizar a execução de qualquer consulta e, assim, podem serempregadas também para responder às consultas por similaridade. A primeira estratégiaé a reescrita de consultas baseada em propriedades algébricas e em funções de custo. Asegunda técnica faz uso de fatores externos à consulta, tais como a semântica esperadapelo usuário, para restringir o espaço das respostas. Esta tese pretende contribuir parao desenvolvimento de técnicas que melhorem o processo de otimização de consultas porsimilaridade, explorando propriedades algébricas e restrições semânticas como refinamentode consulta