Home

- Fachgebiet Datenbanken und Informationssysteme

1. Ein wertabh ngiger Fehler hat zur Folge dass Attributwerte in gleichbedeutender aber schriftlich abweichender Form auftreten Das Auffinden solcher Fehler ben tigt ein Grund wissen ber den korrekten Inhalt des Attributes Dieses kann entweder aus den Attribut werten abgeleitet werden oder muss vorgegeben werden Dabei kann man sich die Ei genschaft zu Nutze machen dass solche fehlerhaften Attributwerte sich wie Duplikate verhalten Das hei t dass sich innerhalb der Attributwertmenge Gruppen hnlicher Wer te bilden lassen So w re zum Beispiel Hans und Hnas ausreichend hnlich um ein Duplikat darzustellen Zur Behebung solcher Fehler kann dann zum Beispiel das Refe renzwertverfahren angewendet werden Siehe dazu Abschnitt 2 4 1 Aus einer Reihe von Attributen ergibt sich schlie lich der Datensatz oder formaler Das Tupel Dieses stellt eine Datenzeile einer Tabelle oder Relation dar Ein typischer Fehlerfall sind gleichbedeutende Tupel die sich geringf gig in der Belegung der Attribute unterscheiden So k nnen im Falle von Abweichungen in den Attributwerten zum Beispiel Attributwertfehler vorliegen hnlich den wertabh ngigen Attributwertfehlern ergeben sich Duplikate von Tupeln Zur Auffindung muss hierbei aber die hnlichkeit ganzer Tupel verglichen werden Die Korrektur dieser erfordert wiederum die Bereinigung der einzelnen Attributwerte zwischen den duplizierten Tupeln Dazu kommt f r Tupel das Me
2. Verwaiste Schl ssel treten in der Regel nach nicht kaskadierten d h nachgef hrten L schoperationen auf Das Beheben solcher Fehler sollte nach Abschluss aller L schvor g nge erfolgen damit also als letzte Instanz beim Bereinigen einer Tabelle Duplikate sind vor allem in verbundenen Tabellen ein Ausl ser f r verwaiste Schl ssel Damit ein Duplikat allerdings zustande kommen kann muss bereits eine Abweichung auf der Attribut Ebene vorliegen Betrachten wir erneut das Beispiel aus Abbildung 2 1 ist hier vor der Behandlung des Verweises die Korrektur des Duplikates in der jeweiligen Tabelle mit Hilfe der Attribut Ebene vorzunehmen Durch die Korrektur des Duplikates m ssen hier nun die Verweise der ersten Tabelle dem neuen Stand der referenzierten Tabelle angepasst werden Attributwertfehler sind die h ufigste Ursache f r Duplikatbildung und treten schon durch geringe Abweichungen bei der Daten bernahme auf Dabei sei zu bemerken dass wertabh ngige Fehler die zu Duplikaten von einzelnen Attributwerten f hren nicht zwangsl ufig zu einem duplizierten Tupel f hren So brauchen zwei Tupel die lediglich ein Attribut mit wertabh ngigem Fehler gemein haben kein Duplikat auf der Tupel Ebene sein Der Fehler selbst kann aber durchaus ein Duplikat auf Attribut Ebene darstellen Dies kann zum Beispiel durch einen Tippfehler eines h ufig vorkommenden typischen Attributwertes f r dieses Attribut geschehen F r di
3. Attribut Ebene Wir betrachten f r jedes Attribut eines Tupels seine Menge an Attri butwerten in der Tabelle Der Datentyp das Eingabeformat und der Dom nentyp seien uns bekannt Da Format also wertunabh ngige Fehler direkt korrigiert werden k nnen soll hier bevorzugt die Bereinigung von Fehlern die einen hnlichkeitsvergleich ben tigen betrachtet werden Aus den Attributeigenschaften leiten wir nun ein geeignetes hnlich keitsma ab Nach der Wahl des hnlichkeitsma es vergleichen wir jede Kombination von Attributwertpaarungen die sich aus der Menge bilden lassen und bestimmen deren hnlichkeitsfaktoren Paare deren Faktoren auf eine hohe hnlichkeit schlie en lassen bestenfalls so dass man von einer Gleichheit ausgehen kann werden nun mit einem Re ferenzwert abgeglichen Anhand eines solchen Wertes wird entschieden welche Eingabe des Attributwertes als die korrekte Eingabe anzusehen ist Es stellt sich der folgende Plan dar Fehlererkennung F r jedes Attribut W hle hnlichkeitsma fertig falsch Solange noch nicht fertig fertig wahr F r jedes Wertepaar der Attributwertmenge Erzeuge hnlichkeitsfaktor Wenn Faktor hoher hnlichkeit aber nicht identisch entspricht Fehlerkorrektur fertig falsch 10 KAPITEL 2 GRUNDLAGEN Ermittle Referenzwert nach Abschnitt 2 4 1 Wende Korrektur durch Referenzwert an Auflistung 2 1 Bereinigung wertabhangiger Fehler der Attribut Ebene De
4. GB Helpert addToPanet anchorBottornt anchorlenter anch rleftl anch orkightl anchor Top anchor Topl emt anchor TopRight tillBothl fillHorl tiler noF ill resetGBly resetGridsizel resettlargin resetPad resetyVeigtht setGridxi setcrid YC setGridheight setGridwictht setliPadsx setiPady C setinsets sethlarginBottome setM arginLeftil setlarginRight sethiarginTope setyVeight i Sefvveichd dt Abbildung 7 4 Klassendiagramm 2 von Paket View Die abstrakte Klasse Init View ist die generische Instanz eines Fensters im Paket View Sie implementiert Prozeduren durch die komplexe Fensterkonfigurationen vereinfacht werden Dies erm glicht durch die Ableitung von der generischen Instanz die Konfigu ration von Fenstern unabhangig von deren zugrunde liegenden Datentyp Die Klasse InitFrame erzeugt ein JFrame Fenster Die Klasse InitIFrame erzeugt ein JInternalFrame Fenster Die Klasse InitDialog erzeugt ein JDialog Fenster Die Klasse GBCHelper erzeugt ein GridBagLayout und vereinfacht das Positionie ren der Elemente durch zus tzliche Hilfsprozeduren Neben dem Grundgedanken das GridBagLayout vereinfacht konstruieren zu k nnen ist es mit dieser Klasse m glich die Layoutgenerierung zu vereinheitlichen 7 2 ENTWURF UND AUFBAU 19 7 2 2 3 Paket Configuration 3 FrameworkCFG Be FrameaorkC FG B addfrocess ka ClesarC ur ster a getCurstatel getDbHostl getDbPort
5. Name und erkannt wird Hans und Hans Ersteres Tupel enth lt aber leere Attributwerte w hrend das zweite Tupel noch eine Adressinformation beinhaltet Nach dem beschriebenen Vorge hen w rden alle Attribute des ersten Tupels ohne Nachfrage angepasst Auf diese Tupel verweisende Tupel k nnen hingegen v llig unterschiedlich sein Da auf Tupel Ebene nicht die Beziehung bewertet wird kann als Schutzma nahme bei einer solchen Erkennung eine Interaktion eingefordert werden 2 5 Bibliographischer Datenbestand des DBIS Die in dieser Arbeit vorgestellten Werkzeuge sollen auf die bibliographische Datenbank vom Fachgebiet Datenbanken und Informationssysteme angewendet werden Dazu stellen wir hier zun chst den Aufbau der Datenbank vor und erl utern die Besonderheiten an denen die Werkzeuge angepasst werden m ssen 2 5 BIBLIOGRAPHISCHER DATENBESTAND DES DBIS 17 Abbildung 2 2 Entity Relationship Model Aus Griinden der Ubersichtlichkeit wurden die Attribute der Tabellen nicht in die Ab bildung 2 2 mit aufgenommen Die relevanten Attribute werden im Folgenden erlautert Dazu wahlen wir zunachst die am haufigsten von Fehlern betroffenen Tabellen aus dem Schema Die Eintr ge der Tabelle Schrift stellen die prim ren Eintr ge f r Schriftst cke dar Ein Schriftst ck muss dabei mindestens einen Titel und einen Schrifttyp haben Die relevanten Attribute und die typischen Fehlerf lle dieser
6. werden sowohl C und D als auch anschlie end A und B erkannt Es ergeben sich also folgende Einf gungen zur Auflistung 2 2 Fehlererkennung Stelle Tabelle zur ck und Bereinige eventuelle referenzierte Tabellen Fehlerkorrektur Korrigiere verwaiste Schl ssel in referenzierender Tabelle Auflistung 2 3 Einf gungen zur Bereinigung von Verweisen Betrachtet man die Ablaufpl ne der Attribut und Tupel Ebene stellt man fest dass bei de eine gewisse hnlichkeit aufweisen So ist beiden gemeinsam dass die Attributwerte bewertet werden und dass Paare gebildet werden die iterativ ausgewertet werden Nun ist dieser einfache Ansatz zwar sicher funktional bei hohem Datenvorkommen aber lauf zeittechnisch sicher nicht w nschenswert Es stellt sich die Frage ob sich Verfahren finden lassen die diese Iterationen vermeiden oder vermindern So kann man beispielsweise Paa re mit hoher hnlichkeit gruppieren Mit zus tzlichen Verbesserungen findet sich dieser Vorschlag in der Literatur unter dem Begriff Clustering F r solche Verbesserungen siehe auch Bra07 Betrachten wir Attribut und Tupel Ebene noch einmal in Hinblick auf diese Paarbildung f llt auf dass sowohl das Auffinden von duplizierten Tupeln als auch von Attributwerten einen identischen Vorgang durchf hren In der Tat k nnen wir erkennen dass das Auffinden von hnlichen Attributwerten sich verh lt wie das Auffin den von duplizierten Tupeln wenn wir
7. 2 2 2 2 om En 18 Zeichendreher mit o 21 Austausch von zwei Zeichen mit g 21 un hnliche Zeichenfolge mit o 21 un hnliche Zeichenfolge mit g 21 un hnliche Zeichenfolge mit Field Similarity 22 Beispiel f r Dreiecksungleichung nach PC Filter 2222222 26 Benutzerinteraktion im Ausf hrungsblock 38 Beispiel f r Differenzbetr ge 2 2 CC a a 48 Modifizierte Field Similarity f r S tze 2 2 oo m rn 50 Modifizierte Field Similarity f r Zeichendreher 2 ol Modifizierte Field Similarity f r Name Vorname Kombinationen Su Modifizierte Field Similarity bei gleichem Zeichenvorrat ol Ersetzung von Werten durch wertunabh ngiges Verfahren 85 Auswertung der Ersetzungstabelle e 87 103 104 ABBILDUNGSVERZEICHNIS Listenverzeichnis 2 1 2 2 2 3 3 1 3 2 4 1 5 1 1 1 1 2 1 3 1 4 1 0 Bereinigung wertabhangiger Fehler der Attribut Ebene 10 Bereinigung auf Tupel Ebene 0 0 000008 10 Einf gungen zur Bereinigung von Verweisen 11 Allgemeine Dreiecksungleichung 2222 a nn 25 Dreiecksungleichung nach PC Filter 2 2 2 2 2 En nn 25 Zusammenfassung der Modifizierte Field Similarity 2 2 2 2 52 Aufruf auf Kommandozeile 2 2 Co Co oo on 56 Merging Clusterbildung 2 Cm non 87 Referenzwert automatische Bildung 2 2 2 m mn nn 88 Implementierung Atomic Strings
8. Am einfachsten ist hierbei das Weglassen von Trennzeichen und die Umrechnung in das 13 stellige Format Der boolsche Vergleich wird angewendet da die Eintragungen der ISBN selten invalide sind Die ISBN kann damit direkt als Kriterium zum Unterscheiden zweier Schriften genutzt werden Dieses Ma ist n tig da es h ufig vorkommt dass die ISBN in verschiedenen Eingabeformaten eingetragen wurde Wurde zuvor nicht der ISBN Pr fer angewendet kann daher nicht direkt mit dem boolschen Vergleich gearbeitet werden 4 8 PROZESSUNTERBRECHUNG 53 4 8 Prozessunterbrechung Eine gew nschte Eigenschaft ist den Bereinigungsprozess unterbrechen zu k nnen um ihn sp ter erneut wieder aufzunehmen Dazu m ssen folgende Bedingungen erf llt wer den e Die aktuelle Position der Abarbeitung muss bekannt sein Prozesszustand e Werkzeuge m ssen unterbrechenbar sein e lempor re Daten die ein Werkzeug ben tigt m ssen persistent gespeichert sein Die erste Bedingung wird dadurch erf llt dass die Abarbeitung der Werkzeuge der Prozessliste folgt und zudem der Controller so konzeptioniert ist dass jede Model Operation einzeln angesto en werden muss Dadurch l sst sich der genau Zustand proto kollieren Dies wird mit dem F hren des Prozesszustandes wie in Abschnitt 4 3 erreicht Nach Erhalten des Pause Signals muss der Prozessblock die Abarbeitung der Prozessliste bzw des aktuellen Werkzeuges unterbrechen Eine Unterbrechung k
9. d een 1 9 ee Z 15 0 75 0 5 lt 0 75 lt 1l vgl 3 4 4 7 HNLICHKEITSVERFAHREN 51 Beispiel 4 4 Modifizierte Field Similarity f r Zeichendreher e A Hans Muster B Muster Hans K 4 Nach boolschen Vergleich A Muster B Muster W rter mit identischen Gegenst cken 2 hnlichkeitsfaktoren nach Field Similarity Muster 2 Muster I 2 2x L_ 7 0 93 K 4 Beispiel 4 5 Modifizierte Field Similarity fiir Name Vorname Kombinationen e A Heinz B Hinze k 2 Nach boolschen Vergleich A Heinz B Hinze W rter mit identischen Gegenst cken J 0 hnlichkeitsfaktoren nach Field Similarity Heinz 1 Hinze 1 nach Anwenden von g 2 auf alle W rter mit hnlichkeitsfaktor 1 Heinz Hinze T 04 32 425 0 40 6 40 6 1 2 I 12 ze z gt 06 Beispiel 4 6 Modifizierte Field Similarity bei gleichem Zeichenvorrat Field Similarity auf die Eingabezeichenketten des Beispiels 4 5 angewendet f hrt zu einem Faktor von 0 916 Da 0 916 lt 0 93 liefert das modifizierte Verfahren eine bessere Erkennung der Identit t der Aussage auf Ebene der Domaine beider Zeichenketten vgl 3 3 Anhand des Beispiels 4 6 k nnen wir sehen dass mit dem modifizierten Verfahren un hn liche Zeichenketten mit gleichem Zeichenvorrat nicht mehr als identisch bewertet werden Zudem zeichnet sich durch die Beispiele
10. re Tabellen keine Interaktion Liste mit Tupeln dessen gew hlte Attribute Nullwerte haben Ziel des Werkzeuges ist es dem Benutzer alle Tupel anzuzeigen die in den gew hlten Attributen Nullwerte haben Teil der Interaktion ist es einem oder mehreren dieser Tupel f r die Attribute Werte zu spezifizieren 4 5 Mergingverfahren Hier wird die Funktionsweise des Merging n her konzipiert Das Merging ist ein Verfahren der Fehlerkorrektur und wird von Werkzeugen im Zusammenhang mit Duplikaterkennung auf Tupel Ebene aufgerufen Wie schon in 4 4 beschrieben hat auch das Mergingverfahren beschreibende Eigenschaften Parameter Duplikattabelle siehe 4 4 1 1 Attributeigenschaften Grenze f r Cluster korrektur zus tzliche Optionen f r Referenzwertverfahren siehe 4 6 Ausgabe keine Tempor re Tabellen Ersetzungstabelle Interaktion Clusterkorrektur Referenzwert Beim Merging gehen wir von einem Cluster von mindestens zwei Tupeln aus Dies ist bei Verbindung mit PC Filter als Erkennungsverfahren bereits gr tenteils geschehen Es bedarf lediglich dem Filtern der jeweiligen Cluster aus der Duplikattabelle durch geschickte Selektierung Der erste Schritt ist daher das Selektieren von Clustern Wir gehen nun die Cluster durch und f hren die folgenden Schritte aus 46 KAPITEL 4 KONZEPTION Die Tupel des Clusters werden Attributweise durchlaufen F r jedes Attribut wird das Referenzwertverfahren angewendet D
11. und kann dann zur Fehlerkorrektur verwendet werden 30 KAPITEL 3 AUSGEWAHLTE VERFAHREN Kapitel 4 Konzeption In diesem Kapitel wird ein Konzept fiir eine Werkzeugsuite zur Datenbereinigung einer Oracle Datenbank vorgestellt 4 1 berblick In den vorherigen Kapiteln haben wir Verfahren vorgestellt die spezielle Teilbereiche der Datenbereinigung abdecken In diesem Kapitel sollen nun Werkzeuge entwickelt werden die den Benutzer bei der Datenbereinigung unterst tzen Dazu definieren wir zun chst das Werkzeug als ein Instrument dass Verfahren einsetzt um ein h heres Ziel zu errei chen So setzt zum Beispiel ein Werkzeug zur Duplikatsbereinigung die Verfahren zur Duplikatserkennnung Verfahren zur Erzeugung von hnlichkeitsfaktoren und das Mer gingverfahren ein mit dem Ziel Duplikate aus der Datenbank zu entfernen Damit der Benutzer solche Werkzeuge verwenden kann bedarf es einer Schnittstelle Diese stellt das Anwendungsprogramm dar Dieses Programm verwaltet die n tigen In formationen die die Werkzeuge ben tigen und l sst den Benutzer mit den Werkzeug interagieren Das Anwendungsprogramm ist damit ein Framework f r Werkzeuge Durch die daraus resultierende Zentralisierung der Werkzeuge ergibt sich die Werkzeugsuite die im Folgenden vorgestellt wird Ein wiederkehrendes Detail wird die Unterbrechbarkeit der Werkzeuge sein die nach 1 2 gefordert wird Dieses Thema soll im Abschnitt 4 8 ausgef h
12. 3 1 Aus der UB und dem LB lassen sich die Eigenschaften 1 und 2 konstruieren Dabei sei G die vorgegebene Genauigkeit 3 5 PC FILTER 27 1 Wenn LBg A C gt G dann ist A und C ein Duplikat kleinster Abstand berschreitet Grenze 2 Wenn UBg A C lt G dann sind A und C kein Duplikat gr ter Ab stand unterhalb der Grenze Partitionen ordnen wir ein in innere und u ere Partitionen Dabei sind alle die Partitio nen zu denen ein Tupel R nicht geh rt Teil der u eren Partitionen von R Vergleichen wir nun ein beliebiges Tupel R mit einer Partition gelten die Eigenschaften 3 und 4 Dabei definieren wir je ein Tupel einer Partition als den so genannten Anchor Record AR Es bietet sich an das mediane Tupel einer Partition zu w hlen MinSim sei dabei definiert als die kleinste hnlichkeit zwischen dem AR und allen Datens tzen der Partition zu dem AR geh rt 3 Wenn Sim R AR MinSim 1 gt G dann ist R definitiv Duplikat zu allen Datens tzen der Partition folgt aus Ungleichung vergleiche Definition von LB 4 Wenn f r jedes Tupel D der Partition gilt 1 min Sim R AR Sim D AR lt G dann ist R kein Duplikat zu einem Datensatz aus der Partition vergleiche Definition von UB Mit diesen Vorbemerkungen k nnen wir die einzelnen Schritte ausf hren Schritt 1 Sortieren Die Datenbank bzw im folgenden zur Einfachheit auf Tabelle reduziert wird nach einem oder mehrer
13. Dies ist n tig um sicherzustellen dass der Wert defini tiv der dominanteste Wert der Menge ist so dass eine Fehlentscheidung f r die Menge vermieden wird Es kann ebenfalls die hnlichkeit zwischen dem so ermittelten Wert und den brigen Attributwerten verglichen werden um Fehlentscheidungen in Einzelf llen zu vermeiden Kombinationen dieser Ans tze sind m glich So kann der Auswertung vorgegebener Re ferenzwerte die automatische Ermittlung folgen K nnen die jeweils vorgestellten auto matischen Verfahren keinen Referenzwert ermitteln zum Beispiel durch Nichterreichen einer Mindesth ufigkeit muss der Benutzer entscheiden 2 4 VERFAHREN ZUR FEHLERKORREKTUR 15 2 4 2 Merging Auf der Tupel Ebene kommt man schnell zu der Frage welches Tupel denn das Duplikat und welches das Original ist In manchen Fallen gibt es darauf keine explizite Antwort So hat Tupel A eine abweichende Belegung vom als Duplikat erkannten Tupel B bei gleich hohem Informationsgehalt Mit einer gr eren Anzahl duplizierter Tupel k nnen auch sporadisch g nzlich abweichende Attributwerte auftreten Dieses Problem so weit wie m glich automatisch zu beheben ist Aufgabe des Merging Das Merging behandelt hnlich zum Referenzwertverfahren eine Menge von Tupeln mit hoher hnlichkeit also ein Cluster von duplizierten Tupeln Es wird f r alle Tupel die Attribute durchlaufen Es ergeben sich also Mengen an Attributwerten Dabei k nnen folgende F lle
14. Hier soll kurz auf den Zusammenhang zwischen dem Prozesszustand der Prozessliste ei ner Interaktion und der Unterbrechung eingegangen werden Eine Interaktion stellt nach 4 3 eine Exception dar Die Natur einer Exception ist das Unterbrechen eines Ablaufs Nun wird eine Interaktionsanfrage nicht zuf llig sondern an genau definierten Stellen ge neriert N mlich dann wenn der Prozess angehalten werden kann ohne dass dadurch Daten verloren gehen Die Interaktion verh lt sich in diesem Zusammenhang wie eine Unterbrechung Aus dieser Erkenntnis k nnen wir ableiten dass sowohl die Unterbre chung als auch die Interaktion den Prozess durch die Informationen des Prozesszustandes fortsetzt Ein Werkzeug wird allgemein durch die runTool Methode gestartet In dieser Metho de wird ebenfalls entschieden die Ausf hrung anzuhalten Daraus resultiert dass diese Methode anhand des Prozesszustandes den Einstiegspunkt in die Ausf hrung des Werk zeugs bestimmt Die Prozessliste sei implementiert als Liste von Prozessen Prozesse haben eine Identi fikation In einem Prozess wird ein Werkzeug ausgef hrt Ein Werkzeug hat ebenfalls eine Identifikation Wir k nnen folgern dass in der Prozessliste eine Prozess Id auf eine Werkzeug Id verweisen sollte Des Weiteren haben Werkzeuge spezifische Einstellungen die sich zwischen Prozessen unterscheiden Die Werkzeugeinstellungen geh ren nicht dem 7 4 IMPLEMENTATION VON WERKZEUGEN 83
15. KAPITEL 7 IMPLEMENTIERUNG 7 2 1 Pakettibersicht l H default package bret Biain v iev Ke Controler Imports Configuration l configuratio imports Configuration Import Teol Gli Importe a tools Supplies Tool Dala og connectior Abbildung 7 1 Paket Diagramm Das Paket default package enth lt den Programmeinstiegspunkt also die Startklas se Von hier werden die Konfiguration und die Oberfl che initialisiert Das Paket View beinhaltet die Klassen zur Darstellung der Bedienoberfl che und stellt also die View dar Das Paket Configuration beinhaltet die Controller Strukturen und stellt den Konfigurations und Initialisierungsblock dar Es verwaltet die internen Speicherstrukturen und f hrt die Konfigurations und Prozessliste Die Werkzeuge registrieren sich an der Konfiguration und sind dann im Projekt f r andere Pakete sichtbar Als Hilfsprozeduren stellt es die Kommunikation mit der Datenbank bereit Das Datenbankverbindungsobjekt wird dabei mit der Konfiguration zusammen initialisiert und durch die gespeicherten Verbindungs daten konfiguriert Das Paket Connection ist ein Unterst zungspaket f r den Controller und beinhaltet Klassen zur Datenbankkommunikation wie das Datenbankverbindungsobjekt Das Paket Tools beinhaltet die Werkzeugklassen Dies umfasst die Funktionsbl cke der Benutzerebene und abh ngig vom Werkzeug die Vorbereitung des Model Teils des
16. MVC Musters Die Klassen des Pakets Tools behandeln ausschlie lich die werkzeugre levanten Operationen Kommunikation mit den Werkzeugen erfolgt ber dieses Paket Damit Werkzeuge dem Projekt bekannt gemacht werden m ssen diese sich an der Kon figuration angemeldet haben Die Datenbankanfragen werden ber die aus dem Paket 7 2 ENTWURF UND AUFBAU Configuration importierten Datenbankobjekte abgewickelt F r die Anzeige der werk zeugrelevanten Oberflaschen stellt es dem Paket View die notwendigen Informationen zur Verf gung 17 2 2 Klassen bersicht Dieser Abschnitt soll eine bersicht ber die f r den Programmaufbau relevanten Klassen geben und diese kommentieren 7 2 2 1 Startklassen 3 Main 3 confiquration Controller H on ciglontroller ge dbonn og startview op fwContig B o a maint i simList Oa toolBox 3 view FrmMainWiew E Frmblainview e Controler addToolt a clearlonfigl a clear ToolContigh actionPerformed P closeDBO OO addComponents af connectDB W eo c fillattrList OO hreakProcess e getDbLiser checklonfigbepthl P getF Config OO Check OO om ei yet SimListr oO checkProcessList o createMenust ACCESS gt amp getSimplequeryArray disableContigt getTool OO disableProcess d getToalarray enableBreak getToolbox OO erable oo e getTooloptionst enableResumec e isonnected o enableRunt loadContig endPr
17. R ckmeldung des SQL Befehls weitergeleitet 4 2 ARCHITEKTUR 33 Fur die Teilblocke der Benutzer und Verarbeitungsebene kann das aus der Software technik bekannte Model View Controller Muster angewendet werden In Abbildung 4 1 ist eine m gliche Zuordnung hervorgehoben Das Ansto Prinzip erfordert eine Ablaufsteuerung die die Kontrolle ber die Werk zeuge bernimmt Zudem bedarf es Vorgaben nach denen die Anwendung reagiert Diesem Modell nach entfallen solche Einstellungen und die Ablaufsteuerung auf die Be nutzerebene Die anfallenden Einstellungen beinhalten dabei die globalen Anwendungs einstellung als auch die spezifischen Werkzeugeinstellungen Die Gesamtheit dieser Ein stellungen bezeichnen wir als Konfiguration Da Werkzeuge f r den Benutzer nur verf g bar sind wenn diese sowohl der Verarbeitungsebene als auch der Benuterebene bekannt sind k nnen wir eine Rahmenstruktur f r die Einbindung von Werkzeugen zur Verf gung stellen Dieser Framework organisiert und verwaltet die Konfiguration und sorgt f r die Ausf hrung der Werkzeuge gem der Ablaufsteuerung 4 2 1 Anwendung des MVC Musters Das View Element des MVC Musters ist f r die graphische Darstellung der Interakti onsschnittstellen zust ndig Dessen Interaktionen werden vom Controller ausgewertet und die Operationen des Model angesto en die auf Datenquellen zugreifen Dies ent spricht bereits gr tenteils der zu
18. Tabelle sind e Autor Formatabweichung Nachnamel Vornamel Nachname2 Vorname etc abweichende Eingabereihenfolge der Co Autoren e Titel Abweichende Titelbezeichnung Die Eintr ge der Tabelle FLit stellen weitere Informationen zu einem Schriftst ck bereit Darunter auch die ISBN Verlag und Erscheinungsjahr sowie Ort e ISBN Uneinheitliches Format 10 oder 13 stellig Trennzeichen e Verlag Mehrfachnennung von Verlagen durch geringe Unterschiede und Abk rzun gen e Ort Mehrfachnennung von Orten durch geringe Unterschiede und Abk rzungen e Sprache Vereinzelt Nullwerte zwar zul ssig aber meist hat ein Schriftst ck eine Sprache Die Tabelle Schlagwort stellt zu Schrift Schlagw rter als Suchbegriffe bereit Aufgrund der Schl sselbeziehung sind Schriftst ck und Schlagwort immer eindeutig Das heist dass es zu einem Schriftst ck kein doppeltes Schlagwort gibt Das Schlagwort Attribut jedoch kann unterschiedliche gleichbedeutende Eingaben enthalten Folgendes Beispiel ist w hrend der Erstellung dieser Arbeit in der Datenbank zu finden 18 KAPITEL 2 GRUNDLAGEN Schrift 12896 Schlagwort view update Schrift 12899 Schlagwort view upadtes Beispiel 2 2 Dupliziertes Schlagwort Die Tabelle Person ist ein Personenverzeichnis verschiedener Personen der Universitat Als Teilmenge davon werden in der Tabelle Mitarbeiter die Mitarbeiter des Fachgebiets aufgenommen Die Personeneintr ge
19. Tupel Duplikatbereiniger eingestellt 5 2 HAUPTOBERFLACHE KONFIGURATION 63 Prozessliste Tabellen 1 A Ersetzer PLPERSON NAME wolski gt Wolski BIPERSON 2 T Tupel Duplikatbereiniger PLSCHRIFT WI Wahlen Verf gbare Attribute ANREDE BMK EMAIL HOMEPAGE u LISTE Hinzuf gen NAME PERSON TITEL Gew hlte Attribute NAME Entfernen VORNAME Attributgewicht 5 M Sortieren nach PERSON Erweiterte Optionen Partitionen if D Randbereich 4 6 Genauigkeit Referenzwerte Verweise D Ubernehmen Abbrechen Fertig Abbildung 5 10 Werkzeugeinstellung Tupel Duplikatbereiniger Die Abbildung 5 10 zeigt das Panel in voller Ausdehnung Beachten Sie dass auf kleineren Bildschirmen Bildlaufleisten angezeigt werden Das erste Feld fordert Sie auf eine der Tabellen aus Ihrer Tabellenkonfiguration 5 2 2 zu w hlen Anschlie end w hlen Sie die Attribute anhand derer nach Duplikaten gesucht werden sollen und f gen Sie mit der Schaltfl che Hinzuf gen der Attributliste hinzu Attributen in der Attributliste kann ein Gewicht zwischen 0 und 10 zugeordnet werden Dieses Gewicht gibt an wie hoch der Einfluss des hnlichkeitsfaktors des Attributes f r die Gesamtbewertung ist Ein Gewicht von 10 ist dabei der st rkste Einfluss Das Fel
20. Umsetzung des Verfahren innerhalb der Werkzeuge ist von der Aufgabe des Werkzeuges abh ngig Als Beispiel sei die Fallunterscheidung zwischen Tupel und Attribut Ebene im Abschnitt 4 5 erw hnt Aus Benutzersicht ist eine gew nschte Datenbereinigung eine Black Box In dieser Werk zeugsuite setzt sich eine solche Datenbereinigung aus einzelnen Werkzeugen zusammen die jedes f r sich eine Bereinigung ausf hrt Das Ziel ist es dem Benutzer zu erm g lichen seine eigene Vorstellung einer Datenbereinigung zu konfigurieren indem er die gew nschten Werkzeuge der Prozessliste hinzuf gt Wir geben dem Benutzer folglich ei ne White Box zur Datenbereinigung an die Hand die sich flexibel an seine W nsche anpassen l sst Klassische Zusammenstellungen von Werkzeugen k nnen dem Benutzer in Form von w hlbaren Voreinstellungen gegeben werden Eine solche Zusammenstellung w re zum Beispiel das Verwenden des Werkzeuges zum Korrigieren von Attributwert Duplikaten vor dem Tupel Duplikatbereiniger Die Werkzeuge die im Framework verf gbar sein werden sind zu unterteilen in e Attributwerkzeuge e lupelwerkzeuge Dabei befassen sich die Attributwerkzeuge mit der Korrektur von Datenwerten also At tributwerten w hrend die Tupelwerkzeuge sich mit dem Korrigieren von Datenzeilen be fassen Dabei sei als Tupelwerkzeug haupts chlich die Duplikaterkennung genannt Dies geht darauf zur ck dass f r die nach Abschnitt 1 2 genannte
21. Werkzeug sondern dem Prozess Die Prozessliste ergibt sich nun aus der Zuordnung einer Prozess Id zu einem Werkzeug und dessen Einstellungen Hieraus folgert dass die Methode die den Prozessblock startet anhand der im Prozess zustand abgelegten Prozess Id aus der Prozessliste das passende Werkzeug startet Das gestartete Werkzeug wird anschlie end aus dem Prozesszustand seinen Einstiegspunkt finden und gem den Werkzeugeinstellungen der Prozessliste fortfahren Es zeigt sich dass der Prozesszustand sowohl aus der Prozess Id der Prozessliste besteht als auch aus Daten die frei vom Werkzeug abgelegt werden k nnen 7 4 Implementation von Werkzeugen Im Abschnitt 7 2 2 4 wurden bereits zwei Klassen vorgestellt die sich mit der Imple mentation von Werkzeugen besch ftigen Dabei steht die Klasse AttributReplacer f r das einfache Bereinigen wertunabh ngiger Fehler und deren Aufbau kann analog auf alle in Abschnitt 4 4 erw hnten wertunabh ngig agierenden Werkzeuge bertragen wer den Die Klasse TupelDuplicate stellt die Implementation des Tupel Duplikatbereinigers aus 4 4 1 1 dar und umfasst die Realisierung von Unterbrechungspunkten und separaten Korrekturverfahren Merging Dieser Abschnitt soll den in 7 2 3 beschriebenen Aufbau verdeutlichen und eine Anleitung zum erweitern des Funktionsumfangs geben 7 4 1 Klasse AttributReplacer Diese Klasse stellt die Implementation des Ersetzer Werkzeuges aus Abschnitt 4 4 2 2 dar E
22. auftreten 1 alle Attributwerte identisch 2 nur ein nicht leerer Attributwert 3 Attributwerte unterscheiden sich Das Vorgehen f r die einzelnen F lle lie e sich wie folgt beschreiben 1 Attribut wird bersprungen da keine Aktion n tig 2 alle Attributwerte werden auf den einen Wert gesetzt 3 zur Ermittlung des Attributwertes wird die Menge an das Referenzwertverfahren bergeben Es erscheint praktikabel unter Verwendung von automatisch ermittelnden Referenzwert verfahren folgende Vorgaben zu beachten e wenn alle Attributwerte identisch sind ist der automatisch ermittelte Referenzwert eben solcher e leere Attributwerte werden bei der automatischen Ermittlung bersprungen e leere Attributwerte werden auf den Referenzwert gesetzt Werden diese Vorgaben erf llt kann hierbei f r jeden Fall das Referenzwertverfahren aufgerufen werden Nach Durchlaufen der Attribute wird ein Tupel als Original bestimmt und der Rest entfernt Anschlie end sind die Verweise auf die entfernten Tupel auf das Originaltupel zu ndern Beim Merging gibt es zwei m gliche Benutzerinteraktionen Zum Einen kann im Sin ne des Referenzwertverfahrens eine Interaktion n tig werden Zum Anderen besteht die M glichkeit dass Tupel in den Cluster eingeordnet wurden die kein richtiges Duplikat zu den anderen Tupeln sind Diese sollten durch eine Benutzerinteraktion aus dem Cluster entfernt werden Dazu ein Beispiel 16
23. das Tupel auf ein einziges Attribut reduzieren Wir k nnen also annehmen dass sich optimierende Techniken wie sie von Verfahren zur Duplikaterkennung zumeist f r Tupel eingesetzt werden auch auf Attribut Ebene als Derivat verwenden lassen Offensichtlich werden zur Fehlererkennung nun Verfahren ben tigt die hnlichkeitsma e bilden und hnlichkeitsfaktoren erstellen k nnen sowie in der Lage sind diese lauf zeittechnisch zu optimieren Im folgenden Abschnitt werden einige bekannte Verfahren genannt von denen wir sp ter spezielle Ausgew hlte genauer betrachten werden 2 3 Verfahren zur Fehlererkennung Zur Ausf hrung des in Abschnitt 2 2 grob dargestellten Ablaufs bedarf es Verfahren die die hnlichkeitsfaktoren bestimmen und die Vergleichsoperation auf hohe hnlich keit ausf hren k nnen Vor allem bei nicht boolschen Vergleichen also Vergleichen die nicht direkt mit ja oder nein beantwortet werden k nnen ist die zuvor angesprochene Pr zision der Verfahren ein entscheidender Faktor Dabei darf allerdings nicht vergessen 12 KAPITEL 2 GRUNDLAGEN werden dass bei einem erheblichen Datenumfang der Rechenaufwand von aufwandigen Verfahren sich exponentiell niederschlagen kann In der Literatur finden sich viele Verfah ren die solche Vergleichsoperationen umsetzen Eine kompakte Ubersicht bietet hierzu zum Beispiel der Artikel ETV07 In diesem Abschnitt sollen einige Verfahren g
24. die aktuelle Tabelle referenziert so muss bei der Werkzeugeinstellung dieses Ber cksichtigt werden 4 4 WERKZEUGE 43 4 4 2 Attributwerkzeuge Lediglich auf der Attribut Ebene erfolgt Datenmanipulation mit Ausnahme des L schens von Tupeln Daraus folgt bereits dass es f r jeden denkbaren Domaintyp von Attribut wert ein Attributwerkzeug zur Bereinigung geben m sste In den folgenden Abschnitten werden die f r das Anwendungsgebiet nach Abschnitt 1 2 und 2 5 ben tigten Attribut werkzeuge beschrieben 4 4 2 1 Formatierungspr fer Parameter Tabelle Eingabeformat Attribut Ausgabe keine Tempor re Tabellen keine Interaktion abschaltbare R ckfrage Dieses Werkzeug verwendet das Eingabeformat oder Dom nenregeln um gem seiner Konfiguration abweichende Attributwerte anzupassen Zugrunde liegen Verfahren die einen Attributwert auf das Eingabeformat anpassen So kann zum Beispiel ein Verfahren Eingabeformate behandeln die sich auf die Textformatierung beziehen Also zum Beispiel das Format erster Buchstabe immer gro schreiben oder nur 5 Zeichen erlaubt Dies ist offenbar eine Umsetzung einer wertunabh ngiger Fehlerkorrektur Ein Beispiel f r die Anwendbarkeit dieses Werkzeuges wurde bereits im Abschnitt 2 1 1 bei der Definition von wertunabh ngigen Fehlern gegeben 4 4 2 2 Ersetzer Parameter Tabelle Attribut Suchmuster Ersetzung Ausgabe keine Tempor re Tabellen keine Interaktion ab
25. e Fei oO Cc or or co 12 13 14 14 14 15 16 19 19 20 22 22 23 INHALTSVERZEICHNIS 4 2 1 Anwendung des MVC Musters 04 33 4 2 2 Blockstruktur nn 34 4 2 3 Datenspeicher 2 m nn nn en 39 4 3 Ablaufbeschreibung 2 2 CC 0 0 0 36 4 4 Werkzeuge 39 4 4 1 Tupelwerkzeuge 2 aaa a 40 4 4 2 Attributwerkzeuge e 43 4 5 Mergingverfahren e 45 4 6 Referenzwertverfahren o oo a 46 4 7 hnlichkeitsverfahren 222 a a AT 4 7 1 Boolscher Vergleich 2 22 CE on nn nn 48 4 7 2 Nummerischer Vergleich 48 4 7 3 Datums Vergleich 2 22 20 20 00 00000 ee ee AQ 4 7 4 Modifizierte Field Smart 49 4 7 5 ISBN Vergleich e 52 4 8 Prozessunterbrechung o ooo aaa a 53 Benutzerhandbuch 55 5 1 Installation und Ausf hrung 0 00000 000 D0 5 1 1 Anforderungen aoaaa 595 5 1 2 Vorbereitungen zur Installation oaoa a nen 56 5 1 3 Ausf hrung aoaaa a 56 5 2 Hauptoberfl che Konfiguration 2 2 2 2 aa 2 000 56 9 2 1 Datenbankzugang ooo aaa nn 58 5 2 2 Tabellenkonfiguration Emm nn 59 5 2 3 Attributkonfiguration 2 2 2 Co mm 60 5 2 4 Prozessliste 2 22 2 Coon 61 5 2 0 Werkzeugeinstellungen 2 020000 008 62 5 3 Hauptoberflache Prozess 2 KL m mn m ne 65 5 4 Interaktion 2 2 2 aa a 66 Testbericht 69 6 1 Vorbereitung oaoa nn 69 6 2 Laufzeittest ooa aa 71 INHALTSVERZEICHNIS 7 Implementierung 7 1 Umgebun
26. eine minimale Schranke ab ab dem zwei Zei chenfolgen als hnlich gelten Diese Schranke ist ungef hr 2 52 KAPITEL 4 KONZEPTION F r jede Zeichenfolge Erstelle anhand eines Irennzeichens Menge von einzelnen W rtern K Anzahl W rter beider Mengen 1 0 Fur jedes Wort der Menge A F r jedes Wort der Menge B Wende boolschen Vergleich auf die Worter an Wenn Vergleich hohe hnlichkeit liefert kass kb Entferne aktuelles Wort der Menge A Entferne aktuelles Wort der Menge B F r jedes Wort der Menge A F r jedes Wort der Menge B Wende Field Similarity auf die W rter an Merke h chsten ermittelten hnlichkeitsfaktor f r jedes Wort F r alle W rter Wenn hnlichkeitsfaktor lt 1 I I hnlichkeitsfaktor Entferne aktuelles Wort aus seiner Menge F r jedes Wort der Menge A F r jedes Wort der Menge B Wende Q Grams q 2 auf die W rter an Merke h chsten ermittelten Ahnlichkeitsfaktor f r jedes Wort F r alle W rter I 1 hnlichkeitsfaktor Ergebnis A Auflistung 4 1 Zusammenfassung der Modifizierte Field Similarity 4 7 5 ISBN Vergleich Parameter zwei Attributwerte vom Dom ntyp ISBN Dieses Verfahren ist abgeleitet aus den in 2 5 dargestellten Werkzeugvorschlagen Dieses Verfahren verwendet einen boolschen Vergleich Die Besonderheit besteht darin dass es bei ISBN Werten verschiedene valide Eingabeformate gibt Vor dem boolschen Vergleich werden die Attributwerte auf ein Normformat gebracht
27. hnliche Zeichenfolge A Mainz B Heinz Eingabe 4 stark un hnliche Zeichenfolge A Mainz B Hinze 3 5 PC FILTER 23 Eingabe 5 un hnliche Zeichenfolge gleicher Zeichenvorrat A Heinz B Hinze Eingabe 6 ausgelassener Buchstabe A Hana B Hanna Pos af a o2 om o6 os ow o6 o 0 6 6 6 8 1 Pozi fp a oss os os Tabelle 3 1 Vergleich der Ahnlichkeitsfaktoren 5 2 0 33 2 gt 1 0 0 0 1 0 Wie wir hier sehen k nnen liefert Field Similarity und q 1 Vergleichsweise hnliche Werte Der Unterschied bei 2 bis 4 ergibt sich aus der Bewertung hinsichtlich der Ge samteingabe bei Q Grams entgegen der Einzelbetrachtung von Field Similarity Beide liefern ein Verh ltnis der enthaltenen Zeichen beider Eingabefolgen Das liefert im Fall 1 eine gute Erkennung des Zeichendrehers und des fehlenden Zeichens in Fall 6 f hrt aber zu einer starken Fehlerkennung im Fall 4 und 5 q 2 gibt durchweg zufrieden stellende Ergebnisse scheitert jedoch an der Erkennung des Zeichendrehers dessen hnlichkeits faktor zu niedrig ist um solche Fehler automatisch entdecken zu k nnen g 3 folgt am ehesten der intuitiven Ahnlichkeitsverteilung scheitert jedoch ebenfalls an dem Zeichen dreher Zudem scheinen sich die Faktoren mit zunehmenden q stark zu reduzieren f r kurze Eingabefolgen Insgesamt l sst sich feststellen dass sich Field Similarity eignet um Z
28. ndig und wertet deren R ckmeldungen aus Dazu z hlt auch die Bereitstellung der Benutzerinteraktion Jeder Ausf hrblock der Werkzeuge ist somit auch Teil der Ablaufsteuerung N heres zum Ausf hrungsblock folgt im Abschnitt 4 3 Der Fehlererkennungsblock beinhaltet Operationen zur Erkennung von Fehlern auf dem Datenbestand und meldet diese dem Ausf hrungsblock zur ck Der Fehlerkorrekturblock wertet das Eregbnis der Erkennung aus f hrt die Korrekturma nahmen durch und schickt dem Ausf hrungsblock eine R ckmeldung ber allen steht die Konfiguration in denen die Einstellungen der Werkzeuge aus dem Konfigurationsblock abgelegt werden und diese den restlichen Bl cken zur Verf gung stellt 4 2 ARCHITEKTUR 39 Benutzerebene Werkzeugkonfiquration Konfiguration ablegen 4 Kanfiguration Konfiguration bereitstellen Zustandwechsel Datenzugriff Ausf hrung Iniaraktionsantrage r ckmeklen e ansio en Fehlerkorrektur Interaktionsanfrage fruckmelden Zustandwechsel Datenbestand i p Datenmanipulation Verarbeitungsebene Abbildung 4 3 Funktionsblocke von Werkzeugen 4 2 3 Datenspeicher Dem MVC zur Folge hat nur der Model Teil Zugriff auf externe Datenquellen Hier soll gezeigt werden dass diese Definition f r unsere Architektur ausreichend ist Der Model Teil befindet sich hier auf der Verarbeitungsebene und hat dort Zugriff auf den Datenbestand Da sic
29. ooo a a 89 Implementierung von Field Similarty 0 90 Implementierung von Q Grams o 90 105 106 ABBILDUNGSVERZEICHNIS Tabellenverzeichnis 3 1 Vergleich der hnlichkeitsfaktoren 2 22 Coco 3 2 Vereinigung der PartListen pro Partition 3 3 PCR Beispiel e 107 108 TABELLENVERZEICHNIS Literaturverzeichnis Bra07 BSo6 EIVO7 pv HS95 HS98 Lev66 MBO6 IME96 ISLP02 M Bramer Principles of Data Mining Springer Verlag London 2007 C Batini M Scannapieco Data Quality Concepts Methodologies and Tech niques 1 edition Data Centric Systems and Applications Springer Verlag Berlin 2006 A K Elmagarmid P G Ipeirotis V S Verykios Duplicate Record Detec tion A Survey IEEE Transactions on Knowledge and Data Engineering 19 1 2007 1 16 D O Holmes M C McCabe Improving Precision and Recall for Soundex Retrieval In I C Society ed International Conference on Information Technology Coding and Computing April 8 10 2002 Las Vegas Nevada USA IEEE Computer Soc Los Alamitos Calif u a 2002 22 27 M A Hern ndez S J Stolfo The Merge Purge Problem for Large Databases In M Carey D Schneider eds Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data San Jose May 22 25 1995 SIGMOD Record 2 ACM Press New York 1995 127 138 M A Hern ndez S J Stolfo Real wo
30. setzen um Daten s tze mit weiterf hrenden Informationen zu verkn pfen Damit lassen sich sehr schnell sehr gro e und komplexe Datenspeicher realisieren Bringt man in ein solches System ein fehlerbehaftetes Element ein ist schnell einleuchtend dass sich dessen Fehler auf den Datenbestand auswirken Ein solches Element ist unter anderem der Mensch Die Eingabe von Daten in ein Datenbanksystem geschieht in der Regel ber vom Men schen geschaffene Kan le Entweder werden Daten per Hand eingegeben oder es werden Importmechanismen genutzt deren Logik sich auf vom Menschen vorgegebene Regeln st tzt Solange bei der Konversion der Quelldaten ber den Kanal in das Datenbank system die von der Datenstruktur des Datenbanksystems implizierten bzw die von dem Verwender antendierten Darstellung beibehalten wird stellt dies kein Problem dar Durch Unwissenheit oder Unachtsamkeit des Eingebenden sowie durch unbehandelte Ausnah men bei der Umwandlung von Quelldaten k nnen allerdings Daten in das Datenbank system gelangen deren Aufbau solch einer Darstellung widerspricht Resultiert dies in einer Verletzung einer explizit oder implizit berwachten Eingaberegel z B Werteberei che oder Datentypen verweigert vermutlich das Datenbanksystem die Eingabe Ist die Verletzung aber nur semantischer Struktur und wird nicht durch eingebaute Eingabere geln berwacht k nnen fehlerhafte Eintr ge zur ckbleiben Dies kann geschehen durch vertauschte Buc
31. sind mitunter schwer zu unterscheiden Es wird deutlich wenn wir zum Beispiel zwei Werte mit der Identit tsfunktion als hnlichkeitsma bewerten Dieser boolscher Vergleich dazu sp ter mehr kann nun den hnlichkeitsfak tor 0 oder 1 erzeugen Wir k nnen den hnlichkeitsfaktor jedoch auch als 1 und 10 definieren Diese abweichende Bestimmung des hnlichkeitsfaktors ndert hingegen nicht das Ma das wir anwenden um die Werte zu vergleichen 2 1 DER BEGRIFF DATENBEREINIGUNG if Weicht ein Attributwert nun von seiner vorgegebenen Form Datentyp Eingabeformat und Dom ne ab kann dies als Attributwertfehler bezeichnet werden Dabei ist zu unterscheiden zwischen wertunabh ngigen Verst en zum Beispiel gegen das Einga beformat und wertabh ngigen Verst en wie zum Beispiel der Dom ne Wertunab h ngige Verst e k nnen anhand der vorgegebenen Regeln direkt korrigiert werden So k nnte zum Beispiel das Eingabeformat 5 Zeichen Buchstaben vorgeben eine Zeichen kette mit mehr als f nf Zeichen zu k rzen Wertabh ngig k nnen Fehler sein die nicht gegen bestimmte Formatierungsregeln versto en sondern von der Bedeutung der Dom ne abweichen Einfache Verletzungen zum Beispiel gegen den Wertebereich k nnen hierbei wie wertunabh ngige Fehler durch geeignete Filter bereinigt werden Im Folgenden sei hier das Mehrfachauftreten gleichbedeutender Attributwerte n her zu Untersuchen
32. void disableFrame public abstract void enableFrame Sperrt bzw aktiviert das Fenster public abstract void disableResize Verhindert das ndern der Fenstergr e mit der Maus public abstract void enableResize Erlaubt das ndern der Fenstergr e mit der Maus Klasse GBCHelper public void resetGBC Setzt das gesamte Layout zurtick public void addToPane Component com F gt eine Komponente dem Layout hinzu 98 public public public public ANHANG A API void noFill void fillHor void fillVer void fillBoth Legt fest in welche Richtung Komponenten ihre Fl che ausf llen public public void setGridX int x void setGridY int y Legt die Koordinaten einer Komponente im Layout fest public public public void resetGridsize void setGridwidth int width void setGridheight int height Legt die Ausdehnung einer Fl che fest public public public void resetWeigth void set WeightX double x void set Weight Y double y Legt die Dehnungsverteilung fest public public public void setIPadX int x void setIPadY int y void resetPad Legt fest wie viel zus tzlichen Platz eine Komponente braucht innerer Rand public public public public public public void setInsets int top int left int bottom int right void resetMargin void setMarginTop int px void setMarginLeft int px void setMarginRight int px void setMarginBottom int px
33. wir die Verbindung der Bl cke zueinander als Final State Machine Interpretieren Dies erlaubt uns jederzeit in unserem Programmablauf den aktuellen Zustand festzuhalten Jeder Funktionsblock kennt seinen Zustand in dem er sich befindet Auf der bergeordneten Ebene k nnen wir beim Wechsel eines Funktionsblockes einen Zustandswechsel verzeichnen F r die bergeordnete Einheit bedeutet ein Zustandswechsel folglich dass die Zustandsinforma tionen des zuletzt aktiven Blockes nicht mehr relevant sind So sind beispielsweise die Oberfl chenoptionen der Konfiguration uninteressant wenn sich die Anwendung in der Ablaufsteuerung befindet Aus der Beschreibung des Frameworks sind uns f r die Benutzerebene schon die bei den Bl cke Konfiguration und Ablaufsteuerung bekannt Dieses soll im Abschnitt 4 3 weiter ausgef hrt werden Zun chst betrachten wir die Blockstruktur f r ein Werkzeug Das Werkzeug setzt sich zusammen aus den Bl cken Konfiguration und Ausf hrung auf der Benutzerebene und den Bl cken Fehlererkennung und Fehlerkorrektur auf der Verarbeitungsebene Der Konfigurationsblock gibt dem Benutzer die M glichkeit das Werkzeug auf seine Bed rfnisse anzupassen oder wichtige Parameter voreinzustellen Der Ausf hrungsblock berwacht die Operationen des Verarbeitungsblockes Das hei t der Ausf hrungsblock ist f r das Abarbeiten der beiden Bl cke der Verarbeitungsebene zust
34. 1 nz 1 z 1 T H1 Hel Heil einl inz1 nz 1 z 1 T To inzl1 nz 1 z 1 TUR M1 Mal Mail ainl inz1 nz 1 z 1 H1 Hel Heil ein1 if Tae mn d 027 lt 5 Beispiel 3 4 un hnliche Zeichenfolge mit q 3 Wie wir an diesen Beispielen sehen k nnen reagiert dieses Verfahren empfindlich auf die Position an denen Zeichenketten sich unterscheiden Nahe beieinander liegende Unter schiede ergeben eine h here hnlichkeit als Verstreute Um speziell Zeichendreher auf finden zu k nnen w rde es sich anbieten das q auf 1 zu reduzieren So f hre dies im Hanna Beispiel sogar auf einen Faktor von 1 Ein Verfahren der Literatur dass sich mit der Anwendung von q 1 befasst soll im Folgenden vorgestellt werden 22 KAPITEL 3 AUSGEW HLTE VERFAHREN 3 3 Field Similarity Das Field Similarity Verfahren wird in der Literatur ZLBLO4 und SLP02 als Ahn lichkeitsma f r den Zeichenkettenvergleich in Verbindung mit PC Filter vorgeschlagen Dieses Verfahren vergleicht zwei Eingangszeichenketten A und B indem die Zeichen ketten in einzelne Zeichen zerlegt werden und dabei die bisherige Auftrittsanzahl eines Zeichens jeweils vermerkt wird Zum Beispiel wird aus der Zeichenkette aabcdb die Menge al a2 b1 c1 d1 b2 Anschlie end werden die Tupel A und B geschnitten Die Schnittmenge enth lt nun die Zeichen die in beiden Zeichenketten in gleicher Auftritts reihenfolge vorkommen Nehmen
35. 5 3 Hinweisfeld e 57 9 4 Datenbanklogin aoao aa aa a 58 5 5 Datenbankzugang ooa aa a nn 58 5 6 Tabellenkonfiguration 222 ao a 59 5 7 Attributkonfiguration 2 2 a a a nn 60 9 8 Prozessliste 22 2 oo oo 61 5 9 Werkzeugeinstellung kein gew hltes Werkzeug 2 2 2 62 5 10 Werkzeugeinstellung Tupel Duplikatbereiniger 2 63 5 11 Werkzeugeinstellung Referenzwerte 20 0 0 000 00 64 5 12 Werkzeugeinstellung Verweise 69 5 13 Hauptoberflache Prozess e 66 5 14 Interaktion Referenzwerte 67 5 15 Interaktion Clusterkorrektur 2 2 CC m on nn 68 102 6 1 6 2 6 3 6 4 1 1 1 2 1 3 1 4 1 9 1 6 1 7 ABBILDUNGSVERZEICHNIS Schlagworttabelle wahlen 69 Attribut Duplikatbereiniger einstellen 2 2 2 CE m mn nn 10 Laufender Prozess 2 2 CC oo no nn 71 Zuviele hnliche Werte 2 CC on nn 12 Paket Diagramm 2 2 n a 14 Klassendiagramm Hauptoberflache oaoa aa a a 19 Klassendiagramm 1 von Paket View 0 0 0 2 004 16 Klassendiagramm 2 von Paket View a 004 18 Klassendiagramm Paket Configuration 08 19 Klassendiagramm Paket Tools 80 Ablauf AttributReplacer 2 2 2 Con on 200 00 00000000058 84 Beispielverzeichnis 2 1 2 2 3 1 3 2 3 3 3 4 3 0 3 6 4 1 4 2 4 3 4 4 4 5 4 6 1 1 1 2 Clusterkorrektur bei unzureichender Duplikaterkennung 16 Dupliziertes Schlagwort
36. 521 In das Feld mit der Bezeichnung SID tragen Sie das Schema ein mit dem Sie verbinden wollen Bitte w hlen Sie ein Schema in dem Ihr Datenbankbenutzer die Rechte Select Insert Update Create Drop Delete hat Datenbankzugang x Hostname leo dbs uni hannover de Port 1927 SID production Abbrechen Speichern und weiter Abbildung 5 5 Datenbankzugang Mit der Schaltfl che Speichern werden Ihre nderungen in die Konfiguration bernom men 5 2 HAUPTOBERFLACHE KONFIGURATION 59 Mit der Schaltfl che Speichern und weiter gelangen Sie zur Tabellenkonfiguration 5 2 2 Mit der Schaltfl che Abbrechen werden Ihre nderungen ignoriert und das Fenster geschlossen 5 2 2 Tabellenkonfiguration In diesem Dialog w hlen Sie die Tabellen auf denen Sie Werkzeuge anwenden wollen Tabellenkonfiguration Tabellen im Benutzerschema Tabellenkontiguration VW BALAUF NEY E Manueller Eintrag PI LY_DUPLIKATE ed PI SCHRIFT PLSCHLAGWORT_BACK PLSCHRIFT PLSCHRIFTDUPLIKATE PLSEMA_BACKUP PLSEMABETREUER PLSEMADOZENT PLSEMAPRUEFER Abbrechen Speichern und weiter Abbildung 5 6 Tabellenkonfiguration Sie k nnen aus der automatisch ermittelten Liste von Tabellen mit der gt Schaltfl che zuvor markierte Eintr ge in Ihre Konfiguration bertragen Wollen Sie eine Tabelle aus der Konfiguration entfernen klicken Sie in der Liste im Panel Tabellen
37. Attributeigenschaften laden hnlichkeitsma w hlen hnlichkeitsfaktor bilden Tupel Ebene Attribute durchgehen Zusammenfassen Abbildung 4 6 Vergleichsverfahren Ablaufdiagramm Alle hier vorgestellten hnlichkeitsma e und Faktorerzeuger sind Verfahren die von Werkzeugen aufgerufen werden k nnen Demnach haben diese Verfahren auch beschrei bende Eigenschaften die denen aus 4 4 hneln Alle hier vorgestellten Verfahren sind als Funktionen umzusetzen Deren Ausgabe ist gem Definition ein Wert zwischen 0 und 1 Eine Benutzerinteraktion ist nicht notwendig Tempor re Tabellen k nnen durch interne Datenstrukturen ersetzt werden da die Verfahren keine Unterbrechungspunkte bieten und der Datenaufwand gering ist 48 KAPITEL 4 KONZEPTION 4 7 1 Boolscher Vergleich Parameter zwei beliebige Attributwerte Die einfachste Form eines hnlichkeitsma es ist der direkte Vergleich zweier Werte auf Gleichheit Das Ergebnis ergibt einen Ahnlichkeitsfaktor von 0 oder 1 4 7 2 Nummerischer Vergleich Parameter zwei Attributwerte eines nummerischen Datentyps Bei dem Vergleich von nummerischen Werten k nnen drei Ans tze gew hlt werden 1 Der Wert ist eindeutig 2 Verhalten wie Zeichenfolge siehe auch Hinweis in 2 3 1 3 Dynamisches Vorgehen Fall 1 impliziert den boolschen Vergleich Im Fall 2 kann Q Grams mit g 2 angewen det werden Field Similarity ist unpraktisch da Zahlen mit den g
38. Aufgabe keine gesamten Tupel ausgetauscht werden brauchen Zur Vollst ndigkeit sei aber eine Tupelloschopera tion vorgestellt Dahingegen sind eine Reihe spezieller Attributwerkzeuge zu entwickeln wie sie in 2 5 bereits angesprochen wurden F r alle Werkzeuge gelten die Frameworkeinstellungen welche die Tabellen und Attribute festlegen auf denen die Werkzeuge agieren sollen Die Werkzeugparamerter sind Teil der Werkzeugeinstellungen und abh ngig vom Werkzeug Zur Festlegung der Attribute z hlt ebenfalls das Zuweisen von Attributeigenschaften Dies ist in Analogie zu der Definition des Begriffes im Abschnitt 2 1 1 der Attribut name Datentyp bzw Domaintyp und eventuell das Attributgewicht f r Werkzeuge die das PC Filter Verfahren nutzen Die Menge dieser Zuweisungen erzeugt die Liste der Attributeigenschaften Der urspr ngliche Begriff wurde dadurch erweitert Das Eingabe format sei f r die hier vorgestellten Werkzeuge nicht zur Wahl eines hnlichkeitsma es notwendig Vielmehr stellt es eine Werkzeugeinstellung dar 40 KAPITEL 4 KONZEPTION Die im Konfigurationsblock festgelegten Werkzeugeinstellungen werden hier zu den Pa rametern der Werkzeuge Welche der Parameter auch Teil der Konfiguration sind h ngt von der Implementierung der Werkzeuge ab da es m glich ist manche Parameter vor eingestellt zu lassen Die nachfolgenden Konzepte f r Werkzeuge beschreiben die Werkzeugbl cke Ausf h rung Fehl
39. Da mit dem Abarbeitung der Prozessliste das Programm in den Prozess bzw Werkzeugblock wechselt w rde die Auswertung der Bedienoberfl che zur ckgestellt bis der Block vollendet wurde Daraus ergibt sich die Notwendigkeit den Prozessblock als eigenen Thread zu starten und durch globale Signale mit der Be dienoberfl che zu kommunizieren W hrend der Abarbeitung wird der aktuelle Block und alle notwendigen Ausf hrungs informationen im Prozesszustand gef hrt Dieser wird vom Werkzeug der Klasse Frame workCFG mitgeteilt Der Model Part der Werkzeuge kann tempor re Tabellen und PL SQL Prozeduren um fassen die vor der Ausf hrung nicht auf der Datenbank vorhanden sind Eine Werkzeug klasse hat folglich die Aufgabe daf r zu sorgen dass auf der Datenbank die ben tigten Werkzeugelemente vorhanden sind Grob gefasst werden beim Ausf hren eines Werk zeuges fehlende Werkzeugelemente auf der Verarbeitungsebene generiert Dies kann zum Beispiel durch das Erstellen von PL SQL Prozeduren auf der Datenbank geschehen Dies kann der Fall sein wenn ein Verfahren zum Beispiel aus Abschnitt 7 5 gebraucht wird Ein solches Verfahren l sst sich mit einer statischen Query auf der Datenbank erstellen und auch wieder entfernen Nach Abarbeitung eines Werkzeuges sollten die auf der Datenbank neu erstellten tempo r ren Elemente wieder entfernt werden um unn tige Datenlast zu vermeiden 7 3 Implementation vom Prozesszustand
40. Dateinamen loadName nach fCfq A 2 Paket View Abstrakte Klasse Standard View public abstract Window getFrame Gibt das Fensterobjekt zur ck dass mit der Klasse instanziert wurde public JButton createJ Button String title ActionListener aListener String com mand Erzeugt einen JButton mit dem Titel title und f gt gleichzeitig den ActionListener und den Commandstring hinzu public JMenultem createJMenultem String title ActionListener aListener String command Erzeugt ein JMenultem mit dem Titel title und f gt gleichzeitig den ActionListener und den Commandstring hinzu public abstract void parentAction String command Object args Wird von bergeordnetem Objekt aufgerufen wenn eine R ckmeldung erforderlich ist Abstrakte Klasse In t View public abstract void unload Vernichtet das Fenster A 2 PAKET VIEW 97 public abstract void pack Wendet das Layout auf die Komponenten an public abstract void show Zeigt das Fenster public abstract void hide Versteckt das Fenster public abstract void centerFrame Erzeugt ein Fenster variabler Gr e in der Bildschirmmitte public abstract void resizeFrame Erzeugt ein Fenster mit Standardabmessungen public abstract void resizeFrame int x int y Erzeugt ein Fenster mit den Abmessungen z und y public abstract void resizeFrameScreen Erzeugt ein Fenster mit der halben Bildschirmaufl sung als Abmessung public abstract
41. Diese Methoden legen die Abstande zwischen Komponenten fest public public public public public public public void anchorCenter void anchorLeft void anchorRight void anchor Top void anchorBottom void anchor TopLeft void anchor TopRight Legt die Ausrichtung einer Komponente in einer Flache fest A 3 PAKET TOOLS 99 A 2 Paket Tools Beinhaltet die Werkzeugklassen Interface ITools public String getToolString Gibt den Namen des Werkzeugs zur ck Namen m ssen eindeutig sein public String getSimNames Gibt die Namen der unterst tzten Dom ntypen zur ck Das Array muss die gleichen Indizes wie die R ckgabe von getSimTypes haben public Sim Tune sl getSimTypes Gibt die zugrunde liegenden Datentypen der Dom ntypen zur ck Das Array muss die gleichen Indizes wie die R ckgabe von getSimNames haben public String getConfigShortText String options Erstellt aus einem String Array von Werkzeugeinstellungen einen Beschreibungstext f r die Listendarstellung public void editConfig int processID JPanel configPanel F gt die Oberfl che der Werkzeugeinstellungen an das configPanel an Der Parameter processID gibt an zu welchem Prozess der Prozessliste die Einstellungen abgelegt werden sollen public void interactionPane int processID JPanel interPanel F gt die Oberfl che der Interaktion an das configPanel an Der Parameter processID gibt an in welchem Prozess sich die Anwe
42. Ebene vorgestellt Das Prinzip dahinter ist eine Kombination aus hnlichkeitsvergleich und abgewandelter Clustertechnik Dabei kann das Verfahren zur hnlichkeitsfaktorbil dung f r die Attribut Ebene sehr leicht ausgetauscht werden solang es sich an die sp ter vorgestellten Regeln h lt Dieses Verfahren teilt den Datenbestand in Partitionen ein die wie Cluster verwaltet werden und erm glicht ein zeiteffektives Auffinden von Duplikaten 19 20 KAPITEL 3 AUSGEWAHLTE VERFAHREN auch in Nachbarpartitionen Damit ist es den Verfahren die nur Sliding Window einset zen berlegen Beim Sliding Window wird eine Menge an Tupeln durchlaufen und eine feste Anzahl an aufeinander folgenden Tupeln miteinander verglichen Es erfolgt also kein Vergleich weit entfernter Tupel Wir haben dieses Verfahren der Sorted Neighborhood Method vorgezogen da es zum Einen f r einen gro en Datenbestand in der Lage ist durch geringen Mehraufwand auch weiter entfernte Daten zu vergleichen Zudem ist es durch die Abtrennung des hnlich keitsvergleiches mit der eigentlichen Duplikaterkennung in der Lage mit austauschbaren hnlichkeitsma en implementiert zu werden Des Weiteren l uft es in berschaubaren Phasen ab so dass eine externe Steuerung m glich wird Dem Verfahren wird dabei eine Menge an Tupeln vorgegeben sowie die Anzahl an Par titionen die Gr e des Partitionsrandbereiches und der gew nschte Genauigkeitsgrad Die Gr e der Partionen
43. Entwicklung von Werkzeugen zur Datenbereinigung in relationalen Datenbanken Bachelorarbeit im Studiengang Informatik Philipp Wolski Mtr Nr 2518220 Fachgebiet Datenbanken und Informationssysteme Institut f r Praktische Informatik Fakult t f r Elektrotechnik und Informatik Gottfried Wilhelm Leibniz Universit t Hannover Pr fer Prof Dr Udo Lipeck Zweitprufer Dr H H Br ggemann Betreuer Prof Dr Udo Lipeck 1 April 2009 il Inhaltsverzeichnis 1 Einleitung 1 1 Motivation 1 2 Zielsetzung und Anforderungen 2 aa 1 3 Aufbau der Arbeit aoaaa 2 Grundlagen 2 1 Der Begriff Datenbereinigung 20 00 5000 2 1 1 Relevante Datengegenstande 008 4 2 1 2 Hierarchien innerhalb der Datengegenst nde 2 2 2 Ablauf einer Bereinigung 2 3 Verfahren zur Fehlererkennung 2 22 2 Cm En nn 2 3 1 Attribut Ebene e 2 3 2 Tupel Ebene 2 2 2 2 CL rn nn 2 3 3 Objekt Ebene 2 0 00 00 0 00 ee 2 4 Verfahren zur Fehlerkorrektur 0 20 0000 2 4 1 Korrektur mit Referenzwert 2 0040 2 4 2 Merging e 2 5 Bibliographischer Datenbestand des DBIS 2 2 3 Ausgew hlte Verfahren 3 1 berblick 22222 ee 3 2 Q Grams 2 on on 3 3 Field Similarity 2 0 3 4 Vergleich von Q Gram zu Field Similarity 3 0 PC Filter 2 oo oo 4 Konzeption 4 1 berblick 2 2 oo 4 2 Architektur gt oo oo ili YN N
44. KAPITEL 2 GRUNDLAGEN Behandelt wird eine Tabelle mit Personendaten Duplikate wurden anhand von Nachnamen und Vornamen erkannt Die als Duplikate erkannten Personen haben unterschiedliche Adressen und Telefonnummern Die Personen stellen keine Duplikate dar Beispiel 2 1 Clusterkorrektur bei unzureichender Duplikaterkennung Das Merging geht auch hier gem der Definition davon aus dass es sich bei der Menge an Tupeln um Duplikate handelt Die Behandlung erfolgt folglich wie oben beschrieben Nun treten bei den Adressen und Telefonnummern eventuell eine Interaktionsanfrage aus dem Referenzwertverfahren auf Hier muss der Benutzer auch entscheiden ob das betroffene Tupel berhaupt zum Cluster geh rt also wirklich ein Duplikat ist Dass die hier angewendete Duplikaterkennung nicht ausreichend war erkennt das Verfahren nicht ohne Interaktion Eine automatische Erkennung von schlecht gew hlten Tupeln kann anhand einer gro en Anzahl leerer Attributwerte erfolgen So zum Beispiel wenn vergleichsweise leere Tupel sich im Cluster befinden dessen Unterscheidungspunkt zwar hnlich aber g nzlich an ders bedeutend ist Dieser Sonderfall tritt beispielsweise bei referenzierten Tupeln auf die Zusatzinformationen zu verweisenden Tupeln beinhalten Hier wurde das Tupel anhand eines Attributes eingeordnet das zwar hohe hnlichkeit aufweist nicht aber auf Objekt Ebene vertr glich ist Zum Beispiel wird gepr ft auf das Attribut
45. Mittelweg gew hlt zwischen den beiden Verfahren indem der Mittelwert beider aus der Q Grams Bewertung mit der Field Similarity Bewertung gebildet wird Letzterer Wert entspricht durch die Bedingung aus dem vorangegangenen Schrittes dem h chsten hnlichkeitsfaktor der gebildet werden kann Verdeutlicht wird sp ter dies in Beispiel 4 4 50 KAPITEL 4 KONZEPTION Die Anzahl identischer W rter einschlie lich der zuvor ermittelten hnlichkeitsfaktoren wird nun durch die Gesamtzahl der W rter geteilt Wir bekommen die mittlere Ahn lichkeit aller W rter der Zeichenfolgen Die Zeichenfolgen lassen sich dann durch den hnlichkeitsfaktor bewerten den die genannte Division liefert Beispiele e A Ich laufe gerne im nahen Wald B lIch sehe gerne den Wald T Ich laufe gerne im nahen Wald Tg Ich sehe gerne den Wald K T 4 Tp 11 Nach boolschen Vergleich T4 laufe im nahen Tp sehe den W rter mit identischen Gegenst cken J 6 hnlichkeitsfaktoren nach Field Similarity laufe Beispiel 4 3 Modifizierte Field Similarity f r S tze e A Hanna B Hanan Ep Nach boolschen Vergleich A Hanna B Hanan W rter mit identischen Gegenst cken J 0 hnlichkeitsfaktoren nach Field Similarity Hanna 1 Hanan 1 nach Anwenden von g 2 auf alle W rter mit hnlichkeitsfaktor 1 Hanna d Hanan 5 1 0 2 gt 42 040 75 40 75 15
46. PER bilden PartList verarbeiten PCG erstellen Innere Partitionen vergleichen Au ere Partitionen vergleichen PC Filter Funktionsbl cke 42 KAPITEL 4 KONZEPTION PC Filter selbst bedarf zudem keinen Zugriff auf die Attributwerte Alle PC Filter Ope rationen sortieren lediglich Zuordnungsnummern Der eigentliche Zugriff erfolgt ber die Verfahren zur Erzeugung von hnlichkeitsfaktoren Damit ist das Verfahren sehr variabel was unterschiedliche Datentypen oder Dom nen betrifft Es muss lediglich das hnlich keitsma angepasst werden Die Attribute die PC Filter zum Vergleich heranziehen soll sind in der Liste der Attributeigenschaften abgelegt Anhand dieser wird auch das hn lichkeitsma bestimmt Der Ablauf von PC Filter erfolgt wie in 3 5 bereits vorgestellt Das Verfahren ist vollst n digin PL SQL programmierbar Damit ist es m glich die Abfragen an den Datenbestand direkt auf der Datenbanke zu starten und die Schnittstellenzeit zu sparen Zudem lassen sich interne Tabellenstrukturen f r die Implementierung nutzen Betrachtet man ein Attribut als eine einspaltige Tabelle so kann man diese ebenfalls mit PC Filter behandeln Damit ist es m glich hnliche Attributwerte zu finden und zu gruppieren Siehe hierzu auch die hnlichkeit der Ablaufpl ne im Abschnitt 2 2 Wird PC Filter auf Tabellen angewendet muss davon ausgegangen werden dass es Ver weise in Form von Foreign Keys geben kann Dazu m ssen a
47. Vererbungspfeile in den Abbildung 7 3 und 7 4 verzichtet Die abstrakte Klasse Standard View stellt die generische Instanz einer View Klasse dar Sie implementiert die Methode parent Action durch die neu generierte Fenster 7 2 ENTWURF UND AUFBAU 17 dem aufrufenden Fenster Nachrichten zukommen lassen kann Die StandardView Klassen dienen als Unterst tzerklassen um den Fensteraufbau zu vereinheitlichen und vorimple mentieren den notwendigen Controller Part f r die Interaktionselemente Diese Klassen vereinheitlichen also den Aufbau der steuernden Klasse wahrend die spater genannten InitView Klassen den Fensteraufbau vereinheiltichen Die abstrakte Klasse StandardFrameView ist die Klasse von der Frame Fenster abgeleitet werden Die Klasse bersetzt den Datentyp JFrame in die generische Form Sie erstellt im Konstruktor einen nitFrame Die abstrakte Klasse StandardIFrameView ist die Klasse von der InternalFrame Fenster abgeleitet werden Die Klasse bersetzt den Datentyp JInternalFrame in die ge nerische Form Sie erstellt im Konstruktor einen nitIFrame Die abstrakte Klasse StandardDialogView ist die Klasse von der Dialog Fenster abgeleitet werden Die Klasse bersetzt den Datentyp JDialog in die generische Form Sie erstellt im Konstruktor einen Init Dialog Die Klassen DlgProcessCfg DlgTableCfg DIgDBCfg sind drei ausgew hlte Klas sen zur Demonstration der Implementierung von Konfigurationsdialogen Ab
48. Zaragoza Spain August 30 September 3 2004 LNCS Springer Verlag Berlin 2004 486 496 Erklarung Hiermit versichere ich dass ich die vorliegende Arbeit und die zugeh rige Implementie rung selbst ndig verfasst und dabei nur die angegebenen Quellen und Hilfsmittel verwen det habe Hannover 02 April 2009 Philipp Wolski 111
49. Zum Beispiel kann das Ersetzen von Wert A durch Wert B geschrieben werden als UPDATE SET Wert B WHERE Wert A Beispiel 7 1 Ersetzung von Werten durch wertunabh ngiges Verfahren Die Anwendung einer solchen Implementierung haben wir bereits im Abschnitt 7 4 1 gesehen 7 5 2 PC Filter PC Filter wird nach Abschnitt 4 4 1 1 in mehrere Bl cke aufgeteilt Hinter jedem Block m ssen tempor re Dateien gespeichert werden Das l sst sich erreichen indem wir das Verfahren als einzelne Prozeduren entsprechend der Blockaufteilung in Abbildung 3 1 86 KAPITEL 7 IMPLEMENTIERUNG implementieren Zus tzlich implementieren wir PC Filter als PL SQL Prozeduren Da durch wird die Schnittstelle zur Datenbank nicht unn tig belastet Um den Datenbestand nicht unn tig zu vergr ern verwenden wir das von Oracle zur Verf gung gestellten Ro wID Attribut Dieses beinhaltet eine eindeutige Identifikationsnummer einer Zeile einer Tabelle Diese werden von Oracle automatisch indexiert Der Ablauf entspricht der in Abschnitt 3 5 beschriebenen Vorgehensweise Es werden folgende tempor re Tabellen ben tigt tmpPartition Tabelle f r Partitionen Anchor Records AR und hnlichkeiten zum AR e tmpPCR Tabelle zum Verwalten der Delimiting Records DR tmpPCRList Tabelle zum Generieren der PartList e tmpPCG Tabelle f r den PCG e tmpDuplicate Ergebmostabelle mit Duplikatpaaren e tmpAttribute Zuweisung von Daten Doma
50. ann nur stattfinden wo kein Zugriff auf Daten erfolgt Das hei t es kann erst unterbrochen werden wenn die letzte Anfrage an das Model quittiert wurde Um Abbrechen zu k nnen muss ein Werk zeug folglich in Detailbl cke kleinste Funktionsbl cke aufgeteilt werden nach denen je weils eine Unterbrechung durchgef hrt werden kann An diesen Unterbrechungspunkten m ssen alle tempor ren Daten persistent Verf gbar oder Teil des Prozesszustandes sein Dies erf llt zugleich die letzte Bedingung dass tempor re Daten gesichert werden Dies ist notwendig um in der Mitte unterbrochene Werkzeuge wieder fortsetzen zu k nnen auch dann wenn lokale Prozedurvariablen bereits gel scht wurden Das Ablegen des Prozesszustandes und der zugeh rigen Konfiguration erfolgt wie in Ab schnitt 4 2 3 beschrieben Durch die Verbindung des Model mit dem DBS bietet es sich an tempor re Daten der Werkzeuge in Form von tempor ren Tabellen in der Datenbank abzulegen Dabei ist darauf zu achten einen Namen f r die Tabelle zu w hlen der mit der Datenstruktur vereinbar ist Das hei t der Name ist nicht bereits Teil des Schemas 54 KAPITEL 4 KONZEPTION Kapitel 5 Benutzerhandbuch Dieses Kapitel soll den Umgang mit der Anwendung demonstrieren 5 1 Installation und Ausf hrung Die Anwendung besteht aus einem Packet mit drei Softwareteilen und einer Unterst t zungsdatei Das Hauptprogramm befindet sich in der DBCleaning jar Als exte
51. as f r jedes Tupel einen individuellen Wert beinhaltet auf bereinstimmung gepr ft Aufw ndiger wird die Duplikaterkennung wenn ber die hnlichkeit von Tupeln ent schieden werden muss Nach einer ersten groben Rasterung kann man die Ans tze zu verschiedenen Verfahren einteilen in lernende und algorithmenbasierende Ans tze Den lernenden Ans tzen liegt im Gro en eine Benutzerinteraktion zugrunde nach der ein Muster gebildet wird anhand dessen sich das hnlichkeitsma bei der Entscheidungsfin dung orientiert Da f r diese Arbeit m glichst wenig Interaktion gew nscht wird sei auf diese Ans tze hier nur verwiesen Eine bersicht findet sich erneut im Artikel ETV07 Bei den algorithmenbasierenden Ans tzen interessieren vor allem die Laufzeiten Ein ein facher Vergleichsalgorithmus wurde bereits in Abschnitt 2 2 gezeigt Die Laufzeit eines solchen Algorithmus ist verst ndlicherweise sehr hoch Die h ufigsten vorzufindenden Verfahren lassen sich einordnen in fensterbasierend und clusterbasierend Bei Fensterbasierenden Verfahren werden die Tupel nach einem Schl ssel sortiert der so berechnet wird dass hnliche Tupel nah beieinander liegen Anschlie end wird mit einer festen Fenstergr e ber die Datens tze gegangen und diese jeweils innerhalb des Fensters untereinander verglichen Ein h ufig erw hnter Vertreter ist die Sorted Neighborhood Method SNM HS98 Clusterbasierende Verfa
52. aus Auflistung 3 2 die Lower und Upper Bound wie folgt LBp A C Sim A B Sim B C 1 UBg A C 1 Sim A B Sim B C Lemma 1 aus ZLBL04 besagt Erf llen die generierten Ahnlichkeitsfaktoren die Drei ecksungleichung insbesondere auch die Ungleichung aus Auflistung 3 2 so gelten die LB und UB Gleichungen A C B 0 6 9 14 20 AC 17 20 AB 12 20 CB 15 20 LB A C 12 20 15 20 1 7 20 UB A C 1 12 20 15 20 17 20 gt 7 20 lt AC lt 17 20 Abbildung 3 3 Lower und Upper Bound am Zahlenstrahl Ein solcher Ahnlichkeitsfaktor der die Ungleichung aus Auflistung 3 2 sicher erfiillt muss folgende Punkte mindestens erf llen e durch geschlossenes Intervall begrenzt e gleiches Verfahren zur Faktorbestimmung f r jedes Tupelpaar Die Intervallbegrenzung ist notwendig um die h chste und niedrigste hnlichkeit fest legen zu k nnen Au erdem muss das Verfahren zur Bildung des hnlichkeitsfaktors das umfasst auch das hnlichkeitsma f r jedes Tupelpaar gleich sein Wie bereits in Abschnitt 3 4 zu sehen war bilden selbst hnliche Verfahren andere Faktoren Wird f r verschiedene Tupelpaare unterschiedliche Verfahren verwendet sind diese nicht vergleich bar Es k nnte kein Dreieck gebildet werden da zum Beispiel AC keinen Zusammenhang zu BC hatte Grams und Field Similarity erf llen sowohl die allgemeine Dreiecksungleichung als auch die Ungleichung nach Auflistung
53. d Wie aus 4 2 2 bereits zu entnehmen und wie es sich im Folgenden zeigen wird besteht die Konfiguration aus einzelnen Bl cken Jedes Werkzeug hat seinen eigenen Konfigu rationsblock Dazu kommt der Block f r allgemeine Einstellungen im Folgenden auch 36 KAPITEL 4 KONZEPTION Frameworkeinstellungen Es bietet sich an eine lokale Speicherstruktur zu nutzen mit derer es moglich ist diese Blocke geordnet zu speichern Idealer Weise lassen sich diese Daten in einer Datenbank ablegen da diese bereits geordnete Strukturen bereitstellt Ei ne Portabilit t w re mit dieser L sung allerdings sehr gering Als besseres Beispiel sei die Extensible Markup Language XML erw hnt mit derer es m glich ist die Daten wie in einer lokalen Datenbank abzulegen und zu verwalten Zudem k nnen diese Dokumente mit sehr geringem Aufwand zwischen verschiedenen Clients ausgetauscht werden 4 3 Ablaufbeschreibung Der bisherige Aufbau des Frameworks besteht aus den Bl cken Konfiguration und Ab laufsteuerung Aus diesen Bl cken die den Aufbau beschreiben sind nun Funktionsbl cke abzuleiten die einen Ablauf beschreiben Aus den Architekturebenen der Abbildung 4 1 ist eine Trennung zwischen dem Client also der dem Framework zugrunde liegen den Instanz und dem DBS zu erkennen Um diese Verbindung herzustellen bedarf es dem Block Initialisierung Dieser Block muss folglich vor der ersten Kommunikation mit der Verarbei
54. d Sortieren nach hat gro en Einfluss auf die Genauigkeit des ersten Suchvor ganges Hier wird festgelegt nach welchem Schl ssel die Tabelle vorsortiert wird Stan dardm ig wird der Prim rschl ssel voreingestellt Meist ist eines der anderen Attribute aber eine bessere Wahl Sie k nnen auch komplexere Ausdr cke schreiben Im Panel mit der Bezeichnung Erweiterte Optionen k nnen Sie die Parameter des Du plikaterkenners modifizieren Das Feld Partitionen gibt an wie stark die Tabelle aufgeteilt wird Eine hohe Aufteilung beschleunigt den Vergleich innerhalb der Partition Allerdings vergr ert sich die Anzahl 64 KAPITEL 5 BENUTZERHANDBUCH der Vergleiche mit u eren Partitionen Das Feld Randbereich legt die Anzahl der Randelemente pro Partition Die Eingabe sollte ein gerader Wert sein Ein gr erer Randbereich verbessert die Genauigkeit des u eren Vergleichs die Anzahl der Vergleiche nimmt aber zu Mit dem Feld Genauigkeit stellen Sie die Grenze ein nach der ein Tupel noch als Duplikat erkannt wird Die Schaltfl che Referenzwerte ffnet einen Dialog zur Eingabe von Referenzwertvor einstellungen Referenzwerte Attribute Mustermann Goethe Abbildung 5 11 Werkzeugeinstellung Referenzwerte Die Schaltfl che Verweise ffnet einen Dialog zur Konfiguration der Behandlung von durch Foreign Key referenzierten Tabellen Standardm ig werden die Ve
55. d Prozessliste und wird von der Klasse Controller instanziert Die Klasse stellt damit die Repr sentation der Daten senke f r die Konfiguration dar Diese wird dabei in lokalen Datenstrukturen gespeichert die ber Interface instanziert werden So ist die Prozessliste vom Typ ProcessList und der Prozesszustand wird in einer Datenstruktur des Typs ProcessState festgehalten Zum Ablegen der Konfiguration in eine externe Datei muss die Klasse Controller folglich alle in der Klasse FrameworkCFG zentralisierten Werte ablegen Dazu wird mit dem Interface IXMLWrapper eine Implementation eines XML Schreibers bzw Lesers von der Klasse 80 KAPITEL 7 IMPLEMENTIERUNG Controller instanziert dessen Methoden die in der Klasse FrameworkCFG abgelegten Datenstrukturen verarbeiten k nnen Der eigentliche Datenzugriff auf gespeicherte Daten bernimmt dabei die Bibliothek JDOM 7 2 2 4 Paket Tools interface configuration lToolList interface configuration SimList configuration FrameworkCFG confiquration Controller interface enumeration ITool configuration SimTypes RegisterTools editContign getContigshortT esti getsimblames l getSimT ypesl getToolString interactionPanel runTooll AttributReplacer TupelDuplicate editlanfigl editlanfigl CO getConfigShortTextl CO getContigShortTextl CO getSsimNamesl CO getsimNamesl getsimTypest getsimTypest getT
56. d versucht den Referenzwert anhand der Referenzwertvoreinstellung zu er mitteln Dazu werden die voreingestellten Referenzwerte mit allen Attributwerten vergli chen Wird eine deutliche hnlichkeit zu den meisten Werten festgestellt so wird dieser Referenzwert bernommen Anschlie end wird versucht durch das mehrheitliche Vorkommen eines Wertes berhalb der gesetzten Grenze den Referenzwert zu bestimmen Schl gt auch dies fehl wird eine Benutzerinteraktion verlangt bei dem der Benutzer den Referenzwert zu den Attributwerten w hlen kann Befindet sich der Nutzer in Dupli katbereinigerwerkzeugen sollte er ebenfalls eine Clusterkorrektur fordern k nnen da er eventuell fr hzeitig in der Lage ist einen solchen Erkennungsfehler festzustellen 4 7 hnlichkeitsverfahren In diesem Abschnitt behandeln wir die zur hnlichkeitsfaktorerzeugung notwendigen hnlichkeitsma e bzw direkt die erzeugenden Funktionen Die hnlichkeitsma e sind ein Hauptbestandteil der Duplikaterkennung mit PC Filter Daher erf llen die vorge stellten Ma e die in Abschnitt 3 5 beschriebene Dreiecksungleichung Zur Erstellung eines hnlichkeitsfaktors werten wir zun chst aus auf welcher Ebene das Vergleichsverfahren gestartet wurde Anschlie end bestimmen wir aus den Attributeigenschaften das ent sprechende hnlichkeitsma Der Faktor wird dann aus einer vorgeschlagenen Funktion gebildet Typ der Funktion Attribut Ebene
57. das Werkzeug verlassen Dazu wird vor dem Start der n chsten Prozedur gepr ft ob das Unterbrechungssignal gesetzt wurde Die tempor ren Daten bleiben erhalten da gem 4 4 1 1 ein stabiler Zustand erreicht wurde Eine Interaktion wird wie unter 7 4 1 ausgel st Was f r eine Interaktion angezeigt wird bestimmt das Werkzeug durch interne Variablen Das Merging wird hier mit den Besonderheiten der Tupel Ebene verwendet Da die Merging Prozedur vom Werkzeug erzeugt wird hat dies keine Auswirkung auf andere Werkzeuge Die Wahl des hnlichkeitsma es geschieht dadurch dass die Funktion zur Erzeugung des hnlichkeitsfaktors aus den Attributeigenschaften das passende Ma ermittelt Es wurden also alle erzeugenden Funktionen bertragen und die Wahl erfolgt w hrend der Laufzeit 7 5 Implementation von Verfahren Bei den hier vorgestellten Verfahren handelt es sich um die Verfahren deren Implementie rung die Unterschiede in der Realisierung der zuvor vorgestellten Verfahren verdeutlicht Weitere zuvor vorgestellte Verfahren lassen sich analog oder trivial implementieren 7 5 1 Wertunabh ngige Verfahren Diese Verfahren k nnen wir in der Regel durch eine geschickt generierte SQL Anfrage sehr einfach realisieren Dazu wird die Bedingung nach der eine Aktion ausgef hrt werden soll als Teil der Filterkette der SQL bersetzt Die Aktion selber definiert den SQL Befehl und stellt den Funktionsteil der SQL dar
58. dessen hnlichkeitsfaktor im Intervall 0 1 liegen sollten um die hier dargestellten Formeln anwenden zu k nnen Werden Tupel mit mehr als einem Attribut verglichen kann es notwendig sein Attri bute zu priorisieren Diese flie en st rker in die hnlichkeitsfaktorbildung zwischen zwei Tupeln ein Diese Priorisierung wird mit dem Attributgewicht W vorgenommen F r jedes Attribut wird ein solches Gewicht festgelegt Die Summe aller Gewichte ist 1 ia Wi Es sei hier die Definition von sim Ta T angenommen wie unter Field Similarity vgl 3 3 Der hnlichkeitsfaktor zweier Tupel A und B berechnet sich dabei aus der Summe aller Produkte aus Attributsgewicht W und hnlichkeitsfaktoren der Attribute mit als Z hler f r das aktuelle Attribut Sim A B a W sim Ta Toi Um die Datens tze effektiv zu vergleichen wird eine Art Transitivit t definiert Ziel ist aus der hnlichkeit von Tupel A zu B sowie B zu C die hnlichkeit von A zu C abzusch tzen Gehen wir von diesem Ziel aus so l sst sich aus den hnlichkeitsfaktoren ein Dreieck konstruieren 3 5 PC FILTER 29 C AC BC AB B Abbildung 3 2 hnlichkeitsfaktoren am Dreieck An diesem Dreieck k nnen wir die allgemeine Dreiecksungleichung anwenden a bl lt ce lt a b nach Abbildung 3 2 A AB b BC C ACG Auflistung 3 1 Allgemeine Dreiecksungleichung Die Begrenzungen die diese Ungleichung vorgibt bezeichnet PC Filter als Up
59. e Typ bernehmen best tigen m ssen Mit der Schaltfl che Speichern werden Ihre nderungen in die Konfiguration bernom men Mit der Schaltfl che Speichern und weiter gelangen Sie zur Prozessliste 5 2 4 Mit der Schaltfl che Abbrechen werden Ihre nderungen ignoriert und das Fenster geschlossen 5 2 HAUPTOBERFLACHE KONFIGURATION 61 5 2 4 Prozessliste Dieser Dialog dient der Verwaltung Ihrer Werkzeuge Im linken Panel sehen Sie die ver f gbaren Werkzeuge Um ein Werkzeug der Prozessliste hinzuzuf gen markieren Sie das gew nschte Werkzeug im linken Panel und bet tigen Sie die Schaltfl che Hinzuf gen ber die Schaltfl che Voreinstellung k nnen Sie typische Werkzeugkombinationen hin zuf gen lassen Um ein Werkzeug wieder zu entfernen markieren Sie im rechten Panel das Werkzeug und klicken Sie auf die Schaltfl che Entfernen Die Position des Werkzeuges in der Liste des rechten Panels ist ebenfalls die Startposi tion des Werkzeuges Um ein Werkzeug fr her zu starten benutzen sie die Schaltfl chen Hoch und Runter indem Sie rechts das Werkzeug markieren und dann auf die ge w nscht Schaltfl che klicken Werkzeugliste Prozessliste Hinzuf gen E Tupel Duplikate v Yoreinstellung T Tupel Entferner A Form tierungspr fer Entfernen 1 A Ersetzer PI PERSON NAME wolski gt Wolski A Erse
60. e public boolean isResumeable Gibt zur ck dass der Prozess fortsetzbar ist public void setResumeable boolean resume Setzt das Flag nach dem die Fortsetzbarkeit entschieden wird public int getProzessID Gibt die aktuellen Prozess Id zur ck public void setProzessID int prozessID Setzt die aktuelle Prozess Id public int get ToolState Gibt den Prozesszustand des Werkzeugs als Nummer zur ck public void setToolState int toolState Setzt den Prozesszustand als Nummer public String getToolOptions Gibt vom Werkzeug gesetzte Prozessdaten zur ck public void setToolOptions String toolOptions Setzt die Prozessdaten public void addToolOption int key String toolOption Setzt gesondert adressierte Prozessdaten auf den Wert von toolOption public String getProcessLog Gibt das Prozesslog zur ck public void setProcessLog String processLog Setzt das Prozesslog 96 ANHANG A API Interface IX MLWrapper public void writeConfig String saveName FrameworkCFG fCfg Speichert die in fCfg abgelegte Konfiguration mit dem Dateinamen saveName public void readConfig String loadName FrameworkCFG fCfg L dt die Konfiguration mit dem Dateinamen loadName nach fCfg public void writeState String saveName FrameworkCFG fCfg Speichert den in fCfg abgelegten Prozesszustand mit dem Dateinamen saveName public void readState String loadName FrameworkCFG fCfg L dt den Prozesszustand mit dem
61. e Datengegenst nde ergeben sich somit folgende Hierarchieebenen e Attribut Ebene 2 2 ABLAUF EINER BEREINIGUNG 9 e lupel Ebene e Beziehungen bzw Objekte Ebene als Erweiterung der Tupel Ebene 2 2 Ablauf einer Bereinigung Es bleibt zu kl ren wie mit den Fehlern umzugehen ist Dabei soll hier zun chst das Prinzip der Bereinigung einer einzelnen Tabelle dargestellt werden an dem sich sp tere Erweiterungen orientieren Der prinzipielle Ablauf einer Bereinigung l sst sich aus der Hierarchie ableiten Zun chst sei eine Bereinigung auf Attribut Ebene und anschlie end auf der Tupel Ebene durchzu f hren Dabei meint Bereinigung wieder die Zusammenfassung von Fehlererkennung und Fehlerkorrektur Mit dem Begriff hohe hnlichkeit soll hier ein hnlichkeitsfaktor bezeichnet werden der ein Paar oder eine Menge als mit Sicherheit hnlich bezeichnet Es dazu sei eine Schranke gegeben die kleiner als der gr te erreichbare hnlichkeitsfaktor ist Es soll immer dann von hoher hnlichkeit gesprochen werden wenn diese Schranke vom Faktor berschritten wird Meist ist diese Schranke als prozentuale Abweichung der Elemente der untersuchten Menge realisiert Eine niedrig gesetzte Schranke erlaubt folglich dass auch weniger hnliche Paare noch mit hoher hnlichkeit bewertet werden Es verringert sich also die Pr zision der Vorhersage der hnlichkeit w hrend bei hohen Schranken nur sehr hnliche Paare erkannt werden
62. e Menge von Attributwerten effektiv miteinander vergleichen und dieses zum Dritten auf Tupel ausweiten Durch die Auszeichnung einer Attributwertmenge als Tupel mit nur einem Attribut entf llt dieser letzte Schritt Wir brauchen also nur ein Verfahren zu w hlen dessen Duplikaterkennung vom eigentlichen Wert des Attributes unabh ngig gestaltet werden kann Dazu wollen wir das Q Gram Verfahren zur hnlichkeitsfaktorbildung vorstellen Der Vorteil dieses Verfahrens ist die Eignung zur Realisierung auf Datenbankebene da das Prinzip des Schneidens zweier Listen bereits in optimierter Form vorhanden ist Dazu werden wir zeigen dass hier insbesondere Tippfehler leicht von g nzlich anderen Worten unterscheidbar sind trotz gleichen Zeichenvorrats Zudem werden wir zeigen dass das Field Similarity Verfahren eine Ableitung des Q Gram Verfahrens darstellt und sich auf grund der Einfachheit leicht durch Kombinationen verbessern l sst Als hnlichkeitsma f r Zeichenketten wollen wir die Verfahren so festlegen dass zwei Zeichenketten einge geben werden und deren hnlichkeitsfaktor im Intervall zwischen 0 und 1 ausgegeben wird Dies erm glicht die direkte Bestimmung des hnlichkeitsfaktors zweier beliebiger Zeichenketten und erlaubt eine Verwendung im sp teren PC Filter Verfahren zur Bestim mung der hnlichkeitsfaktoren auf Attribut Ebene Das PC Filter Verfahren wird in der Literatur als robuster Duplikaterkenner auf Tupel
63. e ausgelassenen Tupel erneut zu gruppieren muss ein neuer Erkennungsvorgang aus der Prozessliste gestartet werden Nachdem der Cluster korrigiert wurde wird obiger Vorgang mit dem neuen Cluster neugestartet Es wurde also ein Prozessschritt verdeckt zur ckgegangen 4 6 Referenzwertverfahren Hier wird die Funktionsweise des Referenzwertverfahrens n her konzipiert In den hier vorgestellten Werkzeugen wird das Referenzwertverfahren als Teil des Merging siehe 4 5 realisiert indem die in 2 4 2 dargestellten Regeln umgesetzt werden Wie schon in 4 4 beschrieben hat auch das Referenzwertverfahren beschreibende Eigenschaften Parameter Cluster von Attributwerten Attributeigenschaften Grenze f r Automatik optionale Referenzwertvoreinstellung Ausgabe Referenzwert Tempor re Tabellen keine Interaktion Referenzwert abschaltbar Kontrolle vom Referenzwert f r Voreinstellungs automatik Das Verfahren ist als Funktion umzusetzen da dies mehr Flexibilit t mit Rollback Operationen erlaubt So f hrt das Merging beispielsweise eine Ersetzungstabelle Diese Eigenschaft bietet zudem wieder einen Unterbrechungspunkt Beim Referenzwertverfahren gehen wir von der bergabe einer Menge von Attributwerten mit hoher hnlichkeit aus Dies ist bereits der Fall wenn das Verfahren durch Merging aufgerufen wurde Im Weiteren folgen wir dem Vorgehen wie in Abschnitt 2 4 1 beschrie ben 4 7 AHNLICHKEITSVERFAHREN 47 Zun chst wir
64. e behandelt nicht aber die Schwierigkeiten beim Vergleich von r umlichen Daten ber cksichtigt Ein 91 92 KAPITEL 8 AUSBLICK solcher Vorgang ben tigt hnlichkeitsma e die die Geometrie der Daten auswerten k n nen Darunter k nnte man auch Vergleichverfahren f r Realms einordnen Die Anwendung besch ftigt sich mit dem Bereinigen einer Tabelle und den von ihr refe renzierten Tabellen Nicht realisiert wurde das angedachte Bereinigen von Tabellen mit Join Bedingungen die nicht zwangsl ufig einen Foreign Key besitzen Dazu m sste der Anwendungspart der sich mit der Aufl sung der Foreign Keys besch ftigt darauf erwei tert werden die Join Bedingung zu analysieren und die entsprechende Bereinigungsrei henfolge herzustellen 8 3 Sicherung der Datenqualit t Mit CHECK Constraints k nnen Attributen Vorgaben zum Wertebereich gemacht wer den Dies ist eine Eigenschaft der Tabelle und wirkt immer F r mehr Flexibilit t k nnen Trigger verwendet werden Dies sind PL SQL Strukturen die auf datenmodifizieren de Anfragen reagieren k nnen Mit einem Trigger ist es ebenfalls m glich die in dieser Arbeit entwickelten PL SQL Funktionen zur Bestimmung von hnlichkeitsfaktoren zu nutzen Damit ist es zum Beispiel m glich bei Einf geoperationen von einem Namen zu pr fen ob ein hnlicher bereits in der Tabelle vorhanden ist Dies ist n tzlich um Daten abzuhalten die nicht schon in der Tabelle sind oder g nzlich
65. e oder die inhaltliche Bedeutungen von Werten die durch Dom nentypen definiert sind Nach der Fehlererkennung wird es mitunter F lle geben in denen entschieden werden muss welche Daten als korrekt gelten Eine solche Entscheidung zu treffen und anschlie kend die Daten zu korrigieren ist Bestandteil der Fehlerkorrektur Im Falle duplizierter Datens tze ist es n tig zu entscheiden welche Informationen aus den Datens tzen den resultierenden Datensatz bilden Das daf r n tige Verfahren wird im Folgenden auch Merging genannt 1 2 Zielsetzung und Anforderungen In dieser Arbeit sollen Werkzeuge entwickelt werden die den Benutzer oder Datenadmi nistrator bei der Bereinigung von relationalen Datenbanken unterst tzen sowie Mafsnah men vorgestellt werden die zur zuk nftigen Sicherung der Datenqualit t beitragen Dazu sollen dem Benutzer Werkzeuge an die Hand gegeben werden die ausgesuchte Ver fahren der Literatur umsetzen und vom Benutzer auf seine Datenbank eingestellt werden k nnen oder mit etwas Programmieraufwand auf eigene Datentypen oder Eingabeforma te erweitert werden k nnen Dabei soll vom Benutzer abgesehen von der Konfiguration auf den Datenbestand m glichst wenig Interaktion erforderlich sein Ebenso sind f r den Benutzer geeignete Voreinstellungen f r Konfigurationsm glichkeiten zu w hlen Als be sonderes Problem gilt es hierbei die Erkennung von Fehlern in zueinander in Beziehung gesetzten Tabellen zu er
66. egeben Als q w hlen wir 2 Die resultierende Menge ist G1 Ge1 eo1 or1 rg1 Ge2 e 1 Diese Mengen die sich aus zwei Eingangszeichenketten ergeben werden anschlie end geschnitten Die Schnittmenge enth lt alle berlappenden Teilstrings der Lange q der beiden Eingangszeichenketten Das hnlichkeitsma ist also das berlappen bzw die Anzahl der berlap pungen der Q Grams zwischen den Zeichenketten Den hier vorgestellten hnlichkeitsfaktor erhalten wir durch die Anzahl der berlappun gen in Relation zu der Gesamtzahl der Elemente des Verbundes der Eingangsmengen e Z Hanna 3 2 Q GRAMS 21 Zo Hanan T H1 Hal anl nn1 nal a 1 T gt H1 Hal anl nal an2 n 1 T AQT H1 Hal nal anl TUT H1 Hal ant nn1 nal a 1 an n 1 sim Tz T2 pie 4 0 5 Beispiel 3 1 Zeichendreher mit q 2 e Z Henne Z Hanna T H1 Hel en nn1 nel e 1 T H1 Hal anl nn1 nal a 1 TAT H1 nn1 T UT3 H1 Hal an1 nnl nal a 1 Hel enl nel e 1 TAT sim Tz Tz FOR 2 1 0 2 Beispiel 3 2 Austausch von zwei Zeichen mit q 2 e Z Mainz Z Heinz T M1 Mal ail inl nz1 z 1 T gt H1 Hel eil inl nz1 z 1 TAT in1 nz1 z 1 T UT M1 Mal ail inl nz1 z 1 H1 Hel eil sim Tz Tz Glo 4 0 3 Beispiel 3 3 unahnliche Zeichenfolge mit q 2 e T M1 Mal Mail ainl inz
67. eichendreher und Zeichenketten mit gleichem Zeichenvorrat zu erkennen Q Grams eignet sich zur Bewer tung der Folge der Zeichen Es biete sich an diese Eigenschaften zu kombinieren um sowohl Tippfehler finden zu k nnen als auch falsche Erkennungen durch hnliche Zei chenvorr te zu vermeiden Des Weiteren liegt es in der Definition der Verfahren eine Menge an W rtern zum Beispiel S tze als ein einziges Wort zu behandeln Durch den Einsatz des Atomic String Prinzips k nnen die Verfahren auch auf S tze angewandt wer den 3 5 PC Filter Das gew hlte Verfahren zur Duplikatserkennung entstammt dem Artikel ZLBLO4 Es handelt sich um ein Verfahren das in drei Hauptschritten eine Menge an Tupeln auf Du plikate untersucht Das hier vorgestellte Verfahren bedarf einer Menge an Tupeln einer Vorgabe f r die Anzahl an Partitionen die Gr e des einzubeziehenden Partitionsrandbe reiches und dem Genauigkeitsgrad als Schranke f r den hnlichkeitsvergleich Optional ist das Angeben verschiedener Attributgewichte s u und hnlichkeitsma e f r jedes Attribut 24 KAPITEL 3 AUSGEW HLTE VERFAHREN Unsortierte Datenbank Sortierte Datenbank ussere Partition Innere Partition Duplikatliste Abbildung 3 1 PC Filter bersicht Die Schritte sind e Sortieren und Partitionieren e Erstellen eines Partitionsgraphen e Partitionen vergleichen Das Verfahren ben tigt mindestens ein hnlichkeitsma
68. en Die gleichzeitige Erw hnung der Begriffe Auffinden und Korrigieren zeigt dass sich eine Bereinigung sowohl aus Fehlererkennung als auch aus Fehlerkorrektur zusammensetzt Dies ist bereits ein Hinweis darauf dass neben der Definition was bereinigt werden soll auch der Umfang bzw die Tiefe der Operationen zu definieren ist nach deren Ausf hrung der Datenbestand als bereinigt angesehen werden soll Es stellen sich folglich die Fragen e Was sind die Daten e Vas sind Verunreinigungen in den Daten e Was soll mit den Verunreinigungen geschehen Statt von Verunreinigungen kann man hier auch von Fehlern sprechen Im Weiteren sei f r diese Arbeit der Begriff Bereinigung mit Datenbereinigung in relevanten Abschnitten gleichbedeutend 2 1 1 Relevante Datengegenst nde Die Aufgabenstellung der Arbeit schr nkt den Raum in dem eine Antwort auf die zuvor genannten Fragen gefunden werden kann auf relationale Datenbanken ein Auf den ersten 5 6 KAPITEL 2 GRUNDLAGEN Blick scheint demnach die Frage nach den Daten mit Datensatzen in einer solchen Da tenbank beantwortet Betrachtet man aber nun die Informationen in einem Datensatz stellt man vor allem bei komplexen Datensatzzusammenhangen fest dass der Begriff Datensatz bzw im sp teren Tupel weder der kleinste noch der gr te Nenner f r die Definition der relevanten Daten sein kann Durch eine Zerlegung l sst sich zudem die Frage nach den Fe
69. en Feldern geordnet nach denen die Wahrschein lichkeit hoch ist dass duplizierte Tupel nah beieinander liegen zum Beispiel nach Nach name oder Orten Laufende Zahlen eignen sich eher nicht Anschlie end wird die sortierte Tabelle in eine Menge von k Partitionen aufgeteilt wobei k vorgegeben ist Von der Gr e k h ngt unter anderem ab wie viele Iterationen das Erstellen des PC Graphen ben tigt W hrend der Aufteilung ist ebenfalls die Bestimmung der Anchor Records vorzunehmen und eine hnlichkeitsliste zu erstellen in der pro Partition die hnlichkeit vom AR zu jedem Datensatz abgelegt wird Dies erleichtert das Anwenden der Eigenschaften 3 und 4 in den folgenden Schritten Um die AR zu bestimmen empfiehlt es sich das mediane Tupel einer Partition zu w hlen da bei guter Wahl der Sortierung im optimalen Fall eine Gleichverteilung der hnlichkeiten zum AR innerhalb der Partition vorliegt Schritt 2 PC Graph erstellen Der Partition Comparision Graph PCG dient dazu Partitionen zu bestimmen die untereinander gepr ft werden m ssen da deren Rand elemente andeuten dass durch das Aufteilen in Schritt 1 Tupel in u eren Partionen eventuelle Duplikate haben Dazu dient die Vorgabe des Partitionsrandbereiches N Vom Anfang und vom Ende der Partition werden je Tupel gew hlt die so genannten Deli miting Records DR Jeder DR f hrt eine Liste an Partitionen Aus dieser Liste werden alle Partitionen entfernt die die Eigenscha
70. enannt werden die auf den in 2 1 2 gezeig ten Ebenen angewendet werden konnen Dabei sei anzumerken dass es sich bei den hier vorgestellten Verfahren auf Attribut Ebene um hnlichkeitsma e handelt w hrend die Tupel Ebene sich mit der Erkennung von Duplikaten mit laufzeitoptimierten Verfahren befasst Wie wir aus Abschnitt 2 2 sehen konnten hat dies den Grund dass auch auf Tupel Ebene im Endeffekt die hnlichkeitsma e der Attribut Ebene zum Einsatz kom men und auf Attribut Ebene die Vergleichsoperationen der Tupel Ebene anwendbar sind 2 3 1 Attr but Ebene Vergleichsoperationen auf der Attribut Ebene besch ftigen sich im Allgemeinen mit der Frage wie hnlich sich zwei Zeichenketten sind Das Ziel ist einen hnlichkeitsfaktor zu ermitteln der bestenfalls darauf hinweist dass eine Zeichenkette aus einer anderen eindeutig hervorgeht Damit sollen Tippfehler und geringf gige Abweichungen behandelt werden k nnen Dazu gibt es prim r den zeichen und den lautbasierenden Ansatz um hnlichkeitsma e zu konstruieren Nummerische Vergleichsoperationen und Ma e seien hiermit als einfache Derivationen erw hnt Der lautbasierende Ansatz hat als Ziel W rter mit gleicher Phonetik aber stark abwei chender Schreibweise ermitteln zu k nnen Da dies f r diese Arbeit nicht notwendig ist sei hiermit als Beispiel auf das Soundex Verfahren verwiesen was in HMO2 zur Anwendung kommt H ufige zeichenbasierende Ans tze sind zum Beisp
71. er Cluster hnlicher Attributwerte f r das Refe renzwertverfahren ist dann die Attributwertmenge des Attributes Die Umsetzung folgt der Darstellung in Abschnitt 2 4 2 Ersetzungen werden in einer Ersetzungstabelle zwischengespeichert um beim Feststellen eines Clusterfehlers reagieren zu k nnen Dies wird umgesetzt indem die der Tupelcluster nochmals mit der Ersetzungstabelle verglichen wird Zeigt ein Tupel zu gro e Unterschie de bersteigt die gesetzte Grenze so wird eine Benutzerinteraktion verlangt Bei der Interaktion kann der Benutzer auch nachtr glich noch Werte in der Ersetzungstabelle n dern Die Eintragungen der Ersetzungstabelle ersetzen nach Durchlaufen aller Attribute die Werte der Originaltupel Wird das Merging als Teil des Tupel Duplikatbereinigers gestartet wird nach dem ber nehmen der Ersetzungstabelle ein Tupel bestimmt das als Originaltupel fungieren soll Dies kann beispielsweise Konfigurationsabh ngig geschehen nach Prim rschl ssel oder sogar nach F llstand der Attribute Nach dem Durchlaufen der Attribute werden alle als nicht original markierten Tupel gel scht Dieser Fall entf llt wenn ein Werkzeug der Attribut Ebene aktiv ist Wird eine Clusterkorrektur ausgel st so wird dem Benutzer der derzeitige Tupelcluster angezeigt Der Benutzer kann dann Tupel aus dem Cluster entfernen Diese Tupel werden dann nicht weiter behandelt da der Fehlererkennungsblock bereits abgelaufen ist Um dies
72. er SELECT Anweisung auftritt und ei ne Interaktion anfordert Eine Interaktion veranlasst die Methode im aktuellen Zustand 84 KAPITEL 7 IMPLEMENTIERUNG anzuhalten und an die bergeordnete Klasse mit Hilfe der parentAction Methode einen Interaktionsdialog einzufordern Dieser Dialog wird mit Hilfe der interactionPa ne Methode f r das Werkzeug erzeugt Intern verwenden wir immer die REGEXP Funktionalit t von Oracle mit der wir SQL Anfragen mit regul ren Ausdr cken schreiben k nnen Die Wahl nach der Art des Such musters bestimmt lediglich ob das Suchmuster bereits ein regul rer Ausdruck ist F r die SELECT Anfrage nutzen wir REGEXP _ LIKE Die Datenmanipulation kann in einem Ausdruck geschehen UPDATE SET Attribut REGEXP_REPLACE Attribut Suchmuster Ersetzung WHERE REGEXP __LIKE Attribut Suchmuster Die folgende Abbildung veranschaulicht diesen Ablauf Programmstart RegisterTools a Werkzeugeinstellung ToolName in ToolList eintrage editLonfigl mit ProzessiD aufrufen runConig ausf hren Dom ntypen und Datentypen abfragen Einstellungen zum Prozesseintrag speichern SOL Befehle anwenden parantAction interactionPane aufrufen Abbildung 7 7 Ablauf AttributReplacer Um das neu erstellte Werkzeug im Programm verwenden zu k nnen wird die Zeile Uon troller addTool new AttributReplacer in die Klasse RegisterTools eingetragen 7 4 2 Klasse TupelDuplicate Diese K
73. ererkennung und Fehlerkorrektur die durch den Block Prozess des Fra meworks gestartet werden Die Bl cke wurden beschrieben in den Abschnitten 4 2 2 und 4 3 Ein Werkzeug hat dabei f nf beschreibende Eigenschaften 1 Die Aufgabe des Werkzeuges ist dem Namen zu entnehmen und beschreibt die Bereinigung die es ausf hrt 2 Ein Werkzeug erh lt vom Framework Elemente der Konfiguration als Parameter bergeben Darunter auch dessen Werkzeugeinstellungen 3 Erstellt ein Werkzeug ein neues presistentes Objekt so erzeugt es eine Ausgabe Dies kann zum Beispiel das Schaffen einer View auf der Datenbank sein Auch der R ckgabewert einer Funktion kann eine Ausgabe sein 4 W hrend der Abarbeitung eines Werkzeuges k nnen tempor re Daten anfallen Ist es dazu notwendig aufgrund der Datenmenge kurzzeitig eine neue Tabelle anzule gen so ist dies eine tempor re Tabelle 5 Ein Werkzeug kann zu einer Interaktion auffordern wenn es auf die Hilfe vom Benutzer angewiesen ist Parameter von Werkzeugen setzen sich zusammen aus den Parametern die f r die ver wendeten Verfahren notwendig sind sowie durch Werkzeugeinstellungen die f r die spe zifische Ausf hrung des Werkzeuges notwendig sind Zum Beispiel welches Verfahren verwendet werden soll 4 4 1 Tupelwerkzeuge Werkzeuge dieser Kategorie arbeiten auf einer Menge von Tupeln Die Attribute der Tupel spielen lediglich f r die untergeordneten V
74. erfahren eine Rolle 4 4 1 1 Tupel Duplikatbereiniger Parameter Menge an Tupeln Liste der Attributeigenschaften Anzahl Partitionen Gr e des Randbereichs Genauigkeit zwischen 0 1 zus tzliche Optionen f r Merging siehe 4 5 Ausgabe keine Temporare Tabellen nach jedem Funktionsblock Interaktion Clusterkorrektur Referenzwert Wir wenden PC Filter als Duplikaterkenner an PC Filter hat dabei f nf Vorteile 4 4 WERKZEUGE Al e Es ist in einzelne Funktionsbl cke aufteilbar e Eine Implementierung nur ber Zuordnungsnummern ist m glich cher Tupel bilden Verfahren zur hnlichkeitsfaktorbildung kann leicht getauscht werden Es l sst sich vollst ndig in PL SQL implementieren Aus der Duplikattabelle s u lassen sich Cluster von Zuordnungsnummern hnli Zun chst erlaubt das leichte Aufteilen in einzelne Funktionsbl cke zum Einen den Aus tausch eben Solcher und zum Anderen bringt das Verfahren von Haus aus Unterbre chungspunkte mit an denen tempor re Daten bereits physisch abgelegt wurden Siehe dazu auch Abschnitt 4 8 Um von dieser Eigenschaft Gebrauch zu machen unterteilen wir die drei Schritte des Verfahrens in kleinere Funktionsbl cke nach denen jeweils ein fester Zustand erreicht wurde Das Ergebnis der Erkennung wird in einer tempor ren Duplikattabelle gesichert Schritt 1 Schritt 2 Schritt 3 Abbildung 4 5 Sortieren und Paritionieren hnlichkeitsliste anlegen
75. es Trennzeichens oder Satzende Gesamtzahl Gesamtzahl 1 TabelleA i Teilfolge zwischen den beiden Auftrittspunkten 1 0 fertig falsch Solange nicht fertig ES EM Finde das iten Auftreten des Trennzeichens in Eingabe B Ist kein i tes Trennzeichen vorhanden dann fertig wahr Wenn nicht fertig Bestimme n chstes Auftreten des Trennzeichens oder Satzende Gesamtzahl Gesamtzahl 1 TabelleB i Teilfolge zwischen den beiden Auftrittspunkten 9 9 Auflistung 7 3 Implementierung Atomic Strings Das Durchlaufen der Wortmengen tibernimmt die steuernde Funktion dadurch konnen die vergleichenden Funktionen sich auf den Vergleich von zwei einfachen Zeichenketten beschranken Der Boolsche Vergleich iiberpriift die Zeichenketten lediglich auf exakte Ubereinstim mung Je nach Werkzeugimplementierung kann diese Funktion auch Teil der steuernden Funktion sein Das Field Similarity Verfahren verwendet PL SQL Tabellen um die Zeichen zu z hlen Dabei wird von der M glichkeit der Oracle 10 Gebrauch gemacht dass PL SQL Tabellen auch ber Zeichenketten indexiert werden k nnen Dazu sei gesagt dass sich eine PL SQL Tabelle wie ein assoziativer Vektor verh lt Zun chst wird die erste Zeichenkette durchlaufen und zu jedem Zeichen ein Vektorindex erstellt Der Wert des Vektors am Vektorindex ist die Auftrittsnummer Wird ein Vekto rindex neu angelegt sei die urspr ngliche Auftrittsnummer 0 Bei bereits existierende
76. figuration erstellen Akutelle Konfiguration ausf hren e Eventuell aktuellen Prozesszustand fortsetzen Das Laden oder Speichern der Konfiguration erlaubt es dem Benutzer die erstellte Kon figuration f r sp teren Gebrauch abzulegen Ebenso kann er die geladene Konfiguration 38 KAPITEL 4 KONZEPTION bearbeiten Ein Sonderfall stellt das Fortsetzen einer Konfiguration dar Zum Fortsetzen muss eine Konfiguration geladen sein und ein abgelegter Prozesszustand in den Prozess block geladen werden Die geladene Konfiguration wird an dieser Stelle fortgesetzt Siehe dazu auch den Abschnitt 4 2 3 und 4 8 Das neue Ausf hren der aktuellen Konfiguration setzt den Prozesszustand zur ck Das Erstellen einer neuen Konfiguration erlaubt es dem Benutzer die zu bearbeitenden Tabellen zu w hlen sowie den Attributen Eigenschaften zuzuordnen Dies stellt die Fra meworkeinstellung dar Anschlie end wird eine Prozessliste erstellt Der Benutzer tr gt alle Werkzeuge ein die nacheinander auf die gew hlten Tabellen angewendet werden Nach erstellen der Prozessliste wird f r jedes eingetragene Werkzeug deren Eigenschaften ge ffnet Dort k nnen werkzeugspezifische Einstellungen festgelegt werden Dies ergibt die Werkzeugeinstellung Der Prozesszustand umfasst die Position der Abarbeitung der Werkzeuge in der Prozessliste im Prozessblock und wird demnach beim Erstellen einer neuen Konfiguration zur ckgesetzt Nach dem Wechsel zum Prozessbloc
77. ft 4 zu DR nicht erfiillen PartListeDR I Ppr P P u ere Partition von DR die Eigenschaft 4 nicht erf llt I ist dabei die Menge aller Partitionen und Ppr bezeichnet die eigene innere Partition von DR Aus diesen Partitionslisten kann nun die Partition Comparision Range PCR erstellt werden Die untere Grenze setzt sich zusammen aus dem Minimum aller nicht 28 KAPITEL 3 AUSGEWAHLTE VERFAHREN leeren Listen der ersten DR zu einer Partition die obere Grenze analog aus dem Maximum der letzten DR zu einer Partition PCRuntereGrenze Mind mind Pari hist DR x min PartList DRx PUR Geese max max PartList DRw t max PartList DRy Sind alle Listen der DR leer so ist dies als zu vermerken Es bildet sich eine Tabelle wie in diesem Beispiel Partitionen 1 2 3 4 J Part List Tabelle 3 3 PCR Beispiel Zum Erstellen des PCG wird jede Partition als Knoten erzeugt Von jedem Knoten geht nun eine Linie zu den Knoten dessen Partition in der PCR liegen Dabei ist darauf zu achten dass es sich beim PCG um einen ungerichteten Graphen handelt 1 ws 3 Abbildung 3 4 PCG Beispiel Schritt 3 Partitionen vergleichen Das Vergleichen der Partitionen erfolgt in zwei Schritten Innerhalb der Partition Zun chst wird innerhalb der Partitionen mit Hilfe der Ei genschaften 1 und 2 jeder Datensatz verglichen Dazu kann die in Schritt 1 erzeugte Ahnlichkeitsl
78. g Jede der sechs Prozeduren erzeugt einen stabilen Endzustand nach der die Abarbeitung pausiert werden kann Die Prozeduren werden von der Werkzeugklasse angesto en 7 5 IMPLEMENTATION VON VERFAHREN 87 7 5 3 Mergingverfahren Ziel des Verfahrens ist es aus den gefundenen Duplikatpaaren durch geschicktes Abfragen der Duplikattabelle eine Menge von Cluster von duplizierten Tupeln zu durchlaufen Die Duplikatpaare liegen als RowID Paare vor Das erste Ziel ist es anhand einer RowID alle direkt oder indirekt verbundenen RowID zu finden Dazu fassen wir die Tabelle als unge richteten Graph auf und suchen mit der Tiefensuche zu einem Knoten alle verbundenen Knoten F r jedes RowID PartnerID Paar aus Duplikattabelle Wenn RowID und PartnerlD noch nicht in Ergebnistabelle F ge Paar in Ergebnistabelle ein Sonst PartnerID in Ergebnistabelle W hle ein Paar aus der Ergebnistabelle mit PartnerID Wenn PartnerlD erstes Element vom Paar F ge das Paar PartnerID RowID in Ergebnistabelle ein Sonst PartnerlD zweites Element vom Paar F ge das Paar Erstes Element RowID in Ergebnistabelle ein Sonst RowID in Ergebnistabelle W hle ein Paar aus der Ergebnistabelle mit RowID Wenn RowlID erstes Element vom Paar Fiige das Paar RowID PartnerID in Ergebnistabelle ein Sonst RowID zweites Element vom Paar Fiige das Paar Erstes Element PartnerID in Ergebnistabelle ein Auflistung 7 1 Merging Clusterbildung Dieser Teil des Mergin
79. g 7 2 Entwurf und Aufbau oo nr 7 2 1 Paketiibersicht ooo 1 2 2 Klassen bersicht 2 2 ee 7 2 3 Aufbau von Werkzeuge 7 3 Implementation vom Prozesszustand 2 22 22 m En nn nn 7 4 Implementation von Werkzeugen 00 0080 eee 7 4 1 Klasse AttributReplacer 2 2 2 aa 7 4 2 Klasse TupelDuplicate 2 22 Co LE nn nn 7 0 Implementation von Verfahren aoao aa a a 1 5 1 Wertunabh ngige Verfahren 2 0048 7 0 2 PC Filter e 1 9 3 Mergingverfahren 2 mn 7 9 4 Referenzwertverfahren 2 2 CK oo a 7 0 0 Modifizierte Field Similarity 22 2 Co on nn 8 Ausblick 8 1 Erweiterung von Tupeln auf Objekter 8 2 Erweiterung der Werkzeuge 2 nn 8 3 Sicherung der Datenqualit t 2 2 CC Em nn nn A API A 1 Paket Configuration 2 m mm A 2 Paket View A 3 Paket Tools Abbildungsverzeichnis Beispielverzeichnis Listenverzeichnis Tabellenverzeichnis Literaturverzeichnis 73 13 13 14 19 81 82 83 83 84 89 89 89 87 88 88 91 91 91 92 101 103 105 107 109 vi INHALTSVERZEICHNIS Kapitel 1 Einleitung 1 1 Motivation Zur Archivierung einer Vielzahl von Daten setzt man heute bevorzugt Datenbanksysteme ein Solche Systeme sind in der Regel sehr leistungsstark im Management der Datens t ze und erlauben das Abspeichern unterschiedlichster Datentypen Weiterhin erlauben es relationale Datenbanken verschiedene Datentabellen in Beziehung zu
80. g zur Wahl des Referenzwertes sein 5 4 INTERAKTION 67 Merging Refernzwert PHW DBCLEANTEST PERSON Tupel anzeigen MAME VNAME INS Wolski Philipp DBS Referenzwert Wolski Prozess anhalten Clusterkorrektur ignorieren und weiter Abbildung 5 14 Interaktion Referenzwerte Im oberen Panel werden Ihnen die Attributwerte angezeigt mit denen das Werkzeug derzeit ein Problem hat Im Dialog zur Wahl des Referenzwertes werden Sie meist zur Wahl eines Wertes zur Ersetzung aller im oberen Panel angezeigten Werte aufgefordert Im unteren Panel steht Ihnen dazu ein Eingabefeld zur Verf gung Um zu einem Wert das gesamte Tupel angezeigt zu bekommen klicken Sie auf die Schalt fl che Tupel anzeigen Ihnen wird dann das zugeh rige Tupel aus der Datenbank ange zeigt In einigen F llen k nnen Sie eine Clusterkorrektur fordern Dazu klicken Sie auf die Schaltfl che Clusterkorrektur Dies erm glicht es Ihnen den Cluster zu ver ndern Dazu k nnen Sie im obigen Panel nun Tupel an oder abw hlen 68 KAPITEL 5 BENUTZERHANDBUCH Merging Clusterkorektur PH Y DBCLEANTEST PERSON MAME VNAME IMS Wolski ane DBS LI otk Philip Home Abgewahtite Tupel werden aus dem Cluster entfernt Abbildung 5 15 Interaktion Clusterkorrektur Nachdem Sie die nderung mit der bernehmen Schaltfl che best tigt haben werden die abgew hlten Tupel aus dem Cluster entfernt Der Prozessablauf wird solan
81. ge angehalten bis Sie die Interaktion beendet haben Dies dient der Datensicherheit f r nachfolgende Werkzeuge W hrend der Interaktion kann der Prozess auch angehalten werden Kapitel 6 Testbericht Wir wollen hier eine Bereinigung der Schlagworte versuchen Hierzu kommt der Attribut Duplikatbereiniger zum Einsatz Dieses Beispiel ist leicht zu konfigurieren und einfach nachzuvollziehen Dennoch wird hier die Erkennungsrate von PC Filter und unserem modifizierten Field Similarity Verfahren scharf gepr ft wie sich sp ter zeigen wird Aus Sicherheitsgr nden wird eine Kopie der Schlagworttabelle genutzt 6 1 Vorbereitung Wir stellen die Frameworkeinstellungen wie in Abschnitt 5 2 ein In der Tabellenkonfigu ration w hlen wir jedoch die kopierte Tabelle Schlagworte 2 Tabellenkonfiguration Tabellen im Benutzerschema Tabellenkontiguration WOLSKIL PRUEFUNG_CP Manueller Eintrag WOLSKIPRUEFUNG_TMP IT WOLSKLSANGEBOT WOLSKLSANGEBOT_CO WOLSKLSANGEBOT_CO WOLSKISANGEBOT_CP WOLSKLSCHLAGWORT WOLSKLSCHRIFT WOLSKLSCHRIFTTYP WOLSKISEMESTER WOLSKILSEMESTER_CO WOLSKILSEMESTER_CO WOLSHKISEMESTER_CP WOLSHKI SG_KAT WOLSKISG_KAT_COPY WOLSHKI SG_KAT_COPY WOLSKISG_KAT_CP_F WOLSKISTUDIENGANG WOLSKLSTUDIENGANG_ WOLSKLSTUDIENGANG_ Abbrechen Speichern und weiter WOLSKILSCHLAGWORT Abbildung 6 1 Schlagworttabelle w hlen 69 10 KAPITEL 6 TESTBERICHT Wir stellen bei der Attributkonfigu
82. geleitet von StandardDialogView und mit dem Fenster vom Typ InitDialog lassen sich diese Klas sen ber die generische Instanz beschreiben Damit k nnen sowohl beliebige Klassen diese Klassen instanzieren als auch beliebige weitere Fensterklassen ber die Dialoge instanziert werden Die Methode saveEntries stellt dabei die bernahmefunktion der Einstellungen in die Konfiguration dar Der Prozeduraufruf ist nicht vererbt sondern stellt die Verbindung zwischen der vom Controller Element verwalteten Konfiguration und der Bedienober fl che der View Elemente dar vgl Abbildung 4 2 Die Methode parentAction wurde aus der Ableitung von der abstrakte Klasse StandardView implementiert Mit dieser kommunizieren Fenster mit deren aufrufen den Fenstern Insbesondere die erw hnten Dialogfenster geben der Klasse FrmMain View deren Zustand zur ck der dort weiter ausgewertet wird So wei am Ende der Controller immer in welchem Prozesszustand sich die Anwendung befindet da auch Interaktions fenster diesem Schema folgen 18 3 InitFrame G Initview certerFramel disableFrame dizableResizel enableFramec enableResizer hide packi resizeframel resizeframel resizeFrameScreen showt E 8668666666 unload 3 InitlFrame KAPITEL 7 InitDialog IMPLEMENTIERUNG 3 GBCHelper ma oO oO oO oO a oO oO a oO oO oO oO oO oO oO oO oO oO oO oO oO oO oO m OO gE pane
83. getDkSIC gelfrocess rrayl getSelExtrasl getSelfieldsl getSelFiterl getSelFrome getSelOrderl readLonfigl Ta getTblList readstater getToollbC wette Oplo ainterface oO getToolOptionst wvriteState lAttrList EE getvVorkList isdbCtyc sinterface 3 Controller STooht Zo IToolList interface IProcessList interface IProcessState interface IXMLWrapper removeProcesst setAttrotgn Da setCurstatel setDeCtg setDbHostl setDbPort setDbSIDC setselExtrasl setselfieldsl setSelfiterl setSelFrome setSelOrder l interface setThiList ISimList o setTaolctal etToolOptionsl 3 connection DBConnect interf o o O toole ITool connection DBDriver aenumeration tools RegisterTools SimTypes gl setvVorkList Abbildung 7 5 Klassendiagramm Paket Configuration Die meisten der in Abbildung 7 5 gezeigten Klassen bilden interne Datenstrukturen Der genaue Aufbau dieser Strukturen wurde aus Gr nden der bersichtlichkeit weggelassen ber die Klasse RegisterTools des Paket Tools werden die im Projekt verf gbaren Werkzeuge der Konfiguration bekannt gemacht indem diese in einer von der Klasse Controller gef hrten Liste vom Typ ToolList eingetragen werden Diese Liste enth lt Elemente des Typs Tool der im Abschnitt 7 2 3 n her beschrieben wird Die Klasse FrameworkCFG verwaltet die Konfiguration un
84. gs l sst sich aus einer Reihe von Abfragen als PL SQL schreiben F r die Umsetzung nach Auflistung 7 1 muss gelten dass keine doppelten Einf gungen erlaubt sind und dass die Elemente der eingef gten Paare nicht gleich sind Anschlie end wird auf Anwendungsebene ein Cluster gew hlt und f r jedes Attribut das Referenzwertverfahren gestartet Dabei wird mitgef hrt in welchem Cluster und in welchem Attribut sich das Verfahren gerade befindet Die R ckgaben des Referenzwert verfahrens werden in der Ersetzungstabelle tmpMerging abgelegt Dabei wird jedem Attribut der Referenzwert zugeordnet Diese Zuordnung kann dann in eine automatisch generierte UPDATE Anweisung umgesetzt werden UPDATE SET Attribut ZugeordneterWert WHERE RowID aktuelle ID Beispiel 7 2 Auswertung der Ersetzungstabelle Wenn das Merging als Teil einer Duplikatbereinigung auf Tupel Ebene gestartet wur de also explizit durch das Werkzeug Iupel Duplikatbereiniger kann das Ersetzen und Entfernen duplizierter Tupel vereinfacht werden indem f r das Originaltupel die den aktuellen Cluster beschreibende RowID verwendet wird Es werden nur in diesem Tupel 88 KAPITEL 7 IMPLEMENTIERUNG Attributwerte ersetzt und anschlie end alle dem Cluster zugeordneten Tupel au er dem Original gel scht Auf Attribut Ebene m ssen alle mit den RowIDs adressierten Tupel angepasst werden und das L schen entf llt Da diese letzten Operationen auf Anwendungsebene gesche
85. h alle andere Elemente auf Benutzerebene befinden ist die erste Vorgabe bereits erf llt Unter Beachtung der unter Abschnitt 1 2 geforderten Konfigura tionseigenschaften und einer eventuellen Unterbrechungs Option wie unter 4 8 beschrie ben ist es notwendig auch auf Benutzerebene einen Datenspeicher zu f hren Dieser kann dabei aber so gestaltet werden dass es sich hierbei nur um eine Sammlung von Zust n den des Controller handelt Dieser kann wenn auch extern gelagert direkt wieder in den Controller eingelesen werden Daher kann diese Funktionalit t als Erweiterung der Controller Funktionalit t aufgefasst werden Es bleibt zu kl ren f r welche Daten des Controller eine persistente Speicherung Sinn macht Das w re zum Einen die Konfiguration In der Konfiguration sind alle vom Benutzer vorgegebenen Einstellungen enthalten Wird diese gespeichert so braucht die se nicht erneut manuell Eingegeben werden wenn die Anwendung zur ckgesetzt wird sondern kann wieder geladen werden Zum Anderen macht das Ablegen des Zustandes der Anwendung Sinn da hiermit der zuletzt aktive Block gem 4 2 2 fortgesetzt werden kann Es reicht den Zustand der Ablaufsteuerung zu speichern da sich die Zust nde der Konfiguration mit dem Erzeugen der zuvor erw hnten Konfiguration besch ftigen und mit dem Speichern eben solcher nicht mehr relevant sind Der Zustand der Ablauf steuerung ist der Prozesszustan
86. hen wird das Verfahren je nach Werkzeug entsprechend anders implementiert 7 5 4 Referenzwertverfahren Das Referenzwertverfahren ist als PL SQL Funktion implementiert Es wird eine SE LECT Anfrage bergeben die in einem Cursor ge ffnet wird Dadurch ist die Funktion unabh ngig vom Zustand tempor rer Tabellen Es wird davon ausgegangen dass immer nur ein Attribut ausgewertet werden soll Entsprechend wird die Attributeigenschaft di rekt bergeben Das Verfahren kann entweder Gebrauch von der tmpAttribute Tabelle machen oder vom Werkzeug mit einem festen hnlichkeitsma erstellt werden Die im Cursor ge ffnete Anfrage wird auf die nach Abschnitt 4 6 beschriebenen Arten untersucht Inwieweit alle Arten unterst tzt werden h ngt vom gew hlten Werkzeug ab Das Grundprinzip f r eine automatische Erkennung lautet dabei F r alle Attributwerte der Query z hle Auftreten des Attributwertes Suche Attributwerte mit der h chsten Auftrittszahl Wenn Anzahl der gefundenen Attributwerte gt 1 Fehler Benutzerinteraktion ben tigt Teile h chste Auftrittszahl durch Gesamtzahl an Attributwerten Wenn die Division eine vorgegebene Schranke berschreitet gebe Attributwert mit h chster Auftrittszahl zur ck sonst Fehler Benutzerinteraktion ben tigt Auflistung 7 2 Referenzwert automatische Bildung Der gefundene Referenzwert wird zur ckgegeben In den aus Kapitel 4 vorgestellten Werkzeugen wird das Referenzwertverfahren i
87. hlern leichter beantworten Das kleinste Element in dem relevante Daten zu finden sind ist das Attribut Die in ihm enthaltenen Daten bilden den Attributwert bzw auf die ganze Tabelle betrachtet die Attributwertmenge Dem Attributwert liegt in der Regel ein Datentyp zugrunde Zum Beispiel k nnen Attri bute mit Ziffern den Datentyp Nummer haben aber auch die Definition als Text ist m g lich Zus tzlich kann von den Werten ein festgelegtes Eingabeformat verlangt werden zum Beispiel Irennstriche nach je drei Ziffern Insbesondere bei einem solchen Eingabe format entspricht der Datentyp trotz der Speicherung von Ziffern meist dem Datenyp Text Diese beiden Eigenschaften gelten generell f r das gesamte Attribut dass hei t der Inhalt der einzelnen Attributwerte ist f r die Anwendung dieser Eigenschaften nicht von belang Ein Attributwert hat zus tzlich zum Datentyp und Eingabeformat auch eine Bedeu tung Diese ist meist nicht automatisch zu erschlie en Wir nehmen dazu an dass sich die Wertemenge eines Attributes in einer Dom ne befindet in denen dom nenspezifische Regeln gelten Anders ausgedr ckt beschreibt hier der Dom nentyp den validen Werte bereich eines Attributwertes gem den in der Dom ne geltenden Vorgaben Zum Beispiel muss eine als Text gespeicherte Identifikationsnummer anders behandelt werden als ein als Text gespeicherter Name da geringf gige Unterschiede zweier Attributwerte im Fall der Identifikat
88. hren gehen von einer angenommenen Transitivitat von Ahnlich keiten aus Das hei t Wenn A hnlich zu B ist und B hnlich zu C so ist A in gewissen Schranken hnlich zu C Unterteilt man den Datenbestand nun in Abschnitte also Clus ter in denen die hnlichkeit nur zu einem stellvertretendem Tupel innerhalb des Clusters berechnet wird braucht zum n heren Vergleich nur noch dieses stellvertretende Tupel ge nutzt werden Von dem oben erw hnten SNM Verfahren gibt es als Erg nzung dazu auch das Clustering SNM HS95 Dabei wird nach dem Sortieren der Datenbestand in klei ne Cluster unterteilt und in denen zun chst unabh ngig SNM angewendet Dabei wird davon ausgegangen dass bei der vorhergehenden Sortierung alle hnlichen Tupel bereits nahe beieinander liegen Es werden die Vergleichsoperationen an den Cluster berg ngen vermieden die beim normalen SNM vorkommen 14 KAPITEL 2 GRUNDLAGEN Kombiniert man diese Technik noch mit dem Aufspalten in Ahnlichkeitspartitionen ge langt man zum Verfahren PC Filter aus ZLBLO04 das in Kapitel 3 5 vorgestellt wird 2 3 3 Objekt Ebene W rde man die Objekt Ebene realisieren so unterscheidet sie sich von der Tupel Ebene haupts chlich davon dass zur Erkennung von Duplikaten enthaltene Verweise auf andere Tabellen mit ber cksichtigt werden Dazu kann eine Beziehung mit einem hnlichkeits maf bewertet werden und dessen Faktor dem Objekt mit zugerechnet werden Anschlie
89. hstaben in Buchtiteln andere Schreibweise f r gleiche W rter oder durch Fehler in der automatischen Neuformatierung von Quelldaten Das Resultat solcher Fehler sind gleichbedeutende Attributwerte in unterschiedlichen Datens tzen mit abweichender Schreibweise oder sogar duplizierte Datens tze Fehler in einer komplexen Datenbank zu beheben kann per Hand sehr aufw ndig sein Da solche Systeme meist darauf ausgelegt sind eine gro e Anzahl an Eintr gen zu verar beiten l ge es nahe dem Datenbanksystem diese Aufgabe zu berlassen Dazu m ssen Methoden entwickelt werden mit denen das System in der Lage ist in annehmbarer Zeit selbst ndig datenbezogene Fehler erkennen und beheben zu k nnen Solche Methoden findet man in der Literatur unter den Begriffen Data Cleaning und Data Cleansing und 2 KAPITEL 1 EINLEITUNG ordnet solche in die Thematik Sicherung der Datenqualit t BS06 ein Der Vorgang ei ner solchen Fehlerbereinigung umfasst wie schon angedeutet die Fehlererkennung und anschlie end die Fehlerkorrektur Die Verfahren zur Fehlererkennung m ssen insbesondere bei der Suche nach duplizierten Daten in der Lage sein sowohl die inhaltliche Gleichheit von Attributwerten zu beurteilen als auch die von ganzen Datens tzen zu erkennen und dies auch in Beziehung gesetzten Tabellen In der Regel erfordert dies eine Spezialisierung auf den gew hlten Datenbestand insbesondere auf die definierten Eingabeformat
90. i vielen Dupli katen auch h ufiger unentdeckt Um dennoch Schreibfehler finden zu k nnen m sste die Duplikattabelle auf eher un hnliche Tupel gepr ft werden Eine einfache L sung w re die Vorauswahl die PC Filter trifft einzuschr nken So kann mit einem Distinct vor der Cursoroffnung ein Gro teil der berfl ssigen Duplikate vermieden werden Dies w re ein Ansatz um die Werkzeugsuite noch zu erweitern Aus den bereits erkannten Duplikaten geht ebenso noch hervor dass die gew hlte Ge nauigkeit bei der hohen Ahnlichkeit zueinander zu gering war ey eet Sech 1274 default reasoning default inhertance 1275 default reasoning default inhertance 1276 default reasoning default inhertance 1277 default reasoning default inheritance 1275 default reasoning default inheritance 1279 default reasoning default inheritance 1280 detaut reasoning default priorities 1231 detaut reasoning d etault priartic 1202 default reasoning default priorities 1253 detaut reasoning defaut priorities sree tau reasoning detaut priorities 1255 FAEM reasoning defautt priorities ede raut reasoning default priorities 1287 EEM reasoning d etault priartie Moree taut reasoning default priorities 1259 default reasoning defaut reaoning 1230 default reasoning defaut reaoning 1291 default reasoning default reaoning 1292 default reasoning defaut reaoning 1293 default reasoning default reacning 1294 defau
91. iel die Ma e Edit Distanz Die Edit Distanz stellt ein einfaches Verfahren dar um die Distanz und daraus abgeleitet die hnlichkeit zweier Zeichenketten zu bestimmen vgl Lev66 Dabei wird bestimmt wie viele Ersetzungsoperationen auf einen Ausdruck angewendet werden m ssen um den jeweils anderen Ausdruck zu erhalten Ber cksichtigt wird jedoch nicht welche Zeichen im Ausdruck gesamt verwendet wurden So ist die Distanz von Mainz und Heinz genauso gro wie Heinz zu Heniz Dass es sich bei letzterem um eine h here hnlichkeit durch einen vermutlichen Tippfehler handelt ist nicht unmittelbar zu entnehmen Es bedarf dazu einer Erweiterung des urspr nglichen Verfahrens Q Grams Beim Q Gram Verfahren werden Zeichenketten in Teilketten Q Grams der L nge q aufgeteilt Die Theorie ist dass wenn Zeichenketten hnlich sind sich viele solcher Q Grams berlappen Der hnlichkeitsfaktor zweier Zeichenketten ermittelt bei spielsweise sich aus der Anzahl solcher berlappungen zur Gesamtzahl der Q Grams Eine umfangreiche Erweiterung als vollst ndige Vergleichsoperation ist dem Artikel MB06 zu entnehmen Dieser besch ftigt sich mit der Verwendung von Q Grams zur Erkennung von hnlichen Attributwerten in Attributwertmengen schlie t also neben dem hnlich keitsma auch eine Anwendung in hier spezialisierten optimierten Verfahrensweisen f r Mengen ein zum Beispiel Cluster Bildung Field Similar
92. iert Zur Fehlerkorrektur verwenden wir wieder das Merging nach 4 5 Durch das bergeben von nur einem Attribut reduziert sich das Merging auf ein Referenzwertverfahren nach 4 6 Der Ablauf dieses Attributwerkzeuges wurde auch im Abschnitt 2 2 grob beschrieben Wir machen uns hier zunutze dass Merging beschrieben nach 4 5 unter Ausnutzung der Bediengungen aus 2 4 2 immer auch ein Referenzwertverfahren einleitet 4 4 2 4 ISBN Pr fer Dieses Werkzeug ist Teil der aus Abschnitt 2 5 geforderten Attributwerkzeugen Parameter Tabelle Attribut ISBN Format Ausgabe keine Tempor re Tabellen ung ltige Nummern Interaktion Benutzerkorrektur f r unklare F lle Ziel des Werkzeuges ist es falsch formatierte ISBNs zu korrigieren Dazu behandelt es die Attributwerte eines Attributes als ISBN Das Werkzeug wird in zwei Schritte durch gef hrt Als Erstes wird auf G ltigkeit der ISBN hinsichtlich Stellenzahl und Zeichenfolge ohne Beachtung von TIrennzeichen gepr ft Nicht g ltige Nummern werden gesammelt und sp ter zur Benutzerinteraktion angezeigt Vorzugsweise mit weiteren Informationen f r den Benutzer Eine entsprechende Einstellung zur Darstellung kann in den Werkzeugein stellungen konfiguriert werden Als Zweites wird versucht das vorgegebene ISBN Format anzuwenden Dies kann zum Beispiel das Einsetzen von Trennzeichen sein oder die Umrechnung in 10 bzw 13 stellige Nummern Nicht berechenbare Nummern werde
93. intypen zu Attributen Die tmpAttribute Tabelle wird aus den Werkzeugeinstellungen generiert und wird fiir die Zuweisung eines hnlichkeitsma es gebraucht Die erste Prozedur sortiert die Tupel gem der Sortiervorgabe und ordnet allen RowIDs eine Partition zu Zeitgleich werden die AR und DR Tupel bestimmt Diese Zuordnungen werden in der tmpPartition und tmpPCR Tabelle abgelegt Mit der Bestimmung der DR Tupel kann auch die PartList zu dem Tupel in tmpPCRList abgelegt werden Die zweite Prozedur berechnet die hnlichkeitsfaktoren zum AR und legt diese mit in tmpPartition ab Die dritte Prozedur wendet nun die Eigenschaft 4 von PC Filter auf die in tmpPCRList abgelegten PartListen an Das Ergebnis wird wieder in tmpPCRList gespeichert Die vierte Prozedur erstellt den PCG aus den PartListen in tmpPCG Die f nfte Prozedur sucht innerhalb der Partitionen nach Duplikaten und legt diese in tmpDuplicate ab Die sechste Prozedur durchl uft die Knoten des PCG aus tmpPCG und sucht nach Du plikaten und legt diese in tmpDuplicate ab Die hnlichkeitsma e werden als PL SQL Funktionen implementiert Dadurch k nnen interne Speicherstrukturen der Datenbank genutzt werden Das f r ein Attribut n tige hnlichkeitsma wird mit einer Funktion bestimmt die die tmpAttribut Tabelle ausliest und die passende Funktion ausf hrt PC Filter verweist auf diese Auswahlfunktion und ist damit von der Konfiguration der Tabelle weitgehend unabh ngi
94. ionsnummer eher keine Tippfehler sein d rften wie dies bei einem Namens feld vermutet werden k nnte Auch wenn beide Attribute keiner speziellen Formatierung unterliegen und beide vom Text Datentyp sind kann man hier zur Untersuchung den Do m nentyp als DNummer vorgeben Diese Dom ne kann die Regel beinhalten dass deren Werte als fortlaufende Zahlen behandelt werden sollen und damit ein boolscher Vergleich stattfinden soll statt eines hnlichkeitsvergleichs Zur Veranschaulichung betrachten wir zum Beispiel die hnlichkeit zwischen 12 und 15 Ausgehend von einer Zeichenfolge k nnte man eine hnlichkeit 50 annehmen da immerhin ein Zeichen identisch ist Als Zahl betrachtet stehen jedoch beide Werte f r sich allein Datentyp Eingabeformat und Dom nentyp stellen die Attributeigenschaften dar und bestimmen welches hnlichkeitsma gew hlt werden muss das speziell die hnlich keit zwischen Attributwerten in deren Attributwertmenge bewertet hnlichkeitsma e k nnen im Folgenden auch zur Bewertung ganzer Datens tze untereinander definiert werden Vergleichsverfahren benutzen hnlichkeitsma e um hnlichkeitsfaktoren zu ermitteln anhand derer die Gleichheit zweier Werte vorhergesagt werden kann Wir k nnen zusammenfassen dass hnlichkeitsma e ein Vorgehen zur Bestimmung der hn lichkeit beschreiben w hrend hnlichkeitsfaktoren die Darstellung der hnlichkeit als Wert bezeichnen Diese Begriffe
95. iste verwendet werden indem in den Eigenschaften fiir das Tupel D der AR eingesetzt wird Damit kann dieser Vergleich durch einen Sweep also dem alleinigen 3 5 PC FILTER 29 Durchgehen der hnlichkeitsliste erfolgen Kommen 1 und 2 zu keinem Ergebnis m ssen die Datens tze direkt verglichen werden ohne Transitivit tausnutzung oder mit genauerem hnlichkeitsma Au erhalb der Partition Wurden alle Partitionen durchsucht wird der PCG abge arbeitet F r jeden Knoten also Partition werden die verbundenen Partitionen gepr ft Dabei wird f r jeden Datensatz R der inneren Partition mit Eigenschaft 3 die hnlich keit zu jedem AR der verbundenen u eren Partitionen gepr ft Kommt dies zu keinen Schluss wird mit Eigenschaft 4 die hnlichkeiten der ganzen benachbarten Partitionen zu R verglichen Kommen 3 und 4 zu keinem Ergebnis ist R mit Eigenschaft 1 und 2 und jedem Eintrag der benachbarten Partition zu vergleichen Nachdem alle verbun denen u eren Partitionen gepr ft wurden kann der Knoten der innere Partition und die damit verbundenen Linien gel scht werden Wurden alle PCG Verbindungen abgearbeitet ist die Suche abgeschlossen Wurde durch die Anwendung von Eigenschaften 1 und 3 oder durch direkten Vergleich festgestellt dass das Tupel R ein Duplikat zu einem oder mehreren weiteren Tupeln ist so sollen diese Tupelpaare in der Duplikatsliste abgelegt werden Diese Ergebnisliste ist gruppiert
96. ity Dies ist ein einfaches Verfahren das die Abweichung zweier Zeichen ketten berechnet indem es jede Zeichenkette in seine Zeichen zerlegt und ein wiederhol tes Auftreten dieser vermerkt Die so erhaltenen Mengen an Zeichen Auftritts Elementen 2 3 VERFAHREN ZUR FEHLERERKENNUNG 13 werden geschnitten Das Ergebnis des Schnitts ins Verh ltnis zur Zeichenanzahl der Aus sangszeichenketten gesetzt ergibt dann einen hnlichkeitsfaktor Ein detaillierter Ein blick findet sich im Kapitel 3 3 dort wird auch die Verwandtschaft zu Q Grams deutlich Im Gegensatz zur Edit Distanz ist bezieht dieses Verfahren den Wertevorrat bei der Be wertung mit ein Als Erweiterung kann man Token Basierende hnlichkeitsma e sehen Ein Beispiel sei das Atomic String Verfahren nach ME96 Dieses Verfahren vergleicht atomare Teilzei chenketten auf Gleichheit und ist damit in der Lage Hans Muster und Muster Hans als identisch zu erkennen Eine Kombination mit einem zeichenbasierenden hnlichkeitsma w re denkbar siehe dazu auch Abschnitt 4 7 4 2 3 2 Tupel Ebene Auf der Tupel Ebene wird versucht Duplikate zu erkennen Wie bereits gezeigt k nnen mit entsprechendem hnlichkeitsma auf Attribut Ebene mit diesen Verfahren auch Du plikate in Attributwertmengen erkannt werden also folglich auch wertabh ngige Fehler Die einfachste Vergleichsoperation ist der boolsche Vergleich Dabei wird ein als Schl s sel fungierendes Attribut d
97. k nnen Duplikate enthalten die durch Abweichun gen von folgenden Attributen unterschieden werden k nnen e Titel e EMail e Homepage Es bleibt festzuhalten dass wir Duplikatbereiniger auf Attribut und Tupel Ebene ben tigen die auch in der Lage sind Tippfehler und andere geringe Abweichungen zu erkennen hnlichkeitsma e m ssen mit Zeichenketten umgehen k nnen die sich aus mehreren W rtern zusammensetzen Wir ben tigen Formatbereiniger die speziell f r ISBN Formatierung und das Einhalten des Autoren Formats optimiert sind Und es wird ein Werkzeug gebraucht mit dem wir Nullwerte auffinden k nnen Bei der Korrektur der gefundenen Fehler auf der Tupel Ebene ist darauf zu achten dass Verweise auf die Tabelle Schrift korrigiert werden sollte in dieser ein Schriftst ck gel scht worden sein Ebenso sind alle Tabellen mit Foreign Keys zu behandeln wie zum Beispiel Tabelle Abschlussarbeit zu Mitarbeiter Kapitel 3 Ausgewahlte Verfahren In diesem Kapitel werden aus der Literatur ausgewahlte Verfahren im Detail besprochen die in dieser Arbeit zur Anwendung kommen werden Dabei handelt es sich um Ver fahren zum Erzeugen eines hnlichkeitsma es sowie auch eines Ahnlichkeitsfaktors f r Zeichenketten und dem Erkennen von Tupel Duplikaten 3 1 berblick Wir haben in Bezug auf Abschnitt 2 2 drei Probleme zu l sen Zum Einen m ssen wir hnlichkeiten zwischen Attributwerten bestimmen k nnen Dann m ssen wir ein
98. k wird die in der Konfiguration abgelegte Prozess liste abgearbeitet Dabei werden der Reihe nach die eingetragenen Werkzeuge gem der Konfiguration voreingestellt und ausgef hrt Der aktuelle Abarbeitungszustand wird im Prozesszustand festgehalten und kann im Falle einer Unterbrechung zusammen mit der Konfiguration gespeichert werden Hierzu sei erw hnt dass Konfiguration und Pro zesszustand seperat gespeichert werden k nnen Es ist jedoch nicht empfehlenswert eine unpassende Konfiguration zu einem Preozesszustand zu laden Der Prozessblock startet den Ausf hrungsblock des aktiven Werkzeuges W hrend der Abarbeitung eines Werkzeuges befindet man sich folglich im Werkzeug Gem den Vor gaben aus Abschnitt 1 2 ist eine Benutzerinteraktion ein Sonderfall Wir betrachten dies also als eine Exception im Werkzeug Das hei t Beantragt das Werkzeug eine Benut zerinteraktion befinden wir uns immer noch im Ausf hrungsblock des Werkzeugs und der weitere Prozessablauf wird angehalten Dies sei anhand folgenden Beispiels erl utert Ein Werkzeug zur Attributwertbereinigung ist vor einer Duplikatbereinigung angesetzt in der Prozessliste Es tritt der Fall ein dass ein Attributwert nicht genau zugeordnet werden kann An dieser Stelle h lt die Ausf hrung und fragt den Benutzer W rde die Ausf hrung mit der Interaktion warten bis die Prozessliste abgeschlossen ist w rde bei der anstehenden Duplikatbereinigung das Tupel bei dem zuvo
99. konfiguration den gew nschten Eintrag an und bet tigen Sie die Schaltfl che Um manuell eine Tabelle hinzuzuf gen geben Sie den gew nschten Tabellennamen in das Feld mit der Beschriftung Manueller Eintrag ein und bet tigen Sie die Hinzuf gen Schaltfl che Beachten Sie dass vor dem Hinzuf gen gepr ft wird ob die Tabelle f r die Anwendung verf gbar ist Mit der Schaltfl che Speichern werden Ihre nderungen in die Konfiguration bernom men Mit der Schaltfl che Speichern und weiter gelangen Sie zur Attributkonfiguration 5 2 3 60 KAPITEL 5 BENUTZERHANDBUCH Mit der Schaltfl che Abbrechen werden Ihre nderungen ignoriert und das Fenster geschlossen 5 2 3 Attributkonfiguration In diesem Dialog legen Sie f r die Attribute der gew hlten Tabellen den Domaintyp fest Standardm ig wird der Datentyp des Attributes voreingetragen 2 Attributkonfiguration Tabellen Attribute PLPERSON a PLSCHRIFT Typ des Attributes wahlen VARCHAR e r Abbrechen Speichern und weiter Abbildung 5 7 Attributkonfiguration In der linken Liste k nnen Sie eine Tabelle ausw hlen im rechten Panel werden Ihnen anschlie end die verf gbaren Attribute angezeigt Klicken Sie auf ein Attribut um den zugewiesenen Daten oder Domaintyp zu ndern Die Typen k nnen Sie aus der Combo Box ausw hlen Beachten Sie dass Sie nach ndern des Typs die nderung mit der Schaltfl ch
100. lasse stellt die Implementation des Tupel Duplikatbereinigers aus Abschnitt 4 4 1 1 dar Der Name und der ConfigShort Iext werden gebildet wie schon unter 7 4 1 F r get SimNames erstellen wir hier ein String Array in dessen Feldern wir die verf gbaren Dom ntypen eintragen die dieses Werkzeug zus tzlich zu den Standarddatentypen ver arbeiten kann Ebenso erstellen wir ein SimTypes Array f r getSimTypes In dessen Feldern tragen wir in gleicher Reihenfolge alle den Dom ntypen entsprechenden Daten typen ein Hier geben wir den Dom ntyp ISBN an und weisen diesem den Datentyp NUMBER als quivalent zu Die editConfig Methode erzeugt wieder die Oberfl che f r die Werkzeugeinstellung Hier weisen wir dem Werkzeug die aus 4 4 1 1 verlangten Parameter zu und behandeln referenzierte Tabellen Mit der runTool Methode werden nun die ben tigten Prozeduren Funktionen und tempor re Tabellen auf die Datenbank bertragen Anschlie end wird f r jede Tabelle 7 5 IMPLEMENTATION VON VERFAHREN 89 der Werkzeugeinstellung deren Liste der Attributeigenschaften generiert und die Prozedu ren angesto en bis alle Tabellen abgearbeitet wurden Dabei werden eventuell verwaiste Schl ssel korrigiert werden m ssen Dazu wird in den Werkzeugeinstellungen festgehalten ob es zu der Tabelle Verweise gibt Tritt w hrenddessen das Unterbrechungssignal auf so wird nach der Ausf hrung der letzten aktiven Prozedur
101. leichen Ziffern unter Umst nden trotz starker Un hnlichkeit mit einem Faktor 1 erkannt werden w rden F r diese Konzeption schlagen wir daher das Entwickeln eines dynamischen Vorgehens vor Wir gehen von zwei m glichen Fehlerf llen aus Zahlendreher und vergessene Ziffer Die R ckgabe ist aus der Menge 0 0 7 1 Die Wahl des mittleren Elements ist dabei willk rlich und sollte knapp oberhalb der Schranke f r hohe hnlichkeit liegen Ziel ist es eine Ziffernfolge als ungleich identisch oder eventuell hnlich zu bewerten Zun chst vergleichen wir die Zahlen mit dem boolschen Vergleich Ist der ermittelte Fak tor 0 k nnen wir den Betrag der Differenzbilden Ist dieser unter 9 mit Ausnahme der 0 kann kein Zahlendreher vorliegen zudem kann Zahl A nicht Teilst ck von Zahl B sein 101 10 9 54 45 9 1 10 9 5 55 50 Beispiel 4 2 Beispiel f r Differenzbetr ge Trifft dies nicht zu vergleichen wir die Anzahl der Ziffern Ist diese ungleich so ist es recht unwahrscheinlich dass ein Zahlendreher vorliegt Andernfalls k nnen wir mit einem Sliding Window der Gr e 2 beide Zahlen parallel durchlaufen und auf Zahlendreher pr fen Ist der Unterschied zwischen der Anzahl der Stellen der Gr e 1 k nnen wir pr fen ob Zahl A Teil von Zahl B ist In diesem Fall ist es wahrscheinlich dass eine Ziffer bei der Eingabe bersehen wurde Erkennt der boolsche Vergleich die Identit t geben wir 1 zu
102. lic static boolean isConnected Gibt den Verbindungszustand zur ck public static FrameworkCFG getF WConfig Gibt die Instanz der Klasse FrameworkCFG zur ck public static void fillAttrList ITableList tls TableList Sucht zu einer Tabelle deren Attribute und erstellt daraus eine Liste public static void saveConfig String saveName public static void saveState String saveName public static void loadConfig String loadName public static void loadState String loadName Speichert bzw ladt die Konfiguration oder Prozesszustand Siehe hierzu das Interface IXMLWrapper Klasse Framework CFG Die Klasse besteht aus einer Vielzahl an Getter und Setter Methoden Hier sei eine Auswahl an nicht trivialen Methoden gegeben public void addProcess String toolID F gt einen neuen Prozess zur Prozessliste mit Verweis auf die Werkzeug Id toolID public void removeProcess int key Entfernt den Prozess mit der Id key public void setToolOptions int przKey String options Setzt die Werkzeugeinstellungen f r eine Prozess Id public String getToolOptions int przKey Findet zu einer Prozess Id die zugeh rigen Werkzeugeinstellungen public String getToolID int key Findet zu einer Prozess Id die zugeh rige Werkzeug Id A 1 PAKET CONFIGURATION 95 public Object getProcessArray Gibt die Prozessliste als Object Array zur ck public void clearCurState Setzt den Prozesszustand zurtick Klasse IProcessStat
103. lle Tabellen gefunden wer den die einen Foreign Key auf die gew hlte Tabelle haben und diese iterativ abgearbeitet werden Das Herausfinden der Tabellen und das Vorbereiten des Werkzeuges ist Teil der Werkzeugeinstellung und beeinflusst den Ausf hrungsblock des Werkzeuges Dieser ver anlasst das wiederholte Ausf hren der Bl cke der Verarbeitungsebene Nach Durchlaufen der Duplikaterkennung wird Merging vgl 4 5 auf die erzeugte tempo r re Duplikattabelle angewendet Zuletzt werden die tempor ren Tabellen entfernt Wird die aktuelle Tabelle referenziert so muss bei der Werkzeugeinstellung dieses Be r cksichtigt werden Die Schl ssel der verweisenden Tabellen m ssen angepasst werden Verweist die aktuelle Tabelle auf Tupel einer anderen Tabelle so muss zun chst diese andere Tabelle bereinigt werden Es gelten die Zus tze zum Ablauplan aus 2 2 4 4 1 2 Tupel Entferner Parameter Tabelle Suchbedingung Ausgabe keine Tempor re Tabellen keine Interaktion R ckfrage mit Liste zu l schender Tupel Dieses Werkzeug ist ein wertunabh ngiges Werkzeug dass es erm glicht Tupel anhand einer Suchbedingung zu l schen Aus Sicherheitsgr nden werden die gefundenen Tupel dem Benutzer zur Interaktion vorgestellt damit dieser notfalls abbrechen kann Feh lererkennung ist hierbei die Filterung nach der Suchbedingung und der R ckfrage vor dem L schen Die Fehlerkorrektur ist die anschlie ende Entfernung der Tupel Wird
104. ls Beispiel nehmen wir die Tabellen Lebensmittel und yp an Verweise nun der Eintrag Brot und Mehl auf zwei Eintr ge Roggen so w rde nach dem Ansatz des Folgens der Verweise nur noch ein Eintrag Roggen brig bleiben auf den beide Lebensmittel verweisen ndert sich nun der Mehltyp auf Weizen darf der nun referenzierte Eintrag Roggen nicht einfach ge ndert werden Beim Objekt soll es sich hier nun um eine Kombination aus Tupel und Beziehung han deln Das Verbindungselement stellt dabei die Beziehung zwischen den Tupeln dar Der referenzierte Tupel wird als Beziehungsattribut an den verweisenden Tupel angeh ngt Die Beziehung zwischen den Tupeln wird damit zum k nstlichen Datentyp und der re ferenzierte Tupel der Attributwert Diesem neuem Attribut kann ein hnlichkeitsma zugeordnet werden Dadurch wird sowohl der verweisende als auch der referenzierte Tu pel als Einheit bewertet Wird nun ein Objekt als Duplikat erkannt und behoben bleibt die urspr ngliche Datenredundanz zu referenzierten Tupeln erhalten 8 2 Erweiterung der Werkzeuge Die hier dargestellten Werkzeuge entsprechen nur einem kleinen Teil des M glichen So kann als Attributwertvergleich zur wertabh ngigen Feglerkorrektur auch das Verfahren von MBO06 eingesetzt werden Zudem k nnen weitere Attributwerkzeuge f r neue Do maintypen erstellt werden So haben wir bisher nur relativ generische F ll
105. lt reasoning default reacning 1295 default reasoning defaut reaoning 1296 default reasoning defaut reaoning 1297 default reasoning defaut reaoning 1295 default reasoning default reaoning 1299 default reasoning default reacning 1300 default reasoning default reacning 1301 default reasoning defaut reaoning Abbildung 6 4 Zuviele hnliche Werte Kapitel 7 Implementierung Hier wird die Implementierung der unter Kapitel 4 vorgestellten Werkzeugsuite erlautert Zu den Methoden der wichtigsten Klassen finden sich in der Schnittstellen API im Anhang A nahere Erlauterungen 7 1 Umgebung Die Anwendung ist f r die Java Versin 1 5 0_17 implementiert und nutzt den Oracle JDBC Treiber in der Version 10 2 0 4 Zur Verbindung mit der Datenbank m ssen die externen Bibliotheken des OCT Instant Clients in der Version 10 2 0 4 der Anwendung zug nglich gemacht werden Dazu m ssen diese sich im Klassenpfad der Anwendung befinden Zum Ablegen von Konfigurationsdaten in eine externe Datenstruktur kommt die JDOM Bibliothek in der Version 1 1 zum Einsatz Diese erlaubt das Anlegen und Einlesen von Dateien im XML Format 7 2 Entwurf und Aufbau Der Entwurf der Java Anwendung folgt den Leitlinien aus dem Kapitel 4 Die Aufteilung der Klassen soll soweit es sinnvoll angewendet werden kann dem MVC Muster folgen Dieser Abschnitt soll einen berblick ber die Realisierung der Anwendungsstruktur als Java Anwendung geben 13 14
106. m Vektorindex wird die Nummer erh ht 90 KAPITEL 7 IMPLEMENTIERUNG Anschlie end wird die zweite Zeichenkette durchlaufen und f r jeden Vektorindex der Wert um einen reduziert Solange der Wert des Vektors am Vektorindex nicht unter 0 f llt wird ein Z hler um einen erh ht Dieser Z hler stellt den Betrag der Schnittmen gen dar Dies wird dadurch klar dass zu jedem Vektorindex dessen Auftrittsnummer reduziert wird ein passendes Zeichen in der zweiten Zeichenkette gefunden wurde Ger t die Auftrittsnummer hingegen unter 0 so ist das Zeichen in der zweiten Zeichenkette zus tzlich enthalten und wird nicht mit zum Z hler gerechnet hnlich wenn nicht alle Auftrittsnummern 0 erreichen hat der erste Zeichenkette mehr Zeichen Im Folgenden sei der Vektor als Auftrittsnummer bezeichnet Der Z hler zum Ermitteln des Betrags der Schnittmenge sei Schnitt Schnitt 0 F r alle Zeichen c aus Eingabe A Erh he Auftrittsnummer c um 1 F r alle Zeichen c aus Eingabe B Verringere Auftrittsnummer c um 1 Wenn Auftrittsnummer c gt 0 Schnitt Schnitt 1 R ckgabe Schnitt Maximum L nge A L nge B Auflistung 7 4 Implementierung von Field Similarty Grams mit g 2 l sst sich hnlich wie Field Similarity implementieren Der Unterschied ist dass je zwei Zeichen einen Vektorindex definieren Auf Start und Endzeichen k nnen wir verzichten wenn wir das erste und das letzte Zeichen separat in de
107. m glichen und diese automatisch zu korrigieren oder Korrektur vorschl ge zur Wahl zu stellen bei denen die Datensatzinformationen bereits bestm glich f r den Benutzer aufgearbeitet wurden Insbesondere wird dieses Werkzeugset zur Bereinigung der vom Fachgebiet Datenban ken und Informationssysteme gef hrten bibliographischen Datenbank entwickelt Es sind daher schwerpunktm ig Funktionen f r das Bereinigen dieser bibliographischen Daten sowie notwendiger Datentypen und Eingabeformate zu entwickeln Die Werkzeuge sind speziell f r ein Oracle Datenbank Management System ab Version 10 zu entwickeln Das erlaubt die Ausnutzung von leistungsf higen datenbankbasierten Programmen 1 3 Aufbau der Arbeit Diese Arbeit setzt sich zusammen aus der Einf hrung in die Grundlagen der Datenbe reinigung der Vorstellung von Verfahren sowie der Konzeption und der Implementierung der zu entwickelnden Werkzeuge 1 3 AUFBAU DER ARBEIT 3 Kapitel 2 besch ftigt sich mit den Grundlagen der Datenbereinigung f hrt die in der Arbeit verwendeten Begriffe ein und gibt eine bersicht ber die speziellen Gegebenheiten der Testdatenbank Das Kapitel 3 stellt die in dieser Arbeit aus der Literatur bernommenen Verfahren vor und erl utert deren Funktionsweise Kapitel 4 besch ftigt sich mit der Konzeption der Werkzeuge dazu wird auf die Entwick lungsumgebung eingegangen die Erweiterungen an den zuvor vorgestellten Verfahren werden besch
108. mmer ber Merging gestartet Das Mer ging startet das Referenzwertverfahren von der Anwendungsebene Die Verfahren agieren also unabh ngig voneinander Wird eine Interaktion ben tigt so wird diese durch das Merging behandelt Die Kontrolle ber die Cluster bleibt auf der Anwendungsseite Das Referenzwertverfahren kann folglich mit beliebigen Clusterzusammensetzungen wieder holt aufgerufen werden ohne dass sich der Prozesszustand ndert Dies erm glicht es eine Clusterkorrektur anzubieten Da sich durch das Referenzwertverfahren der Zustand nicht ge ndert hat kann dieses erneut aufgerufen werden 7 9 5 Modifizierte Field Similarity Das modifizierte Field Similarity Verfahren ist mit vier PL SQL Funktionen implemen tiert Dabei setzen diese sich zusammen aus dem Verfahren zum Boolschen Vergleich 7 5 IMPLEMENTATION VON VERFAHREN 89 das Field Similarity Verfahren dem Q Grams g 2 Verfahren und der Funktion die den Ablauf gem Abschnitt 4 7 4 realisiert Zun chst m ssen die Wortmengen erstellt werden Dies l sst sich mit den INSTR und SUBSTR Funktionen l sen Wir erhalten zwei PL SQL Tabellen die die Wortmengen darstellen Ebenso k nnen wir die Anzahl der W rter z hlen Gesamtzahl 0 1 0 fertig falsch Irennzeichen Solange nicht fertig ES EM Finde das iten Auftreten des Trennzeichens in Eingabe A Ist kein i tes Trennzeichen vorhanden dann fertig wahr Wenn nicht fertig Bestimme n chstes Auftreten d
109. n Diese Schaltfl chen finden sich auch im Men Datei Wenn Sie einen alten Prozesszustand laden wollen achten Sie darauf dass Sie zuvor die passende Konfiguration geladen oder erstellt haben da beim Laden oder ndern einer Konfiguration der Prozesszustand zur ckgesetzt wird Es ist nicht zu empfehlen einen Prozesszustand zur falschen Konfiguration fortzusetzen Wenn die Konfiguration ausreichend erstellt wurde wird die Schaltfl che Prozess starten aktiv Bitte beachten Sie dass erst nach bet tigen der Schaltfl che gepr ft wird ob alle Werkzeugeinstellungen vollst ndig sind Das Bet tigen dieser Schaltfl che setzt den Prozesszustand zur ck und beginnt die Abarbeitung der Prozessliste Um einen Prozesszustand fortzusetzen klicken Sie auf die Schaltfl che Prozess fortset zen Diese wird nur aktiv wenn ein angehaltener Prozesszustand geladen ist W hrend ein Prozess l uft kann die Konfiguration nicht ver ndert werden Um einen Prozess anzuhalten klicken Sie auf die Schaltfl che Prozess anhalten Beachten Sie dass es etwas dauern kann bis das Werkzeug reagiert Die Schaltfl chen dieser Oberfl che finden Sie auch im Men Prozess 5 4 Interaktion Wenn ein Werkzeug nicht in der Lage ist eine Entscheidung automatisch zu treffen regt es eine Benutzerinteraktion an Es ffnet sich ein Dialog dessen Optionen vom Werkzeug abh ngig sind Bei den meisten Werkzeugen wird dies aber der Dialo
110. n Vektor eintragen Schnitt 0 F r erstes Zeichen c aus A Setze Auftrittsnummer c auf 1 F r letztes Zeichen c aus A Setze Auftrittsnummer c auf 1 F r alle 2 Zeichen ab aus Eingabe A Erh he Auftrittsnummer ab um 1 F r alle 2 Zeichen ab aus Eingabe B Verringere Auftrittsnummerlab um 1 Wenn Auftrittsnummer ab gt 0 Schnitt Schnitt 1 F r erstes Zeichen c aus B Verringere Auftrittsnummer c um 1 Wenn Auftrittsnummer c gt 0 Schnitt Schnitt 1 F r letztes Zeichen c aus B Verringere Auftrittsnummer c um 1 Wenn Auftrittsnummer c gt 0 Schnitt Schnitt 1 LenAB Anzahl der erzeugten Indexe R ckgabe Schnitt LenAB Auflistung 7 5 Implementierung von Q Grams q 2 Kapitel 8 Ausblick 8 1 Erweiterung von Tupeln auf Objekte Hier soll das Objekt als neuer Datengegenstand n her erl utert werden Bei der normalen Duplikaterkennung folgen wir gem 2 2 rekursiv den Verweisen und korrigieren die entstandenen verwaisten Schl ssel nach erfolgter Duplikatbereinigung in den referenzierten Tabellen Der Effekt ist dass fremde Tupel die auf stark hnliche Tupel mit Zusatzinformationen verweisen nach Ausf hrung der Bereinigung nur noch auf die gleichen Zusatzinformation zeigen N mlich die die durch das Merging aus den stark hnlichen Zusatzinformationen hervorgegangen sind Im schlechtesten Falle kann das Merging sogar zu Fehlinformationen im Verbund mit dem verweisenden Datensatz f hren A
111. n ebenso als ung ltige Nummer abgelegt und sp ter zur Benutzerinteraktion angezeigt 4 4 2 5 Autoren Formatbereiniger Dieses Werkzeug ist Teil der aus Abschnitt 2 5 geforderten Attributwerkzeugen Parameter Tabelle Attribut Format Ausgabe keine Tempor re Tabellen keine 4 5 MERGINGVERFAHREN 45 Interaktion Benutzerkorrektur f r unklare F lle Ziel des Werkzeuges ist es falsch formatierte Autoren Eintr ge zu korrigieren Dazu wer den die Attributwerte mit dem Format verglichen Das Format kann dabei zum Beispiel im Form eines regul ren Ausdrucks vorliegen Kann der Attributwert nicht mit dem For mat vereinbart werden so wird versucht den Attributwert auf das Format abzu ndern Das kann erfolgen indem im Attributwert nach dem im Format festgelegten Trennzeichen gesucht wird Kann ein Irennzeichen zugeordnet werden so kann davon die Position des Autornamens und von Leerzeichen bestimmt werden Es wird also eine Art r ckw rtiges Parsing verwendet um in dem Attributwert Elemente des Formats zu bestimmen Sobald diese Elemente bestimmt sind k nnen diese neu formatiert werden So k nnen zum Bei spiel fehlende Leerzeichen vor Trennzeichen eingef gt werden oder ein Vertauschen von Vor und Nachnamen aufgrund eines fehlenden Kommas erkannt werden 4 4 2 6 Nullwert Finder Dieses Werkzeug ist Teil der aus Abschnitt 2 5 geforderten Attributwerkzeugen Parameter Tabelle Attribute Ausgabe keine Tempor
112. nd Prozess 4 3 ABLAUFBESCHREIBUNG 37 Initialisierung Zustandswechsel Konfiguration Werkzeugeinstellungen ndern ustandswechsel Prozesszustand aktualisieren 7 Frozesszustang Hrozesezusiand laden ansioten D Ausf hrung L Zustandsr ckmeldung Konfiguration laden Prozesszustand ablegen einlesen Abbildung 4 4 Anwendung Funktionsbl cke Im Initialisierungsblock wird die notwendige Datenverbindung hergestellt Darunter f llt die Authentifizierung an der Datenbank und eventuelle Tests der Verbindung Der Konfigurationsblock steht f r die Einstellung des Frameworks und der Werkzeuge Dabei gelten die Frameworkeinstellungen f r alle Werkzeuge Eine Frameworkeinstellung kann zum Beispiel die gew hlte Tabelle sein Eine Werkzeugeinstellung ist beispielsweise die Erkennungsgenauigkeit Die abgelegte Konfiguration umfasst beide Einstellungen wie in 4 2 definiert Teil des Konfigurationsblocks ist auch die Erstellung der Prozessliste Die Prozessliste gibt vor welche Werkzeuge der Reihenfolge nach ausgef hrt werden sollen Diese muss vor dem festlegen der Werkzeugeinstellungen gef llt werden da die Zuordnung der Einstellung zum eingereiten Werkzeug passen muss Vor dem Wechsel in den Prozessblock sollen dem Benutzer folgende Aktionen verf gbar sein e Laden oder Speichern der Konfiguraten e Laden oder Speichern des Prozesszustandes Aktuelle Konfiguration bearbeiten Kon
113. nd Linux x86 5 1 3 Ausf hrung Um die Anwendung zu starten f hren Sie ber eine GUI zum Beispiel den Windows Explorer oder den Konqueror die DBCleaning jar aus Auf der Kommandozeile k nnen Sie das Programm starten mit java jar DBCleaning jar Auflistung 5 1 Aufruf auf Kommandozeile 5 2 Hauptoberfl che Konfiguration Nach erfolgreichem Start sehen Sie die Hauptoberfl che auf der Registerkarte Konfigu ration E DI Cleaning B lsik Datel Konigi Pi Konfiguration Prozess Konfigpar ation Lader i Kondigur ation speichern Neue baten ar Gr sign Dalenbankzugang Status Programm beenden Abbildung 5 1 Hauptoberfl che Konfiguration Auf dieser Seite k nnen Sie die Konfiguration verwalten 5 2 HAUPTOBERFLACHE KONFIGURATION ot Sie k nnen zuvor erstellte Konfigurationen laden indem Sie auf die Schaltfl che Konfigu ration laden klicken Wollen Sie stattdessen Ihr Konfiguration f r eine sp tere Wartung sichern so bet tigen Sie die Schaltfl che Konfiguration speichern Beide Schaltfl chen sind auch im Men Datei vorhanden 2 Konfiguration laden Suchen in CBA Woski BA Wolski via Ei ae Beispiel _prozess xml Beispiel xml Dateiname Beispielxml Dateityp AML ffnen Abbrechen Abbildung 5 2 Konfiguration laden Den Zustand der aktuellen Konfiguration k nnen Sie im Hinweisfeld ablesen Status Datenhankzugang konfig
114. ndung gerade befindet Mit dieser Information kann die Interaktionsoberfl che von dem Prozesszustand Gebrauch machen public void runTool int processID Standard View parent F hrt ein Werkzeug aus Der Parameter processID gibt an in welchem Prozess sich die Anwendung gerade befindet Damit kann vom Prozesszustand Gebrauch gemacht werden Der Parameter parent zeigt auf die Klasse deren parent Action Methode auf Interaktionsanfragen reagiert Klasse Register Tools public static void register Wird von der Klasse Controller aus dem Paket Configuration aufgerufen Die Methode ist dazu gedacht dass Werkzeuge an der Konfiguration angemeldet werden Siehe auch Controller addTool ITool tool 100 ANHANG A API Abbildungsverzeichnis 2 1 Nachf hrende Behebung von duplizierten Tupeln mit Verweisen 8 2 2 Entity Relationship Model 17 3 1 PC Filter bersicht 2 000000000000 000002 24 3 2 Ahnlichkeitsfaktoren am Dreieck 2 2 a aa 25 3 3 Lower und Upper Bound am Zahlenstrahl 2 2 2 2222 2222 26 3 4 PCG Beispiel e 28 4 1 Architekturebenen 2 2 2 Con 32 4 2 MVC Abhangigkeitsbeispiel 222 2 Co a 33 4 3 Funktionsblocke von Werkzeugen 30 4 4 Anwendung Funktionsbl cke 0 0 20 0 000000 37 4 5 PC Filter Funktionsbl cke e 41 4 6 Vergleichsverfahren Ablaufdiagramm 2 22 nn nn 47 5 1 Hauptoberfl che Konfiguration 0 0000 56 5 2 Konfiguration laden o oo a a ov
115. nen des Frameworks sind die Eigenschaften der Werkzeuge darzustellen Ebenso beschreibt dieses Segment wie die Prozeduren der Werkzeuge auszuf hren sind Es er gibt sich also eine Abh ngigkeit mit der Verarbeitungsebene Abbildung 4 1 zeigt den Aufbau dieser Ebenen Benutzerebene Verarbeitungsebene Bedienoberfl che Werkzeuge Werkzeugeigenschaften Controller aneinker r ckmelden Abbildung 4 1 Architekturebenen In der dargestellten Verarbeitungsebene bildet das Datenbanksystem DBS den Rahmen Dies hat zwei Gr nde Zum Einen haben wir den Datenbestand als Teil der Verarbeitungsebene definiert Die Werkzeuge operieren dabei auf einer Teilmenge dieses Datenbestandes Der Datenbestand selber ist nur eine Teilmenge des DBS Zum Anderen erlaubt uns das Oracle DBS die Werkzeugprozeduren direkt auf der Da tenbank zu Programmieren zum Beispiel unter Ausnutzung von PL SQL Generell ge schehen alle Zugriffe auf den Datenbestand letztendlich nur ber das DBS Damit k nnen wir eine Ansto en und R ckmelden Beziehung zwischen den beiden Ebenen anneh men Dabei besagt das Ansto en dass eine Anforderung an das Werkzeug erfolgt eine Anfrage an die Datenbank zu stellen Dies kann schon ein einfacher SQL Befehl sein Die R ckmeldung aus dem Datenbestand wird anschlie end durch das Werkzeug behandelt und der Benutzerebene zur ckgemeldet Entf llt hier der Werkzeugpart auf der Daten bank so wird dennoch die
116. neu sind So werden Tippfehler schon per Trigger geblockt Da diese Methode sehr radikal ist k nnen auch externe Skripte diese Funktionen nutzen Damit ist es m glich f r eine Eingabemaske zu den bereits eingegebenen Daten hnliche Werte aus der Datenbank anzeigen zu lassen Damit kann das Raten nach der richtigen Schreibweise vermieden werden Anhang A API A l Paket Configuration Klasse Controller public static void register Tools F hrt die Register Tools register Methode aus und erstellt die Liste der Dom ntypen public static void clearConfig Setzt die gesamte Konfiguration zur ck public static void clearToolConfig Setzt die Liste der registrierten Werkzeuge zur ck public static ITool getTool String id Gibt das Werkezug mit der Werkzeug Id zd zur ck public static void addTool ITool tool F gt ein Werkzeug der Konfiguration hinzu public static Object getToolArray Gibt die Liste der Werkzeuge als Objekt Array zur ck public static Object getSimpleQueryArray String query F hrt eine SQL Anweisung aus deren erster R ckgabewert als Objekt Array zur ckge geben wird public static String getDbUser Gibt den Benutzernamen des derzeitig angemeldeten Benutzers zur ck 93 94 ANHANG A API public static void connectDB String user String pass Stellt eine Verbindung mit der Datenbank her public static void closeDB Schlie t die Datenverbindung pub
117. ocess e Joed Zete parent ction a registerToolst resetButtons e resetProcessstatel o setStatusText saveContig OO startProcess g saveState i updatestatusText g Seit WW opfiot amp setToolOptionsr Abbildung 7 2 Klassendiagramm Hauptoberflache Die Klasse Main initialisiert die konfigurationsverwaltende Klasse Controller aus dem Paket Configuration und die Hauptoberflache aus dem Paket View Sie ist relevant als Programmeinstiegspunkt Die Klasse Controller ist die zentrale Konfigurationsverwaltung Die Klasse verwaltet die Frameworkkonfiguration das Datenbankobjekt und verf gt ber Prozeduraufrufe um die Konfiguration als externe Datei abzulegen Durch den Namen der Klasse ist bereits naheliegend dass diese Klasse das Hauptelement des Controller Parts ist Sie stellt aber 16 KAPITEL 7 IMPLEMENTIERUNG nicht den gesamten Controller dar und sollte daher im Folgenden nicht verwechselt wer den Diese Klasse ist als statische Klasse implementiert Dadurch k nnen deren Methoden von jeder Klasse ohne Instanzierung aufgerufen werden Dahingegen instanziert die Klasse die Konfiguration und Datenverbindung Die Klasse FrmMainView stellt die Hauptoberfl che dar Dialogfenster berlagern jeweils diese Hauptoberfl che Sie dient damit neuen Fenstern als Parent Klasse Die Konfiguration und der Prozesszustand haben unmittelbare Auswirkung auf deren Ober f chenverhalten Sie kommunizier
118. odlStringl getTodlStringl interactionPanel interactionPanel runTooli BS modelSetupl B runTooll CG view StandardView Abbildung 7 6 Klassendiagramm Paket Tools In der Abbildung 7 6 sind die Zusammenhange der Klassen des Paket Tools mit denen der verbundenen anderen Pakete dargestellt Aus Griinden der Ubersichtlichkeit reduzie ren wir uns auf die Klassen Klasse TupelDuplicate und Klasse AttributReplacer Diese stellen jeweils ein kompliziertes und ein einfaches Werkzeug dar Beide Klassen implementieren das Interface I Tool und werden durch die Klasse RegisterTools der Klasse Controller bergeben Es ist ersichtlich dass beide Werkzeuge einen durch das Interface ITool vererbten Aufbau haben Dies hat den Grund dass jedes Werkzeug von den aufrufenden Klassen gleich behandelt werden soll Das hei t die Kommunikation mit dem Werkzeug verl uft ber die durch das Interface vererbten Methoden Damit ist es m glich beliebige Werkzeuge zu realisieren und diese mit nur einem Eintrag in die Klasse RegisterTools dem Projekt zu Verf gung zu stellen Dazu sind folgende Methoden von besonderer Bedeutung 7 2 ENTWURF UND AUFBAU 81 Die Methode editConfig erzeugt ein JPanel dass die Oberfl che f r die Werkzeugein stellungen darstellt Die Methode run Tool beinhaltet den Ausf hrungsblock des Werkzeuges Hier werden nacheinander die einzelnen Schritte ausgef hrt und auf Unterbrechungen reagiert Die Me
119. per Bound UB und Lower Bound LB Dabei macht PC Filter davon Gebrauch dass zwei Drei ecksseiten durch die Intervallbeschr nkung maximal die Summe 2 haben k nnen und der Betrag der Subtraktion maximal 1 ist Setzt man nun die hnlichkeitsfaktoren unter Beachtung der Intervallgrenzen ein ergibt sich die Ungleichung AB BC 1 lt sAC lt 1 AB BC AB Sim A B BC Sim B C AC Sim A C Auflistung 3 2 Dreiecksungleichung nach PC Filter Die Umkehrung der Vergleichsoperationen stellt sich dadurch ein dass durch die hier ver wendete Schreibweise es zu einer komplement ren Darstellung der Terme kommt Der Grund liegt darin dass AB BC zwischen 0 und 2 schwankt Durch Abzug von 1 wird ein hnliches Verhalten wie vom urspr nglichen Betragsterm erzielt dessen maxi maler Wert 1 nicht berschreitet Die gew hlten Terme verhalten sich wie die allgemeine Dreiecksungleichung sind aber weniger streng Wir betrachten folgendes Beispiel AB 0 2 BC 0 3 0 5 lt AC lt 0 9 entgegen der allgemeinen Form 0 1 lt AC lt 0 5 26 KAPITEL 3 AUSGEWAHLTE VERFAHREN Beispiel 3 6 Beispiel f r Dreiecksungleichung nach PC Filter Es stellt sich f r unser AC ein gr erer Bereich ein Damit wird mit der Ungleichung nach PC Filter ber cksichtigt dass je unterschiedlicher die Tupel untereinander sind desto weniger ber die hnlichkeit von A zu C ausgesagt werden kann PC Filter beschreibt auf Grund der Ungleichung
120. r ck Bei der Erkennung von Zahlendreher oder vergessener Ziffer geben wir 0 7 als Wert f r eventuelle hnlichkeit zur ck Ansonsten geben wir 0 zur ck 4 7 AHNLICHKEITSVERFAHREN 49 4 7 3 Datums Vergleich Parameter zwei Attributwerte vom Datentyp Datum Vergleichseinheit Vergleichsart Dieses Ma bestimmt die hnlichkeit zwischen zwei Oracle Datumswerten Dabei ist vorzugeben auf welche kleinste Einheit Jahr Monat Tag gepr ft werden soll Je nach Konfiguration bzw Einsatzes kann dieses Ma entweder die Gleichheit von Daten feststellen oder auf Zahlendreher in den Zeitbereichen pr fen Dazu k nnen hnliche Verfahren wie beim nummerischen Vergleich verwendet werden 4 7 4 Modifizierte Field Similarity Parameter zwei Attributwerte eines als Zeichenfolge darstellbaren Datentyps Gro Kleinschreibung beachten Ziel dieser Modifikation ist es die Verfahren Field Similarty Q Grams und das Prin zip des Atomic Strings zu kombinieren Dies soll es erm glichen sowohl Zeichendreher als auch un hnliche Zeichenfolgen mit gleichem Zeichenvorrat unterscheiden zu k nnen Ausserdem soll es uns erm glichen kurze S tze oder Namen Vornamen Kombinationen vergleichen zu k nnen Atomic Strings wurde bereits in Abschnitt 2 3 1 erw hnt Hier wird dessen Grundlage verwendet um ein eigenes Verfahren zu schaffen Der Ablauf von Q Grams wurde in Abschnitt 3 2 erl utert Field Similarity ist zu definieren wie in Abschni
121. r die Ausnahme eingetreten ist eventuell nicht als Duplikat erkannt werden Dadurch m sste die Erkennung ein zweites mal erfolgen Beispiel 4 1 Benutzerinteraktion im Ausf hrungsblock Die Art der Benutzerinteraktion die ein Werkzeug verlangt ist dabei von dessen Ei genschaften abh ngig So kann zum Beispiel die Vergabe von Referenzwerten bereits in den Werkzeugeinstellung erfolgen oder aber bei der Ausnahme vonn ten sein So w re bei einem Duplikatwerkzeug zum Beispiel zwischen dem Fehlererkennungs und dem Fehlerkorrekturblocks die interaktive Korrektur von Clusterzusammensetzungen Clus terkorrektur n tig 4 4 WERKZEUGE 39 4 4 Werkzeuge Es wurde bisher weitestgehend tiber das den Werkzeugen zugrunde liegende Framework gesprochen Dieses stellt dem Benutzer Konfigurationsm glichkeiten zur Verf gung und verwaltet die Werkzeuge Hier sollen nun die zur Verf gung stehenden Werkzeuge bespro chen werden Zun chst wurde bereits erw hnt dass ein Werkzeug Verfahren verwendet um ein h heres Ziel zu erreichen Das hei t mit einem Werkzeug geben wir dem Benutzer eine Black Box der eine Anzahl von Einstellungen bergeben wird und anschlie end gem seiner Bestimmung auf dem Datenbestand arbeitet Ein Werkzeug besch ftigt sich dabei immer mit genau einer Aufgabe Diese ist eine klar definierte Bereinigung durchzuf h ren Das bedeutet dass f r jede Art einer Bereinigung ein Werkzeug erforderlich ist Die
122. r in Auflistung 2 1 dargestellte Plan zeigt ein einfaches Vorgehen zur Erkennung von Duplikaten Dabei wird jeder Wert mit jedem weiteren Wert verglichen Stellt sich dabei eine hohe hnlichkeit ein so wird das Paar korrigiert Nach dem Korrigieren von sp ter behandelten Paaren k nnen hohe hnlichkeiten mit fr heren Werten erzeugt worden sein Daher wird der gesamte Vorgang solange wiederholt bis nur noch identische oder un hnliche Paarungen brig sind Tupel Ebene Um Tupel miteinander zu vergleichen m ssen wir die einzelnen Attribute der Tupel miteinander vergleichen und daraus einen hnlichkeitsfaktor f r das Tupelpaar ableiten Die Bereinigung auf Tupel Ebene setzt sich also zusammen aus einem Vergleich auf der Attribut Ebene einem daraus folgernden Vergleich auf der Tupel Ebene und der Fehlerkorrektur Im Falle der Fehlererkennung ergibt sich nun der Bedarf eines hnlich keitsma es das Tupel bewertet Dieses muss auf dem Vergleich auf der Attribut Ebene aufbauen Ein solches Ma kann zum Beispiel die Aufsummierung der hnlichkeitsfakto ren der Attribute sein Der hnlichkeitsfaktor w re in diesem Beispiel das Ergebnis dieser Summierung Bei der Fehlerkorrektur m ssen nun unterschiedliche Attributwerte der Du plikate zu einem Tupel kombiniert werden und im Gegensatz zur Attribut Ebene das duplizierte Tupel entfernt werden Diese Art der Fehlerkorrektur hei e in dieser Arbeit Merging was in Abschnitt 2 4 2 vorgestellt wi
123. ration sicher dass f r das Attribut SCHLAGWORT VARCHAR2 gew hlt ist Anschlie end stellen wir das Werkzeug ein Als Genauigkeit w hlen wir f r den ersten Versuch 0 75 Als Attribut w hlen wir nun SCHLAG WORT aus Werkzeugeinstellung E Prozessliste Tabellen 1 A Attribut Duplikatbereiniger WVOLSKIL SCHLAGWORT SCHLAGWORT WOLSKI SCHLAGWORT Verf gbare Attribute PERSON PRIORITAET SCHLAGWORT Sortieren nach SCHLAGWORT Erweiterte Optionen Partitionen 6 Randbereich 4 Genauigkeit 0 75 Referenzwerte bernehmen Abbrechen Fertig Abbildung 6 2 Attribut Duplikatbereiniger einstellen Mit diesen Einstellungen k nnen wir nun einen Prozess starten In dem Prozesslog k nnen wir verfolgen wie die Bl cke von PC Filter durchlaufen werden 6 2 LAUFZEITTEST 1 amp DB Cleaning Iof x Datei Prozess Konfiguration Prozess Prozess Log 2009 04 01 07 11 56 111 Attribut Duplikatbereiniger startet 2009 04 01 07 11 56 111 Duplkiaterkennung Phase 1 Prozess anhalten Status Werkzeuge eingestellt 5 5 an DB angemeldet Programm beenden Abbildung 6 3 Laufender Prozess 6 2 Laufzeittest Die Schlagworttabelle hat 29922 Eintr ge Erprobt wurden die Verfahren auf einer Tabelle mit 313 Eintr gen Zus tzlich kommen in der Schlagworttabelle Attributwerte vor die aus mehre
124. rd Fehlererkennung fertig falsch Solange noch nicht fertig fertig wahr F r jedes Paar der Tupelmenge Fur jedes Attribut W hle hnlichkeitsma Erzeuge hnlichkeitsfaktor f r das erhaltene Attributwertpaar Verrechne diesen Faktor mit dem hnlichkeitsfaktor des Tupelpaares Wenn hnlichkeitsfaktor des Tupelpaares hoher hnlichkeit entspricht Fehlerkorrektur Wende Merging an Entferne eines der Tupel eventuell Bevorzugung vorgegeben fertig falsch Auflistung 2 2 Bereinigung auf Tupel Ebene F r Tabellen mit Verweisen auf Tupel fremder Tabellen ist es n tig zun chst dem Ver weis zu folgen und die fremde Tabelle zu bereinigen bevor die referenzierende Tabelle 2 3 VERFAHREN ZUR FEHLERERKENNUNG 11 bereinigt wird Dies wird deutlich wenn wir zu einer Tabelle B cher die Tabelle Aus lecher referenzieren Wir verwenden wieder das Beispiel aus Abbildung 2 1 Seien nun in der Tabelle B cher die B cher A und B Duplikate Buch A verweist auf Ausleiher C und B auf Ausleiher D die beide erneut ein Duplikat seien Nehmen wir an dass dieser Verweis als untrennbare Zusatzinformation zu verstehen ist W rde zun chst B cher bereinigt w rde das Duplikat von A und B nicht auffallen da beide unterschiedliche Zusatzinformationen beinhalten Anschlie end w rde nur das Duplikat von C und D er kannt Beginnt man hingegen mit der referenzierten Tabelle Ausleiher
125. ren W rtern bestehen Folgende Zeiten wurden f r die Ausf hrung mit PC Filter gemessen e Alle sechs Prozeduren auf Testtabelle nur mit Field Similarity 1 5 Sekunden e Testtabelle mit der modifizierten hnlichkeitsfunktion 5 Sekunden Schlagworttabelle erste Prozedur 2 Sekunden Schlagworttabelle zweite Prozedur 285 Sekunden Schlagworttabelle dritte Prozedur 0 5 Sekunden e Schlagworttabelle vierte Prozedur 0 2 Sekunden e Schlagworttabelle f nfte Prozedur gt 25 Minuten e Schlagworttabelle sechste Prozedur Messung abgebrochen Das manuelle Anwenden des Mergingverfahrens auf die unvollst ndige Duplikattabelle er gibt nahezu keine Interaktionsanfragen Eine Anfrage an die Tabelle zeigt dass sich in der Schlagworttabelle sehr viele Attributwerte hoher hnlichkeit befinden Der abgebrochene Vorgang hat bereits 2815 Duplikate gefunden Bei einer hohen Zahl an Duplikaten werden die Verfahren deutlich langsamer Zu erkl ren ist dies daran dass Vergleiche mit u eren 2 KAPITEL 6 TESTBERICHT Partitionen viel eher als Abhangigkeit erkannt werden als bei eher diversem Datenbe stand Da die Verfahren keine lernenden Verfahren sind wird das Wiederkehren bereits als Duplikate erkannter Werte ignoriert und eine neue Pr fung angesto en Tabellen mit vielen Duplikaten f hren ebenfalls dazu dass das Merging mehr Zeit braucht um alle als Cluster zusammenh ngenden Tupel zu finden Fehlerkennungen bleiben be
126. rging zum Einsatz Siehe dazu Abschnitt 2 4 2 Existieren zwischen Tupeln verschiedener oder gleicher Tabellen Beziehungen sind die se Tupel im Verbund zu betrachten Tupel k nnen in einem solchen Fall auf weitere Tupel verweisen die als Duplikate existieren In diesem Fall wollen wir von duplizierten Ver weisen sprechen Im Falle von ehemals duplizierten Tupeln kann auch eine alte Beziehung nicht gel scht worden sein Dadurch k nnen verwaiste Schl ssel zur ck bleiben Bei spiel verweise Tupel A auf C und B auf D und diese seien jeweils Duplikate so m sste bei Korrektur einer der Verweise angepasst werden 8 KAPITEL 2 GRUNDLAGEN Abbildung 2 1 Nachfiihrende Behebung von duplizierten Tupeln mit Verweisen Es ist des Weiteren m glich Tupel und Beziehung als Einheit auf Duplikate zu unter suchen Dadurch ist es m glich die gesamte Beziehung zwischen Tupeln zu vergleichen Eine solche Einheit schafft einen neuen Datengegenstand den wir Objekt nennen wollen Das Objekt wollen wir im Ausblick n her diskutieren da im Rahmen dieser Arbeit die einfache Beziehungsaufl sung zun chst ausreichend ist 2 1 2 Hierarchien innerhalb der Datengegenst nde Es ist eine Hierarchie zu erkennen die bei der Anwendung von Bereinigungsabl ufen zu beachten ist Es wurde bereits kurz erw hnt welche Arten von Fehlern an den Da ten auftreten k nnen dabei ver ndert die Reihenfolge der Behandlung der Fehler das Endergebnis
127. rieben und die Prinzipien der Werkzeuge dargestellt Kapitel 5 enth lt das Handbuch zu den entwickelten Werkzeugen Kapitel 6 zeigt einen Beispielprozess in der Praxis und die Probleme die dabei auftreten k nnen Kapitel 7 beschreibt die Implementierung der in Kapitel 4 entwickelten Werkzeugsuite Das Kapitel 8 gibt einen Ausblick auf weitere M glichkeiten der Datenbereinigung Im Anhang ist die API Dokumentation zu der im Kapitel 6 beschriebenen Implementie rung zu finden KAPITEL 1 EINLEITUNG Kapitel 2 Grundlagen Als ersten Schritt wird sich dieses Kapitel mit den Grundlagen der Datenbereinigung befassen Dazu werden zunachst die zu betrachtenden Datengegenstande vorgestellt die bei einer Bereinigung eine Rolle spielen Anschlie end werden Umfang und Ablauf einer Bereinigung vorgestellt und Beispielverfahren genannt die bei einer Bereinigung zum Ein satz kommen k nnen Abschlie end wird die bibliographische Datenbank des Fachgebiets Datenbanken und Informationssysteme vorgestellt 2 1 Der Begriff Datenbereinigung Der Begriff Datenbereinigung kann sehr allgemein verwendet werden Je nachdem was als Daten und was als Datenverunreinigung angesehen wird ndert sich der Blickwinkel hinsichtlich des Begriffs Datenbereinigung Zum Beispiel kann das Entfernen berfl ssiger Leerzeichen in einem Textdokument eine Datenbereinigung sein aber auch das Auffinden und Korrigieren von fehlerhaften Eintr gen in Datenbank
128. rkn pfungen ignoriert Dies kann aber dazu f hren dass es bei der Fehlerkorrektur zu einer Foreign Key Verletzung kommt 5 3 HAUPTOBERFL CHE PROZESS 65 vYerweisende Tabellen verweise korrigieren verweise korrigieren TERMIN MITARBEITER TELEFON ITARBEITER i i 4 vorher bereinigen Referenzierte Tabellen vorher hereinigen h r Abbildung 5 12 Werkzeugeinstellung Verweise Beachten Sie dass Ihre Werkzeugeinstellung nur bernommen wird wenn Sie im rechten Panel auf die Schaltfl che Ubernehmen klicken siehe Abbildung 5 10 Die Einstellung wird sofort aktiv Mit der Schaltfl che Fertig schlie t das Fenster 5 3 Hauptoberflache Prozess Auf der Registerkarte Prozess der Hauptoberfl che befinden sich die Steuerelemente um eine Bereinigung zu starten 66 KAPITEL 5 BENUTZERHANDBUCH amp DB Cleaning OF x Datei Koniguration Prozess Konfiguration Prozess 1 f Prozesszustand laden Prozesszustand speichern Prozess starten Prozess Log Status Werkzeuge eingestellt 5 5 an DB angemeldet Programm beenden Abbildung 5 13 Hauptoberfl che Prozess Das Textfeld in der Mitte der Oberfl che zeigt den derzeitigen Prozesszustand an Mit den Schaltfl chen Prozesszustand laden und Prozesszustand speichern kann der Pro zesszustand f r eine sp tere Fortsetzung archiviert werde
129. rld Data is Dirty Data Cleansing and The Merge Purge Problem Data Mining and Knowledge Discovery 2 1 1998 9 37 V I Levenshtein Binary codes capable of correcting deletions insertions and reversals Soviet Physics Doklady 10 8 1966 707 710 A Mazeika M H Bohlen Cleansing Databases of Misspelled Proper Nouns In Proceedings of the First Int VLDB Workshop on Clean Databases CleanDB 2006 September 11 2006 Seoul Korea 2006 A E Monge C Elkan The Field Matching Problem Algorithms and Ap plications In E Simoudis J Han U M Fayyad eds Proceedings of the Second International Conference on Knowledge Discovery and Data Mining AAAI Press Menlo Park Calif 1996 267 270 S Y Sung Z Li S Peng A fast filtering scheme for large database cleansing In K Kalpakis ed Proceedings of the Eleventh International Conference on Information and Knowledge Management CIKM 2002 November 4 9 2002 McLean Virginia USA ACM Press New York NY 2002 76 83 109 110 LITERATURVERZEICHNIS Ukk92 E Ukkonen Approximate String Matching with q grams and Maximal Mat ches Theoretical Computer Science 92 1 1992 191 211 ZLBLO4 J Zhang T W Ling R M Bruckner H Liu PC Filter A Robust Filtering Technique for Duplicate Record Detection in Large Databases In F Galindo M Takizawa R Traunmiiller eds Database and Expert Systems Applicati ons 15th International Conference DEXA 2004
130. rne Biblio thek ben tigt es den JDOM Parser aus der jdom jar zum Verarbeiten von XML Dateien Erg nzend zu dieser Datei geh rt der JOBC Datenbanktreiber f r Oracle 10 Datenban ken zum Packet Dieser befindet sich in der Datei ojdbc14_ g jar Schlie lich geh rt zu dem Packet noch eine ZIP Datei mit den Oracle OCI Instant Client Dateien f r Windows und Linux Systeme in der passenden Version zum mitgelieferten JDBC Treiber 5 1 1 Anforderungen F r die Ausf hrung der Anwendung m ssen folgende Anforderungen eingehalten werden ojdbcel4_ g jar muss im gleichen Verzeichnis mit dem Hauptprogramm liegen e jdom jar muss im gleichen Verzeichnis mit dem Hauptprogramm liegen e Es m ssen Oracle Client Dateien auf dem Client PC zur Verf gung stehen Die installierten Oracle Client Dateien m ssen mit dem JDBC Treiber kompatibel sein e Stehen keine Oracle Client Dateien zur Verf gung kann der OCI Instant Client in Version 10 verwendet werden e Es wird eine Java Version ab 1 5 0_ 17 ben tigt 59 56 KAPITEL 5 BENUTZERHANDBUCH 5 1 2 Vorbereitungen zur Installation Kopieren Sie die drei JAR Dateien in ein gemeinsames Verzeichnis Wenn Sie keinen installierten Oracle Client haben oder Sie keinen OCI Instant Client zur Hand haben entpacken Sie die im Packet enthaltene ZIP Datei in dasselbe Verzeichnis in das Sie die JAR Dateien kopiert haben In ihr befindet sich der OCI Instant Client in der Version 10 f r Windows 32Bit u
131. rt werden Im Zusammenhang stehende Funktionalit ten erscheinen aber bereits in den zugeh rigen Abschnitten 4 2 Architektur Konzipiert werden soll eine Werkzeugsuite zur Bereinigung einer Oracle Datenbank als Benutzeranwendung Dies setzt sich zusammen aus dem benutzerinteraktiven Teil einer implizierten Steuereinheit und aus den Werkzeugen die auf den Datenbestand wirken Zur detailierteren Diskussion teilen wir diese Zusammensetzung auf in e Die Benutzerebene e Die Verarbeitungsebene l 32 KAPITEL 4 KONZEPTION Dabei umfasst die Benutzerebene die Interaktionsschnittstelle mit dem Benutzer was auch die Wahl der Werkzeuge beinhaltet Die Verarbeitungsebene stellt den operativen Part der Werkzeuge auf den Datenbestand dar Anders ausgedr ckt entf llt auf die Benut zerebene die graphische Darstellung sowie eine Sammlung an Informationen der verf gba ren Werkzeuge Informationen umfasst hierbei zum Beispiel Konfigurationsm glichkei ten und Parameter Die Verarbeitungsebene wiederum beinhaltet den Datenbestand und die darauf operierenden Prozeduren der Werkzeuge Es zeigt sich dass der Werkzeugpart Teilmenge beider Ebenen ist Der Rahmen der Benutzerebene stellt der Client dar Dieser Client stellt dem Benutzer Interaktionsm glichkeiten zu Verf gung um Werkzeuge auf eine Datenbank anzuwenden Teil des Client ist folglich die Bedienoberfl che Zus tzlich zu den allgemeinen Bedien optio
132. s wird die Klasse AttributReplacer im Paket Tools erstellt die das Interface ITool im plementiert Die Funktionen zur R ckgabe der unterst tzten Dom ntypen k nnen leer bleiben da dieses Werkzeug wertunabh ngig arbeitet Jedoch muss der Name des Werkzeuges in der get ToolString Funktion aufgef hrt sein Namen von Werkzeugen sind eindeutig Die Funktion getConfigShortText erzeugt aus einem String Array das die Werk zeugeinstellungen repr sentiert einen kurzen Beschreibungstext der in den Listenfeldern angezeigt werden soll wenn das Werkzeug konfiguriert wurde Die Zuordnung der Schl s sel zu den Werten entspricht dabei der vom Werkzeug bei der Werkzeugeinstellung selbst erstellten Zuordnungsvorschrift Diese Werkzeugeinstellungen werden mit der Oberfl che erstellt die durch editConfig beschrieben wird Es ist darauf zu achten dass das Werkzeug selber auf Eingaben dieser Maske reagieren muss Die bei Eingaben werden geordnet als String Array dem passendem Eintrag in der Prozessliste aus der Klasse FrameworkCFG zugeordnet Hier w rde die Einstellung der Tabelle des Attributes des Suchmusters die Art des Suchmusters die Ersetzung und ob eine Interaktion vorkommen soll von der Oberfl che verlangt Die run Tool Methode f hrt schlie lich das Werkzeug aus Hier w rde anhand der Ein stellung der Interaktion entschieden ob direkt ein SQL Befehl zur Datenmanipulation abgesetzt wird oder ob erst das Suchmuster in ein
133. schaltbare R ckfrage Hier werden in Attributwerten eines konfigurierten Attributs vorkommende Suchmus ter gegen die konfigurierte Ersetzung ersetzt Das Suchmuster kann dabei ein regul rer Ausdruck oder eine Teilzeichenkette sein Das jeweils passende Verfahren wird durch die Konfiguration bestimmt Damit ist es zum Beispiel m glich alle Mustermann in Mus terfrau zu ndern aber auch komplexere Ersetzungen vorzunehmen Auch hier handelt es sich um eine wertunabh ngige Fehlerkorrektur 4 4 2 3 Attributwert Duplikatbereiniger Parameter Tabelle Attribut Attributeigenschaften zus tzliche Optionen f r Tupel Duplikatbereiniger siehe 4 4 1 1 Ausgabe keine Tempor re Tabellen gem Tupel Duplikatbereiniger Interaktion gem Tupel Duplikatbereiniger 44 KAPITEL 4 KONZEPTION Bei diesem Werkzeug handelt es sich um einen Attributwertvergleich Es sollen dabei alle Attributwerte hnlicher Schreibweise gruppiert werden und auf einen Referenzwert angepasst werden Dies hat das Ziel Schreibfehler zu beheben und hnliche Schreibweisen zu normalisieren Der Aufbau der Fehlererkennung entspricht einer Vereinfachung des Tupel Duplikat bereinigers Dazu wird zun chst das aus den Attributeigenschaften abgeleitete hnlichkeitsma ge w hlt und ein entsprechendes Vergleichverfahren f r PC Filter vorbereitet Anschlie end wird das zu behandelnde Feld als eine einspaltige Tabelle durch PC Filter analys
134. send kann eines der oben genannten Duplikatverfahren angewandt werden 2 4 Verfahren zur Fehlerkorrektur In diesem Abschnitt wird verdeutlicht welche Optionen es zur Fehlerkorrektur auf Attribut Ebene mit Hilfe eines Referenzwertes und auf Tupel Ebene durch Merging gibt 2 4 1 Korrektur mit Referenzwert Wurde durch die Fehlererkennung eine Menge von Attributwerten gefunden die eine hohe hnlichkeit aufweisen also einen Cluster bilden so stellt sich die Frage welcher dieser Attributwerte nun der zur gew nschten Darstellung passende Wert ist Die eigentliche Korrektur besteht aus dem einfachen Ersetzen aller nicht passenden Werte Dazu kann man mehrere Ans tze verfolgen Zun chst besteht die M glichkeit schon vor der Bereinigung Referenzwerte vorzugeben von denen der Passende zur Laufzeit anhand der hnlichkeit zu den Attributwerten be stimmt werden kann Es wird also in einem Lexikon von Referenzwerten nach einem passenden gesucht Ein Anwendungsfall zur effektiven Anwendung vorgegebener Refe renzwerte w re zum Beispiel das automatische Ersetzen von Abk rzungen gegen die ausgeschriebenen Begriffe Der umgekehrte Fall w re dass der Benutzer zu der Menge w hrend der Laufzeit den passenden Referenzwert eingibt Der Referenzwert kann automatisch ermittelt werden indem der am h ufigsten vorkom mende Attributwert ermittelt wird Dessen Auftrittsh ufigkeit sollte dabei eine zuvor gesetzte Schranke berschreiten
135. t dabei mit der Klasse Controller und st t notwendige Funktionsbl cke durch Auswerten der Benutzerinteraktion an 7 2 2 2 Paket View GD StandardView On ghc cresteJButtonf createdhlenutemt Ty getFramec e parentAction GD StandardFrameView StandardlFrameView gt StandardDialogView On frame On frame On frame parent parent parent Ka Ka E l be standardFrame view ei standardiFrameview a standardDialog view a StandardFrame view e standardiFrame view a StandardDialog view a StandardFrame view ei standardiFrame view a StandardDialog view CO actionPerformed 2 slandardiFrame view actionPertormed addCompopertsr actionPerformed e addlomponertsl Da getFramec BEER E crestelntbialogl o getFramet E createlnitDialog getframen getParent Ki setP arentl Da getParent a setParent 3 FrmMainvView DigDBCfy DigProcessCfg DigTableCfg OlgbBctan OlgbBctan e DigProcessCtg DiobrocessC rot DlaTablectat amp DlaTableCtat o actionPerformed o actionPerformed actionPerformed o addComponentst o addlompanentsl o addlompanentsl parentAction parentAction parentAction saweEntriesl CO savweEntriesl CO savweEntriesl CO uUpdateProcessList CO updateSaLTablesl updateToollistl updateTaklelistl Abbildung 7 3 Klassendiagramm 1 von Paket View Aus Gr nden der bersichtlichkeit wurde auf die
136. thode interactionPane erzeugt ein JPanel dass die Oberfl che f r die Benut zerinteraktion darstellt Die Klasse TupelDuplicate besitzt noch die private Methode modelSetup Dabei han delt es sich um eine Methode die SQL Anweisungen zum Generieren der PL SQL Pro zeduren sammelt um die runTool Methode bersichtlich zu behalten 7 2 3 Aufbau von Werkzeuge Werkzeuge werden als Klassen im Paket Tools implementiert Dabei muss eine solche Klasse mindestens folgendes leisten e Es muss eine Prozedur zur Beschreibung eines Konfigurationsdialogs f r die View existieren e Es muss eine Prozedur zur Beschreibung eines Interaktionsdialogs f r die View existieren e Es muss eine Prozedur zum Ausf hren des Werkzeuges geben e Die Klasse muss mit dem Model Part kommunizieren e Das Werkzeug muss auf Abbruchkommandos reagieren Da die Methoden die diese Vorgaben erf llen die Grundlagen f r den Zugriff ber die Klassen des Paket View und Paket Configuration bilden sind diese im Interface I Tool definiert Ein Werkzeug implementiert dieses Interface So kann jedes Werkzeug unab h ngig von seiner genauen Funktion konfiguriert und ausgef hrt werden Werkzeuge werden durch die Klasse RegisterTools an der Konfiguration registriert Das Werkzeug bekommt eine Identifikation und wird als instanziertes Objekt der Liste vom Typ ToolList hinzugef gt Von dort k nnen die Werkzeuge in die Prozessliste a
137. tt 3 3 Der Grundschritt sieht vor die Zeichenketten in deren Mengen von Atomic Strings al so einzelne W rter zu zerlegen und die Gesamtzahl der W rter beider Mengen zu be stimmen Diese einzelnen W rter werden untereinander mit einem boolschen Vergleich gepr ft Identische W rter werden aus beiden Mengen entfernt und gez hlt Wir erhalten die Anzahl identischer W rter die Gesamtzahl aller W rter und zwei Men gen an W rtern die nun auf hnlichkeit gepr ft werden m ssen Die brigen W rter werden mit Field Similarity gepr ft und f r jedes Wort dessen h chs ter hnlichkeitsfaktor gemerkt Alle hnlichkeitsfaktoren die nicht auf eine Identit t hinweisen also unterhalb der h chst m glichen hnlichkeit sind werden zu der Anzahl identischer W rter addiert und die zugeh rigen W rter aus ihren Mengen entfernt Die brigen W rter wurden durch den boolschen Vergleich als nicht identisch gewertet aber wurden durch Field Similarity entsprechend bewertet Dies l sst auf einen gleichen Zeichenvorrat schlie en bei dem Field Similarity die Reihenfolge des Auftretens gem dessen Definition aus Abschnitt 3 3 ignoriert Auf diese W rter wird nun Q Grams mit g 2 angewendet und erneut der h chste hnlichkeitsfaktor gemerkt Alle hnlichkeitsfaktoren werden nun mit dem h chstm glichen hnlichkeitsfaktor ad diert durch 2 geteilt und anschlie end zu der Anzahl identischer W rter addiert Dadurch wird ein
138. tungsebene abgelaufen sein Das hei t er kann vor oder nach dem Kon figurationsblock ablaufen Aus Gr nden der bersichtlichkeit soll zun chst angenommen werden dass er vor dem Konfigurationsblock l uft und damit bereits eine Verbindung zur Verarbeitungsebene besteht Der Block Ablaufsteuerung umfasst die Ausf hrung der Werkzeuge deren Zustands berwachung die eigene Zustands berwachung und den Ablaufplan W hrend sich die Anwendung in diesem Block befindet werden also Werkzeuge ausgef hrt Dabei regelt der Ablaufplan welche Werkzeuge ausgef hrt werden Da die Ausf hrung der Werkzeuge Teil des Ausf hrungsblocks des jeweiligen Werkzeuges ist behandeln wir diesen separat siehe dazu auch 4 2 2 und 4 4 Der Ablaufplan enth lt neben den statischen Programmablauf auch die Aufrufliste f r die Werkzeuge Diese Liste bezeichnen wir als Prozessliste Diese wurde w hrend der Konfiguration erstellt und wird sp ter behandelt Der Zu stand des Ablaufs wird im Prozesszustand festgehalten Darunter f llt die Position in der Prozessliste der Zustand des Ausf hrungsblocks des jeweiligen Werkzeugs und der eigene Zustand Die Elemente Ausf hrung und Zustands berwachung der Ablaufsteuerung bilden den Prozess Block in dem die Anwendung selbstt tig agiert und Zustands nderungen ber wacht Der Ablauf der Anwendung entspricht damit den Bl cken Initialisierung Konfigurati on u
139. tzer 2 T Tupel Duplikatbereiniger A Attribut Duplikatbereiniger A ISBN Pr fer A Autoren Formatbereiniger Runter D Abbrechen Speichern Speichern und weiter Abbildung 5 8 Prozessliste Neu hinzugef gte Werkzeuge sind noch unkonfiguriert und m ssen im n chsten Schritt eingestellt werden Die Grundeinstellung eines Werkzeuges ist anhand des Zusatzes im Listeneintrag zu entnehmen Mit der Schaltfl che Speichern werden Ihre nderungen in die Konfiguration bernom men Mit der Schaltfl che Speichern und weiter gelangen Sie zur Werkzeugeinstellungen 5 2 5 Mit der Schaltfl che Abbrechen werden Ihre nderungen ignoriert und das Fenster geschlossen 62 KAPITEL 5 BENUTZERHANDBUCH 5 2 5 Werkzeugeinstellungen In diesem Dialog legen Sie die Einstellungen f r Ihre Werkzeuge fest Im linken Panel sehen Sie Ihre Prozessliste Allen unkonfigurierten Werkzeugen fehlt ein entsprechender Zusatz im Listeneintrag 2 Werkzeugeinstellung Prozessliste 1 4 Ersetzer PILPERSON NAME wolski gt WWolski 2 D Tupel Duplikatbereiniger KA Abbrechen Abbildung 5 9 Werkzeugeinstellung kein gewahltes Werkzeug Wahlen Sie ein Werkzeug das Sie konfigurieren wollen und im rechten Panel wird sich der Einstellungsdialog ffnen Die verf gbaren Optionen variieren je nach Werkzeug Als Beispiel wird hier ein
140. ufgenom men werden Jedes Element der Prozessliste stellt einen eigenen Prozess dar Es werden zu jedem Prozess die Werkzeugeinstellungen und einen Verweis auf das jeweilige Werk zeug abgelegt Vgl Klasse FrameworkCFG in Abschnitt 7 2 2 3 Dadurch gen gt die einmalige Instanzierung eines Werkzeuges durch die Klasse Register Tools Bisher nicht beachtet wurde das in Abbildung 7 6 und 7 5 vorkommenden Enum Sim Types sowie das Interface ISimList Da jedes Werkzeug ein abgeschlossenes System darstellt ist es der Anwendung nicht bekannt welche optimierten Verfahren zur Ahnlich keitsfaktorerzeugung f r bestimmte Dom nentypen vom Werkzeug unterst tzt werden Beim Anmelden des Werkzeuges wird nun die Information vom Werkzeug abgerufen wel che Dom nentypen es unterst tzt und diese in die Liste vom Typ Jon List eingetragen Da nun nicht jedes Werkzeug die gleichen Dom nentypen kennt wird zus tzlich zu dem Dom nentyp noch der Datentyp auf dem der Dom nentyp basiert in die Liste aufge nommen Damit ist es anderen Werkzeugen m glich bei unbekanntem Dom nentyp das 82 KAPITEL 7 IMPLEMENTIERUNG hnlichkeitsma ber den Datentyp zu w hlen Die unterst tzten Standarddatentypen befinden sich in dem zuvor genannten Enum Sim Types Bei der Abarbeitung der Prozessliste wird die Prozedur zum Ausf hren des Werkzeuges gestartet W hrend sich das Werkzeug in der Ausf hrung befindet muss es auf Abbruch kommandos reagieren k nnen
141. und der Partitionsrandbereich beeinflussen dabei die Anzahl der Iterationen ber die Partitionen Eine Erh hung des Randbereichs erm glicht eine genauere Erkennung von Duplikaten zu Tupeln in verschiedenen Partitionen Durch die steigende Anzahl der Vergleiche verl ngert sich aber auch die Ausf hrzeit Die Ausgabe des Verfahrens sind Cluster mit Tupeln hoher hnlichkeit PC Filter erf llt die oben genannte Vorgabe f r einen Duplikaterkenner f r Attributwerte und ist zudem in der Lage auch entfernte Tupel bzw Attributwerte zu vergleichen So ist es mit PC Filter m glich mit entsprechenden hnlichkeitsma Hans M ller und M ller Hans als Duplikat erkennbar zu machen 3 2 Q Grams Das Q Gram Verfahren Ukk92 zerteilt die Eingangszeichenketten in Teilstrings Q Grams der L nge q Dabei werden die Eingangszeichenketten durch ein sich verschie bendes Fenster dieser Gr e q aufgeteilt Um die Anfangs und Endbuchstaben einzeln auswerten zu k nnen ist es f r q gt 1 n tig vor und hinter der jeweiligen Eingangszeichen kette noch spezielle Steuerzeichen zu setzen die den Anfang sowie das Ende markieren und in der Zeichenkette nicht vorkommen Dies k nnen beispielsweise die Zeichen und 7 sein Jedes Auftreten eines Teilstrings wird mit einer Auftrittsnummer versehen Diese gibt an wie oft der Teilstring bereits aufgetreten ist Als Beispiel sei die Eingangszeichenkette GeorGe g
142. uriert 1 5 an DB angemeldet Abbildung 5 3 Hinweisfeld Um die aktuelle Konfiguration zu entladen und eine neue Konfiguration zu erstellen kli cken Sie auf Neue Konfiguration erstellen Sie k nnen mit den Schaltfl chen des Panels Konfiguration zu den einzelnen Konfigu rationsschritten springen Achten Sie darauf dass einige Konfigurationsabschnitte erst aktiv werden wenn die vorhergehenden Konfigurationsschritte erfolgt sind Ihnen stehen zur Auswahl e Datenbankzugang e Tabellenkonfiguration e Attributkonfiguration 08 KAPITEL 5 BENUTZERHANDBUCH e Prozessliste e Werkzeugeinstellungen Diese Schaltfl chen sind auch im Men Konfiguration verf gbar Beachten Sie dass eine nderung der Konfiguration automatisch den Prozesszustand siehe 5 3 zur cksetzt Sollten Sie eine Schaltfl che bet tigen und folgenden Dialog sehen so bedeutet dies dass die Anwendung zurzeit nicht an der Datenbank angemeldet ist Geben Sie Ihre Datenbanknutzerkennung ein um die Anwendung mit der Datenbank zu verbinden Benutzername p Passwort Abbrechen o Abbildung 5 4 Datenbanklogin 9 2 1 Datenbankzugang Hier tragen Sie die Verbindungsdaten zu Ihrem Oracle Datenbank Server ein In das Feld mit der Bezeichnung Hostname tragen Sie die Adresse des Servers ein Das Feld mit der Bezeichnung Port ist f r den Verbindungsport zust ndig Der Standardport f r Oracle Datenbanken ist 1
143. vor beschriebenen Kommunikation der Ebenen Wir definieren das View Element als die Darstellung der Bedienoberfl che Die Vorkonfigu ration der Anzeige bernimmt f r uns der Controller Part Dieser setzt sich zusammen aus dem frameworksteuernden Segment und dem werkzeugsteuernden Teil Das Frame worksegment folgt dem vorgegebenen Programmablauf und ist f r die Rahmenfunktion der Anwendung notwendig Das Werkzeugsegment setzt sich zusammen aus allen im Fra mework registrierten Werkzeugen Dieses umfasst wiederum die zur Anzeige der Werk zeugeigenschaften notwendigen Informationen als auch die werkzeugsteuernden Operatio nen Das Model schlie lich ist f r den Zugriff auf den Datenbestand zust ndig Die vom Controller aufgerufenen Operationen werden hier abgearbeitet und eine R ckmeldung zur ckgeliefert Bedienoberfl che Werkzeuge Datenbestand Konstruktion Verarbeitung Einstellung Ansto en und und und und Interaktion Oberfl chenparameter berwachung R ckmeldung Controller Konfiguration Frameworkeinstellung Ablauf steuerung Werkzeugeinstellung Prozesszustand Abbildung 4 2 MVC Abh ngigkeitsbeispiel 34 KAPITEL 4 KONZEPTION 4 2 2 Blockstruktur Neben der Aufteilung in Ebenen lassen sich die Funktionseinheiten der Anwendung in Funktionsbl cke aufspalten Durch eine solche Blockstruktur erreichen wir zum Einen eine bersichtliche Aufteilung der Teilsysteme und zum anderen k nnen
144. wir wieder das Beispiel A Mainz B Heinz Ta M1 al il n1 z1 H1 e1 il n1 z1 T Gg fil n1 ek Hier wird ersichtlich dass es sich beim hnlichkeitsma um ein Q Gram Verfahren mit q 1 handelt Die Faktorbildung unterscheidet sich allerdings zum vorher beschriebe nen Verfahren Dementsprechend weicht das Ergebnis von dem mit dem vorgestellten Q Grams Verfahren ab Zur Bestimmung des hnlichkeitsfaktors wird die Anzahl der im resultierenden Tupel enthaltenen Zeichen in Relation zu der Zeichenanzahl der Original tupel gesetzt Es wird der kleinere Wert gew hlt da die hnlichkeit der beiden Zeichen ketten zueinander nicht gr er sein kann als die kleinste hnlichkeit des resultierenden Tupels zu einem Originaltupel sim T Th min ET mnn hier sim Ta Th 2 0 6 entgegen 2 0 42 mit Q Grams q 1 Beispiel 3 5 un hnliche Zeichenfolge mit Field Similarity Wie bereits erw hnt ignoriert dieses Verfahren die Reihenfolge des Auftretens von Zeichen einer Auftrittszahl Dies f hrt dazu dass auch B Hinze einen Ahnlichkeitsfaktor von 3 hat gt 3 4 Vergleich von Q Gram zu Field Similarity Die folgende Tabelle gibt einen berblick ber die erzeugten hnlichkeitsfaktoren von Q Grams mit unterschiedlichen q Werten und Field Similarty Eingabe 1 Zeichendreher A Hanna B Hanan Eingabe 2 Austausch von zwei Zeichen A Henne B Hanna Eingabe 3 un

- Fachgebiet Datenbanken und Informationssysteme

Contents

Download Pdf Manuals

Related Search

Related Contents