Database transformations consist of queries and updates which are two
fundamental types of computations in any databases - the first provides
the capability to retrieve data and the second is used to maintain
databases in light of ever-changing application domains. This
dissertation aims to lay down the foundations for establishing a
theoretical framework of database transformations in the context of
complex-value databases. The previous findings reveal that it is very
difficult to characterise common features of database queries and
updates in a way which is meaningful for further investigations.
Nevertheless, the advent of the sequential Abstract State Machine (ASM)
thesis capturing sequential algorithms sheds light on the study of
database transformations. Observing that the class of computations
described by database transformations may be formalised as algorithms
respecting database principles, we propose the database ASM thesis for a
complete characterisation of database transformations. It turns out that
every database transformation characterised by five postulates can be
behaviourally simulated by a database Abstract State Machine (DB-ASM)
with the same signature and background, and vice versa. Furthermore, a
logic for DB-ASMs is defined. In spite of bounded non-determinism
permitted by DB-ASMs, the logic is proven to be sound and complete.
