Normal forms and minimal keys in the relational datamodel

Demetrovics János; Thi Vu Duc: Normal forms and minimal keys in the relational datamodel. In: Acta cybernetica, (11) 3. pp. 205-215. (1994)

Előnézet

Cikk, tanulmány, mű cybernetica_011_numb_003_205-215.pdf Letöltés (750kB) | Előnézet

Absztrakt (kivonat)

The normalization of relations was introduced by E. F. Codd. The main purpose of normalization is to delete undesired redundancy and anormalies. The most desirable normal forms are second normal form ( 2NF ), third normal form ( 3NF ) and Boyce-Codd normal form ( BCNF ) that have been investigated in a lot of papers. The concepts of minimal key and prime attribute ( recall that an attribute is prime if it belongs to a minimal key, and nonprime otherwise ) directly concern 2NF, 3NF and BCNF. This paper investigates connections between these normal forms and sets of minimal keys. Lucchesi and Osborn showed [ll] that the problem to decide if an arbitrary attribute is prime is NP-complete for relation scheme. We proved [9] that a set of all nonprime attributes is the intersection of all antikeys ( maximal nonkeys ) and this prime attribute problem can be solved by polynomial time algorithm for relation. From these results some problems are NP-complete for relation scheme, but for relation these problems are solved by polynomial time algorithms. It is known [5j that a set of all minimal keys of a relation scheme ( and a relation ) is a Sperner system ( sometimes it is called an antichain ) and for an arbitrary Sperner system there exists a relation scheme the set of all minimal keys of which is exactly this Sperner system. In this \ paper the following concepts are introduced. A Sperner system K is in 2NF ( 3NF, BCNF, respectively ) if for each relation scheme s such that K, — K then « is in 2NF ( 3NF, BCNF, respectively ), where K, is a set of all minimal keys of e. This paper gives necessary and sufficient conditions for an arbitrary Sperner system is in 2NF or 3NF or BCNF. We prove that problems of deciding whether K, is in 2NF ( 3NF, respectively ) are NP-complete. However, we show that if a relation scheme is changed to a relation then these problems are solved by polynomial time algorithms. We give a new characterization of relations and relation schemes that are uniquely determined by their minimal keys. From this characterization we give a polynomial time algorithm deciding whether an arbitrary relation is uniquely determined by its set of all minimal keys. Osborn [14] gives a polynomial time algorithm testing BCNF property of a given relation scheme. This paper gives a polynomial time algorithm recognizing BCNF and finding a set of all minimal keys and a minimum cover if a given relation scheme is in BCNF.

Mű típusa:	Cikk, tanulmány, mű
Befoglaló folyóirat/kiadvány címe:	Acta cybernetica
Dátum:	1994
Kötet:	11
Szám:	3
ISSN:	0324-721X
Oldalak:	pp. 205-215
Nyelv:	angol
Kiadás helye:	Szeged
Befoglaló mű URL:	http://acta.bibl.u-szeged.hu/38497/
Kulcsszavak:	Számítástechnika, Kibernetika
Megjegyzések:	Bibliogr.: p. 214-215. ; ö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. 11:24
URI:	http://acta.bibl.u-szeged.hu/id/eprint/12529

Bővebben:

Tétel nézet