In the context of object databases, we study the application of an update method to a collection of receivers rather than to a single one. The obvious strategy of applying the update to the receivers one after the other, in some arbitrary order, brings up the problem of order independence. On a very general level, we investigate how update behavior can be analyzed in terms of certain schema annotations, called colorings. We are able to characterize those colorings that always describe order-independedent updates. We also consider a more specific model of update methods implemented in the relational algebra. Order-independence of such algebraic methods is undecidable in general, but decidable if the expressions used are positive. Finally, we consider an alternative parallel strategy for set-oriented applications of algebraic update methods and compare and relate it to the sequential strategy.

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.

In the context of object databases, we study the application of an update method to a collection of receivers rather than to a single one.The obvious strategy of applying the update to the receivers one after the other, in some arbkrary order, brings up the problem of order independence.On a very general level, we investigate how update behavior

Recently, various database query languages have been considered that have the ability to create new domain elements. These languages, however, are not complete in the sense of Abiteboul and Kanellakis (1989). They provide a precise characterization for the class of queries that can be expressed in these languages. They call this class the constructive queries and motivate this term by establishing a close correspondence between object creation and the construction of hereditarily finite sets.>