Dublin Core
Title
Extending query languages for data exchange
Subject
000
Ciencias de la computación
Lenguajes de programación (Computadores electrónicos).
Procesamiento electrónico de datos.
Administración de bases de datos.
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2009
El problema del Data Exchange consiste en tomar datos estructurados bajo un esquema fuente y crear una instancia de un esquema destino que refleje lo más adecuadamente posible los datos fuente. La clase de unión de consultas conjuntivas (UCQ) se comporta particularmente bien en el entorno de Data Exchange; sus respuestas certeras se pueden computar en tiempo polinomial (complejidad de datos). Pero esta no es la única clase con esa propiedad: las respuestas certeras para cualquier programa en DATALOG también pueden seer computadas en tiempo polinomial. El problema es que tanto UCQ como DATALOG no permiten la negación de átomos, pues el añadir negación no restringida vuelve intratable el problema.
En este trabajo, proponemos un lenguaje llamado DATALOGc(\2260), que extiende al lenguaje DATALOG con una forma restringida de negación, y estudiamos algunas de sus propiedades fundamentales. En particular, mostramos que las respuestas certeras a programas DATALOGc(\2260) pueden ser computadas en tiempo polinomial (complejidad de datos), y que toda unión de consultas conjuntivas con a lo más una desigualdad o átomo negado por disyunción puede ser reescrita como un programa en DATALOGc(\2260). Ms aún, mostramos que este también es el caso para una restricción sintáctica de la clase de uniones de consultas conjuntivas con a lo más dos desigualdades por disyunción. Esta restricción es óptima, pues el computar respuestas certeras se vuelve intratable al remover cualesquiera de ellas. Finalmente, proveemos de un análisis detallado de la complejidad combinada de computar las respuestas certeras a un programa en DATALOGc(\2260) y otros lenguajes de consulta relacionados. En particular, mostramos que este problema es EXPTIME-completo para DATALOGc(\2260), incluso si se restringe a consultas conjuntivas con una desigualdad, que es un fragmento de DATALOGc(\2260) por los resultados enunciados anteriormente.
Creator
Reutter de la Maza, Juan
Date
2012-10-25T12:20:45Z
2012-10-25T12:20:45Z
2009
Contributor
Arenas Saavedra, Marcelo Alejandro
Pontificia Universidad Católica de Chile. Escuela de Ingeniería
Rights
acceso abierto
Format
application/pdf
Language
en
Type
tesis de maestría
Identifier
10.7764/tesisUC/ING/1343
https://doi.org/10.7764/tesisUC/ING/1343
https://repositorio.uc.cl/handle/11534/1343