RECOVERING A RELATION FROM A DECOMPOSITION USING CONSTRAINT SATISFACTION

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.