Complexity of a proposed database storage structure

摘要

An alternate method for storing M to N relationships is presented. Implementing this method involves a minimization procedure which is shown to be equivalent to finding the minimal number of bipartite cliques which cover all of the edges of a related bipartite graph. This bipartite edge clique cover problem is known to be NP-complete, suggesting that attention should be focused on finding heuristic, not necessarily optimal, algorithms which produce solutions in polynomial-time. One such heuristic is presented which seems to work well on a variety of bipartite graphs. However, there are bipartite graphs for which its performance is poor, i.e. the heuristic produces solutions significantly worse than optimum. A family of bipartite graphs is presented for which the performance factor is unbounded.