Algebraic aspects of relational database decomposition

ABSTRACT

An algebraic framework for investigating the problem of decomposing a relational database schema into components is developed. It is argued that the views of a relational schema which are to be the components of a decomposition should form a finite atomic Boolean algebra. The unit of the algebra is the identity view, and the zero is the null view. The join operation in this algebra is to be a generalization of the usual concept of join; the resulting view should contain precisely the representation contained in the two component views as a unit. The meet operation in this algebra is to measure the interdependence of the components, and is to be zero if and only if they are independent. A decomposition of the schema is then to be a decomposition of the identity component, with the ultimate decomposition the one consisting entirely of atoms.The thrust of the results is in two directions. First, the general properties of relational schemata particular to this problem are developed, within the framework of first-order logic. The key formulations are those of abstract meet and join of schemata. Using these formulations, it is shown that a completely general decomposition theory is impossible. The second part of the work islolates a relatively large class of schemata which do admit reasonable decompositions. These schemata include all of the usual decomposition problems, including project-join decompositions and horizontal decompositions of schemata constrained by universal Horn sentences.

REFERENCES

• 1: A. V. Aho , C. Beeri , J. D. Ullman, The theory of joins in relational databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.297-314, Sept. 1979 [doi>10.1145/320083.320091]
• 2: {ArCa78} Arora, A K, and C R Carlson, "The information preservation properties of relational database transformations", Proc 1978 VLDB Conf, pp 352-359
• 3: {BaSp81} Bancilhon, F and N Spyratos, "Independent components of databases", Proc 1981 VLDB Conf, pp 398-408
• 4: {BeBG78} Beeri, C, P A Bernstein, and N Goodman, "A sophisticate's introduction to database normalization theory", Proc 1978 VLDB Conf, pp 113-124
• 5: {BeRi80} Beeri, C, and J Rissanen, Faithful Representation of Relational Database Schemes IBM Research Report RJ2722, 1980
• 6: {BeVa81} Beeri, C, and M Vardi, "On the properties of join dependencies", in Advances in Data Base Theory, Vol 1 ed by H Gallaire, J Minker, and J M Nicolas, Plenum Press, 1981, pp 25-71
• 7: {Birk67} Birkhoff G, Lattice Theory, Third Edition, American Mathematical Society, 1967
• 8: Marco A. Casanova , Ronald Fagin , Christos H. Papadimitriou, Inclusion dependencies and their interaction with functional dependencies, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588141]
• 9: {Ende72} Enderton, H B, A Mathematical Introduction to Logic, Academic Press, 1972
• 10: Ronald Fagin, Horn clauses and database dependencies, Journal of the ACM (JACM), v.29 n.4, p.952-985, Oct. 1982 [doi>10.1145/322344.322347]
• 11: {Grat78} Gratzer, G General Lattice Theory, Academic Press, 1978
• 12: Marc H. Graham , Mihalis Yannakakis, Independent database schemas, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588144]
• 13: {Gran82} Grant, J, Adequate Database Transformations, TR-1145, Towson State University, February 1982
• 14: John Grant , Barry E. Jacobs, On the family of generalized dependency constraints, Journal of the ACM (JACM), v.29 n.4, p.986-997, Oct. 1982 [doi>10.1145/322344.322348]
• 15: {Halm74} Halmos, P R, Lectures on Boolean Algebras Springer-Verlag, 1974
• 16: {Jaco79} Jacobs, B E, Applications of Database Logic to Conceptual and External View Protection, U of Md Comp Sci Tech Report 815, Sept 1979
• 17: Barry E. Jacobs, On Database Logic, Journal of the ACM (JACM), v.29 n.2, p.310-332, April 1982 [doi>10.1145/322307.322310]
• 18: Barry E. Jacobs , Anthony C. Klug , Alan R. Aronson, On interpretations of relational languages and solutions to the implied constraint problem, ACM Transactions on Database Systems (TODS), v.7 n.2, p.291-315, June 1982 [doi>10.1145/319702.319730]
• 19: W. Kent, Consequences of assuming a universal relation, ACM Transactions on Database Systems (TODS), v.6 n.4, p.539-556, Dec. 1981 [doi>10.1145/319628.319630]
• 20: {Lien79} Lien, Y E, "Multivalued dependencies with null values in relational databases", Proc 1919 VLDB Conf, pp 61-66
• 21: {McMi79} McSkimin J R and J Minker, "A predicate calculus based semantic network for deductive searching", in Associative Netowrks, ed by N V Findler, Academic Press, 1979 pp 205-238
• 22: 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]
• 23: {MMSU81} Maier, D, A O Mendelzon, F Sadri, and J D Ullman, "Adequacy of decompositions of relational databases", in Advances in Data Base Theory, Vol 1, ed by H Gallaire J Minker, and J M Nicolas, Plenum Press, 1981, pp 101-114
• 24: {Monk76} Monk, J D, Mathematical Logic, Springer-Verlag 1976
• 25: Raymond Reiter, Equality and Domain Closure in First-Order Databases, Journal of the ACM (JACM), v.27 n.2, p.235-249, April 1980 [doi>10.1145/322186.322189]
• 26: 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]
• 27: Fereidoon Sadri , Jeffrey D. Ullman, Template Dependencies: A Large Class of Dependencies in Relational Databases and Its Complete Axiomatization, Journal of the ACM (JACM), v.29 n.2, p.363-372, April 1982 [doi>10.1145/322307.322312]
• 28: {Scio80} Sciore, E, The Universal Instance and Database Design, TR #271 Princeton University, 1980
• 29: Edward Sciore, A Complete Axiomatization of Full Join Dependencies, Journal of the ACM (JACM), v.29 n.2, p.373-393, April 1982 [doi>10.1145/322307.322313]
• 30: John Miles Smith , Diane C. P. Smith, Database abstractions: aggregation and generalization, ACM Transactions on Database Systems (TODS), v.2 n.2, p.105-133, June 1977 [doi>10.1145/320544.320546]
• 31: {Smit78} Smith, J M, "A normal form for abstract syntax", Proc 1978 VLDB Conf, pp 156-162
• 32: {Ullm80} Ullman, J D, Principles of Database Systems, Computer Science Press, 1980
• 33: Carlo Zaniolo, Database relations with null values, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588117]