[pt] Bases de conhecimento são ferramentas poderosas que fornecem suporte a um amplo espectro de aplicações como, por exemplo, busca exploratória, ranqueamento e recomendação. Bases de conhecimento podem ser vistas como grafos, onde os nós representam entidades e as arestas seus relacionamentos. Atualmente, motores de busca usam bases de conhecimento para melhorar suas recomendações. No entanto, motores de busca são orientados a uma única entidade e enfrentam dificuldades ao tentar explicar porque e como duas entidades estão relacionadas, um problema conhecido como relacionamento entre entidades. Esta tese explora o uso de bases de conhecimento em formato RDF para endereçar o problema de relacionamento entre entidades, em duas direções. Em uma direção, a tese define o conceito de perfis de conectividade para pares de entidades, que são explicações concisas sobre como as entidades se relacionam. A tese introduz uma estratégia para gerar um perfil de conectividade entre um par de entidades, que combina anotações semânticas e métricas de similaridade para resumir um conjunto de caminhos entre as duas entidades. Em seguida, introduz a ferramenta DBpedia profiler, que implementa a estratégia proposta, e cuja efetividade foi medida através de experimentos com usuários. Em outra direção, considerando os desafios para explorar grandes bases de conhecimento online, a tese apresenta uma estratégia genérica de busca baseada na heurística backward, a qual prioriza alguns caminhos sobre outros. A estratégia combina medidas de similaridade e de ranqueamento, criando diferentes alternativas. Por último, a tese avalia e compara as diferentes alternativas em dois domínios, música e filmes, adotando como ground truth rankings especializados de caminhos especialmente desenvolvidos para os experimentos. / [en] Knowledge bases are a powerful tool for supporting a large spectrum of applications such as exploratory search, ranking, and recommendation. Knowledge bases can be viewed as graphs whose nodes represent entities and whose edges represent relationships. Currently, search engines take advantage of knowledge bases to improve their recommendations. However, search engines are single entity-centric and face difficulties when trying to explain why and how two entities are related, a problem known as entity relatedness. This thesis explores the use of knowledge bases in RDF format to address the entity relatedness problem, in two directions. In one direction, it defines the concept of connectivity profiles for entity pairs, which are concise explanations about how the entities are related. The thesis introduces a strategy to generate a connectivity profile for an entity pair that combines semantic annotations and similarity metrics to summarize a set of relationship paths between the given entity pair. The thesis then describes the DBpedia profiler tool, which implements the strategy for DBpedia, and whose effectiveness was evaluated through user experiments. In another direction, motivated by the challenges of exploring large online knowledge bases, the thesis introduces a generic search strategy, based on the backward search heuristic, to prioritize certain paths over others. The strategy combines similarity and ranking measures to create different alternatives. Finally, the thesis evaluates and compares the different alternatives in two domains, music and movies, based on specialized path rankings taken as ground truth.

O uso da XML (Extensible Markup Language) em aplicações envolvendo bancos de dados vem se consolidando nos últimos dois anos. Os principais sistemas de gerenciamento de banco de dados já incorporam essa tecnologia em suas mais recentes versões. Dentre diversas aplicações destaca-se a publicação de dados relacionais em visões XML. Diferentemente da XML, o Modelo Temporal de Versões (TVM) não apresenta suporte entre os bancos de dados atuais. Esse modelo, que une características temporais com o conceito de versão para projetar aplicações orientadas a objetos, precisa ser mapeado para ser adequadamente controlado em um SGBD (Sistema de Gerenciamento de Banco de Dados). Cumprida essa etapa, aplicações do TVM também podem gerar visões XML. Nesse trabalho é inicialmente apresentada uma forma de representar instâncias de aplicações do TVM em um formato XML. Os documentos definidos a partir desse formato de representação são utilizados como base para consultas. Em seguida, é proposta uma extensão de uma linguagem de consulta XML visando proporcionar recursos para a recuperação de informações temporais e de versão representadas em documentos XML. São definidas funções temporais e versionadas que são incorporadas à linguagem base. O funcionamento das funções e a especificação de consultas temporais versionadas são descritos em detalhes no decorrer do trabalho. Uma ferramenta que implementa a linguagem base é utilizada na realização de testes visando validar as novas funções. / The use of the XML in applications involving databases has grown in the last two years. Recent versions of the main database management systems already incorporate this technology. Publishing relational data in XML can be identified as one of the different applications of XML. The Temporal Version Model (TVM) has no support in current databases. This model matches temporal features with the version concept to project object-oriented applications and needs to be mapped to be managed in a DBMS (Database Management System). Once this mapping is achieved, TVM applications can also generate XML views. This work presents initially a way to represent TVM instances in a XML format. Thus, documents created following this representation may be used in queries. Afterwards, an extension of a XML query language is proposed, aiming to provide features for the retrieval of temporal and version information represented in XML documents. Temporal and version functions are defined and incorporated in a base language. The way functions are executed and the specification of temporal version queries are described in details. A tool that implements the base language is used to test the new functions, with the aim of validation.

Esta tese de doutorado apresenta um modelo de especificação, textual e grafico, para sistemas transacionais em banco de dados (ER/T+) e, também, um modelo de implementação desta especificação. Sugere uma técnica de proceduralização de especificações declarativas, usando um grafo de dependencia de fluxos de dados para estabelecer a relação de precedecia entre os fluxos do diagrama da linguagem gráfica de especificação. Apresenta, também, os mecanismos de execução da linguagem de especificação proposta e as regras de mapeamento da linguagem de especificação, em seus aspectos estruturais (dados) e comportamentais (transações), para correspondentes construções na linguagem de implementação (C e SQL). Adicionalmente, são discutidos aspectos de otimização de consultas no âmbito da linguagem de especificação de transações e, também, aspectos de aninhamento de consultas para combinar diversos fluxos do diagrama ER/T+ em expressões complexas de consultas SQL. / This Ph.D thesis presents a graphic and textual specification model for database transactions systems (ER/T+) and, also, an implementation model for this specification. Suggest a proceduralization technique for declarative specifications using a data flow dependency graph to establish a precedence relation between the diagram flows of the graphics specification language. Furthermore it presents the execution mechanism of the proposal specification language and the behavioral and structural rules for mapping the specification language into corresponding implementation language (C and SQL) constructions. Additionaly, are discussed query optimization aspects for transaction specification language and aspects of nested queries to combine various ER/T+ diagram flows into complex SQL query expressions

Bancos de dados biológicos utilizados para comparação e alinhamento local de sequências tem crescido de forma exponencial. Isso popularizou programas que realizam buscas nesses bancos. As implementações dos algoritmos de alinhamento de sequências Smith- Waterman e distância Levenshtein demonstraram ser computacionalmente intensivas e, portanto, propícias para aceleração em hardware. Este trabalho descreve arquiteturas em hardware dedicado prototipadas para FPGA e ASIC para acelerar os algoritmos Smith- Waterman e distância Levenshtein mantendo os mesmos resultados obtidos por softwares. Descrevemos uma nova e eficiente unidade de processamento para o cálculo do Smith- Waterman utilizando affine gap. Também projetamos uma arquitetura que permite particionar as sequências de entrada para a distância Levenshtein em um array sistólico de tamanho fixo. Nossa implementação em FPGA para o Smith-Waterman acelera de 275 a 494 vezes o algoritmo em relação a um computador com processador de propósito geral. Ainda é 52 a 113% mais rápida em relação, segundo nosso conhecimento, as mais rápidas arquiteturas recentemente publicadas. / Bioinformatics databases used for sequence comparison and local sequence alignment are growing exponentially. This has popularized programs that carry out database searches. Current implementations of sequence alignment methods based on Smith- Waterman and Levenshtein distance have proven to be computationally intensive and, hence, amenable for hardware acceleration. This Msc. Thesis describes an FPGA and ASIC based hardware implementation designed to accelerate the Smith-Waterman and Levenshtein distance maintaining the same results yielded by general softwares. We describe an new efficient Smith-Waterman affine gap process element and a new architecture to partitioning and maping the Levenshtein distance into fixed size systolic arrays. Our FPGA Smith-Waterman implementation delivers 275 to 494-fold speed-up over a standard desktop computer and is also about 52 to 113% faster, to the best of our knowledge, than the fastest implementation in a most recent family of accelerators.

O uso da XML (Extensible Markup Language) em aplicações envolvendo bancos de dados vem se consolidando nos últimos dois anos. Os principais sistemas de gerenciamento de banco de dados já incorporam essa tecnologia em suas mais recentes versões. Dentre diversas aplicações destaca-se a publicação de dados relacionais em visões XML. Diferentemente da XML, o Modelo Temporal de Versões (TVM) não apresenta suporte entre os bancos de dados atuais. Esse modelo, que une características temporais com o conceito de versão para projetar aplicações orientadas a objetos, precisa ser mapeado para ser adequadamente controlado em um SGBD (Sistema de Gerenciamento de Banco de Dados). Cumprida essa etapa, aplicações do TVM também podem gerar visões XML. Nesse trabalho é inicialmente apresentada uma forma de representar instâncias de aplicações do TVM em um formato XML. Os documentos definidos a partir desse formato de representação são utilizados como base para consultas. Em seguida, é proposta uma extensão de uma linguagem de consulta XML visando proporcionar recursos para a recuperação de informações temporais e de versão representadas em documentos XML. São definidas funções temporais e versionadas que são incorporadas à linguagem base. O funcionamento das funções e a especificação de consultas temporais versionadas são descritos em detalhes no decorrer do trabalho. Uma ferramenta que implementa a linguagem base é utilizada na realização de testes visando validar as novas funções. / The use of the XML in applications involving databases has grown in the last two years. Recent versions of the main database management systems already incorporate this technology. Publishing relational data in XML can be identified as one of the different applications of XML. The Temporal Version Model (TVM) has no support in current databases. This model matches temporal features with the version concept to project object-oriented applications and needs to be mapped to be managed in a DBMS (Database Management System). Once this mapping is achieved, TVM applications can also generate XML views. This work presents initially a way to represent TVM instances in a XML format. Thus, documents created following this representation may be used in queries. Afterwards, an extension of a XML query language is proposed, aiming to provide features for the retrieval of temporal and version information represented in XML documents. Temporal and version functions are defined and incorporated in a base language. The way functions are executed and the specification of temporal version queries are described in details. A tool that implements the base language is used to test the new functions, with the aim of validation.

Devant des collections massives et hétérogènes de données, les systèmes de RI doivent désormais pouvoir appréhender des comportements d'utilisateurs aussi variés qu'imprévisibles. L'objectif de notre travail est d'évaluer la façon dont un même utilisateur verbalise un besoin informationnel à travers un énoncé de type « expression libre » (appelé langage naturel) et un énoncé de type mots-clés (appelé langage de requêtes). Pour cela, nous nous situons dans un contexte applicatif, à savoir des demandes de remboursement des utilisateurs d'un moteur de recherche dédié à des études économiques en français. Nous avons recueilli via ce moteur, les deux types d'énoncés sur 5 années consécutives totalisant un corpus de 1398 demandes en langage naturel et de 3427 requêtes. Nous avons alors comparé l'expression en tant que tel du besoin informationnel et mis en avant ce qu'apportait, en termes d'informations et de précisions, le recours à l'un ou l'autre du langage utilisé. / With the massive and heterogeneous web document collections, IR system must analyze the behaviors of users which are unpredictable and varied. The approach described in this thesis provides a comparison of the verbalizations for both natural language and web query for the same information need by the same user. For this, we used data collected (i.e. users' complaints in natural language and web queries) through a search engine dedicated to economic reports in French over 5 consecutive years totaling a corpus of 1398 natural language requests and 3427 web queries. Then, we compared the expression of the information need and highlighted the contributions in terms of information and clarification, the use of either language used.

Made available in DSpace on 2016-06-02T19:05:26Z (GMT). No. of bitstreams: 1 1634.pdf: 2033754 bytes, checksum: ef58063d765aca814c3608c0828d4965 (MD5) Previous issue date: 2007-06-22 / Financiadora de Estudos e Projetos / As availability of data from several areas of knowledge grows, it is even more necessary to develop effective techniques to retrieve the desired information, aiming to reduce irrelevant answers and ensure that relevant results are not ignored. Considering this context, we present the FOQuE system, developed to perform query expansion in order to retrieve semantically relevant and broad results. Based on fuzzy ontologies, this system is able to obtain approximate results that satisfy user requirements according to expansion parameters defined by the user. The additional answers retrieved by the FOQuE system are classified according to the semantic expansion performed and the relevance to the query, therefore it is possible to improve results that are presented to the user. / Diante da crescente facilidade de acesso a dados de diversas áreas do conhecimento, cada vez mais são necessárias técnicas eficazes para recuperar a informação desejada, visando reduzir respostas irrelevantes e assegurar que resultados relevantes não sejam desprezados. Dentro deste contexto, este trabalho apresenta o sistema FOQuE, desenvolvido para realizar diversos tipos de expansão de consultas com o intuito de recuperar resultados semanticamente relevantes e abrangentes. Baseado em ontologias difusas, este sistema é capaz de obter resultados aproximados que satisfaçam aos requisitos do usuário, de acordo com parâmetros de expansão especificados por ele. As respostas adicionais recuperadas pelo sistema FOQuE são classificadas segundo o tipo de expansão realizada e a relevância para a consulta, melhorando, assim, a forma como os resultados são apresentados ao usuário.

Ensuring code quality is crucial in software development. Not seldom, developers resort to static analysis tools to assist them in both understanding pieces of code and identifying defects or refactoring opportunities during development activities. A critical issue when defining such tools is their ability to obtain information about code. Static analysis tools depend, in general, of an intermediate program representation to identify locations that meet the conditions described in their algorithms. This perspective can be enlarged when techniques of crosscutting concerns modularization, such as aspect-oriented programming (AOP) is applied. In AOP applications, a piece of code can be systematically affected, using both static and dynamic combinations. The main goal of this dissertation is the specification and the implementation of AQL, a domain-specific language (DSL) designed to search aspect-oriented code bases. AQL is a declarative language, based on object query language (OQL), which enables the task of querying elements, relationships and program metrics to support the construction of static analysis and code searching tools for aspect oriented programs. The language was designed in two steps. First, we built a framework (AOPJungle), responsible to extract data from aspect-oriented programs. AOPJungle performs the computation of metrics, inferences and connections between the elements of the program. In the second step, we built an AQL compiler as a reference implementation. We adopted a source-to-source transformation for this step, in which an AQL query is transformed into HQL statements before being executed. In order to evaluate the reference implementation, we developed a static analysis tool for identifying refactoring opportunities in aspect-oriented programs. This tool receives a set of AQL queries to identify potential scenarios where refactoring could be applied. / Assegurar a qualidade de código é um ponto crucial durante o desenvolvimento de software. Frequentemente, os desenvolvedores recorrem às ferramentas de análise estática para auxiliá-los tanto na compreensão de código, quanto na identificação de defeitos ou de oportunidades de refatoração durante o ciclo de desenvolvimento de aplicações. Um dos pontos críticos na definição de tais ferramentas está na sua capacidade de obter informações a respeito de código. As ferramentas de análise estática dependem, em geral, de uma representação intermediária de um programa para identificar situações que atendam às condições necessárias descritas em seus algoritmos. Esse panorama se amplia com o uso de técnicas de modularização de interesses transversais, tais como a programação orientada a aspectos (POA), na qual um código pode ser afetado de forma sistêmica, por meio de combinações estáticas e dinâmicas. O principal objetivo desta dissertação é a especificação e implementação de AQL, uma DSL (linguagem específica de domínio) para a realização de busca em código orientado a aspectos. A AQL é uma linguagem declarativa, baseada em linguagem de busca em objetos (OQL) e que permite consultar elementos, relações, derivações e métricas de um programa orientado a aspectos (OA), a fim de apoiar a construção de ferramentas de análise estática e de pesquisa em código. O projeto de implementação da linguagem foi realizado em duas etapas. Primeiro, foi criado um framework (AOPJungle) para a extração de dados de programas OA. O AOPJungle além de extrair dados de programas OA, realiza a computação de métricas, inferências e ligações entre os elementos de um programa. Na segunda etapa, um compilador de referência para AQL foi construído. A abordagem adotada foi a transformação fonte a fonte, sendo uma consulta AQL transformada em uma consulta HQL (Hibernate Query Language) antes de sua execução. A fim de avaliar a implementação proposta, uma ferramenta de análise estática para identificação de oportunidades de refatoração em programas AO foi elaborada, usando a AQL para a busca de dados sobre esses programas.

Made available in DSpace on 2015-05-14T12:36:56Z (GMT). No. of bitstreams: 1 parte1.pdf: 1854774 bytes, checksum: 9564eb94b101d580f9879bf9c9422f98 (MD5) Previous issue date: 2010-08-10 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Several areas of knowledge domain, such as remote sensing systems, transportation, telecommunication, digital mapping, among others, make use of large amounts of geographic data. Typically, these data are stored in Management Systems Geographic Database (SGBDGeo), through which can be often manipulated by Geographic Information Systems (GIS). However, these systems are not able to extract new information, previously unknown to users, which may be embedded within the database field analysed and that, somehow, represent new and userful knowledge, for example, for decision making. In this case, it is necessary to make use of specific techniques of Knowledge Discovery in Databases (KDD). Moreover, spatial data present inherently visual characteristics that, often, can be associated with geometric and pictographic visual representations. In this context, there are few visual query languages for spatial data. However, few of this treat mining methods among the spatial data. Thus, this paper proposes the construction of an environment for data mining tasks performed under certain geographical areas, beyond the formal specification of a visual query language to be used in this environment. These queries are formulated through pictorial representations of geographic features, operators, and spatial relationships between these data. To this end, we use metaphorical abstractions on the metadata of the geographical environment, and the approach defined as "flowing stream" in which the user focuses attention on certain stages of the mining process, facilitating the construction of these consultations a number of them. Thus, the proposed environment aims to simplify the tasks of consultations on mining spatial data, making them more user friendly, providing more efficiency and speed when compared to textual queries scripts. / Diversas áreas de domínio de conhecimento, tais como os sistemas de sensoriamente remoto, transportes, telecomunicações, cartografia digital, entre outras, fazem uso de uma grande quantidade de dados geográficos. Normalmente, esses dados são armazenados em Sistemas Gerenciadores de Banco de Dados Geográficos (SGBDGeo), através dos quais, muitas vezes, podem ser manipulados por Sistemas de Informações Geográficas (SIG). Entretanto, esses sistemas não são capazes de extrair novas informações, previamente desconhecidas pelos usuários, as quais podem estar embutidas dentro da base de dados do domínio analisado e que, de certo modo, representam algum conhecimento novo e de grande utilidade, por exemplo, para tomadas de decisões. Neste caso, é necessário fazer uso de técnicas específicas de Descoberta de Conhecimento em Banco de Dados (DCBD ou KDD, Knowledge Discovery in Database). Além disso, os dados geográficos apresentam características inerentemente visuais que, muitas vezes, podem ser associados a representações visuais geométricas ou pictográficas. Nesse contexto, existem algumas linguagens de consultas visuais para dados geográficos. Todavia, poucas delas tratam métodos de mineração espacial entre os dados. Desta forma, este trabalho propõe a construção de um ambiente para as tarefas de mineração de dados realizada sob certos domínios geográficos, além da especificação formal de uma linguagem de consulta visual a ser usada neste ambiente. Estas consultas são formuladas através de representações pictóricas de feições geográficas, operadores e relacionamentos espaciais existentes entre estes dados. Para tal, utilizam-se abstrações metafóricas sobre os metadados do ambiente geográfico, além da abordagem definida como fluxo corrente na qual o usuário foca a sua atenção em determinadas etapas do processo de mineração, facilitando a construção destas consultas por parte dos mesmos. Desta forma, o ambiente proposto tem como objetivo simplificar as consultas sobre tarefas de mineração de dados geográficos, tornando-as mais amigáveis aos usuários, concedendo mais eficiência e rapidez quando se comparado aos scripts textuais de consultas.

Bancos de dados biológicos utilizados para comparação e alinhamento local de sequências tem crescido de forma exponencial. Isso popularizou programas que realizam buscas nesses bancos. As implementações dos algoritmos de alinhamento de sequências Smith- Waterman e distância Levenshtein demonstraram ser computacionalmente intensivas e, portanto, propícias para aceleração em hardware. Este trabalho descreve arquiteturas em hardware dedicado prototipadas para FPGA e ASIC para acelerar os algoritmos Smith- Waterman e distância Levenshtein mantendo os mesmos resultados obtidos por softwares. Descrevemos uma nova e eficiente unidade de processamento para o cálculo do Smith- Waterman utilizando affine gap. Também projetamos uma arquitetura que permite particionar as sequências de entrada para a distância Levenshtein em um array sistólico de tamanho fixo. Nossa implementação em FPGA para o Smith-Waterman acelera de 275 a 494 vezes o algoritmo em relação a um computador com processador de propósito geral. Ainda é 52 a 113% mais rápida em relação, segundo nosso conhecimento, as mais rápidas arquiteturas recentemente publicadas. / Bioinformatics databases used for sequence comparison and local sequence alignment are growing exponentially. This has popularized programs that carry out database searches. Current implementations of sequence alignment methods based on Smith- Waterman and Levenshtein distance have proven to be computationally intensive and, hence, amenable for hardware acceleration. This Msc. Thesis describes an FPGA and ASIC based hardware implementation designed to accelerate the Smith-Waterman and Levenshtein distance maintaining the same results yielded by general softwares. We describe an new efficient Smith-Waterman affine gap process element and a new architecture to partitioning and maping the Levenshtein distance into fixed size systolic arrays. Our FPGA Smith-Waterman implementation delivers 275 to 494-fold speed-up over a standard desktop computer and is also about 52 to 113% faster, to the best of our knowledge, than the fastest implementation in a most recent family of accelerators.