Paper Info
Title
The structure of inverses in schema mappings
Abstract
A schema mapping is a specification that describes how data structured under one schema (the source schema) is to be transformed into data structured under a different schema (the target schema). The notion of an inverse of a schema mapping is subtle, because a schema mapping may associate many target instances with each source instance, and many source instances with each target instance. In PODS 2006, Fagin defined a notion of the inverse of a schema mapping. This notion is tailored to the types of schema mappings that commonly arise in practice (those specified by “source-to-target tuple-generating dependencies”, or s-t tgds). We resolve the key open problem of the complexity of deciding whether there is an inverse. We also explore a number of interesting questions, including: What is the structure of an inverse? When is the inverse unique? How many nonequivalent inverses can there be? When does an inverse have an inverse? How big must an inverse be? Surprisingly, these questions are all interrelated. We show that for schema mappings M specified by full s-t tgds (those with no existential quantifiers), if M has an inverse, then it has a polynomial-size inverse of a particularly nice form, and there is a polynomial-time algorithm for generating it. We introduce the notion of “essential conjunctions” (or “essential atoms” in the full case), and show that they play a crucial role in the study of inverses. We use them to give greatly simplified proofs of some known results about inverses. What emerges is a much deeper understanding about this fundamental and complex operator.
Year
DOI
Venue
2010
10.1145/1857914.1857915
Journal of the ACM (JACM)
Keywords
DocType
Volume
essential conjunction,different schema,target instance,chase,nonequivalent inverse,target schema,inverse,schema mappings M,dependencies,source schema,polynomial-size inverse,data integration,schema mapping,essential atom,model management,source instance,data exchange
Journal
57
Issue
ISSN
Citations 
6
0004-5411
10
PageRank 
References 
Authors
0.75
12
2
Name
Order
Citations
PageRank
Ronald Fagin188082643.66
Alan Nash256327.90