What if SELECT, FROM, WHERE were functions?

prela

Check out this code:

movie WHERE ((company.country == "[us]") AND (keyword == "character-name-in-title")) SELECT (title AND cast.person.alias.text)

From a mile a way this just looks like a regular SQL query. If you stare at it though, a few things are off: where's the FROM clause? Why does the SELECT clause come last (like a sane language)? And what's going on with cast.person.alias.text? Is that JSON? Let me explain. First, I'll strip away some syntax magic. The same code in Rust looks like this:

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

Both snippets are queries in a new embedded query language/library we're building called Prela. The original snippet was actually in Scala, and each of WHERE, AND, and SELECT is an infix function, corresponding to Rust's .with, .and, and .select. The == operator is overloaded and corresponds to .eq. Finally, the . operator is also overloaded; it corresponds to Rust's .s which is just an alias for .select. In other words, each of the keywords/operators is a function. But what do the functions take in and produce?

The source code of Prela can be found here.

SQL is based on Codd's Relational Algebra (RA) which is an algebra of relations, a.k.a. tables. Each relational algebra operator takes in tables and produces a table. In contrast, Prela is based on Tarski's Algebra of Relations1 (TAR), which is much less known and much older than Codd's Relational Algebra — although TAR is named after Tarski, its main ideas date all the way back to De Morgan in the 1860s. We've said RA is an algebra of tables — we can think of TAR as an algebra of columns . In both code snippets, each of the variables including movie, company, country conceptually corresponds to a table column. More concretely, they are represented as binary relations under the hood. To understand what's going on, let's consider the following table:

ID title year keyword

646 The Godfather 1972 Crime

478 Seven Samurai 1954 War

583 Casablanca 1942 Romance

This table decomposes into 4 binary relations: the first maps each ID to its row, and the other 3 map each row to its title, year, and keyword, respectively. The special treatment of the ID column will make sense later.

movie

646

478

583

title

The Godfather

Seven Samurai

Casablanca

year

1972

1954

1942

keyword

Crime

War

Romance

We'll call the tables movie, title, year, and keyword from left to right. Now let's consider the simplest query we can write: movie.select(title) in Rust, or movie SELECT title in Scala. The .select operator implements relation composition , which first joins its arguments using the second column of the LHS and the first column of the RHS, then throws away the join column. Formally, r.select(s) is equivalent to the RA expression \pi_{r.1, s.2}(r \Join_{r.2 = s.1} s) where r.i is the i-th column of r. Another way to understand relation composition is to view it as a generalization of function composition, in the same way (binary) relations generalize functions. A binary relation is just a function that can map the same "input" to multiple different "outputs". Let's write r[x] to denote the values x maps to under r as if "applying" r to x, i.e., r[x] = \{y \mid (x, y) \in r\}. Further generalize the notation to allow a set as an argument, i.e., r[\mathbf{x}] = \bigcup_{x\in \mathbf{x}} r[x]. Then, the composition r.select(s) is exactly \lambda \mathbf{x} . r[s[\mathbf{x}]] (with further abuse of notation identifying a relation with its "function"). That's all very abstract, so let's go back to our example. The composition movie.select(title) joins the movie relation (the ID relation) with the title relation on row number. The result is a binary relation mapping every movie ID to its title. This also explains why we needed the row number on the second column of the ID table, because we need to join on it. Similarly, movie.select(year) maps IDs to years, and movie.select(keyword) maps IDs to keywords.

Composition also plays the roles of joins. Say we add a company column to the movie table, mapping each movie's row number to the ID of its production company, and decompose a separate company table with columns id, name, and country.

company

657

188

353

id2row

657

188

353

name

Paramount

Toho

Warner Bros.

country

USA

Japan

USA

The query movie.s(company).s(id2row).s(country) then finds the country of a movie's production company, where id2row maps company IDs to row numbers. Because joining on a foreign key almost always means "resolving" the key to a row number first, Prela automatically inserts that .s(id2row) step for us, the same way Rust automatically dereferences pointers on field access. This lets us simply write movie.s(company).s(country), which reads as "movie's company's country". This is also what...

What if SELECT, FROM, WHERE were functions?

Related Articles

Incident with Github.com

(no title)

Scientists reverse brain aging, with a nasal spray

NHS apologises and admits Palantir have access to identifiable patient data

Cursor Origin