Functions in databases

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.

REFERENCES

• 1: AHO, A.V., SAGXV, Y., AND ULLMAN, J. Equivalence among relational expressions. SIAM J. Comput. 8, 2 (1979), 218-246.
• 2: ARMSTRONG, W.W. Dependency structures of data base relationships. In Proc. IFIP 1974, Elsevier North-Holland, New York, 1974, pp. 580-583.
• 3: ARORA, A.K., AND CARLSON, C.R. The information preserving properties of relational database transformations. In Proc. 4th Int. Conf. Very Large Data Bases (West Berlin, Sept. 13-15), ACM, New York, 1978, pp. 352-359.
• 4: BEERI, C., BERNSTEIN, P.A., AND GOODMAN, N. A sophisticate's introduction to database normalization theory. In 4th Int. Conf. Very Large Data Bases (West Berlin, Sept. 13-15), ACM, New York, 1978, pp. 113-124.
• 5: BEERI, C., MENDELZON, A., SAGIV, Y., AND ULLMAN, J. Equivalence of relational database schemes. Siam J. Comput. 10, 2 (May 1981), 352-370.
• 6: Philip A. Bernstein, Synthesizing third normal form relations from functional dependencies, ACM Transactions on Database Systems (TODS), v.1 n.4, p.277-298, Dec. 1976 [doi>10.1145/320493.320489]
• 7: BERNSTEIN, P. A., AND GOODMAN, N. What does Boyce-Codd Normal Form do? In 6th Int. Conf. Very Large Data Bases (Montreal, Oct. 1-3), ACM, New York, 1980, pp. 245-259.
• 8: Joachim Biskup , Umeshwar Dayal , Philip A. Bernstein, Synthesizing independent database schemas, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582118]
• 9: CODD, E.F. Further normalization of the data base relational model. In Data Base Systems, R. Rustin, Ed. Prentice-Hall, Englewood Cliffs, N.J., 1972, pp. 33-64.
• 10: Peter J. Downey , Ravi Sethi , Robert Endre Tarjan, Variations on the Common Subexpression Problem, Journal of the ACM (JACM), v.27 n.4, p.758-771, Oct. 1980 [doi>10.1145/322217.322228]
• 11: FAGIN, R. The decomposition versus synthetic approach to relational database design. In 3rd. Int. Conf. Very Large Data Bases (Tokyo, Oct. 6-8), ACM, New York, 1977, pp. 441-446.
• 12: Ronald Fagin, A normal form for relational databases that is based on domains and keys, ACM Transactions on Database Systems (TODS), v.6 n.3, p.387-415, Sept. 1981 [doi>10.1145/319587.319592]
• 13: Marc Henry Graham, Satisfying database states, 1982
• 14: HARARY, F. Graph Theory. Addison-Wesley, Reading Mass., 1969.
• 15: Peter Honeyman, Testing satisfaction of functional dependencies, Journal of the ACM (JACM), v.29 n.3, p.668-677, July 1982 [doi>10.1145/322326.322330]
• 16: HONEYMAN, P., LADNER, R., AND YANNAKAKIS, M. Testing the universal instance assumption. Inf. Proc. Lett. 10, 1 (1980), 14-19.
• 17: LING) T., AND TOMPA, F. Implicit constraints within relational databases. CS-78-35, Dep. of Computer Science, Univ. of Waterloo, Waterloo, Ont., Canada, 1978.
• 18: David Maier , Alberto O. Mendelzon , Yehoshua Sagiv, Testing implications of data dependencies, ACM Transactions on Database Systems (TODS), v.4 n.4, p.455-469, Dec. 1979 [doi>10.1145/320107.320115]
• 19: Edward Sciore, Improving semantic specification in a relational database, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582124]
• 20: Dionysios C. Tsichritzis , Frederick H. Lochovsky, Data Models, Prentice Hall Professional Technical Reference, 1982
• 21: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 22: Yannis Vassiliou, A formal treatment of imperfect information in database management, 1980

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Normal forms

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema

General Terms:
Theory

Keywords:
functional dependencies, tableaux