• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Aproximaciones eficientes de consultas conjuntivas

Romero Orth, Miguel January 2012 (has links)
Cuando encontrar la respuesta exacta a una consulta sobre una base de datos muy grande es intratable, es natural aproximar la consulta por otra más eficiente que pertenezca a una clase con buenas cotas en la complejidad de evaluación de consultas. En esta tesis estudiamos tales aproximaciones para consultas conjuntivas. Estas consultas son de especial interés en base de datos, y además sabemos muy bien qué clases de consultas admiten una evaluación eficiente, como las consultas acíclicas, o las de (hyper)treewidth acotado. Definimos una aproximación a una consulta Q como una consulta de una de esas clases que discrepa con Q lo menos posible. Nos concentramos en aproximaciones que siempre entregan respuestas correctas. Probamos que para las clases tratables de consultas conjuntivas mencionadas anteriormente, siempre existen aproximaciones y sus tamaños son a lo más polinomiales en el tamaño de la consulta original. Esto se sigue de resultados generales obtenidos que relacionan propiedades de clausura de clases de consultas conjuntivas con la existencia de aproximaciones. Además, probamos que en muchos casos el tamaño de la aproximación es a lo más el tamaño de la consulta original. Presentamos una serie de resultados sobre cómo ciertas propiedades combinatoriales de las consultas afectan a sus aproximaciones y estudiamos cotas en la cantidad de aproximaciones, al igual que la complejidad de encontrar e identificar aproximaciones. Finalmente, consideramos aproximaciones que entregan todas las respuestas correctas y estudiamos sus propiedades.

Page generated in 0.0673 seconds