Magíster en Ciencias, Mención Computación / En las últimas décadas presenciamos un aumento exponencial en la generación y en el almacenamiento de datos en el mundo. En paralelo, han surgido movimientos promoviendo el acceso abierto a los datos. En Chile, por ejemplo, se dictó la Ley Nº20285 sobre el acceso a la información pública, que obliga a las instituciones públicas a publicar cierto conjunto de información y define la forma en que el resto puede ser requerida. En esta dirección han surgido iniciativas que promueven además la publicación de datos en forma de datos enlazados. Este cambio de paradigma en el manejo de la información y datos requiere de nuevas políticas y estándares. La presente tesis aborda los problemas observados en la publicación de datos, los conceptualiza y propone buenas prácticas para su publicación. Las prácticas propuestas se organizan en tres niveles, que van desde lo general a lo particular. En el primer nivel se presentan prácticas generales, que son independientes de las tecnologías usadas y que tienen por objetivo satisfacer los principios de los datos abiertos. En el segundo, se proponen prácticas para la publicación usando el lenguaje RDF. RDF es un estándar del Consorcio de la Web, y su modelo de grafos facilita la integración de datos, uno de los desafíos principales de la publicación de datos. Es de particular interés en este segundo nivel la discusión sobre cómo modelar usando el lenguaje RDF. En esta tesis se propone un conjunto de prácticas y se plantea la necesidad de desarrollar metodologías. Finalmente, en el tercer nivel, se presenta un modelo (o vocabulario RDF) que ejemplifica las prácticas propuestas sobre un caso de estudio particular, centrado en la publicación de datos de transparencia gubernamental y en datos de historia política chilena. La tesis concluye con una discusión sobre aquellos aspectos de RDF que lo hacen complejo y que se vislumbran como una barrera para su amplia adopción. Es decir, se plantea la necesidad de revisar la pregunta sobre si las bases de RDF necesitan ser cambiadas.

Magíster en Ciencias, Mención Computación. Ingeniero Civil en Computación / SPARQL es el lenguaje de consulta estándar para RDF, definido por el World Wide Web Consortium. Presentemente, hay una gran cantidad de servicios de consulta de SPARQL en la Web. También hay una gran demanda por estos servicios diariamente. Debido a la gran cantidad de consultas que deben procesar estos servicios, los procesadores sufren una sobrecarga que podría ser reducida si fuésemos capaces de detectar consultas equivalentes. Nuestra propuesta consiste en el diseño y la implementación de un algoritmo de canonicalización eficiente, el cual nos permitirá computar una forma canónica para las consultas. Las consultas que sean equivalentes deben tener la misma forma canónica, lo cual haría posible detectar un mayor número de consultas duplicadas. Hemos cubierto una parte significante de SPARQL 1.0 con nuestro trabajo; principalmente consultas que tengan la forma de uniones de consultas conjuntivas. El algoritmo que hemos desarrollado realiza una canonicalización completa de las consultas que contienen estas operaciones. Para las otras operaciones, realizamos una canonicalización parcial, pues estas otras operaciones son usadas popularmente en consultas reales. Hemos diseñado experimentos para probar la correctitud y el desempeño de nuestro algoritmo en comparación contra otros métodos sintácticos. Realizamos nuestros experimentos sobre consultas reales extraídas de bitácoras de bases de datos de RDF, y también sobre consultas sintéticas que diseñamos para forzar un mal comportamiento del algoritmo. Los resultados de nuestros experimentos son excitosos, pues la mayoría de las consultas reales son procesables en un tiempo corto, menor a un segundo. El número de consultas duplicadas encontradas es considerablemente superior que las encontradas por el algoritmo base definido. Finalmente, el algoritmo deja de funcionar únicamente para las consultas sintéticas diseñadas por nosotros, y de una gran complejidad, las cuales no ocurren en la práctica. El siguiente documento presenta el trabajo hecho.

No description available.

Ingeniero Civil en Computación / A partir de información representada en una colección de declaraciones en RDF (Resource Description Framework), esta representa intrínsecamente un multi-grafo etiquetado, dirigido. Con esto es posible utilizar algoritmos de búsqueda de caminos, que permiten encontrar la ruta más corta entre dos nodos. Con el fin de estudiar tecnologías basadas en el desarrollo de la web semántica, el tema de memoria propuesto consiste en la búsqueda de caminos relevantes para grafos en RDF. Para esto se construye una herramienta la que, a partir de un archivo con información en RDF, sea capaz de resolver consultas sobre caminos entre un nodo de origen y un nodo objetivo de tal manera que estos contengan información relevante para el usuario. La relevancia de los caminos se representa a través del peso asignado tanto a aristas, según su etiqueta, como a vértices, principalmente por métodos basados en su grado, PageRank o variaciones de estos. Para la búsqueda del camino mínimo entre un nodo origen y un nodo objetivo se implementa una versión del algoritmo de Dijkstra para grafos ponderados. Con el objetivo de tener la posibilidad de visualizar los resultados obtenidos y usar la herramienta en un contexto real para reportar resultados, es que se construye una aplicación que resuelva consultas de caminos entre dos nodos y represente esta respuesta gráficamente. Finalmente se realizan pruebas de rendimiento del algoritmo utilizado y pruebas para comparar los caminos resultantes de los distintos métodos de ponderación del grafo. Además se lleva a cabo una evaluación con usuarios para la validación de la solución obtenida.

No description available.

L'utilité et la pertinence des données se trouvent dans l'information qui peut en être extraite.Le taux élevé de publication des données et leur complexité accrue, par exemple dans le cas des données du Web sémantique autodescriptives et hétérogènes, motivent l'intérêt de techniques efficaces pour la manipulation de données.Dans cette thèse, nous utilisons la technologie mature de gestion de données relationnelles pour l'interrogation des données du Web sémantique.La première partie se concentre sur l'apport de réponse aux requêtes sur les données soumises à des contraintes RDFS, stockées dans un système de gestion de données relationnelles. L'information implicite, résultant du raisonnement RDF est nécessaire pour répondre correctement à ces requêtes.Nous introduisons le fragment des bases de données RDF, allant au-delà de l'expressivité des fragments étudiés précédemment.Nous élaborons de nouvelles techniques pour répondre aux requêtes dans ce fragment, en étendant deux approches connues de manipulation de données sémantiques RDF, notamment par saturation de graphes et reformulation de requêtes.En particulier, nous considérons les mises à jour de graphe au sein de chaque approche et proposerons un procédé incrémental de maintenance de saturation. Nous étudions expérimentalement les performances de nos techniques, pouvant être déployées au-dessus de tout moteur de gestion de données relationnelles.La deuxième partie de cette thèse considère les nouvelles exigences pour les outils et méthodes d'analyse de données, issues de l'évolution du Web sémantique.Nous revisitons intégralement les concepts et les outils pour l'analyse de données, dans le contexte de RDF.Nous proposons le premier cadre formel pour l'analyse d'entrepôts RDF. Notamment, nous définissons des schémas analytiques adaptés aux graphes RDF hétérogènes à sémantique riche, des requêtes analytiques qui (au-delà de cubes relationnels) permettent l'interrogation flexible des données et schémas, ainsi que des opérations d'agrégation puissantes de type OLAP. Des expériences sur une plateforme entièrement implémentée démontrent l'intérêt pratique de notre approche. / The utility and relevance of data lie in the information that can be extracted from it.The high rate of data publication and its increased complexity, for instance the heterogeneous, self-describing Semantic Web data, motivate the interest in efficient techniques for data manipulation.In this thesis we leverage mature relational data management technology for querying Semantic Web data.The first part focuses on query answering over data subject to RDFS constraints, stored in relational data management systems. The implicit information resulting from RDF reasoning is required to correctly answer such queries. We introduce the database fragment of RDF, going beyond the expressive power of previously studied fragments. We devise novel techniques for answering Basic Graph Pattern queries within this fragment, exploring the two established approaches for handling RDF semantics, namely graph saturation and query reformulation. In particular, we consider graph updates within each approach and propose a method for incrementally maintaining the saturation. We experimentally study the performance trade-offs of our techniques, which can be deployed on top of any relational data management engine.The second part of this thesis considers the new requirements for data analytics tools and methods emerging from the development of the Semantic Web. We fully redesign, from the bottom up, core data analytics concepts and tools in the context of RDF data. We propose the first complete formal framework for warehouse-style RDF analytics. Notably, we define analytical schemas tailored to heterogeneous, semantic-rich RDF graphs, analytical queries which (beyond relational cubes) allow flexible querying of the data and the schema as well as powerful aggregation and OLAP-style operations. Experiments on a fully-implemented platform demonstrate the practical interest of our approach.

[pt] O termo dados interligados refere-se a conjuntos de triplas RDF organizados segundo certos princípios que facilitam a publicação e o acesso a dados por meio da infraestrutura da Web. Os princípios para organização de dados interligados são de grande importância pois oferecem uma forma de minimizar o problema de interoperabilidade entre bancos de dados expostos na Web. Este trabalho propõe enriquecer um banco de dados que contém descrições em RDF de cubos de dados, interligando seus componentes com entidades definidas em fontes de dados externas através de triplas owl:sameAs. O trabalho propõe uma arquitetura composta por dois componentes principais, o enriquecedor automático e o enriquecedor manual. O primeiro componente gera triplas owl:sameAs automaticamente enquanto que o segundo componente permite ao usuário definir manualmente as ligações. Em conjunto, estes componentes facilitam a definição de cubos de dados de acordo com os princípios de dados interligados / [en] The term Linked Data refers to a set of RDF triples organized according to certain principles that facilitate the publishing and consumption of data using the Web infrastructure. The importance of the Linked Data principles stems from the fact that they offer a way to minimize the interoperability problem between databases exposed on the Web. This dissertation proposes to enrich a database that contains Linked Data cube descriptions by interconnecting the components of the data cubes with entities defined in external data sources, using owl:sameAs triples. The dissertation proposes an architecture consisting of two major components, the automatic enriching component and the manual enriching component. The first component automatically generates owl:sameAs triples, while the second component helps the user manually define owl:sameAs triples that the automatic component was not able to uncover. Together, these components therefore facilitate the definition of data cubes according to the Linked Data principles.

La recherche de points communs entre des descriptions de données ou de connaissances est un problème de raisonnement fondamental en Machine Learning, qui a été formalisé par G. Plotkin dans les années 70s sous la forme du calcul du plus petit généralisant de ces descriptions. L'identification des plus petits généralisants a un large panel d'applications qui vont de l'optimisation de requêtes (e.g., pour matérialiser les points communs entre des requêtes lors de la sélection de vues ou pour factoriser leur exécution dans un contexte d'accès concurrentiel), à la recommandation dans le contexte des réseaux sociaux (e.g. pour créer de liens entre des utilisateurs basées sur leurs points communs selon leur profil ou leurs recherches). Dans cette thèse nous avons revisité la notion du plus petit généralisant dans le contexte de Resource Description Framework (RDF) et le fragment conjonctif de son langage de requêtes associé SPARQL, alias Basic Graph Pattern (BGP) queries. Contrairement à l'état de l'art, nous ne considérons aucune restriction, ni structurelle ni sémantique, sur les graphes et les requêtes. Nos contributions incluent la définition et le calcul des plus petits généralisants dans ces deux formalismes ce qui revient à trouver le plus grand ensemble de points communs entre des bases de données incomplètes et des requêtes conjonctives en présence de contraintes déductives. Nous proposons également une évaluation expérimentale de nos contributions. / Finding commonalities between descriptions of data or knowledge is a fundamental task in Machine Learning. The formal notion characterizing precisely such commonalities is known as least general generalization of descriptions and was introduced by G. Plotkin in the early 70's, in First Order Logic. Identifying least general generalizations has a large scope of database applications ranging from query optimization (e.g., to share commonalities between queries in view selection or multi-query optimization), to recommendation in social networks (e.g., to establish connections between users based on their commonalities between proles or searches), through exploration (e.g., to classify/categorize datasets and to identify common social graph patterns between organizations (e.g., criminal ones)). In this thesis we revisit the notion of least general generalizations in the entire Resource Description Framework (RDF) and popular conjunctive fragment of SPARQL, a.k.a. Basic Graph Pattern (BGP) queries. By contrast to the literature, we do not restrict the structure nor semantics of RDF graphs and BGPQs. Our contributions include the denition and the computation of least general generalizations in these two settings, which amounts to nding the largest set of commonalities between incomplete databases and conjunctive queries, under deductive constraints. We also provide an experimental assessment of our technical contributions.

Esta dissertação analisa a utilização do modelo de dados padronizado pela norma IEC 61970 (CIM), tida como uma ferramenta para troca de informações cadastrais e operacionais entre empresas de energia elétrica, com sistemas computacionais de diferentes fabricantes. O propósito deste padrão é criar um mecanismo para troca de informações baseado em XML, denominado de CIM/XML – um formato, especificamente, utilizado pelos Centros de Controle de Energia Elétrica para troca de dados. Os modelos de dados do padrão IEC 61970 são apresentados, bem como a avaliação do CIM/XML como uma ferramenta de interoperabilidade de dados entre empresas de energia que apresentam bases de dados de diferentes modelagem e implementação. Um dos méritos deste modelo, além de fazer uso de uma tecnologia aberta (XML) disponível em qualquer tipo de computador, e que possibilita armazenar e transferir não só dados cadastrais de equipamentos, mas também dados de topologia da rede, curvas de carga, programação de geração, saídas programadas de equipamentos, bem como medições de sistemas SCADA, indicações de estado e alarmes. Possibilita ainda armazenamento de resultados de simulação, tais como resultados do programa de fluxo de potência. Adicionalmente, é apresentado em detalhes informações sobre: a implementação do modelo lógico orientado a objetos do CIM, numa base de dados relacional; os registros de equipamentos e a topologia de um trecho de linha de sub-transmissão aéreo e subterrâneo; as informações (exportadas e importadas no formato CIM/XML) inseridas na base de dados, e a geração do documento CIM/XML. / This dissertation provides an analysis about the application of a data model based on IEC 61970 (CIM) standard – a tool for exchanging operational and equipments information among different Electrical Power Utilities' computing systems. The purpose of this standard is to create a mechanism for information exchange using XML, called CIM/XML – a format specifically used by Electrical Power Utilities' Control Centers for data exchange. The IEC 61970 standard-based data models is presented as well the evaluation of CIM/XML as a tool for data interoperability among Electrical Power Utilities' databases, that uses different modeling and implementation approaches. The benefit of this model – besides of using a open standard technology (XML) that can be found on any type of computer – is the capability of store and transfer information not only from equipments, but also from network topology, load flow curves, generation scheduling, equipments outages, SCADA system measurements, status indication and alarms. It also enables the storage of simulation results, such as the power flow bus voltage and lines loads. Additionally, is also provided highly detailed information about: the CIM object-oriented model implementation mapped to a relational database; the records of equipments and topology of an aerial and underground subtransmission line section; the information (exported and imported using CIM/XML format) included in the database, and the CIM/XML document generation.

Esta dissertação analisa a utilização do modelo de dados padronizado pela norma IEC 61970 (CIM), tida como uma ferramenta para troca de informações cadastrais e operacionais entre empresas de energia elétrica, com sistemas computacionais de diferentes fabricantes. O propósito deste padrão é criar um mecanismo para troca de informações baseado em XML, denominado de CIM/XML – um formato, especificamente, utilizado pelos Centros de Controle de Energia Elétrica para troca de dados. Os modelos de dados do padrão IEC 61970 são apresentados, bem como a avaliação do CIM/XML como uma ferramenta de interoperabilidade de dados entre empresas de energia que apresentam bases de dados de diferentes modelagem e implementação. Um dos méritos deste modelo, além de fazer uso de uma tecnologia aberta (XML) disponível em qualquer tipo de computador, e que possibilita armazenar e transferir não só dados cadastrais de equipamentos, mas também dados de topologia da rede, curvas de carga, programação de geração, saídas programadas de equipamentos, bem como medições de sistemas SCADA, indicações de estado e alarmes. Possibilita ainda armazenamento de resultados de simulação, tais como resultados do programa de fluxo de potência. Adicionalmente, é apresentado em detalhes informações sobre: a implementação do modelo lógico orientado a objetos do CIM, numa base de dados relacional; os registros de equipamentos e a topologia de um trecho de linha de sub-transmissão aéreo e subterrâneo; as informações (exportadas e importadas no formato CIM/XML) inseridas na base de dados, e a geração do documento CIM/XML. / This dissertation provides an analysis about the application of a data model based on IEC 61970 (CIM) standard – a tool for exchanging operational and equipments information among different Electrical Power Utilities' computing systems. The purpose of this standard is to create a mechanism for information exchange using XML, called CIM/XML – a format specifically used by Electrical Power Utilities' Control Centers for data exchange. The IEC 61970 standard-based data models is presented as well the evaluation of CIM/XML as a tool for data interoperability among Electrical Power Utilities' databases, that uses different modeling and implementation approaches. The benefit of this model – besides of using a open standard technology (XML) that can be found on any type of computer – is the capability of store and transfer information not only from equipments, but also from network topology, load flow curves, generation scheduling, equipments outages, SCADA system measurements, status indication and alarms. It also enables the storage of simulation results, such as the power flow bus voltage and lines loads. Additionally, is also provided highly detailed information about: the CIM object-oriented model implementation mapped to a relational database; the records of equipments and topology of an aerial and underground subtransmission line section; the information (exported and imported using CIM/XML format) included in the database, and the CIM/XML document generation.