Em busca da documentação e otimização de seus processos, a área de Business Process Management (BPM) vem cada vez mais atraindo o interesse do meio empresarial, por ser um importante método no auxílio ao ganho de resultados, como redução de custos e aumento de produtividade. Modelar processos, entretanto, não basta. É preciso que se atente para métodos eficientes de armazená-los, permitindo que as informações sejam manipuladas e utilizadas de maneira prática e inteligente. A presente dissertação propõe duas abordagens para armazenamento de modelos de processo, uma em bancos de dados relacionais e outra em bancos de dados orientados a grafos, comparando-os através de aspectos como desempenho na execução das operações e proximidade da abordagem de cada um deles com os modelos de processos. Enquanto os bancos de dados relacionais são mais populares, sendo utilizados na maior parte das aplicações atuais, os bancos de dados orientados a grafos possuem propriedades e representação gráfica semelhantes aos modelos de processos. Foram realizados testes que visam analisar o desempenho de ambas as abordagens, além da facilidade dos usuários em interagir com os modelos propostos. Os resultados deste estudo podem ser utilizados para a criação de repositórios que compartilhem processos de maneira eficiente, bem como incentivar o estudo de novas maneiras para o armazenamento de processos. / Business Process Management (BPM) area has been increasingly attracted the interest of the business community because users are looking for documentation and optimization. These documents can be an important method in helping to gain results such as reduced costs and increased productivity. However, to model processes is not enough. It is necessary to pay attention to efficient storage methods, allowing information to be handled and used in a practical and intelligent way. The present article compares the use of relational databases and graph databases, considering aspects such as performance in the execution of operations and proximity of the approach of each of them with the process models. While relational databases are more popular, being used in most of the current applications, graph databases have properties and graphical representations similar to process models. The results of this study can be used to create repositories which can both share process efficiently, and encourage the study of new ways of storing processes.

O paradigma da orientação a objetos esta se tomando a abordagem preferida para construção de sistemas em ambiente de banco de dados. Por outro lado, a tecnologia relacional e amplamente adotada para gerenciar dados corporativos. Os bancos de dados relacionais tornaram-se o padrão no armazenamento de dados para aplicações de processamento de transações on-line (OLTP). Estas tendências estão motivando a necessidade de construção de aplicações orientadas a objetos que acessem banco de dados relacionais. 0 uso de conceitos orientado a objetos, como herança, permitem uma modelagem !Dais adequada e uma melhor implementação da aplicação baseada em sistema de banco de dados orientado a objetos. Entretanto, os resultados do projeto orientado a objetos, podem também ser aplicados em sistemas clássicos de banco de dados. 0 trabalho apresenta o uso de padrões de projeto na construção de una arquitetura de um framework que auxilie o mapeamento de uma aplicação 00 a um SGBD relacional. Esta arquitetura segue a abordagem de persistência de objetos baseada em gateways, que é uma camada de software inserida entre o sistema gerenciador de banco de dados e a aplicação orientada a objetos, cujo o objetivo é dar suporte a um modelo de programação de aplicações 00. A característica principal desta arquitetura é a separação clara das classes que tratam da base de dados em relação as classes que tratam do domínio do problema da aplicação. Esta divisão de responsabilidades permite a substituição das classes referentes a base de dados por outras, permitindo a migração da aplicação entre bases de dados diferentes. São apresentados neste trabalho, formas de mapeamentos de esquemas orientados a objetos para esquemas relacionais. Estes mapeamentos acontecem do modelo 00 para o modelo relacional. E importante salientar, que a arquitetura que esta sendo proposta, não vai impedir que aplicações estruturadas deixem ter acesso a base de dados relacional mapeada, pois esta abordagem foi escolhida para permitir que novas aplicações 00 tenham acesso a base de dados relacionais já existentes. Como a implementação deste trabalho segue a abordagem de gateway, são apresentados os conceitos de orientação objetos, e como estes serão suportados na arquitetura, ou seja, o que o gateway devera implementar. / The paradigm of the object-oriented is becoming the approach preferred for construction of systems in database environment. On the other hand, the technology relational is adopted thoroughly for management corporate data. The relational databases they became the pattern in the storage of data for applications of processing of transactions on-line (OLTP). These tendencies are motivating the need of construction of applications object-oriented that acessem relational databases. The way of using object-oriented conception, how inheritance, to make possible the better modeling and implementation based in object-oriented database systems. Therefore, the objetc-oriented design results, also is possible to application in classics database systems. The work presents the use of project patterns in the construction of an architecture of a framework that aids the mapeamento of an application 00 to a SGBD relacional. This architecture follows the approach of set persistence of objects in gateways, that is a software layer inserted among the system database manager and the object-oriented application, whose the objective is to give support to a model of programming of applications 00. The main characteristic of this architecture is the clear separation of the classes that are about the database in relation to the classes that are about the domain of the problem of the application. This division of responsibilities allows the substitution of the referring classes the database for other, allowing the migration of the application among different databases. They are presented in this work, forms of mapping the object-oriented model for relational model. These mappings happens of the model 00 for the model relational. It is important to point out, that the architecture that it is being proposed, won't impede that structured applications let to have access to the relational database, because this approach was chosen to allow that new applications 00 has access the relational database already existent. As the implementation of this work follows the gateway approach, the concepts of object-oriented are presented, and as these they will be supported in the architecture, that is to say, which the gateway should implement.

XML vem se tornando um importante meio para intercâmbio de dados, e é frequentemente usada com uma interface para - isto é, uma visão de - um banco de dados relacional. Apesar de existirem muitos trabalhos que tratam de consultas a bancos de dados através de visões XML, o problema de atualização de bancos de dados relacionais através de visões XML não tem recebido muita atenção. Neste trabalho, apresentam-se os primeiros passos para a solução deste problema. Usando query trees para capturar noções de seleção, projeção, aninhamento, agrupamento e conjuntos heterogêneos, presentes na maioria das linguagens de consulta XML, demonstra-se como visões XML expressas através de query trees podem ser mapeadas para um conjunto de visões relacionais correspondentes. Consequentemente, esta tese transforma o problema de atualização de bancos de dados relacionais através de visões XML em um problema clássico de atualização de bancos de dados através de visões relacionais. A partir daí, este trabalho mostra como atualizações na visão XML são mapeadas para atualizações sobre as visões relacionais correspondentes. Trabalhos existentes em atualização de visões relacionais podem então ser aplicados para determinar se as visões são atualizáveis com relação àquelas atualizações relacionais, e em caso a rmativo, traduzir as atualizações para o banco de dados relacional. Como query trees são uma caracterização formal de consultas de de nição de visões, elas não são adequadas para usuários nais. Diante disso, esta tese investiga como um subconjunto de XQuery pode ser usado como uma linguagem de de nição das visões, e como as query trees podem ser usadas como uma representação intermedi ária para consultas de nidas nesse subconjunto. / XML has become an important medium for data exchange, and is frequently used as an interface to - i.e. a view of - a relational database. Although lots of work have been done on querying relational databases through XML views, the problem of updating relational databases through XML views has not received much attention. In this work, we give the rst steps towards solving this problem. Using query trees to capture the notions of selection, projection, nesting, grouping, and heterogeneous sets found throughout most XML query languages, we show how XML views expressed using query trees can be mapped to a set of corresponding relational views. Thus, we transform the problem of updating relational databases through XML views into a classical problem of updating relational databases through relational views. We then show how updates on the XML view are mapped to updates on the corresponding relational views. Existing work on updating relational views can then be leveraged to determine whether or not the relational views are updatable with respect to the relational updates, and if so, to translate the updates to the underlying relational database. Since query trees are a formal characterization of view de nition queries, they are not well suited for end-users. We then investigate how a subset of XQuery can be used as a top level language, and show how query trees can be used as an intermediate representation of view de nitions expressed in this subset.

Informações temporais estão presentes numa ampla gama de aplicações. Praticamente qualquer aplicação possui pelo menos um campo que contém dados temporais como datas ou timestamps. Entretanto, bancos de dados tradicionais não tem um suporte amplo para armazenamento e consulta sobre esse tipo de dados eficientemente, e SGBDs com suporte nativo para dados temporais raramente estão disponíveis para os desenvolvedores de sistemas. Na maior parte do tempo, bases de dados comuns são usadas para armazenar dados das aplicações, e quando dados temporais são necessários, eles são gerenciados utilizando o pobre suporte oferecido por SGBDs relacionais tradicionais. Dito isso, o projetista da base de dados precisa confiar em um bom design de esquema para que a dificuldade natural enfrentada ao lidar com dados temporais possa ser minimizada. Enquanto algumas escolhas de design podem parecer óbvias, outras são difíceis de avaliar apenas com uma análise superficial, necessitando experimentação antes de serem aplicadas ou não. Por exemplo, em vários casos pode ser difícil de medir o quanto uma determinada escolha de design vai afetar o consumo de espaço em disco, e quanto essa mesma escolha afetará a performance geral. Esse tipo de informação é necessária para que o projetista da base de dados seja capaz de determinar se , por exemplo, o aumento no consumo de espaço em disco gerado por uma escolha específica é aceitável por conta da melhora de performance que ela oferece. O problema é que não há estudo que analise as escolhas de design disponíveis, fazendo uma análise através de dados concretos. Mesmo quando é fácil identificar, dentre duas escolhas, qual tem performance melhor em um determinado critério, é difícil mensurar o quão melhor a escolha melhor se sai, e se algum efeito colateral trazido por ela é aceitável. Ter dados concretos para suportar esse tipo de decisão permite ao projetista da base de dados fazer escolhas que se enquadram melhor no contexto da sua aplicação. O objetivo desse trabalho é analisar algumas escolhas de design comuns para representar e gerenciar dados temporais em SGBDs relacionais tradicionais, provendo direcionamento sobre qual alternativa se enquadra melhor em cada situação onde dados temporais são necessários. Dados concretos sobre cada uma das alternativas estudadas são gerados e analisados e conclusões são obtidas a partir deles. / Temporal information is present on a wide range of applications. Almost every application has at least one field that contains temporal data like dates or timestamps. However, traditional databases don’t have a comprehensive support to storage and query this kind of data efficiently, and DBMS with native support for temporal data are rarely available to system developers. Most of the time, regular databases are used to store application data and when temporal data is needed, it is handled using the poor support offered by standard relational DBMS. That said, the database designer must rely on good schema design so that the natural difficulty faced when dealing with temporal data on standard relational DBMS can be minimized. While some design choices may seem obvious, others are difficult to evaluate just by looking at them, therefore needing experimentation prior to being applied or not. For example, in several cases it might be difficult to measure how much will a specific design choice affect the disk space consumption, and how much will this same design choice affect overall performance. This kind of information is needed so that the database designer will be able to determine if, for example, the increased disk space consumption generated by a given choice is acceptable because of the performance enhancement it gives. The problem is that there is no study that analyses the design choices available, analyzing them through concrete data. Even when it is easy to see which of two design choices perform better in a given criterion, it is hard to see how better the better choice does, and if any other side-effect it has is acceptable. Having concrete data to support this kind of decision allows the database designer to make the choices that suits his application’s context best. The objective of this work is to analyze several common design choices to represent and handle different kinds of temporal data on standard SQL DBMS, providing guidance on which alternative suits best each situation where temporal data is required. Concrete data about each of the studied alternatives are generated and analyzed, and conclusions are drawn from them.

Em busca da documentação e otimização de seus processos, a área de Business Process Management (BPM) vem cada vez mais atraindo o interesse do meio empresarial, por ser um importante método no auxílio ao ganho de resultados, como redução de custos e aumento de produtividade. Modelar processos, entretanto, não basta. É preciso que se atente para métodos eficientes de armazená-los, permitindo que as informações sejam manipuladas e utilizadas de maneira prática e inteligente. A presente dissertação propõe duas abordagens para armazenamento de modelos de processo, uma em bancos de dados relacionais e outra em bancos de dados orientados a grafos, comparando-os através de aspectos como desempenho na execução das operações e proximidade da abordagem de cada um deles com os modelos de processos. Enquanto os bancos de dados relacionais são mais populares, sendo utilizados na maior parte das aplicações atuais, os bancos de dados orientados a grafos possuem propriedades e representação gráfica semelhantes aos modelos de processos. Foram realizados testes que visam analisar o desempenho de ambas as abordagens, além da facilidade dos usuários em interagir com os modelos propostos. Os resultados deste estudo podem ser utilizados para a criação de repositórios que compartilhem processos de maneira eficiente, bem como incentivar o estudo de novas maneiras para o armazenamento de processos. / Business Process Management (BPM) area has been increasingly attracted the interest of the business community because users are looking for documentation and optimization. These documents can be an important method in helping to gain results such as reduced costs and increased productivity. However, to model processes is not enough. It is necessary to pay attention to efficient storage methods, allowing information to be handled and used in a practical and intelligent way. The present article compares the use of relational databases and graph databases, considering aspects such as performance in the execution of operations and proximity of the approach of each of them with the process models. While relational databases are more popular, being used in most of the current applications, graph databases have properties and graphical representations similar to process models. The results of this study can be used to create repositories which can both share process efficiently, and encourage the study of new ways of storing processes.

nÃo hà / A iniciativa Linked Data trouxe novas oportunidades para a construÃÃo da nova geraÃÃo de aplicaÃÃes Web. Entretanto, a utilizaÃÃo das melhores prÃticas estabelecidas por este padrÃo depende de mecanismos que facilitem a transformaÃÃo dos dados armazenados em bancos relacionais em triplas RDF. Recentemente, o grupo de trabalho W3C RDB2RDF propÃs uma linguagem de mapeamento padrÃo, denominada R2RML, para especificar mapeamentos customizados entre esquemas relacionais e vocabulÃrios RDF. No entanto, a geraÃÃo de mapeamentos R2RML nÃo à uma tarefa fÃcil. à imperativo, entÃo, definir: (a) uma soluÃÃo para mapear os conceitos de um esquema relacional em termos de um esquema RDF; (b) um processo que suporte a publicaÃÃo dos dados relacionais no formato RDF; e (c) uma ferramenta para facilitar a aplicaÃÃo deste processo. Assertivas de correspondÃncia sÃo propostas para formalizar mapeamentos entre esquemas relacionais e esquemas RDF. VisÃes sÃo usadas para publicar dados de uma base de dados em uma nova estrutura ou esquema. A definiÃÃo de visÃes RDF sobre dados relacionais permite que esses dados possam ser disponibilizados em uma estrutura de termos de uma ontologia OWL, sem que seja necessÃrio alterar o esquema da base de dados. Neste trabalho, propomos uma arquitetura em trÃs camadas â de dados, de visÃes SQL e de visÃes RDF â onde a camada de visÃes SQL mapeia os conceitos da camada de dados nos termos da camada de visÃes RDF. A criaÃÃo desta camada intermediÃria de visÃes facilita a geraÃÃo dos mapeamentos R2RML e evita que alteraÃÃes na camada de dados impliquem em alteraÃÃes destes mapeamentos. Adicionalmente, definimos um processo em trÃs etapas para geraÃÃo das visÃes RDF. Na primeira etapa, o usuÃrio define o esquema do banco de dados relacional e a ontologia OWL alvo e cria assertivas de correspondÃncia que mapeiam os conceitos do esquema relacional nos termos da ontologia alvo. A partir destas assertivas, uma ontologia exportada à gerada automaticamente. O segundo passo produz um esquema de visÃes SQL gerado a partir da ontologia exportada e um mapeamento R2RML do esquema de visÃes para a ontologia exportada, de forma automatizada. Por fim, no terceiro passo, as visÃes RDF sÃo publicadas em um SPARQL endpoint. Neste trabalho sÃo detalhados as assertivas de correspondÃncia, a arquitetura, o processo, os algoritmos necessÃrios, uma ferramenta que suporta o processo e um estudo de caso para validaÃÃo dos resultados obtidos. / The Linked Data initiative brought new opportunities for building the next generation of Web applications. However, the full potential of linked data depends on how easy it is to transform data stored in conventional, relational databases into RDF triples. Recently, the W3C RDB2RDF Working Group proposed a standard mapping language, called R2RML, to specify customized mappings between relational schemas and target RDF vocabularies. However, the generation of customized R2RML mappings is not an easy task. Thus, it is mandatory to define: (a) a solution that maps concepts from a relational schema to terms from a RDF schema; (b) a process to support the publication of relational data into RDF, and (c) a tool that implements this process. Correspondence assertions are proposed to formalize the mappings between relational schemas and RDF schemas. Views are created to publish data from a database to a new structure or schema. The definition of RDF views over relational data allows providing this data in terms of an OWL ontology structure without having to change the database schema. In this work, we propose a three-tier architecture â database, SQL views and RDF views â where the SQL views layer maps the database concepts into RDF terms. The creation of this intermediate layer facilitates the generation of R2RML mappings and prevents that changes in the data layer result in changes on R2RML mappings. Additionally, we define a three-step process to generate the RDF views of relational data. First, the user defines the schema of the relational database and the target OWL ontology. Then, he defines correspondence assertions that formally specify the relational database in terms of the target ontology. Using these assertions, an exported ontology is generated automatically. The second step produces the SQL views that perform the mapping defined by the assertions and a R2RML mapping between these views and the exported ontology. This dissertation describes a formalization of the correspondence assertions, the three-tier architecture, the publishing process steps, the algorithms needed, a tool that supports the entire process and a case study to validate the results obtained.

Informações temporais estão presentes numa ampla gama de aplicações. Praticamente qualquer aplicação possui pelo menos um campo que contém dados temporais como datas ou timestamps. Entretanto, bancos de dados tradicionais não tem um suporte amplo para armazenamento e consulta sobre esse tipo de dados eficientemente, e SGBDs com suporte nativo para dados temporais raramente estão disponíveis para os desenvolvedores de sistemas. Na maior parte do tempo, bases de dados comuns são usadas para armazenar dados das aplicações, e quando dados temporais são necessários, eles são gerenciados utilizando o pobre suporte oferecido por SGBDs relacionais tradicionais. Dito isso, o projetista da base de dados precisa confiar em um bom design de esquema para que a dificuldade natural enfrentada ao lidar com dados temporais possa ser minimizada. Enquanto algumas escolhas de design podem parecer óbvias, outras são difíceis de avaliar apenas com uma análise superficial, necessitando experimentação antes de serem aplicadas ou não. Por exemplo, em vários casos pode ser difícil de medir o quanto uma determinada escolha de design vai afetar o consumo de espaço em disco, e quanto essa mesma escolha afetará a performance geral. Esse tipo de informação é necessária para que o projetista da base de dados seja capaz de determinar se , por exemplo, o aumento no consumo de espaço em disco gerado por uma escolha específica é aceitável por conta da melhora de performance que ela oferece. O problema é que não há estudo que analise as escolhas de design disponíveis, fazendo uma análise através de dados concretos. Mesmo quando é fácil identificar, dentre duas escolhas, qual tem performance melhor em um determinado critério, é difícil mensurar o quão melhor a escolha melhor se sai, e se algum efeito colateral trazido por ela é aceitável. Ter dados concretos para suportar esse tipo de decisão permite ao projetista da base de dados fazer escolhas que se enquadram melhor no contexto da sua aplicação. O objetivo desse trabalho é analisar algumas escolhas de design comuns para representar e gerenciar dados temporais em SGBDs relacionais tradicionais, provendo direcionamento sobre qual alternativa se enquadra melhor em cada situação onde dados temporais são necessários. Dados concretos sobre cada uma das alternativas estudadas são gerados e analisados e conclusões são obtidas a partir deles. / Temporal information is present on a wide range of applications. Almost every application has at least one field that contains temporal data like dates or timestamps. However, traditional databases don’t have a comprehensive support to storage and query this kind of data efficiently, and DBMS with native support for temporal data are rarely available to system developers. Most of the time, regular databases are used to store application data and when temporal data is needed, it is handled using the poor support offered by standard relational DBMS. That said, the database designer must rely on good schema design so that the natural difficulty faced when dealing with temporal data on standard relational DBMS can be minimized. While some design choices may seem obvious, others are difficult to evaluate just by looking at them, therefore needing experimentation prior to being applied or not. For example, in several cases it might be difficult to measure how much will a specific design choice affect the disk space consumption, and how much will this same design choice affect overall performance. This kind of information is needed so that the database designer will be able to determine if, for example, the increased disk space consumption generated by a given choice is acceptable because of the performance enhancement it gives. The problem is that there is no study that analyses the design choices available, analyzing them through concrete data. Even when it is easy to see which of two design choices perform better in a given criterion, it is hard to see how better the better choice does, and if any other side-effect it has is acceptable. Having concrete data to support this kind of decision allows the database designer to make the choices that suits his application’s context best. The objective of this work is to analyze several common design choices to represent and handle different kinds of temporal data on standard SQL DBMS, providing guidance on which alternative suits best each situation where temporal data is required. Concrete data about each of the studied alternatives are generated and analyzed, and conclusions are drawn from them.

XML vem se tornando um importante meio para intercâmbio de dados, e é frequentemente usada com uma interface para - isto é, uma visão de - um banco de dados relacional. Apesar de existirem muitos trabalhos que tratam de consultas a bancos de dados através de visões XML, o problema de atualização de bancos de dados relacionais através de visões XML não tem recebido muita atenção. Neste trabalho, apresentam-se os primeiros passos para a solução deste problema. Usando query trees para capturar noções de seleção, projeção, aninhamento, agrupamento e conjuntos heterogêneos, presentes na maioria das linguagens de consulta XML, demonstra-se como visões XML expressas através de query trees podem ser mapeadas para um conjunto de visões relacionais correspondentes. Consequentemente, esta tese transforma o problema de atualização de bancos de dados relacionais através de visões XML em um problema clássico de atualização de bancos de dados através de visões relacionais. A partir daí, este trabalho mostra como atualizações na visão XML são mapeadas para atualizações sobre as visões relacionais correspondentes. Trabalhos existentes em atualização de visões relacionais podem então ser aplicados para determinar se as visões são atualizáveis com relação àquelas atualizações relacionais, e em caso a rmativo, traduzir as atualizações para o banco de dados relacional. Como query trees são uma caracterização formal de consultas de de nição de visões, elas não são adequadas para usuários nais. Diante disso, esta tese investiga como um subconjunto de XQuery pode ser usado como uma linguagem de de nição das visões, e como as query trees podem ser usadas como uma representação intermedi ária para consultas de nidas nesse subconjunto. / XML has become an important medium for data exchange, and is frequently used as an interface to - i.e. a view of - a relational database. Although lots of work have been done on querying relational databases through XML views, the problem of updating relational databases through XML views has not received much attention. In this work, we give the rst steps towards solving this problem. Using query trees to capture the notions of selection, projection, nesting, grouping, and heterogeneous sets found throughout most XML query languages, we show how XML views expressed using query trees can be mapped to a set of corresponding relational views. Thus, we transform the problem of updating relational databases through XML views into a classical problem of updating relational databases through relational views. We then show how updates on the XML view are mapped to updates on the corresponding relational views. Existing work on updating relational views can then be leveraged to determine whether or not the relational views are updatable with respect to the relational updates, and if so, to translate the updates to the underlying relational database. Since query trees are a formal characterization of view de nition queries, they are not well suited for end-users. We then investigate how a subset of XQuery can be used as a top level language, and show how query trees can be used as an intermediate representation of view de nitions expressed in this subset.

There is a need of storing and keeping track of things. As the amount of information increases, so does the demand for suitable applications that can manage the data. This thesis has had its focus on developing a web administration interface for relational databases, where the focus has been on managing and visualizing the data, where relationships between data within the database could be predicted through an algorithm. During the thesis, it was revealed that administrators can utilize naming conventions for databases, a property which can be used to predict its relationships. Furthermore, existing applications for managing databases has been compared with the thesis' implementation. Notable differences are that existing solutions are focused towards the structure of the data, rather than the data itself. To accomplish all this, an agile method was chosen for fast results within the deadline, together with standardized web development tools and JavaScript frameworks. The resulting implementation consists of a front- and backend. The frontend was developed using the Ember.JS framework for making web applications and the backend was implemented using Node.JS, together with a component for handling different database dialects called Sequelize. It has been concluded that the prototype this thesis has resulted in works as a proof of concept, complete with a prediction algorithm that can suggest relationships within databases that utilizes convenient and consistent naming conventions. In the future, further research and tests could be conducted to evaluate the security, reliability and usability of the application, to ensure its production quality.

Ces dernières années ont vu un regain d’intérêt dans l’utilisation de données semi-structurées, grâce à la standardisation de formats d’échange de données sur le Web tels que XML et RDF. On notera en particulier le Linking Open Data Project qui comptait plus de 31 milliard de triplets RDF à la fin de l’année 2011. XML reste, pour sa part, l’un des formats de données privilégié de nombreuses bases de données de grandes tailles dont Uniprot, Open Government Initiative et Penn Treebank. <p><p>Cet accroissement du volume de données semi-structurées a suscité un intérêt croissant pour le développement de bases de données adaptées. Parmi les différentes approches proposées, on peut distinguer les approches relationnelles et les approches graphes, comme détaillé au Chapitre 3. Les premières visent à exploiter les moteurs de bases de données relationnelles existants, en y intégrant des techniques spécialisées. Les secondes voient les données semistructurées comme des graphes, c’est-à-dire un ensemble de noeuds liés entre eux par des arêtes étiquetées, dont elles exploitent la structure. L’une des techniques de ce domaine, connue sous le nom d’indexation structurelle, vise à résumer les graphes de données, de sorte à pouvoir identifier rapidement les données utiles au traitement d’une requête.<p><p>Les index structurels classiques sont construits sur base des notions de simulation et de bisimulation sur des graphes. Ces notions, qui sont d’usage dans de nombreux domaines tels que la vérification, la sécurité, et le stockage de données, sont des relations sur les noeuds des graphes. Fondamentalement, ces notions caractérisent le fait que deux noeuds partagent certaines caractéristiques telles qu’un même voisinage. <p><p>Bien que les approches graphes soient efficaces en pratique, elles présentent des limitations dans le cadre de RDF et son langage de requêtes SPARQL. Les étiquettes sont, dans cette optique, distinctes des noeuds du graphe .Dans le modèle décrit par RDF et supporté par SPARQL, les étiquettes et noeuds font néanmoins partie du même ensemble. C’est pourquoi, les approches graphes ne supportent qu’un sous-ensemble des requêtes SPARQL. Au contraire, les approches relationnelles sont fidèles au modèle RDF, et peuvent répondre au différentes requêtes SPARQL. <p><p>La question à laquelle nous souhaitons répondre dans cette thèse est de savoir si les approches relationnelles et graphes sont incompatible, ou s’il est possible de les combiner de manière avantageuse. En particulier, il serait souhaitable de pouvoir conserver la performance des approches graphe, et la généralité des approches relationnelles. Dans ce cadre, nous réalisons un index structurel adapté aux données relationnelles. <p><p>Nous nous basons sur une méthodologie décrite par Fletcher et ses coauteurs pour la conception d’index structurels. Cette méthodologie repose sur trois composants principaux. Un premier composant est une caractérisation dite structurelle du langage de requêtes à supporter. Il s’agit ici de pouvoir identifier les données qui sont retournées en même temps par n’importe quelle requête du langage aussi précisément que possible. Un second composant est un algorithme qui doit permettre de grouper efficacement les données qui sont retournées en même temps, d’après la caractérisation structurelle. Le troisième composant est l’index en tant que tel. Il s’agit d’une structure de données qui doit permettre d’identifier les groupes de données, générés par l’algorithme précédent pour répondre aux requêtes. <p><p>Dans un premier temps, il faut remarquer que le langage SPARQL pris dans sa totalité ne se prête pas à la réalisation d’index structurels efficaces. En effet, le fondement des requêtes SPARQL se situe dans l’expression de requêtes conjonctives. La caractérisation structurelle des requêtes conjonctives est connue, mais ne se prête pas à la construction d’algorithmes efficaces pour le groupement. Néanmoins, l’étude empirique des requêtes SPARQL posées en pratique que nous réalisons au Chapitre 5 montre que celles-ci sont principalement des requêtes conjonctives acycliques. Les requêtes conjonctives acycliques sont connues dans la littérature pour admettre des algorithmes d’évaluation efficaces. <p><p>Le premier composant de notre index structurel, introduit au Chapitre<p>6, est une caractérisation des requêtes conjonctives acycliques. Cette<p>caractérisation est faite en termes de guarded simulation. Pour les graphes la<p>notion de simulation est une version restreinte de la notion de bisimulation.<p>Similairement, nous introduisons la notion de guarded simulation comme une<p>restriction de la notion de guarded bisimulation, une extension connue de la<p>notion de bisimulation aux données relationelles. <p><p>Le Chapitre 7 offre un second composant de notre index structurel. Ce composant est une structure de données appelée guarded structural index qui supporte le traitement de requêtes conjonctives quelconques. Nous montrons que, couplé à la caractérisation structurelle précédente, cet index permet d’identifier de manière optimale les données utiles au traitement de requêtes conjonctives acycliques. <p><p>Le Chapitre 8 constitue le troisième composant de notre index structurel et propose des méthodes efficaces pour calculer la notion de guarded simulation. Notre algorithme consiste essentiellement en une transformation d’une base de données en un graphe particulier, sur lequel les notions de simulation et guarded simulation correspondent. Il devient alors possible de réutiliser les algorithmes existants pour calculer des relations de simulation. <p><p>Si les chapitres précédents définissent une base nécessaire pour un index structurel visant les données relationnelles, ils n’intègrent pas encore cet index dans le contexte d’un moteur de bases de données relationnelles. C’est ce que propose le Chapitre 9, en développant des méthodes qui permettent de prendre en compte l’index durant le traitement d’une requête SPARQL. Des résultats expérimentaux probants complètent cette étude. <p><p>Ce travail apporte donc une première réponse positive à la question de savoir s’il est possible de combiner de manière avantageuse les approches relationnelles et graphes de stockage de données RDF.<p> / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished