Hasso-Plattner-Institut
  
Hasso-Plattner-Institut
Prof. Dr. Felix Naumann
  
 

Neue Entwicklungen im Bereich Informationssysteme

Im Rahmen dieses Forschungsseminars stellen Mitarbeiter und Studenten ihre Forschungsarbeiten auf diesem Gebiet vor. Studenten und Gäste sind herzlich eingeladen.

Allgemein

Wann: Montag, 15:15 - 16:45 Uhr

Wo: Raum A-1.2

Sascha Szott: XML Schema Matching unter Verwendung der Tree-Edit-Distance

Das Schema Matching beschreibt das Problem des (semi)automatischen Auffindens der semantisch äquivalenten Elemente in heterogenen Datenquellen, wobei wir uns auf XML-Datenquellen beschränken wollen, und tritt beispielsweise im Rahmen der Integration dieser auf. Ein Schema Matching System erhält damit als Eingabe zwei XML Schema Definitionen, d. h. zwei in der Sprache XML Schema spezifizierte Schemata, und liefert als Ergebnis ein sogenanntes Schema Mapping, das die als semantisch äquivalent betrachteten Schemaelemente definiert. Nach einer Einführung der Tree-Edit-Distance wird im Rahmen des Vortrages ein Ansatz vorgestellt, der die Tree-Edit-Distance für die Berechnung des Schema Mappings einzusetzen versucht. Wir zeigen exemplarisch auf, welche Probleme sich dabei ergeben und präsentieren daraufhin einen alternativen, auf der Tree-Edit-Distance aufbauenden Ansatz. Im letzten Teil des Vortrages stellen wir die im Rahmen der Evaluation des Ansatzes gewonnen Ergebnisse vor. Diese zeigen auf, dass die ermittelten Schema Mappings im Allgemeinen von höher Qualität sind. Wir beschließen den Vortrag mit einem Ausblick und geben im Anschluss die Möglichkeit der Diskussion.

Melanie Weis: Structure-Based Inference of XML Similarity for Fuzzy Duplicate Detection

Fuzzy duplicate detection aims at identifying multiple representations of real-world objects stored in a data source, and is a task of critical practical relevance in data cleaning, data mining, or data integration. Fuzzy duplicate detection has a long history for relational data stored in a single table (or in multiple tables with equal schema). Algorithms for fuzzy duplicate detection in more complex structures, e.g., hierarchies of a data warehouse, XML data, or graph data have only recently emerged. These algorithms use similarity measures that consider the duplicate status of their direct neighbors, e.g., children in hierarchical data, to improve duplicate detection effectiveness.

We propose a novel similarity measure for fuzzy duplicate detection in hierarchical and semi-structured XML data. Unlike previous approaches, it not only considers the duplicate status of children, but rather the probability of descendants being duplicates. Probabilities are computed using Bayesian networks. Experiments show the proposed algorithm is able to maintain high precision and recall values even when dealing with data containing a high amount of errors, and it obtains up to 10% higher f-measure scores than another state-of-the-art XML similarity measure.

Paul Führung: Emergent Data Quality Annotation and Visualization

The systematic assessment, storage, and retrieval of data quality scores has proven to be an elusive problem, often tackled only with classifications, questionnaires, and models. We present a concrete solution for the graphical annotation of data with quality scores, to enable their efficient storage and retrieval, and ultimately their graphical display on top of the actual data. Our tool, VIQTOR, enables users to assign quality scores using simple point and click techniques in a natural data display environment, such as spreadsheets.

The particular challenges we tackle are the support of multiple users assigning different quality scores, the flexible assignment of quality scores to any subset of the data (rows and columns), the assignment and storage of scores in multiple quality criteria, and the graphical display of those scores aggregated both across users and across quality
criteria. As multiple users assess scores, an overall quality assessment emerges.

Melanie Weis: Duplikaterkennung in XML Daten (Probevortrag Disputation)

Duplikaterkennung beschäftigt sich mit der Identifikation verschiedener Repräsentationen jedes in einer Datenquelle repräsentierten Objekts. Duplikaterkennung ist Bestandteil von Datenreinigungs- und Datenintegrationsprozessen und wurde bisher für einen innerhalb einer Relation repräsentierten Objekttyp behandelt. Wir betrachten nun iterative Duplikaterkennung in XML Daten, bei der mehrere in Beziehung zueinander stehende Objekttypen betrachtet werden.

In diesem Probevortrag zu meiner Promotionsverteidigung betrachte ich die Fälle, in denen Beziehungen eine hierarchische Struktur ergeben und beschreibe sowohl ein Ähnlichkeitsmaß als auch Algorithmen, die für XML Duplikaterkennung besser als herkömmliche Verfahren geeignet sind.

Jürgen Göres: Ein Metadaten-Verwaltungs-Framework für die dynamische Informationsintegration

Um die effiziente Nutzung von über das Internet oder mittels Data Grids verfügbaren, strukturierten und semistrukturierten Datenquellen zu ermöglichen, ist die Bereitstellung von einfach zu benutzenden Integrationsdiensten erforderlich, die es mit möglichst geringem manuellen Aufwand erlauben, eine auf die jeweilige Anwendung zugeschnittene, homogene integrierte Sicht über die relevanten Datenquellen zu erstellen.
Um dieses Ziel zu erreichen, ist das Zusammenführen bestehender und die Entwicklung neuer Ansätze für die Lösung der vielfältigen Herausforderungen bei der Informationsintegration erforderlich, z.B. Techniken für das Schema Matching oder Merging, oder das Erstellen von Abbildungsvorschriften Mappings), welche die integrierte Sicht bereitstellen. Im Rahmen des PALADIN-Projekts entsteht die erforderliche Infrastruktur, um die Komposition bestehender und die Entwicklung neuer Integrationsdienste zu erleichtern. Zentraler Aspekt ist ein graphbasiertes, erweiterbares Metamodell, um so die Bereitstellung, Speicherung und den Austausch von Metadaten und Daten verschiedener Datenmodelle zwischen den Diensten zu ermöglichen. Graphtransformationen ermöglichen die Datenmodell- und Plattform-unabhängige, deklarative Beschreibung von Operationen auf Metadaten und Daten. Eine Skriptsprache erlaubt die einfache Komposition bestehender Integrationsdienste zu komplexeren Diensten. Ein generischer, mittels Graph-Stylesheets konfigurierbarer Editor vereinfacht die Bereitstellung von maßgeschneiderten Visualisierungs- und Editierfunktionen für jene Problemstellungen, die weiterhin menschliche Interaktion erfordern.

Oliver Albrecht: Filtern von Fremdschlüsseln aus Inklusionsbeziehungen

Um in Datenbanken unbekannter Struktur die vorhandenen Fremdschlüsselbeziehungen zu finden, ist es möglich aus den Inklusionsabhängigekeiten innerhalb der Datenbank jene zu filtern, die ein ein Fremdschlüssel sind. Gezeigt wird ein Verfahren, was die Inklusionsabhängigkeiten einer Datenbank analysiert und anhand von verschiedenen Eigenschaften bewertet, ob es sich um einen Fremdschlüssel handelt oder nicht.
Im Rahmen einer Studienarbeit am Lehrstuhl für Wissensmanagement in der Bioinformatik wurden Fremdschlüssel dahingehen untersucht in wie weit man sie automatisiert erkennen kann, ohne über die Semantik der Daten Kenntnis zu haben. Ergebnis dieser Arbeit sind verschiedene Heuristiken mit denen es möglich ist mit einer Precision von über 90% aus Inklusionsabhängigkeiten Fremdschlüssel heraus zu filtern.

Jan Schaffner, Jens Krüger, Anja Bog: Towards an ETL-less Zero-redundancy Architecture for Reporting on OLTP Data

While OLTP systems store up-to-date data, efficient reporting on top of these systems is not practicable due to performance reasons. OLAP systems provide sophisticated reporting capabilities, but do usually not use up-to-date data: common reporting architectures rely on complex, resource-intensive ETL processes that replicate OLTP data into read-optimized data structures in a batch job fashion during low system load times. This paper introduces an architecture for reporting directly on top of OLTP data that preserves the short response times of OLAP systems. To do so, data transformations typically carried out during ETL are performed at query-runtime in a column-oriented main memory database. The advantages over traditional reporting architectures are that up-to-date data can be provided and that additional OLAP data stores are no longer required. We validate our architecture with a prototypical implementation on the basis of SAP's ERP and DW products. A case study from the field of financial accounting will be introduced and used to compare the performance of our prototype to the existing product.

Andreas Thor: Automatische Mapping-Verarbeitung auf Webdaten

Das World Wide Web stellt eine Vielzahl von Informationen zur Verfügung. Neben dem Inhalt der Webseiten stellt ihre Verknüpfung durch Verweise zwischen ihnen eine wichtige Informationsquelle dar. So unterstützen z.B. Webseitenempfehlungen auf interessante andere Produkte Kunden großer E-Commerce-Websites bei der Suche nach dem passenden Produkt. Zusätzlich finden sich auf Seiten verschiedener Websites auch Informationen zum gleichen Objekt der realen Welt, so dass durch Links zwischen ihnen alle verfügbaren Informationen aus mehreren Datenquellen für entsprechende Analysen, z.B. einem Preisvergleich, erreichbar werden. In dieser Arbeit werden Verweise als sogenannte Mappings zusammengefasst, wobei ein Mapping eine Menge paarweiser Zuordnungen, sogenannter Korrespondenzen, zwischen Instanzdaten (Objekten) repräsentiert. Dabei wird mit dem Begriff Korrespondenz nicht nur die Verknüpfung gleicher Objekte gemeint, sondern allgemein eine semantische Beziehung zwischen zwei Objekten ausgedrückt. Innerhalb dieser Dissertation steht die Verarbeitung solcher Mappings, d.h. ihre Erzeugung, Optimierung und Verwendung, im Mittelpunkt.

Extended Abstract

Jens Bleiholder: Minimum- und Complement-Union und ihr Einsatz in DBMSs

Minimum Union ist die Kombination von Outer Union und der Entfernung subsummierter Tupel. Es wird u.a. in der Datenbank-Optimierung zur Umformulierung von Outer Join Anfragen verwendet, im Semantic Web Umfeld zur Implementierung des OPTIONAL Operators von SPARQL und auch zur Datenfusion. Dabei werden Unsicherheiten (Konflikte zischen Werten und NULL-Werten) beseitigt, aber nicht alle Fälle abgedeckt. Wir schlagen deshalb einen weiteren Operator vor, den Complement Union Operator, der Outer Union mit der Entfernung sich komplementierender Tupel kombiniert. Wir stellen Algorithmen zur Entfernung subsummierter und komplementärer Tupel vor, sowie die Implementierung von Minimum- und Complement Union und vergleichen diese. Desweiteren wird gezeigt wie diese neuen Operatoren in Anfragebäumen verschoben werden können.

Vergangene Forschungsseminare

Forschungsseminar 07

Forschungsseminar 06/07