Squashed embedding of E-R schemas in hypercubes

We have been investigating an approach to parallel database processing based on treating Entity-Relationship (E-R) 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 (relaxed squashed or RS embeddings) or into adjacent subcubes (relaxed extended squashed or RES embeddings) 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([left ceiling]log2n[right ceiling]) for a completely connected graph, Kn, and RS embedding provides an RS-WCD of O([left ceiling]log2n[right ceiling] + [left ceiling]log2m[right ceiling]) for a completely connected bigraph, Km,n. Typical E-R graphs are incompletely connected bigraphs. An algorithm for embedding incomplete bigraphs is presented.Peer Reviewedhttp://deepblue.lib.umich.edu/bitstream/2027.42/28651/1/0000467.pd