Implementing core computation for data exchange

Abstract

Datenaustausch (engl. Data exchange) beschäftigt sich mit dem Datentransfer zwischen Datenbanken mit unterschiedlichen Schemata, wobei die Quelldaten durch die Zieldaten so genau wie möglich dargestellt werden sollten. Zu einer gegebenen Quellinstanz gibt es normalerweise viele Lösungen (d.h. Zielinstanzen) für das Datenaustauschproblem. Fagin et al. gaben überzeugende Argumente, dass in vielen Fällen der "Kern" (engl. Core) als Zieldatenbank gewählt werden sollte.<br /> Der allgemeinste Algorithmus, um den Kern eines Datenaustauschproblems in polynomieller Zeit zu berechnen, ist der FindCore Algorithmus von Gottlob und Nash. Er lässt sich auf Datenaustauschprobleme anwenden, die folgende Abhängigkeiten verwenden: zwischen Quell- und Zielschema bestehen tupel-erzeugende Abhängigkeiten, und auf dem Zielschema bestehen sowohl schwach azyklische tupel-erzeugende als auch gleichheits-erzeugende Abhängigkeiten.<br />Ein wesentliches Merkmal des FindCore Algorithmus ist die Simulation der gleichheitserzeugenden Abhängigkeiten durch tupel-erzeugende Abhängigkeiten. In dieser Diplomarbeit wird eine verbesserte Version dieses Algorithmus vorgestellt, die anstelle der Simulation mittels tupel-erzeugenden Abhängigkeiten die gleichheits-erzeugenden Abhängigkeiten direkt behandelt.<br /> Außerdem wurde im Rahmen dieser Arbeit der veresserte Algorithmus implementiert. Die Diplomarbeit enthält auch eine Beschreibung der Implementierung sowie erste experimentelle Resultate.<br />

Data exchange is concerned with the transfer of data between databases with different schemas, whereby the source data should be re ected as accurately as possible by the target data. Given a source instance, there may be many solutions (i.e., target instances) to the data exchange problem. The most compact one among the most general (universal) solutions is called a core. Fagin et al. gave convincing arguments that, in many cases, the core should be the database to be materialized. The most general to-date polynomial time algorithm for core computation is the FindCore algorithm developed by Gottlob and Nash. It tackles data exchange problems where dependencies between source and target schemas are arbitrary tuple generating dependencies (TGDs), and target constraints consist of equality generating dependencies (EGDs) and weakly acyclic TGDs. One important feature of the FindCore algorithm is that the EGDs are simulated by TGDs. In this paper, we present an enhanced version of this algorithm, which includes EGDs directly in the target chase and avoids the simulation with TGDs.<br /> We have developed a prototype implementation of the enhanced algorithm. The thesis contains its description, as well as a summary of the first experimental results.