Viele Anwendungsgebiete, wie zum Beispiel Wissenschaftliche Berechnungen, Data-Warehousing und Datenintegration, benötigen detaillierte Informationen über die Herkunft von Daten. Solche Informationen werden oft als Data Provenance bezeichnet. Die Herkunft eines so genannten Datenelements, beinhaltet Informationen über die Eingabedaten von denen das Datenelement abgeleitet wurde und die Transformationen die zu seiner Entstehung und aktuellen Darstellung beigetragen haben. Provenance für relationale Datenbanken ist sowohl theoretisch als auch in algorithmischer Hinsicht untersucht worden. Trotz der Fortschritte auf diesem Gebiet, muss ein Mangel an praktisch einsetzbaren Systemen konstatiert werden, die die Erzeugung und Speicherung von Provenance und Anfragen über solche Informationen unterst ützen (Im Folgenden bezeichnen wir solche Systeme als Provenance Management Systeme oder kurz PMS). Herkömmliche Systeme unterstützen nur Teilmengen der Sprachkonstrukte von SQL, was eine erhebliche Einschränkung der Praxis-Tauglichkeit dieser Systeme darstellt, da die meisten Anwendungsgebiete, die von Provenance Funktionalität profitieren, komplexe Anfragefunktionalität benötigen. Dazu gehören zum Beispiel geschachtelte Unter-Anfragen, Aggregation und vom Benutzer definierte Funktionen. Ein PMS, das diese Sprachkonstrukte nicht unterstützt, ist nur von sehr eingeschränktem Nutzen. Die meisten Ansätze benutzen unterschiedliche Datenmodelle zur Repräsentation von Provenance Informationen und der Daten für die Provenance berechnet wurde (normale Daten). Dies hat den unvermeidbaren Nachteil, das eine neue Anfragesprache entwickelt werden muss, um Provenance Daten abfragen zu können. Es ist nicht verwunderlich, das die Mächtigkeit und Reife solcher Sprachen nicht an die einer langzeitig entwickelten Anfragesprache wie SQL heranreicht. In dieser Dissertation stellen wir das innovative PMS Perm vor, das die oben genannten Nachteile von herkömmlichen Systemen behebt. Die dem Ansatz zugrundeliegende Idee ist es, Provenance Informationen als normale Relationen darzustellen, die mit Hilfe von Standard SQL Anfragen generiert und angefragt werden; ”Benutze SQL um die Provenance von SQL Anfragen zu berechnen und anzufragen”. Perm wurde basierend auf PostgreSQL umgesetzt und erweitert den SQL Dialekt dieses Systems mit neue Sprachkonstrukten für die Berechnung von Provenance. Diese Sprachkonstrukte sind intern als Anfragetransformationen (query rewrites) realisiert. Dieser Ansatz ermöglicht es Perm von dem fortschrittlichen Anfrageoptimierer von PostgreSQL zu profitieren und ermöglicht den Einsatz von SQL als Anfragesprache für Provenance Informationen. Die Umsetzung unserer Vision eines ”rein relationalen” PMS erfolgte in mehreren Schritten. Zunächst war die Entwicklung von neuen Provenance Definitionen notwendig, um SQL Konstrukte zu unterstützen, die von den Standard Provenance Definitionen nicht behandelt werden. Basierend auf diesen Definitionen haben wir Anfragetransformationen entwickelt, die eine Anfrage q in eine Anfrage überführen, die die Provenance von q berechnet. Diese Anfragetransformationen sind beweisbar korrekt und vollständig. Die Implementierung von Perm baut auf diesem soliden theoretischen Hintergrund auf. In der Implementierung werden neuartige Optimierungstechniken eingesetzt, um die Effizienz der inhärent aufwändigen Provenance Berechnung zu steigern. Der erfolgreiche Einsatz von Perm zur Fehlerdiagnose für Datenintegration - einem weit verbreiteten Einsatzgebiet von Provenance - und umfangreichen Experimente zur Analyse der Effizienz der Provenance Berechnung in Perm belegen die Vorteile unseres Systems gegenüber alternativen Ansätzen.

University of Zurich, Department of Informatics

dbtg