Transition System for a Three-Processor, Four Relation Multijoin

Here's a complete graphical representation of all the ways in which we can move from a given initial state X (subscript 0), where the data is in four relations that are physically stored in three different systems, to one of three possible end states (F (subscript 1), F (subscript 2), F (subscript 3)) in which all the relations have been joined into a single relation residing in one processor.

Along the way, there are 11 possible intermediate states. We move from one state to another by performing one of three possible actions: joining two relations already in a single processor, moving a relation to another processor and joining it with a relation already there, or doing any two of these in parallel.

For simplicity's sake, this diagram uses 1 to represent the relation r (subscript 1), and so on. While some paths from X (subscript 0) to the end states are clearly shorter than others, we can find the most efficient path (and thereby the most efficient end state) only by calculating the costs of the operations involved for each state cha nge. For example, in joining a small relation with a large one, where each resides on a different machine, it's obviously more efficient to move the small one than to move the large one.