Optimizing schema mappings with relaxed notions of equivalence

Abstract

Schema-Abbildungen spielen eine wichtige Rolle in verschiedenen Bereichen der Datenbankforschung -- insbesondere im Bereich der Datenintegration und des Datenaustauschs. Die Grundlagen der Optimierung von Schema-Abbildungen wurden vor kurzem von Fagin et al. geschaffen, indem neue Konzepte der "Äquivalenz" zwischen zwei Schema-Abbildungen eingeführt wurden. Dies sind die Datenaustausch-Äquivalenz und die konjunktive Abfrageäquivalenz. Beides sind natürliche abgeschwächte Formen der logischen Äquivalenz. Fagin et al. haben verschiedene wichtige Eigenschaften dieser abgeschwächten Formen der Äquivalenz gezeigt, die klar das Potenzial dieser Konzepte zur Optimierung verschiedenster Klassen von Schema-Abbildungen dargelegt haben.<br />In dieser Arbeit untersuchen wir das Potenzial von abgeschwächten Formen der Äquivalenz zur Optimierung von Schema-Abbildungen bestehend aus source-to-target tuple-generating dependencies, abgekürzt s-t tgds (dt.<br />Quelle-zu-Ziel-basierte, Tupel-generierende Abhängigkeiten), und target equality-generating dependencies, abgekürzt target egds (dt.<br />Ziel-basierte, Gleichheit-generierende Abhängigkeiten). Einerseits möchten wir das zusätzliche Optimierungspotenzial mittels abgeschwächter Formen der Äquivalenz ergründen. Andererseits betrachten wir eine Reihe von Entscheidbarkeitsfragen.<br />Insbesondere beweisen wir die Unentscheidbarkeit sowohl der Datenaustausch-Äquivalenz als auch der konjunktiven Abfrageäquivalenz für Schema-Abbildungen basierend auf s-t tgds und target egds. Außerdem zeigen wir für eine große Klasse von Optimalitätskriterien, dass die abgeschwächten Formen der Äquivalenz kein zusätzliches Optimierungspotenzial für die s-t tgds bieten. Im Gegensatz dazu beweisen wir, dass die target egds unter abgeschwächten Formen der Äquivalenz sehr wohl zusätzliches Optimierungspotenzial bieten, die gebräuchlichsten Optimierungsaufgaben allerdings unentscheidbar sind.<br />

Schema mappings play an important role in several areas of database research -- above all in data integration and data exchange.<br />The foundation of optimizing schema mappings has been laid in a recent paper by Fagin et al., where new concepts of "equivalence" between two schema mappings have been introduced, namely data exchange equivalence and conjunctive query equivalence. These are natural relaxations of logical equivalence. Fagin et al. proved several important properties of these relaxed notions of equivalence, which clearly demonstrated the potential of these notions in optimizing various kinds of schema mappings.<br />In this work, we investigate the potential of the relaxed notions of equivalence in optimizing schema mappings that consist of source-to-target tuple-generating dependencies (s-t tgds) and target equality-generating dependencies (target egds). On the one hand, we want to clarify if the relaxed notions of equivalence allow for additional optimization possibilities compared with logical equivalence. On the other hand, we also analyze several decidability questions.<br />In particular, we prove that both data-exchange equivalence and conjunctive-query equivalence are undecidable for schema mappings based on s-t tgds and target egds. We also show that for a broad class of optimality criteria, optimizing the s-t tgds does not give us additional power compared to logical equivalence. In contrast, we do gain power for optimizing the target egds by using the relaxed notions of equivalence, but the most common optimization tasks are undecidable.<br />