Synthesizing independent database schemas

ABSTRACT

We study the following database design problem. Given a universal relation scheme 〈U, F〉 where F is a set of functional dependencies, find an in some way normalized database schema D = {〈X1, F1〉,..., 〈Xn, Fn〉} where Xi ⊂ U and Fi is inherited from F, such that D is an independent representation of the universal scheme 〈U, F〉. This means that D has both the lossless join property and the faithful closure property, (***** Fi)⁺ = F⁺, where ⁺ denotes the closure of a set of functional dependencies. We show that this goal can easily be achieved by an extension of the well-known synthetic approach of Bernstein and others to database design. We merely have to check whether the usual synthesis procedure has produced a key component 〈Xi, Fi〉 such that Xi → U ε F⁺; in case this is true the output of the synthesis procedure is actually an independent (and not only faithful) representation, otherwise we only have to add one further component, namely just a key. These claims are proved by a careful inspection of the Aho/Beeri/Ullman algorithm to test for losslessness. Finally, we show how to use our method to synthesize minimal independent third normal form schemas.

REFERENCES

• 1: Aho, A.V., Beeri, C., and Ullman, J.D. The theory of joins in relational data bases. Proc. 18th IEEE Symp. on Foundations of Computer Science, Oct. 1977, pp.107--113.
• 2: Catriel Beeri , Philip A. Bernstein, Computational problems related to the design of normal form relational schemas, ACM Transactions on Database Systems (TODS), v.4 n.1, p.30-59, March 1979 [doi>10.1145/320064.320066]
• 3: Beeri, C., Bernstein, P.A., and Goodman, N. A sophisticate's introduction to database normalization theory. Proc. 4th Int. Conf. on Very Large Data Bases, Berlin, Sep. 1978, pp. 113--124.
• 4: Catriel Beeri , Ronald Fagin , John H. Howard, A complete axiomatization for functional and multivalued dependencies in database relations, Proceedings of the 1977 ACM SIGMOD international conference on Management of data, August 03-05, 1977, Toronto, Ontario, Canada [doi>10.1145/509404.509414]
• 5: 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]
• 6: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 7: Codd, E.F. Further normalization of the data base relational model. In Courant Computer Science Symposia 6: Data Base Systems. Prentice Hall, Englewood Cliffs, N.J., 1971, pp. 33--64.
• 8: Dayal, U., and Bernstein, P.A. The fragmentation problem: lossless decomposition of relations into files. Technical Report TR-78-13, Computer Corporation of America, Cambridge, Mass., (Nov. 1978).
• 9: Fagin, R. Functional dependencies in a relational database and propositional logic. IBM Journal of Research and Development 21,6 (Nov. 1977), pp. 534--544.
• 10: Ronald Fagin, Multivalued dependencies and a new normal form for relational databases, ACM Transactions on Database Systems (TODS), v.2 n.3, p.262-278, Sept. 1977 [doi>10.1145/320557.320571]
• 11: Jorma Rissanen, Independent components of relations, ACM Transactions on Database Systems (TODS), v.2 n.4, p.317-325, Dec. 1977 [doi>10.1145/320576.320580]
• 12: Rissanen, J. Theory of relations for databases --- a tutorial survey. Proc. 7th Symp. on Mathematical Foundations of Computer Science, Zakopane, 1978. Lecture Notes in Computer Science 64, Springer-Verlag, Berlin-Heidelberg-New York, 1978, pp. 536--551.
• 13: Carlo Antonio Zaniolo, Analysis and design of relational schemata for database systems., 1976
• 14: Zaniolo, C., Melkanoff, M.A. Relational schemas for data base systems. Technical Report UCLA-ENG-7801, UCLA, Jan. 1978.