Relationale Datenbanksysteme als hocheffiziente XQuery-Prozessoren: Compilationstechniken und Laufzeitsysteme
Final Report Abstract
Seit den 1970er Jahren wurden die Interna relationaler Datenbanksysteme konzipiert, implementiert und immer weiter optimiert, um Daten in strikter Tabellenform - dem sogenannten relationalen Datenmodell - effizient zu verarbeiten. Dieses Forschungsprojekt hat das Ziel, diese ausgefeilte und etablierte Datenbanktechnologie zu nutzen, um auch nicht-tabellarische Daten zu speichern, anzufragen und zu transformieren. Im Fokus steht hier vor allem das hierarische XML-Datenmodell, dessen Daten eine baumartige Struktur aufweisen. Die Familie der XML-Standards definiert nicht durch das Datenmodell, sondern auch assoziierte Sprachen (XPath und XQuery), die Baumstrukturen traversieren und neu konstruieren können. XML bildet zwar das Rückgrat des modernen Web und geniesst damit unter den hierarchischen Datenmodellen eine Ausnahmestellung - die in diesem Projekt gewonnenen Einsichten lassen sich aber unmittelbar auf weitere Baumdatenstrukturen, etwa die JavaScript Object Notation (JSON), anwenden. Wir verwandelt man relationale Datenbanksysteme in effiziente und skalierbare Baumprozessoren? 1. Die Arbeitspakete dieses Projektes haben Abbildungen untersucht, die Baumstrukturen in tabellarischer Form codieren. Wichtig war dabei, die relevanten Eigenschaften der Bäume (Typen und Inhalte der Knoten, Ordnung der Knoten untereinander, . . . ) getreu abzubilden. Effiziente Umkehrabbildungen, die aus den Tabellendaten wieder die originalen Bäume rekonstruieren können (Serialisierung), wurden ebenfalls entwickelt. 2. Wir haben Baumcodierungen gefunden, die einem relationalen Datenbanksystem die effiziente Auswertung von Baumtraversierung, -transformation und -konstruktion (in XPath und XQuery) ermöglichen. Es entstand der Compiler Pathfinder, der XQuery-Programme in äquivalente relationale Anfragen (sowohl algebraisch als auch in SQL formuliert) übersetzt. Auf diesem Fundament hat dieses Projekt unter anderem Verfahren zur effizienten Verarbeitung geordneter Datenstrukturen, Optimierung sehr grosser Anfragen, Updates auf Baumcodierungen, Validierung von XML-Daten, Debugging von XQuery, rekursiven Baumanfragen und der effizienten Konstruktion von Bäumen entwickelt. Charakteristisch für unseren Ansatz ist, dass die Interna des zugrundeliegenden relationalen Systems für seinen Einsatz als Baumprozessor nicht geändert werden müssen. Das hat zur unmittelbaren Anwendbarkeit und einer weiten Verbreitung unserer Techniken geführt. Unsere Systeme, Algorithmen und Verfahren (etwa Pathfinder, das relationale XML-Datenbanksystem MonetDB/XQuery, die pre/post-Ebene, Staircase Join oder Loop Lifting) sind im Feld der datenbankgestützten Verarbeitung von Baumstrukturen bis heute viel zitiert, oft adaptiert und weiterentwickelt worden - auch in kommerziellen Kontexten. Besonders die in Pathfinder eingesetzten Übersetzungstechniken - unter anderem das Loop Lifting - führten zu generellen Einsichten in die Compilation (funktionaler) Programmiersprachen, die auch jenseits von XML und XQuery einsetzbar sind. Dies führte letztendlich zum DFG-geförderten Projekt Ferry, in dem Datenbanksysteme in skalierbare Laufzeitsysteme für Programmiersprachen verwandelt werden.
Publications
- Why Off-The-Shelf RDBMSs are Better at XPath Than You Might Expect. In Proc. of the ACM SIGMOD Int’l Conference on Management of Data, Beijing, China, 2007
T. Grust, J. Rittinger, and J. Teubner
- MonetDB/XQuery: A Fast XQuery Processor Powered by a Relational Engine. In Proc. of the ACM SIGMOD Int’l Conference on Management of Data, Chicago, USA, 2006
P. Boncz, T. Grust, M. van Keulen, S. Manegold, J. Rittinger, and J. Teubner
- XQuery Off the Relational Shelf. Bulletin of the IEEE Technical Commitee on Data Engineering, Special Issue on XQuery Processing: Practice and Experience, 31(4), 2008
T. Grust, J. Rittinger, and J. Teubner
- Ferry: Database-Supported Program Execution. In Proc. of the ACM SIGMOD Int’l Conference on Management of Data (SIGMOD), Providence, USA, 2009
T. Grust, M. Mayr, J. Rittinger, and T. Schreiber
- XQuery Join Graph Isolation. In Proc. of the Int’l Conference on Data Engineering (ICDE), Shanghai, China, 2009
T. Grust, M. Mayr, and J. Rittinger
- Let SQL Drive the XQuery Workhorse. In Proc. of the Int’l Conference on Extending Database Technology (EDBT), Lausanne, Switzerland, 2010
T. Grust, M. Mayr, and J. Rittinger
