Constraint driven schema merging

Li, Xiang; Jarke, Matthias

doi:32026

Constraint driven schema merging = Constraint driven schema merging

Li, Xiang (Author)

2012

Verantwortlichkeitsangabevorgelegt von Xiang Li

ImpressumAachen : Publikationsserver der RWTH Aachen University 2012

UmfangIX, 221 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2012

Zsfassung in dt. und engl. Sprache

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Jarke, Matthias (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2012-10-23

Online
URN: urn:nbn:de:hbz:82-opus-43183
URL: https://publications.rwth-aachen.de/record/82754/files/4318.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Schema (Genormte SW) ; Abfrage (Genormte SW) ; Datenintegration (Genormte SW) ; Sichtenkonzept (Genormte SW) ; Minimierung (Genormte SW) ; Informatik (frei) ; schema integration (frei) ; schema merging (frei) ; minimization (frei) ; data integration (frei) ; schema mappings (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Schemaintegration ist das Zusammenführen von einer Menge von Quellschemata in ein einheitliches, integriertes Schema, damit man auf Informationen aus unterschiedlichen Datenquellen über das integrierte Schema einheitlich zugreifen kann. Schemaintegration ist in vielen Szenarien notwendig, z.B. Datenintegration, logischer Datenbankentwurf, Data-Warehouse-Systeme und Schemaevolution. Damit das integrierte Schema für den Austausch von Daten genutzt werden kann, müssen die Datentransformationen zwischen Quellschemata und integriertem Schema formal in Mappings definiert werden. Bisherige Ansätze sind vor allem in zwei Aspekten eingeschränkt. Erstens ist die Erkennung von Beziehungen zwischen Schemata (Schema Matching) oft vermischt mit dem Prozess der Zusammenführung und Restrukturierung der Schemata (Schema Merging). Trotzdem haben sich Schema Matching und Schema Merging als zwei unabhängige Forschungsbereiche weiterentwickelt. Zweitens werden Mappings als konzeptuelle Beziehungen zwischen Entitätstypen oder als syntaktische Korrespondenzen zwischen Attributen dargestellt. Keine dieser beiden Mapping-Sprachen kann komplexe Beziehungen zwischen mehreren Modellierungskonstrukten ausdrücken. Logischen Mapping-Sprachen in der Form von Datenabhaengigkeiten können diese komplexen Beziehungen darstellen, jedoch wurden diese Sprachen für die Schemaintegration bisher nur selten eingsetzt. In dieser Arbeit stellen wir einen neuen Ansatz für das Zusammenführen von Schemata mit logischen Mappings, insbesondere Tuple-Generating Dependencies (TGDs) und Equality-Generating Dependencies (EGDs), vor. Wir stellen eine wohlbegründete Semantik für die Schemaintegration in zwei Szenarien vor: Datenintegration und View-Integration. Basierend auf der formalen Beschreibung des Schema-Merging-Problems entwickeln wir ein Schema-Minimierungsverfahren, das minimale, integriete Schemata generiert, die die gleiche Menge von Anfragen beantworten können wie die Quellschemata. Des Weiteren untersuchen wir die Komplexität der vorgeschlagenen Algorithmen und zeigen, dass das Schema-Minimierungsproblem hartnäckig im allgemeinen Fall ist. Jedoch haben wir syntaktische Einschränkungen auf den Eingabe-Mappings identifiziert, die sicherstellen, dass die vorgestellten Algorithmen zu PTIME gehören. Darüber hinaus haben wir die Algorithmen in einem Prototyp implementiert. Die Evaluierung mit realen und generierten Testfällen zeigt die Anwendbarkeit und Skalierbarkeit des Ansatzes.

Schema integration is the process of consolidating several source schemas to generate a unified view, called the mediated schema, so that information scattered in the sources can be served uniformly from the mediated schema. Schema integration occurs in many scenarios such as data integration, logical database design, data warehousing and schema evolution. To make the mediated schema useful for data interoperability tasks, mappings between the source schemas and the mediated schema have to be derived. Previous approaches fall short in two aspects. First, the identification of inter-schema relationships (i.e., schema matching) is usually mixed with the process of combining and restructuring schemas (i.e., schema merging). The coupling of schema matching and schema merging results in increased complexities and human interventions in the schema integration process. Second, the schema mappings are either conceptual alignments between entity types or syntactical correspondences between attributes. Neither of the two mapping languages is able to express complex relationships among several modeling constructs. Logical schema mappings in the form of data dependencies are able express such complex relationships but are less explored for schema merging. In this thesis, we propose a new approach to schema merging using logical schema mappings, more specifically tuple-generating dependencies(tgds) and equality-generating dependencies (egds). We provide well founded semantics of schema merging under two scenarios: view integration and data integration. Based on the formal characterization of the schema merging problem, we develop a schema minimization approach which generates minimal mediated schemas with the same query answering capacity as the source schemas. We study the complexity of the proposed algorithms and show that the schema minimization problems are intractable in the general case. However, we have identified syntactical constraints on the input mappings which ensure that the proposed algorithms are in PTIME. In addition, we have implemented the schema merging algorithms in a prototype. The evaluation on real world and synthetic data sets shows the applicability and scalability of the approach.

Fulltext:
PDF