Optimal graph clustering problems with applications to information system design (partitioning, database)
Wan-Ping Chiang · Deep Blue (University of Michigan) · 1984
Information system design problems, including database and software, can often be represented in terms of directed or undirected graphs. Some of these problems typically involve determining how to cut the graph into a set of nonvoid and disjoint subgraphs such that each of the subgraphs is of a limited weight and belongs to a graph class while an objective function defined over the subgraphs is optimized. The class of information system design problems is analyzed with the following three objectives: First, to formally define this class of problems as an Optimal Graph Clustering (OGC) problem and classify it into a set of subproblems. Second, to find efficient algorithms that give an exact and optimal solution to each subproblem with nontrivial objective function and constraints. An third, to demonstrate these algorithms' usefulness by formalizing and solving some information system (database and software) design problems. Eight classes of digraphs (general digraph, acyclic digraph, out-necklace, out-tree, out-star, in-necklace, in-tree and in-star) and four classes of undirected graphs (general undirected graph, necklace, tree and star) are considered and are used to classify the OGC problem into thirty-five subproblems. These subproblems are shown to be NP-complete problems. Sequential clustering technique and maximal clusterings enumeration are used to show those OGC subproblems with given graphs that have n vertices and n-1 arcs or n arcs can be solved in pseudopolynomial time. It is also determined that for the other NP-complete problems, if the graphs are sparse (i.e., the number of arcs does not exceed the number of vertices greatly) they are solvable by computer. The class of possible objective functions and constraints applicable to these solutions such that all time complexities remain the same is also defined. All monotonic objective functions and constant time computable constraints are found to be applicable. The solutions' usefulness is demonstrated by solving three information system design problems: B-tree secondary storage allocation, translation of an integrated schema into a hierarchial schema, and database record clustering.