The following problem is called the everywhere-cover problem:“Given a set of dependencies over a database scheme,is the set of dependencies explicitly given for each relation scheme equivalent to the dependencies imp...The following problem is called the everywhere-cover problem:“Given a set of dependencies over a database scheme,is the set of dependencies explicitly given for each relation scheme equivalent to the dependencies implied for that relation scheme?”It is shown that when the everywhere-cover problem has a ‘yes’ answer,examining only the dependencies explicitly given will suffice to test 3NF,BCNF and 4NF of a database scheme.But this does not hold for 2NF.Consequently,in such cases,tests of BCNF and 4NF all take polynomial time.Then a proof is given that test of 3NF of a database scheme is Co-NP-complete,and from this result it is shown that everywhere-cover is also Co-NP-complete when only functional dependencies are allowed.These results lead to doubt the truth of the well believed conjec- ture that no polynomial time algorithm for designing a Iossless BCNF database scheme is likely to exist.展开更多
基金Supported by the National Natural Science Foundation of China.
文摘The following problem is called the everywhere-cover problem:“Given a set of dependencies over a database scheme,is the set of dependencies explicitly given for each relation scheme equivalent to the dependencies implied for that relation scheme?”It is shown that when the everywhere-cover problem has a ‘yes’ answer,examining only the dependencies explicitly given will suffice to test 3NF,BCNF and 4NF of a database scheme.But this does not hold for 2NF.Consequently,in such cases,tests of BCNF and 4NF all take polynomial time.Then a proof is given that test of 3NF of a database scheme is Co-NP-complete,and from this result it is shown that everywhere-cover is also Co-NP-complete when only functional dependencies are allowed.These results lead to doubt the truth of the well believed conjec- ture that no polynomial time algorithm for designing a Iossless BCNF database scheme is likely to exist.
