Show simple item record

Professor Guidedc.contributor.advisorBarcelo Baeza, Pablo
Authordc.contributor.authorRomero Orth, Miguel 
Staff editordc.contributor.editorFacultad de Ciencias Físicas y Matemáticas
Staff editordc.contributor.editorDepartamento de Ciencias de la Computación
Associate professordc.contributor.otherKiwi Krauskopf, Marcos 
Associate professordc.contributor.otherNavarro Badino, Gonzalo
Associate professordc.contributor.otherPérez Rojas, Jorge 
Associate professordc.contributor.otherArenas Saavedra, Marcelo
Admission datedc.date.accessioned2012-10-01T17:58:45Z
Available datedc.date.available2012-10-01T17:58:45Z
Publication datedc.date.issued2012
Identifierdc.identifier.urihttp://repositorio.uchile.cl/handle/2250/110949
Abstractdc.description.abstractCuando 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.es_CL
Lenguagedc.language.isoeses_CL
Publisherdc.publisherUniversidad de Chilees_CL
Keywordsdc.subjectMinería de datoses_CL
Keywordsdc.subjectHomomorfismos (Matemáticas)es_CL
Keywordsdc.subjectConjuctive queryes_CL
Keywordsdc.subjectQuery approximationes_CL
Títulodc.titleAproximaciones eficientes de consultas conjuntivases_CL
Document typedc.typeTesises_CL


Files in this item

Icon

This item appears in the following Collection(s)

Show simple item record