Some problems concerning Armstrong relations of dual schemes and relation schemes in the relational datamodel
Several papers [3,5,6,7,8,9,11,12] have appeared for investigating dual dependency. The practical meaning of dual dependency was shown in [5,6]. In this paper we give some new results concerning dual dependency. The concept of dual scheme is introduced. Some characterizations of dual scheme, such as...
Saved in:
| Main Authors: | |
|---|---|
| Format: | Article |
| Published: |
1993
|
| Series: | Acta cybernetica
11 No. 1-2 |
| Kulcsszavak: | Számítástechnika, Kibernetika |
| Subjects: | |
| Online Access: | http://acta.bibl.u-szeged.hu/12519 |
| Summary: | Several papers [3,5,6,7,8,9,11,12] have appeared for investigating dual dependency. The practical meaning of dual dependency was shown in [5,6]. In this paper we give some new results concerning dual dependency. The concept of dual scheme is introduced. Some characterizations of dual scheme, such as closure, generator, generating Armstrong relation, inferring dual dependencies, irredundant cover, normal cover are studied from different aspects. We give a characterization of Armstrong relations for a given dual scheme. We prove that the membership problem for dual dependencies is solved by a polynomial time algorithm. We show that the time complexity of finding an Armstrong relation of a given dual scheme is exponential in the number of attributes. Conversely, we give an algorithm to construct a dual scheme from a given relation R such that R is Armstrong relation of it. This paper gives some polynomial time algorithms which find closure, irredundant cover, normal cover from a given dual scheme. In the second part of this paper we present some results related to Armstrong relations for functional dependency (FD for short) in Boyce-Codd normal form. The concepts of unique relation and unique relation scheme are introduced. We prove that deciding whether a given relation R over a set of attributes U is unique is solved by a polynomial time algorithm. We show some cases in which FD-relation equivalence problem is solved .in polynomial time. |
|---|---|
| Physical Description: | 35-47 |
| ISSN: | 0324-721X |