Title: Implementing core computation for data exchange
Language: English
Authors: Savenkov, Vadim
Qualification level: Diploma
Keywords: Datenaustausch/Datentransfer/Kern/Kernberechnung/Relationalen Datenbanksystemen
Heterogenous Databases/Data Exchange/Relational Databases/Core/Core/Data Translation/Data Mapping
Advisor: Pichler, Reinhard 
Issue Date: 2007
Number of Pages: 67
Qualification level: Diploma
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.
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.
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.
Außerdem wurde im Rahmen dieser Arbeit der veresserte Algorithmus implementiert. Die Diplomarbeit enthält auch eine Beschreibung der Implementierung sowie erste experimentelle Resultate.

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.
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.
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-17263
http://hdl.handle.net/20.500.12708/10825
Library ID: AC05035741
Organisation: E184 - Institut für Informationssysteme 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:

File Description SizeFormat
Implementing core computation for data exchange.pdf882.33 kBAdobe PDFThumbnail
 View/Open
Show full item record

Page view(s)

11
checked on Feb 21, 2021

Download(s)

57
checked on Feb 21, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.