Can we use the universal instance assumption without using nulls?

ABSTRACT

We claim that the representative instance of [Ho1, Va3] is a correct representation of the data stored in a database even when the relations of the database are not the projections of a single universal instance. If no constraint (other than functional and join dependencies) is imposed on the data, then projections of the representative instance cannot always be computed by lossless joins. We show that if the database satisfies a modified foreign-key constraint, then projections of the representative instance can be computed by performing the union of several lossless joins. A class of relation schemes for which no constraint is necessary is characterized, and we show how to compute projections of the representative instance for databases that belong to this class.

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: {ASU1} Aho, A. V., Y. Sagiv, and J. D. Ullman, "Equivalences Among Relational Expressions," SIAM J. Computing, Vol. 8, No. 2 (May 1979), pp. 218--246.
• 3: A. V. Aho , Y. Sagiv , J. D. Ullman, Efficient optimization of a class of relational expressions, ACM Transactions on Database Systems (TODS), v.4 n.4, p.435-454, Dec. 1979 [doi>10.1145/320107.320112]
• 4: {Arm} Armstrong, W. W., "Dependency Structures of Database Relationships," Proc. IFIP 74, North Holland, 1974, pp. 580--583.
• 5: 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]
• 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: 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]
• 8: Catriel Beeri , Alberto O. Mendelzon , Yehoshua Sagiv , Jeffrey D. Ullman, Equivalence of relational database schemes, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.319-329, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804424]
• 9: {BG} Bernstein, P. A., and N. Goodman, "What Does Boyce-Codd Normal Form Do?," Proc. Int. Conf. on Very Large Data Bases, 1980, pp. 245--259.
• 10: 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]
• 11: 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]
• 12: E. F. Codd, Extending the database relational model to capture more meaning, ACM Transactions on Database Systems (TODS), v.4 n.4, p.397-434, Dec. 1979 [doi>10.1145/320107.320109]
• 13: 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]
• 14: {FMU} Fagin, R., A. O. Mendelzon, and J. D. Ullman, "A Simplified Universal Relation Assumption and Its Properties," IBM research report, RJ2900, Nov., 1980.
• 15: {Ho1} Honeyman, P., "Testing Satisfaction of Functional Dependencies," Proc. XP1 Conf., Stonybrook, N. Y., June, 1980.
• 16: {Ho2} Honeyman, P., "Extension Joins," Proc. Int. Conf. on Very Large Data Bases, 1980, pp. 239--244.
• 17: {HLY} Honeyman, P., R. E. Ladner, and M. Yannakakis, "Testing the Universal Instance Assumption," Information Processing Letters, Vol. 10, No. 1 (Feb. 1980), pp. 14--19.
• 18: {Ko} Korth, H. F., "A Proposal for the SYSTEM/U Query Language," unpublished memorandum, Stanford University, Stanford, CA, 1980.
• 19: {KU} Korth, H. F. and J. D. Ullman, "System/U: a Database System Based on the Universal Relation Assumption," Proc. XP1 Conf., Stonybrook, N. Y., June, 1980.
• 20: {KS} Kuck, S. M., and Y. Sagiv, "A Universal Relation Interface for Network Schemas," in preparation.
• 21: {Li} Lien, Y. E., "Multivalued Dependencies With Null Values in Relational Databases," Proc. Int. Conf. on Very Large Data Bases, 1979.
• 22: {Ma} Maier, D., "Discarding the Universal Instance Assumption: Preliminary Results," Proc. XP1 Conf., Stonybrook, N. Y., June, 1980.
• 23: 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]
• 24: {Ris} Rissanen, J., "Theory of Relations for Databases --- A Tutorial Survey," Proc. 7th Symp. on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 64, Springer-Verlag, 1978, pp. 536--551.
• 25: {Sag} Sagiv, Y., manuscript in preparation.
• 26: Edward Sciore, The universal instance and database design, 1980
• 27: John Miles Smith , Diane C. P. Smith, Database abstractions: aggregation, Communications of the ACM, v.20 n.6, p.405-413, June 1977 [doi>10.1145/359605.359620]
• 28: {Va1} Vassiliou, Y., "Functional Dependencies and Incomplete Information," Proc. Int. Conf. on Very Large Data Bases, 1980, pp. 260--269.
• 29: {Va2} Vassiliou, Y. and F. H. Lochovsky, "DBMS Transaction Translation," Proc. COMPSAC 80, Oct., 1980.
• 30: {Va3} Vassiliou, Y., "A Formal Treatment of Imperfect Information in Database Management," Technical Report CSRG-123, University of Toronto, Nov., 1980.
• 31: {Za1} Zaniolo, C., "Analysis and Design of Relational Schemata for Database Systems," Tech. Rep. UCLA-ENG-7669, Dept. of Comp. Sci., UCLA, July 1976.
• 32: Carlo Zaniolo, Design of relational views over network schemas, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582126]