Re: Relational database design

In article <965ea573.0206180243.5ad716c9_at_posting.google.com>, Ksenia <ksenia_at_olis.ru> wrote:
>
>During my work I have to proove the NP-completness of additional key
>finding problem, find the polynomial algorithm, which gives the
>solution accuracy to within multiplicative constant (if it exists) and
>find polynomial algorithms, which solve the special instance of
>problem.

I can only tell you that the proof of NP completeness is in some unpublished manuscript by Catriel Beeri and Bernstein titled "Computational problems related to design of normal form relationa schemes" in 1978, that showed a reduction to HITTING SET. (See Garey and Johnson)

For the approximation algorithm did you have already a cost function in mind? The size of the set of keys, perhaps?

• Jan Hidders