Foundational aspects of schema mapping optimization and normalization

Abstract

Schemaabbildungen sind ein grundlegendes Konzept in Datenintegration und Datenaustausch, welches die Beziehung zwischen zwei Datenbankschemas beschreibt. Schemaabbildungen können als deklarative Programme verstanden werden, die entweder Daten von einem Schema in ein anderes transferieren, oder eine Abfrage über einem Schema in eine Abfrage über einem anderem Schema übersetzen. Der erste Teil dieser Arbeit beschäftigt sich mit der Frage der Optimierung und Normalisierung von Schemaabbildungen bezüglich logischer Äquivalenz. Für Schemaabbildungen, definiert durch sogenannte "embedded dependencies", formulieren wir konkrete Optimalitätskriterien und definieren ein System von Transformationsregeln, das eine als sogenannte Quelle-zu-Ziel Beziehungen gegebene Abbildung in eine optimale Darstellung überführt. Wir beweisen, dass das Ergebnis der Anwendung dieser Transformationsregeln eindeutig ist. Dieses Resultat ist dann für Schemaabbildungen erweitert, welche zusätzlich Gleichheit erzeugende Abhängigkeiten auf dem Ziel-Schema erlauben. Der zweite Teil der Arbeit betrachtet weniger strenge Äquivalenzbegriffe, wie sie von Fagin et al. definiert wurden, nämlich Datenaustauschäquivalenz (DE-Äquivalenz) und Äquivalenz bezüglich konjunktiver Abfragen (CQ-Äquivalenz). Es ist bekannt, dass die gelockerten Äquivalenzbegriffe im Allgemeinen unentscheidbar sind, wenn diese Ziel-Bedingungen nicht fixiert sind. Für CQ-Äquivalenz gilt dies sogar für den Fall dass diese Bedingungen nur Schlüssel sind. Wir identifizieren eine praktisch relevante Klasse von Ziel-Bedingungen, die sowohl die Funktionalen- als auch Inklusionsabhängigkeiten beinhaltet.<br />Für diese ist DE-Äquivalenz entscheidbar, und darüber hinaus bietet sie zusätzliches Optimierungspotential gegenüber logischer Äquivalenz.<br />Abschließend betrachten wir das Problem SO-Abbildungen ("SO-tgds") auf CQ-Äquivalenz zu überprüfen. Wir zeigen, dass dieses Problem unter der realistischen Annahme, dass das Quell-Schema Schlüssel besitzt, unentscheidbar ist.<br />

Schema mappings represent a basic concept of data integration and data exchange, expressing the relationship between database schemas.<br />They can be seen as declarative programs, transforming the data from one schema to another, or rewriting the query against one schema as a query against another schema. The first part of this dissertation deals with the question of optimization and normalization of schema mappings with respect to logical equivalence. We prove that a unique normal form exists for the set of source-to-target tuple generating dependencies and that this form is unique up to isomorphism. Moreover, we extend this result by defining a normal form in presence of target equality generating dependencies and show the trade-off between uniqueness and optimality in this setting.<br />In the second part of the dissertation, we move on to relaxed notions of equivalence, proposed by Fagin et al. in 2008: namely, data exchange equivalence and conjunctive query equivalence. If no integrity constraints are defined over the target schema, these notions are known to coincide with logical equivalence. In contrast, conjunctive query equivalence becomes undecidable even in presence of target key dependencies. We identify a practically relevant class of target dependencies, including functional and inclusion dependencies, for which data exchange equivalence is decidable, and thus offers more optimization potential than logical equivalence.<br />Finally, we consider testing conjunctive query equivalence for mappings based on Second Order tuple generating dependencies and show undecidability of this task, under a realistic assumption that key dependencies are defined over the source schema.<br />