Automatic composition of data structures to represent relations

The authors describe a very general class of composite data structures, and a language in which programmers can describe which to use for each purpose. These data structures are composed of primitive data structures drawn from a relatively small library that can be extended by the programmer. They describe the semantics of composite data structures in terms of a relational model. Programmers can use relational programming languages to express computations, independent of data representation decisions, and then use the data structure language to specify representations for the relations in their programs. A compiler is described that translates operations on relations represented by composite data structures. It uses a cost model to choose among alternative algorithms