Introducción al Trabajo de Título
Entrar

Resolviendo BGPs + RPQs con estructuras compactas en bases de datos de grafos Memoria Ciencia e Ingeniería de datos Teoría de la computación

Profesor Guia
Sub Áreas Bases de datos, Procesamiento masivo de datos, Web semántica, Análisis y diseño de algoritmos y estructuras de datos

Descripción


Los qdags son una estructura geométrica que pueden representar un grafo con labels mediante tener una matriz de adyacencia por label. Existen dos consultas principales en este tipo de grafos: los basic graph patterns (BGPs), que son un subgrafo con variables a calzar en el grafo de los datos, y las regular path queries (RPQs), que son expresiones regulares sobre la secuencia de labels de caminos del grafo. Tenemos en este momento algoritmos para tanto BGPs como RPQs sobre qdags, pero éstos no conversan e incluso están escritos uno en C++ y el otro en C. En esta memoria se quieren unificar estas implementaciones y poder soportar, usando qdags, consultas que mezclan BGPs con RPQs.