Strong Connectivity in Directed Hypergraphs and its Application to the Atomic Decomposition of Ontologies

Los hipergrafos dirigidos se han empleado en problemas relacionados con lógica proposicional, bases de datos relacionales, linguística computacional y aprendizaje automático. Los hipergrafos dirigidos han sido también utilizados como alternativa a los grafos (bipartitos) dirigidos para facilitar el estudio de las interacciones entre componentes de sistemas complejos que no pueden ser fácilmente modelados usando exclusivamente relaciones binarias. En este contexto, este tipo de representación es conocida como hiper-redes. Un hipergrafo dirigido es una generalización de un grafo dirigido especialmente adecuado para la representación de relaciones de muchos a muchos. Mientras que una arista en un grafo dirigido define una relación entre dos de sus nodos, una hiperarista en un hipergrafo dirigido define una relación entre dos conjuntos de sus nodos. La conexión fuerte es una relación de equivalencia que divide el conjunto de nodos de un hipergrafo dirigido en particiones y cada partición define una clase de equivalencia conocida como componente fuertemente conexo. El estudio de los componentes fuertemente conexos de un hipergrafo dirigido puede ayudar a conseguir una mejor comprensión de la estructura de este tipo de hipergrafos cuando su tamaño es considerable. En el caso de grafo dirigidos, existen algoritmos muy eficientes para el cálculo de los componentes fuertemente conexos en grafos de gran tamaño. Gracias a estos algoritmos, se ha podido averiguar que la estructura de la WWW tiene forma de “pajarita”, donde más del 70% del los nodos están distribuidos en tres grandes conjuntos y uno de ellos es un componente fuertemente conexo. Este tipo de estructura ha sido también observada en redes complejas en otras áreas como la biología. Estudios de naturaleza similar no han podido ser realizados en hipergrafos dirigidos porque no existe algoritmos capaces de calcular los componentes fuertemente conexos de este tipo de hipergrafos. En esta tesis doctoral, hemos investigado como calcular los componentes fuertemente conexos de un hipergrafo dirigido. En concreto, hemos desarrollado dos algoritmos para este problema y hemos determinado que son correctos y cuál es su complejidad computacional. Ambos algoritmos han sido evaluados empíricamente para comparar sus tiempos de ejecución. Para la evaluación, hemos producido una selección de hipergrafos dirigidos generados de forma aleatoria inspirados en modelos muy conocidos de grafos aleatorios como Erdos-Renyi, Newman-Watts-Strogatz and Barabasi-Albert. Varias optimizaciones para ambos algoritmos han sido implementadas y analizadas en la tesis. En concreto, colapsar los componentes fuertemente conexos del grafo dirigido que se puede construir eliminando ciertas hiperaristas complejas del hipergrafo dirigido original, mejora notablemente los tiempos de ejecucion de los algoritmos para varios de los hipergrafos utilizados en la evaluación. Aparte de los ejemplos de aplicación mencionados anteriormente, los hipergrafos dirigidos han sido también empleados en el área de representación de conocimiento. En concreto, este tipo de hipergrafos se han usado para el cálculo de módulos de ontologías. Una ontología puede ser definida como un conjunto de axiomas que especifican formalmente un conjunto de símbolos y sus relaciones, mientras que un modulo puede ser entendido como un subconjunto de axiomas de la ontología que recoge todo el conocimiento que almacena la ontología sobre un conjunto especifico de símbolos y sus relaciones. En la tesis nos hemos centrado solamente en módulos que han sido calculados usando la técnica de localidad sintáctica. Debido a que las ontologías pueden ser muy grandes, el cálculo de módulos puede facilitar las tareas de re-utilización y mantenimiento de dichas ontologías. Sin embargo, analizar todos los posibles módulos de una ontología es, en general, muy costoso porque el numero de módulos crece de forma exponencial con respecto al número de símbolos y de axiomas de la ontología. Afortunadamente, los axiomas de una ontología pueden ser divididos en particiones conocidas como átomos. Cada átomo representa un conjunto máximo de axiomas que siempre aparecen juntos en un modulo. La decomposición atómica de una ontología es definida como un grafo dirigido de tal forma que cada nodo del grafo corresponde con un átomo y cada arista define una dependencia entre una pareja de átomos. En esta tesis introducimos el concepto de“axiom dependency hypergraph” que generaliza el concepto de descomposición atómica de una ontología. Un modulo en una ontología correspondería con un componente conexo en este tipo de hipergrafos y un átomo de una ontología con un componente fuertemente conexo. Hemos adaptado la implementación de nuestros algoritmos para que funcionen también con axiom dependency hypergraphs y poder de esa forma calcular los átomos de una ontología. Para demostrar la viabilidad de esta idea, hemos incorporado nuestros algoritmos en una aplicación que hemos desarrollado para la extracción de módulos y la descomposición atómica de ontologías. A la aplicación la hemos llamado HyS y hemos estudiado sus tiempos de ejecución usando una selección de ontologías muy conocidas del área biomédica, la mayoría disponibles en el portal de Internet NCBO. Los resultados de la evaluación muestran que los tiempos de ejecución de HyS son mucho mejores que las aplicaciones más rápidas conocidas. ABSTRACT Directed hypergraphs are an intuitive modelling formalism that have been used in problems related to propositional logic, relational databases, computational linguistic and machine learning. Directed hypergraphs are also presented as an alternative to directed (bipartite) graphs to facilitate the study of the interactions between components of complex systems that cannot naturally be modelled as binary relations. In this context, they are known as hyper-networks. A directed hypergraph is a generalization of a directed graph suitable for representing many-to-many relationships. While an edge in a directed graph defines a relation between two nodes of the graph, a hyperedge in a directed hypergraph defines a relation between two sets of nodes. Strong-connectivity is an equivalence relation that induces a partition of the set of nodes of a directed hypergraph into strongly-connected components. These components can be collapsed into single nodes. As result, the size of the original hypergraph can significantly be reduced if the strongly-connected components have many nodes. This approach might contribute to better understand how the nodes of a hypergraph are connected, in particular when the hypergraphs are large. In the case of directed graphs, there are efficient algorithms that can be used to compute the strongly-connected components of large graphs. For instance, it has been shown that the macroscopic structure of the World Wide Web can be represented as a “bow-tie” diagram where more than 70% of the nodes are distributed into three large sets and one of these sets is a large strongly-connected component. This particular structure has been also observed in complex networks in other fields such as, e.g., biology. Similar studies cannot be conducted in a directed hypergraph because there does not exist any algorithm for computing the strongly-connected components of the hypergraph. In this thesis, we investigate ways to compute the strongly-connected components of directed hypergraphs. We present two new algorithms and we show their correctness and computational complexity. One of these algorithms is inspired by Tarjan’s algorithm for directed graphs. The second algorithm follows a simple approach to compute the stronglyconnected components. This approach is based on the fact that two nodes of a graph that are strongly-connected can also reach the same nodes. In other words, the connected component of each node is the same. Both algorithms are empirically evaluated to compare their performances. To this end, we have produced a selection of random directed hypergraphs inspired by existent and well-known random graphs models like Erd˝os-Renyi and Newman-Watts-Strogatz. Besides the application examples that we mentioned earlier, directed hypergraphs have also been employed in the field of knowledge representation. In particular, they have been used to compute the modules of an ontology. An ontology is defined as a collection of axioms that provides a formal specification of a set of terms and their relationships; and a module is a subset of an ontology that completely captures the meaning of certain terms as defined in the ontology. In particular, we focus on the modules computed using the notion of syntactic locality. As ontologies can be very large, the computation of modules facilitates the reuse and maintenance of these ontologies. Analysing all modules of an ontology, however, is in general not feasible as the number of modules grows exponentially in the number of terms and axioms of the ontology. Nevertheless, the modules can succinctly be represented using the Atomic Decomposition of an ontology. Using this representation, an ontology can be partitioned into atoms, which are maximal sets of axioms that co-occur in every module. The Atomic Decomposition is then defined as a directed graph such that each node correspond to an atom and each edge represents a dependency relation between two atoms. In this thesis, we introduce the notion of an axiom dependency hypergraph which is a generalization of the atomic decomposition of an ontology. A module in the ontology corresponds to a connected component in the hypergraph, and the atoms of the ontology to the strongly-connected components. We apply our algorithms for directed hypergraphs to axiom dependency hypergraphs and in this manner, we compute the atoms of an ontology. To demonstrate the viability of this approach, we have implemented the algorithms in the application HyS which computes the modules of ontologies and calculate their atomic decomposition. In the thesis, we provide an experimental evaluation of HyS with a selection of large and prominent biomedical ontologies, most of which are available in the NCBO Bioportal. HyS outperforms state-of-the-art implementations in the tasks of extracting modules and computing the atomic decomposition of these ontologies.

Autogestor de contenidos dinámico (ACD)

Este proyecto se centra en la construcción de una herramienta para la gestión de contenidos de muy diversos tipos, siendo fácilmente adaptable a cada uno de los contextos. Permite guardar los contenidos necesarios gracias a un formulario previamente personalizado, de este modo hay un editor que se dedica solamente a la introducción de los contenidos y un administrador que personaliza los campos del formulario según los contenidos. En esencia la herramienta sirve de apoyo a dos tipos de usuario, desarrolladores (administrador) y redactores (editor), a los primeros les simplifica las tareas de conceptualización de las estructuras de datos de las que se desea tener persistencia y sirve como base para construir los editores que usan los redactores, por otro lado proporciona un API sencillo, potente y ágil para recuperar los datos introducidos por los redactores. La herramienta a su vez está pensada para ser interoperable, es decir, no obliga a usar un tipo de almacenamiento persistente concreto. Puede utilizar desde los sencillos archivos de texto, con lo que puede desplegarse en servidores treméndamente básicos. Por otro lado, si se necesita potencia en las búsquedas, nada debe impedir el uso de bases de datos relacionales como MySql. O incluso si se quiere dar un paso más y se quiere aprovechar la flexibilidad, potencia y maleabilidad de las bases de datos NoSql (como MongoDB) no es costoso, lo que hay que hacer es implementar una nueva clase de tipo PersistentManager y desarrollar los tipos de búsqueda y recuperación de contenidos que se necesiten. En la versión inicial de la herramienta se han implementado estos tres tipos de almacenes, nada impide usar sólo alguno de ellos y desechar el resto o implementar uno nuevo. Desde el punto de vista de los redactores, les ofrece un entorno sencillo y potente para poder realizar las tareas típicas denominadas CRUD (Create Read Update Delete, Crear Leer Actualizar y Borrar), un redactor podrá crear, buscar, re-aprovechar e incluso planificar publicación de contenidos en el tiempo. ABSTRACT This project focuses on building a tool for content management of many types, being easily adaptable to each context. Saves the necessary content through a previously designed form, thus there will be an editor working only on the introduction of the contents and there will be an administrator to customize the form fields as contents. Essentially the tool provides support for two types of users, developers (administrator) and editors, the first will have simplified the tasks of conceptualization of data structures which are desired to be persistent and serve as the basis for building the structures that will be used by editors, on the other hand provides a simple, powerful and agile API to retrieve the data entered by the editors. The tool must also be designed to be interoperable, which means not to be bound by the use of a particular type of persistent storage. You can use simple text files, which can be deployed in extremely basic servers. On the other hand, if power is needed in searches, nothing should prevent the use of relational databases such as MySQL. Or even if you want to go a step further and want to take advantage of the flexibility, power and malleability of NoSQL databases (such as MongoDB) it will not be difficult, you will only need to implement a new class of PersistentManager type and develop the type of search and query of content as needed. In the initial version of the tool these three types of storage have been implemented, it will be entitled to use only one of them and discard the rest or implement a new one. From the point of view of the editors, it offers a simple and powerful environment to perform the typical tasks called CRUD (Create Read Update Delete), an editor can create, search, re-use and even plan publishing content in time.

Unify 2000

En la primera parte se presenta un esquema introductorio al tema para explicar qué es una base de datos y al definir un esbozo general de la arquitectura de un sistema de bases de da· tos. En la presentación de qué es un sistema de base de datos veremos cada uno de los cuatro componentes principales de la base de datos: datos, hardware, software y usuarios; así como su función dentro de la base de datos. Además, presentaremos aspectos importantes de por qué utilizar un sistema de base de datos. La presentación de la arquitectura sirve de marco de referencia para la exposición de nuestro tema.

Ingeniería reversa

En muchas organizaciones hay un gran número de Bases de Datos que se han desarrollado en muchos años. Una gran dificultad con estas Bases de Datos es que frecuentemente el significado de los datos se ha perdido, además de que no se conoce exactamente cuá- fes son los datos y las relaciones entre ellos. Esta falta de entendimiento dificulta la utilización efectiva de los datos, dentro de una organización, y también reduce la probabilidad de que las actividades de mantenimiento puedan ser realizadas correctamente

Un diseño óptimo en tercera forma normal

Existen métodos clásicos de diseño de bases de datos relacionales -descomposición y síntesis- El objetivo de esas aproximaciones clásicas es alcanzar el más alto nivel de normalización. El método de diseño por descomposición es “top-down” que comienza con una relación existente, investiga su forma normal y la descompone vía proyecciones hasta que el esquema relacional adquiera el grado de normalización deseado.

Bioqueries: a collaborative environment to create, explore and share SPARQL queries in Life Sciences

Bioqueries provides a collaborative environment to create, explore, execute, clone and share SPARQL queries (including Federated Queries). Federated SPARQL queries can retrieve information from more than one data source.

Bioqueries: a collaborative environment to create, explore and share SPARQL queries in Life Sciences

Bioqueries provides a collaborative environment to create, explore, execute, clone and share SPARQL queries (including Federated Queries). Federated SPARQL queries can retrieve information from more than one data source.

Espacios relacionales de organizaciones cross‐culturales en el contexto de la globalización contemporánea

En este estudio se describen los espacios geográficos y el fenómeno técnico como una construcción relacional, discursiva e histórica de organizaciones cross-culturales, identificando la lógica, las formas, contenidos y comportamientos que afectan las prácticas, filosofías y estrategias de organizaciones transfronterizas. Las técnicas y métodos empleados surgen de la evolución de la investigación cualitativa de los años 90 y principios del nuevo milenio basados en formas de interpretación como el análisis del discurso, imágenes, videos, documentos institucionales, bases de datos organizacionales entre otros. Los hallazgos encontrados muestran que los espacios o cortes relacionales de organizaciones cross-culturales son construidos por el espectro de culturas en un sentido solidario de convergencia de acciones y eventos para lograr una coherencia e intencionalidad global. En este escenario el fenómeno técnico esta presente como un protocolo de comunicación que transmite la intencionalidad creando espacios geográficos artificiales y descartables que afectan y cambian el tiempo y el espacio de organizaciones transfronterizadas.

Redes neuronales artificiales aplicadas al análisis de datos en ingeniería ambiental e impacto ambiental

Resumen: Se realiza una revisión sobre los antecedentes de las Redes Neuronales Artificiales (RNA) como método de análisis de bases de datos medioambientales, aplicado en las diversas áreas de la Ingeniería Ambiental en general y de Impacto Ambiental en particular. Se describe como ejemplo, la aplicación de RNA en los algoritmos de inversión de datos obtenidos por sensado remoto satelital, para la medición de variables geofísicas

Aplicación de persistencia políglota usando tecnología NoSQL

En los últimos años se han popularizado los sistemas de bases de datos NoSQL y con ellos, recientemente, ha surgido la idea de Aplicación de Persistencia Políglota. Ésta sostiene que debido a la gran variedad y cantidad de datos, y los diversos servicios que pueden dar las aplicaciones hoy en día; es posible que un único tipo de sistema de almacenamiento no sea capaz de cubrir de forma eficiente todas las necesidades de la aplicación que use dicho sistema. Sin embargo, sostiene que las aplicaciones se pueden beneficiar del uso de varios sistemas de distinto tipo donde los datos se repartirían entre los sistemas que mejor fueran capaces de dar acceso a estos en función del tipo de datos, y de las tareas que se realizarán con ellos. Además, con esta idea también se considera que se tiene que ir más allá de los sistemas de almacenamiento relacionales y utilizar, además, sistemas de almacenamiento NoSQL.

Desarrollo de un sistema de simulación de datos de metilación

Hasta hace poco, enfermedades como el cáncer o el Alzheimer eran interpretadas solo como mutaciones genéticas, es decir, cambios en la secuencia genética. Sin embargo, son muchos los que últimamente se interesan por la epigenética y por la relación con las enfermedades. La epigenética va más allá que la genética, se basa en los cambios reversibles del ADN y de las proteínas que se unen en él. Esto hace que, sin necesidad de alterar su secuencia, un gen pueda ser expresado o por el contrario quede silenciado. Uno de estos cambios epigenéticos es la metilación del ADN que consiste en una modificación química en el dinucleotido CpG (citosina-fosfato-guanina, es decir, donde una citosina es seguida de una guanina). Existen métodos experimentales para poder detectar la metilación, como por ejemplo, los métodos basados en la modificación del ADN con bisulfito y posterior análisis con arrays de ADN. El objetivo de este proyecto es imitar, mediante la simulación computacional y el estudio de distintas bases de datos, el comportamiento del sistema biológico, a fin de generar datos similares a los reales. Esta simulación de los datos reales permitirá, entre otras cosas, generar escenarios controlados en los que evaluar los métodos de análisis. Adicionalmente, el proceso de diseño permitirá explorar el proceso biológico que da lugar a los datos.

Diseño e implementación de una herramienta para la integración de datos de QoS en Internet publicados por el regulador español

[ES]Este proyecto tiene como objetivo el diseño e implementación de una herramienta para la integración de los datos de calidad de servicio (QoS) en Internet publicados por el regulador español. Se trata de una herramienta que pretende, por una parte, unificar los diferentes formatos en que se publican los datos de QoS y, por otra, facilitar la conservación de los datos favoreciendo la obtención de históricos, datos estadísticos e informes. En la página del regulador sólo se puede acceder a los datos de los 5 últimos trimestres y los datos anteriormente publicados no permanecen accesibles si no que son sustituidos por los más recientes por lo que, desde el punto de vista del usuario final, estos datos se pierden. La herramienta propuesta en este trabajo soluciona este problema además de unificar formatos y facilitar el acceso a los datos de interés. Para el diseño del sistema se han usado las últimas tecnologías en desarrollo de aplicaciones web con lo que la potencia y posibilidad de futuras ampliaciones son elevadas.

Diseño, creación y explotación de una base de datos en el ámbito de la gestión empresarial

Duración (en horas): Más de 50 horas Destinatario: Estudiante y Docente

Banco de Datos Hesperia de Lenguas Paleohispánicas (BDHESP) II. Numimática paleohispánica

El Banco de Datos de Lenguas Paleohispánicas Hesperia tiene como finalidad la catalogación y la difusión de los textos escritos en las antiguas lenguas locales de la Península Ibérica, con exclusión del fenicio, el griego y el latín. El presente volumen es la versión impresa –a fecha de 2015– de una de las bases de datos que integra dicho banco: la correspondiente a la epigrafía monetal. Recoge las leyendas monetales redactadas en una lengua paleohispánica (fundamentalmente ibérico y celtibérico) tanto de la Península Ibérica cuanto del sureste de las Galias, incluidas las redactadas en latín y griego en las emisiones bilingües. Dada la controvertida lectura y adscripción lingüística de los rótulos “libiofenicios”, estos no son tomados en consideración. Las fichas están ordenadas alfabéticamente y agrupan todos los rótulos monetales correspondientes a una misma ceca, designada convencionalmente mediante una o varias de las leyendas toponímicas más frecuente, independientemente de su morfología (p. ej.: untikesken, salduie, kalakorikos o turiazu). Cada ficha presenta cuatro apartados: “Generalidades”, “Leyendas”, “Lengua y escritura” y “Bibliografía”.

Levantamiento de una base de datos para el diagnóstico de fallas en motores de combustión interna ciclo Otto con sistema MPFI mediante el análisis del sensor MAP

En el presente documento se presenta el desarrollo de la creación de una base de datos para el diagnóstico de fallas en los motores de combustión interna MPFI mediante el análisis del sensor MAP (Manifold Absolute Pressure), a través del cual se puede determinar y diagnosticar fallas en sensores, actuadores y sistemas auxiliares.