The logical data model

ABSTRACT

We propose an object-oriented data model that generalizes the relational, hierarchical, and network models. A database scheme in this model is a directed graph, whose leaves represent data and whose internal nodes represent connections among the data. Instances are constructed from objects, which have separate names and values. We define a logic for the model, and describe a nonprocedural query language that is based on the logic. We also describe an algebraic query language and show that it is equivalent to the logical language.

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: ABITEBOUL, S., AND BEERI, C. On the power of languages for the manipulation of complex objects. Tech. Rep. 846, INRIA, 1988.
• 3: Serge Abiteboul , Paris C. Kanellakis, Object identity as a query language primitive, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.159-173, June 1989, Portland, Oregon, United States
• 4: Serge Abiteboul , Stéphane Grumbach, A rule-based language with functions and sets, ACM Transactions on Database Systems (TODS), v.16 n.1, p.1-30, March 1991 [doi>10.1145/103140.103141]
• 5: ACZEL, P. Non-Well-Founded Sets. Stanford University, Center for Study of Language and Information Lecture Notes, no. 14, 1988.
• 6: 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]
• 7: François Banciihon, Object-oriented database systems, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.152-162, March 1988, Austin, Texas, United States [doi>10.1145/308386.308429]
• 8: Francois Bancilhon , Setrag Khoshafian, A calculus for complex objects, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.53-60, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15404]
• 9: C. Beeri , S. Naqvi , R. Ramakrishnan , O. Shmueli , S. Tsur, Sets and negation in a logic data base language (LDL1), Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.21-37, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28662]
• 10: Francois Bancilhon , Raghu Ramakrishnan, An amateur's introduction to recursive query processing strategies, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.16-52, May 28-30, 1986, Washington, D.C., United States
• 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: Umeshwar Dayal , Philip A. Bernstein, On the correct translation of update operations on relational views, ACM Transactions on Database Systems (TODS), v.7 n.3, p.381-416, Sept. 1982 [doi>10.1145/319732.319740]
• 14: Antonio L. Furtado , Larry Kerschberg, An algebra of quotient relations, Proceedings of the 1977 ACM SIGMOD international conference on Management of data, August 03-05, 1977, Toronto, Ontario, Canada [doi>10.1145/509404.509406]
• 15: FISCHER, P. C., AND THOMAS, S.J. Operators for non-first-normal-form relations. In Proceedings of the IEEE Computer Software Applications Conference (1983), 464-475.
• 16: Dipayan Gangopadhyay , Umeshwar Dayal , James C. Browne, Semantics of Network Data Manipulation Languages: An Object-Oriented Approach, Proceedings of the 8th International Conference on Very Large Data Bases, p.357-369, September 08-10, 1982
• 17: GRAHAM, M. H. NETS: operations and logic. In A Panache of DBMS Ideas H, F. H. Lochovsky, Ed., 152 179. Tech. Rep. CSRG-101, Computer Systems Research Group, Univ. of Toronto, 1979.
• 18: Hm~DGRAVE, W. T. Ambiguity in processing boolean queries on TDMS tree-structures: A study of four different philosophies. Tech. Rep. IFSM TR-35, Univ. of Maryland, 1978.
• 19: R. Hull, A survey of theoretical research on typed complex database objects, Databases, Academic Press Ltd., London, UK, 1988
• 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: 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]
• 22: Lawrence J. Henschen , Shamim A. Naqvi, On compiling queries in recursive first-order databases, Journal of the ACM (JACM), v.31 n.1, p.47-85, Jan. 1984 [doi>10.1145/2422.2423]
• 23: HULL, R, AND SU, J. Domain independence and the relational calculus. Tech. Rep. 88-64. Univ. of Southern California, 1989.
• 24: 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]
• 25: JACOBS, B.E. Application of database logm to database design. Tech. Rep TR-892, Univ. of Maryland at College Park, 1979.
• 26: 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]
• 27: G. Jaeschke , H. J. Schek, Remarks on the algebra of non first normal form relations, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588133]
• 28: Michael Kifer , Georg Lausen, F-logic: a higher-order language for reasoning about objects, inheritance, and scheme, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.134-146, June 1989, Portland, Oregon, United States
• 29: KOBAYASHI, I An overview of the database management technology Tech. Rep. TRCS-4-1, Sanno College, Kanagawa, Japan, 1980, 259-11.
• 30: Mark A. Roth , Henry F. Korth , Avi Silberschatz, Extended Algebra and Calculus for ~1NF Relational Databases, University of Texas at Austin, Austin, TX, 1984
• 31: Gabriel Mark Kuper, The logical data model: a new approach to database logic, Stanford University, Stanford, CA, 1986
• 32: Gabriel M. Kuper , Moshe Y. Vardi, A new approach to database logic, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588026]
• 33: Gabriel M. Kuper , Moshe Y. Vardi, On the expressive power of the logical data model: prelimiary report, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.180-187, May 1985, Austin, Texas, United States
• 34: G. M. Kuper , M. Y. Vardi, On the complexity of queries in the logical data model, Lecture notes in computer science on ICDT '88, p.267-280, October 1988, Bruges, Belgium
• 35: Gabriel M. Kuper, Logic programming with sets, Journal of Computer and System Sciences, v.41 n.1, p.44-64, August 1990 [doi>10.1016/0022-0000(90)90033-H]
• 36: MAIEI~, D. A logic for objects. In Proceedzngs of the Workshop on Foundatzons of Deductive Databases and Logw Programmlng (Washington, D.C., 1986).
• 37: MAKINOUCHI, A. A consideration on normal form of not-necessarily normalized relations in the relational data model. In Proceedings of the Thtrd Internattonal Conference on Very Large Data Bases (Tokyo, 1977), IEEE, 447 453.
• 38: Frank Manola , Alain Pirotte, CQLF---a query language for CODASYL-type databases, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582369]
• 39: G. Özsoyoğlu , Z. M. Özsoyoğlu , V. Matos, Extending relational algebra and relational calculus with set-valued attributes and aggregate functions, ACM Transactions on Database Systems (TODS), v.12 n.4, p.566-592, Dec. 1987 [doi>10.1145/32204.32219]
• 40: Z. Meral Özsoyoglu , Li-Yan Yuan, A normal form for nested relations, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.251-260, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325451]
• 41: Joan Peckham , Fred Maryanski, Semantic data models, ACM Computing Surveys (CSUR), v.20 n.3, p.153-189, Sept. 1988 [doi>10.1145/62061.62062]
• 42: REITER, R. Deductive question answering in relational databases. In Logzc and Databases, H. Gallaire and J. Minker, Eds., Plenum Press, 1978, 147-177.
• 43: RAFANELLI, M., AND RICCI, F.L. A data definition language for a statistical database. Tech. Rep. TR-62, IASI-CNR, July 1983.
• 44: 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]
• 45: Hans-Jörg Schek , Peter Pistor, Data Structures for an Integrated Data Base Management and Information Retrieval System, Proceedings of the 8th International Conference on Very Large Data Bases, p.197-207, September 08-10, 1982
• 46: 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]
• 47: Dionysios C. Tsichritzis , Frederick H. Lochovsky, Data Models, Prentice Hall Professional Technical Reference, 1982
• 48: D. Tsichritzis, LSL: a Link and Selector Language, Proceedings of the 1976 ACM SIGMOD international conference on Management of data, June 02-04, 1976, Washington, D.C.
• 49: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 50: Jeffrey D. Ullman, Implementation of logiclal query languages for databases (abstract only), ACM SIGMOD Record, v.14 n.4, p.444, May 1985
• 51: 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]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Design, Languages, Theory

Keywords:
Algebra, database schema, logic, relational database, tuple calculus