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

El alcance del presente proyecto de fin de carrera el análisis y diseño de los procesos que componen el conjunto de ITIL como son: La Gestión de Configuraciones y La Gestión de Cambios; elaborada para el área de TI de la empresa importadora y distribuidora de vidrios y aluminios. El presente proyecto tiene como finalidad establecer una guía de buenas prácticas en el área de TI, la cual pueda ser consultada al realizarse las tareas que involucran los procesos de gestión de configuraciones y gestión de cambios. La presente propuesta está dirigida a todas las organizaciones y/o empresas que manejen recursos de TI. Por lo tanto, las recomendaciones o buenas prácticas tratarán de ser las más genéricas posibles para poder apartase fácilmente a cualquier ambiente. Todos los requerimientos serán tomados de ITIL v3 ya que este constituye un marco de trabajo de las mejores prácticas destinadas a facilitar la entrega de servicios de tecnologías de la información (TI) de alta calidad. Cabe resaltar que no se realizará la implantación de un sistema propiamente dicho en el presente proyecto de fin de carrera dado el tiempo limitado que se tiene para realizar el proyecto y la resistencia al cambio de parte de la gerencia general de la empresa. / Tesis

La investigación es una de las funciones más importantes de la PUCP, en la cual participan investigadores y alumnos. De estas investigaciones se obtienen distintos resultados como publicaciones, conferencias, tesis, entre otros. Para obtener información acerca de las investigaciones que han sido o están siendo realizadas en la PUCP, se puede hacer uso de algunas herramientas disponibles en la web. Sin embargo, se puede apreciar que la información disponible es escasa y se encuentra dispersa entre varias herramientas. Por estas razones, se propone el desarrollo de un sistema de gestión de la investigación para la sección de Ingeniería Informática que centralice y gestione la información sobre la investigación y genere reportes que los investigadores consideren necesarios. Este sistema permite el registro de información sobre todos los componentes que forman parte de una investigación en la sección. Con ello se puede consultar el tipo de investigación, paradigma usado o la etapa en la que se encuentra un proyecto, así como los participantes y los resultados del proyecto (como publicaciones y eventos). De la misma manera se puede obtener información sobre investigadores, grupos, proyectos, colaboración científica, financiamiento, líneas de investigación y resultados de un proyecto. A partir de esto, se permite el descubrimiento de información acerca de la investigación en la sección para obtener un panorama más claro sobre su estado. Por otro lado, los investigadores pueden requerir la elaboración manual de reportes solicitados tanto por la universidad como por entidades externas que otorguen financiamiento como FINCyT o FONDECYT. Esta tarea es simplificada con la generación de reportes a partir del sistema desarrollado. Gracias a esto, el usuario puede evaluar el estado de la investigación en cualquier periodo dado, tanto a nivel de la sección como a nivel de un grupo, persona o línea de investigación. Finalmente, para facilitar la migración de datos hacia el sistema, se incluyó un módulo de importación de datos en formato XML. Esto facilita la tarea de migrar la información almacenada en otros sistemas de la universidad o información histórica almacenada en otros medios. / Tesis

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.

Ingeniero Civil en Computación / Hoy en día, la automatización de procesos manuales permite en las empresas logran optimizar su tiempo para poder utilizarlo en otros recursos. A continuación se presenta la finalización de la construcción de un sistema capaz de dar apoyo en este sentido a la parte medioambiental de una empresa, específicamente en todos los procesos que son necesarios realizar para un correcto levantamiento de información de flora. Chile posee una amplia variedad de especies de flora registradas hasta la fecha, conocer todos sus nombres y modificaciones de los mismos es prácticamente imposible además de recordar cuales de ellas están en categoría de conservación, lo que es de vital importancia para un informe de flora. Para poder suplir esto, los especialistas llevan consigo libros con información de las especies existentes a terreno junto con un dispositivo GPS para ubicarse y un cuaderno para tomar notas de las especies observadas. Luego del proceso de toma de datos, los expertos deben generar listados con todas las especies vistas y verificar una por una cuales están en alguna categoría de conservación para agregar los datos correspondientes, además de comprobar que el nombre que se tiene de la especie es el último aceptado hasta la fecha del informe a entregar. Mientras tanto, por otro lado se tiene a una persona que está constantemente consultando por los avances llevados a cabo en cortos periodos de tiempo. Para solucionar lo anterior, se creó una herramienta computacional que permite la actualización de las especies de flora, almacenamiento de información de observaciones y generación de informes florísticos de manera automática por mencionar algunas funcionalidades que ayudan a los cuatro tipos de usuario: Administrador, Coordinador, Colector y Fiscalizador. Esta memoria describe el desarrollo de esta herramienta, la cual consiste en una aplicación móvil para Android junto con un sistema web de administración de datos. En este sistema se incorporaron dos extractores de información o crawlers que mensualmente recolectan los datos de la especies de flora presentes en Chile y también extraen la información correspondiente a todas las especies que están en alguna categoría de conservación vigente en el país. Junto con esto, se crearon interfaces en la aplicación móvil que son capaces de mostrar al usuario un mapa con los lugares donde debe realizar sus tomas de datos y actualizar el listado de especies a la última versión disponible. Además también se creó una vista web para que las personas que quieran estar al tanto del avance puedan hacerlo ingresando simplemente al sistema y, por último, se terminó la construcción de otra interfaz en la cual es posible descargar los informes finales que son necesarios para un correcto levantamiento de flora. El nuevo sistema brinda un ahorro de trabajo de gabinete que llega a los tres días según la empresa, permite la generación de informes automática con datos más completos de las especies y un cliente que puede supervisar el avance de sus proyectos en tiempo real.

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.

Muestra como mejorar el servicio prestado por Microtec, garantizando la disponibilidad del hardware y software que se utiliza en el dictado de los cursos haciendo que se interactue con el sistema de matricula para reconocer y permitir el acceso al alumno a través de las computadoras del laboratorio de FIA - DATA a los programas que requiera según su especialidad.

Guía de recursos para la investigación para usuario de la Facultad de Artes Comtemporáneas.

Made available in DSpace on 2012-09-06T01:11:57Z (GMT). No. of bitstreams: 2 license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) 849.pdf: 1878124 bytes, checksum: 96c6fd44407809d315bca0121b1f16ff (MD5) Previous issue date: 2005 / Este trabalho analisa as possibilidades de tornar interoperáveis bases de dados heterogêneas, de forma que possam ser pesquisadas através de uma única interface. A biblioteca do Instituto Fernandes Figueira, Unidade materno-infantil da Fiocruz é referência em tratamento de doenças de alta complexidade. Estes profissionais buscam a Biblioteca co necessidades de informações voltadas para a decisão clínica. As bases de dados mais pesquisadas por estes profissionais são as bases de dados LILACS, MEDLINE e ACERVO FIOCRUZ. Portanto estas bases norteiam este estudo e são algumas facetas como: os procedimentos de descrição e as estruturas das bases, buscando semelhanças e divergências nos índices e nos campos de exibição dos Tesauros DeCS e MeSH; e tecnologias utilizadas e/ou compatíveis. Paalelamente busca-se apresentar algumas ferramentas tecnológicas como os protocolos Z39.50 e o OAI-PMH, os meuscadores, o conjunto de metadados Dublin Core e o MetaIAH. Através destas análises delineou-se três modelos conceituais para alcançar a interoperabilidade, são eles: compartilhamento de esforços, quando tanto a Interface de Consulta (IC) e os Recursos Informacionais (RI) trabalham para garantir interoperabilidade; Esforço concentrado nos Ris, quando os Recursos Informacionais arcam com todo o esforço para possibilitar a interoperabilidade; e, Esforço concentrado na IC, quando a Interface de consulta se adapta para suprir as divergências de cada base proporcionando a interoperabilidade. Para finalizar comparam-se os modelos e as bases de dados estudadas destacando-se os modelos que se constituem como alternativas de interoperabilidade para a biblioteca do Instituto Fernandes e quais as vantagens e desvantagens de cada uma delas.