• Felix Naumann
• Melanie Weis

One problem of data integration is the occurrence of sereval different representations of a same real-world object, which are called duplicates. The goal of this project is to devise algorithms that detect different representations of objects in XML data. To this end, we develop methods that consider  descriptive data of an object as well as relationships to other objects, e.g., in children, parent, or sibling XML elements. Traditionally, relational approaches only consider data stored in a single relational table, i.e., previous methods do not consider relationships.

Data cleaning defines the process of correcting errors in data, e.g., typographical errors, outdated information, or different formats. Duplicate detection is a crucial step in data cleaning, but we also consider further cleaning steps.

We propose three duplicate detection algorithms for XML Data. The goal of all three algorithms is to detect a maximum number of true duplicates without detecting false duplicates (effectivity) in a reasonlable amount of time (efficiency).

The top-down algorithm is useful for efficient and effective duplicate detection in hierarchical XML data, assuming that nesting of XML elements reflects 1:N relationships in the real world. This is for instance true for XML elements representing states and nesting city elements as children, because a city can only be located in a single state. Opposed to that, we observe a M:N relationship between movie XML elements and actor XML elements, although actors are nested under movies. In such scenarios, the top-down algorithm no longer performs effective duplicate detection, for which we propose the bottom-up algorithm. In general, an XML document may reflect a graph structure, e.g., if key references are used. An actor XML element nested under a movie XML elmenent may for instance be one of possibly many references to a an actor element.  We developed a third algorithm for scenarios where relationships form a graph. The algorithm exploits the additional relationships to improve effectivenes.

We developed a system for XML data cleaning in cooperation with INRIA Futurs, France. This system, named XClean, allows a declarative specification of an XML cleaning process. This program is then compiled to an XQuery, which can then be executed on any XQuery processor. Further information on XClean is available at http://www.hpi.uni-potsdam.de/~naumann/xclean/