Closed sets and translations of relation schemes

AbstractThe concept of translation of relation schemes is introduced. Some characterizations of various closed sets in relation schemes, such as generators, coatoms or antikeys are investigated from different aspects. The connections between these objects in a given relation scheme alone and in the prime and translated relation schemes are presented. It is shown that translating a relation scheme can be done in O(|F| · |R|) time and testing whether a subset of attributes is an antikey can be done in O(|F| · |R|2) time, where |F| is the number of functional dependencies and |R| is the number of attributes. It is shown that computing the intersection of all antikeys is NP-complete, but computing their union can be done in polynomial time. A connection between three well-known results of Beeri et al., Demetrovics and Thi, and Ginsburg and Hull about relations representing a given relation scheme or Sperner system is presented