[Back]

R. Pichler, E. Sallinger, V. Savenkov:
"Relaxed Notions of Schema Mapping Equivalence Revisited";
Talk: International Conference on Database Theory (ICDT), Uppsala, Schweden; 2011-03-21 - 2011-03-25; in: "Proceedings of the 14th International Conference Database Theory", T. Milo (ed.); ACM, (2011), ISBN: 978-1-4503-0529-7; Paper ID 10, 12 pages.

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.

Project Head Reinhard Pichler:
Service-orientierte Datenintegration