The Format Model: A Theory of database Organization

ABSTRACT

A mathematical theory for the study of data representation in databases is introduced and developed. The theory focuses on three data constructs (collection, composition and classification). "Formats" with semantically rich yet tractable structure are built recursively using these constructs. Using formats, we obtain several nontrivial results concerning notions of relative information capacity and restructuring of data sets. As such, the format model provides a new approach for the formal study of the construction of "user views" and other data manipulations in databases.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
• 2: BORGIDA, A., AND MYLOPOULOS, J. Semantic modds in databases: Some formal aspects. Tech. Report, Dept. Computer Science, Univ. of Toronto, Toronto, Ont., Canada, July 1981.
• 3: 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]
• 4: José Mauro V. de Castilho , Marco A. Casanova , Antonio L. Furtado, A Temporal Framework for Database Specifications, Proceedings of the 8th International Conference on Very Large Data Bases, p.280-291, September 08-10, 1982
• 5: 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]
• 6: CHAMBERLIN, D. D., GRAY, J. N., AND TRAIGER, I. L. Views, authorization, and locking in a relational database system. In Proceedings of the AFIPS National Computer Conference (Anaheim, Calif., May 19-22), Vol. 44. AFIPS Press, Arlington, Va., 1975, pp. 425--430.
• 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: 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]
• 9: C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 10: C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 11: Claude Delobel, Normalization and hierarchical dependencies in the relational data model, ACM Transactions on Database Systems (TODS), v.3 n.3, p.201-222, Sept. 1978 [doi>10.1145/320263.320271]
• 12: HAMMER, M., AND MCLEOD, D.Semantic integrity in a relation data base system. In Proceedings of the 1st Rand and A CM-SIGBDP, SIGIR, SIGMOD International Conference on Very Large Data Bases (Framingham, Mass., Sept. 22-24). ACM, New York, 1975, pp. 25-47.
• 13: 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]
• 14: HENSON, C. W., AND RUBEL, L. A.Some applications of Nevanlinna theory to mathematical logic: ldenuties of exponential functions. Teeh. Report, Dept. Mathematics, Univ. of Illinois at Urbana-Champaign, July 1982.
• 15: HOARE, C. A. R.Notes on data structuring. In APIC Studies in Data Processing. No. 8: Structured Programming. Academic Press, New York, 1972, pp. 83-174.
• 16: KING, R., AND MCLFX)D, D.Semantic database models. To appear in Database Destgn, S. B. Yao, ed., 1984.
• 17: KING, R., AND McLEoD, D. The event database specification model. In Proceedings of the 2nd Internattonal Conference on Databases Improving Usabthty and Responsiveness (Jerusalem, Israel, June). Academic Press, New York, 1982, pp. 299-321.
• 18: 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]
• 19: 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]
• 20: UNLAING, C., AND YAP, C. K.Generic transformation of data structures, In Proceedings of the 23rd Annual Sympostum of Foundatlons of Computer Scwnce (Chicago, I11., Nov.). IEEE, New York, 1982, pp. 186-195.
• 21: Clesio Saraiva dos Santos , Erich J. Neuhold , Antonio L. Furtado, A Data Type Approach to the Entity-Relationship Approach, Proceedings of the 1st International Conference on the Entity-Relationship Approach to Systems Analysis and Design, p.103-119, January 1980
• 22: Hans Albrecht Schmid , J. Richard Swenson, On the semantics of the relational data model, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California [doi>10.1145/500080.500110]
• 23: 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]
• 24: 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]
• 25: 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]
• 26: Su, S. Y. W., AND LO, D. H.A semantic associaUon model for conceptual database design. In Proceedmgs of the International Conference on Enttty.Relatwnshlp Approach to Systems Analysis and Design (Los Angeles, Calif., Dec.). Elsevier-North Holland, New York, 1979, pp. 147-171.
• 27: Dionysios C. Tsichritzis , Frederick H. Lochovsky, Data Models, Prentice Hall Professional Technical Reference, 1982
• 28: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 29: YAO, S. B., WADDLE) V. AND HOUSEL, B. C.View modeling and mtegration using the fimotional data model. IEEE Trans. Softw. Eng SE-8, 6 (Nov. 1982), 544-553.

INDEX TERMS

Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Composite structures**

  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Information theory
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models; Schema and subschema

General Terms:
Design, Theory, Verification