On the completeness of object-creating database transformation languages

ABSTRACT

Object-oriented applications of database systems require database transformations involoving nonstandard functionalities such as set manipulation and object creation, that is, the introduction of new domain elements. To deal with thse functionalities, Abiteboul and Kanellakis [1989] introduced the “determinate” transformations as a generalization of the standard domain-preserving transformations. The obvious extensions of complete standard database programming languages, however, are not complete for the determinate transformations. To remedy this mismatch, the “constructive” transformations are proposed. It is shown that the constructive transformations are precisely the transformations that can be expressed in said extensions of complete standard languages. Thereto, a close correspondence between object creation and the construction of hereditarily finite sets is established.A restricted version of the main completeness result for the case where only list manipulations are involved is also presented.

REFERENCES

• 2: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 3: Serge Abiteboul , Paris C. Kanellakis, Object identity as a query language primitive, ACM SIGMOD Record, v.18 n.2, p.159-173, June 1989
• 4: Serge Abiteboul , Victor Vianu, Procedural languages for database queries and updates, Journal of Computer and System Sciences, v.41 n.2, p.181-229, Oct. 1990 [doi>10.1016/0022-0000(90)90036-K]
• 5: Serge Abiteboul , Victor Vianu, Datalog extensions for database queries and updates, Journal of Computer and System Sciences, v.43 n.1, p.62-124, Aug. 1991 [doi>10.1016/0022-0000(91)90032-Z]
• 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: Marc Andries , Jan Paredaens, On instance-completeness for database query languages involving object creation, Journal of Computer and System Sciences, v.52 n.2, p.357-373, April 1996 [doi>10.1006/jcss.1996.0027]
• 8: BANCILHON, F. 1978. On the completeness of query languages for relational data bases. In Proceedings of the 7th Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 64. Springer-Verlag, New York, pp. 112-123.
• 9: BARWISE, J. 1975. Admissible Sets and Structures. Springer-Verlag, New York.
• 10: C. Beeri, A formal approach to object-oriented databases, Data & Knowledge Engineering, v.5 n.4, p.353-382, Oct. 1990 [doi>10.1016/0169-023X(90)90020-E]
• 11: CHANDRA, A., AND HAREL, D. 1980. Computable queries for relational database systems. J. Comput. Syst. Sci. 21, 2, 156-178.
• 12: 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]
• 13: CODD, E. 1972a. Further normalization of the data base relational model. In Data Base Systems, R. Rustin, ed. Prentice-Hall, Englewood Cliffs, N.J., pp. 33-64.
• 14: CODD, E. 1972b. Relational completeness of data base sublanguages. In Data Base Systems, R. Rustin, ed. Prentice-Hall, Englewood Cliffs, N. J., pp. 65-98.
• 15: D Dahlhaus , J A Makowsky, The choice of programming primitives for set-like programming languages, Proc. of the European symposium on programming on ESOP 86, p.160-172, March 1986, Saarbru:9Aicken, Germany
• 16: E. Dahlhaus , J. A. Makowsky, Query languages for hierarchic databases, Information and Computation, v.101 n.1, p.1-32, Nov. 1992 [doi>10.1016/0890-5401(92)90074-P]
• 17: Karl Denninghoff , Victor Vianu, Database method schemas and object creation, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.265-275, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153911]
• 18: GAIFMAN, H., AND VARDI, M. Y. 1985. A simple proof that connectivity is not first-order definable. Bull EATCS, 26, 43-45.
• 19: M. Gyssens , J. Paredaens , J. Van den Bussche , D. Van Gucht, A Graph-Oriented Object Database Model, IEEE Transactions on Knowledge and Data Engineering, v.6 n.4, p.572-586, August 1994 [doi>10.1109/69.298174]
• 20: Marc Gyssens , Jan Paredaens , Dirk van Gucht, A graph-oriented object database model, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.417-424, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298593]
• 21: FAGIN, R. 1975. Monadic generalized spectra. Z. Mathe. Logik Grund. Math. 21, 89-96.
• 22: Richard Hull , Jianwen Su, Algebraic and calculus query languages for recursively typed complex objects, Journal of Computer and System Sciences, v.47 n.1, p.121-156, Aug. 1993
• 23: 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]
• 24: 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
• 25: Michael Kifer , James Wu, A logic for programming with complex objects, Journal of Computer and System Sciences, v.47 n.1, p.77-120, Aug. 1993
• 26: Gabriel M. Kuper , Moshe Y. Vardi, The logical data model, ACM Transactions on Database Systems (TODS), v.18 n.3, p.379-413, Sept. 1993 [doi>10.1145/155271.155274]
• 27: PAREDAENS, J. 1978. On the expressive power of the relational algebra. Inf. Proc. Lett. 7, 2.
• 28: Leon Sterling , Ehud Shapiro, The art of Prolog: advanced programming techniques, MIT Press, Cambridge, MA, 1986
• 29: TARSKI, A. 1986. What are logical notions? Hist. Phil. Logic 7, 143-154, J. Corcoran, ed.
• 30: Jan Van den Bussche , Jan Paredaens, The expressive power of complex values in object-based data models, Information and Computation, v.120 n.2, p.220-236, Aug. 1, 1995 [doi>10.1006/inco.1995.1110]
• 31: VAN DEN BUSSCHE, J., AND VAN GUCHT, D. 1997. A semi-deterministic approach to object creation and non-determinism in database queries. J. Comput. Syst. Sci. 54, 1 (Feb.), 34-47.
• 32: VAN ROSSUM, J. 1992. Master's dissertation. Technical University of Eindhoven, Eindhoven, The Netherlands, (in Dutch).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Computability theory

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

General Terms:
Languages, Theory

Keywords:
computational completeness, constructive transformation, first-order logic, object creation, object-oriented database, while loop