operations described in Section 2 into code tailored to a particular decomposition. There are two basic kinds of relational operation, namely queries and mutations. Since we use queries when implementing mutations, we describe queries first.

4. 1. Queries and query plans

Recall that the query operation retrieves data from a relation; given a relation r, a tuple t, and a set of columns C, a query returns the projection onto columns C of the tuples of r that match tuple t. We implement queries in two stages, similar to a database: query planning, which attempts to find the most efficient execution plan q for a query, and query execution, which evaluates a particular query plan over a decomposition instance.

In the RelC compiler, query planning is performed at compile time; the compiler generates specialized code to evaluate the chosen plan q with no run-time planning or evaluation overhead. The compiler is free to use any method it likes to chose a query plan, as long as the plan answers the query correctly.

As a motivating example, suppose we want to find the set of pid values of processes that match the tuple ns: 7, state: R using the decomposition of Figure 2. That is, we want to find the running processes in namespace 7. One possible strategy would be to look up state: R on the right-hand side, and then to iterate over all ns, pid pairs associated with the state, checking to see whether they are in the correct namespace. Another strategy would be to look up namespace 7 on the left-hand side, and to iterate over the set of pid values associated with the namespace. For each pid, we then check to see whether the ns and pid pair is in the set of processes associated with state: R on the right-hand side. Each strategy has a different computational complexity; the query planner enumerates the alternatives and chooses the “best” strategy.

A query plan is a tree of query plan operators. The query plan tree is superimposed on a decomposition and rooted at the decomposition’s root. A query plan prescribes an ordered sequence of nodes and edges of the decomposition instance to visit. There are five query plan operators:

 

Unit The qunit operator returns the unique tuple represented by a unit decomposition instance if that tuple matches t. It returns the empty set otherwise.

scan The operator qscan(q) invokes operator q for each child node vs where s matches t. Recall a map primitive is a mapping from a set of key columns C to a set of child nodes {vt}t T. Since operator qscan iterates over the contents of a map data structure, it typically takes time linear in the number of entries.

Lookup The qlookup(q) operator looks up a particular set of key values in a map decomposition; each of the key columns of the map must be bound in the tuple t given as input to the operator. Query operator q is invoked on the resulting sub-decomposition, if any. The complexity of the qlookup depends on the particular choice of data structure. In general, we expect qlookup to have better time complexity than qscan.

Join The qjoin(q1, q2, lr) operator performs a join across both sides of a join decomposition. The computational complexity of the join may depend on the order of evaluation. If lr is the value left, then first query q1 is executed on the left side of the join decomposition, and query q2 is executed on the right side of the join for each tuple returned by tuple q1; the result of the join operator is the natural join of the two subqueries. If lr is the value right, the two queries are executed in the opposite order. The qlr(q, lr) operator is a special case of the join operator, which performs query q on either the left-hand or right-hand side of a join specified by the argument lr. The other side of the join is ignored.

 

Recall our motivating example, namely the query

query r ns: 7, state: R {pid}
that returns the set of running processes in namespace 7.

q1 = qlr(qlookup(qscan(qunit) ), right)
q2 = qjoin(qlookup(qscan(qunit) ),
An important property of the query operators is that they
all require only constant space; there is no need to allocate
intermediate data structures to execute a query. Constant-
space queries can also be a disadvantage; for example, the
current restrictions would not allow a “hash-join” strategy
for implementing the join operator, nor is it possible to
perform duplicate-elimination. It would be straightfor-
ward to extend the query language with nonconstant-space
operators.

4. 2. mutations

Next we turn our attention to operations dempty, which creates an empty instance of a decomposition dˆ, and dinsert, which inserts a tuple t into a decomposition instance d.

To create an empty instance of a decomposition, the dempty operation simply creates a single instance of the root node of the decomposition graph; since the relation does not contain any tuples, we do not need to create instances of any map edges. The adequacy conditions for