Extending query languages for data exchange
Loading...
Date
2009
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.
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.
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2009