Data Lineage

Data Lineage

Data-Lineage bzw. Datenherkunft (auch Data Provenance oder Data Pedigree, dtsch. auch Datenabstammung und -stammbaum) bezeichnet in einem Data-Warehouse-System (Datenlager) die Fragestellung, zu gegebenen aggregierten Datensätzen die ursprünglichen Datensätze zu bestimmen, aus denen sie entstanden sind.

Üblicherweise werden in einem Data-Warehouse-System Daten aus verschiedenen Quellen extrahiert, nach bestimmten Regeln transformiert und zur Analyse bereitgestellt (siehe ETL-Prozess). Beim Data-Lineage muss der umgekehrte Weg beschrieben werden, um von Analyseergebnissen zu den Quellen zu gelangen. Dazu werden die Transformationen mathematisch modelliert, um für gegebene Ausgabewerte einer Transformation die dazu gehörenden Eingabewerte zu bestimmen (siehe auch EVA-Prinzip).

Inhaltsverzeichnis

Transformationen

Alle Verarbeitungsschritte werden als Transformation T modelliert, die aus einer Eingabe E eine Ausgabe A erzeugen: T(E) = A. Die Lineage T' eines Datensatzes a der Ausgabe ist definiert als die Teilmenge E' der Eingabe, die an der Konstruktion von a beteiligt war: E' = T'(a,E). Die Lineage einer Menge von Datensätzen setzt sich aus der Lineage ihrer Elemente zusammen.

Alle Transformationen lassen sich in drei Klassen einteilen. Dabei wird davon ausgegangen, dass die Transformationen stabil und deterministisch sind, das heißt es werden keine neuen Ausgabeobjekte erfunden und die Ausgabe ist bei gleicher Eingabe konstant.

Blackbox

Blackbox

Eine Blackbox ist eine Transformation, über die sich keine speziellen Eigenschaften angeben lässt. Jedes Element der Ausgabe kann von jedem Element der Eingabe abhängen. Ein Beispiel für eine Blackbox ist eine Funktion, die für jede Zahl einer Menge die Abweichung vom Mittelwert angibt. Die Data Lineage ist somit die gesamte Eingabe:

T'(a,E) = E
Dispatcher

Dispatcher

Ein Dispatcher ist eine Transformation, die Elemente der Eingabe unabhängig voneinander behandelt. Jedes Eingabeelement kann beliebig viele Ausgabeelemente erzeugen (auch Null). Die Lineage eines Elements der Ausgabe eines Dispatchers setzt sich aus allen Elementen e der Eingabe zusammen:

T'(a,E)=\{e \in E | a \in T(e)\}

Ein Spezialfall eines Dispatchers ist ein Filter. In einem Filter erzeugt jedes Eingabeelement entweder sich selbst oder gar keine Ausgabe. Die Lineage eines Filters entspricht genau der Ausgabe:

T'(a,E) = a.


Aggregator

Aggregator

Ein Aggregator ist eine Transformation, bei der jedes Eingabeelement an mindestens einem Ausgabeelement beteiligt ist und sich die Eingabe so in disjunkte Partitionen teilen lässt, dass jede Partition genau für ein Ausgabeelement verantwortlich ist. Jedes Element der Ausgabe lässt sich so eindeutig einer Gruppe von Eingabeelementen zuordnen. Die Lineage eines bestimmten Ausgabeelements ak entspricht seiner Eingabepartition:

T'(ak,E) = Ek

Eine spezielles Beispiel von Aggregatoren sind schlüsselerhaltende Aggregatoren, bei denen nur Eingabeelemente mit einem übereinstimmenden Schlüsselattribut das gleiche Ausgabeelement erzeugen, in dem der gleiche Schlüssel vorkommt.

Eine weitere Klasse von Aggregatoren sind kontextfreie Aggregatoren, bei denen die Ausgabe eines Eingabeelements unabhängig von den anderen Eingabeelementen derselben Partition ist.

Eine Transformation, die alle Eingabeobjekte auf sich selber abbildet (Identität) oder jedes Eingabeelement eine einfachen Berechnung unterwirft (z.B. Formatumwandlung) ist gleichzeitig Dispatcher und Aggregator und wird auch als Filter bezeichnet.

Berechnung der Data-Lineage

Die Data-Lineage einer gegebenen Ausgabe lässt sich bei bekannter Eigenschaft der Transformation mit einer Tracing-Prozedur bestimmen.

  • Für Dispatcher wird jedes Element der Eingabe geprüft, ob es die Ausgabe erzeugt und in diesem Fall zur Data-Lineage hinzugefügt.
  • Für kontextfreie Aggregatoren werden zunächst die Partitionen gebildet und dann diejenige gewählt, die zur Ausgabe führt. Die Partionen werden ermittelt indem die Eingabeelemente sukzessive zu bereits vorhandenen Partitionen hinzugefügt werden, falls dabei die Größe der Ausgabe gleich einem Element bleibt.
  • Für schlüsselerhaltende Aggregatoren werden die Schlüssel der Eingabeelemente überprüft.
  • Für Filter entspricht die Data-Lineage der Ausgabe

Für allgemeine Aggregatoren oder Black Boxes ist der Aufwand für ein Tracing zu groß, da Potenzmengen der Eingabeelemente gebildet werden müssten. Deshalb muss zur effektiven Ermittlung der Data-Lineage einer Transformation entweder eine explizite Tracingprozedur bekannt. Die Inverse Funktion einer Transformation ist nur bei Aggregatoren als Tracingprozedur nutzbar, da sie nicht unbedingt eindeutig ist.

Um für eine ganze Kette von Transformationen die Data-Lineage zu bestimmen ohne alle Zwischenergebnisse speichern zu müssen, werden die Transformationen normalisiert, indem man einige von ihnen zusammenfasst, ohne dass die speziellen Eigenschaften (Aggregator, Dispatcher, Filter...) verloren gehen, so dass ein effektives Tracing möglich ist. Die Bestimmung der optimalen Sequenz für das Tracing einer hintereinander geschalteten Reihe von Transformationen hängt auch von dem jeweiligen Kostenmodell ab.

Literatur

  • Yingwei Cui, Jennifer Widom. Lineage Tracing for General Data Warehouse Transformations. In: Proceedings of the 27th International Conference on Very Large Data Bases (VLDB'01). 2001.

Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Data-Lineage — bzw. Datenherkunft (auch Data Provenance oder Data Pedigree, deutsch auch Datenabstammung und stammbaum) bezeichnet in einem Data Warehouse System (Datenlager) die Fragestellung, zu gegebenen aggregierten Datensätzen die ursprünglichen Datensätze …   Deutsch Wikipedia

  • Data mapping — Data transformation/Source transformation Concepts metadata · data mapping data transformation · model transf …   Wikipedia

  • Data integrity — in its broadest meaning refers to the trustworthiness of system resources over their entire life cycle. In more analytic terms, it is the representational faithfulness of information to the true state of the object that the information represents …   Wikipedia

  • Lineage (evolution) — An evolutionary lineage is a sequence of species, that form a line of descent, each new species the direct result of speciation from an immediate ancestral species. [The University of California, Berkeley resource on understanding evolution… …   Wikipedia

  • Data cleansing — Not to be confused with Sanitization (classified information). Data cleansing, data cleaning, or data scrubbing is the process of detecting and correcting (or removing) corrupt or inaccurate records from a record set, table, or database. Used… …   Wikipedia

  • Tree (data structure) — A simple unordered tree; in this diagram, the node labeled 7 has two children, labeled 2 and 6, and one parent, labeled 2. The root node, at the top, has no parent. In computer science, a tree is a widely used data structure that emulates a… …   Wikipedia

  • Association of Religion Data Archives — The Association of Religion Data Archives (ARDA) is a free source of online information related to American and international religion. Founded as the American Religion Data Archive in 1997, and online since 1998, the archive was initially… …   Wikipedia

  • Jefferson DNA data — was taken from living male claimed descendants of Jefferson and Hemings. [cite journal|last = Foster | first = EA |coauthors = Jobling MA, Taylor PG, Donnelly P, de Knijff P,Mieremet R, Zerjal T, Tyler Smith C | year = 1998 | title = Jefferson… …   Wikipedia

  • Dataspaces — are an abstraction in data management that aim to overcome some of the problems encountered in data integration system. The aim is to reduce the effort required to set up a data integration system by relying on existing matching and mapping… …   Wikipedia

  • Datenintegration — Unter Informationsintegration versteht man das Zusammenführen von Informationen aus verschiedenen Datenbeständen (Datenquellen) mit in der Regel unterschiedlichen Datenstrukturen in eine gemeinsame einheitliche Datenstruktur. Dabei sollen vor… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”