Functions in Databases.

@article{DBLP:journals/tods/Graham83,
  author    = {Marc H. Graham},
  title     = {Functions in Databases},
  journal   = {ACM Trans. Database Syst.},
  volume    = {8},
  number    = {1},
  year      = {1983},
  pages     = {81-109},
  ee        = {http://doi.acm.org/10.1145/319830.319835, db/journals/tods/Graham83.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We discuss the objectives of including functional dependencies in the definition of a relational database. We find two distinct objectives. The appearance of a dependency in the definition of a database indicates that the states of the database are to encode a function. A method based on the chase of calculating the function encoded by a particular state is given and compared to methods utilizing derivations of the dependency. A test for deciding whether the states of a schema may encode a nonempty function is presented as is a characterization of the class of schemas which are capable of encoding nonempty functions for all the dependencies in the definition. This class is the class of dependency preserving schemas as defined by Beeri et al. and is strictly larger than the class presented by Bernstein.

The second objective of including a functional dependency in the definition of a database is that the dependency be capable of constraining the states of the database; that is, capable of uncovering input errors made by the users. We show that this capability is weaker than the first objective; thus, even dependencies whose functions are everywhere empty may still act as constraints. Bounds on the requirements for a dependency to act as a constraint are derived.

These results are founded on the notion of a weak instance for a database state, which replaces the universal relation instance assumption and is both intuitively and computationally more nearly acceptable.

Copyright © 1983 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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

• 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
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An3-1 or /cdrom

• 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
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

References

[1]

Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX

[2]

William Ward Armstrong: Dependency Structures of Data Base Relationships. IFIP Congress 1974: 580-583 BibTeX

[3]

Adarsh K. Arora, C. Robert Carlson: The Information Preserving Properties of Relational Database Transformations. VLDB 1978: 352-359 BibTeX

[4]

Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124 BibTeX

[5]

Catriel Beeri, Alberto O. Mendelzon, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalence of Relational Database Schemes. SIAM J. Comput. 10(2): 352-370(1981) BibTeX

[6]

Philip A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Trans. Database Syst. 1(4): 277-298(1976) BibTeX

[7]

Philip A. Bernstein, Nathan Goodman: What does Boyce-Codd Normal Form Do? VLDB 1980: 245-259 BibTeX

[8]

Joachim Biskup, Umeshwar Dayal, Philip A. Bernstein: Synthesizing Independent Database Schemas. SIGMOD Conference 1979: 143-151 BibTeX

[9]

E. F. Codd: Further Normalization of the Data Base Relational Model. IBM Research Report, San Jose, California RJ909: (1971) BibTeX

[10]

Peter J. Downey, Ravi Sethi, Robert Endre Tarjan: Variations on the Common Subexpression Problem. J. ACM 27(4): 758-771(1980) BibTeX

[11]

Ronald Fagin: The Decomposition Versus Synthetic Approach to Relational Database Design. VLDB 1977: 441-446 BibTeX

[12]

Ronald Fagin: A Normal Form for Relational Databases That Is Based on Domians and Keys. ACM Trans. Database Syst. 6(3): 387-415(1981) BibTeX

[13]

...

[14]

...

[15]

Peter Honeyman: Testing satisfaction of functional dependencies. J. ACM 29(3): 668-677(1982) BibTeX

[16]

Peter Honeyman, Richard E. Ladner, Mihalis Yannakakis: Testing the Universal Instance Assumption. Inf. Process. Lett. 10(1): 14-19(1980) BibTeX

[17]

...

[18]

David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) BibTeX

[19]

Edward Sciore: Improving Semantic Specification in a Relational Database. SIGMOD Conference 1979: 170-178 BibTeX

[20]

...

[21]

Jeffrey D. Ullman: Principles of Database Systems, 1st Edition. Computer Science Press 1980
BibTeX

[22]

...

Referenced by

1. John L. Knapp: Uniqueness Conditions for ER Representations. OOER 1995: 296-307
2. Alberto O. Mendelzon: Database States and Their Tableaux. ACM Trans. Database Syst. 9(2): 264-282(1984)
3. Marc H. Graham: Path Expressions in Databases. PODS 1983: 366-378
4. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
   Contents
5. Paolo Atzeni, Douglas Stott Parker Jr.: Assumptions in Relational Database Theory. PODS 1982: 1-9