This paper focuses on a problem that occurs in the process of database design, that is keys generation. The problem of keys determination is known to be NP-complete for relation schemes. This is why a solution might be the problem size minimization which can be done by different approaches combination. Firstly, all dependencies that do not participate in new keys generation are eliminated.Secondly, those keys that don’t participate in new keys generation are identified. Finally, is determined an order of application of functional dependencies over existent keys for new keys generation. All these processes reduce the size of the problem of searching of the unsynthesized keys and serve as base to obtain a polynomial algorithm for keys generation.