decompositions ensure that the root node does not contain any unit decompositions, so it is always possible to represent the empty relation.

To insert a tuple t into an instance d of a decomposition dˆ, for each node v: B  C in the decomposition we need to find or create a node instance vs in the decomposition instance, where s is tuple t restricted to columns B. For each edge in the decomposition we also need to find or create an instance of the edge connecting the corresponding pair of node instances. We perform insertion over the nodes of a decomposition in topologically sorted order. For each node v we locate the existing node instance vs corresponding to tuple t, if any. If no such vs exists, we create one, inserting vs into any data structures that link it to its ancestors. For example, inserting the tuple ns: 2, pid: 1, state: S, cpu: 5 into the decomposition instance shown in Figure 3(a) yields the state shown in Figure 3(b).

We next consider the dremove and dupdate operations. Operation dremove removes tuples matching tuple s from an instance d of decomposition dˆ.

To remove tuples matching a tuple t, we compute a cut of the decomposition between those nodes that can only be part of the representation of tuples matching t, and those nodes that may form part of the representation of tuples that do not match t. We then break any edge instances crossing the cut. To find the edge instances to break we can reuse the query planner. Once all such references are removed, the instances of nodes in Y are unreachable from the root of the instance and can be deallocated. We can also clean up any map nodes in X that are now devoid of children.

Operation dupdate updates tuples matching s using values from u in an instance d of decomposition dˆ. Semantically, updates are a removal followed by an insertion. In the implementation we can reuse the nodes and edges discarded in the removal in the subsequent insertion—that is, we can perform the update in place.

4. 3. soundness of relational operations Finally we show that the operations on decompositions faithfully implement their relational specifications.

Theorem 2. Let C be a set of columns, a set of FDs, and dˆ

figure 3. example of insertion and removal. inserting the tuple t = ⟨ns: 2, pid: 1, state: S, cpu: 5⟩ into instance (a) produces instance (b); conversely removing tuple t from (b) produces (a). Differences between the instances are shown using dashed lines.

(a)

y1 1

pid 1

x
zS zR
ns
S
state

R

2 ns, pid

1, 1 ns, pid

1, 2

;cpu: 7ñ ;cpu: 4ñ w1 1 w2 1

(b)

x
zS zR
ns

2S
state
ns, pid

1, 1 2, 1

ns, pid 1, 2

y1 y2 1

pid

12 pid

1

;cpu: 7ñ ;cpu: 4ñ w1 1 w21

ácpu: 5ñ w12

a decomposition adequate for C and . Suppose a sequence of insert, update and remove operators starting from the empty relation produce a relation r, and each intermediate relation satisfies FDs . Then the corresponding sequence of dinsert, dupdate, and dremove operators given dempty dˆ as input produce an instance d such that a(d) = r.

5. auto-tuneR

Thus far we have concentrated on the problem of compiling relational operations for a particular decomposition of a relation. However, a programmer may not know, or may not want to invest time in finding the best possible decomposition for a relation. We have therefore constructed an auto-tuner that, given a program written to the relational interface, attempts to infer the best possible decomposition for that program.

The auto-tuner takes as input a benchmark program that produces as output a cost value (e.g., execution time), together with the name of a relation to optimize. The auto-tuner then exhaustively constructs all decompositions for that relation up to a given bound on the number of edges, recompiles and runs the benchmark program for each decomposition, and returns a list of decompositions sorted by increasing cost. We do not make any assumptions about the cost metric—any value of interest such as execution time or memory consumption may be used.

6. eXPeRiments

We have implemented a compiler, named RelC, that takes as input a relational specification and a decomposition, and emits C++ code implementing the relation. We evaluate our compiler using micro-benchmarks and three real-world systems. The micro-benchmarks (Section 6. 1) show that different decompositions have dramatically different performance characteristics. Since our compiler generates C++ code, it is easy to incorporate synthesized data representations into existing systems. We apply synthesis to three existing systems (Section 6. 2), namely a Web server, a network flow accounting daemon, and a map viewer, and show that synthesis leads to code that is simultaneously simpler, correct by construction, and comparable in performance to the code it replaces.

We chose C++ because it allows low-level control over memory layout, has a powerful template system, and has widely used libraries of data structures from which we can draw. Data structure primitives are implemented as C++ template classes that implement a common associative container API. The set of data structures can easily be extended by writing additional templates and providing the compiler some basic information about the data structure’s capabilities. We have implemented a library of data structures that wrap code from the C++ Standard Template Library and the Boost Library, namely doubly linkedlists(std::list, boost::intrusive::list), binary trees (std::map, boost::intrusive::set hash-tables (boost::unordered_map), and vectors (std::vector). The library includes both nonintru-sive containers, in which elements are represented out-of-line as pointers, and intrusive containers, in