• Tanja Auge
• Florian Rose
• Andreas Görres
• Andreas Heuer

• Konzeption einer eigenen theoretischen Lösung
• Weiterentwicklung des Prototyps ChaTEAU

• Bachelor: Vorlesungen:
  • Datenbanken I
  • Datenbanken II
  • Data Science oder Informationssysteme und Dienste
  • KSWS oder Projekt
• Master:
  • Grundlagen der Datenbankforschung
  • Theorie relationaler Datenbanken
  • NEidI

Der CHASE ist eine Basistechnik in der Datenbanktheorie. (1) Möchte man k heterogene Datenbanken integrieren, so kann man mit dem CHASE den integrierten Datenbestand aus Korrespondenzen zwischen den k Datenbanken berechnen. (2) Möchte man eine Anfrage (etwa aus Datenschutzgründen) in eine andere Anfrage umformen, die nur über erlaubte Sichten auf einen Datenbestand zugreift, so kann man mit dem CHASE die Informationen über die verfügbaren Sichten in die Anfrage einbauen. (3) Möchte man eine Anfrage unter Integritätsbedingungen optimieren, so kann man die Integritätsbedingungen mit Hilfe des CHASE in eine Anfrage einarbeiten. (4) Möchte man die Herkunft von Daten bei einer wissenschaftlichen Auswertung bestimmen (Provenance), so muss eine inverse Abbildung zur gegebenen Auswertung berechnet werden: auch hier gibt es diverse auf dem CHASE basierende Invertierungstechniken. Wendet man den CHASE für die Fälle (2) bis (4) an, so wird dem CHASE noch ein zweiter BACKCHASE-Prozess hinzugefügt, der die Ermittlung der gesuchten Ergebnisanfrage erst ermöglicht.

Ziel von ChaTEAU ist es, die verschiedenen CHASE-Anwendungsfälle in einem Tool zu vereinen. Die Idee dahinter basiert auf der Tatsache, dass die CHASE-Objekte O und Parameter ⋆ im Wesentlichen austauschbar sind, ohne die Art und Weise, wie der CHASE ausgeführt wird, wesentlich zu verändern. Denn: Für ein Objekt O (z.B. eine Datenbank, oder eine Abfrage) und eine Menge von Abhängigkeiten ⋆ (z.B. eine Menge von FDs und JDs) nimmt CHASE ⋆ in O auf, so dass ⋆ implizit in O enthalten ist. 

ChaTEAU ist derzeit für die Anwendungen (1) und (3) entwickelt und implementiert. ChaTEAU beinhaltet zudem einige Techniken, die die Terminierung und Konfluenz des CHASE vor dem Start des Verfahrens sicherstellen. Die Erweiterung um die Fälle (2) und (4) steht aktuell noch aus. Hierfür sind zunächst einige Vorüberlegungen nötig:

• Kann der BACKCHASE ebenso wie der CHASE zu einem Verfahren verallgemeinert werden?
• Erweiterung von ChaTEAU um das Konzept von Data Provenance?
• Erweiterung von ChaTEAU um eine BACKCHASE-Phase für
  1. Anfragen auf Views
  2. Rekonstruktion der Originalinstanz
  3. Optimierung
• Entwicklung einer Nutzerschnittstelle durch
  1. Implementierung einer geeigneten Nutzeroberfläche
  2. Anbindung einer postgresSQL- oder mySQL-Datenbank

Für das Jahr 2021 werden konkret folgende drei Teilthemen ausgeschrieben:

• Nutzung von ChaTEAU für das Answering-Queries-using-Views-Problem (AQuV)
  Hier soll ein Modul konzipiert und entwickelt werden, das den CHASE von ChaTEAU für das o.a. Szenario (2) nutzt. In diesem Fall muss in der CHASE-Phase eine Menge von Sichten (CHASE-Parameter) in eine Anfrage (CHASE-Objekt) eingearbeitet werden. Die Sichten werden dabei in Form von st-tgds definiert.
  
  Innerhalb einer zweiten BACKCHASE-Phase muss ChaTEAU nun auch für die generierte, auf Sichten beschränkte Anfrage (dem sogenannten universellen Plan) als CHASE-Objekt angewendet werden. Die CHASE-Parameter sind nun inverse Sichtdefinitionen, quasi ts-tgds. Um die BACKCHASE-Phase effizienter zu gestalten, kann die BACKCHASE-Phase um Pruning oder why-Provenance-Informationen ergänzt werden.
  
  Als Funktionsumfang sind die im Artikel von Deutsch und Hull aufgeführten Beispiele beziehungsweise die in der letzten Übung der Master-Vorlesung GDBF vorgestellten Beispiele zu implementieren.
   
• Nutzung von ChaTEAU für die semantische Anfrageoptimierung 
  Hier soll ein Modul konzipiert und entwickelt werden, das den CHASE von ChaTEAU für das klassische Szenario (3) der semantischen Anfrageoptimierung nutzt.  In diesem Fall müssen in der CHASE-Phase die vorliegenden Integritätsbedingungen als CHASE-Parameter in eine Anfrage als CHASE-Objekt eingearbeitet werden. Für diese Phase ist ChaTEAU bereits durch studentische Vorarbeiten gerüstet. Es fehlt dann noch die BACKCHASE-Phase, in der aus der um Integritätsbedingungen angereicherten Anfrage eine minimale Anfrage erzeugt wird, die im Anschluss dann in eine klassische Anfragesprache (SQL, Relationenalgebra mit Erweiterungen oder Datalog) rückübersetzt wird. Um diese BACKCHASE-Phase effizient zu gestalten, kann man bekannte Techniken aus der Forschung wie Graphen (Ansatz Meier, Freiburg), Provenance-Informationen (Ansatz Ileana, Paris) oder erweiterte Tableaus (Ansatz Terei, Clausthal und Bruder, Rostock) nutzen.
  
  Als Funktionsumfang sind die in der entstehenden Dissertation von Ilvio Bruder oder die in dem letzten Kapitel der Master-Vorlesung GDBF vorgestellten Benchmark-Anfragen umzusetzen.
   
• Erweiterung von ChaTEAU um Second-Order-TGDs
  In dieser Arbeit sollen die CHASE-Parameter von ChaTEAU um Second-Order-TGDs (so-tgds) erweitert werden. Die bisher implementierten egds, tgds und st-tgds ermöglichen eine Darstellung von Integritätsbedingungen und Schema-Abbildungen, letztere können auch als Datenbanktransformationen oder klassische Datenbankanfragen (die wir im Szenario des Forschungsdatenmanagements Auswertungsanfragen nennen) genutzt werden. Im Forschungsprototypen ProSA, der für Provenance-Anfragen why und how eine minimale Forschungsdatenbank berechnen soll, die zur Replizierbarkeit des Auswertungsergebnisses gesichert werden muss, sollen allerdings die Provenance-Prozesse mit Evolutionen der Datenbankstrukturen und Datenbankinhalte kombiniert werden. Leider müssen dazu diverse Anfragen, also Schemaabbildungen und damit st-tgds, invertiert und hintereinandergeschaltet werden. Nach Ergebnissen von Fagin ist diese Hintereinanderschaltung im allgemeinen Fall dann nicht mehr mit st-tgds darstellbar. Man muss dazu auf prädikatenlogische Ausdrücke zweiter Ordnung (second order) ausweichen, die u.a. globale Funktionen erlauben, die prädikatübergreifend quantifiziert werden, sowie Gleichheitsprädikate einführen. 
  
  Als Funktionsumfang sollen mindestens die in der Masterarbeit von Florian Rose konzipierten Techniken zur Kombination von Evolution und Provenance umgesetzt werden. Dabei können Funktionen etwa auch zusätzlich gespeichert werden, etwa in Form von „side-tables“. 

• Einarbeitung in das Gebiet/ Literaturrecherche:
  • Grundlagen des CHASE, BACKCHASE, Provenance, …
  • Einarbeitung in ChaTEAU
• Entwicklung eines eigenen Konzepts
• (Prototypische) Implementierung in ChaTEAU

• Java
• Provenance-Tools: PERM, ProvSQL (abhängig vom Thema)
• Chase-Tools: Graal, Llunatic, PDQ, ChaseTEQ (abhängig vom Thema)

• Bisherige Abschlussarbeiten:
  • Tanja Auge: Umsetzung von Provenance-Anfragen in Big-Data-Analytics-Umgebungen.
    Masterarbeit, Universität Rostock, Institut für Informatik, 2017
  • Martin Jurklies: CHASE und BACKCHASE: Entwicklung eines Universal-Werkzeugs für eine Basistechnik der Datenbankforschung.
    Masterarbeit, Universität Rostock, Institut für Informatik, 2018
  • Fabian Renn: Erweiterung des CHASE-Werkzeugs ChaTEAU um Anfragetrans-formationen.
    Bachelorarbeit, Universität Rostock, Institut für Informatik, 2019
  • Jakob Zimmer: Vereinheitlichung des CHASE auf Instanzen und Anfragen am Beispiel ChaTEAU.
    Bachelorarbeit, Universität Rostock, Institut für Informatik, 2020
  • Andreas Görres: Erweiterung des CHASE-Werkzeugs ChaTEAU um ein Terminierungskriterium.
    Masterarbeit, Universität Rostock, Institut für Informatik, 2020
  • Florian Rose: Erweiterung des CHASE-Werkzeugs ChaTEAU um eine BACKCHASE-Phase.
    Masterarbeit, Universität Rostock, Institut für Informatik, 2020
  • Nico Trebbin: Nutzung von ChaTEAU für das Answering-Queries-using-Views-Problem (AQuV).
    Bachelorarbeit, Universität Rostock, Institut für Informatik, 2022
• Dokumentationen aus den Projektveranstaltungen KSWS und NEidI aus dem Jahren 2016-2019
• Konferenz- und Journalpaper:
  • M. Benedikt, G. Konstantinidis, G. Mecca, B. Motik, P. Papotti, D. Santoro, E. Tsamoura: Benchmarking the Chase.
    In: PODS 2017, pp. 37-52, 2017
  • S. Greco, C. Molinaro, F. Spezzano: Incomplete Data and Data Dependencies in Relational Databases.
    Morgan & Claypool Publishers, 2012
  • R. Fagin, P. G. Kolaitis, R. J. Miller, L. Popa: Data exchange: semantics and query answering.
    In: Theor. Comput. Sci., Vol. 336 No. 1, pp. 89-124, 2005
  • A. Deutsch, V. Tannen: XML queries and constraints, containment and refor-mulation.
    In: Theor. Comput. Sci., Vol. 336, No. 1, pp. 57-87, 2005
  • B. Glavic: A Primer on Database Provenance.
    Technischer Bericht, Illinois Institute of Technology, 2014
  • J. Cheney, L. Chiticariu, W.-C. Tan: Provenance in Databases: Why, How, and Where.
    In: Foundations and Trends in Databases, 1(4), pp.379-474, 2009
  • A. Doan, A. Y. Halevy, Z. G. Ives: Principles of Data Integration.
    Morgan Kaufmann, 2012
  • R. Fagin, P. G. Kolaitis, L. Popa, W. C. Tan: Schema mapping evolution through composition and inversion.
    In: Schema Matching and Mapping, Springer, pp. 191–222, 2011
  • A. Deutsch, V. Tannen: XML queries and constraints, containment and reformulation.
    In: Theor. Comput. Sci., Vol. 336, No. 1, pp. 57-87, 2005
  • T. Auge, A. Heuer: ProSA --- Using the CHASE for Provenance Management.
    In: ADBIS, Lecture Notes in Computer Science, Vol. 11695, Springer, pp. 357-372, 2019
  • A. Deutsch, R. Hull: Provenance-Directed Chase&Backchase.
    In: In Search of Elegance in the Theory and Practice of Computation, Lecture Notes in Computer Science, Vol. 8000, Springer, pp. 227-236, 2020