Introducción al Trabajo de Título
Entrar

Análisis combinatorio de los order graphs Memoria Doble Titulación Ciencia e Ingeniería de datos Teoría de la computación

Profesor Guia
Sub Áreas Bases de datos, Análisis y diseño de algoritmos y estructuras de datos

Descripción


Los order graphs son una invención reciente para minimizar la cantidad de índices que deben mantenerse en una base de datos para poder realizar los joins en forma worst-case-optimal. Si la tabla tiene k columnas, basta con un order graph de dimensión k. Un order graph de dimensión k puede tener hasta k! nodos, uno por cada permutación de los atributos 1..k, y satisfacer cierta propiedad combinatorial (deben existir determinados caminos en el grafo). No sabemos en este momento todo sobre el tamaño mínimo de los order graphs, especialmente para dimensiones más allá de 6, sólo tenemos cotas inferiores y superiores demostradas, así como algunos programas de búsqueda exhaustiva o heurísticas que hemos usado para establecer cotas superiores en forma empírica. En la memoria se busca obtener nuevos resultados, ya sea en forma de trabajo teórico mediante análisis combinatorio, o en forma de trabajo empírico desarrollando mejores métodos de búsqueda.