A purely distributive representation of a relation is characterized by
invariance under changes in the sorted order of the tuples of the rel
ation. Natural join, intersection, and union operations can be perform
ed on distributive representations of the operands with very high para
llelism because there is no need for any search, nor for prior sorting
. What is obtained is a distributive representation of the result rela
tion, from which the relation itself can be recovered, in any desired
sorted order, by a serial tree-search process. This paper describes a
particular distributive representation scheme, and demonstrates that t
he associated recovery process corresponds to solving a constraint sat
isfaction problem. It is shown that by pruning the tree-search, it is
possible to carry out the recovery process in a time which is linear i
n the cardinality of the recovered relation, in some cases. Although t
he recovery process may occasionally obtain additional spurious tuples
, not present in the relation, it is shown that the occurrence of thes
e spurious tuples may be made extremely rare by an appropriate choice
of system parameters.