On the complexity of bidirectional constraints for data exchange
Loading...
Date
2014
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Los mapeos de esquemas tienen una importancia fundamental en el manejo de datos, pues han mostrado ser la base para numerosas tareas de interoperabilidad de datos como intercambio de información, integración de datos y manejo de datos entre pares. La mayor parte de la investigación sobre mapeos de esquemas se ha concentrado en mapeos descritos por st-tgds, las cuales si bien son naturales y simples de especificar, no logran imponer suficientes condiciones para definir sin ambigüedad cuáles son las instancias que debieran materializarse al intercambiar información. Recientemente, se ha propuesto el uso de dependencias bidireccionales en la especificación de mapeos de esquemas, siendo capaces de imponer al mismo tiempo restricciones sobre las instancias del source y del target que participan en ellos, y teniendo el potencial de minimizar la ambigüedad en la descripción de las instancias target. En esta tesis continuamos con el estudio formal sobre las dependencias bidireccionales. En particular, estudiamos la complejidad computacional de dos problemas fundamentales en el contexto de intercambio de información: verificar la existencia de soluciones y contestar consultas. En el primer caso, se analiza tanto la complejidad de los datos como la complejidad combinada, mostrando cotas superiores e inferiores en distintos escenarios. En el segundo caso, además distinguimos entre diversos lenguajes de consulta con distintos poderes expresivos. En las demostraciones introducimos algunas técnicas nuevas, como una versión modificada del clásico algoritmo de chase.
Description
Tesis (Master of Sciences in Engineering)--Pontificia Universidad Católica de Chile, 2014