On Complexity of Effective Data Granulation in Databases

We present a problem of splitting objects from finite set into heterogenous groups of equal or almost equal cardinalities. The problem resembles the classic problem of data clustering, but additional constraint on groups size and global measure of clustering quality makes well known clustering algorithms hardly applicable. Such problem occurs - as we believe - in many important aspects in computer science. We will consider its context in database area and make "body of research" the Info bright RDBMS as we noticed the problem emerges there in some natural way. In the paper we define the problem and present some specified applications. The main contribution of the article is the proof of its NP-hardness.