A Better SQL in 11 Lines of Code

Prela is a novel query language crafted at UCLA RePL that diverges significantly from SQL. Despite its distinct nature, Prela's fundamental concepts are straightforward. This tutorial aims to construct a basic version of Prela using Python to grasp its core principles. By the tutorial's conclusion, you'll comprehend how the following query operates: it identifies all movies produced by American companies, features a character's name in their title, and outputs the title alongside the alias for each cast member. Remarkably, the equivalent SQL query spans over 20 lines.

One of Prela's unique features is its reliance on binary relations—tables with precisely two columns. Though this may seem restrictive initially, it's easy to transform a wide table with multiple columns into binary relations. Consider a table containing movie data—by dividing it into three binary relations, each linking the row number to the corresponding column value, we can represent the ID, title, and year columns of the original table.

A key motivation behind Prela's focus on binary relations is their ability to generalize functions. Functions are powerful because they compose, serving as the building blocks of programs. Functions map every input to a unique output, whereas binary relations can link an input to multiple outputs. In essence, binary relations can be seen as nondeterministic functions, and they compose similarly to how functions do.

Now, let's delve into an example. For simplicity, we'll concentrate on relations that map every input to exactly one output, essentially treating them as functions. Turning a relation into a dictionary and looking up a value constitutes calling a relation. With this understanding, we're prepared to introduce Prela's most crucial operator: relation composition.

Function composition involves applying one function first, followed by applying another function to the output. The composition of two relations, r and s, yields a new relation that first maps x with r to obtain y, then maps y with s for the final output. Implementing this involves converting s into a dictionary, iterating over the (x, y) pairs in r, and then outputting (x, d[y]) if y is found in d.

Using our movie example, the query below composes movie with title to generate a relation mapping each movie ID to its title. Experiment by substituting title with year to observe the result. The true power of composition becomes evident when chaining multiple .select calls. Suppose we introduce a foreign key column linking each movie to its production company, and another table for movie companies.

We can then find the country of a movie's production company through a series of .select calls, abbreviated using .s. Prela automatically inserts the necessary step to resolve an ID to a row, allowing us to write, for instance, movie.s(company).s(country), which mirrors the behavior seen in cast.s(person).s(alias).s(text) in the initial snippet.

Thus far, every query has produced a single column of values. To select multiple attributes, we introduce the & operator. While .select matches the second column of r against the first column of s, & joins r and s on the first column of both, subsequently pairing up their second columns. Consequently, title & year maps each movie row to both of its attributes simultaneously.

The result remains a binary relation, with & merely nesting the values within a tuple. This enables us to continue composing it like any other relation, facilitating the retrieval of multiple columns.

Next, we require a means to specify which rows we desire. The predicate .eq(v) filters a relation, retaining only the pairs whose second column equals v. On its own, .eq narrows the relation it is applied to. The query below still maps movie rows to countries but excludes certain entries. Lastly, the restriction operator .where takes a predicate like .eq and filters another relation with it.

Applying our predicate to .where transforms it into a filter on movies: This reads directly from the code: movies where the company's country is [us]. The query has grown lengthy, so let's refactor it. Interestingly, a CTE (Common Table Expression) has been created using a plain Python variable, which is possible because Prela queries consist of operators, and each subexpression constitutes a valid query.

Conditions can be combined using & since it doubles as a logical conjunction when nested within .where. The query now identifies Casablanca, an American film released in 1942. Putting it all together, .select fetches the desired columns for the movies that passed the filter. We can even move the predicate into the select clause for a more concise query.

Lastly, Prela supports grouping and aggregation, along with other common operators. A comprehensive language documentation is in development, so refer to our paper for further details. As an exercise, attempt to define the required relations so that the snippet at the top executes successfully. A self-contained Python program for our toy Prela is available here.

This technique is known as 6NF decomposition. For those concerned about potential overheads, Prela compiles away the indirection using CPS (Continuation-Passing Style), which you can explore in this post.