[Back]

R. Pichler, E. Sallinger, V. Savenkov:
"Relaxed Notions of Schema Mapping Equivalence Revisited";
Theory of Computing Systems (invited), 52 (2013), 3; 483 - 541.

Recently, two relaxed notions of equivalence of schema mappings have been introduced, which provide more potential of optimizing schema mappings than logical equivalence: data exchange (DE) equivalence and conjunctive query (CQ) equivalence. In this work, we systematically investigate these notions of equivalence for mappings consisting of s-t tgds and target egds and/or target tgds. We prove that both CQ- and DE-equivalence are undecidable and so are some important optimization tasks (like detecting if some dependency is redundant). However, we also identify an important difference between the two notions of equivalence: CQ-equivalence remains undecidable even if the schema mappings consist of s-t tgds and target dependencies in the form of key dependencies only. In contrast, DE-equivalence is decidable for schema mappings with s-t tgds and target dependencies in the form of functional and inclusion dependencies with terminating chase property.

Schema mappings, Schema mapping equivalence, Data translation, Data exchange, Data integration

http://dx.doi.org/10.1007/s00224-012-9397-0

http://link.springer.com/article/10.1007%2Fs00224-012-9397-0

Project Head Reinhard Pichler:
Service-orientierte Datenintegration