An Improved Algorithm for Finding a Key of a Relation.

Sukhamay Kundu: An Improved Algorithm for Finding a Key of a Relation. PODS 1985: 189-192

@inproceedings{DBLP:conf/pods/Kundu85,
  author    = {Sukhamay Kundu},
  title     = {An Improved Algorithm for Finding a Key of a Relation},
  booktitle = {Proceedings of the Fourth ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, March 25-27, 1985, Portland, Oregon},
  publisher = {ACM},
  year      = {1985},
  isbn      = {0-89791-153-9},
  pages     = {189-192},
  ee        = {http://doi.acm.org/10.1145/325405.325431, db/conf/pods/Kundu85.html},
  crossref  = {DBLP:conf/pods/85},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

We present here an improved algorithm to find a key of a relation R(A) on the attributes A. The algorithm requires O(|K|.||F||) time, where |K| is the size of the key obtained and ||F|| is the length of the input specification for the functional dependencies F. The previously known algorithms require O(|A|.||F||) time, which can be an order of magnitude larger if |K| is small compared to |A|.

Copyright © 1985 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

BibTeX

Printed Edition

Proceedings of the Fourth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 25-27, 1985, Portland, Oregon. ACM 1985, ISBN 0-89791-153-9
Contents BibTeX

Online Edition: ACM Digital Library

References

[1]: Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX
[2]: ...
[3]: Catriel Beeri, Philip A. Bernstein: Computational Problems Related to the Design of Normal Form Relational Schemas. ACM Trans. Database Syst. 4(1): 30-59(1979) BibTeX
[4]: Philip A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Trans. Database Syst. 1(4): 277-298(1976) BibTeX
[5]: E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[6]: ...
[7]: Tok Wang Ling, Frank Wm. Tompa, Tiko Kameda: An Improved Third Normal Form for Relational Databases. ACM Trans. Database Syst. 6(2): 329-346(1981) BibTeX
[8]: Claudio L. Lucchesi, Sylvia L. Osborn: Candidate Keys for Relations. J. Comput. Syst. Sci. 17(2): 270-279(1978) BibTeX

Referenced by

Mark Levene, George Loizou: Database Design for Incomplete Relations. ACM Trans. Database Syst. 24(1): 80-125(1999)

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]