Globales Matching bezeichnet im Rahmen der Informationsintegration einen Prozess zur automatischen Abbildung verschiedener Schemas aufeinander (Schema-Matching). Dabei werden Ergebnisse aus verschiedenen Matching-Verfahren verwendet, um Attribute der zu matchenden Schemas tatsächlich aufeinander abzubilden.
Begriffsklärung Durch das Globale Matching wird versucht, die Attribute und Relationen verschiedener Schemas (im Allgemeinen zwei) miteinander in Beziehung zu setzen. Globales Matching kann daher auf zweierlei Arten verstanden werden. Globales Matching ist ein „normales“ Matching-Verfahren, das Attribute (ganze Spalten) miteinander matcht, Globales Matching ist andererseits ein Schritt, der aus den bereits gewonnenen Informationen tatsächliche Matches zwischen den Attributen (und Relationen) zweier Schemas generiert. Er versucht, möglichst die richtigen Matches auszuwählen, die zusammen ein möglichst gutes Mapping der beiden Schemas bilden.
Im Folgenden wird die zweite Interpretation behandelt. Da sich Globales Matching sowohl auf die Ergebnisse einfacher als auch auf Ergebnisse zusammengesetzter Matcher beziehen kann, lässt es sich nicht in die Kategorisierung des Schema Matchings einordnen.
Problemstellung Die Matchings zwischen zwei beliebigen Attributen zweier unterschiedlicher Schemas werden durch vorhergehende Matchingverfahren (z. B. Edit-Distance, (künstliche) neurale Netze oder Similarity Flooding) mit einer Wahrscheinlichkeit belegt. Die Schwierigkeit besteht nun darin, diejenigen Paare aus Attributen auszuwählen, die tatsächlich zusammengehören. Es reicht dabei im Allgemeinen nicht aus, jedem Attribut des ersten Schemas das Attribut des zweiten Schemas mit der größten Korrespondenzwahrscheinlichkeit zuzuordnen. Es können die folgenden Probleme auftreten: Mehrere Attribute des zweiten Schemas haben hinsichtlich eines Attributes des ersten Schemas die gleiche Ähnlichkeit. Eventuell sind sie sogar „echt“ semantisch ähnlich wie das folgende Beispiel zeigt. zentriert Statt 1:1-Matches gibt es 1:n-Matches, beispielsweise wenn Vorname und Nachname in einem anderen Schema als Attribut „Name“ zusammengefasst sind. Es müssen also genau die richtigen Attribute (ggf. sogar in der richtigen Reihenfolge und mit dem richtigen Konkatenationsoperator) ausgewählt werden. zentriert Einige Attribute dürfen vielleicht nicht gematcht werden, weil sie im anderen Schema keine Entsprechung besitzen. Die schiere kombinatorische Komplexität der möglichen Paarungen lässt die Berechnung lange dauern. Zudem erschweren es die tatsächlich gefundenen und dem Benutzer vorgeschlagenen Paarungen dem Benutzer, das Ergebnis zu bewerten. Das gilt insbesondere dann, wenn sich viele falsch positive Treffer darunter befinden.
Grenzen des Globalen Matchings Globales Matching zielt darauf ab, zwei Schemas aufeinander abzubilden und sich dafür der Hilfe verschiedener Matching-Verfahren zu bedienen, die die Ähnlichkeiten zwischen den Attributen ausgerechnet/geschätzt haben.
Die derzeit auf dem Markt verfügbaren Lösungen bieten häufig nur 1:1-Mappings an und verlassen sich auf strukturelle oder Namensähnlichkeiten. Sie lösen also nicht alle der zuvor geschilderten Probleme.
Workflow rechts|mini|Workflow beim Global Matching Im Folgenden wird der Workflow beim Global Matching gezeigt.
Gegeben sind zwei Schemas, die integriert werden sollen. In der Praxis könnte dabei das eine Schema das Quellschema sein, aus dem die Daten in ein Zielschema migriert werden sollen. Dies ist beispielsweise bei der Übernahme eines Unternehmens durch ein anderes Unternehmen denkbar. Das Schema des übernommenen Unternehmens wäre dabei das Quellschema, das andere entsprechend das Zielschema. Aus den entsprechenden Schemas werden die interessierenden Relationen und Attribute ausgewählt, beispielsweise ein Produktkatalog, während Kunden- oder Umsatzdaten ignoriert werden.
Im nächsten Schritt müssen die ausgewählten Attribute gematcht werden. Dazu wird eine bestimmte, nicht-leere Menge an Matchern ausgewählt, die die paarweise Ähnlichkeit der ausgewählten Attribute ermittelt. Die Matcher bedienen sich je nach Typ und Verfügbarkeit externer Daten wie beispielsweise Wörterbüchern oder den in der Datenbank abgelegten Typinformationen oder Fremdschlüsselbeziehungen.
Die Ergebnisse der Matcher werden in einer Ähnlichkeitsmatrix aufgestellt. Wurden mehrere Matcher benutzt, müssen die Einzelergebnisse gewichtet und gegebenenfalls normalisiert werden. Die Ähnlichkeitsmatrix gibt für jedes Attributpaar (gebildet aus je einem Attribut beider Schemas) an, wie gut/wahrscheinlich beide Paarteilnehmer semantisch zusammenpassen. Die Ähnlichkeitswerte müssen nicht notwendigerweise im Intervall [0, 1] liegen. Im Allgemeinen lässt sich die Ähnlichkeitsmatrix nicht durch Umsortieren der Zeilen oder Spalten in eine Einheitsmatrix umwandeln; Attributen aus dem einen Schema sind also meist mehrere Attribute mit einer gewissen Ähnlichkeit aus dem anderen Schema zugeordnet und umgekehrt. Durch Algorithmen wie dem Similarity Flooding kann die Ähnlichkeitsmatrix verbessert werden. Eine Ähnlichkeitsmatrix kann auch als Liste dargestellt werden, deren Einträge Tripel (Attribut1, Attribut2, Ähnlichkeitswert) sind.
Um die folgende Arbeit effizienter zu gestalten und die Anzahl der False Positives zu verringern, ist vor dem nächsten ein Zwischenschritt denkbar, der die Ähnlichkeitsmatrix filtert. Dabei können beispielsweise Schwellwerte für die Ähnlichkeiten festgelegt werden. Geringere Ähnlichkeiten werden als zu unwahrscheinlich angesehen und auf 0 gesetzt. Zudem können Typinformationen einbezogen werden, falls dies nicht durch die Matcher bereits erledigt wurde. Der Zwischenschritt mag implizit erfolgen, wenn die Zusammenfassung mehrerer Matchingverfahren durch einen kombinierenden Matcher erledigt wurde und er danach die Filterung intern vornimmt.
Aus der (nun möglicherweise ausgedünnten) Ähnlichkeitsmatrix werden anschließend Mappings gewonnen. Ein Mapping ist eine Auswahl eineindeutiger Zuordnungen zwischen Elementen beider Mengen, wobei es auch Elemente geben kann, die keinem Element der anderen Menge zugeordnet sind. Da im Allgemeinen immer noch keine bzw. nicht nur 1:1-Zuordnungen in der Ähnlichkeitsmatrix vorliegen, gibt es mehrere theoretisch denkbare Mappings. Die Ähnlichkeitsmatrix erzeugt also ein Multimapping, aus dem mehrere Mappings erzeugt werden können. Es gibt verschiedene Algorithmen, „gute“ Mappings auszuwählen. Sie werden im nächsten Abschnitt vorgestellt. Die durch die Algorithmen erzeugten Mappings werden dem Benutzer anschließend präsentiert.
Algorithmen Nachfolgend sollen einige Mapping-Algorithmen kurz erläutert werden. Sie versuchen jeweils, Paare aus Elementen zweier Mengen zu bilden, zu denen Metainformationen über die Wahrscheinlichkeit des Zusammenpassens (die Ähnlichkeitsmatrix) bekannt sind.
Stable Marriage Der Stable-Marriage-Algorithmus von Gale und ShapelyD. Gale und S. Shapely: “College Admissions and the Stability of Marriage.” The American Mathematical Monthly 69.1 (Jan., 1962): 9-15. versucht, zwei Elemente derart zusammenzubringen, dass sie mit ihrem der Wahrscheinlichkeit nach passendsten Pendant (also dem mit dem größten Wert) verbunden sind, das nicht selbst wiederum mit einem anderen Element mit noch höherer Wahrscheinlichkeit verbunden ist. Übertragen formuliert gibt es zwei Personengruppen, Männer und Frauen, wobei jede Person eine Rangliste von allen Personen des anderen Geschlechts besitzt. Die Personen werden nun so verheiratet, dass keine Person mit einer anderen verheiratet ist, die nicht die höchstmögliche Stellung in der Präferenzliste verbliebener Heiratskandidaten besetzt.
Elemente sind hierbei die kleinen Kreise, die jeweils zur Menge der gleichfarbigen Kreise gehören.
Dieser Algorithmus wird anhand des folgenden Beispiels erklärt. zentriert Der linke und der rechte Teil zeigen dieselbe Ähnlichkeitsmatrix.
Für den Algorithmus muss die Ähnlichkeitsmatrix in zwei Präferenzlisten umgewandelt werden, in eine „aus Sicht der blauen Menge“ und in eine „aus Sicht der roten Menge“. Dabei spielen die Zahlenverhältnisse keine Rolle, sondern nur die Reihenfolge. Die Reihenfolge entsteht durch ein Null-basiertes Abzählen der Elementindizes (A bzw. D haben beispielsweise den Index 0, C und F dagegen den Index 2). Die Präferenzlisten sehen folgendermaßen aus: „Präferenzliste der blauen Menge“ „Präferenzliste der roten Menge“ A: 2 1 0 D: 2 1 0 B: 1 2 0 E: 2 1 0 C: 0 1 2 F: 0 1 2 unter Auflösung der Indizes: „Präferenzliste der blauen Menge“ „Präferenzliste der roten Menge“ A: F E D D: C B A B: E F D E: C B A C: D E F F: A B C
Diese Umwandlung ist nicht eindeutig, die Präferenzliste von C hätte auch 1 0 2 lauten können. Eine konkrete Implementation muss sich für eine Variante entscheiden. Ein weiterer Indeterminismus bleibt bestehen, da „Frau D und Frau E in der gleichen Reihenfolge um die Männer konkurrieren“. Mit anderen Worten: Die Reihenfolge der Attribute ist für das Ergebnis relevant.
Nachdem die Präferenzlisten erstellt wurden, kann der eigentliche Algorithmus beginnen. Dabei werden die Attribute der einen Menge durchgegangen. Die jeweils „best-passendsten“ Attribute des anderen Schemas werden als Match vorgemerkt. Dabei kann der Fall auftreten, dass ein Attribut bereits vorgemerkt ist, bei einem anderen aber in der Präferenzliste an vorderster Stelle steht. Um diesen Konflikt zu lösen, wird in der Präferenzliste des strittigen Attributes nachgesehen, welches der beiden konkurrierenden Attribute die höhere Ähnlichkeit hat. Ist es das bereits vorgemerkte, ändert sich nichts und es wird versucht, das „unterlegene“ Attribut gegen das nächste in seiner Präferenzliste zu matchen. Besitzt das dritte Attribut jedoch bezüglich des zu matchenden Attributes eine höherwertige Stelle in der Präferenzliste, wird diese Paarung vorgemerkt und die alte vorgemerkte Paarung gestrichen.
Eigenschaften Ein Stable-Marriage-Mapper erfordert eine gleiche Anzahl an Attributen im Quell- und Zielschema und mappt die beiden Schemas vollständig. Dabei erzeugt er 1:1-Mappings.
Er ist mehrdeutig beim Erstellen der Präferenzlisten und auch beim Abwickeln der Paarbildungen, bei der es auf die Reihenfolge ankommt. Er wählt für jedes Attribut das bestmögliche Mapping aus.
Maximum Weighted Bipartite Graph Matching Die Ähnlichkeitsmatrix kann auch als Graph verstanden werden, der bipartit ist (zwei Knotenarten), ungerichtet und gewichtet. Dieser soll transformiert werden in einen Graphen, der zudem noch unzusammenhängend ist, in dem also gerade genau zwei Knoten miteinander verbunden sind. Dazu müssen lediglich „die richtigen“ Kanten des ersten Graphen ausgewählt und in den zweiten Graphen übernommen werden.
Der Maximum-Weighted-Bipartite-Graph-Matching-Algorithmus (z. B. umgesetzt durch den Ungarischen Algorithmus) versucht, die Summe der Gewichte der „aktivierten“ Kanten zu maximieren, was übertragen auf das Hochzeitsproblem einer Maximierung der Gesamtzufriedenheit entspricht, auch auf die Gefahr hin, Einzelpersonen untermaximal zufriedenzustellen.
Dafür müssen zunächst die Werte der Ähnlichkeitsmatrix in Distanzmaße umgewandelt werden, beispielsweise, indem man die jeweilige Ähnlichkeit von eins abzieht. Anschließend wird von jeder Zeile das Zeilenminimum abgezogen, dann von jeder Spalte das Spaltenminimum. Dadurch ergeben sich zwangsläufig Nullen. Diese Nullen werden durch einen oder mehrere gedachte Balken abgedeckt, jedoch mit so wenigen wie möglich. Stimmt die Zahl der Balken mit der Anzahl der Attribute überein, wird zeilenweise die darin enthaltene Null gesucht. Gibt es nur eine Null, definiert sie den Match der beiden Attribute. Zeile und Spalte werden gelöscht. Gibt es mehrere, wird sie zunächst ausgelassen und mit der nächsten Zeile fortgefahren. Anschließend wiederholt sich der Ablauf für Spalten.