Data exchange and schema mappings in open and closed worlds

Leonid Libkin, Cristina Sirangelo

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In the study of data exchange one usually assumes an open-world semantics, making it possible to extend instances of target schemas. An alternative closed-world semantics only moves 'as much data as needed' from the source to the target to satisfy constraints of a schema mapping. It avoids some of the problems exhibited by the open-world semantics, but limits the expressivity of schema mappings. Here we propose a mixed approach: one can designate different attributes of target schemas as open or closed, to combine the additional expressivity of the open-world semantics with the better behavior of query answering in closed worlds.

We define such schema mappings, and show that they cover a large space of data exchange solutions with two extremes being the known open and closed-world semantics. We investigate the problems of query answering and schema mapping composition, and prove two trichotomy theorems, classifying their complexity based on the number of open attributes. We find conditions under which schema mappings compose, extending known results to a wide range of closed-world mappings. We also provide results for restricted classes of queries and mappings guaranteeing lower complexity.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2008, June 9-11, 2008, Vancouver, BC, Canada
PublisherACM
Pages139-148
Number of pages10
ISBN (Print)978-1-60558-152-1
DOIs
Publication statusPublished - 9 Jun 2008

Fingerprint

Dive into the research topics of 'Data exchange and schema mappings in open and closed worlds'. Together they form a unique fingerprint.

Cite this