Reflective programming in the relational algebra

ABSTRACT

In reflective programming languages it is possible for a program to generate code that is integrated into the program's own execution. We introduce a reflective version of the relational algebra. Reflection is achieved by storing and manipulating relational algebra programs as relations in the database. We then study the expressibility and complexity of the reflective algebra thus obtained. It turns out that there is a close correspondence between reflection and bounded looping. We also discuss the applicability of the reflective algebra.

REFERENCES

• AK89: Serge Abiteboul , Paris C. Kanellakis, Object identity as a query language primitive, ACM SIGMOD Record, v.18 n.2, p.159-173, June 1989
• AR89: Harvey Abramson , M. H. Rogers, Meta-programming in logic programming, MIT Press, Cambridge, MA, 1989
• CH80: A. Chandra and D. Harel. Computable queries for relational database systems. Journal of Computer and System Sciences, 21(2):156-178, 1980.
• Cha81: Ashok K. Chandra, Programming primitives for database languages, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.50-62, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567537]
• CLM89: Proceedings of the 1989 ACM SIGMOD international conference on Management of data, June 1989
• HS89: Richard Hull , Jianwen Su, On accessing object-oriented databases: expressive power, complexity, and restrictions, ACM SIGMOD Record, v.18 n.2, p.147-158, June 1989
• HY90: Richard Hull , Masatoshi Yoshikawa, ILOG: declarative creation and manipulation of object identifiers, Proceedings of the sixteenth international conference on Very large databases, p.455-468, September 1990, Brisbane, Australia
• KL89: Won Kim , F. H. Lochovsky, Object-oriented concepts, databases, and applications, ACM Press, New York, NY, 1989
• MN88: Pattie Maes , D. Nardi, Meta-Level Architectures and Reflection, Elsevier Science Inc., New York, NY, 1988
• Ros92: Kenneth A. Ross, Relations with relation names as arguments: algebra and calculus, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.346-353, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137905]
• S+84: Michael Stonebraker , Erika Anderson , Eric Hanson , Brad Rubenstein, QUEL as a data type, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• S+87: Michael Stonebraker , Jeff Anton , Eric Hanson, Extending a database system with procedures, ACM Transactions on Database Systems (TODS), v.12 n.3, p.350-376, Sept. 1987 [doi>10.1145/27629.27631]
• S+90: David Stemple , Leo Fegaras , Tim Sheard , Adolfo Socorro, Exceeding the limits of polymorphism in database programming languages, Proceedings of the international conference on extending database technology on Advances in database technology, p.269-285, March 1990, Venice, Italy
• S+92: D. Stemple et al. Type-safe linguistic reflection: a generator technology. Research report CS/92/6, Univ. St Andrews, 1992.
• SVGG93: L.V. Saxton, D. Van Gucht, and M. Gandhi. Universal queries for relational query languages. Technical Report 374, Indiana University Dept. Computer Sci., 1993.
• Var82: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Data manipulation languages (DML)
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Dictionaries

General Terms:
Algorithms, Languages, Theory