Ontologias de representação de conhecimento são modelos que agrupam e definem construtos de modelagem (tais como conceito, classe, frame). Uma ontologia temporal é uma especificação de uma conceitualização do domínio acrescida dos aspectos de tempo sobre os objetos do domínio. No caso de esta ontologia tratar somente de aspectos temporais ligados a eventos, ela é chamada ontologia de eventos. Este trabalho propõe uma extensão de uma ontologia de representação de conhecimento (RC) com construtos temporais, ou seja, estender um modelo de conceitualização de domínios com os construtos necessários para se representar eventos. A definição original de uma ontologia de RC foi estendida neste trabalho com os seguintes construtos: (i) o construto evento (que define um evento como um acontecimento que pode alterar objetos do domínio) e (ii) o construto relação-temporal (que define uma relação de tempo entre os eventos). O objetivo deste trabalho é, baseando-se nos novos construtos propostos na ontologia de RC, criar um modelo de conhecimento específico para um domínio, o qual suporta a representação das seguintes primitivas: características do domínio, eventos geradores das características do domínio, associações entre características do domínio, relações temporais entre eventos. Além disso, o modelo tem o objetivo de suportar métodos de raciocínio para inferir a seqüência em que as características do domínio foram geradas pelos eventos, ou seja, inferir a ordem dos eventos. O domínio de aplicação deste trabalho é a petrografia sedimentar. Esse domínio apresenta diversas tarefas de interpretação que exigem conhecimento especializado para sua solução. Dentre estas tarefas, o foco de estudo deste trabalho é a interpretação de seqüência diagenética, a qual procura identificar a ordem em que os processos diagenéticos atuaram sobre os constituintes das rochas sedimentares. Para compreender e coletar o conhecimento necessário para a modelagem dessa tarefa, as principais técnicas de aquisição de conhecimento para sistemas baseados em conhecimento foram aplicadas em sessões com um especialista em petrografia sedimentar, gerando os principais objetos do domínio que precisavam ser modelados para se atingir o objetivo da ordenação de eventos. Esses objetos foram representados como um modelo de conhecimento específico para o domínio da petrografia, aplicando os construtos de eventos e relação temporal. Esse modelo foi validado através da implementação de um módulo de inferência no sistema PetroGrapher. A validação foi efetuada comparando as respostas do algoritmo com as interpretações do especialista, e foi possível notar que apesar de a apresentação gráfica da seqüência de eventos ainda ser diferente da original do especialista, o algoritmo efetua a ordenação de eventos corretamente. / O domínio de aplicação deste trabalho é a petrografia sedimentar. Esse domínio apresenta diversas tarefas de interpretação que exigem conhecimento especializado para sua solução. Dentre estas tarefas, o foco de estudo deste trabalho é a interpretação de seqüência diagenética, a qual procura identificar a ordem em que os processos diagenéticos atuaram sobre os constituintes das rochas sedimentares. Para compreender e coletar o conhecimento necessário para a modelagem dessa tarefa, as principais técnicas de aquisição de conhecimento para sistemas baseados em conhecimento foram aplicadas em sessões com um especialista em petrografia sedimentar, gerando os principais objetos do domínio que precisavam ser modelados para se atingir o objetivo da ordenação de eventos. Esses objetos foram representados como um modelo de conhecimento específico para o domínio da petrografia, aplicando os construtos de eventos e relação temporal. Esse modelo foi validado através da implementação de um módulo de inferência no sistema PetroGrapher. A validação foi efetuada comparando as respostas do algoritmo com as interpretações do especialista, e foi possível notar que apesar de a apresentação gráfica da seqüência de eventos ainda ser diferente da original do especialista, o algoritmo efetua a ordenação de eventos corretamente. The application domain of this work is the sedimentary petrography. This domain presents several interpretation tasks that demand specialized knowledge for their solution. Among these tasks, the focus of this work is the diagenetic sequence interpretation, which aims to identify the order in that diagenetic processes occurred over the constituents of sedimentary rocks. In order to understand and collect the necessary knowledge for modeling this task, the main techniques of knowledge acquisition for knowledge-based systems were applied to an expert in sedimentary petrography. These sessions of knowledge acquisition revealed the domain objects that needed to be modeled to reach the objective of the ordering of events. Those objects were represented in a knowledge model for the petrography domain, which applied the proposed constructs (events and time relation). That model was validated by the implementation of an inference module in the PetroGrapher system. The validation proceeded by comparing the outputs of the algorithm with the expert's interpretations, and it was possible to notice that despite the graphic presentation of the sequence of events being different from what the expert produces as a sequence of events, the algorithm is able to order the events correctly.

Ontologias de representação de conhecimento são modelos que agrupam e definem construtos de modelagem (tais como conceito, classe, frame). Uma ontologia temporal é uma especificação de uma conceitualização do domínio acrescida dos aspectos de tempo sobre os objetos do domínio. No caso de esta ontologia tratar somente de aspectos temporais ligados a eventos, ela é chamada ontologia de eventos. Este trabalho propõe uma extensão de uma ontologia de representação de conhecimento (RC) com construtos temporais, ou seja, estender um modelo de conceitualização de domínios com os construtos necessários para se representar eventos. A definição original de uma ontologia de RC foi estendida neste trabalho com os seguintes construtos: (i) o construto evento (que define um evento como um acontecimento que pode alterar objetos do domínio) e (ii) o construto relação-temporal (que define uma relação de tempo entre os eventos). O objetivo deste trabalho é, baseando-se nos novos construtos propostos na ontologia de RC, criar um modelo de conhecimento específico para um domínio, o qual suporta a representação das seguintes primitivas: características do domínio, eventos geradores das características do domínio, associações entre características do domínio, relações temporais entre eventos. Além disso, o modelo tem o objetivo de suportar métodos de raciocínio para inferir a seqüência em que as características do domínio foram geradas pelos eventos, ou seja, inferir a ordem dos eventos. O domínio de aplicação deste trabalho é a petrografia sedimentar. Esse domínio apresenta diversas tarefas de interpretação que exigem conhecimento especializado para sua solução. Dentre estas tarefas, o foco de estudo deste trabalho é a interpretação de seqüência diagenética, a qual procura identificar a ordem em que os processos diagenéticos atuaram sobre os constituintes das rochas sedimentares. Para compreender e coletar o conhecimento necessário para a modelagem dessa tarefa, as principais técnicas de aquisição de conhecimento para sistemas baseados em conhecimento foram aplicadas em sessões com um especialista em petrografia sedimentar, gerando os principais objetos do domínio que precisavam ser modelados para se atingir o objetivo da ordenação de eventos. Esses objetos foram representados como um modelo de conhecimento específico para o domínio da petrografia, aplicando os construtos de eventos e relação temporal. Esse modelo foi validado através da implementação de um módulo de inferência no sistema PetroGrapher. A validação foi efetuada comparando as respostas do algoritmo com as interpretações do especialista, e foi possível notar que apesar de a apresentação gráfica da seqüência de eventos ainda ser diferente da original do especialista, o algoritmo efetua a ordenação de eventos corretamente. / O domínio de aplicação deste trabalho é a petrografia sedimentar. Esse domínio apresenta diversas tarefas de interpretação que exigem conhecimento especializado para sua solução. Dentre estas tarefas, o foco de estudo deste trabalho é a interpretação de seqüência diagenética, a qual procura identificar a ordem em que os processos diagenéticos atuaram sobre os constituintes das rochas sedimentares. Para compreender e coletar o conhecimento necessário para a modelagem dessa tarefa, as principais técnicas de aquisição de conhecimento para sistemas baseados em conhecimento foram aplicadas em sessões com um especialista em petrografia sedimentar, gerando os principais objetos do domínio que precisavam ser modelados para se atingir o objetivo da ordenação de eventos. Esses objetos foram representados como um modelo de conhecimento específico para o domínio da petrografia, aplicando os construtos de eventos e relação temporal. Esse modelo foi validado através da implementação de um módulo de inferência no sistema PetroGrapher. A validação foi efetuada comparando as respostas do algoritmo com as interpretações do especialista, e foi possível notar que apesar de a apresentação gráfica da seqüência de eventos ainda ser diferente da original do especialista, o algoritmo efetua a ordenação de eventos corretamente. The application domain of this work is the sedimentary petrography. This domain presents several interpretation tasks that demand specialized knowledge for their solution. Among these tasks, the focus of this work is the diagenetic sequence interpretation, which aims to identify the order in that diagenetic processes occurred over the constituents of sedimentary rocks. In order to understand and collect the necessary knowledge for modeling this task, the main techniques of knowledge acquisition for knowledge-based systems were applied to an expert in sedimentary petrography. These sessions of knowledge acquisition revealed the domain objects that needed to be modeled to reach the objective of the ordering of events. Those objects were represented in a knowledge model for the petrography domain, which applied the proposed constructs (events and time relation). That model was validated by the implementation of an inference module in the PetroGrapher system. The validation proceeded by comparing the outputs of the algorithm with the expert's interpretations, and it was possible to notice that despite the graphic presentation of the sequence of events being different from what the expert produces as a sequence of events, the algorithm is able to order the events correctly.

Hoje em dia, muitas empresas de petróleo estão adotando diferentes sistemas baseados em conhecimento com o objetivo de ter uma melhor predição de qualidade de reservatório. No entanto, existem obstáculos que não permitem geólogos com diferentes formações recuperar as informações sem a necessidade da ajuda de um especialista em tecnologia da informação. O principal problema é a heterogeneidade semântica dos usuários finais quando fazem consultas em um sistema de consulta visual (VQS). Isto pode ser pior quando há uma nova terminologia na base de conhecimentos que afetam a interação do usuário, especialmente para usuários novatos. Neste contexto, apresentamos contribuições teóricas e práticas que explora o sinergismo entre ontologia e interação homem-computador (HCI). Do lado da teoria, introduzimos o conceito de visão de ontologia bem fundamentada e a sua definição formal. Nós nos concentramos na extração de vista ontologia de uma ontologia bem fundamentada e completa, baseando-nos em meta-propriedades ontológicas e propusemos um algorítmo independente da linguagem para extração de sub-ontologia que é guiada por meta-propriedades ontológicas. No lado prático, baseado nos princípios de HCI e desenho de interação, propusemos um novo sistema de consulta visual que usa o enfoque de vistas de ontologias para guiar o processo de consulta. Também o nosso desenho inclui visualizações de dados que ajudarão geólogos a entender os dados recuperados. Além disso, avaliamos nosso desenho com um teste de usabilidade a-través de um questionário em experimento controlado. Cinco geólogos que trabalham na área de Geologia do Petróleo foram avaliados. O enfoque proposto é avaliado no domínio de petrografia tomando as comunidades de Diagênese e Microestrutural adotando o critério de precisão e revocação. Os resultados experimentais mostram que termos relevantes obtidos de documentos de uma comunidade varia entre 30 a 66% de precisão e 4.6 a 36% de revocação, dependendo do enfoque selecionado e da combinação de parâmetros. Além disso, os resultados mostram que, para toda combinação de parâmetros, a revocação obtidos de artigos de diagênese usando a sub-ontologia gerada para a comunidade de diagênese é maior que a revocação e f-measure usando a sub-ontologia gerada para a comunidade de microestrutural. Por outro lado, resultados para toda combinação de parâmetros mostram que a revocação e f-measure obtida de artigos de microestrutural usando a sub-ontologia gerada para a comunidade de microestrutural é maior que a revocação e o fmeasure usando a sub-ontologia gerada para a comunidade de diagêneses. / Nowadays many petroleum companies are adopting different knowledge-based systems aiming to have a better reservoir quality prediction. However, there are obstacles that not allow different background geologists to retrieve information without needing the help of an information technology expert. The main problem is the heterogeneity semantic of end users when doing queries in a visual query system (VQS). This can be worst when there is new terminology in the knowledge-base affecting the user interaction, particularly for novice users. In this context, we present theoretical and practical contributions that exploit the synergism between ontology and human computer interaction (HCI). On the theory side, we introduce the concept of ontology view for well-founded ontology and provide a formal definition and expressive power characterization. We focus in the ontology view extraction of a well-founded and complete ontology based on ontological meta-properties and propose a language independent algorithm for sub-ontology extraction, which is guided by ontological meta-properties. On the practical side, based on the principles of HCI and interaction design, we propose a new Visual Query System that uses the ontology view approach to guide the query process. Also, our design includes data visualizations that will help geologists to make sense of the retrieved data. Furthermore, we evaluated our interaction design with five users performing a usability testing through a questionnaire in a controlled experiment. The evaluation was performed over geologists that work in the area of petroleum geology. The approach proposed is evaluated on the petrography domain taking the communities of Diagenesis and MicroStructural adopting the well known criteria of precision and recall. Experimental results show that relevant terms obtained from the documents of a community varies from 30 to 66 % of precision and 4.6 to 36% of recall depending on the approach selected and the parameters combination. Furthermore, results show that almost for all the parameters combination that recall and f-measure obtained from diagenesis articles using the sub-ontology generated for the diagenesis community is greater than recall and f-measure using the sub-ontology generated for microstructural community. On the other hand, results for all the parameters combination that recall and f-measure obtained from microstructural articles using the sub-ontology generated for the microstructural community is greater than recall and f-measure using the subontology generated for diagenesis community.

Nos domínios visuais, interpretações são iniciadas pela identificação de feições em imagens que irão, posteriormente, dar suporte aos processos mais abstratos de inferência. Para desenvolver sistemas de conhecimento neste tipo de domínio é necessário buscar a melhor representação do conhecimento visual para ser utilizado pelos métodos de inferência. A representação em formato simbólico deste conhecimento auxilia na captura do conhecimento implícito presente em imagens, permitindo seu uso nos processos de raciocínio, mesmo aceitando que parte desse conhecimento não é externalizado e, em conseqüência, não poderá ser representado adequadamente. Estudos recentes têm utilizado anotação de imagens como uma maneira capaz de auxiliar na explicitação do conhecimento, ampliando a expressividade dos formalismos de representação e permitindo o registro das informações associadas às imagens. Embora anotações de imagens flexibilizem a captura do conhecimento, ontologias são associadas às anotações para garantir a formalização do conhecimento nas imagens, suprindo os termos de domínio que podem ser usados para anotar e auxiliar a uniformização da linguagem nas consultas. O objetivo desse trabalho é capturar e documentar o conhecimento visual que dá suporte à inferência nas tarefas de interpretações. Nesse trabalho é elaborada uma maneira de identificar objetos em imagens que contenham feições diagnósticas através da utilização de uma ontologia de domínio pré-existente. Essa identificação de objetos é explorada para permitir a localização física de uma determinada feição em um objeto real. O resultado disso é a identificação de feições em uma imagem tendo-se um referencial de posição segundo um sistema de coordenadas espacial, possibilitando o seu re-posicionamento. O trabalho ainda explora recursos para a melhor utilização de informações relacionadas a uma imagem. Dessa forma, serve de documentação auxiliar para prover diferencial em interpretações. O domínio de aplicação deste trabalho é a Petrografia Sedimentar que tem como uma das tarefas a descrição quantitativa e qualitativa dos minerais que compõem uma amostra de rocha, visando a análise do potencial de um reservatório de petróleo. As informações são visualizadas em uma amostra de rocha e, assim, um especialista toma decisões quanto à viabilidade de exploração do reservatório. Esse modelo foi validado através da implementação de um módulo de anotação de imagem e de referenciamento de objetos, juntamente com um hardware. O processo de descrição de amostra de rocha é detalhado para se explorar o conhecimento em imagens com a precisão da localização dos objetos nela identificados. Essa abordagem complementa os modelos de representação simbólica, que normalmente são insuficientes para capturar a semântica das feições que dão suporte a inferência em domínios visuais. / Problem solvers in visual domains apply image interpretation to extract evidences to support the reasoning process in the search of solution. In order to develop knowledge systems in this kind of domain, it is necessary to represent the knowledge that is extracted from the scenes in the domain in such way that can be used by the inference methods. The symbolic representation formalisms help in shading light on the implicit knowledge embodied in images, allowing its use in reasoning processes, even accepting that part of this knowledge can not be properly expressed by the experts and, in consequence, it is never going to be adequately represented in knowledge models. Some studies use image annotation to extend the semantic capture of the visual knowledge beyond the expressiveness of representation formalisms, allowing that additional content could be described and stored with the images. Although the annotation is a more flexible way of capturing knowledge, ontologies are used along with it to guarantee the formalization of the knowledge annotated in the images, supplying the domain terms that can be used in the annotation process and helping the uniformization of the language and further consultation. The goal of this work is capturing and documenting the visual knowledge that supports inference on interpretation tasks. The work offer a way of identifying objects in images that correspond to diagnostic features and describing them with the support of a pre-existent domain ontology. The object identification is associated to the physical location of the feature in the real object, with the help of a hardware appliance. The result is the feature identification in the image with the reference of its position in a system of spatial coordinates. The work also explores multimedia resources for the best use of information associated to the image, providing an extra-support for knowledge documentation for interpretation tasks. The application domain of this work is the sedimentary petrography, the formal description of rocks in the scope of Petrological studies. The task in focus is the compositional description of minerals in a rock sample, both in qualitative and quantitative way, in order to evaluate the potential of a petroleum reservoir. Several aspects of the rock are studied by the geologist to suggest better techniques for exploration and production of oil fields. The approach defined in this project was validated through the implementation of an image annotation and referencing modules associated to microscope stage appliance that allows the computer to control the movement of the stage during the description process. The whole process of rock sample analysis using the software and the hardware is detailed in order to expose the visual knowledge and its physical position in the rock sample. This approach complements the symbolic representation models that are usually insufficient to capture the semantic of diagnostic features that support reasoning in visual domains.

Um Sistema de Informação Geográfica armazena e mantém dados geográficos, combinando-os, para obter novas representações do espaço geográfico. A junção espacial combina duas relações de geometrias geo-referenciadas de acordo com algum predicado espacial, como intersecção e distância entre objetos. Trata-se de uma operação essencial, pois é constantemente utilizada e possui um alto custo de realização devido a realização de grande número de operações de Entrada/Saída e a complexidade do algoritmo. Este trabalho estuda o desempenho de algoritmos de junção espacial. Inicialmente, apresenta a análise dos algoritmos já publicados na literatura, obtendo expressões de custo para número de operações de disco e processamento. Após, descreve-se a implementação de alguns algoritmos em um ambiente de testes. Este ambiente permite ao usuário variar diversos parâmetros de entrada: cardinalidade dos conjuntos, memória disponível e predicado de junção, envolvendo dados reais e sintéticos. O ambiente de testes inclui os algoritmos de Laços Aninhados, Partition Based Spatial Join Method (PBSM), Synchronized Tree Transversal (STT) para árvores R* e Iterative Spatial Stripped Join (ISSJ). Os testes demonstraram que o STT é adequado para conjuntos pequenos de dados; o ISSJ se houver memória suficiente para ordenar os conjuntos internamente; e o PBSM se houver pouca memória disponível para buffer de dados. A partir da análise um novo algoritmo, chamado Histogram-based Hash Stripped Join (HHSJ) é apresentado. O HSSJ utiliza histogramas da distribuição dos objetos no espaço para definir o particionamento, armazena os objetos em arquivos organizados em hash e subdivide o espaço em faixas (strips) para reduzir o processamento. Os testes indicam que o HHSJ é mais rápido na maioria dos cenários, sendo ainda mais vantajoso quanto maior o número de objetos envolvidos na junção. Um módulo de otimização de consultas baseado em custos, capaz de escolher o melhor algoritmo para realizar a etapa de filtragem é descrito. O módulo utiliza informações estatísticas mantidas no dicionário de dados para estimar o tempo de resposta de cada algoritmo, e indicar o mais rápido para realizar uma operação específica. Este otimizador de consultas acertou a indicação em 88,9% dos casos, errando apenas na junção de conjuntos pequenos, quando o impacto é menor. / A Geographic Information System (GIS) stores geographic data, combining them to obtain new representations of the geographic space. The spatial join operation combines two sets of spatial features, A and B, based on a spatial predicate. It is a fundamental as well as one of the most expensive operations in GIS. Combining pairs of spatial, georreferenced data objects of two different, and probably large data sets implies the execution of a significant number of Input/Output (I/O) operations as well as a large number of CPU operations. This work presents a study about the performance of spatial join algorithms. Firstly, an analysis of the algorithms is realized. As a result, mathematical expressions are identified to predict the number of I/O operations and the algorithm complexity. After this, some of the algorithms (e.g.; Nested Loops, Partition Based Spatial Join Method (PBSM), Synchronized Tree Transversal (STT) to R-Trees and Iterative Spatial Stripped Join (ISSJ)) are implemented, allowing the execution of a series of tests in different spatial join scenarios. The tests were performed using both synthetic and real data sets. Based on the results, a new algorithm, called Histogram-based Hash Stripped Join (HHSJ), is proposed. The partitioning of the space is carried out according to the spatial distribution of the objects, maintained in histograms. In addition, a hash file is created for each input data set and used to enhance both the storage of and the access to the minimum bounding rectangles (MBR) of the respective set elements. Furthermore, the space is divided in strips, to reduce the processing time. The results showed that the new algorithm is faster in almost all scenarios, specially when bigger data sets are processed. Finally, a query optimizer based on costs, capable to choose the best algorithm to perform the filter step of a spatial join operation, is presented. The query optimizer uses statistical information stored in the data dictionary to estimate the response time for each algorithm and chooses the faster to realize the operation. This query optimizer choose the right one on 88.9% of cases, mistaken just in spatial join envolving small data sets, when the impact is small.

Um Sistema de Informação Geográfica armazena e mantém dados geográficos, combinando-os, para obter novas representações do espaço geográfico. A junção espacial combina duas relações de geometrias geo-referenciadas de acordo com algum predicado espacial, como intersecção e distância entre objetos. Trata-se de uma operação essencial, pois é constantemente utilizada e possui um alto custo de realização devido a realização de grande número de operações de Entrada/Saída e a complexidade do algoritmo. Este trabalho estuda o desempenho de algoritmos de junção espacial. Inicialmente, apresenta a análise dos algoritmos já publicados na literatura, obtendo expressões de custo para número de operações de disco e processamento. Após, descreve-se a implementação de alguns algoritmos em um ambiente de testes. Este ambiente permite ao usuário variar diversos parâmetros de entrada: cardinalidade dos conjuntos, memória disponível e predicado de junção, envolvendo dados reais e sintéticos. O ambiente de testes inclui os algoritmos de Laços Aninhados, Partition Based Spatial Join Method (PBSM), Synchronized Tree Transversal (STT) para árvores R* e Iterative Spatial Stripped Join (ISSJ). Os testes demonstraram que o STT é adequado para conjuntos pequenos de dados; o ISSJ se houver memória suficiente para ordenar os conjuntos internamente; e o PBSM se houver pouca memória disponível para buffer de dados. A partir da análise um novo algoritmo, chamado Histogram-based Hash Stripped Join (HHSJ) é apresentado. O HSSJ utiliza histogramas da distribuição dos objetos no espaço para definir o particionamento, armazena os objetos em arquivos organizados em hash e subdivide o espaço em faixas (strips) para reduzir o processamento. Os testes indicam que o HHSJ é mais rápido na maioria dos cenários, sendo ainda mais vantajoso quanto maior o número de objetos envolvidos na junção. Um módulo de otimização de consultas baseado em custos, capaz de escolher o melhor algoritmo para realizar a etapa de filtragem é descrito. O módulo utiliza informações estatísticas mantidas no dicionário de dados para estimar o tempo de resposta de cada algoritmo, e indicar o mais rápido para realizar uma operação específica. Este otimizador de consultas acertou a indicação em 88,9% dos casos, errando apenas na junção de conjuntos pequenos, quando o impacto é menor. / A Geographic Information System (GIS) stores geographic data, combining them to obtain new representations of the geographic space. The spatial join operation combines two sets of spatial features, A and B, based on a spatial predicate. It is a fundamental as well as one of the most expensive operations in GIS. Combining pairs of spatial, georreferenced data objects of two different, and probably large data sets implies the execution of a significant number of Input/Output (I/O) operations as well as a large number of CPU operations. This work presents a study about the performance of spatial join algorithms. Firstly, an analysis of the algorithms is realized. As a result, mathematical expressions are identified to predict the number of I/O operations and the algorithm complexity. After this, some of the algorithms (e.g.; Nested Loops, Partition Based Spatial Join Method (PBSM), Synchronized Tree Transversal (STT) to R-Trees and Iterative Spatial Stripped Join (ISSJ)) are implemented, allowing the execution of a series of tests in different spatial join scenarios. The tests were performed using both synthetic and real data sets. Based on the results, a new algorithm, called Histogram-based Hash Stripped Join (HHSJ), is proposed. The partitioning of the space is carried out according to the spatial distribution of the objects, maintained in histograms. In addition, a hash file is created for each input data set and used to enhance both the storage of and the access to the minimum bounding rectangles (MBR) of the respective set elements. Furthermore, the space is divided in strips, to reduce the processing time. The results showed that the new algorithm is faster in almost all scenarios, specially when bigger data sets are processed. Finally, a query optimizer based on costs, capable to choose the best algorithm to perform the filter step of a spatial join operation, is presented. The query optimizer uses statistical information stored in the data dictionary to estimate the response time for each algorithm and chooses the faster to realize the operation. This query optimizer choose the right one on 88.9% of cases, mistaken just in spatial join envolving small data sets, when the impact is small.

Um Sistema de Informação Geográfica armazena e mantém dados geográficos, combinando-os, para obter novas representações do espaço geográfico. A junção espacial combina duas relações de geometrias geo-referenciadas de acordo com algum predicado espacial, como intersecção e distância entre objetos. Trata-se de uma operação essencial, pois é constantemente utilizada e possui um alto custo de realização devido a realização de grande número de operações de Entrada/Saída e a complexidade do algoritmo. Este trabalho estuda o desempenho de algoritmos de junção espacial. Inicialmente, apresenta a análise dos algoritmos já publicados na literatura, obtendo expressões de custo para número de operações de disco e processamento. Após, descreve-se a implementação de alguns algoritmos em um ambiente de testes. Este ambiente permite ao usuário variar diversos parâmetros de entrada: cardinalidade dos conjuntos, memória disponível e predicado de junção, envolvendo dados reais e sintéticos. O ambiente de testes inclui os algoritmos de Laços Aninhados, Partition Based Spatial Join Method (PBSM), Synchronized Tree Transversal (STT) para árvores R* e Iterative Spatial Stripped Join (ISSJ). Os testes demonstraram que o STT é adequado para conjuntos pequenos de dados; o ISSJ se houver memória suficiente para ordenar os conjuntos internamente; e o PBSM se houver pouca memória disponível para buffer de dados. A partir da análise um novo algoritmo, chamado Histogram-based Hash Stripped Join (HHSJ) é apresentado. O HSSJ utiliza histogramas da distribuição dos objetos no espaço para definir o particionamento, armazena os objetos em arquivos organizados em hash e subdivide o espaço em faixas (strips) para reduzir o processamento. Os testes indicam que o HHSJ é mais rápido na maioria dos cenários, sendo ainda mais vantajoso quanto maior o número de objetos envolvidos na junção. Um módulo de otimização de consultas baseado em custos, capaz de escolher o melhor algoritmo para realizar a etapa de filtragem é descrito. O módulo utiliza informações estatísticas mantidas no dicionário de dados para estimar o tempo de resposta de cada algoritmo, e indicar o mais rápido para realizar uma operação específica. Este otimizador de consultas acertou a indicação em 88,9% dos casos, errando apenas na junção de conjuntos pequenos, quando o impacto é menor. / A Geographic Information System (GIS) stores geographic data, combining them to obtain new representations of the geographic space. The spatial join operation combines two sets of spatial features, A and B, based on a spatial predicate. It is a fundamental as well as one of the most expensive operations in GIS. Combining pairs of spatial, georreferenced data objects of two different, and probably large data sets implies the execution of a significant number of Input/Output (I/O) operations as well as a large number of CPU operations. This work presents a study about the performance of spatial join algorithms. Firstly, an analysis of the algorithms is realized. As a result, mathematical expressions are identified to predict the number of I/O operations and the algorithm complexity. After this, some of the algorithms (e.g.; Nested Loops, Partition Based Spatial Join Method (PBSM), Synchronized Tree Transversal (STT) to R-Trees and Iterative Spatial Stripped Join (ISSJ)) are implemented, allowing the execution of a series of tests in different spatial join scenarios. The tests were performed using both synthetic and real data sets. Based on the results, a new algorithm, called Histogram-based Hash Stripped Join (HHSJ), is proposed. The partitioning of the space is carried out according to the spatial distribution of the objects, maintained in histograms. In addition, a hash file is created for each input data set and used to enhance both the storage of and the access to the minimum bounding rectangles (MBR) of the respective set elements. Furthermore, the space is divided in strips, to reduce the processing time. The results showed that the new algorithm is faster in almost all scenarios, specially when bigger data sets are processed. Finally, a query optimizer based on costs, capable to choose the best algorithm to perform the filter step of a spatial join operation, is presented. The query optimizer uses statistical information stored in the data dictionary to estimate the response time for each algorithm and chooses the faster to realize the operation. This query optimizer choose the right one on 88.9% of cases, mistaken just in spatial join envolving small data sets, when the impact is small.

Um software de modelagem de especiação geoquímica é responsável pelo cálculo da distribuição das espécies dissolvidas entre solutos e complexos aquosos, e também computar os índices de saturação para diferentes minerais. Neste trabalho nós apresentamos SHPECK, um software desenvolvido para modelar sistemas de equilíbrio geoquímico usando condições de balanço de massa baseadas no conceito da lei de fases (GARRELS; CHRIST, 1965). SHPECK gera um sistema de equações de ação de massa acopladas com restrições de equilíbrio e resolve com a utilização do método se Newton-Raphson. Nosso software aceita qualquer combinação de elementos, espécies e reações, permitindo ao usuário criar diferentes ambientes de simulação e, portanto, controlar qualquet aspecto e configuração do modelo. SHPECK contém uma interface de interação com o usuário e também um banco de dados estruturado que controla todo o gerenciamento dos dados termodinâmicos utilizados para a modelagem geoquímica. Aliado a isso, apresentamos também os conceitos básicos necessários para compreenção da modelagem geoquímica seguida por uma revisão de opções de software disponíveis para modelagem geoquímica. Para finalizar, fizemos uma validação do SHPECK através da modelagem de um sistema de reações diagenéticas observadas em um reservatório asiliclástico e realizamos um estudo comparativo dos resultados do SHPECK com outros software disponíveis. Também para validação, realizamos uma avaliação de tempo de acesso ao banco de dados e pode-se notar um aumento de performance considerável através do uso de um banco de dados relacional comparando-se aos approaches existentes. / A geochemical speciation modeling software is responsible for calculating the distribution of dissolved species between solutes and aqueous complexes, and also computes saturation indexes for different minerals. In this work we introduce SHPECK, a software program developed to model geochemical equilibrium systems using the mass-balance conditions based on the phase rule concept (GARRELS; CHRIST, 1965). SHPECK composes a system of mass-action equations coupled with equilibrium constraints and solve using Newton-Raphson method. Our software accepts any general combination of elements, species, and reactions, allowing the user to create different environments, simulations and, therefore, fully control any aspect and configuration of the model. It provides an interactive user interface as well as the support of a builtfrom- the-ground database structure that handles the management of the whole thermodynamic data used for the geochemical modeling. Also, we present the basic concepts for geochemical modeling followed by a computer science based review about the available geochemical modeling software. Finally, we validate SHPECK by modeling the diagenetic reactions observed in asiliciclastic reservoir and by performing a comparative study with other modelling software package. In addition to this, a database comparison was addressed and the results demonstrate a substantial improvement on the performance by the use of the SHPECK’s relational database comparing to the existent approaches.

Um software de modelagem de especiação geoquímica é responsável pelo cálculo da distribuição das espécies dissolvidas entre solutos e complexos aquosos, e também computar os índices de saturação para diferentes minerais. Neste trabalho nós apresentamos SHPECK, um software desenvolvido para modelar sistemas de equilíbrio geoquímico usando condições de balanço de massa baseadas no conceito da lei de fases (GARRELS; CHRIST, 1965). SHPECK gera um sistema de equações de ação de massa acopladas com restrições de equilíbrio e resolve com a utilização do método se Newton-Raphson. Nosso software aceita qualquer combinação de elementos, espécies e reações, permitindo ao usuário criar diferentes ambientes de simulação e, portanto, controlar qualquet aspecto e configuração do modelo. SHPECK contém uma interface de interação com o usuário e também um banco de dados estruturado que controla todo o gerenciamento dos dados termodinâmicos utilizados para a modelagem geoquímica. Aliado a isso, apresentamos também os conceitos básicos necessários para compreenção da modelagem geoquímica seguida por uma revisão de opções de software disponíveis para modelagem geoquímica. Para finalizar, fizemos uma validação do SHPECK através da modelagem de um sistema de reações diagenéticas observadas em um reservatório asiliclástico e realizamos um estudo comparativo dos resultados do SHPECK com outros software disponíveis. Também para validação, realizamos uma avaliação de tempo de acesso ao banco de dados e pode-se notar um aumento de performance considerável através do uso de um banco de dados relacional comparando-se aos approaches existentes. / A geochemical speciation modeling software is responsible for calculating the distribution of dissolved species between solutes and aqueous complexes, and also computes saturation indexes for different minerals. In this work we introduce SHPECK, a software program developed to model geochemical equilibrium systems using the mass-balance conditions based on the phase rule concept (GARRELS; CHRIST, 1965). SHPECK composes a system of mass-action equations coupled with equilibrium constraints and solve using Newton-Raphson method. Our software accepts any general combination of elements, species, and reactions, allowing the user to create different environments, simulations and, therefore, fully control any aspect and configuration of the model. It provides an interactive user interface as well as the support of a builtfrom- the-ground database structure that handles the management of the whole thermodynamic data used for the geochemical modeling. Also, we present the basic concepts for geochemical modeling followed by a computer science based review about the available geochemical modeling software. Finally, we validate SHPECK by modeling the diagenetic reactions observed in asiliciclastic reservoir and by performing a comparative study with other modelling software package. In addition to this, a database comparison was addressed and the results demonstrate a substantial improvement on the performance by the use of the SHPECK’s relational database comparing to the existent approaches.

Um software de modelagem de especiação geoquímica é responsável pelo cálculo da distribuição das espécies dissolvidas entre solutos e complexos aquosos, e também computar os índices de saturação para diferentes minerais. Neste trabalho nós apresentamos SHPECK, um software desenvolvido para modelar sistemas de equilíbrio geoquímico usando condições de balanço de massa baseadas no conceito da lei de fases (GARRELS; CHRIST, 1965). SHPECK gera um sistema de equações de ação de massa acopladas com restrições de equilíbrio e resolve com a utilização do método se Newton-Raphson. Nosso software aceita qualquer combinação de elementos, espécies e reações, permitindo ao usuário criar diferentes ambientes de simulação e, portanto, controlar qualquet aspecto e configuração do modelo. SHPECK contém uma interface de interação com o usuário e também um banco de dados estruturado que controla todo o gerenciamento dos dados termodinâmicos utilizados para a modelagem geoquímica. Aliado a isso, apresentamos também os conceitos básicos necessários para compreenção da modelagem geoquímica seguida por uma revisão de opções de software disponíveis para modelagem geoquímica. Para finalizar, fizemos uma validação do SHPECK através da modelagem de um sistema de reações diagenéticas observadas em um reservatório asiliclástico e realizamos um estudo comparativo dos resultados do SHPECK com outros software disponíveis. Também para validação, realizamos uma avaliação de tempo de acesso ao banco de dados e pode-se notar um aumento de performance considerável através do uso de um banco de dados relacional comparando-se aos approaches existentes. / A geochemical speciation modeling software is responsible for calculating the distribution of dissolved species between solutes and aqueous complexes, and also computes saturation indexes for different minerals. In this work we introduce SHPECK, a software program developed to model geochemical equilibrium systems using the mass-balance conditions based on the phase rule concept (GARRELS; CHRIST, 1965). SHPECK composes a system of mass-action equations coupled with equilibrium constraints and solve using Newton-Raphson method. Our software accepts any general combination of elements, species, and reactions, allowing the user to create different environments, simulations and, therefore, fully control any aspect and configuration of the model. It provides an interactive user interface as well as the support of a builtfrom- the-ground database structure that handles the management of the whole thermodynamic data used for the geochemical modeling. Also, we present the basic concepts for geochemical modeling followed by a computer science based review about the available geochemical modeling software. Finally, we validate SHPECK by modeling the diagenetic reactions observed in asiliciclastic reservoir and by performing a comparative study with other modelling software package. In addition to this, a database comparison was addressed and the results demonstrate a substantial improvement on the performance by the use of the SHPECK’s relational database comparing to the existent approaches.