ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Practical Algorithms for Finding Prime Attributes and Testing Normal Forms.

Heikki Mannila, Kari-Jouko Räihä: Practical Algorithms for Finding Prime Attributes and Testing Normal Forms. PODS 1989: 128-133
@inproceedings{DBLP:conf/pods/MannilaR89,
  author    = {Heikki Mannila and
               Kari-Jouko R{\"a}ih{\"a}},
  title     = {Practical Algorithms for Finding Prime Attributes and Testing
               Normal Forms},
  booktitle = {Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 29-31, 1989, Philadelphia,
               Pennsylvania},
  publisher = {ACM Press},
  year      = {1989},
  isbn      = {0-89791-308-6},
  pages     = {128-133},
  ee        = {http://doi.acm.org/10.1145/73721.73734, db/conf/pods/MannilaR89.html},
  crossref  = {DBLP:conf/pods/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Several decision problems for relational schemas with functional dependencies are computationally hard. Such problems include determining whether an attribute is prime and testing if a schema is in normal form. Algorithms for these problems are needed in database design tools. The problems can be solved by trivial exponential algorithms. Although the size of the instance is usually given by the number of attributes and hence is fairly small, such exponential algorithms are not usable for all design tasks. We give algorithms for these problems whose running time is polynomial in the number of maximal sets not determining an attribute or, equivalently, the number of generators of the family of closed attribute sets. There is theoretical and practical evidence that this quantity is small for the schemas occurring in practice and exponential only for pathological schemas. The algorithms are simple to implement and fast in practice. They are in use in the relational database design tool Design-By-Example.

Copyright © 1989 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 ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 29-31, 1989, Philadelphia, Pennsylvania. ACM Press 1989, ISBN 0-89791-308-6
Contents BibTeX

Online Edition: ACM Digital Library

References

[1]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX
[2]
José A. Blakeley, Neil Coburn, Per-Åke Larson: Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates. ACM Trans. Database Syst. 14(3): 369-400(1989) BibTeX
[3]
José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71 BibTeX
[4]
Peter J. Downey, Ravi Sethi, Robert Endre Tarjan: Variations on the Common Subexpression Problem. J. ACM 27(4): 758-771(1980) BibTeX
[5]
...
[6]
Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976) BibTeX
[7]
Harry B. Hunt III, Daniel J. Rosenkrantz: The Complexity of Testing Predicate Locks. SIGMOD Conference 1979: 127-133 BibTeX
[8]
Anthony C. Klug: Locking Expressions for Increased Database Concurrency. J. ACM 30(1): 36-54(1983) BibTeX
[9]
Per-Åke Larson, H. Z. Yang: Computing Queries from Derived Relations. VLDB 1985: 259-269 BibTeX
[10]
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX
[11]
Greg Nelson, Derek C. Oppen: Simplification by Cooperating Decision Procedures. ACM Trans. Program. Lang. Syst. 1(2): 245-257(1979) BibTeX
[12]
Derek C. Oppen: Complexity, Convexity and Combinations of Theories. Theor. Comput. Sci. 12: 291-302(1980) BibTeX
[13]
...
[14]
Robert Endre Tarjan: Efficiency of a Good But Not Linear Set Union Algorithm. J. ACM 22(2): 215-225(1975) BibTeX

Referenced by

  1. Joachim Biskup, Ralf Menzel, Torsten Polle, Yehoshua Sagiv: Decomposition of Relationships through Pivoting. ER 1996: 28-41
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:56 2009