The theory of joins in relational databases

ABSTRACT

Answering queries in a relational database often requires that the natural join of two or more relations be computed. However, the result of a join may not be what one expects. In this paper we give efficient algorithms to determine whether the join of several relations has the intuitively expected value (is lossless) and to determine whether a set of relations has a subset with a lossy join. These algorithms assume that all data dependencies are functional. We then discuss the extension of our techniques to the case where data dependencies are multivalued.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	ARMSTRONG, W.W. Dependency structures of data base relationships. Information Processing 74, North-Holland Pub. Co., Amsterdam, 1974, pp. 580-583.
	3	ARORA, A.K., AND CARLSON, C.R. The information preserving properties of relational database transformations. Proc. Int. Conf. on Very Large Data Bases, West Berlin, Sept. 1978, pp. 352-359.
	4	BEF.RI, C. On the membership problem for multivalued dependencies in relational database systems. Tech. Rep. 229, Dept. Elec. Eng. and Comptr. Sci., Princeton U., Princeton, N.J., Sept. 1977. To appear in A CM Trans. Database Syst.
	5	BEERI, C., BERNSTEIN, P.A., AND GOODMAN, N. A sophisticate's introduction to database normalization theory. Proc. Int. Conf. on Very Large Data Bases, West Ber!in, Sept. 1978, pp. 113-124.
	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 BEERI, C. An algorithmic approach to normalization of relational database schemas. Tech. Rep. CSRG-73, Comptr. Sci. Res. Group, U. of Toronto, Toronto, Canada, Sept. 1976.
	8	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]
	9	C. Robert Carlson , Robert S. Kaplan, A generalized access path model and its application to a relational data base system, Proceedings of the 1976 ACM SIGMOD international conference on Management of data, June 02-04, 1976, Washington, D.C.
	10	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]
	11	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.
	12	CODD, E.F. Recent investigations in relational data base systems. Information Processing 74, North-Holland Pub. Co., Amsterdam, 1974, pp. 1017-1021.
	13	DELOBEL, C. Contributions theoretiques a la conception d'un systeme d'informations. Ph.D. Th., U. of Grenoble, Grenoble, France, Oct. 1973.
	14	DELOBEL, C., AND CASEY, R.G. Decomposition of a data base and the theory of Boolean switching functions. IBM J. Res. and Develop. 17, 5 (Sept. 1972), 370-386.
	15	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]
	16	GUTHERY, S.B., AND O'NEILL, D.M. The syntax and semantics of functional dependency. Unpub. memo., Bell Laboratories, Holmdel, N.J., 1976.
	17	MAIER, D., MENDELZON, A.O., SADRI, F., AND ULLMAN, J.D. Adequacy of decompositions of relational databases. Dept. Elec. Eng. and Comptr. Sci., Princeton University, Princeton, N.J., 1979.
	18	MANACHER, G.K. On the feasibility of implementing a large relational data base with optimal performance on a minicomputer. Proc. Int. Conf. on Very Large Data Bases, Framingham, Mass., Sept. 1975, pp. 175-201.
	19	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]
	20	TARJAN, R.E. Depth-first search and linear graph algorithms. SIAM J. Comptng. 1, 2 (1972), 146-160.
	21	ZANIOLO, C. Analysis and design of relational schemata for database systems. Tech. Rep. UCLA- ENG-7769, Dept. Comptr. Sci., U. of California, Los Angeles, Calif., July 1976.