In type systems, is there a name for SQL's way of cutting and combining record types into new types?

Question

I'd like to have this feature in my application programming language (which these days, is Scala), but when I went to learn more about it on the internets, I realized I don't know the name of it. I'm talking about the ability to do this (in Scala-ish pseudocode):

// Define some types that correspond to table rows in relational DB
class User 
   val id: Int
   val name: String
   val email: String
   val created: DateTime

class Comment
   val id: Int
   val text: String
   val userId: Int
   val created: DateTime

// Call a select/join query function
val list = select c.id, c.text, u.name
           from comments c join user u on c.userId = u.id ...

And then list gets a type of something like List[R] where R is an unnamed record type with properties id, text, name, or maybe c.id,c.text,u.name.

Some languages, like Scala, support you writing that select function so it returns a tuple type (Int, String, String), but not a type with named fields.

Is there a name for that?

Answer 1

I think what you are looking for is type inference for record types. Let me give you a bit of an overview on each of those; but those keywords should help you find a lot more on those topics.

---

Type inference means that you don't need to declare the type of everything. Instead, the compiler figures out the types where it can, from context. For instance if you write a function

function f(x,y):
    return (x+y)/2

the compiler can figure out that f is a function that accepts two ints and returns an int. (How? It knows that 2 is an int, and that both operands to the / operator must have the same type. Therefore, the type of (x+y) must be int. That in turn means that both x and y must have type int. And so on.)

You want type inference, so you don't need to explicitly declare the type of the result of the select and join operations.

---

A record type is basically just a fancy name for a struct.

A record is an object that has a list of fields; each field has a name and a type. For instance, to invent some example syntax: {height: 69, weight: 152, name: "Bob"} might be a record with three fields; if r is a variable holding this record, then you might be able to use syntax like r.height to access the height field.

You might notice that a record is a lot like a tuple, except that the elements of a tuple do not have names (you just access the first element, second element, third element, etc. of a tuple), whereas the elements of a record do have names. The ability to provide names is convenient.

Others have suggested you want anonymous record types, meaning you don't have to explicitly declare the record type. That might be relevant, too.

---

With those concepts, here's what I think you want from a language. First, I think you want your language to support records. Second, assuming you want a statically typed language, it sounds like you want your language to support type inference, so that the compiler can infer the types of records where possible. (In a dynamically typed language, you might not need the type inference part.) Third, you want your language to provide select and join operations that operate on records and return records, and (assuming you want a statically typed language) you want the type inference operation to be able to infer the types on their result based on the types of what they're operating on.

There are some questions you'll need to decide. Will select and join be built into the language? Or do you want to enable them to be implemented as libraries or user-defined functions?

You'll also need to make some decisions about your type system. Do you want to alow subtyping on records? Do you want to allow functions in your language to be polymorphic over records? For instance, consider the following function:

function g(r):
    return (r.weight + 10) / r.height

Do you want your type inference routine to infer that g is polymorphic in the sense that it can accept any record containing width and height fields that are both ints? Do you want to allow first-class field names? For instance, consider the following function:

function extract(r,f):
    return r.f

r = {height: 69, weight: 152, name: "Bob"}
extract(r, #weight)

In other words, do you want to be able to pass the name of a field as a first-class value?

---

There's lots of work on type systems for this sort of stuff, in the programming languages community -- and especially in functional languages. I believe that F# and ML support sophisticated record types. Here are two samples:

• A proposal for records in Haskell. Simon Peyton Jones and Greg Morrisett, 2003.

• Record Polymorphism in SML#. Atsushi Ohori, Katsuhiro Ueno, 2012.

For experience about how to integrate SQL-like database queries directly into the programming language, take a look at LINQ, which provides support for SQL queries directly in .NET / C#. There are both academic papers on LINQ and lots of documentation for developers. It looks very close to what you are looking for.