SOME PROBLEMS CONCERNING KEYS FOR RELATION SCHEMES AND RELATIONS IN THE RELATIONAL DATAMODEL

We give some results related to the following three problems. For a gi ven relation r and relation scheme s, decide whether: (1) each key of s is a key of r, (2) all keys of r are keys of s and (3) K(r) = K(s), where K(r),K(s) are sets of minimal keys of r,s. We show that the firs t problem is solved in polynomial time and the second problem is co-NP -complete. For the third problem we prove that if relations and relati on schemes satisfy certain additional properties, then this problem is solved in polynomial time. This paper shows also that the time comple xity of finding a relation r from a given relation scheme s such that K(r) = K(s) is exponential in the size of s.