ON THE COMPLETENESS OF OBJECT-CREATING DATABASE TRANSFORMATION LANGUAGES

Object-oriented applications of database systems require database tran sformations involving nonstandard functionalities such as set manipula tion and object creation, that is, the introduction of new domain elem ents. To deal with these functionalities, Abiteboul and Kanellakis [19 89] introduced the ''determinate'' transformations as a generalization of the standard domain-preserving transformations. The obvious extens ions of complete standard database programming languages, however, are not complete for the determinate transformations. To remedy this mism atch, the ''constructive'' transformations are proposed. It is shown t hat the constructive transformations are precisely the transformations that can be expressed in said extensions of complete standard languag es. Thereto, a close correspondence between object creation and the co nstruction of hereditarily finite sets is established. A restricted ve rsion of the main completeness result for the case where only list man ipulations are involved is also presented.