Relations with relation names as arguments: algebra and calculus

ABSTRACT

We consider a version of the relational model in which relation names may appear as arguments of other relations. Allowing relation names as arguments provides enhanced modelling capabilities, allowing some object-oriented features to be expressed within the relational model. We extend relational algebra with operators for accessing relations, and also define a relational calculus based on the logic HiLog. We prove two equivalence results between extensions of relational algebra provide higher expressive power than relational algebra on any given database. Finally, we argue that the extensions proposed here are relatively easy to provide in practice, and should be expressible within modern query languages.

REFERENCES

• C+76: D.D. Chamberlin et al. SEQUEL 2: A unified approach to data definition, manipulation and control. IBM Journal of Research and Develipment, 20(6):560- 575, 1976.
• CKW89: W. Chen, M. Kifer, and D. S. Warren. ttiLog: A first order semantics for higher-order logic programming constructs. In Proc. Norih American Logic Programming Conference, 1989.
• Cod70: 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]
• Cod72: E. F. Codd. Relational completeness of data base sublanguages. Data Base Systems, pages 65-98, 1972.
• DiP69: Robert A. Di Paola, The Recursive Unsolvability of the Decision Problem for the Class of Definite Formulas, Journal of the ACM (JACM), v.16 n.2, p.324-327, April 1969 [doi>10.1145/321510.321524]
• Klu82: Anthony Klug, Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions, Journal of the ACM (JACM), v.29 n.3, p.699-717, July 1982 [doi>10.1145/322326.322332]
• PDR91: Geoffrey Phipps , Marcia A. Derr , Kenneth A. Ross, Glue-Nail: a deductive database system, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.308-317, May 29-31, 1991, Denver, Colorado, United States
• Ros91: Kenneth A. Ross, On negation in HiLog (extended abstract), Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.206-215, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113432]
• SS77: 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]
• Ull89: J.D. V11m n. of Knowledge Base Systems. Computer Science Press, Rockville, MD, 1989. (Two volumes).

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Data manipulation languages (DML); Query languages

General Terms:
Languages