CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / Nesta dissertaÃÃo foi estudado o problema de processar consultas kNN em redes de rodovias considerando o histÃrico das condiÃÃes de trÃfego, em particular o caso onde a velocidade dos objetos mÃveis depende do tempo. Dado que um usuÃrio està em uma dada localizaÃÃo e em um determinado instante de tempo, a consulta retorna os k pontos de interesse (por exemplo, postos de gasolina) que podem ser alcanÃados em uma quantidade de tempo mÃnima considerando condiÃÃes histÃricas de trÃfego. SoluÃÃes anteriores para consultas kNN e outras consultas comuns em redes de rodovia estÃticas nÃo funcionam quando o custo das arestas (tempo de viagem) à dependente do tempo. A construÃÃo de estratÃgias e algoritmos eficientes e corretos, e mÃtodos de armazenamento e acesso para o processamento destas consultas à um desafio desde que algumas das propriedades de grafos comumente supostas em estratÃgias para redes estÃticas nÃo se mantÃm para redes dependentes do tempo. O mÃtodo proposto aplica uma busca A∗ à medida que vai, de maneira incremental, explorando a rede. O objetivo do mÃtodo à reduzir o percentual da rede avaliado na busca. Para dar suporte à execuÃÃo do algoritmo, foi tambÃm proposto um mÃtodo para armazenamento e acesso para redes dependentes do tempo. A construÃÃo e a corretude do algoritmo sÃo discutidas e sÃo apresentados resultados experimentais com dados reais e sintÃticos que mostram a eficiÃncia da soluÃÃo. / In this dissertation we study the problem of processing k-nearest neighbours (kNN)queries in road networks considering the history of traffic conditions, in particular the case where the speed of moving objects is time-dependent. For instance, given that the user is at a given location at a certain time, the query returns the k points of interest (e.g., gas stations) that can be reached in the minimum amount of time. Previous solutions to answer kNN queries and others common queries in road networks do not work when the moving speed in each road is not constant. Building efficient and correct approaches and algorithms and storage and access schemes for processing these queries is a challenge because graph properties considered in static networks do not hold in the time dependent case. Our approach uses the well-known A∗ search algorithm by applying incremental network expansion and pruning unpromising vertices. The goal is reduce the percentage of network assessed in the search. To support the algorithm execution, we propose a storage and access method for time-dependent networks. We discuss the design and correctness of our algorithm and present experimental results that show the efficiency and effectiveness of our solution.

Um data warehouse geográco (DWG) é um banco de dados multidimensional, orientado a assunto, integrado, histórico, não-volátil e geralmente organizado em níveis de agregação. Além disso, também armazena dados espaciais em uma ou mais dimensões ou em pelo menos uma medida numérica. Visando oferecer suporte à tomada de decisão, é possível realizar em DWGs consultas SOLAP (spatial online analytical processing ), isto é, consultas analíticas multidimensionais (e.g., drill-down, roll-up, drill-across ) com predicados espaciais (e.g., intersecta, contém, está contido) denidos para range queries e junções espaciais. Um desafio no processamento dessas consultas é recuperar, de forma eficiente, dados espaciais e convencionais em DWGs muito volumosos. Na literatura, existem poucos índices voltados à indexação de DWGs, e ainda assim nenhum desses índices dedica-se a indexar consultas SOLAP drill-across e com junção espacial. Esta dissertação visa suprir essa limitação, por meio da proposta de estratégias para o processamento dessas consultas complexas. Para o processamento de consultas SOLAP drill-across foram propostas duas estratégias, Divide e Única, além da especicação de um conjunto de diretrizes que deve ser seguido para o projeto de um esquema de DWG que possibilite a execução dessas consultas e da especicação de classes de consultas. Para o processamento de consultas SOLAP com junção espacial foi proposta a estratégia SJB, além da identicação de quais características o esquema de DWG deve possuir para possibilitar a execução dessas consultas e da especicação do formato dessas consultas. A validação das estratégias propostas foi realizada por meio de testes de desempenho considerando diferentes congurações, sendo que os resultados obtidos foram contrastados com a execução de consultas do tipo junção estrela e o uso de visões materializadas. Os resultados mostraram que as estratégias propostas são muito eficientes. No processamento de consultas SOLAP drill-across, as estratégias Divide e Única mostraram uma redução no tempo de 82,7% a 98,6% com relação à junção estrela e ao uso de visões materializadas. No processamento de consultas SOLAP com junção espacial, a estratégia SJB garantiu uma melhora de desempenho na grande maioria das consultas executadas. Para essas consultas, o ganho de desempenho variou de 0,3% até 99,2% / A geographic data warehouse (GDW) is a special kind of multidimensional database. It is subject-oriented, integrated, historical, non-volatile and usually organized in levels of aggregation. Furthermore, a GDW also stores spatial data in one or more dimensions or at least in one numerical measure. Aiming at decision support, GDWs allow SOLAP (spatial online analytical processing) queries, i.e., multidimensional analytical queries (e.g., drill-down, roll-up, drill-across) extended with spatial predicates (e.g., intersects, contains, is contained) dened for range and spatial join queries. A challenging issue related to the processing of these complex queries is how to recover spatial and conventional data stored in huge GDWs eciently. In the literature, there are few access methods dedicated to index GDWs, and none of these methods focus on drill-across and spatial join SOLAP queries. In this master\'s thesis, we propose novel strategies for processing these complex queries. We introduce two strategies for processing SOLAP drill-across queries (namely, Divide and Unique), dene a set of guidelines for the design of a GDW schema that enables the execution of these queries, and determine a set of classes of these queries to be issued over a GDW schema that follows the proposed guidelines. As for the processing of spatial join SOLAP queries, we propose the SJB strategy, and also identify the characteristics of a DWG schema that enables the execution of these queries as well as dene the format of these queries. We validated the proposed strategies through performance tests that compared them with the star join computation and the use of materialized views. The obtained results showed that our strategies are very ecient. Regarding the SOLAP drill-across queries, the Divide and Unique strategies showed a time reduction that ranged from 82,7% to 98,6% with respect to star join computation and the use of materialized views. Regarding the SOLAP spatial join queries, the SJB strategy guaranteed best results for most of the analyzed queries. For these queries, the performance gain of the SJB strategy ranged from 0,3% to 99,2% over the star join computation and the use of materialized view

[pt] O processamento de consulta paralelo tradicional utilize- se de nós computacionais para reduzir o tempo de processamento de consultas. Com o surgimento das grades computacionais, milhares de nós podem ser utilizados, desafiando as atuais técnicas de processamento de consulta a oferecerem um suporte massivo ao paralelismo em um ambiente onde as condições variam todo a instante. Em adição, as aplicações científicas executadas neste ambiente oferecem novas características de processamento de dados que devem ser integradas em um sistema desenvolvido para este ambiente. Neste trabalho apresentamos o sistema de processamento de consulta paralelo do CoDIMS-G, e seu novo operador Orbit que foi desenvolvido para suportar a avaliação de consultas iterativas. Neste modelo de execução as tuplas são constantemente avaliadas por um fragmento paralelo do plano de execução. O trabalho inclui o desenvolvimento do sistema de processamento de consulta e um novo algoritmo de escalonamento que, considera as variações de rede e o throughput de cada nó, permitindo ao sistema se adaptar constantemente as variações no ambiente. / [en] Traditional parallel query processing uses multiple computing nodes to reduce query response time. Within a Grid computing context, the availability of thousands of nodes challenge current parallel query processing techniques to support massive parallelism in a constantly varying environment conditions. In addition, scientific applications running on Grids offer new data processing characteristics that shall be integrated in such a framework. In this work we present the CoDIMS-G parallel query processing system with a full-fledged new query execution operator named Orbit. Orbit is designed for evaluating massive iterative based data processing. Tuples in Orbit iterate over a parallelized fragment of the query execution plan. This work includes the development of the query processing system and a new scheduling algorithm that considers variation on network and the throughput of each node. Such algorithm permits the system to adapt constantly to the changes in the environment.

Submitted by Kamila Costa (kamilavasconceloscosta@gmail.com) on 2015-06-11T19:18:34Z No. of bitstreams: 1 Dissertação-Lídia L S de Carvalho.pdf: 837456 bytes, checksum: 620d89f05fc84dc2af7b89b6b6e587a0 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2015-06-15T17:53:19Z (GMT) No. of bitstreams: 1 Dissertação-Lídia L S de Carvalho.pdf: 837456 bytes, checksum: 620d89f05fc84dc2af7b89b6b6e587a0 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2015-06-15T17:57:19Z (GMT) No. of bitstreams: 1 Dissertação-Lídia L S de Carvalho.pdf: 837456 bytes, checksum: 620d89f05fc84dc2af7b89b6b6e587a0 (MD5) / Made available in DSpace on 2015-06-15T17:57:19Z (GMT). No. of bitstreams: 1 Dissertação-Lídia L S de Carvalho.pdf: 837456 bytes, checksum: 620d89f05fc84dc2af7b89b6b6e587a0 (MD5) Previous issue date: 2015-03-11 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Several research efforts have been conducted in the literature to develop methods to reduce the cost of query processing in search engines. This research aims to propose modifications to improve the performance of the block-Max WAND (BMW) algorithm, one of the most efficient algorithms proposed previously. The BMW algorithm uses heuristics to discard the documents entries at query processing, which makes it extremely fast. In this dissertation, we propose and evaluate additional heuristics to improve the perfomance of BMW and your variant BMW-CS in an attempt to both further reduces query processing times and the amount of memory required for processing queries. / Nos últimos anos, pesquisas relacionadas ao processamento de consultas em máquinas de busca têm sido realizadas com o objetivo de desenvolver métodos que reduzam o seu custo. Este trabalho visa propor modificações para melhorar o desempenho do algoritmo Block-Max WAND (BMW), um dos algoritmos mais eficientes propostos na literatura. O algoritmo BMW utiliza heurísticas para descartar documentos da resposta durante o processamento de consultas, o que torna sua execução extremamente veloz. Nesta dissertação, serão propostas e experimentadas modificações nas heurísticas de descarte de documentos e redução na quantidade de memória utilizada para processar consultas pelo algoritmo BMW e suas variantes, buscando-se assim ganhos de desempenho.

COSTA, Camila Ferreira. Nearest Neighbors with Operating Time Constraints and Optimal Sequenced Route Queries in Time-Dependent Road Networks. 2014. 75 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2014. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-06T19:14:12Z No. of bitstreams: 1 2014_dis_cfcosta.pdf: 2126584 bytes, checksum: a2635ed2f82226579173a9e49d960c00 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-06T19:18:16Z (GMT) No. of bitstreams: 1 2014_dis_cfcosta.pdf: 2126584 bytes, checksum: a2635ed2f82226579173a9e49d960c00 (MD5) / Made available in DSpace on 2016-06-06T19:18:16Z (GMT). No. of bitstreams: 1 2014_dis_cfcosta.pdf: 2126584 bytes, checksum: a2635ed2f82226579173a9e49d960c00 (MD5) Previous issue date: 2014 / In this thesis we study the problems of processing a variation of nearest neighbors and of routing planning queries in time-dependent road networks, i.e., one where travel time along each edge is a function of the departure time. We first study the problem of finding the k points of interest (POIs), for example, museums or restaurants, in which a user can start to be served in the minimum amount of time, accounting for both the travel time to the POI and the waiting time there, if it is closed. Previous works have proposed solutions to answer k-nearest neighbor queries considering the time dependency of the network but not the operating times of the points of interest. We propose and discuss three solutions to this type of query which are based on the previously proposed incremental network expansion and use the A* search algorithm equipped with suitable heuristic functions. We also present experimental results comparing the number of disk access required in each solution with respect to a few different parameters. In the second query, we aim at finding the optimal route that connects a origin to a destination and passes through a number of POIs in a specific sequence imposed on the categories of the POIs. Previous works have addressed this problem, but they do not consider the time dependency of the network. We propose an optimal sequenced route query algorithm which performs an incremental network expansion adopting an A* search. Furthermore, as an OSR query on road network tends to re-expand an extremely large number of nodes, we propose a scheme to reduce the re-expansions. For comparison purposes, we also present a baseline solution which was obtained by extending the previously proposed progressive neighbor exploration algorithm to cope with the time-dependent problem. We performed experiments in synthetic networks comparing the proposed solutions according to the number of expanded vertices in the search and the processing time of the queries. / Nesta dissertação nós estudamos os problemas de processar uma variação de consulta de vizinhos mais próximos e de planejamento de rotas em redes viárias dependentes do tempo. Diferentemente de redes convencionais, onde o custo de deslocamento de um ponto a outro é geralmente dado pela distância física entre esses dois pontos, uma rede dependente do tempo representa de forma mais realista o custo de realizar esse deslocamento, considerando o histórico das condições de tráfego. Mais especificamente, o tempo que um objeto móvel leva para percorrer uma via em tal rede depende do tempo de partida. Por exemplo, o tempo para se deslocar de um ponto a outro em grandes centros durante os horários de pico, quando o tráfego é intenso e as ruas estão congestionadas, é muito maior do que em horários normais. Dentro do contexto apresentado, primeiramente nós estudamos o problema de encontrar k pontos de interesse, como por exemplo, museus ou restaurantes, nos quais um usuário pode começar a ser servido o mais rápido possível. Em outras palavras, nós buscamos minimizar a soma do tempo de viagem até um ponto de interesse mais o tempo de espera até que ele abra, caso esteja fechado. Trabalhos anteriores tratam do problema de encontrar os k vizinhos mais próximos em redes dependentes do tempo, porém, eles não levam em consideração o horário de funcionamento dos pontos de interesse. Desta forma, a consulta abordada nesses trabalhos pode retornar pontos de interesse que estão mais próximos do usuário, considerando um dado tempo de partida, mas que podem demorar para abrir, fazendo com que o usuário espere por muito tempo. Nós propomos e discutimos três soluções para essa consulta que são baseadas em um algoritmo de expansão incremental da rede previamente proposto na literatura e usam o algoritmo de busca A* equipado com funções heurísticas adequadas para cada solução. Com o uso do algoritmo A*, nós visamos reduzir o percentual da rede avaliado na busca, evitando expandir vértices que oferecem uma baixa probabilidade de alcançar nosso objetivo. Também apresentamos resultados experimentais que comparam o número de acessos ao disco exigido em cada solução em relação a alguns parâmetros diferentes e que indicam em que casos deve-se optar por cada solução. Na segunda consulta, nós visamos encontrar a rota ótima que conecta uma dada origem a um dado destino e que passa por uma série de pontos de interesse pertencentes a categorias determinadas pelo usuário em uma certa ordem também especificada pelo usuário. Esse tipo de consulta é conhecida como OSR, do inglês, Optimal Sequenced Route, na literatura. Como exemplo, considere que alguém está indo do trabalho para casa e no seu caminho deseja passar em um banco para sacar dinheiro e depois ir a um restaurante para jantar. Embora existam vários bancos e restaurantes em uma cidade, uma consulta OSR deve procurar pelo banco e pelo restaurante que minimizam o custo da viagem do trabalho para casa. Trabalhos anteriores propuseram soluções para consultas OSR em redes com arestas de custo fixo, mas nenhum deles considerou que esse custo pode variar de acordo com o tempo de partida. Nós propomos uma solução ótima para esse problema que, assim como as abordagens propostas para o problema anterior, expande a rede incrementalmente e usa o algoritmo A* para guiar essa expansão. Além disso, como uma consulta OSR em redes viárias tende a re-expandir um número muito grande de vértices, nós incorporamos à essa solução um esquema para reduzir o número de re-expansões. Nós também apresentamos resultados experimentais que mostram a eficiência dessa solução em comparação com uma solução de base que foi obtida a partir da estensão de um algoritmo anteriormente proposto na literatura. Todos os experimentos foram realizados em redes sintéticas.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / Nesta dissertaÃÃo nÃs estudamos os problemas de processar uma variaÃÃo de consulta de vizinhos mais prÃximos e de planejamento de rotas em redes viÃrias dependentes do tempo. Diferentemente de redes convencionais, onde o custo de deslocamento de um ponto a outro à geralmente dado pela distÃncia fÃsica entre esses dois pontos, uma rede dependente do tempo representa de forma mais realista o custo de realizar esse deslocamento, considerando o histÃrico das condiÃÃes de trÃfego. Mais especificamente, o tempo que um objeto mÃvel leva para percorrer uma via em tal rede depende do tempo de partida. Por exemplo, o tempo para se deslocar de um ponto a outro em grandes centros durante os horÃrios de pico, quando o trÃfego à intenso e as ruas estÃo congestionadas, à muito maior do que em horÃrios normais. Dentro do contexto apresentado, primeiramente nÃs estudamos o problema de encontrar k pontos de interesse, como por exemplo, museus ou restaurantes, nos quais um usuÃrio pode comeÃar a ser servido o mais rÃpido possÃvel. Em outras palavras, nÃs buscamos minimizar a soma do tempo de viagem atà um ponto de interesse mais o tempo de espera atà que ele abra, caso esteja fechado. Trabalhos anteriores tratam do problema de encontrar os k vizinhos mais prÃximos em redes dependentes do tempo, porÃm, eles nÃo levam em consideraÃÃo o horÃrio de funcionamento dos pontos de interesse. Desta forma, a consulta abordada nesses trabalhos pode retornar pontos de interesse que estÃo mais prÃximos do usuÃrio, considerando um dado tempo de partida, mas que podem demorar para abrir, fazendo com que o usuÃrio espere por muito tempo. NÃs propomos e discutimos trÃs soluÃÃes para essa consulta que sÃo baseadas em um algoritmo de expansÃo incremental da rede previamente proposto na literatura e usam o algoritmo de busca A* equipado com funÃÃes heurÃsticas adequadas para cada soluÃÃo. Com o uso do algoritmo A*, nÃs visamos reduzir o percentual da rede avaliado na busca, evitando expandir vÃrtices que oferecem uma baixa probabilidade de alcanÃar nosso objetivo. TambÃm apresentamos resultados experimentais que comparam o nÃmero de acessos ao disco exigido em cada soluÃÃo em relaÃÃo a alguns parÃmetros diferentes e que indicam em que casos deve-se optar por cada soluÃÃo. Na segunda consulta, nÃs visamos encontrar a rota Ãtima que conecta uma dada origem a um dado destino e que passa por uma sÃrie de pontos de interesse pertencentes a categorias determinadas pelo usuÃrio em uma certa ordem tambÃm especificada pelo usuÃrio. Esse tipo de consulta à conhecida como OSR, do inglÃs, Optimal Sequenced Route, na literatura. Como exemplo, considere que alguÃm està indo do trabalho para casa e no seu caminho deseja passar em um banco para sacar dinheiro e depois ir a um restaurante para jantar. Embora existam vÃrios bancos e restaurantes em uma cidade, uma consulta OSR deve procurar pelo banco e pelo restaurante que minimizam o custo da viagem do trabalho para casa. Trabalhos anteriores propuseram soluÃÃes para consultas OSR em redes com arestas de custo fixo, mas nenhum deles considerou que esse custo pode variar de acordo com o tempo de partida. NÃs propomos uma soluÃÃo Ãtima para esse problema que, assim como as abordagens propostas para o problema anterior, expande a rede incrementalmente e usa o algoritmo A* para guiar essa expansÃo. AlÃm disso, como uma consulta OSR em redes viÃrias tende a re-expandir um nÃmero muito grande de vÃrtices, nÃs incorporamos à essa soluÃÃo um esquema para reduzir o nÃmero de re-expansÃes. NÃs tambÃm apresentamos resultados experimentais que mostram a eficiÃncia dessa soluÃÃo em comparaÃÃo com uma soluÃÃo de base que foi obtida a partir da estensÃo de um algoritmo anteriormente proposto na literatura. Todos os experimentos foram realizados em redes sintÃticas. / In this thesis we study the problems of processing a variation of nearest neighbors and of routing planning queries in time-dependent road networks, i.e., one where travel time along each edge is a function of the departure time. We first study the problem of finding the k points of interest (POIs), for example, museums or restaurants, in which a user can start to be served in the minimum amount of time, accounting for both the travel time to the POI and the waiting time there, if it is closed. Previous works have proposed solutions to answer k-nearest neighbor queries considering the time dependency of the network but not the operating times of the points of interest. We propose and discuss three solutions to this type of query which are based on the previously proposed incremental network expansion and use the A* search algorithm equipped with suitable heuristic functions. We also present experimental results comparing the number of disk access required in each solution with respect to a few different parameters. In the second query, we aim at finding the optimal route that connects a origin to a destination and passes through a number of POIs in a specific sequence imposed on the categories of the POIs. Previous works have addressed this problem, but they do not consider the time dependency of the network. We propose an optimal sequenced route query algorithm which performs an incremental network expansion adopting an A* search. Furthermore, as an OSR query on road network tends to re-expand an extremely large number of nodes, we propose a scheme to reduce the re-expansions. For comparison purposes, we also present a baseline solution which was obtained by extending the previously proposed progressive neighbor exploration algorithm to cope with the time-dependent problem. We performed experiments in synthetic networks comparing the proposed solutions according to the number of expanded vertices in the search and the processing time of the queries.

Submitted by Ricardo Cedraz Duque Moliterno (ricardo.moliterno@uefs.br) on 2017-11-28T21:38:06Z No. of bitstreams: 1 dissertacao-versao-final.pdf: 2717503 bytes, checksum: a1476bba65482b40daa1a139191ea912 (MD5) / Made available in DSpace on 2017-11-28T21:38:06Z (GMT). No. of bitstreams: 1 dissertacao-versao-final.pdf: 2717503 bytes, checksum: a1476bba65482b40daa1a139191ea912 (MD5) Previous issue date: 2017-07-17 / With the popularization of databases containing objects with spatial and textual information (spatio-textual object), the interest in new queries and techniques for retrieving these objects have increased. In this scenario, the main query is the the top-k spatio-textual query. This query retrieves the k best spatio-textual objects considering the distance of the object to the query location and the textual similarity between the query keywords and the textual information of the objects. However, most the studies related to top-k spatio-textual query are performed in centralized environments, not addressing real world problems such as scalability. In this paper, we study different strategies for partitioning the data and processing the top-k spatio-textual query in a distributed environment. We evaluate each strategy in a real distributed environment, employing real datasets. / Com a populariza??o de bases de dados contendo objetos que possuem informa??o espacial e textual (objeto espa?o-textual), aumentou o interesse por novas consultas e t?cnicas capazes de recuperar esses objetos de forma eficiente. Uma das principais consultas para objetos espa?o-textuais ? a consulta espa?o-textual top-k. Essa consulta visa recuperar os k melhores objetos considerando a dist?ncia do objeto at? um local informado na consulta e a similaridade textual entre palavras-chave de busca e a informa??o textual dos objetos. No entanto, a maioria dos estudos para consultas espa?o-textual top-k assumem ambientes centralizados, n?o abordando problemas frequentes em aplica??es do mundo real como escalabilidade. Nesta disserta??o s?o estudadas diferentes formas de particionar os dados e o impacto destes particionamentos no processamento da consulta espa?o-textual top-k em um ambiente distribu?do. Todas as estrat?gias propostas s?o avaliadas em um ambiente distribu?do real, utilizando dados reais.

[pt] O processamento de consultas em Sistemas de Gerência de Banco de Dados tradicionais tem sido largamente estudado na literatura e utilizado comercialmente com enorme sucesso. Isso é devido, em parte, à eficiência das Máquinas de Execução de Consultas (MEC) no suporte ao modelo de execução tradicional. Porém, o surgimento de novos cenários de aplicação, principalmente em conseqüência do modelo computacional da web, motivou a pesquisa de novos modelos de execução, tais como: modelo adaptável e modelo contínuo, além da pesquisa de modelos de dados semi-estruturados, tal como o XML, ambos não suportados pelas MEC tradicionais. O objetivo desta tese consiste no desenvolvimento de uma MEC extensível frente a diferentes modelos de execução e de dados. Adicionalmente, esta proposta trata de maneira ortogonal o modelo de execução e o modelo de dados, o que permite a avaliação de planos de execução de consultas (PEC) com fragmentos em diferentes modelos. Utilizou-se a técnica de framework de software para a especificação da MEC extensível, produzindo o framework QEEF (Query Execution Engine Framework). A extensibilidade da solução reflete-se em um meta-modelo, denominado QUEM (QUery Execution Meta-model), capaz de exprimir diferentes modelos em um meta-PEC. O framework QEEF pré-processa um meta-PEC e produz um PEC final a ser avaliado pela MEC instanciada. Como parte da validação desta proposta, instanciou-se o QEEF para diferentes modelos de execução e de dados. / [en] Querying processing in traditional Database Management Systems (DBMS) has been extensively studied in the literature and adopted in industry. Such success is, in part, due to the performance of their Query Execution Engines (QEE) for supporting the traditional query execution model. The advent of new query scenarios, mainly due to the web computational model, has motivate the research on new execution models such as: adaptive and continuous, and on semistructured data models, such as XML, both not natively supported by traditional query engines. This thesis proposes the development of an extensible QEE adapted to the new execution and data models. Achieving this goal, we use a software design approach based on framework technique to produce the Query Execution Engine Framework (QEEF). Moreover, we address the question of the orthogonality between execution and data models, witch allows for executing query execution plans (QEP) with fragments in different models. The extensibility of our solution is specified by in a QEP by an execution meta- model named QUEM (QUery Execution Meta-model) used to express different models in a meta-QEP. During query evaluation, the latter is pre-processed by the QEEF producing a final QEP to be evaluated by the running QEE. The QEEF is instantiated for different execution and data models as part of the validation of this proposal.

Submitted by Luis Ricardo Andrade da Silva (lrasilva@uefs.br) on 2016-03-01T21:58:16Z No. of bitstreams: 1 disserta??o.pdf: 1075417 bytes, checksum: 1ac0911a0f45578306a02c8eae7a090f (MD5) / Made available in DSpace on 2016-03-01T21:58:16Z (GMT). No. of bitstreams: 1 disserta??o.pdf: 1075417 bytes, checksum: 1ac0911a0f45578306a02c8eae7a090f (MD5) Previous issue date: 2015-12-17 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior - CAPES / With the popularity of devices that are able to annotate data with spatial information (latitude and longitude), the processing of spatial queries has received a lot of attention from the research community recently. In this dissertation, we study a new query type named Top-k Spatial Keyword Preference Query that selects objects of interest based on the textual relevance of other spatio-textual objects in their spatial neighborhood. This work introduces this new query type, presents three algorithms for processing the query efficiently and performs an experimental evaluation using real databases to study the performance of the proposed algorithms. / Com a popularidade de dispositivos capazes de anotar dados com coordenadas espaciais (latitude e longitude), o processamento de consultas espaciais tem recebido bastante aten??o da comunidade cient?fica recentemente. Esta disserta??o apresenta uma nova consulta, chamada Consulta Espacial Preferencial por Palavra-chave, que seleciona objetos de interesse de acordo com a relev?ncia textual de outros objetos espa?o-textuais presentes na sua vizinhan?a espacial. Este trabalho introduz esta nova consulta, apresenta tr?s algoritmos para process?-la de forma eficiente e avalia o desempenho dos algoritmos propostos atrav?s de um estudo experimental, utilizando bases de dados reais.