Strukturanalyse

Strukturanalyse

Strukturanalyse

Strukturanalyse

Strukturanalyse

Strukturanalyse

Aufgrund des subjektiven Architekturansatzes werden kaum auf einem Gebiet exakt passende Strukturen zu finden sein. Die Identifizierung und Nutzung semantischer Korrespondenzen zwischen den Elementen zweier Schemata wird mit „Schema-Alignment“ bezeichnet und gilt es in einer Vielzahl von Anwendungen zu lösen. Im Bereich der Daten-Integrationen sowie XML-Message-Mapping in heterogenen Systemen beispielsweise vorgefunden, kommen Struktur-Analysen bei e-Commerce- oder Data-Warehousing-Applicationen stark zum Einsatz. Oftmals werden dabei diese Mapping-Aufgaben noch manuell (händisch) mit teilweiser graphischer Unterstützung erledigt, was nicht nur zeitaufwendig sondern mit zunehmender Anzahl unterschiedlicher Schemata ansteigend unpraktikabel ist.

Unterschiede in Schemata können sowohl auf einer sprachlichen als auch auf der Bedeutungsebene auftreten.

So können sich sprachliche Ausdrücke

• gegenseitig verneinen,
• Schnittmengen bilden,
• Vereinigungen (Oberbegriff), aber auch
• Disjunktionen

darstellen.

Auf Bedeutungsebene kann beispielsweise

• ein Term unterschiedliche Konzepte beschreiben
• ebenso verschiedene Terme beschreiben unterschiedliche Konzepte
• gleiche Terme unterschiedliche Konzepte beschreiben
• verschiedene Modellierungsparadigmen gelten
• verschiedene Modellierungskonventionen gelten
• ein abweichender Granularitätslevel auftreten
• verschiedene Abdeckung oder
• unterschiedliche Standpunkte vertreten werden.

[Noy05] nennt für die automatische Alternative der Strukturvereinigung die Herangehensweisen „Mapping“, „Artikulation“ und „Merging“.

Das Ziel des Mappings ist es, für die Abbildung gegeneinander ein Dokument als Adapter anzulegen. Es beinhaltet Elemente, welche die Symbole des einen Alphabetes mit denen des zweiten Alphabets verknüpfen.

Diese Mapping-Elemente sind hierbei jeweils 5-Tupel (id, e, e',R,n) mit

• dem uniquen Identifier des gegebenen Mapping-Elements <var>id</var>
• e und e', den Entitätsklassen (also z.B., XML-Elemente, Klassen)
• Rals Relation zwischen e und e' (z.B. Gleichheit , Generalisierung , Disjunktion)
• n als Vertrauensmessung in einer mathematischen Struktur (typischerweise zwischen [0,1])

Eine Angleichung A ist damit eine Menge von Mapping-Elementen, welche von zwei Schemata abhängt. Sie besitzt einige Multiplizitäten (1-1, 1-*, etc.) sowie einige andere Eigenschaften.

Da dabei nicht-übereinstimmende Aspekte leicht verloren gehen, kann diese Mapping gemeinsam mit den beiden Originaldokumenten präsentiert werden. Strukturen die in allgemeineren Wegen als durch binär ausdrückbare Gemeinsamkeiten miteinander in Beziehungen stehen, so zum Beispiel durch Relationen anstatt von Funktionen, wie es bei Ontologien gegeben ist, können gemeinsam mit einem gemappten Grundübereinstimmungsdokument präsentiert werden, Artikulation genannt.

Beim Merging wir auf Grundlage aller beteiligter Quellen eine komplett neue Struktur erstellt, welche die Instanzen beider zusammenführt.

Zur Analyse von Strukturen werden in [VLDBJ2001] folgende Betrachtungsaspekte genannt:

Schema-Matching betrachtet das Schema einer Struktur und versucht auf Grundlage der Eigenschaften von Schema-Elementen, wie deren Name, deren Beschreibungstext, deren Beziehungentypen zu anderen Elementen (Is-a oder Sub-/Supkonzept-Eigenschaften) sowie gegebenen Constraints jeweils Übereinstimmungen in beiden Basen zu finden.

Bei Datensammlungen, welche nur in limitierter Weise nützliche Schema-Informationen enthalten, seien dies semistrukturierten Daten in Form von HTML-Seiten, gibt Instanzenwissen wichtige Einblicke in den Inhalt und die Bedeutung von einzelnen Schemaelementen. Im Extremfall ist keinerlei Schema vorgegeben und muss von den Instanzendaten manuell oder automatisch erstellt werden. Dabei kommen oftmals die im Kapitel "Inhaltsintegration" ausführlich behandelten Datenharmonisierungstechniken zum Einsatz.

Aber auch bei vorhandenen Schemata kann Instanzensichtung wichtig sein, um abweichende Interpretationen der Schema-Informationen aufzudecken. Falls bei einem solchem Matching beispielsweise zwei Schema-Zuweisungen gleiche Wahrscheinlichkeit besitzten, kann auf das Element mit höherer Übereinstimmung in den Instanzen zurückgegriffen werden.

Im Idealfall eines Matchings besitzen alle Elemente eines Schemas mit Ihnen identische Elemente des zweiten Schemas auf der selben Hierarchie-Ebene. Beide unterscheiden sich hierbei lediglich durch abweichende Schema-Bezeichnungen wie „Adresse.ZIP“ und „Adresse.PLZ“. Oftmals wird diese feinste Granularität über die Attribute jedoch nicht erreicht, und Informationseinheiten überlappen einander oder sind in verschiedenen Sub- oder Subkonzepten vertreten.

Beispielsweise kann in einem Schema Postleitzahl und Ort in einem Attribut zusammengefasst sein. Besitzen nun beide Schemata nur eine bestimmte Schnittmenge gemeinsamer Informationen, wird nur eine partielle strukturelle Übereinstimmung gesucht.

Element-Level-Matcher sind auf eine Ebene beschränkt, während Struktur-Matcher darüber- und darunterliegende Konzepte ebenso als zur Struktur gehörig betrachten, um darin gemeinsame Schnittpunkte zu finden.

Im Gegensatz zu einem Struktur-Matcher ignoriert ein Elementmatcher bestehende SubKonzepte. Er ist jedoch auch nicht auf das Atomare Level beschränkt, sondern kann auch auf grobkörnigere, höhere nicht-atomare Elemente angewendet werden, jedoch nur in einer Hierarchieebene arbeitend. Er nutzen eine Vielzahl der in der relationalen Datenbank-Bearbeitung genutzen Methoden (siehe Datenharmonisierung), und wendet diese auf Elementnamen, Beschreibung oder Datentyp des einzelnen Schema-Elementes an.

Ein Element eines Schemas S1 kann Ähnlichkeiten zu einem oder mehreren Elementen des Schemas S2 besitzen. Ebenso kann umgekehrt ein Element aus S2 mehrere Vertreter aus S1 haben. Es sind demnach beim Struktumatching gewöhnliche Beziehungsrelationen (1:1), mengenorientierte Fälle (1:n bzw. n:1) bis hin zu n:m – Relationen denkbar, jeweils entweder auf eine globale Kardinalität zwischen verschiedenen Mapping-Elementen oder einer lokalen Kardinalität zu einem individuellen Mapping-Element. Element-Level Matching ist meist auf eine lokale Kardinalität von 1:1, 1:n und n:1 beschränkt. n:m – Ergebnisse erfordern in jeden Fall eine zusätzliche Strukturmatching-Analyse (siehe Kapitel 2.2.2)

Die linguistische Annäherung wird zunächst in Form der Namensübereinstimmung verwendet. Damit kann ein gleicher Name, ein gleicher Name in kanonischer Sicht, aber auch gleiche Synonyme gemeint sein. Ebenso können zwei Bezeichner einen gemeinsamen Oberbegriff (Hypernym, bspw. in Form einer Inklusions-Beziehung („is-a“)) teilen, oder auf Zeichenebene Ähnlichkeiten besitzen. Domänenabhängig kann vom Nutzer auch eine Ersetzungsliste geliefert werden. Weitere Vorgehen in diesem Bereich werden im Kapitel "Onthologien" und "Zeichenmetriken" vorgestellt.

Da oftmals in Schemata Kommentare und Beschreibungstexte in natürlicher Sprache die gewünschte Semantik der Schemaelemente ausdrücken, können hierin ebenfalls Schlüsselwörter extrahiert werden.

Constraint-basierte Untersuchung beinhaltet den Vergleich zweier Elemente auf gleiche/ähnliche Datentypen, Wertebereiche, Beziehungstypen, Kardinalitäten oder etwaige Optionalität.

Weiterhin kann ihre Eigenschaft als Schlüsselcharakter (unique, Primär-, Fremdschlüssel) genutzt werden. Eine alleinige Nutzung dieser Methode würde zu falschen Übereinstimmungen führen, aber als unterstützendes Element ist die constraintbasierte Untersuchung sehr hilfreich.

Meist werden zusätzlich zu den oben genannten Faktoren noch externe Quellen wie Wörterbücher und Thesauri-Lexika für Stemming, Synonym-Identifizierungen und somit der Auflösung von Verklemmungen genutzt werden. Ebenfalls kann man bereits bestehende Matchings anderer Strukturen mit der gleichen Domäne verwenden, um eine mögliche Ausrichtung besser erahnen zu können.

[Studer05] gibt in Bezug auf das „OntologyAlignment“ einen grundsätzlich erkennbaren Ablauf einer Strukturanalysen vor, auf den sich [Meh05] genauer bezieht und ihn an diversen Systemen zeigt. Da Ontologien eine spezialisierte Struktur darstellen, ist das Ontology-Alignment eine Unterform der Struktur-Analyse und kann auf alle übrigen XML-Strukturen Anwendung finden.

Zwei Schemas aufeinander abzubilden bedeutet hierin, dass für jede Entität (Begriff, Relation, Instanz) des ersten Schemas die Entsprechung mit derselben Bedeutung im zweiten Schema gesucht wird. Es wird die 5-Tupel- Funktion align auf einem Vokabular E aller Entitäten $e\in E$ , d.h. Begriffe, Relationen und Instanzen und der Menge möglicher Schemata S als partielle Funktion $\begin{array}{}\text{align}:E\times O\times O\to E,\text{mit}\forall e\in E_{O_1}\exists f\in E_{O_2},O_{\mathrm{1,}}{O}_2\in O:\text{align}(e,O_{\mathrm{1,}}{O}_2)=f\vee \text{align}(e,O_{\mathrm{1,}}{O}_2)=\downarrow \end{array}$ angewendet.

1.Merkmalskonstruktion

In diesem Schritt werden die Merkmale einer Entität ausgewählt, welche sie treffend beschreiben. Dies kann ein lexikalischer Eintrag einer Entität sein, aber auch eine intensionale Struktureigenschaft wie die is-a Beziehung.Desweiteren werden extensionale Beschreibungen genutzt

2.Suchraumbestimmung

Zur Ableitung von Abbildungen in Strukturen wird ein Suchraum von Kandidaten aufgestellt. Ähnlich einer Blockingmethode stellt diese sinnvolle Kandidaten für einen Vergleich auf und sortiert alle übrigen somit aus.

3.Ähnlichkeitsberechnung

Hier werden die im Kapitel Datenharmonisierung vorgestellten Methoden, ebenso wie Ähnlichkeitsfunktionen für Einzelobjekte oder Objektmengen genutzt, um die Ähnlichkeit zweier Entitäten zu bestimmen.

4.Ähnlichkeitsaufsummierung

Im Allgemeinen werden dabei mehrere Ähnlichkeitswerte für ein Entitätenpaar errechnet, beispielsweise auf lexikalische Einträge oder Ähnlichkeit der Relationen zu anderen Entitäten. Es entspricht der in Kapitel Klassifikation näher vorgestellten Klassifikation.

5.Interpretation

Die Aufsummierten Ähnlichkeitswerte werden nun zur Abbildung der Entitäten aufeinander genutzt. Möglichkeiten dafür sind ein Schwellenwert, eine Mischung aus Struktur und Ähnlichkeitswerten oder Relaxation Labelling, welches Letztere mit weiteren Heuristiken mischt [semanticIntegration_glue]

6.Iteration

Um die Struktur des Schemas besser zu nutzen, wiederholt ein Algorithmus die beschriebenen Schritte.

Die grundsätzlichen Algorithmen der Stufen 2 bis 5 finden analog bei der Datenharmonisierung Anwendung, welche im Kapitel 3 näher vorgestellt wird. Jeder dieser 6 Schritte besitzt natürlich selbst eigene spezifische Methoden mit jeweils entsprechenden zu setzenden Parametern.

Eine Vielzahl von Applikationen und Frameworks haben dieses Vorgehen bereits fest umgesetzt. Es wird dabei oftmals zwischen Individual und kombinatorischen Systemen unterschieden. Während ersterer sich auf einen Algorithmus konzentriert, verwenden die Vertreter der zweiten Gruppe mehrere Algorithmen und gewichten die Teilergebnisse.

Grundsätzlich verwendete Methoden sind

• Heuristisch und Regelbasierte Methoden
• Graphenanalyse
• Maschinen-Lernen-Statistiken
• Probalistische Annäherung
• Reasoning

Es soll nun Auswahl aktueller, aussichtsreicher Vertreter folgen. Diese werden in [Meh05], [Cupid01] und [ChiunchigliaEtAl'04] näher evaluierter.

„Seamless Moell Integration“ als instanzbasiertes System assoziiert Attribute in beiden Schemen mit Treffer-Signaturen. Diese bestehen aus 15 constraint-basierenden und 5 content-basierenden Kriterien, welche von den Instanz-Werten abgeleitet und auf [0,1] normalisiert werden, so daß jedes Kriterium einen Wert in einem 20-dimensionalen Vektorraum einnimmt. Diese werden auf Grundlage ihrer Euklid-Distanz geclustert und ein neuronales Netz mit Ihnen trainiert, welches auf das zweite Schema angewendet wird. Hierbei handelt es sich um einen hybriden Elementlevel-Matcher, welcher die Schemastruktur nicht beachtet. [Cupid01]. Semint ist einer der ersten Anläufe, keine hartkodierten Kombinationen von individuellen regelbasierten Ähnlichkeiten zu nutzen, sondern statdessen einen auf Maschinenlernbarkeit basierenden Ansatz zu wählen, besitzt jedoch kein namens- bzw. graphenbasiertes Matching.

Dike ermittelt Synonym- und Inklusions-Beziehungen (is-a) eines EntityRelationship-Schemas. Objekte werden als ähnlich markiert, falls die damit verknüpften Attribute ähnlich sind. Als Ergebnis auf zwei ER-Schemata werden die Wahrscheinlichkeitswerte zwischen beiden, gemeinsam mit Synonymen und Inklusionen ausgegeben.

Cupid ist ein Mehrzweck-Schemamatcher, welcher mit hybriden Verfahren arbeitet. Er funktioniert sowohl element- als auch strukturbasiert, spezialisiert sich jedoch auf Ähnlichkeiten von atomaren Elementen, da dort viele Schemasemantiken aufzufinden sind. Laut [Cupid01] werden ebenso interne Strukturen erkundet, wobei deren Differenzen nur gering in die Gesamtklassifizierung einfließen. Der Gesamtablauf ist in 3 Stufen gegliedert, wobei im ersten Schritt Elemente (Knoten des Schemas) auf linguistische Eigenschaften verglichen werden, inklusive externen Abgleich von Synonymen. Für den zweiten Schritt, den strukturellen Ablauf, wird das Datamodell in eine Baumstruktur transformiert und Paare daraufhin anhand ihrer Blattknoten verglichen. Ein Ähnlichkeit wird durch den gewichteten Abgleich zwischen linguistischem und strukturellem Ergebnis ermittelt. In der dritten Phase entscheidet der Schwellwert (Threshold) über Übereinstimmung. Dieser Wert ist domänenabhängig und kann nicht im Voraus angegeben werden.

„Combination of Matching-Algorithms“ nutzt einen direkten, azyklischen Graphen, und arbeitet semiautomatisch mit Hilfe von User-Feedback. COMA befolgt ebenfalls einen Kompositions-Ansatz, welcher eine erweiterbare Bibliothek von verschiedenen Matchern zur Verfügung stellt und eine Vielzahl von Kombination der ermittelten Matching-Ergebnisse unterstützt. Hier finden ebenfalls zuvor errechnete Resultate wiederverwendung. Die Kompositionsstrategien adressieren verschiedene Aspekte des Matching-Prozesses, so z.B. die Aggregation von Matcher-spezifischen Ergebnissen und Match-Kandidaten-Auswahl. Schemata werden auch hier in gerichtete direkte azyklische Graphen transformiert, auf denen alle Algorithmen arbeiten. Jedes Schema ist unique identifiziert durch seinen kompletten Pfad von der Quelle des Schemengraphes bis zum korrepsondierenden Knoten.

COMA erzeugt auf Elementebene Übereinstimmungen von 1:1 lokaler und m:n globaler Kardinalität. Der Alignment-Prozess besteht auch hier aus 3 Phasen, die iterativ durchlaufen werden und wobei die erste stets eine User-Feedback-Dialog zum Einstellen verschiedener Parameter darstellt (e.g. Auswahl des entsprechenden Matchers/Annahme, Ablehnung eines entsprechenden Entwurfes.). Daraufhin werden die individuellen Ähnlichkeiten berechnet. Diese basieren meist auf linguistischen Informationen, nutzen ebenso im Hintergrund Wörterbücher und strukturelle Elemente as Kinder oder Blätter. In der dritten Phase werden die Matcher wiederum kombiniert, entweder durch ein Maximum, einer Gewichtung einem Durchschnitt oder einer MinimumStrategie. Verschiedene Annäherungen für Schwellwert-Determinationen werden gegeben. Es ist ebenso möglich, das Programm komplett automatisch zu betreiben.

S-Match ermittelt Annäherungen, um semantische Beziehung zwischen Klassen zweier Klassifikationsschemata abzuleiten. Diese werden dazu von einer Datenbank oder Ontologie extrahiert. Sie basieren auf Untersuchung der Labels m.H. von „Wordnet“ als Synonym- Thesaurus-Überprüfung. Es sind laut [ChiunchigliaEtAl'04] ebenfalls weitere Element-Matcher vorhanden. Zusätzlich kommt hier ein SAT-Solver zum Einsatz, welcher die Schemata untersucht und dabei vor allem die Taxonomie und geschlußfolgerte Implikationen ermittelt. Er gibt entweder Gleichheit, Untermenge oder Unabhängigkeit zwischen 2 Klassen zurück.

Auf den vorangegangen Seiten wurden Methoden und Vorgehensweisen zur Identifizierung von Bestandteilen eines unbekannten Schemas vorgestellt. Fünf konkrete Beispiele aus dem universitären Umfeld, welche (semi-) automatische Umsetzungen durchführen, erlauben mit Hilfe einer Vergleichsstruktur, lokale Komponentenschemata zu erkennen.

Mit diesem Strukturwissen kann ein Abfrageterm für Xcerpt generiert werden, welcher die entsprechenden Felder der Struktur gezielt ansteuert.

Instanzen der globalen Komponente werden dadurch extrahiert und über einen global identischen Konstruktionsterm zur Verfügung gestellt.

Auf diese Instanzen kann im nächsten Kapiteln transparent zurückgegriffen werden, und deren Inhalt semantisch angeglichen sowie abschließend untereinander verknüpft werden.

Aufgrund des subjektiven Architekturansatzes werden kaum auf einem Gebiet exakt passende Strukturen zu finden sein. Die Identifizierung und Nutzung semantischer Korrespondenzen zwischen den Elementen zweier Schemata wird mit „Schema-Alignment“ bezeichnet und gilt es in einer Vielzahl von Anwendungen zu lösen. Im Bereich der Daten-Integrationen sowie XML-Message-Mapping in heterogenen Systemen beispielsweise vorgefunden, kommen Struktur-Analysen bei e-Commerce- oder Data-Warehousing-Applicationen stark zum Einsatz. Oftmals werden dabei diese Mapping-Aufgaben noch manuell (händisch) mit teilweiser graphischer Unterstützung erledigt, was nicht nur zeitaufwendig sondern mit zunehmender Anzahl unterschiedlicher Schemata ansteigend unpraktikabel ist.

Motivation

Unterschiede in Schemata können sowohl auf einer sprachlichen als auch auf der Bedeutungsebene auftreten.

So können sich sprachliche Ausdrücke

• gegenseitig verneinen,
• Schnittmengen bilden,
• Vereinigungen (Oberbegriff), aber auch
• Disjunktionen

darstellen.

Auf Bedeutungsebene kann beispielsweise

• ein Term unterschiedliche Konzepte beschreiben
• ebenso verschiedene Terme beschreiben unterschiedliche Konzepte
• gleiche Terme unterschiedliche Konzepte beschreiben
• verschiedene Modellierungsparadigmen gelten
• verschiedene Modellierungskonventionen gelten
• ein abweichender Granularitätslevel auftreten
• verschiedene Abdeckung oder
• unterschiedliche Standpunkte vertreten werden.

Ansätze

[Noy05] nennt für die automatische Alternative der Strukturvereinigung die Herangehensweisen „Mapping“, „Artikulation“ und „Merging“.

Das Ziel des Mappings ist es, für die Abbildung gegeneinander ein Dokument als Adapter anzulegen. Es beinhaltet Elemente, welche die Symbole des einen Alphabetes mit denen des zweiten Alphabets verknüpfen.

Diese Mapping-Elemente sind hierbei jeweils 5-Tupel (id, e, e',R,n) mit

• dem uniquen Identifier des gegebenen Mapping-Elements <var>id</var>
• e und e', den Entitätsklassen (also z.B., XML-Elemente, Klassen)
• Rals Relation zwischen e und e' (z.B. Gleichheit , Generalisierung , Disjunktion)
• n als Vertrauensmessung in einer mathematischen Struktur (typischerweise zwischen [0,1])

Eine Angleichung A ist damit eine Menge von Mapping-Elementen, welche von zwei Schemata abhängt. Sie besitzt einige Multiplizitäten (1-1, 1-*, etc.) sowie einige andere Eigenschaften.

Da dabei nicht-übereinstimmende Aspekte leicht verloren gehen, kann diese Mapping gemeinsam mit den beiden Originaldokumenten präsentiert werden. Strukturen die in allgemeineren Wegen als durch binär ausdrückbare Gemeinsamkeiten miteinander in Beziehungen stehen, so zum Beispiel durch Relationen anstatt von Funktionen, wie es bei Ontologien gegeben ist, können gemeinsam mit einem gemappten Grundübereinstimmungsdokument präsentiert werden, Artikulation genannt.

Beim Merging wir auf Grundlage aller beteiligter Quellen eine komplett neue Struktur erstellt, welche die Instanzen beider zusammenführt.

Betrachtungsaspekte

Zur Analyse von Strukturen werden in [VLDBJ2001] folgende Betrachtungsaspekte genannt:

Schema- und Instanzenmatching

Schema-Matching betrachtet das Schema einer Struktur und versucht auf Grundlage der Eigenschaften von Schema-Elementen, wie deren Name, deren Beschreibungstext, deren Beziehungentypen zu anderen Elementen (Is-a oder Sub-/Supkonzept-Eigenschaften) sowie gegebenen Constraints jeweils Übereinstimmungen in beiden Basen zu finden.

Bei Datensammlungen, welche nur in limitierter Weise nützliche Schema-Informationen enthalten, seien dies semistrukturierten Daten in Form von HTML-Seiten, gibt Instanzenwissen wichtige Einblicke in den Inhalt und die Bedeutung von einzelnen Schemaelementen. Im Extremfall ist keinerlei Schema vorgegeben und muss von den Instanzendaten manuell oder automatisch erstellt werden. Dabei kommen oftmals die im Kapitel "Inhaltsintegration" ausführlich behandelten Datenharmonisierungstechniken zum Einsatz.

Aber auch bei vorhandenen Schemata kann Instanzensichtung wichtig sein, um abweichende Interpretationen der Schema-Informationen aufzudecken. Falls bei einem solchem Matching beispielsweise zwei Schema-Zuweisungen gleiche Wahrscheinlichkeit besitzten, kann auf das Element mit höherer Übereinstimmung in den Instanzen zurückgegriffen werden.

Element- und Strukturmatching

Im Idealfall eines Matchings besitzen alle Elemente eines Schemas mit Ihnen identische Elemente des zweiten Schemas auf der selben Hierarchie-Ebene. Beide unterscheiden sich hierbei lediglich durch abweichende Schema-Bezeichnungen wie „Adresse.ZIP“ und „Adresse.PLZ“. Oftmals wird diese feinste Granularität über die Attribute jedoch nicht erreicht, und Informationseinheiten überlappen einander oder sind in verschiedenen Sub- oder Subkonzepten vertreten.

Beispielsweise kann in einem Schema Postleitzahl und Ort in einem Attribut zusammengefasst sein. Besitzen nun beide Schemata nur eine bestimmte Schnittmenge gemeinsamer Informationen, wird nur eine partielle strukturelle Übereinstimmung gesucht.

Element-Level-Matcher sind auf eine Ebene beschränkt, während Struktur-Matcher darüber- und darunterliegende Konzepte ebenso als zur Struktur gehörig betrachten, um darin gemeinsame Schnittpunkte zu finden.

Im Gegensatz zu einem Struktur-Matcher ignoriert ein Elementmatcher bestehende SubKonzepte. Er ist jedoch auch nicht auf das Atomare Level beschränkt, sondern kann auch auf grobkörnigere, höhere nicht-atomare Elemente angewendet werden, jedoch nur in einer Hierarchieebene arbeitend. Er nutzen eine Vielzahl der in der relationalen Datenbank-Bearbeitung genutzen Methoden (siehe Datenharmonisierung), und wendet diese auf Elementnamen, Beschreibung oder Datentyp des einzelnen Schema-Elementes an.

Matching-Kardinalität

Ein Element eines Schemas S1 kann Ähnlichkeiten zu einem oder mehreren Elementen des Schemas S2 besitzen. Ebenso kann umgekehrt ein Element aus S2 mehrere Vertreter aus S1 haben. Es sind demnach beim Struktumatching gewöhnliche Beziehungsrelationen (1:1), mengenorientierte Fälle (1:n bzw. n:1) bis hin zu n:m – Relationen denkbar, jeweils entweder auf eine globale Kardinalität zwischen verschiedenen Mapping-Elementen oder einer lokalen Kardinalität zu einem individuellen Mapping-Element. Element-Level Matching ist meist auf eine lokale Kardinalität von 1:1, 1:n und n:1 beschränkt. n:m – Ergebnisse erfordern in jeden Fall eine zusätzliche Strukturmatching-Analyse (siehe Kapitel 2.2.2)

Sprache und Constraints

Die linguistische Annäherung wird zunächst in Form der Namensübereinstimmung verwendet. Damit kann ein gleicher Name, ein gleicher Name in kanonischer Sicht, aber auch gleiche Synonyme gemeint sein. Ebenso können zwei Bezeichner einen gemeinsamen Oberbegriff (Hypernym, bspw. in Form einer Inklusions-Beziehung („is-a“)) teilen, oder auf Zeichenebene Ähnlichkeiten besitzen. Domänenabhängig kann vom Nutzer auch eine Ersetzungsliste geliefert werden. Weitere Vorgehen in diesem Bereich werden im Kapitel "Onthologien" und "Zeichenmetriken" vorgestellt.

Da oftmals in Schemata Kommentare und Beschreibungstexte in natürlicher Sprache die gewünschte Semantik der Schemaelemente ausdrücken, können hierin ebenfalls Schlüsselwörter extrahiert werden.

Constraint-basierte Untersuchung beinhaltet den Vergleich zweier Elemente auf gleiche/ähnliche Datentypen, Wertebereiche, Beziehungstypen, Kardinalitäten oder etwaige Optionalität.

Weiterhin kann ihre Eigenschaft als Schlüsselcharakter (unique, Primär-, Fremdschlüssel) genutzt werden. Eine alleinige Nutzung dieser Methode würde zu falschen Übereinstimmungen führen, aber als unterstützendes Element ist die constraintbasierte Untersuchung sehr hilfreich.

helfende Systeme

Meist werden zusätzlich zu den oben genannten Faktoren noch externe Quellen wie Wörterbücher und Thesauri-Lexika für Stemming, Synonym-Identifizierungen und somit der Auflösung von Verklemmungen genutzt werden. Ebenfalls kann man bereits bestehende Matchings anderer Strukturen mit der gleichen Domäne verwenden, um eine mögliche Ausrichtung besser erahnen zu können.

Vorgehen

[Studer05] gibt in Bezug auf das „OntologyAlignment“ einen grundsätzlich erkennbaren Ablauf einer Strukturanalysen vor, auf den sich [Meh05] genauer bezieht und ihn an diversen Systemen zeigt. Da Ontologien eine spezialisierte Struktur darstellen, ist das Ontology-Alignment eine Unterform der Struktur-Analyse und kann auf alle übrigen XML-Strukturen Anwendung finden.

Zwei Schemas aufeinander abzubilden bedeutet hierin, dass für jede Entität (Begriff, Relation, Instanz) des ersten Schemas die Entsprechung mit derselben Bedeutung im zweiten Schema gesucht wird. Es wird die 5-Tupel- Funktion align auf einem Vokabular E aller Entitäten $e\in E$ , d.h. Begriffe, Relationen und Instanzen und der Menge möglicher Schemata S als partielle Funktion $\begin{array}{}\text{align}:E\times O\times O\to E,\text{mit}\forall e\in E_{O_1}\exists f\in E_{O_2},O_{\mathrm{1,}}{O}_2\in O:\text{align}(e,O_{\mathrm{1,}}{O}_2)=f\vee \text{align}(e,O_{\mathrm{1,}}{O}_2)=\downarrow \end{array}$ angewendet.

1.Merkmalskonstruktion

In diesem Schritt werden die Merkmale einer Entität ausgewählt, welche sie treffend beschreiben. Dies kann ein lexikalischer Eintrag einer Entität sein, aber auch eine intensionale Struktureigenschaft wie die is-a Beziehung.Desweiteren werden extensionale Beschreibungen genutzt

2.Suchraumbestimmung

Zur Ableitung von Abbildungen in Strukturen wird ein Suchraum von Kandidaten aufgestellt. Ähnlich einer Blockingmethode stellt diese sinnvolle Kandidaten für einen Vergleich auf und sortiert alle übrigen somit aus.

3.Ähnlichkeitsberechnung

Hier werden die im Kapitel Datenharmonisierung vorgestellten Methoden, ebenso wie Ähnlichkeitsfunktionen für Einzelobjekte oder Objektmengen genutzt, um die Ähnlichkeit zweier Entitäten zu bestimmen.

4.Ähnlichkeitsaufsummierung

Im Allgemeinen werden dabei mehrere Ähnlichkeitswerte für ein Entitätenpaar errechnet, beispielsweise auf lexikalische Einträge oder Ähnlichkeit der Relationen zu anderen Entitäten. Es entspricht der in Kapitel Klassifikation näher vorgestellten Klassifikation.

5.Interpretation

Die Aufsummierten Ähnlichkeitswerte werden nun zur Abbildung der Entitäten aufeinander genutzt. Möglichkeiten dafür sind ein Schwellenwert, eine Mischung aus Struktur und Ähnlichkeitswerten oder Relaxation Labelling, welches Letztere mit weiteren Heuristiken mischt [semanticIntegration_glue]

6.Iteration

Um die Struktur des Schemas besser zu nutzen, wiederholt ein Algorithmus die beschriebenen Schritte.

Die grundsätzlichen Algorithmen der Stufen 2 bis 5 finden analog bei der Datenharmonisierung Anwendung, welche im Kapitel 3 näher vorgestellt wird. Jeder dieser 6 Schritte besitzt natürlich selbst eigene spezifische Methoden mit jeweils entsprechenden zu setzenden Parametern.

Beispiele

Eine Vielzahl von Applikationen und Frameworks haben dieses Vorgehen bereits fest umgesetzt. Es wird dabei oftmals zwischen Individual und kombinatorischen Systemen unterschieden. Während ersterer sich auf einen Algorithmus konzentriert, verwenden die Vertreter der zweiten Gruppe mehrere Algorithmen und gewichten die Teilergebnisse.

Grundsätzlich verwendete Methoden sind

• Heuristisch und Regelbasierte Methoden
• Graphenanalyse
• Maschinen-Lernen-Statistiken
• Probalistische Annäherung
• Reasoning

Es soll nun Auswahl aktueller, aussichtsreicher Vertreter folgen. Diese werden in [Meh05], [Cupid01] und [ChiunchigliaEtAl'04] näher evaluierter.

SemInt

„Seamless Moell Integration“ als instanzbasiertes System assoziiert Attribute in beiden Schemen mit Treffer-Signaturen. Diese bestehen aus 15 constraint-basierenden und 5 content-basierenden Kriterien, welche von den Instanz-Werten abgeleitet und auf [0,1] normalisiert werden, so daß jedes Kriterium einen Wert in einem 20-dimensionalen Vektorraum einnimmt. Diese werden auf Grundlage ihrer Euklid-Distanz geclustert und ein neuronales Netz mit Ihnen trainiert, welches auf das zweite Schema angewendet wird. Hierbei handelt es sich um einen hybriden Elementlevel-Matcher, welcher die Schemastruktur nicht beachtet. [Cupid01]. Semint ist einer der ersten Anläufe, keine hartkodierten Kombinationen von individuellen regelbasierten Ähnlichkeiten zu nutzen, sondern statdessen einen auf Maschinenlernbarkeit basierenden Ansatz zu wählen, besitzt jedoch kein namens- bzw. graphenbasiertes Matching.

Dike

Dike ermittelt Synonym- und Inklusions-Beziehungen (is-a) eines EntityRelationship-Schemas. Objekte werden als ähnlich markiert, falls die damit verknüpften Attribute ähnlich sind. Als Ergebnis auf zwei ER-Schemata werden die Wahrscheinlichkeitswerte zwischen beiden, gemeinsam mit Synonymen und Inklusionen ausgegeben.

Cupid

Cupid ist ein Mehrzweck-Schemamatcher, welcher mit hybriden Verfahren arbeitet. Er funktioniert sowohl element- als auch strukturbasiert, spezialisiert sich jedoch auf Ähnlichkeiten von atomaren Elementen, da dort viele Schemasemantiken aufzufinden sind. Laut [Cupid01] werden ebenso interne Strukturen erkundet, wobei deren Differenzen nur gering in die Gesamtklassifizierung einfließen. Der Gesamtablauf ist in 3 Stufen gegliedert, wobei im ersten Schritt Elemente (Knoten des Schemas) auf linguistische Eigenschaften verglichen werden, inklusive externen Abgleich von Synonymen. Für den zweiten Schritt, den strukturellen Ablauf, wird das Datamodell in eine Baumstruktur transformiert und Paare daraufhin anhand ihrer Blattknoten verglichen. Ein Ähnlichkeit wird durch den gewichteten Abgleich zwischen linguistischem und strukturellem Ergebnis ermittelt. In der dritten Phase entscheidet der Schwellwert (Threshold) über Übereinstimmung. Dieser Wert ist domänenabhängig und kann nicht im Voraus angegeben werden.

COMA

„Combination of Matching-Algorithms“ nutzt einen direkten, azyklischen Graphen, und arbeitet semiautomatisch mit Hilfe von User-Feedback. COMA befolgt ebenfalls einen Kompositions-Ansatz, welcher eine erweiterbare Bibliothek von verschiedenen Matchern zur Verfügung stellt und eine Vielzahl von Kombination der ermittelten Matching-Ergebnisse unterstützt. Hier finden ebenfalls zuvor errechnete Resultate wiederverwendung. Die Kompositionsstrategien adressieren verschiedene Aspekte des Matching-Prozesses, so z.B. die Aggregation von Matcher-spezifischen Ergebnissen und Match-Kandidaten-Auswahl. Schemata werden auch hier in gerichtete direkte azyklische Graphen transformiert, auf denen alle Algorithmen arbeiten. Jedes Schema ist unique identifiziert durch seinen kompletten Pfad von der Quelle des Schemengraphes bis zum korrepsondierenden Knoten.

COMA erzeugt auf Elementebene Übereinstimmungen von 1:1 lokaler und m:n globaler Kardinalität. Der Alignment-Prozess besteht auch hier aus 3 Phasen, die iterativ durchlaufen werden und wobei die erste stets eine User-Feedback-Dialog zum Einstellen verschiedener Parameter darstellt (e.g. Auswahl des entsprechenden Matchers/Annahme, Ablehnung eines entsprechenden Entwurfes.). Daraufhin werden die individuellen Ähnlichkeiten berechnet. Diese basieren meist auf linguistischen Informationen, nutzen ebenso im Hintergrund Wörterbücher und strukturelle Elemente as Kinder oder Blätter. In der dritten Phase werden die Matcher wiederum kombiniert, entweder durch ein Maximum, einer Gewichtung einem Durchschnitt oder einer MinimumStrategie. Verschiedene Annäherungen für Schwellwert-Determinationen werden gegeben. Es ist ebenso möglich, das Programm komplett automatisch zu betreiben.

CTX S-Match

S-Match ermittelt Annäherungen, um semantische Beziehung zwischen Klassen zweier Klassifikationsschemata abzuleiten. Diese werden dazu von einer Datenbank oder Ontologie extrahiert. Sie basieren auf Untersuchung der Labels m.H. von „Wordnet“ als Synonym- Thesaurus-Überprüfung. Es sind laut [ChiunchigliaEtAl'04] ebenfalls weitere Element-Matcher vorhanden. Zusätzlich kommt hier ein SAT-Solver zum Einsatz, welcher die Schemata untersucht und dabei vor allem die Taxonomie und geschlußfolgerte Implikationen ermittelt. Er gibt entweder Gleichheit, Untermenge oder Unabhängigkeit zwischen 2 Klassen zurück.

Zusammenfassung

Auf den vorangegangen Seiten wurden Methoden und Vorgehensweisen zur Identifizierung von Bestandteilen eines unbekannten Schemas vorgestellt. Fünf konkrete Beispiele aus dem universitären Umfeld, welche (semi-) automatische Umsetzungen durchführen, erlauben mit Hilfe einer Vergleichsstruktur, lokale Komponentenschemata zu erkennen.

Mit diesem Strukturwissen kann ein Abfrageterm für Xcerpt generiert werden, welcher die entsprechenden Felder der Struktur gezielt ansteuert.

Instanzen der globalen Komponente werden dadurch extrahiert und über einen global identischen Konstruktionsterm zur Verfügung gestellt.

Auf diese Instanzen kann im nächsten Kapiteln transparent zurückgegriffen werden, und deren Inhalt semantisch angeglichen sowie abschließend untereinander verknüpft werden.

Aufgrund des subjektiven Architekturansatzes werden kaum auf einem Gebiet exakt passende Strukturen zu finden sein. Die Identifizierung und Nutzung semantischer Korrespondenzen zwischen den Elementen zweier Schemata wird mit „Schema-Alignment“ bezeichnet und gilt es in einer Vielzahl von Anwendungen zu lösen. Im Bereich der Daten-Integrationen sowie XML-Message-Mapping in heterogenen Systemen beispielsweise vorgefunden, kommen Struktur-Analysen bei e-Commerce- oder Data-Warehousing-Applicationen stark zum Einsatz. Oftmals werden dabei diese Mapping-Aufgaben noch manuell (händisch) mit teilweiser graphischer Unterstützung erledigt, was nicht nur zeitaufwendig sondern mit zunehmender Anzahl unterschiedlicher Schemata ansteigend unpraktikabel ist.

Motivation

Unterschiede in Schemata können sowohl auf einer sprachlichen als auch auf der Bedeutungsebene auftreten.

So können sich sprachliche Ausdrücke

• gegenseitig verneinen,
• Schnittmengen bilden,
• Vereinigungen (Oberbegriff), aber auch
• Disjunktionen

darstellen.

Auf Bedeutungsebene kann beispielsweise

• ein Term unterschiedliche Konzepte beschreiben
• ebenso verschiedene Terme beschreiben unterschiedliche Konzepte
• gleiche Terme unterschiedliche Konzepte beschreiben
• verschiedene Modellierungsparadigmen gelten
• verschiedene Modellierungskonventionen gelten
• ein abweichender Granularitätslevel auftreten
• verschiedene Abdeckung oder
• unterschiedliche Standpunkte vertreten werden.

Ansätze

[Noy05] nennt für die automatische Alternative der Strukturvereinigung die Herangehensweisen „Mapping“, „Artikulation“ und „Merging“.

Das Ziel des Mappings ist es, für die Abbildung gegeneinander ein Dokument als Adapter anzulegen. Es beinhaltet Elemente, welche die Symbole des einen Alphabetes mit denen des zweiten Alphabets verknüpfen.

Diese Mapping-Elemente sind hierbei jeweils 5-Tupel (id, e, e',R,n) mit

• dem uniquen Identifier des gegebenen Mapping-Elements <var>id</var>
• e und e', den Entitätsklassen (also z.B., XML-Elemente, Klassen)
• Rals Relation zwischen e und e' (z.B. Gleichheit , Generalisierung , Disjunktion)
• n als Vertrauensmessung in einer mathematischen Struktur (typischerweise zwischen [0,1])

Eine Angleichung A ist damit eine Menge von Mapping-Elementen, welche von zwei Schemata abhängt. Sie besitzt einige Multiplizitäten (1-1, 1-*, etc.) sowie einige andere Eigenschaften.

Da dabei nicht-übereinstimmende Aspekte leicht verloren gehen, kann diese Mapping gemeinsam mit den beiden Originaldokumenten präsentiert werden. Strukturen die in allgemeineren Wegen als durch binär ausdrückbare Gemeinsamkeiten miteinander in Beziehungen stehen, so zum Beispiel durch Relationen anstatt von Funktionen, wie es bei Ontologien gegeben ist, können gemeinsam mit einem gemappten Grundübereinstimmungsdokument präsentiert werden, Artikulation genannt.

Beim Merging wir auf Grundlage aller beteiligter Quellen eine komplett neue Struktur erstellt, welche die Instanzen beider zusammenführt.

Betrachtungsaspekte

Zur Analyse von Strukturen werden in [VLDBJ2001] folgende Betrachtungsaspekte genannt:

Schema- und Instanzenmatching

Schema-Matching betrachtet das Schema einer Struktur und versucht auf Grundlage der Eigenschaften von Schema-Elementen, wie deren Name, deren Beschreibungstext, deren Beziehungentypen zu anderen Elementen (Is-a oder Sub-/Supkonzept-Eigenschaften) sowie gegebenen Constraints jeweils Übereinstimmungen in beiden Basen zu finden.

Bei Datensammlungen, welche nur in limitierter Weise nützliche Schema-Informationen enthalten, seien dies semistrukturierten Daten in Form von HTML-Seiten, gibt Instanzenwissen wichtige Einblicke in den Inhalt und die Bedeutung von einzelnen Schemaelementen. Im Extremfall ist keinerlei Schema vorgegeben und muss von den Instanzendaten manuell oder automatisch erstellt werden. Dabei kommen oftmals die im Kapitel "Inhaltsintegration" ausführlich behandelten Datenharmonisierungstechniken zum Einsatz.

Aber auch bei vorhandenen Schemata kann Instanzensichtung wichtig sein, um abweichende Interpretationen der Schema-Informationen aufzudecken. Falls bei einem solchem Matching beispielsweise zwei Schema-Zuweisungen gleiche Wahrscheinlichkeit besitzten, kann auf das Element mit höherer Übereinstimmung in den Instanzen zurückgegriffen werden.

Element- und Strukturmatching

Im Idealfall eines Matchings besitzen alle Elemente eines Schemas mit Ihnen identische Elemente des zweiten Schemas auf der selben Hierarchie-Ebene. Beide unterscheiden sich hierbei lediglich durch abweichende Schema-Bezeichnungen wie „Adresse.ZIP“ und „Adresse.PLZ“. Oftmals wird diese feinste Granularität über die Attribute jedoch nicht erreicht, und Informationseinheiten überlappen einander oder sind in verschiedenen Sub- oder Subkonzepten vertreten.

Beispielsweise kann in einem Schema Postleitzahl und Ort in einem Attribut zusammengefasst sein. Besitzen nun beide Schemata nur eine bestimmte Schnittmenge gemeinsamer Informationen, wird nur eine partielle strukturelle Übereinstimmung gesucht.

Element-Level-Matcher sind auf eine Ebene beschränkt, während Struktur-Matcher darüber- und darunterliegende Konzepte ebenso als zur Struktur gehörig betrachten, um darin gemeinsame Schnittpunkte zu finden.

Im Gegensatz zu einem Struktur-Matcher ignoriert ein Elementmatcher bestehende SubKonzepte. Er ist jedoch auch nicht auf das Atomare Level beschränkt, sondern kann auch auf grobkörnigere, höhere nicht-atomare Elemente angewendet werden, jedoch nur in einer Hierarchieebene arbeitend. Er nutzen eine Vielzahl der in der relationalen Datenbank-Bearbeitung genutzen Methoden (siehe Datenharmonisierung), und wendet diese auf Elementnamen, Beschreibung oder Datentyp des einzelnen Schema-Elementes an.

Matching-Kardinalität

Ein Element eines Schemas S1 kann Ähnlichkeiten zu einem oder mehreren Elementen des Schemas S2 besitzen. Ebenso kann umgekehrt ein Element aus S2 mehrere Vertreter aus S1 haben. Es sind demnach beim Struktumatching gewöhnliche Beziehungsrelationen (1:1), mengenorientierte Fälle (1:n bzw. n:1) bis hin zu n:m – Relationen denkbar, jeweils entweder auf eine globale Kardinalität zwischen verschiedenen Mapping-Elementen oder einer lokalen Kardinalität zu einem individuellen Mapping-Element. Element-Level Matching ist meist auf eine lokale Kardinalität von 1:1, 1:n und n:1 beschränkt. n:m – Ergebnisse erfordern in jeden Fall eine zusätzliche Strukturmatching-Analyse (siehe Kapitel 2.2.2)

Sprache und Constraints

Die linguistische Annäherung wird zunächst in Form der Namensübereinstimmung verwendet. Damit kann ein gleicher Name, ein gleicher Name in kanonischer Sicht, aber auch gleiche Synonyme gemeint sein. Ebenso können zwei Bezeichner einen gemeinsamen Oberbegriff (Hypernym, bspw. in Form einer Inklusions-Beziehung („is-a“)) teilen, oder auf Zeichenebene Ähnlichkeiten besitzen. Domänenabhängig kann vom Nutzer auch eine Ersetzungsliste geliefert werden. Weitere Vorgehen in diesem Bereich werden im Kapitel "Onthologien" und "Zeichenmetriken" vorgestellt.

Da oftmals in Schemata Kommentare und Beschreibungstexte in natürlicher Sprache die gewünschte Semantik der Schemaelemente ausdrücken, können hierin ebenfalls Schlüsselwörter extrahiert werden.

Constraint-basierte Untersuchung beinhaltet den Vergleich zweier Elemente auf gleiche/ähnliche Datentypen, Wertebereiche, Beziehungstypen, Kardinalitäten oder etwaige Optionalität.

Weiterhin kann ihre Eigenschaft als Schlüsselcharakter (unique, Primär-, Fremdschlüssel) genutzt werden. Eine alleinige Nutzung dieser Methode würde zu falschen Übereinstimmungen führen, aber als unterstützendes Element ist die constraintbasierte Untersuchung sehr hilfreich.

helfende Systeme

Meist werden zusätzlich zu den oben genannten Faktoren noch externe Quellen wie Wörterbücher und Thesauri-Lexika für Stemming, Synonym-Identifizierungen und somit der Auflösung von Verklemmungen genutzt werden. Ebenfalls kann man bereits bestehende Matchings anderer Strukturen mit der gleichen Domäne verwenden, um eine mögliche Ausrichtung besser erahnen zu können.

Vorgehen

[Studer05] gibt in Bezug auf das „OntologyAlignment“ einen grundsätzlich erkennbaren Ablauf einer Strukturanalysen vor, auf den sich [Meh05] genauer bezieht und ihn an diversen Systemen zeigt. Da Ontologien eine spezialisierte Struktur darstellen, ist das Ontology-Alignment eine Unterform der Struktur-Analyse und kann auf alle übrigen XML-Strukturen Anwendung finden.

Zwei Schemas aufeinander abzubilden bedeutet hierin, dass für jede Entität (Begriff, Relation, Instanz) des ersten Schemas die Entsprechung mit derselben Bedeutung im zweiten Schema gesucht wird. Es wird die 5-Tupel- Funktion align auf einem Vokabular E aller Entitäten $e\in E$ , d.h. Begriffe, Relationen und Instanzen und der Menge möglicher Schemata S als partielle Funktion $\begin{array}{}\text{align}:E\times O\times O\to E,\text{mit}\forall e\in E_{O_1}\exists f\in E_{O_2},O_{\mathrm{1,}}{O}_2\in O:\text{align}(e,O_{\mathrm{1,}}{O}_2)=f\vee \text{align}(e,O_{\mathrm{1,}}{O}_2)=\downarrow \end{array}$ angewendet.

1.Merkmalskonstruktion

In diesem Schritt werden die Merkmale einer Entität ausgewählt, welche sie treffend beschreiben. Dies kann ein lexikalischer Eintrag einer Entität sein, aber auch eine intensionale Struktureigenschaft wie die is-a Beziehung.Desweiteren werden extensionale Beschreibungen genutzt

2.Suchraumbestimmung

Zur Ableitung von Abbildungen in Strukturen wird ein Suchraum von Kandidaten aufgestellt. Ähnlich einer Blockingmethode stellt diese sinnvolle Kandidaten für einen Vergleich auf und sortiert alle übrigen somit aus.

3.Ähnlichkeitsberechnung

Hier werden die im Kapitel Datenharmonisierung vorgestellten Methoden, ebenso wie Ähnlichkeitsfunktionen für Einzelobjekte oder Objektmengen genutzt, um die Ähnlichkeit zweier Entitäten zu bestimmen.

4.Ähnlichkeitsaufsummierung

Im Allgemeinen werden dabei mehrere Ähnlichkeitswerte für ein Entitätenpaar errechnet, beispielsweise auf lexikalische Einträge oder Ähnlichkeit der Relationen zu anderen Entitäten. Es entspricht der in Kapitel Klassifikation näher vorgestellten Klassifikation.

5.Interpretation

Die Aufsummierten Ähnlichkeitswerte werden nun zur Abbildung der Entitäten aufeinander genutzt. Möglichkeiten dafür sind ein Schwellenwert, eine Mischung aus Struktur und Ähnlichkeitswerten oder Relaxation Labelling, welches Letztere mit weiteren Heuristiken mischt [semanticIntegration_glue]

6.Iteration

Um die Struktur des Schemas besser zu nutzen, wiederholt ein Algorithmus die beschriebenen Schritte.

Die grundsätzlichen Algorithmen der Stufen 2 bis 5 finden analog bei der Datenharmonisierung Anwendung, welche im Kapitel 3 näher vorgestellt wird. Jeder dieser 6 Schritte besitzt natürlich selbst eigene spezifische Methoden mit jeweils entsprechenden zu setzenden Parametern.

Beispiele

Eine Vielzahl von Applikationen und Frameworks haben dieses Vorgehen bereits fest umgesetzt. Es wird dabei oftmals zwischen Individual und kombinatorischen Systemen unterschieden. Während ersterer sich auf einen Algorithmus konzentriert, verwenden die Vertreter der zweiten Gruppe mehrere Algorithmen und gewichten die Teilergebnisse.

Grundsätzlich verwendete Methoden sind

• Heuristisch und Regelbasierte Methoden
• Graphenanalyse
• Maschinen-Lernen-Statistiken
• Probalistische Annäherung
• Reasoning

Es soll nun Auswahl aktueller, aussichtsreicher Vertreter folgen. Diese werden in [Meh05], [Cupid01] und [ChiunchigliaEtAl'04] näher evaluierter.

SemInt

„Seamless Moell Integration“ als instanzbasiertes System assoziiert Attribute in beiden Schemen mit Treffer-Signaturen. Diese bestehen aus 15 constraint-basierenden und 5 content-basierenden Kriterien, welche von den Instanz-Werten abgeleitet und auf [0,1] normalisiert werden, so daß jedes Kriterium einen Wert in einem 20-dimensionalen Vektorraum einnimmt. Diese werden auf Grundlage ihrer Euklid-Distanz geclustert und ein neuronales Netz mit Ihnen trainiert, welches auf das zweite Schema angewendet wird. Hierbei handelt es sich um einen hybriden Elementlevel-Matcher, welcher die Schemastruktur nicht beachtet. [Cupid01]. Semint ist einer der ersten Anläufe, keine hartkodierten Kombinationen von individuellen regelbasierten Ähnlichkeiten zu nutzen, sondern statdessen einen auf Maschinenlernbarkeit basierenden Ansatz zu wählen, besitzt jedoch kein namens- bzw. graphenbasiertes Matching.

Dike

Dike ermittelt Synonym- und Inklusions-Beziehungen (is-a) eines EntityRelationship-Schemas. Objekte werden als ähnlich markiert, falls die damit verknüpften Attribute ähnlich sind. Als Ergebnis auf zwei ER-Schemata werden die Wahrscheinlichkeitswerte zwischen beiden, gemeinsam mit Synonymen und Inklusionen ausgegeben.

Cupid

Cupid ist ein Mehrzweck-Schemamatcher, welcher mit hybriden Verfahren arbeitet. Er funktioniert sowohl element- als auch strukturbasiert, spezialisiert sich jedoch auf Ähnlichkeiten von atomaren Elementen, da dort viele Schemasemantiken aufzufinden sind. Laut [Cupid01] werden ebenso interne Strukturen erkundet, wobei deren Differenzen nur gering in die Gesamtklassifizierung einfließen. Der Gesamtablauf ist in 3 Stufen gegliedert, wobei im ersten Schritt Elemente (Knoten des Schemas) auf linguistische Eigenschaften verglichen werden, inklusive externen Abgleich von Synonymen. Für den zweiten Schritt, den strukturellen Ablauf, wird das Datamodell in eine Baumstruktur transformiert und Paare daraufhin anhand ihrer Blattknoten verglichen. Ein Ähnlichkeit wird durch den gewichteten Abgleich zwischen linguistischem und strukturellem Ergebnis ermittelt. In der dritten Phase entscheidet der Schwellwert (Threshold) über Übereinstimmung. Dieser Wert ist domänenabhängig und kann nicht im Voraus angegeben werden.

COMA

„Combination of Matching-Algorithms“ nutzt einen direkten, azyklischen Graphen, und arbeitet semiautomatisch mit Hilfe von User-Feedback. COMA befolgt ebenfalls einen Kompositions-Ansatz, welcher eine erweiterbare Bibliothek von verschiedenen Matchern zur Verfügung stellt und eine Vielzahl von Kombination der ermittelten Matching-Ergebnisse unterstützt. Hier finden ebenfalls zuvor errechnete Resultate wiederverwendung. Die Kompositionsstrategien adressieren verschiedene Aspekte des Matching-Prozesses, so z.B. die Aggregation von Matcher-spezifischen Ergebnissen und Match-Kandidaten-Auswahl. Schemata werden auch hier in gerichtete direkte azyklische Graphen transformiert, auf denen alle Algorithmen arbeiten. Jedes Schema ist unique identifiziert durch seinen kompletten Pfad von der Quelle des Schemengraphes bis zum korrepsondierenden Knoten.

COMA erzeugt auf Elementebene Übereinstimmungen von 1:1 lokaler und m:n globaler Kardinalität. Der Alignment-Prozess besteht auch hier aus 3 Phasen, die iterativ durchlaufen werden und wobei die erste stets eine User-Feedback-Dialog zum Einstellen verschiedener Parameter darstellt (e.g. Auswahl des entsprechenden Matchers/Annahme, Ablehnung eines entsprechenden Entwurfes.). Daraufhin werden die individuellen Ähnlichkeiten berechnet. Diese basieren meist auf linguistischen Informationen, nutzen ebenso im Hintergrund Wörterbücher und strukturelle Elemente as Kinder oder Blätter. In der dritten Phase werden die Matcher wiederum kombiniert, entweder durch ein Maximum, einer Gewichtung einem Durchschnitt oder einer MinimumStrategie. Verschiedene Annäherungen für Schwellwert-Determinationen werden gegeben. Es ist ebenso möglich, das Programm komplett automatisch zu betreiben.

CTX S-Match

S-Match ermittelt Annäherungen, um semantische Beziehung zwischen Klassen zweier Klassifikationsschemata abzuleiten. Diese werden dazu von einer Datenbank oder Ontologie extrahiert. Sie basieren auf Untersuchung der Labels m.H. von „Wordnet“ als Synonym- Thesaurus-Überprüfung. Es sind laut [ChiunchigliaEtAl'04] ebenfalls weitere Element-Matcher vorhanden. Zusätzlich kommt hier ein SAT-Solver zum Einsatz, welcher die Schemata untersucht und dabei vor allem die Taxonomie und geschlußfolgerte Implikationen ermittelt. Er gibt entweder Gleichheit, Untermenge oder Unabhängigkeit zwischen 2 Klassen zurück.

Zusammenfassung

Auf den vorangegangen Seiten wurden Methoden und Vorgehensweisen zur Identifizierung von Bestandteilen eines unbekannten Schemas vorgestellt. Fünf konkrete Beispiele aus dem universitären Umfeld, welche (semi-) automatische Umsetzungen durchführen, erlauben mit Hilfe einer Vergleichsstruktur, lokale Komponentenschemata zu erkennen.

Mit diesem Strukturwissen kann ein Abfrageterm für Xcerpt generiert werden, welcher die entsprechenden Felder der Struktur gezielt ansteuert.

Instanzen der globalen Komponente werden dadurch extrahiert und über einen global identischen Konstruktionsterm zur Verfügung gestellt.

Auf diese Instanzen kann im nächsten Kapiteln transparent zurückgegriffen werden, und deren Inhalt semantisch angeglichen sowie abschließend untereinander verknüpft werden.

Aufgrund des subjektiven Architekturansatzes werden kaum auf einem Gebiet exakt passende Strukturen zu finden sein. Die Identifizierung und Nutzung semantischer Korrespondenzen zwischen den Elementen zweier Schemata wird mit „Schema-Alignment“ bezeichnet und gilt es in einer Vielzahl von Anwendungen zu lösen. Im Bereich der Daten-Integrationen sowie XML-Message-Mapping in heterogenen Systemen beispielsweise vorgefunden, kommen Struktur-Analysen bei e-Commerce- oder Data-Warehousing-Applicationen stark zum Einsatz. Oftmals werden dabei diese Mapping-Aufgaben noch manuell (händisch) mit teilweiser graphischer Unterstützung erledigt, was nicht nur zeitaufwendig sondern mit zunehmender Anzahl unterschiedlicher Schemata ansteigend unpraktikabel ist.

Motivation

Unterschiede in Schemata können sowohl auf einer sprachlichen als auch auf der Bedeutungsebene auftreten.

So können sich sprachliche Ausdrücke

• gegenseitig verneinen,
• Schnittmengen bilden,
• Vereinigungen (Oberbegriff), aber auch
• Disjunktionen

darstellen.

Auf Bedeutungsebene kann beispielsweise

• ein Term unterschiedliche Konzepte beschreiben
• ebenso verschiedene Terme beschreiben unterschiedliche Konzepte
• gleiche Terme unterschiedliche Konzepte beschreiben
• verschiedene Modellierungsparadigmen gelten
• verschiedene Modellierungskonventionen gelten
• ein abweichender Granularitätslevel auftreten
• verschiedene Abdeckung oder
• unterschiedliche Standpunkte vertreten werden.

Ansätze

[Noy05] nennt für die automatische Alternative der Strukturvereinigung die Herangehensweisen „Mapping“, „Artikulation“ und „Merging“.

Das Ziel des Mappings ist es, für die Abbildung gegeneinander ein Dokument als Adapter anzulegen. Es beinhaltet Elemente, welche die Symbole des einen Alphabetes mit denen des zweiten Alphabets verknüpfen.

Diese Mapping-Elemente sind hierbei jeweils 5-Tupel (id, e, e',R,n) mit

• dem uniquen Identifier des gegebenen Mapping-Elements <var>id</var>
• e und e', den Entitätsklassen (also z.B., XML-Elemente, Klassen)
• Rals Relation zwischen e und e' (z.B. Gleichheit , Generalisierung , Disjunktion)
• n als Vertrauensmessung in einer mathematischen Struktur (typischerweise zwischen [0,1])

Eine Angleichung A ist damit eine Menge von Mapping-Elementen, welche von zwei Schemata abhängt. Sie besitzt einige Multiplizitäten (1-1, 1-*, etc.) sowie einige andere Eigenschaften.

Da dabei nicht-übereinstimmende Aspekte leicht verloren gehen, kann diese Mapping gemeinsam mit den beiden Originaldokumenten präsentiert werden. Strukturen die in allgemeineren Wegen als durch binär ausdrückbare Gemeinsamkeiten miteinander in Beziehungen stehen, so zum Beispiel durch Relationen anstatt von Funktionen, wie es bei Ontologien gegeben ist, können gemeinsam mit einem gemappten Grundübereinstimmungsdokument präsentiert werden, Artikulation genannt.

Beim Merging wir auf Grundlage aller beteiligter Quellen eine komplett neue Struktur erstellt, welche die Instanzen beider zusammenführt.

Betrachtungsaspekte

Zur Analyse von Strukturen werden in [VLDBJ2001] folgende Betrachtungsaspekte genannt:

Schema- und Instanzenmatching

Schema-Matching betrachtet das Schema einer Struktur und versucht auf Grundlage der Eigenschaften von Schema-Elementen, wie deren Name, deren Beschreibungstext, deren Beziehungentypen zu anderen Elementen (Is-a oder Sub-/Supkonzept-Eigenschaften) sowie gegebenen Constraints jeweils Übereinstimmungen in beiden Basen zu finden.

Bei Datensammlungen, welche nur in limitierter Weise nützliche Schema-Informationen enthalten, seien dies semistrukturierten Daten in Form von HTML-Seiten, gibt Instanzenwissen wichtige Einblicke in den Inhalt und die Bedeutung von einzelnen Schemaelementen. Im Extremfall ist keinerlei Schema vorgegeben und muss von den Instanzendaten manuell oder automatisch erstellt werden. Dabei kommen oftmals die im Kapitel "Inhaltsintegration" ausführlich behandelten Datenharmonisierungstechniken zum Einsatz.

Aber auch bei vorhandenen Schemata kann Instanzensichtung wichtig sein, um abweichende Interpretationen der Schema-Informationen aufzudecken. Falls bei einem solchem Matching beispielsweise zwei Schema-Zuweisungen gleiche Wahrscheinlichkeit besitzten, kann auf das Element mit höherer Übereinstimmung in den Instanzen zurückgegriffen werden.

Element- und Strukturmatching

Im Idealfall eines Matchings besitzen alle Elemente eines Schemas mit Ihnen identische Elemente des zweiten Schemas auf der selben Hierarchie-Ebene. Beide unterscheiden sich hierbei lediglich durch abweichende Schema-Bezeichnungen wie „Adresse.ZIP“ und „Adresse.PLZ“. Oftmals wird diese feinste Granularität über die Attribute jedoch nicht erreicht, und Informationseinheiten überlappen einander oder sind in verschiedenen Sub- oder Subkonzepten vertreten.

Beispielsweise kann in einem Schema Postleitzahl und Ort in einem Attribut zusammengefasst sein. Besitzen nun beide Schemata nur eine bestimmte Schnittmenge gemeinsamer Informationen, wird nur eine partielle strukturelle Übereinstimmung gesucht.

Element-Level-Matcher sind auf eine Ebene beschränkt, während Struktur-Matcher darüber- und darunterliegende Konzepte ebenso als zur Struktur gehörig betrachten, um darin gemeinsame Schnittpunkte zu finden.

Im Gegensatz zu einem Struktur-Matcher ignoriert ein Elementmatcher bestehende SubKonzepte. Er ist jedoch auch nicht auf das Atomare Level beschränkt, sondern kann auch auf grobkörnigere, höhere nicht-atomare Elemente angewendet werden, jedoch nur in einer Hierarchieebene arbeitend. Er nutzen eine Vielzahl der in der relationalen Datenbank-Bearbeitung genutzen Methoden (siehe Datenharmonisierung), und wendet diese auf Elementnamen, Beschreibung oder Datentyp des einzelnen Schema-Elementes an.

Matching-Kardinalität

Ein Element eines Schemas S1 kann Ähnlichkeiten zu einem oder mehreren Elementen des Schemas S2 besitzen. Ebenso kann umgekehrt ein Element aus S2 mehrere Vertreter aus S1 haben. Es sind demnach beim Struktumatching gewöhnliche Beziehungsrelationen (1:1), mengenorientierte Fälle (1:n bzw. n:1) bis hin zu n:m – Relationen denkbar, jeweils entweder auf eine globale Kardinalität zwischen verschiedenen Mapping-Elementen oder einer lokalen Kardinalität zu einem individuellen Mapping-Element. Element-Level Matching ist meist auf eine lokale Kardinalität von 1:1, 1:n und n:1 beschränkt. n:m – Ergebnisse erfordern in jeden Fall eine zusätzliche Strukturmatching-Analyse (siehe Kapitel 2.2.2)

Sprache und Constraints

Die linguistische Annäherung wird zunächst in Form der Namensübereinstimmung verwendet. Damit kann ein gleicher Name, ein gleicher Name in kanonischer Sicht, aber auch gleiche Synonyme gemeint sein. Ebenso können zwei Bezeichner einen gemeinsamen Oberbegriff (Hypernym, bspw. in Form einer Inklusions-Beziehung („is-a“)) teilen, oder auf Zeichenebene Ähnlichkeiten besitzen. Domänenabhängig kann vom Nutzer auch eine Ersetzungsliste geliefert werden. Weitere Vorgehen in diesem Bereich werden im Kapitel "Onthologien" und "Zeichenmetriken" vorgestellt.

Da oftmals in Schemata Kommentare und Beschreibungstexte in natürlicher Sprache die gewünschte Semantik der Schemaelemente ausdrücken, können hierin ebenfalls Schlüsselwörter extrahiert werden.

Constraint-basierte Untersuchung beinhaltet den Vergleich zweier Elemente auf gleiche/ähnliche Datentypen, Wertebereiche, Beziehungstypen, Kardinalitäten oder etwaige Optionalität.

Weiterhin kann ihre Eigenschaft als Schlüsselcharakter (unique, Primär-, Fremdschlüssel) genutzt werden. Eine alleinige Nutzung dieser Methode würde zu falschen Übereinstimmungen führen, aber als unterstützendes Element ist die constraintbasierte Untersuchung sehr hilfreich.

helfende Systeme

Meist werden zusätzlich zu den oben genannten Faktoren noch externe Quellen wie Wörterbücher und Thesauri-Lexika für Stemming, Synonym-Identifizierungen und somit der Auflösung von Verklemmungen genutzt werden. Ebenfalls kann man bereits bestehende Matchings anderer Strukturen mit der gleichen Domäne verwenden, um eine mögliche Ausrichtung besser erahnen zu können.

Vorgehen

[Studer05] gibt in Bezug auf das „OntologyAlignment“ einen grundsätzlich erkennbaren Ablauf einer Strukturanalysen vor, auf den sich [Meh05] genauer bezieht und ihn an diversen Systemen zeigt. Da Ontologien eine spezialisierte Struktur darstellen, ist das Ontology-Alignment eine Unterform der Struktur-Analyse und kann auf alle übrigen XML-Strukturen Anwendung finden.

Zwei Schemas aufeinander abzubilden bedeutet hierin, dass für jede Entität (Begriff, Relation, Instanz) des ersten Schemas die Entsprechung mit derselben Bedeutung im zweiten Schema gesucht wird. Es wird die 5-Tupel- Funktion align auf einem Vokabular E aller Entitäten $e\in E$ , d.h. Begriffe, Relationen und Instanzen und der Menge möglicher Schemata S als partielle Funktion $\begin{array}{}\text{align}:E\times O\times O\to E,\text{mit}\forall e\in E_{O_1}\exists f\in E_{O_2},O_{\mathrm{1,}}{O}_2\in O:\text{align}(e,O_{\mathrm{1,}}{O}_2)=f\vee \text{align}(e,O_{\mathrm{1,}}{O}_2)=\downarrow \end{array}$ angewendet.

1.Merkmalskonstruktion

In diesem Schritt werden die Merkmale einer Entität ausgewählt, welche sie treffend beschreiben. Dies kann ein lexikalischer Eintrag einer Entität sein, aber auch eine intensionale Struktureigenschaft wie die is-a Beziehung.Desweiteren werden extensionale Beschreibungen genutzt

2.Suchraumbestimmung

Zur Ableitung von Abbildungen in Strukturen wird ein Suchraum von Kandidaten aufgestellt. Ähnlich einer Blockingmethode stellt diese sinnvolle Kandidaten für einen Vergleich auf und sortiert alle übrigen somit aus.

3.Ähnlichkeitsberechnung

Hier werden die im Kapitel Datenharmonisierung vorgestellten Methoden, ebenso wie Ähnlichkeitsfunktionen für Einzelobjekte oder Objektmengen genutzt, um die Ähnlichkeit zweier Entitäten zu bestimmen.

4.Ähnlichkeitsaufsummierung

Im Allgemeinen werden dabei mehrere Ähnlichkeitswerte für ein Entitätenpaar errechnet, beispielsweise auf lexikalische Einträge oder Ähnlichkeit der Relationen zu anderen Entitäten. Es entspricht der in Kapitel Klassifikation näher vorgestellten Klassifikation.

5.Interpretation

Die Aufsummierten Ähnlichkeitswerte werden nun zur Abbildung der Entitäten aufeinander genutzt. Möglichkeiten dafür sind ein Schwellenwert, eine Mischung aus Struktur und Ähnlichkeitswerten oder Relaxation Labelling, welches Letztere mit weiteren Heuristiken mischt [semanticIntegration_glue]

6.Iteration

Um die Struktur des Schemas besser zu nutzen, wiederholt ein Algorithmus die beschriebenen Schritte.

Die grundsätzlichen Algorithmen der Stufen 2 bis 5 finden analog bei der Datenharmonisierung Anwendung, welche im Kapitel 3 näher vorgestellt wird. Jeder dieser 6 Schritte besitzt natürlich selbst eigene spezifische Methoden mit jeweils entsprechenden zu setzenden Parametern.

Beispiele

Eine Vielzahl von Applikationen und Frameworks haben dieses Vorgehen bereits fest umgesetzt. Es wird dabei oftmals zwischen Individual und kombinatorischen Systemen unterschieden. Während ersterer sich auf einen Algorithmus konzentriert, verwenden die Vertreter der zweiten Gruppe mehrere Algorithmen und gewichten die Teilergebnisse.

Grundsätzlich verwendete Methoden sind

• Heuristisch und Regelbasierte Methoden
• Graphenanalyse
• Maschinen-Lernen-Statistiken
• Probalistische Annäherung
• Reasoning

Es soll nun Auswahl aktueller, aussichtsreicher Vertreter folgen. Diese werden in [Meh05], [Cupid01] und [ChiunchigliaEtAl'04] näher evaluierter.

SemInt

„Seamless Moell Integration“ als instanzbasiertes System assoziiert Attribute in beiden Schemen mit Treffer-Signaturen. Diese bestehen aus 15 constraint-basierenden und 5 content-basierenden Kriterien, welche von den Instanz-Werten abgeleitet und auf [0,1] normalisiert werden, so daß jedes Kriterium einen Wert in einem 20-dimensionalen Vektorraum einnimmt. Diese werden auf Grundlage ihrer Euklid-Distanz geclustert und ein neuronales Netz mit Ihnen trainiert, welches auf das zweite Schema angewendet wird. Hierbei handelt es sich um einen hybriden Elementlevel-Matcher, welcher die Schemastruktur nicht beachtet. [Cupid01]. Semint ist einer der ersten Anläufe, keine hartkodierten Kombinationen von individuellen regelbasierten Ähnlichkeiten zu nutzen, sondern statdessen einen auf Maschinenlernbarkeit basierenden Ansatz zu wählen, besitzt jedoch kein namens- bzw. graphenbasiertes Matching.

Dike

Dike ermittelt Synonym- und Inklusions-Beziehungen (is-a) eines EntityRelationship-Schemas. Objekte werden als ähnlich markiert, falls die damit verknüpften Attribute ähnlich sind. Als Ergebnis auf zwei ER-Schemata werden die Wahrscheinlichkeitswerte zwischen beiden, gemeinsam mit Synonymen und Inklusionen ausgegeben.

Cupid

Cupid ist ein Mehrzweck-Schemamatcher, welcher mit hybriden Verfahren arbeitet. Er funktioniert sowohl element- als auch strukturbasiert, spezialisiert sich jedoch auf Ähnlichkeiten von atomaren Elementen, da dort viele Schemasemantiken aufzufinden sind. Laut [Cupid01] werden ebenso interne Strukturen erkundet, wobei deren Differenzen nur gering in die Gesamtklassifizierung einfließen. Der Gesamtablauf ist in 3 Stufen gegliedert, wobei im ersten Schritt Elemente (Knoten des Schemas) auf linguistische Eigenschaften verglichen werden, inklusive externen Abgleich von Synonymen. Für den zweiten Schritt, den strukturellen Ablauf, wird das Datamodell in eine Baumstruktur transformiert und Paare daraufhin anhand ihrer Blattknoten verglichen. Ein Ähnlichkeit wird durch den gewichteten Abgleich zwischen linguistischem und strukturellem Ergebnis ermittelt. In der dritten Phase entscheidet der Schwellwert (Threshold) über Übereinstimmung. Dieser Wert ist domänenabhängig und kann nicht im Voraus angegeben werden.

COMA

„Combination of Matching-Algorithms“ nutzt einen direkten, azyklischen Graphen, und arbeitet semiautomatisch mit Hilfe von User-Feedback. COMA befolgt ebenfalls einen Kompositions-Ansatz, welcher eine erweiterbare Bibliothek von verschiedenen Matchern zur Verfügung stellt und eine Vielzahl von Kombination der ermittelten Matching-Ergebnisse unterstützt. Hier finden ebenfalls zuvor errechnete Resultate wiederverwendung. Die Kompositionsstrategien adressieren verschiedene Aspekte des Matching-Prozesses, so z.B. die Aggregation von Matcher-spezifischen Ergebnissen und Match-Kandidaten-Auswahl. Schemata werden auch hier in gerichtete direkte azyklische Graphen transformiert, auf denen alle Algorithmen arbeiten. Jedes Schema ist unique identifiziert durch seinen kompletten Pfad von der Quelle des Schemengraphes bis zum korrepsondierenden Knoten.

COMA erzeugt auf Elementebene Übereinstimmungen von 1:1 lokaler und m:n globaler Kardinalität. Der Alignment-Prozess besteht auch hier aus 3 Phasen, die iterativ durchlaufen werden und wobei die erste stets eine User-Feedback-Dialog zum Einstellen verschiedener Parameter darstellt (e.g. Auswahl des entsprechenden Matchers/Annahme, Ablehnung eines entsprechenden Entwurfes.). Daraufhin werden die individuellen Ähnlichkeiten berechnet. Diese basieren meist auf linguistischen Informationen, nutzen ebenso im Hintergrund Wörterbücher und strukturelle Elemente as Kinder oder Blätter. In der dritten Phase werden die Matcher wiederum kombiniert, entweder durch ein Maximum, einer Gewichtung einem Durchschnitt oder einer MinimumStrategie. Verschiedene Annäherungen für Schwellwert-Determinationen werden gegeben. Es ist ebenso möglich, das Programm komplett automatisch zu betreiben.

CTX S-Match

S-Match ermittelt Annäherungen, um semantische Beziehung zwischen Klassen zweier Klassifikationsschemata abzuleiten. Diese werden dazu von einer Datenbank oder Ontologie extrahiert. Sie basieren auf Untersuchung der Labels m.H. von „Wordnet“ als Synonym- Thesaurus-Überprüfung. Es sind laut [ChiunchigliaEtAl'04] ebenfalls weitere Element-Matcher vorhanden. Zusätzlich kommt hier ein SAT-Solver zum Einsatz, welcher die Schemata untersucht und dabei vor allem die Taxonomie und geschlußfolgerte Implikationen ermittelt. Er gibt entweder Gleichheit, Untermenge oder Unabhängigkeit zwischen 2 Klassen zurück.

Zusammenfassung

Auf den vorangegangen Seiten wurden Methoden und Vorgehensweisen zur Identifizierung von Bestandteilen eines unbekannten Schemas vorgestellt. Fünf konkrete Beispiele aus dem universitären Umfeld, welche (semi-) automatische Umsetzungen durchführen, erlauben mit Hilfe einer Vergleichsstruktur, lokale Komponentenschemata zu erkennen.

Mit diesem Strukturwissen kann ein Abfrageterm für Xcerpt generiert werden, welcher die entsprechenden Felder der Struktur gezielt ansteuert.

Instanzen der globalen Komponente werden dadurch extrahiert und über einen global identischen Konstruktionsterm zur Verfügung gestellt.

Auf diese Instanzen kann im nächsten Kapiteln transparent zurückgegriffen werden, und deren Inhalt semantisch angeglichen sowie abschließend untereinander verknüpft werden.

Aufgrund des subjektiven Architekturansatzes werden kaum auf einem Gebiet exakt passende Strukturen zu finden sein. Die Identifizierung und Nutzung semantischer Korrespondenzen zwischen den Elementen zweier Schemata wird mit „Schema-Alignment“ bezeichnet und gilt es in einer Vielzahl von Anwendungen zu lösen. Im Bereich der Daten-Integrationen sowie XML-Message-Mapping in heterogenen Systemen beispielsweise vorgefunden, kommen Struktur-Analysen bei e-Commerce- oder Data-Warehousing-Applicationen stark zum Einsatz. Oftmals werden dabei diese Mapping-Aufgaben noch manuell (händisch) mit teilweiser graphischer Unterstützung erledigt, was nicht nur zeitaufwendig sondern mit zunehmender Anzahl unterschiedlicher Schemata ansteigend unpraktikabel ist.

Motivation

Unterschiede in Schemata können sowohl auf einer sprachlichen als auch auf der Bedeutungsebene auftreten.

So können sich sprachliche Ausdrücke

• gegenseitig verneinen,
• Schnittmengen bilden,
• Vereinigungen (Oberbegriff), aber auch
• Disjunktionen

darstellen.

Auf Bedeutungsebene kann beispielsweise

• ein Term unterschiedliche Konzepte beschreiben
• ebenso verschiedene Terme beschreiben unterschiedliche Konzepte
• gleiche Terme unterschiedliche Konzepte beschreiben
• verschiedene Modellierungsparadigmen gelten
• verschiedene Modellierungskonventionen gelten
• ein abweichender Granularitätslevel auftreten
• verschiedene Abdeckung oder
• unterschiedliche Standpunkte vertreten werden.

Ansätze

[Noy05] nennt für die automatische Alternative der Strukturvereinigung die Herangehensweisen „Mapping“, „Artikulation“ und „Merging“.

Das Ziel des Mappings ist es, für die Abbildung gegeneinander ein Dokument als Adapter anzulegen. Es beinhaltet Elemente, welche die Symbole des einen Alphabetes mit denen des zweiten Alphabets verknüpfen.

Diese Mapping-Elemente sind hierbei jeweils 5-Tupel (id, e, e',R,n) mit

• dem uniquen Identifier des gegebenen Mapping-Elements <var>id</var>
• e und e', den Entitätsklassen (also z.B., XML-Elemente, Klassen)
• Rals Relation zwischen e und e' (z.B. Gleichheit , Generalisierung , Disjunktion)
• n als Vertrauensmessung in einer mathematischen Struktur (typischerweise zwischen [0,1])

Eine Angleichung A ist damit eine Menge von Mapping-Elementen, welche von zwei Schemata abhängt. Sie besitzt einige Multiplizitäten (1-1, 1-*, etc.) sowie einige andere Eigenschaften.

Da dabei nicht-übereinstimmende Aspekte leicht verloren gehen, kann diese Mapping gemeinsam mit den beiden Originaldokumenten präsentiert werden. Strukturen die in allgemeineren Wegen als durch binär ausdrückbare Gemeinsamkeiten miteinander in Beziehungen stehen, so zum Beispiel durch Relationen anstatt von Funktionen, wie es bei Ontologien gegeben ist, können gemeinsam mit einem gemappten Grundübereinstimmungsdokument präsentiert werden, Artikulation genannt.

Beim Merging wir auf Grundlage aller beteiligter Quellen eine komplett neue Struktur erstellt, welche die Instanzen beider zusammenführt.

Betrachtungsaspekte

Zur Analyse von Strukturen werden in [VLDBJ2001] folgende Betrachtungsaspekte genannt:

Schema- und Instanzenmatching

Schema-Matching betrachtet das Schema einer Struktur und versucht auf Grundlage der Eigenschaften von Schema-Elementen, wie deren Name, deren Beschreibungstext, deren Beziehungentypen zu anderen Elementen (Is-a oder Sub-/Supkonzept-Eigenschaften) sowie gegebenen Constraints jeweils Übereinstimmungen in beiden Basen zu finden.

Bei Datensammlungen, welche nur in limitierter Weise nützliche Schema-Informationen enthalten, seien dies semistrukturierten Daten in Form von HTML-Seiten, gibt Instanzenwissen wichtige Einblicke in den Inhalt und die Bedeutung von einzelnen Schemaelementen. Im Extremfall ist keinerlei Schema vorgegeben und muss von den Instanzendaten manuell oder automatisch erstellt werden. Dabei kommen oftmals die im Kapitel "Inhaltsintegration" ausführlich behandelten Datenharmonisierungstechniken zum Einsatz.

Aber auch bei vorhandenen Schemata kann Instanzensichtung wichtig sein, um abweichende Interpretationen der Schema-Informationen aufzudecken. Falls bei einem solchem Matching beispielsweise zwei Schema-Zuweisungen gleiche Wahrscheinlichkeit besitzten, kann auf das Element mit höherer Übereinstimmung in den Instanzen zurückgegriffen werden.

Element- und Strukturmatching

Im Idealfall eines Matchings besitzen alle Elemente eines Schemas mit Ihnen identische Elemente des zweiten Schemas auf der selben Hierarchie-Ebene. Beide unterscheiden sich hierbei lediglich durch abweichende Schema-Bezeichnungen wie „Adresse.ZIP“ und „Adresse.PLZ“. Oftmals wird diese feinste Granularität über die Attribute jedoch nicht erreicht, und Informationseinheiten überlappen einander oder sind in verschiedenen Sub- oder Subkonzepten vertreten.

Beispielsweise kann in einem Schema Postleitzahl und Ort in einem Attribut zusammengefasst sein. Besitzen nun beide Schemata nur eine bestimmte Schnittmenge gemeinsamer Informationen, wird nur eine partielle strukturelle Übereinstimmung gesucht.

Element-Level-Matcher sind auf eine Ebene beschränkt, während Struktur-Matcher darüber- und darunterliegende Konzepte ebenso als zur Struktur gehörig betrachten, um darin gemeinsame Schnittpunkte zu finden.

Im Gegensatz zu einem Struktur-Matcher ignoriert ein Elementmatcher bestehende SubKonzepte. Er ist jedoch auch nicht auf das Atomare Level beschränkt, sondern kann auch auf grobkörnigere, höhere nicht-atomare Elemente angewendet werden, jedoch nur in einer Hierarchieebene arbeitend. Er nutzen eine Vielzahl der in der relationalen Datenbank-Bearbeitung genutzen Methoden (siehe Datenharmonisierung), und wendet diese auf Elementnamen, Beschreibung oder Datentyp des einzelnen Schema-Elementes an.

Matching-Kardinalität

Ein Element eines Schemas S1 kann Ähnlichkeiten zu einem oder mehreren Elementen des Schemas S2 besitzen. Ebenso kann umgekehrt ein Element aus S2 mehrere Vertreter aus S1 haben. Es sind demnach beim Struktumatching gewöhnliche Beziehungsrelationen (1:1), mengenorientierte Fälle (1:n bzw. n:1) bis hin zu n:m – Relationen denkbar, jeweils entweder auf eine globale Kardinalität zwischen verschiedenen Mapping-Elementen oder einer lokalen Kardinalität zu einem individuellen Mapping-Element. Element-Level Matching ist meist auf eine lokale Kardinalität von 1:1, 1:n und n:1 beschränkt. n:m – Ergebnisse erfordern in jeden Fall eine zusätzliche Strukturmatching-Analyse (siehe Kapitel 2.2.2)

Sprache und Constraints

Die linguistische Annäherung wird zunächst in Form der Namensübereinstimmung verwendet. Damit kann ein gleicher Name, ein gleicher Name in kanonischer Sicht, aber auch gleiche Synonyme gemeint sein. Ebenso können zwei Bezeichner einen gemeinsamen Oberbegriff (Hypernym, bspw. in Form einer Inklusions-Beziehung („is-a“)) teilen, oder auf Zeichenebene Ähnlichkeiten besitzen. Domänenabhängig kann vom Nutzer auch eine Ersetzungsliste geliefert werden. Weitere Vorgehen in diesem Bereich werden im Kapitel "Onthologien" und "Zeichenmetriken" vorgestellt.

Da oftmals in Schemata Kommentare und Beschreibungstexte in natürlicher Sprache die gewünschte Semantik der Schemaelemente ausdrücken, können hierin ebenfalls Schlüsselwörter extrahiert werden.

Constraint-basierte Untersuchung beinhaltet den Vergleich zweier Elemente auf gleiche/ähnliche Datentypen, Wertebereiche, Beziehungstypen, Kardinalitäten oder etwaige Optionalität.

Weiterhin kann ihre Eigenschaft als Schlüsselcharakter (unique, Primär-, Fremdschlüssel) genutzt werden. Eine alleinige Nutzung dieser Methode würde zu falschen Übereinstimmungen führen, aber als unterstützendes Element ist die constraintbasierte Untersuchung sehr hilfreich.

helfende Systeme

Meist werden zusätzlich zu den oben genannten Faktoren noch externe Quellen wie Wörterbücher und Thesauri-Lexika für Stemming, Synonym-Identifizierungen und somit der Auflösung von Verklemmungen genutzt werden. Ebenfalls kann man bereits bestehende Matchings anderer Strukturen mit der gleichen Domäne verwenden, um eine mögliche Ausrichtung besser erahnen zu können.

Vorgehen

[Studer05] gibt in Bezug auf das „OntologyAlignment“ einen grundsätzlich erkennbaren Ablauf einer Strukturanalysen vor, auf den sich [Meh05] genauer bezieht und ihn an diversen Systemen zeigt. Da Ontologien eine spezialisierte Struktur darstellen, ist das Ontology-Alignment eine Unterform der Struktur-Analyse und kann auf alle übrigen XML-Strukturen Anwendung finden.

Zwei Schemas aufeinander abzubilden bedeutet hierin, dass für jede Entität (Begriff, Relation, Instanz) des ersten Schemas die Entsprechung mit derselben Bedeutung im zweiten Schema gesucht wird. Es wird die 5-Tupel- Funktion align auf einem Vokabular E aller Entitäten $e\in E$ , d.h. Begriffe, Relationen und Instanzen und der Menge möglicher Schemata S als partielle Funktion $\begin{array}{}\text{align}:E\times O\times O\to E,\text{mit}\forall e\in E_{O_1}\exists f\in E_{O_2},O_{\mathrm{1,}}{O}_2\in O:\text{align}(e,O_{\mathrm{1,}}{O}_2)=f\vee \text{align}(e,O_{\mathrm{1,}}{O}_2)=\downarrow \end{array}$ angewendet.

1.Merkmalskonstruktion

In diesem Schritt werden die Merkmale einer Entität ausgewählt, welche sie treffend beschreiben. Dies kann ein lexikalischer Eintrag einer Entität sein, aber auch eine intensionale Struktureigenschaft wie die is-a Beziehung.Desweiteren werden extensionale Beschreibungen genutzt

2.Suchraumbestimmung

Zur Ableitung von Abbildungen in Strukturen wird ein Suchraum von Kandidaten aufgestellt. Ähnlich einer Blockingmethode stellt diese sinnvolle Kandidaten für einen Vergleich auf und sortiert alle übrigen somit aus.

3.Ähnlichkeitsberechnung

Hier werden die im Kapitel Datenharmonisierung vorgestellten Methoden, ebenso wie Ähnlichkeitsfunktionen für Einzelobjekte oder Objektmengen genutzt, um die Ähnlichkeit zweier Entitäten zu bestimmen.

4.Ähnlichkeitsaufsummierung

Im Allgemeinen werden dabei mehrere Ähnlichkeitswerte für ein Entitätenpaar errechnet, beispielsweise auf lexikalische Einträge oder Ähnlichkeit der Relationen zu anderen Entitäten. Es entspricht der in Kapitel Klassifikation näher vorgestellten Klassifikation.

5.Interpretation

Die Aufsummierten Ähnlichkeitswerte werden nun zur Abbildung der Entitäten aufeinander genutzt. Möglichkeiten dafür sind ein Schwellenwert, eine Mischung aus Struktur und Ähnlichkeitswerten oder Relaxation Labelling, welches Letztere mit weiteren Heuristiken mischt [semanticIntegration_glue]

6.Iteration

Um die Struktur des Schemas besser zu nutzen, wiederholt ein Algorithmus die beschriebenen Schritte.

Die grundsätzlichen Algorithmen der Stufen 2 bis 5 finden analog bei der Datenharmonisierung Anwendung, welche im Kapitel 3 näher vorgestellt wird. Jeder dieser 6 Schritte besitzt natürlich selbst eigene spezifische Methoden mit jeweils entsprechenden zu setzenden Parametern.

Beispiele

Eine Vielzahl von Applikationen und Frameworks haben dieses Vorgehen bereits fest umgesetzt. Es wird dabei oftmals zwischen Individual und kombinatorischen Systemen unterschieden. Während ersterer sich auf einen Algorithmus konzentriert, verwenden die Vertreter der zweiten Gruppe mehrere Algorithmen und gewichten die Teilergebnisse.

Grundsätzlich verwendete Methoden sind

• Heuristisch und Regelbasierte Methoden
• Graphenanalyse
• Maschinen-Lernen-Statistiken
• Probalistische Annäherung
• Reasoning

Es soll nun Auswahl aktueller, aussichtsreicher Vertreter folgen. Diese werden in [Meh05], [Cupid01] und [ChiunchigliaEtAl'04] näher evaluierter.

SemInt

„Seamless Moell Integration“ als instanzbasiertes System assoziiert Attribute in beiden Schemen mit Treffer-Signaturen. Diese bestehen aus 15 constraint-basierenden und 5 content-basierenden Kriterien, welche von den Instanz-Werten abgeleitet und auf [0,1] normalisiert werden, so daß jedes Kriterium einen Wert in einem 20-dimensionalen Vektorraum einnimmt. Diese werden auf Grundlage ihrer Euklid-Distanz geclustert und ein neuronales Netz mit Ihnen trainiert, welches auf das zweite Schema angewendet wird. Hierbei handelt es sich um einen hybriden Elementlevel-Matcher, welcher die Schemastruktur nicht beachtet. [Cupid01]. Semint ist einer der ersten Anläufe, keine hartkodierten Kombinationen von individuellen regelbasierten Ähnlichkeiten zu nutzen, sondern statdessen einen auf Maschinenlernbarkeit basierenden Ansatz zu wählen, besitzt jedoch kein namens- bzw. graphenbasiertes Matching.

Dike

Dike ermittelt Synonym- und Inklusions-Beziehungen (is-a) eines EntityRelationship-Schemas. Objekte werden als ähnlich markiert, falls die damit verknüpften Attribute ähnlich sind. Als Ergebnis auf zwei ER-Schemata werden die Wahrscheinlichkeitswerte zwischen beiden, gemeinsam mit Synonymen und Inklusionen ausgegeben.

Cupid

Cupid ist ein Mehrzweck-Schemamatcher, welcher mit hybriden Verfahren arbeitet. Er funktioniert sowohl element- als auch strukturbasiert, spezialisiert sich jedoch auf Ähnlichkeiten von atomaren Elementen, da dort viele Schemasemantiken aufzufinden sind. Laut [Cupid01] werden ebenso interne Strukturen erkundet, wobei deren Differenzen nur gering in die Gesamtklassifizierung einfließen. Der Gesamtablauf ist in 3 Stufen gegliedert, wobei im ersten Schritt Elemente (Knoten des Schemas) auf linguistische Eigenschaften verglichen werden, inklusive externen Abgleich von Synonymen. Für den zweiten Schritt, den strukturellen Ablauf, wird das Datamodell in eine Baumstruktur transformiert und Paare daraufhin anhand ihrer Blattknoten verglichen. Ein Ähnlichkeit wird durch den gewichteten Abgleich zwischen linguistischem und strukturellem Ergebnis ermittelt. In der dritten Phase entscheidet der Schwellwert (Threshold) über Übereinstimmung. Dieser Wert ist domänenabhängig und kann nicht im Voraus angegeben werden.

COMA

„Combination of Matching-Algorithms“ nutzt einen direkten, azyklischen Graphen, und arbeitet semiautomatisch mit Hilfe von User-Feedback. COMA befolgt ebenfalls einen Kompositions-Ansatz, welcher eine erweiterbare Bibliothek von verschiedenen Matchern zur Verfügung stellt und eine Vielzahl von Kombination der ermittelten Matching-Ergebnisse unterstützt. Hier finden ebenfalls zuvor errechnete Resultate wiederverwendung. Die Kompositionsstrategien adressieren verschiedene Aspekte des Matching-Prozesses, so z.B. die Aggregation von Matcher-spezifischen Ergebnissen und Match-Kandidaten-Auswahl. Schemata werden auch hier in gerichtete direkte azyklische Graphen transformiert, auf denen alle Algorithmen arbeiten. Jedes Schema ist unique identifiziert durch seinen kompletten Pfad von der Quelle des Schemengraphes bis zum korrepsondierenden Knoten.

COMA erzeugt auf Elementebene Übereinstimmungen von 1:1 lokaler und m:n globaler Kardinalität. Der Alignment-Prozess besteht auch hier aus 3 Phasen, die iterativ durchlaufen werden und wobei die erste stets eine User-Feedback-Dialog zum Einstellen verschiedener Parameter darstellt (e.g. Auswahl des entsprechenden Matchers/Annahme, Ablehnung eines entsprechenden Entwurfes.). Daraufhin werden die individuellen Ähnlichkeiten berechnet. Diese basieren meist auf linguistischen Informationen, nutzen ebenso im Hintergrund Wörterbücher und strukturelle Elemente as Kinder oder Blätter. In der dritten Phase werden die Matcher wiederum kombiniert, entweder durch ein Maximum, einer Gewichtung einem Durchschnitt oder einer MinimumStrategie. Verschiedene Annäherungen für Schwellwert-Determinationen werden gegeben. Es ist ebenso möglich, das Programm komplett automatisch zu betreiben.

CTX S-Match

S-Match ermittelt Annäherungen, um semantische Beziehung zwischen Klassen zweier Klassifikationsschemata abzuleiten. Diese werden dazu von einer Datenbank oder Ontologie extrahiert. Sie basieren auf Untersuchung der Labels m.H. von „Wordnet“ als Synonym- Thesaurus-Überprüfung. Es sind laut [ChiunchigliaEtAl'04] ebenfalls weitere Element-Matcher vorhanden. Zusätzlich kommt hier ein SAT-Solver zum Einsatz, welcher die Schemata untersucht und dabei vor allem die Taxonomie und geschlußfolgerte Implikationen ermittelt. Er gibt entweder Gleichheit, Untermenge oder Unabhängigkeit zwischen 2 Klassen zurück.

Zusammenfassung

Auf den vorangegangen Seiten wurden Methoden und Vorgehensweisen zur Identifizierung von Bestandteilen eines unbekannten Schemas vorgestellt. Fünf konkrete Beispiele aus dem universitären Umfeld, welche (semi-) automatische Umsetzungen durchführen, erlauben mit Hilfe einer Vergleichsstruktur, lokale Komponentenschemata zu erkennen.

Mit diesem Strukturwissen kann ein Abfrageterm für Xcerpt generiert werden, welcher die entsprechenden Felder der Struktur gezielt ansteuert.

Instanzen der globalen Komponente werden dadurch extrahiert und über einen global identischen Konstruktionsterm zur Verfügung gestellt.

Auf diese Instanzen kann im nächsten Kapiteln transparent zurückgegriffen werden, und deren Inhalt semantisch angeglichen sowie abschließend untereinander verknüpft werden.

Aufgrund des subjektiven Architekturansatzes werden kaum auf einem Gebiet exakt passende Strukturen zu finden sein. Die Identifizierung und Nutzung semantischer Korrespondenzen zwischen den Elementen zweier Schemata wird mit „Schema-Alignment“ bezeichnet und gilt es in einer Vielzahl von Anwendungen zu lösen. Im Bereich der Daten-Integrationen sowie XML-Message-Mapping in heterogenen Systemen beispielsweise vorgefunden, kommen Struktur-Analysen bei e-Commerce- oder Data-Warehousing-Applicationen stark zum Einsatz. Oftmals werden dabei diese Mapping-Aufgaben noch manuell (händisch) mit teilweiser graphischer Unterstützung erledigt, was nicht nur zeitaufwendig sondern mit zunehmender Anzahl unterschiedlicher Schemata ansteigend unpraktikabel ist.

Motivation

Unterschiede in Schemata können sowohl auf einer sprachlichen als auch auf der Bedeutungsebene auftreten.

So können sich sprachliche Ausdrücke

• gegenseitig verneinen,
• Schnittmengen bilden,
• Vereinigungen (Oberbegriff), aber auch
• Disjunktionen

darstellen.

Auf Bedeutungsebene kann beispielsweise

• ein Term unterschiedliche Konzepte beschreiben
• ebenso verschiedene Terme beschreiben unterschiedliche Konzepte
• gleiche Terme unterschiedliche Konzepte beschreiben
• verschiedene Modellierungsparadigmen gelten
• verschiedene Modellierungskonventionen gelten
• ein abweichender Granularitätslevel auftreten
• verschiedene Abdeckung oder
• unterschiedliche Standpunkte vertreten werden.

Ansätze

[Noy05] nennt für die automatische Alternative der Strukturvereinigung die Herangehensweisen „Mapping“, „Artikulation“ und „Merging“.

Das Ziel des Mappings ist es, für die Abbildung gegeneinander ein Dokument als Adapter anzulegen. Es beinhaltet Elemente, welche die Symbole des einen Alphabetes mit denen des zweiten Alphabets verknüpfen.

Diese Mapping-Elemente sind hierbei jeweils 5-Tupel (id, e, e',R,n) mit

• dem uniquen Identifier des gegebenen Mapping-Elements <var>id</var>
• e und e', den Entitätsklassen (also z.B., XML-Elemente, Klassen)
• Rals Relation zwischen e und e' (z.B. Gleichheit , Generalisierung , Disjunktion)
• n als Vertrauensmessung in einer mathematischen Struktur (typischerweise zwischen [0,1])

Eine Angleichung A ist damit eine Menge von Mapping-Elementen, welche von zwei Schemata abhängt. Sie besitzt einige Multiplizitäten (1-1, 1-*, etc.) sowie einige andere Eigenschaften.

Da dabei nicht-übereinstimmende Aspekte leicht verloren gehen, kann diese Mapping gemeinsam mit den beiden Originaldokumenten präsentiert werden. Strukturen die in allgemeineren Wegen als durch binär ausdrückbare Gemeinsamkeiten miteinander in Beziehungen stehen, so zum Beispiel durch Relationen anstatt von Funktionen, wie es bei Ontologien gegeben ist, können gemeinsam mit einem gemappten Grundübereinstimmungsdokument präsentiert werden, Artikulation genannt.

Beim Merging wir auf Grundlage aller beteiligter Quellen eine komplett neue Struktur erstellt, welche die Instanzen beider zusammenführt.

Betrachtungsaspekte

Zur Analyse von Strukturen werden in [VLDBJ2001] folgende Betrachtungsaspekte genannt:

Schema- und Instanzenmatching

Schema-Matching betrachtet das Schema einer Struktur und versucht auf Grundlage der Eigenschaften von Schema-Elementen, wie deren Name, deren Beschreibungstext, deren Beziehungentypen zu anderen Elementen (Is-a oder Sub-/Supkonzept-Eigenschaften) sowie gegebenen Constraints jeweils Übereinstimmungen in beiden Basen zu finden.

Bei Datensammlungen, welche nur in limitierter Weise nützliche Schema-Informationen enthalten, seien dies semistrukturierten Daten in Form von HTML-Seiten, gibt Instanzenwissen wichtige Einblicke in den Inhalt und die Bedeutung von einzelnen Schemaelementen. Im Extremfall ist keinerlei Schema vorgegeben und muss von den Instanzendaten manuell oder automatisch erstellt werden. Dabei kommen oftmals die im Kapitel "Inhaltsintegration" ausführlich behandelten Datenharmonisierungstechniken zum Einsatz.

Aber auch bei vorhandenen Schemata kann Instanzensichtung wichtig sein, um abweichende Interpretationen der Schema-Informationen aufzudecken. Falls bei einem solchem Matching beispielsweise zwei Schema-Zuweisungen gleiche Wahrscheinlichkeit besitzten, kann auf das Element mit höherer Übereinstimmung in den Instanzen zurückgegriffen werden.

Element- und Strukturmatching

Im Idealfall eines Matchings besitzen alle Elemente eines Schemas mit Ihnen identische Elemente des zweiten Schemas auf der selben Hierarchie-Ebene. Beide unterscheiden sich hierbei lediglich durch abweichende Schema-Bezeichnungen wie „Adresse.ZIP“ und „Adresse.PLZ“. Oftmals wird diese feinste Granularität über die Attribute jedoch nicht erreicht, und Informationseinheiten überlappen einander oder sind in verschiedenen Sub- oder Subkonzepten vertreten.

Beispielsweise kann in einem Schema Postleitzahl und Ort in einem Attribut zusammengefasst sein. Besitzen nun beide Schemata nur eine bestimmte Schnittmenge gemeinsamer Informationen, wird nur eine partielle strukturelle Übereinstimmung gesucht.

Element-Level-Matcher sind auf eine Ebene beschränkt, während Struktur-Matcher darüber- und darunterliegende Konzepte ebenso als zur Struktur gehörig betrachten, um darin gemeinsame Schnittpunkte zu finden.

Im Gegensatz zu einem Struktur-Matcher ignoriert ein Elementmatcher bestehende SubKonzepte. Er ist jedoch auch nicht auf das Atomare Level beschränkt, sondern kann auch auf grobkörnigere, höhere nicht-atomare Elemente angewendet werden, jedoch nur in einer Hierarchieebene arbeitend. Er nutzen eine Vielzahl der in der relationalen Datenbank-Bearbeitung genutzen Methoden (siehe Datenharmonisierung), und wendet diese auf Elementnamen, Beschreibung oder Datentyp des einzelnen Schema-Elementes an.

Matching-Kardinalität

Ein Element eines Schemas S1 kann Ähnlichkeiten zu einem oder mehreren Elementen des Schemas S2 besitzen. Ebenso kann umgekehrt ein Element aus S2 mehrere Vertreter aus S1 haben. Es sind demnach beim Struktumatching gewöhnliche Beziehungsrelationen (1:1), mengenorientierte Fälle (1:n bzw. n:1) bis hin zu n:m – Relationen denkbar, jeweils entweder auf eine globale Kardinalität zwischen verschiedenen Mapping-Elementen oder einer lokalen Kardinalität zu einem individuellen Mapping-Element. Element-Level Matching ist meist auf eine lokale Kardinalität von 1:1, 1:n und n:1 beschränkt. n:m – Ergebnisse erfordern in jeden Fall eine zusätzliche Strukturmatching-Analyse (siehe Kapitel 2.2.2)

Sprache und Constraints

Die linguistische Annäherung wird zunächst in Form der Namensübereinstimmung verwendet. Damit kann ein gleicher Name, ein gleicher Name in kanonischer Sicht, aber auch gleiche Synonyme gemeint sein. Ebenso können zwei Bezeichner einen gemeinsamen Oberbegriff (Hypernym, bspw. in Form einer Inklusions-Beziehung („is-a“)) teilen, oder auf Zeichenebene Ähnlichkeiten besitzen. Domänenabhängig kann vom Nutzer auch eine Ersetzungsliste geliefert werden. Weitere Vorgehen in diesem Bereich werden im Kapitel "Onthologien" und "Zeichenmetriken" vorgestellt.

Da oftmals in Schemata Kommentare und Beschreibungstexte in natürlicher Sprache die gewünschte Semantik der Schemaelemente ausdrücken, können hierin ebenfalls Schlüsselwörter extrahiert werden.

Constraint-basierte Untersuchung beinhaltet den Vergleich zweier Elemente auf gleiche/ähnliche Datentypen, Wertebereiche, Beziehungstypen, Kardinalitäten oder etwaige Optionalität.

Weiterhin kann ihre Eigenschaft als Schlüsselcharakter (unique, Primär-, Fremdschlüssel) genutzt werden. Eine alleinige Nutzung dieser Methode würde zu falschen Übereinstimmungen führen, aber als unterstützendes Element ist die constraintbasierte Untersuchung sehr hilfreich.

helfende Systeme

Meist werden zusätzlich zu den oben genannten Faktoren noch externe Quellen wie Wörterbücher und Thesauri-Lexika für Stemming, Synonym-Identifizierungen und somit der Auflösung von Verklemmungen genutzt werden. Ebenfalls kann man bereits bestehende Matchings anderer Strukturen mit der gleichen Domäne verwenden, um eine mögliche Ausrichtung besser erahnen zu können.

Vorgehen

[Studer05] gibt in Bezug auf das „OntologyAlignment“ einen grundsätzlich erkennbaren Ablauf einer Strukturanalysen vor, auf den sich [Meh05] genauer bezieht und ihn an diversen Systemen zeigt. Da Ontologien eine spezialisierte Struktur darstellen, ist das Ontology-Alignment eine Unterform der Struktur-Analyse und kann auf alle übrigen XML-Strukturen Anwendung finden.

Zwei Schemas aufeinander abzubilden bedeutet hierin, dass für jede Entität (Begriff, Relation, Instanz) des ersten Schemas die Entsprechung mit derselben Bedeutung im zweiten Schema gesucht wird. Es wird die 5-Tupel- Funktion align auf einem Vokabular E aller Entitäten $e\in E$ , d.h. Begriffe, Relationen und Instanzen und der Menge möglicher Schemata S als partielle Funktion $\begin{array}{}\text{align}:E\times O\times O\to E,\text{mit}\forall e\in E_{O_1}\exists f\in E_{O_2},O_{\mathrm{1,}}{O}_2\in O:\text{align}(e,O_{\mathrm{1,}}{O}_2)=f\vee \text{align}(e,O_{\mathrm{1,}}{O}_2)=\downarrow \end{array}$ angewendet.

1.Merkmalskonstruktion

In diesem Schritt werden die Merkmale einer Entität ausgewählt, welche sie treffend beschreiben. Dies kann ein lexikalischer Eintrag einer Entität sein, aber auch eine intensionale Struktureigenschaft wie die is-a Beziehung.Desweiteren werden extensionale Beschreibungen genutzt

2.Suchraumbestimmung

Zur Ableitung von Abbildungen in Strukturen wird ein Suchraum von Kandidaten aufgestellt. Ähnlich einer Blockingmethode stellt diese sinnvolle Kandidaten für einen Vergleich auf und sortiert alle übrigen somit aus.

3.Ähnlichkeitsberechnung

Hier werden die im Kapitel Datenharmonisierung vorgestellten Methoden, ebenso wie Ähnlichkeitsfunktionen für Einzelobjekte oder Objektmengen genutzt, um die Ähnlichkeit zweier Entitäten zu bestimmen.

4.Ähnlichkeitsaufsummierung

Im Allgemeinen werden dabei mehrere Ähnlichkeitswerte für ein Entitätenpaar errechnet, beispielsweise auf lexikalische Einträge oder Ähnlichkeit der Relationen zu anderen Entitäten. Es entspricht der in Kapitel Klassifikation näher vorgestellten Klassifikation.

5.Interpretation

Die Aufsummierten Ähnlichkeitswerte werden nun zur Abbildung der Entitäten aufeinander genutzt. Möglichkeiten dafür sind ein Schwellenwert, eine Mischung aus Struktur und Ähnlichkeitswerten oder Relaxation Labelling, welches Letztere mit weiteren Heuristiken mischt [semanticIntegration_glue]

6.Iteration

Um die Struktur des Schemas besser zu nutzen, wiederholt ein Algorithmus die beschriebenen Schritte.

Die grundsätzlichen Algorithmen der Stufen 2 bis 5 finden analog bei der Datenharmonisierung Anwendung, welche im Kapitel 3 näher vorgestellt wird. Jeder dieser 6 Schritte besitzt natürlich selbst eigene spezifische Methoden mit jeweils entsprechenden zu setzenden Parametern.

Beispiele

Eine Vielzahl von Applikationen und Frameworks haben dieses Vorgehen bereits fest umgesetzt. Es wird dabei oftmals zwischen Individual und kombinatorischen Systemen unterschieden. Während ersterer sich auf einen Algorithmus konzentriert, verwenden die Vertreter der zweiten Gruppe mehrere Algorithmen und gewichten die Teilergebnisse.

Grundsätzlich verwendete Methoden sind

• Heuristisch und Regelbasierte Methoden
• Graphenanalyse
• Maschinen-Lernen-Statistiken
• Probalistische Annäherung
• Reasoning

Es soll nun Auswahl aktueller, aussichtsreicher Vertreter folgen. Diese werden in [Meh05], [Cupid01] und [ChiunchigliaEtAl'04] näher evaluierter.

SemInt

„Seamless Moell Integration“ als instanzbasiertes System assoziiert Attribute in beiden Schemen mit Treffer-Signaturen. Diese bestehen aus 15 constraint-basierenden und 5 content-basierenden Kriterien, welche von den Instanz-Werten abgeleitet und auf [0,1] normalisiert werden, so daß jedes Kriterium einen Wert in einem 20-dimensionalen Vektorraum einnimmt. Diese werden auf Grundlage ihrer Euklid-Distanz geclustert und ein neuronales Netz mit Ihnen trainiert, welches auf das zweite Schema angewendet wird. Hierbei handelt es sich um einen hybriden Elementlevel-Matcher, welcher die Schemastruktur nicht beachtet. [Cupid01]. Semint ist einer der ersten Anläufe, keine hartkodierten Kombinationen von individuellen regelbasierten Ähnlichkeiten zu nutzen, sondern statdessen einen auf Maschinenlernbarkeit basierenden Ansatz zu wählen, besitzt jedoch kein namens- bzw. graphenbasiertes Matching.

Dike

Dike ermittelt Synonym- und Inklusions-Beziehungen (is-a) eines EntityRelationship-Schemas. Objekte werden als ähnlich markiert, falls die damit verknüpften Attribute ähnlich sind. Als Ergebnis auf zwei ER-Schemata werden die Wahrscheinlichkeitswerte zwischen beiden, gemeinsam mit Synonymen und Inklusionen ausgegeben.

Cupid

Cupid ist ein Mehrzweck-Schemamatcher, welcher mit hybriden Verfahren arbeitet. Er funktioniert sowohl element- als auch strukturbasiert, spezialisiert sich jedoch auf Ähnlichkeiten von atomaren Elementen, da dort viele Schemasemantiken aufzufinden sind. Laut [Cupid01] werden ebenso interne Strukturen erkundet, wobei deren Differenzen nur gering in die Gesamtklassifizierung einfließen. Der Gesamtablauf ist in 3 Stufen gegliedert, wobei im ersten Schritt Elemente (Knoten des Schemas) auf linguistische Eigenschaften verglichen werden, inklusive externen Abgleich von Synonymen. Für den zweiten Schritt, den strukturellen Ablauf, wird das Datamodell in eine Baumstruktur transformiert und Paare daraufhin anhand ihrer Blattknoten verglichen. Ein Ähnlichkeit wird durch den gewichteten Abgleich zwischen linguistischem und strukturellem Ergebnis ermittelt. In der dritten Phase entscheidet der Schwellwert (Threshold) über Übereinstimmung. Dieser Wert ist domänenabhängig und kann nicht im Voraus angegeben werden.

COMA

„Combination of Matching-Algorithms“ nutzt einen direkten, azyklischen Graphen, und arbeitet semiautomatisch mit Hilfe von User-Feedback. COMA befolgt ebenfalls einen Kompositions-Ansatz, welcher eine erweiterbare Bibliothek von verschiedenen Matchern zur Verfügung stellt und eine Vielzahl von Kombination der ermittelten Matching-Ergebnisse unterstützt. Hier finden ebenfalls zuvor errechnete Resultate wiederverwendung. Die Kompositionsstrategien adressieren verschiedene Aspekte des Matching-Prozesses, so z.B. die Aggregation von Matcher-spezifischen Ergebnissen und Match-Kandidaten-Auswahl. Schemata werden auch hier in gerichtete direkte azyklische Graphen transformiert, auf denen alle Algorithmen arbeiten. Jedes Schema ist unique identifiziert durch seinen kompletten Pfad von der Quelle des Schemengraphes bis zum korrepsondierenden Knoten.

COMA erzeugt auf Elementebene Übereinstimmungen von 1:1 lokaler und m:n globaler Kardinalität. Der Alignment-Prozess besteht auch hier aus 3 Phasen, die iterativ durchlaufen werden und wobei die erste stets eine User-Feedback-Dialog zum Einstellen verschiedener Parameter darstellt (e.g. Auswahl des entsprechenden Matchers/Annahme, Ablehnung eines entsprechenden Entwurfes.). Daraufhin werden die individuellen Ähnlichkeiten berechnet. Diese basieren meist auf linguistischen Informationen, nutzen ebenso im Hintergrund Wörterbücher und strukturelle Elemente as Kinder oder Blätter. In der dritten Phase werden die Matcher wiederum kombiniert, entweder durch ein Maximum, einer Gewichtung einem Durchschnitt oder einer MinimumStrategie. Verschiedene Annäherungen für Schwellwert-Determinationen werden gegeben. Es ist ebenso möglich, das Programm komplett automatisch zu betreiben.

CTX S-Match

S-Match ermittelt Annäherungen, um semantische Beziehung zwischen Klassen zweier Klassifikationsschemata abzuleiten. Diese werden dazu von einer Datenbank oder Ontologie extrahiert. Sie basieren auf Untersuchung der Labels m.H. von „Wordnet“ als Synonym- Thesaurus-Überprüfung. Es sind laut [ChiunchigliaEtAl'04] ebenfalls weitere Element-Matcher vorhanden. Zusätzlich kommt hier ein SAT-Solver zum Einsatz, welcher die Schemata untersucht und dabei vor allem die Taxonomie und geschlußfolgerte Implikationen ermittelt. Er gibt entweder Gleichheit, Untermenge oder Unabhängigkeit zwischen 2 Klassen zurück.

Zusammenfassung

Auf den vorangegangen Seiten wurden Methoden und Vorgehensweisen zur Identifizierung von Bestandteilen eines unbekannten Schemas vorgestellt. Fünf konkrete Beispiele aus dem universitären Umfeld, welche (semi-) automatische Umsetzungen durchführen, erlauben mit Hilfe einer Vergleichsstruktur, lokale Komponentenschemata zu erkennen.

Mit diesem Strukturwissen kann ein Abfrageterm für Xcerpt generiert werden, welcher die entsprechenden Felder der Struktur gezielt ansteuert.

Instanzen der globalen Komponente werden dadurch extrahiert und über einen global identischen Konstruktionsterm zur Verfügung gestellt.

Auf diese Instanzen kann im nächsten Kapiteln transparent zurückgegriffen werden, und deren Inhalt semantisch angeglichen sowie abschließend untereinander verknüpft werden.

Aufgrund des subjektiven Architekturansatzes werden kaum auf einem Gebiet exakt passende Strukturen zu finden sein. Die Identifizierung und Nutzung semantischer Korrespondenzen zwischen den Elementen zweier Schemata wird mit „Schema-Alignment“ bezeichnet und gilt es in einer Vielzahl von Anwendungen zu lösen. Im Bereich der Daten-Integrationen sowie XML-Message-Mapping in heterogenen Systemen beispielsweise vorgefunden, kommen Struktur-Analysen bei e-Commerce- oder Data-Warehousing-Applicationen stark zum Einsatz. Oftmals werden dabei diese Mapping-Aufgaben noch manuell (händisch) mit teilweiser graphischer Unterstützung erledigt, was nicht nur zeitaufwendig sondern mit zunehmender Anzahl unterschiedlicher Schemata ansteigend unpraktikabel ist.

Motivation

Unterschiede in Schemata können sowohl auf einer sprachlichen als auch auf der Bedeutungsebene auftreten.

So können sich sprachliche Ausdrücke

• gegenseitig verneinen,
• Schnittmengen bilden,
• Vereinigungen (Oberbegriff), aber auch
• Disjunktionen

darstellen.

Auf Bedeutungsebene kann beispielsweise

• ein Term unterschiedliche Konzepte beschreiben
• ebenso verschiedene Terme beschreiben unterschiedliche Konzepte
• gleiche Terme unterschiedliche Konzepte beschreiben
• verschiedene Modellierungsparadigmen gelten
• verschiedene Modellierungskonventionen gelten
• ein abweichender Granularitätslevel auftreten
• verschiedene Abdeckung oder
• unterschiedliche Standpunkte vertreten werden.

Ansätze

[Noy05] nennt für die automatische Alternative der Strukturvereinigung die Herangehensweisen „Mapping“, „Artikulation“ und „Merging“.

Das Ziel des Mappings ist es, für die Abbildung gegeneinander ein Dokument als Adapter anzulegen. Es beinhaltet Elemente, welche die Symbole des einen Alphabetes mit denen des zweiten Alphabets verknüpfen.

Diese Mapping-Elemente sind hierbei jeweils 5-Tupel (id, e, e',R,n) mit

• dem uniquen Identifier des gegebenen Mapping-Elements <var>id</var>
• e und e', den Entitätsklassen (also z.B., XML-Elemente, Klassen)
• Rals Relation zwischen e und e' (z.B. Gleichheit , Generalisierung , Disjunktion)
• n als Vertrauensmessung in einer mathematischen Struktur (typischerweise zwischen [0,1])

Eine Angleichung A ist damit eine Menge von Mapping-Elementen, welche von zwei Schemata abhängt. Sie besitzt einige Multiplizitäten (1-1, 1-*, etc.) sowie einige andere Eigenschaften.

Da dabei nicht-übereinstimmende Aspekte leicht verloren gehen, kann diese Mapping gemeinsam mit den beiden Originaldokumenten präsentiert werden. Strukturen die in allgemeineren Wegen als durch binär ausdrückbare Gemeinsamkeiten miteinander in Beziehungen stehen, so zum Beispiel durch Relationen anstatt von Funktionen, wie es bei Ontologien gegeben ist, können gemeinsam mit einem gemappten Grundübereinstimmungsdokument präsentiert werden, Artikulation genannt.

Beim Merging wir auf Grundlage aller beteiligter Quellen eine komplett neue Struktur erstellt, welche die Instanzen beider zusammenführt.

Betrachtungsaspekte

Zur Analyse von Strukturen werden in [VLDBJ2001] folgende Betrachtungsaspekte genannt:

Schema- und Instanzenmatching

Schema-Matching betrachtet das Schema einer Struktur und versucht auf Grundlage der Eigenschaften von Schema-Elementen, wie deren Name, deren Beschreibungstext, deren Beziehungentypen zu anderen Elementen (Is-a oder Sub-/Supkonzept-Eigenschaften) sowie gegebenen Constraints jeweils Übereinstimmungen in beiden Basen zu finden.

Bei Datensammlungen, welche nur in limitierter Weise nützliche Schema-Informationen enthalten, seien dies semistrukturierten Daten in Form von HTML-Seiten, gibt Instanzenwissen wichtige Einblicke in den Inhalt und die Bedeutung von einzelnen Schemaelementen. Im Extremfall ist keinerlei Schema vorgegeben und muss von den Instanzendaten manuell oder automatisch erstellt werden. Dabei kommen oftmals die im Kapitel "Inhaltsintegration" ausführlich behandelten Datenharmonisierungstechniken zum Einsatz.

Aber auch bei vorhandenen Schemata kann Instanzensichtung wichtig sein, um abweichende Interpretationen der Schema-Informationen aufzudecken. Falls bei einem solchem Matching beispielsweise zwei Schema-Zuweisungen gleiche Wahrscheinlichkeit besitzten, kann auf das Element mit höherer Übereinstimmung in den Instanzen zurückgegriffen werden.

Element- und Strukturmatching

Im Idealfall eines Matchings besitzen alle Elemente eines Schemas mit Ihnen identische Elemente des zweiten Schemas auf der selben Hierarchie-Ebene. Beide unterscheiden sich hierbei lediglich durch abweichende Schema-Bezeichnungen wie „Adresse.ZIP“ und „Adresse.PLZ“. Oftmals wird diese feinste Granularität über die Attribute jedoch nicht erreicht, und Informationseinheiten überlappen einander oder sind in verschiedenen Sub- oder Subkonzepten vertreten.

Beispielsweise kann in einem Schema Postleitzahl und Ort in einem Attribut zusammengefasst sein. Besitzen nun beide Schemata nur eine bestimmte Schnittmenge gemeinsamer Informationen, wird nur eine partielle strukturelle Übereinstimmung gesucht.

Element-Level-Matcher sind auf eine Ebene beschränkt, während Struktur-Matcher darüber- und darunterliegende Konzepte ebenso als zur Struktur gehörig betrachten, um darin gemeinsame Schnittpunkte zu finden.

Im Gegensatz zu einem Struktur-Matcher ignoriert ein Elementmatcher bestehende SubKonzepte. Er ist jedoch auch nicht auf das Atomare Level beschränkt, sondern kann auch auf grobkörnigere, höhere nicht-atomare Elemente angewendet werden, jedoch nur in einer Hierarchieebene arbeitend. Er nutzen eine Vielzahl der in der relationalen Datenbank-Bearbeitung genutzen Methoden (siehe Datenharmonisierung), und wendet diese auf Elementnamen, Beschreibung oder Datentyp des einzelnen Schema-Elementes an.

Matching-Kardinalität

Ein Element eines Schemas S1 kann Ähnlichkeiten zu einem oder mehreren Elementen des Schemas S2 besitzen. Ebenso kann umgekehrt ein Element aus S2 mehrere Vertreter aus S1 haben. Es sind demnach beim Struktumatching gewöhnliche Beziehungsrelationen (1:1), mengenorientierte Fälle (1:n bzw. n:1) bis hin zu n:m – Relationen denkbar, jeweils entweder auf eine globale Kardinalität zwischen verschiedenen Mapping-Elementen oder einer lokalen Kardinalität zu einem individuellen Mapping-Element. Element-Level Matching ist meist auf eine lokale Kardinalität von 1:1, 1:n und n:1 beschränkt. n:m – Ergebnisse erfordern in jeden Fall eine zusätzliche Strukturmatching-Analyse (siehe Kapitel 2.2.2)

Sprache und Constraints

Die linguistische Annäherung wird zunächst in Form der Namensübereinstimmung verwendet. Damit kann ein gleicher Name, ein gleicher Name in kanonischer Sicht, aber auch gleiche Synonyme gemeint sein. Ebenso können zwei Bezeichner einen gemeinsamen Oberbegriff (Hypernym, bspw. in Form einer Inklusions-Beziehung („is-a“)) teilen, oder auf Zeichenebene Ähnlichkeiten besitzen. Domänenabhängig kann vom Nutzer auch eine Ersetzungsliste geliefert werden. Weitere Vorgehen in diesem Bereich werden im Kapitel "Onthologien" und "Zeichenmetriken" vorgestellt.

Da oftmals in Schemata Kommentare und Beschreibungstexte in natürlicher Sprache die gewünschte Semantik der Schemaelemente ausdrücken, können hierin ebenfalls Schlüsselwörter extrahiert werden.

Constraint-basierte Untersuchung beinhaltet den Vergleich zweier Elemente auf gleiche/ähnliche Datentypen, Wertebereiche, Beziehungstypen, Kardinalitäten oder etwaige Optionalität.

Weiterhin kann ihre Eigenschaft als Schlüsselcharakter (unique, Primär-, Fremdschlüssel) genutzt werden. Eine alleinige Nutzung dieser Methode würde zu falschen Übereinstimmungen führen, aber als unterstützendes Element ist die constraintbasierte Untersuchung sehr hilfreich.

helfende Systeme

Meist werden zusätzlich zu den oben genannten Faktoren noch externe Quellen wie Wörterbücher und Thesauri-Lexika für Stemming, Synonym-Identifizierungen und somit der Auflösung von Verklemmungen genutzt werden. Ebenfalls kann man bereits bestehende Matchings anderer Strukturen mit der gleichen Domäne verwenden, um eine mögliche Ausrichtung besser erahnen zu können.

Vorgehen

[Studer05] gibt in Bezug auf das „OntologyAlignment“ einen grundsätzlich erkennbaren Ablauf einer Strukturanalysen vor, auf den sich [Meh05] genauer bezieht und ihn an diversen Systemen zeigt. Da Ontologien eine spezialisierte Struktur darstellen, ist das Ontology-Alignment eine Unterform der Struktur-Analyse und kann auf alle übrigen XML-Strukturen Anwendung finden.

Zwei Schemas aufeinander abzubilden bedeutet hierin, dass für jede Entität (Begriff, Relation, Instanz) des ersten Schemas die Entsprechung mit derselben Bedeutung im zweiten Schema gesucht wird. Es wird die 5-Tupel- Funktion align auf einem Vokabular E aller Entitäten $e\in E$ , d.h. Begriffe, Relationen und Instanzen und der Menge möglicher Schemata S als partielle Funktion $\begin{array}{}\text{align}:E\times O\times O\to E,\text{mit}\forall e\in E_{O_1}\exists f\in E_{O_2},O_{\mathrm{1,}}{O}_2\in O:\text{align}(e,O_{\mathrm{1,}}{O}_2)=f\vee \text{align}(e,O_{\mathrm{1,}}{O}_2)=\downarrow \end{array}$ angewendet.

1.Merkmalskonstruktion

In diesem Schritt werden die Merkmale einer Entität ausgewählt, welche sie treffend beschreiben. Dies kann ein lexikalischer Eintrag einer Entität sein, aber auch eine intensionale Struktureigenschaft wie die is-a Beziehung.Desweiteren werden extensionale Beschreibungen genutzt

2.Suchraumbestimmung

Zur Ableitung von Abbildungen in Strukturen wird ein Suchraum von Kandidaten aufgestellt. Ähnlich einer Blockingmethode stellt diese sinnvolle Kandidaten für einen Vergleich auf und sortiert alle übrigen somit aus.

3.Ähnlichkeitsberechnung

Hier werden die im Kapitel Datenharmonisierung vorgestellten Methoden, ebenso wie Ähnlichkeitsfunktionen für Einzelobjekte oder Objektmengen genutzt, um die Ähnlichkeit zweier Entitäten zu bestimmen.

4.Ähnlichkeitsaufsummierung

Im Allgemeinen werden dabei mehrere Ähnlichkeitswerte für ein Entitätenpaar errechnet, beispielsweise auf lexikalische Einträge oder Ähnlichkeit der Relationen zu anderen Entitäten. Es entspricht der in Kapitel Klassifikation näher vorgestellten Klassifikation.

5.Interpretation

Die Aufsummierten Ähnlichkeitswerte werden nun zur Abbildung der Entitäten aufeinander genutzt. Möglichkeiten dafür sind ein Schwellenwert, eine Mischung aus Struktur und Ähnlichkeitswerten oder Relaxation Labelling, welches Letztere mit weiteren Heuristiken mischt [semanticIntegration_glue]

6.Iteration

Um die Struktur des Schemas besser zu nutzen, wiederholt ein Algorithmus die beschriebenen Schritte.

Die grundsätzlichen Algorithmen der Stufen 2 bis 5 finden analog bei der Datenharmonisierung Anwendung, welche im Kapitel 3 näher vorgestellt wird. Jeder dieser 6 Schritte besitzt natürlich selbst eigene spezifische Methoden mit jeweils entsprechenden zu setzenden Parametern.

Beispiele

Eine Vielzahl von Applikationen und Frameworks haben dieses Vorgehen bereits fest umgesetzt. Es wird dabei oftmals zwischen Individual und kombinatorischen Systemen unterschieden. Während ersterer sich auf einen Algorithmus konzentriert, verwenden die Vertreter der zweiten Gruppe mehrere Algorithmen und gewichten die Teilergebnisse.

Grundsätzlich verwendete Methoden sind

• Heuristisch und Regelbasierte Methoden
• Graphenanalyse
• Maschinen-Lernen-Statistiken
• Probalistische Annäherung
• Reasoning

Es soll nun Auswahl aktueller, aussichtsreicher Vertreter folgen. Diese werden in [Meh05], [Cupid01] und [ChiunchigliaEtAl'04] näher evaluierter.

SemInt

„Seamless Moell Integration“ als instanzbasiertes System assoziiert Attribute in beiden Schemen mit Treffer-Signaturen. Diese bestehen aus 15 constraint-basierenden und 5 content-basierenden Kriterien, welche von den Instanz-Werten abgeleitet und auf [0,1] normalisiert werden, so daß jedes Kriterium einen Wert in einem 20-dimensionalen Vektorraum einnimmt. Diese werden auf Grundlage ihrer Euklid-Distanz geclustert und ein neuronales Netz mit Ihnen trainiert, welches auf das zweite Schema angewendet wird. Hierbei handelt es sich um einen hybriden Elementlevel-Matcher, welcher die Schemastruktur nicht beachtet. [Cupid01]. Semint ist einer der ersten Anläufe, keine hartkodierten Kombinationen von individuellen regelbasierten Ähnlichkeiten zu nutzen, sondern statdessen einen auf Maschinenlernbarkeit basierenden Ansatz zu wählen, besitzt jedoch kein namens- bzw. graphenbasiertes Matching.

Dike

Dike ermittelt Synonym- und Inklusions-Beziehungen (is-a) eines EntityRelationship-Schemas. Objekte werden als ähnlich markiert, falls die damit verknüpften Attribute ähnlich sind. Als Ergebnis auf zwei ER-Schemata werden die Wahrscheinlichkeitswerte zwischen beiden, gemeinsam mit Synonymen und Inklusionen ausgegeben.

Cupid

Cupid ist ein Mehrzweck-Schemamatcher, welcher mit hybriden Verfahren arbeitet. Er funktioniert sowohl element- als auch strukturbasiert, spezialisiert sich jedoch auf Ähnlichkeiten von atomaren Elementen, da dort viele Schemasemantiken aufzufinden sind. Laut [Cupid01] werden ebenso interne Strukturen erkundet, wobei deren Differenzen nur gering in die Gesamtklassifizierung einfließen. Der Gesamtablauf ist in 3 Stufen gegliedert, wobei im ersten Schritt Elemente (Knoten des Schemas) auf linguistische Eigenschaften verglichen werden, inklusive externen Abgleich von Synonymen. Für den zweiten Schritt, den strukturellen Ablauf, wird das Datamodell in eine Baumstruktur transformiert und Paare daraufhin anhand ihrer Blattknoten verglichen. Ein Ähnlichkeit wird durch den gewichteten Abgleich zwischen linguistischem und strukturellem Ergebnis ermittelt. In der dritten Phase entscheidet der Schwellwert (Threshold) über Übereinstimmung. Dieser Wert ist domänenabhängig und kann nicht im Voraus angegeben werden.

COMA

„Combination of Matching-Algorithms“ nutzt einen direkten, azyklischen Graphen, und arbeitet semiautomatisch mit Hilfe von User-Feedback. COMA befolgt ebenfalls einen Kompositions-Ansatz, welcher eine erweiterbare Bibliothek von verschiedenen Matchern zur Verfügung stellt und eine Vielzahl von Kombination der ermittelten Matching-Ergebnisse unterstützt. Hier finden ebenfalls zuvor errechnete Resultate wiederverwendung. Die Kompositionsstrategien adressieren verschiedene Aspekte des Matching-Prozesses, so z.B. die Aggregation von Matcher-spezifischen Ergebnissen und Match-Kandidaten-Auswahl. Schemata werden auch hier in gerichtete direkte azyklische Graphen transformiert, auf denen alle Algorithmen arbeiten. Jedes Schema ist unique identifiziert durch seinen kompletten Pfad von der Quelle des Schemengraphes bis zum korrepsondierenden Knoten.

COMA erzeugt auf Elementebene Übereinstimmungen von 1:1 lokaler und m:n globaler Kardinalität. Der Alignment-Prozess besteht auch hier aus 3 Phasen, die iterativ durchlaufen werden und wobei die erste stets eine User-Feedback-Dialog zum Einstellen verschiedener Parameter darstellt (e.g. Auswahl des entsprechenden Matchers/Annahme, Ablehnung eines entsprechenden Entwurfes.). Daraufhin werden die individuellen Ähnlichkeiten berechnet. Diese basieren meist auf linguistischen Informationen, nutzen ebenso im Hintergrund Wörterbücher und strukturelle Elemente as Kinder oder Blätter. In der dritten Phase werden die Matcher wiederum kombiniert, entweder durch ein Maximum, einer Gewichtung einem Durchschnitt oder einer MinimumStrategie. Verschiedene Annäherungen für Schwellwert-Determinationen werden gegeben. Es ist ebenso möglich, das Programm komplett automatisch zu betreiben.

CTX S-Match

S-Match ermittelt Annäherungen, um semantische Beziehung zwischen Klassen zweier Klassifikationsschemata abzuleiten. Diese werden dazu von einer Datenbank oder Ontologie extrahiert. Sie basieren auf Untersuchung der Labels m.H. von „Wordnet“ als Synonym- Thesaurus-Überprüfung. Es sind laut [ChiunchigliaEtAl'04] ebenfalls weitere Element-Matcher vorhanden. Zusätzlich kommt hier ein SAT-Solver zum Einsatz, welcher die Schemata untersucht und dabei vor allem die Taxonomie und geschlußfolgerte Implikationen ermittelt. Er gibt entweder Gleichheit, Untermenge oder Unabhängigkeit zwischen 2 Klassen zurück.

Zusammenfassung

Auf den vorangegangen Seiten wurden Methoden und Vorgehensweisen zur Identifizierung von Bestandteilen eines unbekannten Schemas vorgestellt. Fünf konkrete Beispiele aus dem universitären Umfeld, welche (semi-) automatische Umsetzungen durchführen, erlauben mit Hilfe einer Vergleichsstruktur, lokale Komponentenschemata zu erkennen.

Mit diesem Strukturwissen kann ein Abfrageterm für Xcerpt generiert werden, welcher die entsprechenden Felder der Struktur gezielt ansteuert.

Instanzen der globalen Komponente werden dadurch extrahiert und über einen global identischen Konstruktionsterm zur Verfügung gestellt.

Auf diese Instanzen kann im nächsten Kapiteln transparent zurückgegriffen werden, und deren Inhalt semantisch angeglichen sowie abschließend untereinander verknüpft werden.

Aufgrund des subjektiven Architekturansatzes werden kaum auf einem Gebiet exakt passende Strukturen zu finden sein. Die Identifizierung und Nutzung semantischer Korrespondenzen zwischen den Elementen zweier Schemata wird mit „Schema-Alignment“ bezeichnet und gilt es in einer Vielzahl von Anwendungen zu lösen. Im Bereich der Daten-Integrationen sowie XML-Message-Mapping in heterogenen Systemen beispielsweise vorgefunden, kommen Struktur-Analysen bei e-Commerce- oder Data-Warehousing-Applicationen stark zum Einsatz. Oftmals werden dabei diese Mapping-Aufgaben noch manuell (händisch) mit teilweiser graphischer Unterstützung erledigt, was nicht nur zeitaufwendig sondern mit zunehmender Anzahl unterschiedlicher Schemata ansteigend unpraktikabel ist.

Unterschiede in Schemata können sowohl auf einer sprachlichen als auch auf der Bedeutungsebene auftreten.

So können sich sprachliche Ausdrücke

• gegenseitig verneinen,
• Schnittmengen bilden,
• Vereinigungen (Oberbegriff), aber auch
• Disjunktionen

darstellen.

Auf Bedeutungsebene kann beispielsweise

• ein Term unterschiedliche Konzepte beschreiben
• ebenso verschiedene Terme beschreiben unterschiedliche Konzepte
• gleiche Terme unterschiedliche Konzepte beschreiben
• verschiedene Modellierungsparadigmen gelten
• verschiedene Modellierungskonventionen gelten
• ein abweichender Granularitätslevel auftreten
• verschiedene Abdeckung oder
• unterschiedliche Standpunkte vertreten werden.

[Noy05] nennt für die automatische Alternative der Strukturvereinigung die Herangehensweisen „Mapping“, „Artikulation“ und „Merging“.

Das Ziel des Mappings ist es, für die Abbildung gegeneinander ein Dokument als Adapter anzulegen. Es beinhaltet Elemente, welche die Symbole des einen Alphabetes mit denen des zweiten Alphabets verknüpfen.

Diese Mapping-Elemente sind hierbei jeweils 5-Tupel (id, e, e',R,n) mit

• dem uniquen Identifier des gegebenen Mapping-Elements <var>id</var>
• e und e', den Entitätsklassen (also z.B., XML-Elemente, Klassen)
• Rals Relation zwischen e und e' (z.B. Gleichheit , Generalisierung , Disjunktion)
• n als Vertrauensmessung in einer mathematischen Struktur (typischerweise zwischen [0,1])

Eine Angleichung A ist damit eine Menge von Mapping-Elementen, welche von zwei Schemata abhängt. Sie besitzt einige Multiplizitäten (1-1, 1-*, etc.) sowie einige andere Eigenschaften.

Da dabei nicht-übereinstimmende Aspekte leicht verloren gehen, kann diese Mapping gemeinsam mit den beiden Originaldokumenten präsentiert werden. Strukturen die in allgemeineren Wegen als durch binär ausdrückbare Gemeinsamkeiten miteinander in Beziehungen stehen, so zum Beispiel durch Relationen anstatt von Funktionen, wie es bei Ontologien gegeben ist, können gemeinsam mit einem gemappten Grundübereinstimmungsdokument präsentiert werden, Artikulation genannt.

Beim Merging wir auf Grundlage aller beteiligter Quellen eine komplett neue Struktur erstellt, welche die Instanzen beider zusammenführt.

Zur Analyse von Strukturen werden in [VLDBJ2001] folgende Betrachtungsaspekte genannt:

Schema-Matching betrachtet das Schema einer Struktur und versucht auf Grundlage der Eigenschaften von Schema-Elementen, wie deren Name, deren Beschreibungstext, deren Beziehungentypen zu anderen Elementen (Is-a oder Sub-/Supkonzept-Eigenschaften) sowie gegebenen Constraints jeweils Übereinstimmungen in beiden Basen zu finden.

Bei Datensammlungen, welche nur in limitierter Weise nützliche Schema-Informationen enthalten, seien dies semistrukturierten Daten in Form von HTML-Seiten, gibt Instanzenwissen wichtige Einblicke in den Inhalt und die Bedeutung von einzelnen Schemaelementen. Im Extremfall ist keinerlei Schema vorgegeben und muss von den Instanzendaten manuell oder automatisch erstellt werden. Dabei kommen oftmals die im Kapitel "Inhaltsintegration" ausführlich behandelten Datenharmonisierungstechniken zum Einsatz.

Aber auch bei vorhandenen Schemata kann Instanzensichtung wichtig sein, um abweichende Interpretationen der Schema-Informationen aufzudecken. Falls bei einem solchem Matching beispielsweise zwei Schema-Zuweisungen gleiche Wahrscheinlichkeit besitzten, kann auf das Element mit höherer Übereinstimmung in den Instanzen zurückgegriffen werden.

Im Idealfall eines Matchings besitzen alle Elemente eines Schemas mit Ihnen identische Elemente des zweiten Schemas auf der selben Hierarchie-Ebene. Beide unterscheiden sich hierbei lediglich durch abweichende Schema-Bezeichnungen wie „Adresse.ZIP“ und „Adresse.PLZ“. Oftmals wird diese feinste Granularität über die Attribute jedoch nicht erreicht, und Informationseinheiten überlappen einander oder sind in verschiedenen Sub- oder Subkonzepten vertreten.

Beispielsweise kann in einem Schema Postleitzahl und Ort in einem Attribut zusammengefasst sein. Besitzen nun beide Schemata nur eine bestimmte Schnittmenge gemeinsamer Informationen, wird nur eine partielle strukturelle Übereinstimmung gesucht.

Element-Level-Matcher sind auf eine Ebene beschränkt, während Struktur-Matcher darüber- und darunterliegende Konzepte ebenso als zur Struktur gehörig betrachten, um darin gemeinsame Schnittpunkte zu finden.

Im Gegensatz zu einem Struktur-Matcher ignoriert ein Elementmatcher bestehende SubKonzepte. Er ist jedoch auch nicht auf das Atomare Level beschränkt, sondern kann auch auf grobkörnigere, höhere nicht-atomare Elemente angewendet werden, jedoch nur in einer Hierarchieebene arbeitend. Er nutzen eine Vielzahl der in der relationalen Datenbank-Bearbeitung genutzen Methoden (siehe Datenharmonisierung), und wendet diese auf Elementnamen, Beschreibung oder Datentyp des einzelnen Schema-Elementes an.

Ein Element eines Schemas S1 kann Ähnlichkeiten zu einem oder mehreren Elementen des Schemas S2 besitzen. Ebenso kann umgekehrt ein Element aus S2 mehrere Vertreter aus S1 haben. Es sind demnach beim Struktumatching gewöhnliche Beziehungsrelationen (1:1), mengenorientierte Fälle (1:n bzw. n:1) bis hin zu n:m – Relationen denkbar, jeweils entweder auf eine globale Kardinalität zwischen verschiedenen Mapping-Elementen oder einer lokalen Kardinalität zu einem individuellen Mapping-Element. Element-Level Matching ist meist auf eine lokale Kardinalität von 1:1, 1:n und n:1 beschränkt. n:m – Ergebnisse erfordern in jeden Fall eine zusätzliche Strukturmatching-Analyse (siehe Kapitel 2.2.2)

Die linguistische Annäherung wird zunächst in Form der Namensübereinstimmung verwendet. Damit kann ein gleicher Name, ein gleicher Name in kanonischer Sicht, aber auch gleiche Synonyme gemeint sein. Ebenso können zwei Bezeichner einen gemeinsamen Oberbegriff (Hypernym, bspw. in Form einer Inklusions-Beziehung („is-a“)) teilen, oder auf Zeichenebene Ähnlichkeiten besitzen. Domänenabhängig kann vom Nutzer auch eine Ersetzungsliste geliefert werden. Weitere Vorgehen in diesem Bereich werden im Kapitel "Onthologien" und "Zeichenmetriken" vorgestellt.

Da oftmals in Schemata Kommentare und Beschreibungstexte in natürlicher Sprache die gewünschte Semantik der Schemaelemente ausdrücken, können hierin ebenfalls Schlüsselwörter extrahiert werden.

Constraint-basierte Untersuchung beinhaltet den Vergleich zweier Elemente auf gleiche/ähnliche Datentypen, Wertebereiche, Beziehungstypen, Kardinalitäten oder etwaige Optionalität.

Weiterhin kann ihre Eigenschaft als Schlüsselcharakter (unique, Primär-, Fremdschlüssel) genutzt werden. Eine alleinige Nutzung dieser Methode würde zu falschen Übereinstimmungen führen, aber als unterstützendes Element ist die constraintbasierte Untersuchung sehr hilfreich.

Meist werden zusätzlich zu den oben genannten Faktoren noch externe Quellen wie Wörterbücher und Thesauri-Lexika für Stemming, Synonym-Identifizierungen und somit der Auflösung von Verklemmungen genutzt werden. Ebenfalls kann man bereits bestehende Matchings anderer Strukturen mit der gleichen Domäne verwenden, um eine mögliche Ausrichtung besser erahnen zu können.

[Studer05] gibt in Bezug auf das „OntologyAlignment“ einen grundsätzlich erkennbaren Ablauf einer Strukturanalysen vor, auf den sich [Meh05] genauer bezieht und ihn an diversen Systemen zeigt. Da Ontologien eine spezialisierte Struktur darstellen, ist das Ontology-Alignment eine Unterform der Struktur-Analyse und kann auf alle übrigen XML-Strukturen Anwendung finden.

Zwei Schemas aufeinander abzubilden bedeutet hierin, dass für jede Entität (Begriff, Relation, Instanz) des ersten Schemas die Entsprechung mit derselben Bedeutung im zweiten Schema gesucht wird. Es wird die 5-Tupel- Funktion align auf einem Vokabular E aller Entitäten $e\in E$ , d.h. Begriffe, Relationen und Instanzen und der Menge möglicher Schemata S als partielle Funktion $\begin{array}{}\text{align}:E\times O\times O\to E,\text{mit}\forall e\in E_{O_1}\exists f\in E_{O_2},O_{\mathrm{1,}}{O}_2\in O:\text{align}(e,O_{\mathrm{1,}}{O}_2)=f\vee \text{align}(e,O_{\mathrm{1,}}{O}_2)=\downarrow \end{array}$ angewendet.

1.Merkmalskonstruktion

In diesem Schritt werden die Merkmale einer Entität ausgewählt, welche sie treffend beschreiben. Dies kann ein lexikalischer Eintrag einer Entität sein, aber auch eine intensionale Struktureigenschaft wie die is-a Beziehung.Desweiteren werden extensionale Beschreibungen genutzt

2.Suchraumbestimmung

Zur Ableitung von Abbildungen in Strukturen wird ein Suchraum von Kandidaten aufgestellt. Ähnlich einer Blockingmethode stellt diese sinnvolle Kandidaten für einen Vergleich auf und sortiert alle übrigen somit aus.

3.Ähnlichkeitsberechnung

Hier werden die im Kapitel Datenharmonisierung vorgestellten Methoden, ebenso wie Ähnlichkeitsfunktionen für Einzelobjekte oder Objektmengen genutzt, um die Ähnlichkeit zweier Entitäten zu bestimmen.

4.Ähnlichkeitsaufsummierung

Im Allgemeinen werden dabei mehrere Ähnlichkeitswerte für ein Entitätenpaar errechnet, beispielsweise auf lexikalische Einträge oder Ähnlichkeit der Relationen zu anderen Entitäten. Es entspricht der in Kapitel Klassifikation näher vorgestellten Klassifikation.

5.Interpretation

Die Aufsummierten Ähnlichkeitswerte werden nun zur Abbildung der Entitäten aufeinander genutzt. Möglichkeiten dafür sind ein Schwellenwert, eine Mischung aus Struktur und Ähnlichkeitswerten oder Relaxation Labelling, welches Letztere mit weiteren Heuristiken mischt [semanticIntegration_glue]

6.Iteration

Um die Struktur des Schemas besser zu nutzen, wiederholt ein Algorithmus die beschriebenen Schritte.

Die grundsätzlichen Algorithmen der Stufen 2 bis 5 finden analog bei der Datenharmonisierung Anwendung, welche im Kapitel 3 näher vorgestellt wird. Jeder dieser 6 Schritte besitzt natürlich selbst eigene spezifische Methoden mit jeweils entsprechenden zu setzenden Parametern.

Eine Vielzahl von Applikationen und Frameworks haben dieses Vorgehen bereits fest umgesetzt. Es wird dabei oftmals zwischen Individual und kombinatorischen Systemen unterschieden. Während ersterer sich auf einen Algorithmus konzentriert, verwenden die Vertreter der zweiten Gruppe mehrere Algorithmen und gewichten die Teilergebnisse.

Grundsätzlich verwendete Methoden sind

• Heuristisch und Regelbasierte Methoden
• Graphenanalyse
• Maschinen-Lernen-Statistiken
• Probalistische Annäherung
• Reasoning

Es soll nun Auswahl aktueller, aussichtsreicher Vertreter folgen. Diese werden in [Meh05], [Cupid01] und [ChiunchigliaEtAl'04] näher evaluierter.

„Seamless Moell Integration“ als instanzbasiertes System assoziiert Attribute in beiden Schemen mit Treffer-Signaturen. Diese bestehen aus 15 constraint-basierenden und 5 content-basierenden Kriterien, welche von den Instanz-Werten abgeleitet und auf [0,1] normalisiert werden, so daß jedes Kriterium einen Wert in einem 20-dimensionalen Vektorraum einnimmt. Diese werden auf Grundlage ihrer Euklid-Distanz geclustert und ein neuronales Netz mit Ihnen trainiert, welches auf das zweite Schema angewendet wird. Hierbei handelt es sich um einen hybriden Elementlevel-Matcher, welcher die Schemastruktur nicht beachtet. [Cupid01]. Semint ist einer der ersten Anläufe, keine hartkodierten Kombinationen von individuellen regelbasierten Ähnlichkeiten zu nutzen, sondern statdessen einen auf Maschinenlernbarkeit basierenden Ansatz zu wählen, besitzt jedoch kein namens- bzw. graphenbasiertes Matching.

Dike ermittelt Synonym- und Inklusions-Beziehungen (is-a) eines EntityRelationship-Schemas. Objekte werden als ähnlich markiert, falls die damit verknüpften Attribute ähnlich sind. Als Ergebnis auf zwei ER-Schemata werden die Wahrscheinlichkeitswerte zwischen beiden, gemeinsam mit Synonymen und Inklusionen ausgegeben.

Cupid ist ein Mehrzweck-Schemamatcher, welcher mit hybriden Verfahren arbeitet. Er funktioniert sowohl element- als auch strukturbasiert, spezialisiert sich jedoch auf Ähnlichkeiten von atomaren Elementen, da dort viele Schemasemantiken aufzufinden sind. Laut [Cupid01] werden ebenso interne Strukturen erkundet, wobei deren Differenzen nur gering in die Gesamtklassifizierung einfließen. Der Gesamtablauf ist in 3 Stufen gegliedert, wobei im ersten Schritt Elemente (Knoten des Schemas) auf linguistische Eigenschaften verglichen werden, inklusive externen Abgleich von Synonymen. Für den zweiten Schritt, den strukturellen Ablauf, wird das Datamodell in eine Baumstruktur transformiert und Paare daraufhin anhand ihrer Blattknoten verglichen. Ein Ähnlichkeit wird durch den gewichteten Abgleich zwischen linguistischem und strukturellem Ergebnis ermittelt. In der dritten Phase entscheidet der Schwellwert (Threshold) über Übereinstimmung. Dieser Wert ist domänenabhängig und kann nicht im Voraus angegeben werden.

„Combination of Matching-Algorithms“ nutzt einen direkten, azyklischen Graphen, und arbeitet semiautomatisch mit Hilfe von User-Feedback. COMA befolgt ebenfalls einen Kompositions-Ansatz, welcher eine erweiterbare Bibliothek von verschiedenen Matchern zur Verfügung stellt und eine Vielzahl von Kombination der ermittelten Matching-Ergebnisse unterstützt. Hier finden ebenfalls zuvor errechnete Resultate wiederverwendung. Die Kompositionsstrategien adressieren verschiedene Aspekte des Matching-Prozesses, so z.B. die Aggregation von Matcher-spezifischen Ergebnissen und Match-Kandidaten-Auswahl. Schemata werden auch hier in gerichtete direkte azyklische Graphen transformiert, auf denen alle Algorithmen arbeiten. Jedes Schema ist unique identifiziert durch seinen kompletten Pfad von der Quelle des Schemengraphes bis zum korrepsondierenden Knoten.

COMA erzeugt auf Elementebene Übereinstimmungen von 1:1 lokaler und m:n globaler Kardinalität. Der Alignment-Prozess besteht auch hier aus 3 Phasen, die iterativ durchlaufen werden und wobei die erste stets eine User-Feedback-Dialog zum Einstellen verschiedener Parameter darstellt (e.g. Auswahl des entsprechenden Matchers/Annahme, Ablehnung eines entsprechenden Entwurfes.). Daraufhin werden die individuellen Ähnlichkeiten berechnet. Diese basieren meist auf linguistischen Informationen, nutzen ebenso im Hintergrund Wörterbücher und strukturelle Elemente as Kinder oder Blätter. In der dritten Phase werden die Matcher wiederum kombiniert, entweder durch ein Maximum, einer Gewichtung einem Durchschnitt oder einer MinimumStrategie. Verschiedene Annäherungen für Schwellwert-Determinationen werden gegeben. Es ist ebenso möglich, das Programm komplett automatisch zu betreiben.

S-Match ermittelt Annäherungen, um semantische Beziehung zwischen Klassen zweier Klassifikationsschemata abzuleiten. Diese werden dazu von einer Datenbank oder Ontologie extrahiert. Sie basieren auf Untersuchung der Labels m.H. von „Wordnet“ als Synonym- Thesaurus-Überprüfung. Es sind laut [ChiunchigliaEtAl'04] ebenfalls weitere Element-Matcher vorhanden. Zusätzlich kommt hier ein SAT-Solver zum Einsatz, welcher die Schemata untersucht und dabei vor allem die Taxonomie und geschlußfolgerte Implikationen ermittelt. Er gibt entweder Gleichheit, Untermenge oder Unabhängigkeit zwischen 2 Klassen zurück.

Auf den vorangegangen Seiten wurden Methoden und Vorgehensweisen zur Identifizierung von Bestandteilen eines unbekannten Schemas vorgestellt. Fünf konkrete Beispiele aus dem universitären Umfeld, welche (semi-) automatische Umsetzungen durchführen, erlauben mit Hilfe einer Vergleichsstruktur, lokale Komponentenschemata zu erkennen.

Mit diesem Strukturwissen kann ein Abfrageterm für Xcerpt generiert werden, welcher die entsprechenden Felder der Struktur gezielt ansteuert.

Instanzen der globalen Komponente werden dadurch extrahiert und über einen global identischen Konstruktionsterm zur Verfügung gestellt.

Auf diese Instanzen kann im nächsten Kapiteln transparent zurückgegriffen werden, und deren Inhalt semantisch angeglichen sowie abschließend untereinander verknüpft werden.