Neue Übersetzungs- und Ausführungstechniken für datenintensive Programme

• Antragsteller: Professor Dr. Torsten Grust
• Fachliche Zuordnung: Sicherheit und Verlässlichkeit, Betriebs-, Kommunikations- und verteilte Systeme
• Förderung: Förderung von 2010 bis 2015
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 161858209

• Erstellungsjahr: 2016

Zusammenfassung der Projektergebnisse

Programmier- und Datenbankanfragesprachen haben sich in den zurückliegenden vier Jahrzehnten im Wesentlichen getrennt voneinander entwickelt. Es entstand eine Lücke (impedance mismatch) in Syntax und Semantik, die es sehr erschwert, beide Welten in einem System zusammenzubringen. Das ist vor allem deshalb unglücklich, weil sich in modernen Programmier- und Skriptsprachen oft Teilsprachen identifizieren lassen - meist in Form einer Familie von Konstrukten oder Funktionen über Arrays, Listen oder anderen Containern - die sich mittels datenbank-basierter Verfahren effizienter und auf grösseren Datenmengen auswerten liessen, als es die Laufzeitsysteme der Programmiersprachen derzeit selbst vermögen. Dieses Projekt verfolgte daher als Ziel, diese Lücke zu überwinden und Datenbanksysteme als effiziente und skalierbare Co-Prozessoren für die Auswertung von daten-intensiven Programmen einzusetzen: Programmfragmente werden in Datenbankanfragen- etwa SQL - übersetzt und zur Auswertung an das Datenbanksystem übergeben. Die Ausführung dort kann sich auf etablierte Anfrageoptimierer, Datenlayouts und Indexstrukturen stützen, bevor das (oft kleine) Anfragergebnis der Programmiersprache zur weiteren Verarbeitung übergeben wird. Der Erfolg dieses Modells beruht auf einer engen Interaktion der vormals separierten Welten. Unter anderem waren 1. Techniken zu entwickeln, die eine nahtlose syntaktische Einbettung von Anfragen in die Gastprogrammiersprache ermöglichen und sich idealerweise nur auf bereits existierende (idiomatische, wohlbekannte) Konstrukte der Gastsprache stützen, 2. Übersetzungsverfahren für ausdrucksstarke Teilsprachen zu finden, die die Auswertung von möglichst großen Programmfragmenten durch das Datenbanksystem - und damit in der direkten Nähe der Daten selbst - erlauben, 3. Datenbankrepräsentationen für die Werte der Gastsprache anzugeben, die auch Aspekte wie Ordnung und tiefe Schachteltung respektieren, und 4. Brücken zwischen den Ausführungsmodellen von Gastsprache und Datenbanksystem (iterativ vs. mengenorientiert) zu schlagen. Dieses Projekt adressierte all diese Herausforderungen und baute dabei oft auf Verfahren, die in einer Welt erfolgreich etabliert, in der anderen bisher aber unbekannt waren oder noch keinen Einsatz finden konnten. Wir adaptierten beispielsweise die Ideen des Flattening (in der Welt der datenparallelen Programmierung bekannt seit Beginn der 90er Jahre) und entwickelten daraus eine neue Übersetzungsstrategie für sehr ausdrucksstarke Anfragesprachen über reichen Datenstrukturen, die sich am vektorbasierten Ausführungsmodell moderner Datenbanksysteme orientiert. Im Laufe des Projektes entwickelte sich die Identifikation derartiger Verfahren, ihrer Übertragung in und Adaption für die jeweilige Gegenseite geradezu zu einem Leitmotiv. Es zeigte sich ein Potential für eine ganze Reihe von vielversprechender Anschlussarbeiten im Grenzbereich zwischen Programmiersprachen und Datenbanksystemen, deren Verfolgung die DFG im Projekt ALIEN seit 2016 im Rahmen einer Sachbeihilfe fördert.

Projektbezogene Publikationen (Auswahl)

• Avalanche-Safe LINQ Compilation. In Proc. of the VLDB Endowment, volume 3, Singapore, 2010
  T. Grust, J. Rittinger, and T. Schreiber
  
• Bringing Back Monad Comprehensions. In Proc. of the ACM SIGPLAN Haskell Symposium, Tokyo, Japan, 2011
  G. Giorgdize, T. Grust, N. Schweinsberg, and J. Weijers
  
• Haskell Boards the Ferry: Database-Supported Program Execution for Haskell. In Selected Papers of the Int’l Symposium on Implementation and Application of Functional Languages (IFL), Alphen ann den Rijn, Netherlands, 2011. Best Paper Award (Peter Landin Prize 2011)
  G. Giorgidze, T. Grust, T. Schreiber, and J. Weijers
  
• A Deep Embedding of Queries into Ruby. In Proc. of the Int’l Conference on Data Engineering (ICDE), Washington (DC), USA, 2012
  T. Grust and M. Mayr
  
• First-Class Functions for First-Order Database Engines. In Proc. of the 14th International Symposium on Database Programming Languages (DBPL), Riva del Garda, Italy, 2013
  T. Grust and A. Ulrich
  
• Observing SQL Queries in their Natural Habitat. ACM Transactions on Database Systems (TODS), 38(1), 2013
  T. Grust and J. Rittinger