A recuperação de dados armazenados em Bancos de Dado em geral é feita utilizando estruturas de indexação, que permitem fazer a recuperação dos dados muito mais rapidamente do que se a busca fosse feita sequencialmente. No entanto, as estruturas de indexação que podem ser utilizadas dependem das propriedades dos domínios de dados indexados e do tipo de consultas que devem ser respondidas. Tradicionalmente, os gerenciadores de bancos de dados suportam bem dados de domínios que possuem a propriedade de relação de ordem total, tais como números e textos com a relação de ordem lexicográfica permitindo consultas por igualdade e consultas envolvendo relações de ordem tais como >, < ou =, >, < ou = etc. Além disso, as estruturas de indexação comumente utilizadas em sistemas gerenciadores de bases de dados são construídas para serem armazenadas em disco, particionando o conjunto de dados em registros de tamanho fixo. O exemplo mais comum desse arranjo é o das árvores de indexação, quando os registros são então chamados \"nós\". Aplicações mais sofisticadas frequentemente apresentam dados em outros domínios, com outros tipos de consulta. Quando as aplicações lidam com dados em domínio métrico, além dos próprios elementos de dados, é definida uma função de similaridade (ou de distância) entre pares de elementos, e essa função é a única maneira de comparação entre dois elementos de dados do conjunto. Existem diversas estruturas de indexação criadas para dados em domínios métricos . Entretanto essas estruturas ou são estáticas (impedindo que novos elementos sejam acrescentados depois que a estrutura foi criada), ou são para armazenamento em disco. Neste trabalho foi desenvolvida uma nova estrutura métrica dinâmica para dados métricos totalmente armazenada em memória principal. Uma outra propriedade interessante dessa estrutura é que a execução de uma consulta por existência (point query) percorre um único caminho de busca. Essa característica é muito interessante, pois todas as outras árvores dinâmicas existentes requerem que a navegação seja feita não apenas em profundidade, mas também em largura. A estrutura proposta permite a navegação apenas em profundidade para a consulta por existência. / The stored data recovery in Data bases, in general is made using indexation structures, that allow to much more quickly make the data recovery of that if the search was made sequentially. However, the indexation structures that can be used depend on the domains properties of the of indexing data and the type of queries that must be answered. Traditionally, the data bases management systems support well domains dataset that possess the property of relation of total order, such as numbers and texts with the lexicographical relation order allowing to queries for equality and queries involving order relations such as >, < or =, > and < or =. Moreover, the commonly indexing structures used in data bases management systems are constructed to be stored in record, partitioning the data set in registers of so great fixture. The example most common of this arrangement is of the indexing trees, when the registers then are called \"nodes\". Sophisticated applications more frequently present datasets in other domains, with other types of quey. When the applications deal with data in metric domain, beyond the proper data elements, a similarity function (or distance) between pairs of elements is defined, and this function is the only way of comparison enters two elements of data of the set. There are diverse metric domain data indexing structures created. However these structures are static (hindering that new elements are added later that the structure was created), or are for record storage. In this work a new dynamic metric structure for metric data total stored in principal memory e was developed. One another interesting property of this structure is that the execution of a quey for existence (point query) covers an only way of search. This characteristic is very interesting, therefore ali the other existing dynamic trees require that the navigation is made not only in depth, but also in width. The structure proposal allows the navigation only in depth for the quey for existence.
Identifer | oai:union.ndltd.org:IBICT/oai:teses.usp.br:tde-10112014-104117 |
Date | 13 August 2003 |
Creators | Andréia Dal Ponte Novelli |
Contributors | Caetano Traina Junior, Josiane Maria Bueno, Jander Moreira |
Publisher | Universidade de São Paulo, Ciências da Computação e Matemática Computacional, USP, BR |
Source Sets | IBICT Brazilian ETDs |
Language | Portuguese |
Detected Language | Portuguese |
Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
Source | reponame:Biblioteca Digital de Teses e Dissertações da USP, instname:Universidade de São Paulo, instacron:USP |
Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0015 seconds