[Back]

F. Wagner:
"Analyse von Redundanzen beim Datenaustausch";
Supervisor: R. Pichler, V. Savenkov; Institut für Informationssysteme, Arbeitsbereich Datenbanken & Artificial Intelligence, 2009; final examination: 07-2009.

Data Exchange tries to transfer data from a source schema as accurate as possible into a target schema. There may be a lot of solutions. Among these the smallest solution, that is called core, should be stored in the target database. Current solutions compute a universal solution and from that the core. Even though the algorithms have polynomial runtime, dealing with large databases becomes extremely expensive. Pichler and Savenkov have developed a new method to compute the core directly from a source database. This is done by analyzing and optimazing the dependencies. This thesis implements the analysis of the dependencies in Java and generates new versions of dependencies. The new generated dependencies are essential for developing a Algorithm that directly computes the core.
Anaylzing the dependencies is very expensive, but has to be done only once. Thus the new moethod is more suitible for large databases. The thesis also deals with main aspects of data exchange and the old method for computing the core.

Beim Datenaustausch (data exchange) wird versucht, die Daten eines Quellschemas möglichst adäquat in Daten eines Zielschemas zu überführen. Als Lösung gibt es viele Möglichkeiten, wobei die Kompakteste aller Lösungen Kern (core) genannt wird und in der Zieldatenbank gespeichert werden sollte. Bisherige Lösungen berechnen zuerst eine allgemeine Lösung und aus dieser den Kern. Die besten dieser Algorithmen, sind trotz polynomieller Laufzeit bei großen Datenbeständen nicht mehr sinnvoll verwendbar. Um auch bei großen Datenbanken den Kern in akzeptabler Zeit berechnen zu können, haben Pichler und Savenkov einen neuen Ansatz entwickelt, der den Kern ohne den Umweg einer allgemeinen Lösung berechnen kann. Dazu wird das Zusammenspiel alle Abhängigkeiten zwischen Quelle und Ziel untersucht und die Abhängigkeiten gegebenenfalls abgeändert. Darauf aufbauend kann der Kern direkt berechnet werden. Die Diplomarbeit verfolgt das Ziel, die Analyse von Abhängigkeiten in Java zu implementieren und als Ergebnis abgeänderte Abhängigkeiten zu liefern. Dies macht es möglich, einen Algorithmus zu entwickeln, der den Kern direkt berechnen kann. Trotz einer einmal notwendigen aufwändigen Untersuchung der Abhängigkeiten ist der neue Ansatz für große Datenmengen besser geeignet als der bisherige.
Neben der Implementierung besteht die Diplomarbeit auch aus einer Betrachtung wesentlicher Grundlagen des Datenaustausches und dem bisherigen Ansatz zur Berechnung von Kernen.

data exchange / chase / dependencies / core computation / universal solution / dependency analysis