laws such as distribution of selection: σ(p,σ(q,xs)) = σ(xp(x)∧q(x),xs); and then translates these logical expressions into a physical query plan that is executed by the RDBMS.

For example, the SQL query SELECT Name FROM Friend WHERE Likes(Friend, Sushi) is translated into the relational algebra expression π(f⇒ f.Name,(σ(f⇒Likes(f,Sushi ),Friend). To speed up the execution of the query, the RDBMS may use an index to quickly look up friends who like Sushi instead of doing a linear scan over the whole collection.

The cross-apply operator is
particularly powerful since it allows
for correlated subqueries where you
generate a second collection for each
value from a first collection and flat-
ten the results into a single collection
(f,{a,…,z})=f(a)∪…∪f(z). All other
relational operators can be defined in
terms of the cross-apply operator:
over these collections by desugaring
query syntax:

∅ ∈ M<Σ> { _ } ∈ Σ→M<Σ>

∪ ∈ M<Σ>xM<Σ>→M<Σ>
∈ (ΣM<Λ>)xM<Σ>→M<Λ>
xs X ys = @(x⇒π(y⇒(x,y),ys),xs)
π(f,xs) = @(x⇒{f(x)},xs)
σ(p,xs) = @(x⇒p(x)?{x}:∅,xs)i

As a programmer you can eas-
ily imagine writing up a simple imple-
mentation of cross-apply: you would
just iterate over the items in the input
set, apply the given function, and ac-
cumulate the results into a result set.
Such an implementation, however,
wouldn’t need its argument to be as
set {Σ}; anything that we can iterate
over such as a list, array, or hash table
would suffice. Similarly, there is no
reason at all that relational algebra
operations should be restricted to
sets of values {Σ}. They can be imple-
mented based on other types of col-
lections as well.

figure 3. LinQ standard query operators and relational algebra.

//projection π

IEnumerable<T> Select<S,T>(IEnumerable<S> source, Func<S,T> selector)

//CROSS-APPLY
IEnumerable<T> SelectMany<S,T>(IEnumerable<S> source,
Func<S,IEnumerable<T>> selector)
//selection σ

IEnumerable<T> Where<T>(IEnumerable<T> source,

Func<T,bool> predicate)

For programmers this is just separating interface from implementation; mathematicians call the resulting structure monads, and instead of queries they speak of comprehensions.

An OO language such as C# uses the canonical interface for collections IEnumerable<T> as a specific instance of the abstract collection type M<T> and uses delegates Func<Σ,Λ> to represent computations ΣΛ. By doing this, you recognize the operators from relational algebra as the LINQ standard query operators as defined in the Linq.Enumerable class, as shown in Figure 3.

Alternatively, you can use the IQueryable<T> interface to represent collections M<T> and expression tree Expression<Func<Σ,Λ>> to represent computations ΣΛ. In that case you recognize the relational algebra operators as the LINQ standard query operators as defined in the Linq.Que-ryable class. The ability to treat code as data using morphisms—or in the C# case using the Expression type and lambda expressions for code literals— is a fundamental capability that allows the program itself to manipulate, optimize, and translate queries at runtime.

Instead of SQL syntax, the C# language defines XQuery-like comprehensions of the form from-where-se-lect. The previous SQL query example looks like this:

 

from friend in friends where friend. Likes(Sushi) select friend.Name

figure 4. Yahoo weather state machine.

.Where(…)

Weather
InCity
.Where(…)

Weather
InCityInunits

Just as in SQL, comprehensions are translated by the compiler into the underlying LINQ query algebra:

Weather

friends.Where(friend⇒friend. Likes(Sushi)).Select(friend⇒ friend.Name)

.Weatherservice()

.getAwaiter
.getAwaiter
Yahoo
TaskAwaiter
<response>

Depending on the overloads of Where and Select, the lambda expressions will be interpreted as code or data. A simplified implementation of IQueryable is discussed later.