A Deep Embedding of Queries into Ruby

DSpace Repository


Dateien:

URI: http://nbn-resolving.de/urn:nbn:de:bsz:21-opus-69305
http://hdl.handle.net/10900/49911
Dokumentart: Dissertation
Date: 2013
Language: English
Faculty: 7 Mathematisch-Naturwissenschaftliche Fakultät
Department: Informatik
Advisor: Grust, Torsten (Prof. Dr.)
Day of Oral Examination: 2013-07-05
DDC Classifikation: 004 - Data processing and computer science
Keywords: Programmiersprache , Datenbank , Algebra , Typsystem , SQL
Other Keywords: Ruby , Datenbanksysteme , Relationale Algebra , Loop Lifting , Typ-System , Dynamische Typisierung
Database system , Relational algebra , Intersection types , Subtyping , Coercion , Dynamic typing
License: Publishing license including print on demand
Order a printed copy: Print-on-Demand
Show full item record

Inhaltszusammenfassung:

Relationale Datenbanksysteme und Programmiersprachen sind von un- terschiedlichen Paradigmen geprägt. Datenbanksysteme beschränken sich noch immer auf die Verarbeitung flacher Tabellen (ein Modell, das sich insbesondere für große Datenmengen bewährt hat). Dem gegenüber unterstützen moderne Programmiersprachen eine Vielzahl von Hilfsmittel und Abstraktionsmöglichkeiten, die den Entwicklern die Datenmodellierung erheblich erleichtern. Unter diesen Hilfsmitteln finden sich beispielsweise geordnete und verschachtelte Datenstrukturen samt entsprechenden Operationen, um diese zu verarbeiten. Da Datenbanksysteme aus den meisten Webapplikationen nicht mehr wegzudenken sind, sind insbesondere Web-Entwickler dem ständigen Wechsel zwischen diesen beiden Paradigmen ausgesetzt. Die Kommunikation mit Datenbanksystemen macht es erforderlich, Anfragen in SQL zu formulieren, um auf persistente Informationen zurückzugreifen. Um die Informationen weiterzuverarbeiten, müssen diese in das Datenmodell der jeweiligen Gastsprache konvertiert werden. Es ist wenig überraschend, dass dieser Ansatz unweigerlich zu schwer wartbaren Programmen, sowie zu Performanzproblemen und sogar Sicherheitslücken führt. Das Problem ist einfach: Es ist mehr als doppelt so schwierig zwei Programmiersprachen zu benutzen als eine. (Cheney, Lindley und Wadler) Mit den Techniken, welche wir in dieser Arbeit vorstellen werden, rückt die Lösung dieses Problems in greifbare Nähe. Wir wenden uns dem auf der Programmiersprache Ruby basierenden Web-Framework Ruby on Rails (auch Rails genannt) zu. Dabei werden wir eine Reihe von Problemen aufzeigen, welche auf ActiveRecord, die Datenbankanbindung in Rails, zurückzuführen sind. Unsere Aufmerksamkeit gilt vor allem der großen Ähnlichkeit zwischen ActiveRecord und SQL, eine Ähnlichkeit, die es mitunter unmöglich macht, Ruby Idiome in der Formulierung von Datenbankanfragen zu verwenden: (1) Anfragen werden im Wesentlichen basierend auf einem sehr einfachen Konzept formuliert. SQL Fragmente werden in Ruby als Zeichenketten formuliert und dann durch entsprechende Methodenaufrufe direkt in eine der SQL Klauseln eingefügt. (2) Weder geordnete noch ver- schachtelte Datenstrukturen und deren Verarbeitung werden nicht unterstützt. (3) Zudem werden in der Regel SQL Anfragen in Abhängigkeit der Daten erzeugt, welche angefragt werden. Dies führt mitunter zu erheblichen Performanzproblemen. Mit Switch, einer nahtlosen Integration einer Anfragesprache in Ruby, verfolgen wir das Ziel, die Grenzen zwischen der Gastsprache und dem Datenbanksystem zu verwischen. Mit unserem Ansatz adressieren wir alle inActiveRecord auftretenden Probleme auf einen Streich: Mit Switch gibt es (1) weder einen stilistischen noch einen syntaktischen Unterschied zwischen Ruby Programmen, die auf Arrays im Hauptspeicher oder Tabellen in einer Datenbank operieren, (2) selbst wenn sich diese Programme auf Ordnung verlassen oder verschachtelte Datenstrukturen verwenden. (3) Der Übersetzungsmechanismus und der SQL Generator in Switch garantieren, dass nur wenige Anfragen erzeugt werden. Dies hilft uns dabei, die Performanzprobleme, welche mit ActiveRecord entstehen, zu mindern. In der vorliegenden Arbeit werden wir jene Schritte erläutern, die es ermöglichen, Ruby Ausdrücke in semantisch äquivalente SQL Anfragen zu übersetzen. Wir werden eine Reihe von sorgfältig ausgewählten Ruby Konstrukten und Idiomen identifizieren, deren Semantik sich auch im Datenbankkontext modellieren lässt. Ein Mechanismus, der uns den Zugriff auf die Syntaxbäume dieser Konstrukte erlaubt, ebnet dabei den Weg, auf etablierte Übersetzungstechniken aufzubauen. Aufbauend auf einer Übersetzungstechnik namens Loop Lifting werden aus den Ruby Ausdrücken Anfragepläne erzeugt. Diese Pläne bestehen vorwiegend aus Primitiven aus der klassischen Relationalen Algebra. Nur wenige Operatoren wurden hinzugefügt, um zum Beispiel geordnete Datenstrukturen korrekt im Kontext einer Datenbank abzubilden. Diese Vorgehensweise erlaubt es uns zudem auf eine bereits bestehende Infrastruktur zurückzugreifen, um die ungewöhnlichen Anfragepläne signifikant zu vereinfachen. Mit einem SQL Generator beenden wir unsere Reise durch die verschiedenen Etappen der Übersetzung. Der Generator verwandelt die Anfragepläne in Standard konforme SQL:1999 Anfragen, um von jenen Systemen zu profitieren, die für die Verarbeitung großer Datenmengen prädestiniert sind. Es sieht aus wie Ruby, ist aber so schnell wie handgeschriebenes SQL, ist das Ideal, welches die Entwicklung und Forschung rund um Switch antreibt.

Abstract:

The mismatch between relational database systems and programming languages is a long-standing problem in the community. Whereas database systems still operate on flat tables, modern programming languages support a garden variety of features, including ordered and nested data structures, as well as data abstraction. Particularly web developers suffer from this two-paradigms approach, because they must repeatedly undergo the mental shift from the host language to SQL (and vice versa) that enables them to communicate with the relational back-end. It does not come as a surprise that this approach inherently leads to unmaintainable code, performance issues, and even security holes such as SQL injection attacks. The problem is simple: two programming languages are more than twice as difficult to use as one language. (Cheney, Lindley, and Wadler) With the techniques we developed in this work, the solution to this problem is close at hand. We will turn our focus on Ruby on Rails (Rails, for short), a Ruby-based web-framework, and identify the key issues that trace back to Rails’s ActiveRecord database-binding. We will demonstrate that ActiveRecord’s query interface is little more than SQL in disguise: (1) Query construction relies on a simplistic, concatenative semantics, (2) order- and nesting-based programming is not supported, and (3) the number and size of generated queries directly depends on the queried data. Our efforts to provide a solution for the above problems assembled into Switch, a deep embedding of queries into Ruby and Ruby on Rails, which aims to blur the traditional lines between the host language and the relational database back-end. Our approach tackles all of the above issues at a single stroke: With Switch, there are (1) no syntactic or stylistic differences between Ruby programs that operate over in-memory array objects or database-resident tables, (2) even if these programs rely on array order and nesting. (3) Switch’s built-in compiler and SQL code generator guarantee to emit few queries, addressing performance issues that arise in ActiveRecord. This thesis details the steps necessary to take a Ruby expression all the way down to SQL. We will identify a sensible set of native Ruby constructs, yet feasible to be translated into a database-executable form. A mechanism that enables us to turn Ruby expressions into a runtime-accessible expres- sion tree paves way for a full-fledged compiler-backend. To take the Ruby expression towards a database-executable format, we directly expand on a compilation technique, called loop lifting. The query plans resulting from this technique primarly consist of primitives that resemble the operators of the classical relational algebra, enriched with ranking facilities to correctly reflect order. We take advantage of an existing optimization infrastructure designed to significantly simplify the unusual plan shapes stemming from the loop-lifted compilation. With the SQL:1999 code generator we conclude our journey through the different stages of our compiler. The code generator turns intermediate algebraic plans into strictly standard-compliant SQL:1999 queries and lets them take advantage of one of the most capable systems for processing large- scale data available today. Looks like Ruby, but performs like handcrafted SQL, is the ideal that drove the research and development effort behind Switch.

This item appears in the following Collection(s)