摘要 |
In accordance with the present invention, a system and method for positioning data in a database is provided which employs coarsening a graph representing the data in order to reduce the computational complexity of determining an efficient partitioning. In certain object-oriented databases embodying the present invention, for example, a graph is constructed in which each object corresponds to a vertex, and the affinities of pairs of objects correspond to edges. The affinities are assigned based on a combination of predefined access types associated with collection and statistical data regarding actual access patterns. Simpler graphs are then iteratively produced by collapsing pairs of vertices into single vertices in the successive graphs until a graph of the desired simplicity is constructed; this graph is then partitioned, producing a rough partitioning of the objects, which can then be refined. <IMAGE>
|