Re: Many to Many Relationships
From: Jan Hidders <hidders_at_uia.ua.ac.be>
Date: Wed, 5 Dec 2001 13:06:50 +0100
Message-ID: <3c0e0dcc$1_at_news.uia.ac.be>
> There are also strong JPNF and overstrong JPNF, which make use of JOIN
> dependencies (JD for short). Unfortunately, there is no systematic
> way to find a JPNF or 4NF schema, because the problem is known to be
> NP complete.
Date: Wed, 5 Dec 2001 13:06:50 +0100
Message-ID: <3c0e0dcc$1_at_news.uia.ac.be>
--CELKO-- <71062.1056_at_compuserve.com> wrote in message news:c0d87ec0.0112041036.75c1d6e0_at_posting.google.com...
>
> There are also strong JPNF and overstrong JPNF, which make use of JOIN
> dependencies (JD for short). Unfortunately, there is no systematic
> way to find a JPNF or 4NF schema, because the problem is known to be
> NP complete.
Which problem exactly? I know that the problem of deciding if a relation is in BCNF is already NP complete if all you have is the FDs. However, this changes if you know already the candidate keys. I believe the same holds for deciding if a relation is in PJ/NF.
- Jan Hidders