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.
| Identifer | oai:union.ndltd.org:UCHILE/oai:repositorio.uchile.cl:2250/114719 |
| Date | January 2013 |
| Creators | Ríos Díaz, Gonzalo Andrés |
| Contributors | Barcelo Baeza, Pablo, Facultad de Ciencias Físicas y Matemáticas, Departamento de Ciencias de la Computación, Navarro Badino, Gonzalo, Pérez Rojas, Jorge, Kiwi Krauskopf, Marcos |
| Publisher | Universidad de Chile |
| Source Sets | Universidad de Chile |
| Language | Spanish |
| Detected Language | Spanish |
| Type | Tesis |
| Rights | Attribution-NonCommercial-NoDerivs 3.0 Chile, http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ |
Page generated in 0.0018 seconds