IFO: a formal semantic database model

ABSTRACT

A new, formally defined database model is introduced that combines fundamental principles of “semantic” database modeling in a coherent fashion. Using a graph-based formalism, the IFO model provides mechanisms for representing structured objects, and functional and ISA relationships between them. A number of fundamental results concerning semantic data modeling are obtained in the context of the IFO model. Notably, the types of object structure that can arise as a result of multiple uses of ISA relationships and object construction are described. Also, a natural, formal definition of update propagation is given, and it is shown that (under certain conditions) a correct update always exists.

REFERENCES

• 1: Serge Abiteboul , Nicole Bidoit, Non first normal form relations: An algebra allowing data restructuring, Journal of Computer and System Sciences, v.33 n.3, p.361-393, Dec. 1986 [doi>10.1016/0022-0000(86)90058-9]
• 2: Serge Abiteboul , Richard Hull, IFO: a formal semantic database model, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588029]
• 3: Serge Abiteboul , Richard Hull, Restructuring hierarchical database objects, Theoretical Computer Science, v.62 n.1-2, p.3-38, December 1988 [doi>10.1016/0304-3975(86)90010-1]
• 4: ABRIAL, J.R. Data semantics. In Data Base Management, North-Holland, Amsterdam, 1974, 1-59.
• 5: Paolo Atzeni , Douglas Stott Parker, Jr., Formal Properties of Net-Based Knowledge Representation Schemes, Proceedings of the Second International Conference on Data Engineering, p.700-706, February 05-07, 1986
• 6: BANClLHON, F. ET AL. Verso: A relational back end data base machine. In Advanced Database Machine Architecture, D. K. Hsiao, Ed. Prentice-Hall, Englewood Cliffs, N.J., 1983.
• 6a: C. Batini , M. Lenzerini , S. B. Navathe, A comparative analysis of methodologies for database schema integration, ACM Computing Surveys (CSUR), v.18 n.4, p.323-364, Dec. 1986 [doi>10.1145/27633.27634]
• 7: BOUZEGHOUB, M. MORSE: A functional query language built on a semantic network. SABRE Project, INRIA and Univ. of Paris VI, Rocquencourt, France, Dec. 1983.
• 8: BRODIE, M. L., AND RIDJANOVIC, D. On the design and specification of database transactions. In On Conceptual Modelling. Brodie, Mylopoulus, and Schmidt, Eds., Springer-Verlag, New York, 1984, 277-306.
• 9: Robert Brown , Douglas Stott Parker, Jr., LAURA: A Formal Data Model and her Logical Design Methodology, Proceedings of the 9th International Conference on Very Large Data Bases, p.206-218, October 31-November 02, 1983
• 10: Daniel Bryce , Richard Hull, SNAP: A Graphics-based Schema Manager, Proceedings of the Second International Conference on Data Engineering, p.151-164, February 05-07, 1986
• 11: Peter Buneman , Robert E. Frankel , Rishiyur Nikhil, An implementation technique for database query languages, ACM Transactions on Database Systems (TODS), v.7 n.2, p.164-186, June 1982 [doi>10.1145/319702.319711]
• 12: CASANOVA, M. A., FAGIN, R., AND PAPADIMITRIOU, C.H. Inclusion dependencies and their interaction with functional dependencies. J. Comput. Syst. Sci. 28, 1 (1984), 29-59.
• 13: 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]
• 14: 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]
• 15: 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]
• 16: DAYAL, U., AND HWANt;, H.-Y. View definition and generalization for database integration in a multidatabase system. IEEE Trans. Softw. Eng. SE-IO, 6 {1984), 628-644.
• 17: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 18: Michael Hammer , Dennis Mc Leod, Database description with SDM: a semantic database model, ACM Transactions on Database Systems (TODS), v.6 n.3, p.351-386, Sept. 1981 [doi>10.1145/319587.319588]
• 19: HECHT, M. S., AND KERSCHBERG, L. Update semantics for the functional data model. Bell Laboratories, Holmdel, N.J., Jan. 1981.
• 20: Richard Hull , Roger King, Semantic database modeling: survey, applications, and research issues, ACM Computing Surveys (CSUR), v.19 n.3, p.201-260, Sept. 1987 [doi>10.1145/45072.45073]
• 21: Richard Hull , Chee K. Yap, The Format Model: A Theory of database Organization, Journal of the ACM (JACM), v.31 n.3, p.518-544, July 1984 [doi>10.1145/828.832]
• 22: KENT, W. Data and Reality. North-Holland, Amsterdam, 1978.
• 23: William Kent, Limitations of record-based information models, ACM Transactions on Database Systems (TODS), v.4 n.1, p.107-131, March 1979 [doi>10.1145/320064.320070]
• 24: KERSCHBERG, L., AND PACHECO, J. E. S. A functional data base model. Pontificia Univ. Catolica do Rio de Janeiro, Rio de Janeiro, Brazil, Feb. 1976.
• 25: KING, R., AND MCLEOD, D. The event database specification model. In Proceedings of the 2nd International Conference on Databases: Improving Usability and Responsiveness (Jerusalem, June 1982), Academic Press, New York, 1982, 299-321.
• 26: Roger King , Dennis McLeod, A database design methodology and tool for information systems, ACM Transactions on Information Systems (TOIS), v.3 n.1, p.2-21, Jan. 1985 [doi>10.1145/3864.3869]
• 27: KING, R., AND MCLEOD, D. Semantic database models. In Database Design, S. B. Yao, Ed., Springer-Verlag, New York, 1985, 115-150.
• 28: Dennis McLeod , John Miles Smith, Abstraction in databases, Proceedings of the 1980 workshop on Data abstraction, databases and conceptual modeling, p.19-25, June 23-26, 1980, Pingree Park, Colorado, United States
• 29: Amihai Motro , Peter Buneman, Constructing superviews, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582327]
• 30: John Mylopoulos , Philip A. Bernstein , Harry K. T. Wong, A language facility for designing database-intensive applications, ACM Transactions on Database Systems (TODS), v.5 n.2, p.185-207, June 1980 [doi>10.1145/320141.320150]
• 31: David W. Shipman, The functional data model and the data languages DAPLEX, ACM Transactions on Database Systems (TODS), v.6 n.1, p.140-173, March 1981 [doi>10.1145/319540.319561]
• 32: SMITH, J. M., Fox, S., AND LANDERS, T. Reference Manual for ADAPLEX. Computer Corporation of America, Cambridge, Mass., 1981.
• 33: 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]
• 34: St), S. Y.W. SAM*: A semantic association model for corporate and scientific-statistical databases. Inf. Sci. 29 (1983), 151-199.
• 35: Dionysios C. Tsichritzis , Frederick H. Lochovsky, Data Models, Prentice Hall Professional Technical Reference, 1982
• 36: Gio Wiederhold , Ramez Elmasri, The Structural Model for Database Design, Proceedings of the 1st International Conference on the Entity-Relationship Approach to Systems Analysis and Design, p.237-258, January 1980
• 37: ZLOOF, M. Query-by-example: A database language. IBM Syst. J. 16 (1977), 324-343.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Semantic networks

General Terms:
Algorithms, Design, Theory, Verification