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.

Ingeniero Civil Industrial / Uno de los elementos primordiales en la investigación financiera, sin importar el propósito que se tenga, es la necesidad de contar con datos confiables y reales que permitan llevarlas a cabo. Sin embargo, hoy en día es difícil acceder a los datos que forman parte del mercado financiero, más aún, el tiempo que se utiliza en su recolección no es despreciable, haciendo finalmente que se pierda la motivación por el tema. Es por ello que nace la necesidad de crear sistemas automatizados que capturen datos financieros relevantes. Esta memoria se centra en la creación de un sistema de información que se encargue de capturar y proveer datos financieros relevante para los profesores, investigadores y alumnos que participan en el Centro de Finanzas del Departamento de Ingeniería Civil Industrial de la Universidad de Chile. Específicamente, mediante el diseño de una Aplicación Web en donde a través de un software se recopilan los datos necesarios y luego se muestran en la plataforma. Para esto se busca hacer un levantamiento de requerimientos, el diseño de los sistemas de información apropiados y la generación de un software que permita recopilar los datos. Hay que tener en consideración, que algunos datos no pueden ser almacenados directamente al no estar en una pagina web, como lo son los de la SBIF, por lo que se almacenan las URLs de los archivos en que están los datos. La metodología utilizada consiste en la recolección de los datos que necesitan o podrían necesitar en el futuro los miembros del Centro de Finanzas. Luego, se diseñan y construyen los sistemas de información apropiados, los que consideran varios filtros al momento de insertar datos para asegurar la calidad de estos. Por último se documenta el sistema permitiendo que a futuro pueda ser extendido a otras necesidades, por lo que su diseño e implementación tendrá que estar pensado para la escalabilidad que se pueda presentar. El proceso de extracción de datos se lleva a cabo, mediante la utilización de Crawlers, conformados de dos tipos de objetos, triggers y jobs. Los triggers se encargan de realizar las tareas que se necesitan cuantas veces sea necesario, puede ser en forma periódica. Y los jobs, de ejecutar cualquier tarea que se desee recalendarizar, en este caso los crawlers que recopilan datos financieros. En caso de que estos fallen, se vuelve a intentar en otro momento, y, si es que vuelve a fallar, se notifica al administrador vía correo electrónico, que cierta tarea no se ha ejecutado exitosamente. Una vez capturados los datos, el sistema sigue funcionando continuamente recopilando y actualizando nuevos datos del día a día para mantener la base de datos siempre actual, ayudando a que el sistema cumpla con su fin principal de mantener informados a todos los interesados. A la fecha de esta memoria, contabilizando data histórica más la extraída, se tienen más de 500 mil datos. Finalmente, gracias a la implementación de este sistema se logra tener acceso rápido a datos financieros importantes, cumpliéndose con los objetivos de este proyecto.

Doctor en Ciencias, Mención Computación / Las bases de datos de grafos han recibido mucho interés en los últimos años, debido a sus aplicaciones en temas como las redes sociales o la Web Semántica. En esta tesis estudiamos lenguajes de consultas que poseen las características navegaciones fundamentales para las distintas aplicaciones de bases de datos de grafos. Estos incluyen la clase de consultas regulares de caminos (RPQs), las cuales chequean si dos nodos están conectados por un camino cuya etiqueta satisface una expresión regular; la clase de las RPQs con inversos (2RPQs), que adicionalmente permiten navegar arcos en la dirección reversa; la clase de las uniones de conjunciones de 2RPQs (UC2RPQs), que resulta de cerrar las 2RPQs bajo las operaciones de join, projección y unión; y la clase de las consultas regulares (RQs) que adicionalmente cierra las UC2RPQs bajo clausura transitiva. En esta tesis demostramos nuevos resultados de complejidad para UC2RPQs y RQs. En la primera parte, estudiamos evaluación de UC2RPQs. Este problema es computacionalmente difícil: NP-completo en general y W[1]-completo en complejidad parametrizada. Esto ha motivado la búsqueda de restricciones que hacen que la evaluación sea tratable o tratable de parámetro fijo. Las más importantes son las clases de UC2RPQs de treewidth acotado, que se pueden evaluar en tiempo polinomial, pero hasta la fecha no se conocen otras restricciones que sean tratables o tratables de parámetro fijo. El resultado principal de esta parte es que la evaluación de UC2RPQs de treewidth acotado módulo equivalencia es tratable de parámetro fijo. Más precisamente, demostramos que, para cada k fijo, existe un algoritmo tratable de parámetro fijo que evalúa UC2RPQs que son equivalentes a alguna UC2RPQ de treewidth a lo más k. También estudiamos el caso cuando la cota k es 1, esto es, la clase de UC2RPQs semánticamente acíclicas, y obtenemos aún más resultados. En particular, demostramos que chequear acaso una UC2RPQ es semánticamente acíclica es decidible y EXPSPACE-completo. En la segunda parte, estudiamos contención de RQs. Las RQs han emergido recientemente como un lenguaje natural para bases de datos de grafos. Las RQs tienen propiedades naturales de clausura, no como las UC2RPQs que no son cerradas bajo clausura transitiva. Además, evaluar RQs no es más difícil que evaluar UC2RPQs (NP-completo). Sin embargo, el problema de contención de RQs aún está abierto. Este problema es decidible, pero sólo cotas no elementales son conocidas. En contraste, es sabido que contención de UC2RPQs es elemental, específicamente, EXPSPACE-completo. El resultado principal de esta parte es que contención de RQs es 2EXPSPACE-completo, y luego, tiene complejidad elemental tal como las UC2RPQs. También estudiamos restricciones de RQs que mejoran la complejidad de evaluación o contención, y algunas extensiones. En particular, demostramos que contención para una generalización natural de RQs para bases de datos relacionales es 2EXPSPACE-completo. / Graph databases have gained renewed interest in recent years, due to their application in areas such as social networks and the Semantic Web. We study graph query languages that provide the fundamental navigational features needed in di erent graph database applications. This includes the class of regular path queries (or RPQs for short), which check whether two nodes are connected by a path whose label satis es a regular expression; the class of two-way RPQs (2RPQs), which additionally enables backward navigation of edges; the class of unions of conjunctive 2RPQs (UC2RPQs), which results from closing 2RPQs under the operations of join, projection, and union; and the class of regular queries (RQs), which additionally closes UC2RPQs under transitive closure. In this thesis, we provide new complexity results for UC2RPQs and RQs. In the rst part, we study query evaluation for UC2RPQs. This problem is known to be computationally hard: NP-complete in combined complexity and W[1]-complete in parameterized complexity. This has motivated the search for restrictions that lead to ( xed-parameter) tractable evaluation. The most prominent restrictions are the classes of UC2RPQs of bounded treewidth, which can be evaluated in polynomial time, but no other tractable or xed-parameter tractable restrictions are known to date. Our main result in this part is that evaluation for UC2RPQs of bounded treewidth modulo equivalence is xed-parameter tractable. More precisely, we show that, for each xed k 1, there is a xed-parameter tractable algorithm that evaluates UC2RPQs that are equivalent to some UC2RPQ of treewidth at most k. We also study the case when the bound k equals 1, that is, the class of semantically acyclic UC2RPQs, and provide further results. In particular, we show that checking whether a UC2RPQ is semantically acyclic is decidable and Expspace-complete. In the second part, we study query containment for RQs. The class of RQs has emerged only recently as a natural graph query language. RQs have natural closure properties, unlike UC2RPQs that are not closed under transitive closure. Moreover, RQs are not harder to evaluate than UC2RPQs (NP-complete). Nevertheless, the containment problem for RQs has been open so far. This problem is decidable, but only nonelementary complexity upper bounds are known. In contrast, query containment for UC2RPQs is known to be elementary, speci cally, Expspace-complete. Our main result in this part is that containment of RQs is 2Expspace-complete, and therefore, it has elementary complexity just like UC2RPQs. We also study restrictions of RQs that help to alleviate the complexity of evaluation or containment, and also some extensions. In particular, we show that containment of a natural generalization of RQs for relational databases is still 2Expspace-complete. / Este trabajo ha sido financiado por Conicyt y el Centro de Investigación de la Web Semántica

Ingeniero Civil Matemático / En muchos problemas que surgen en el contexto de consultar información en bases de datos estructuradas sobre grafos (como encontrar asociaciones semanticas en grafos RDF, encontrar emparejamientos exactos o aproximados the patrones de texto, realizar alineación de secuencias de texto, etc.) es un requerimiento común el buscar entidades unidas por secuencias de etiquetas relacionales de acuerdo a un patrón regular. Para este propósito, el lenguaje de consulta $\CRPQ(\S)$ ha sido propuesto para extender la altamente estudiada clase de consultas conjuntivas por caminos regulares (CRPQs por su sigla en inglés), la cual es insuficiente para esta tarea, realizando comparación de caminos con relaciones en la clase $\S$.\\ Poco es conocido acerca de la complejidad computacional precisa de la evaluación de consultas en $\CRPQ(\S)$ cuando $\S$ es una relación de interés por aparecer naturalmente en aplicaciones en bases de datos, como lo son \emph{subsecuencia} ($\ss$), \emph{sufijo} $(\suff)$ y \emph{subpalabra} ($\sw$). Esta pregunta es consecuentemente estudiada en esta tesis, proporcionando nuevas cotas de complejidad para la evaluación de consultas en los lenguajes $\CRPQ(\ss)$, $\CRPQ(\suff)$ y $\CRPQ(\sw)$. Se muestra que el primer lenguaje es dificil de ser practicable, construyendo una consulta en él cuya complejidad de evaluación es $\NP$-completo. Se muestra también que la evaluación de consultas en los últimos dos lenguajes puede realizarse en $\PSPACE$, mediante la reducción del problema a \emph{ecuaciones de palabras con restricciones regulares}. Adicionalmente, se muestra que la classe $\CRPQ(\suff)$ es práctica, construyendo un algoritmo de evaluación cuya complejidad, cuando la consulta es considerada una constante, está en $\NLOGSPACE$ , la cuál es una complejidad de evaluación estandar en este contexto.\\ Esta tesis plantea además interesantes preguntas teóricas sobre ecuaciones de palabras con restricciones regulares. Más precisamente, cuál es la complejidad de resolver ecuaciones fijas con restricciones como entrada, la cual es una pregunta abierta en la literatura al leal saber y entendimiento del autor. Un resultado es establecido para el caso más simple, mostrando una clase de ecuaciones cuya satisfacibilidad con restricciones regulares puede ser decidida en $\NLOGSPACE$.

Ingeniera Civil en Computación / Business Intelligence es la habilidad para transformar datos en información, y la información en conocimiento, de forma que se pueda optimizar la toma de decisiones en los negocios. Debido al aumento exponencial en la cantidad de datos disponibles en los ultimos años y a la complejidad de estos, las herramientas tradicionales de bases de datos y business intelligence pueden no dar a basto, suponiendo numerosos riesgos para las empresas. El objetivo de la presente memoria fue analizar el uso del framework de aplicaciones distribuidas Hadoop en comparación a la solución actual de Penta Analytics, buscando hacer un mejor uso de la infraestructura y aumentando la disponibilidad de los datos a medida que el volumen de estos crece. Actualmente esta compañía utiliza un motor de bases de datos analíticas llamado Infobright, que permite la ejecución de consultas de manera eficiente dada su estructura columnar, pero a nivel de un único servidor, limitando las capacidades de manejo de datos y uso eficiente de todos los servidores. Para realizar la comparación se tomaron en cuenta dos casos de procesamiento de datos reales; consultas OLAP y ETL, además de tres casos de consultas estándar. Para cada uno de estos casos se realizaron tres variantes según el volumen a procesar para evaluar el rendimiento según crecían los datos. La solución Hadoop fue desarrollada en un cluster en la nube, con tres servidores (un maestro y dos esclavos). En el sistema de archivos del cluster se almacenó la información a procesar y se realizaron los sets de consultas mediante dos herramientas Hadoop: Hive e Impala. Los resultados obtenidos arrojaron que Hive presenta tiempo superiores a Impala e Infobright, esto debido al overhead que implica lanzar las tareas map y reduce, sin embargo es el único que ofrece tolerancia ante el fallo de un nodo. Por otro lado Impala presenta la menor latencia, con un tiempo de respuesta mucho menor a Infobright, no obstante presenta la mayor utilización de memoria. A partir de los resultados se pudo observar que Hive se comporta mejor en trabajos pesados tipo ETL donde la robustez prime sobre el tiempo, e Impala aplica mejor en consultas ligeras donde prime la velocidad. Se pudo concluir que la combinación de distintas herramientas en un ambiente con tecnología Hadoop pueden ofrecer un buen desempeño, además de mejor utilización de máquinas y eventual tolerancia a fallos. Sin embargo hay que tomar en cuenta la curva de aprendizaje implicada.

Magíster en Ingeniería de Redes de Comunicaciones / La industria de telefonía móvil de prepago chilena concentra al 70% de los clientes móviles de los principales operadores en el país. Este servicio utiliza un proceso de descuento y abono en línea que permite rebajar en forma casi instantánea los créditos consumidos al utilizar los servicios de voz y datos habilitados en el terminal, y abonar el crédito correspondientes cuando se hace aplica una recarga prepagada, que son las operaciones más habituales que se aplican para cambiar el estado de operación de un terminal móvil prepago. La dinámica de estas transiciones depende de manera íntima de la operatividad del sistema computacional que administra y ejecuta estos cambios. Su arquitectura, del tipo servidor-cola de comandos, utiliza una filosofía first-in first-out (FIFO) para procesar cada comando asociado a la transición de estado que debe aplicarse sobre cada terminal de la red. Este sistema de administración de comandos puede colapsar si la demanda por cambios de estado aumenta en forma repentina y supera la capacidad de procesamiento del servidor. Ello tiene como consecuencia un aumento desmedido del tamaño de la cola de comandos, lo que a su vez, puede originar problemas en las prestaciones de telecomunicaciones dentro de la red y pérdidas monetarias al operador al dejar fuera de línea el sistema de cobro. Este fenómeno, que se denomina encolamiento, es controlado en los sistemas comerciales utilizando alarmas por umbral, las que indican a los administradores del sistema la necesidad de activar las contramedidas necesarias para restablecer el correcto funcionamiento del sistema. Sin embargo, el valor de este umbral es fijado sin utilizar necesariamente criterios de optimalidad de desempeño, lo que reduce la eficiencia en la operación técnica y comercial del servicio. La hipótesis de trabajo de esta investigación es que el uso un umbral ``duro'' puede ser mejorado al emplear un enfoque que incorpore la historia del proceso que describe la longitud de la cola de comandos, como el basado en las distribuciones de probabilidad de las condiciones de operación normal y de encolamiento. Para validar esta conjetura, se diseñó un detector de encolamientos basado en la divergencia de Kullback-Leibler, la que permite comparar la distribución instantánea de las observaciones con las correspondientes a la condición de operación normal y de encolamiento. La metodología empleada para validar esta tesis se basó en la simulación computacional de las transiciones de estado descrita mediante el uso de una cadena de Markov de 3 estados, que se utilizó para cuantificar la operación del detector y compararla con las métricas asociadas a la detección dura mediante umbrales. Las métricas de desempeño empleadas fueron el porcentaje de errores de tipo I (no detección) y de tipo II (falso positivo), las cuales fueron calculadas en forma empírica en ambos detectores. Además, el funcionamiento del detector fue validado con datos reales de operación a partir de un registro de 14 meses de observaciones. Los resultados obtenidos avalan la hipótesis planteada, en el sentido que se observaron mejoras de desempeño de hasta un 60% en la detección de encolamiento y un 85% en la disminución de falsos positivos al comparar el detector de Kullback-Leibler con aquellos basados en umbral. En este sentido, estos resultados constituyen un avance importante en el aumento de la precisión y confiabilidad de detección de condiciones de fallas que justifica la incorporación de esta nueva estrategia en el ambiente de operaciones de una empresa de telecomunicaciones. Además, la hace eventualmente extensible a procesos controlados a través de colas.

Magíster en Ciencias, Mención Computación / Ingeniero Civil Matemático / Las bases de datos de grafos son un modelo que ha ganado terreno en los últimos años, dada la necesidad de modelar situaciones complejas en donde el modelo relacional no es suficiente. En este trabajo introducimos el tema haciendo una revisión del estado del arte de las bases de datos de grafos, explicando algunas de sus aplicaciones reales, definiendo algunos de los diferentes modelos teóricos y analizando las implementaciones más importantes que existen en la realidad. De nuestro análisis concluimos que la gran falencia en el tema es la ausencia de un lenguaje de consulta formal, con una sintaxis y semántica clara, y que tenga un buen equilibrio entre expresividad y complejidad. Nuestra propuesta para solucionar este problema es utilizar Converse-PDL como lenguaje de consulta de bases de datos de grafos, definiéndolo formalmente, y demostrando que su complejidad teórica es óptima. Además, mostramos que la expresividad de este lenguaje es suficiente para una gran cantidad de aplicaciones. Una vez definido nuestro lenguaje, procedemos a diseñar una implementación eficiente, definiendo los algoritmos y las estructuras de datos necesarias, cuidando de cumplir todas las restricciones que están presentes en nuestro modelo computacional. Luego, procedemos a realizar la implementación en sí, describiendo en detalle las representaciones internas de los distintos elementos, respaldando con resultados experimentales las decisiones tomadas. Además, explicamos las distintas mejoras y optimizaciones que realizamos, con el fin de obtener la mayor eficiencia posible. Una vez terminada la implementación, procedemos a explicar todos los archivos programados y la interfaz de usuario implementada, con el fin de facilitar los futuros desarrollos. Con el fin de validar nuestra implementación, procedemos a diseñar un experimento para evaluar cuantitativamente el desempeño de nuestra implementación. El experimento diseñado se ejecuta en nuestra implementación, así como en otras tres implementaciones existentes, escogiendo los proyectos más competitivos, para así realizar una comparación objetiva. Finalizamos nuestro trabajo con las conclusiones obtenidas a partir de los experimentos, destacando los aspectos más importantes de nuestra implementación, y exponiendo algunas ideas a desarrollar en el futuro.

No autorizado por el autor para ser publicada a texto completo / Los Sistemas de Información tradicionales generan muchas incertidumbres al minuto de realizar búsquedas en un ambiente de negocio. Esto es producto que la principal características de dicha información es que la componen documentos que poseen un diccionario de palabras pequeño, acotado al negocio y de un tamaño reducido, que apunta a entregar una información específica. En esta tesis abordamos el diseño y desarrollo de un buscador que utiliza las variables relevantes del negocio para pesar los documentos que recupera. Con este proyecto se logró obtener un Sistema de Recuperación de la Información que valoriza los documentos por las variables de las reglas de negocio y por variables del usuario del Sistema, diseñado en un sistema parametrizable, permitiendo la adaptación a distintos negocios y distintos tipos de documentos. Las pruebas de usuario comprueban que el buscador posee un rendimiento similar a otros al momento de recuperar documentos relevantes, pero utilizando variables del documento propios del negocio. Este logro es fundamental, ya que no sólo sabemos que los resultados poseen contenidos relevantes para el usuario, sino que también poseen una relevancia en las operaciones que la empresa realiza.

No description available.

El Perú ha logrado encabezar el ranking de Microfinanzas en los últimos años, y se ha mantenido entre los primeros puestos destacando el buen desempeño de las políticas y regulaciones que tiene para ofrecer sus servicios garantizando su prestación a personas de más bajos ingresos. Según ASOMIF, el sector Microfinanciero, compuesto en su mayoría por micro y pequeñas empresas, ha alcanzado un saldo de 38,661 millones de soles expresado en un 14.73% de crecimiento respecto a los años 2016 y 2017, incrementando constantemente la cartera de clientes, servicios y productos financieros. Por ello, es inminente no considerar que el crecimiento de los datos que maneja este sector también presentará un crecimiento exponencial con el pasar de los años. Por tal motivo, el presente proyecto consiste en la implementación de un modelo de madurez de gestión de datos maestros en una entidad microfinanciera del Perú, con la finalidad de que dichas entidades puedan identificar el nivel de madurez en la gestión de sus datos y tomar acciones reactivas según el caso. Como primer paso, se realizó una investigación profunda de artículos relacionados a la Gestión de Datos Maestros, logrando identificar casos de éxitos, Modelos de Gestión de Datos, conceptos de Gobierno de Datos, participación activa del sector Microfinanciero en el Perú y herramientas que involucra soluciones de MDM. Seguidamente, se planteó un modelo de madurez con el propósito de medir el estado actual de la gestión de datos que lleva a cabo la entidad, constituido por 6 dimensiones y 15 criterios, distribuidos en 5 niveles de madurez. Posteriormente, el modelo fue implementado en una microfinanciera peruana, haciendo uso de una herramienta web que se desarrolló en el transcurso del proyecto, identificando los puntos de mejora y aplicando los planes de acción correspondientes. Finalmente, se realizó un artículo de investigación, el cual fue aprobado en el Congreso ICKMS 2018 en Florida, EEUU. / Peru has managed to lead the ranking of Microfinance in recent years, and has remained among the top positions highlighting the good performance of policies and regulations that have to offer their services guaranteeing their provision to people with lower incomes. According to ASOMIF, the Microfinance sector, composed mostly of micro and small companies, has reached a balance of 38,661 million soles expressed in a 14.73% growth compared to 2016 and 2017, constantly increasing the portfolio of clients, services and financial products. Therefore, it is imminent not to consider that the growth of the data handled by this sector will also show exponential growth over the years. For this reason, the present project consists of the implementation of a master data management maturity model in a microfinance institution in Peru, with the purpose that these entities can identify the level of maturity in the management of their data and take actions reactive according to the result. As a first step, an in-depth investigation of articles related to the Management of Master Data was carried out, successfully identifying cases of success, Data Management Models, Data Governance concepts, active participation of the Microfinance sector in Peru and tools that involve solutions of MDM. Next, a maturity model was proposed with the purpose of measuring the current state of data management carried out by the entity, consisting of 6 dimensions and 15 criteria, divided into 5 levels of maturity. Subsequently, the model was implemented in a Peruvian microfinance institution, making use of a web tool that was developed during the course of the project, identifying points of improvement and applying the corresponding action plans. Finally, a research article was prepared and approved at the ICKMS 2018 Congress in Florida, USA / Tesis