A Better SQL in 11 Lines of Code

Prela is a new query language being developed at UCLA RePL. The language is quite different from SQL, but its key ideas are very simple. In this short tutorial, we will build a toy version of Prela in Python to understand its core principles. By the end of this tutorial, you will know how the following query works:

movie.where(company.s(country).eq("[us]") &
            keyword.eq("character-name-in-title"))
    .select(title & cast.s(person).s(alias).s(text))

You can probably already guess what it's doing: the query finds every movie produced by an American company and has a character name in its title, and outputs the title along with the alias for each cast member. Note that the equivalent query in SQL spans over 20 lines.

The first special thing about Prela is that there are only binary relations, i.e., tables with two columns. That may sound very limiting at first, but it's easy to "binarize" a wide table with multiple columns. Suppose we have a table of movies:

We can decompose the 3-column table into 3 binary relations,¹ each mapping the row number to the column value:

movie = Rel([(646, 0),
             (478, 1),
             (583, 2)])

title = Rel([(0, "The Godfather"),
             (1, "Seven Samurai"),
             (2, "Casablanca")])

year  = Rel([(0, 1972),
             (1, 1954),
             (2, 1942)])

The movie, title, and year relations above represent the ID, title, and year columns of the original table, respectively. Note how the row number comes first in title and year, but second in movie (which is also not called ID). The reason for this will become clear later.

The motivation for focusing on binary relations is that they generalize functions. Functions are powerful because they compose, making them the building blocks of programs. A function maps every input to a unique output, where as a relation can map an input to multiple different outputs. In a sense, a relation can be viewed as a nondeterministic function.

That is all very abstract, so let's go back to our examples. To keep things simple, we will focus on relations mapping every input to exactly one output, i.e., they all happen to be functions. "Calling" a relation then boils down to turning that relation into a dictionary and looking up the value:

print(dict(movie)[646], dict(title)[0], dict(year)[0])

We're now ready to introduce the first and most important operator in Prela, the relation composition. Function composition works by applying one function first, then applying the other one to the output. The composition of two relations r and s is itself a relation, first mapping x with r to get some y, then map y with s for the final "output". This can be implemented by turning s into a dictionary d, iterating the (x, y) pairs in r, and finally outputting (x, d[y]) if y is found in d:

def select(r, s):
  d = dict(s)
  return [ (x, d[y]) for x, y in r if y in d ]

Using our example, the query below composes movie with title to get a relation mapping each movie ID to its title:³

print(movie.select(title))

Try changing title to year and see what you get. The power of composition really shows when we chain together multiple .select calls. Suppose we add a foreign key column mapping each movie to its production company, and another table for movie companies:

Decomposing the same way gives us four more relations:

company = Rel([(0, 0),
               (1, 1),
               (2, 2)])

id2row  = Rel([(0, 0),
               (1, 1),
               (2, 2)])

name    = Rel([(0, "Paramount"),
               (1, "Toho"),
               (2, "Warner Bros.")])

country = Rel([(0, "[us]"),
               (1, "[jp]"),
               (2, "[us]")])

Then, we can find the country of a movie's production company by a chain of .select calls, where we abbreviate with .s:

print(movie.s(company).s(id2row).s(country))

Because joining via a foreign key almost always require "resolving" an ID to a row, Prela automatically inserts that step so one can write the following,⁴ which reads just like "a movie's company's country"!

print(movie.s(company).s(country))

This is also what happened in cast.s(person).s(alias).s(text) on the last line of the snippet in the beginning of the tutorial.

So far every query has returned a single column of values. To select multiple attributes, we introduce the & operator.

Where .select matches the second column of r against the first column of s, & joins r and s on the first column of both, then pairs up their second columns:

def and_(r, s):
  d = dict(s)
  return [ (x, (y, d[x])) for x, y in r if x in d ]

So title & year maps every movie row to both of its attributes at once:

print(title & year)

Note that the result is still a binary relation, & simply nests the values into a tuple. That means we can keep composing it like any other relation, which is how a query returns more than one column:

print(movie.select(title & year))

Next, we need a way to say which rows we want. The predicate .eq(v) filters a relation, keeping only the pairs whose second column equals v:

def eq(r, v):
  return [ (x, y) for x, y in r if y == v ]

On its own, .eq only narrows the relation it is applied to. The query below still maps movie rows to countries, just no longer all of them:

print(company.s(country).eq("[us]"))

Finally, the restriction operator .where takes a predicate like the one above and filters another relation with it.

def where(r, s):
  d = dict(s)
  return [ (x, y) for x, y in r if y in d ]

Handing our predicate to .where turns it into a filter on movies:

print(movie.where(company.s(country).eq("[us]")))

This reads right off the code: "movies where the company's country is [us]".

The query is getting long, so let's refactor it:

american = company.s(country).eq("[us]")
print(movie.where(american))

Wait, did we just create a CTE with a plain Python variable? Yes! This is possible because Prela queries are made up of operators, and every subexpression is a valid query.

How do we have multiple conditions? A happy accident is that, becuase & joins its arguments, it doubles as logical conjunction once nested inside a .where:

print(movie.where(american & year.eq(1942)))

Only Casablanca is American and from 1942. Putting it all together, .select then fetches whatever columns we want to see for the movies that survived the filter:

print(movie.where(american & year.eq(1942)).select(title & year))

We can even push the predicate into the select clause for a cleaner query:

print(movie.where(american).select(title & year.eq(1942)))

And that's pretty much the whole language! Prela also supports grouping and aggregation, and other common operators. We are working a full documentation for the language, so for now you can refer to our paper for more details. As an excercise,⁵ you can try to define the necessary relations so that the snippet at the top runs.

# keyword = ...
# ...

print(movie.where(company.s(country).eq("[us]") &
                  keyword.eq("character-name-in-title"))
          .select(title & cast.s(person).s(alias).s(text)))

A self-contained Python program for our toy Prela can be found here.