Some problems concerning Armstrong relations of dual schemes and relation schemes in the relational datamodel

Demetrovics János; Thi Vu Duc: Some problems concerning Armstrong relations of dual schemes and relation schemes in the relational datamodel. In: Acta cybernetica, (11) 1-2. pp. 35-47. (1993)

[thumbnail of cybernetica_011_numb_001_002_035-047.pdf]
Előnézet
Cikk, tanulmány, mű
cybernetica_011_numb_001_002_035-047.pdf

Letöltés (814kB) | Előnézet

Absztrakt (kivonat)

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.

Mű típusa: Cikk, tanulmány, mű
Befoglaló folyóirat/kiadvány címe: Acta cybernetica
Dátum: 1993
Kötet: 11
Szám: 1-2
ISSN: 0324-721X
Oldalak: pp. 35-47
Nyelv: angol
Kiadás helye: Szeged
Befoglaló mű URL: http://acta.bibl.u-szeged.hu/38496/
Kulcsszavak: Számítástechnika, Kibernetika
Megjegyzések: Bibliogr.: p. 46-47. ; összefoglalás angol nyelven
Szakterület: 01. Természettudományok
01. Természettudományok > 01.02. Számítás- és információtudomány
Feltöltés dátuma: 2016. okt. 15. 12:26
Utolsó módosítás: 2022. jún. 13. 10:47
URI: http://acta.bibl.u-szeged.hu/id/eprint/12519
Bővebben:
Tétel nézet Tétel nézet