Re: Relational database design

> 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)

Thanks, but I already have this reduction. The main and only question is that I really need to proove not-existance of approximate algorithm gives the solution accuracy within the additional constsnt (so |ALG(I) - OPT(I)| <= CONST) and proove the same or find an algorithm for multiplicative constant (so ALG(I) / OPT(I) <= CONST)
And that is my headache ;-).

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

And about cost function I also think the same, cause in hitting set optimized problem it is the number of elements in the hitting set. Received on Wed Jun 19 2002 - 12:34:43 CEST