Abstract

We have been investigating an approach to parallel database processing based on treating Entity-Relationship schema graphs as dataflow graphs. A prerequisite is to find appropriate embeddings of the schema graphs into a processor graph, in this case a hypercube. This paper studies a class of adjacency preserving embeddings that map a node in the schema graph into a subcube or into adjacent subcubes of a hypercube. The mapping algorithm is motivated by the technique used for state assignment in asynchronous sequential machines. In general, the dimension of the cube required for squashed embedding of a graph is called the weak cubical dimension or WCD of the graph. The RES embedding provides an RES-WCD of O for a completely connected graph, Kn, and RS embedding provides an RS-WCD of O for a completely connected bigraph, Km,n. Typical E-R graphs are incompletely connected bigraphs. An algorithm for embedding incomplete bigraphs is presented.