Designing globally consistent network schemas

ABSTRACT

In this paper we address several problems relating to functional dependencies and network schemas. We investigate properties of the functional dependencies that are implicitly defined in a network schema. A definition for the satisfaction of functional dependencies by a network database is proposed, and then we give a sufficient condition for the global consistency of a network schema. A network schema is globally consistent if all its databases satisfy the functional dependencies that are implicitly defined in the schema. Finally, we describe a design methodology for producing a network schema whose set of implicitly defined functional dependencies implies a set of functional dependencies specified by the user.

REFERENCES

• 1: Charles W. Bachman, Data structure diagrams, ACM SIGMIS Database, v.1 n.2, p.4-10, Summer 1969 [doi>10.1145/1017466.1017467]
• 2: 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]
• 3: 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]
• 4: Peter Pin-Shan Chen, The entity-relationship model—toward a unified view of data, ACM Transactions on Database Systems (TODS), v.1 n.1, p.9-36, March 1976 [doi>10.1145/320434.320440]
• 5: {CKPS} Chen, H.-H., S. Kuck, J. Peterson and Y. Sagiv, "A User's Manual for AURICAL: A Universal Relation Implementation via Codasyl," UIUCDCS-R-82-1114, Dept. of Computer Science, Univ. of IL at Urbana-Champaign, Urbana, IL, Dec. 1982.
• 6: {CODA} "CODASYL Data Description Language Journal of Development," Government Printing Office, Wash., D.C., June, 1973.
• 7: 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]
• 8: Ronald Fagin , Alberto O. Mendelzon , Jeffrey D. Ullman, A simplied universal relation assumption and its properties, ACM Transactions on Database Systems (TODS), v.7 n.3, p.343-360, Sept. 1982 [doi>10.1145/319732.319735]
• 9: 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]
• 10: 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]
• 11: {Kuck} Kuck, S. M., "A Design Methodology for a Universal Relation Scheme Implementation via CODASYL," UIUCDCS-R-82-1106, Dept. of Computer Science, Univ. of IL at Urbana-Champaign, Urbana, IL, Sept. 1982.
• 12: Sharon McCure Kuck , Yehoshua Sagiv, A universal relation database system implemented via the network model, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588135]
• 13: Y. Edmund Lien, On the Equivalence of Database Models, Journal of the ACM (JACM), v.29 n.2, p.333-362, April 1982 [doi>10.1145/322307.322311]
• 14: 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]
• 15: {MUV} Maier, D., J. D. Ullman and M. Y. Vardi, "The Equivalence of Universal Relation Definitions," unpublished manuscript.
• 16: {Nava} Navathe, S. B., "An Intuitive Approach to Normalize Network Structured Data," Proc. Int. Conf. on Very Large Data Bases, 1980, pp.350--358.
• 17: Yehoshua Sagiv, Can we use the universal instance assumption without using nulls?, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582336]
• 18: Yehoshua Sagiv, A characterization of globally consistent databases and their correct access paths, ACM Transactions on Database Systems (TODS), v.8 n.2, p.266-286, June 1983 [doi>10.1145/319983.319988]
• 19: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 20: Eugene Wong , Randy H. Katz, Logical Design and Schema Conversion for Relational and DBTG Databases, Proceedings of the 1st International Conference on the Entity-Relationship Approach to Systems Analysis and Design, p.311-322, January 1980
• 21: 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]