Optimization and serializability of update transactions in marked databases

Marked databases are a generalization of relational databases in which there are no fixed schemas, and in which tuples are never deleted, but eventually marked as invalid. The study of marked databases has recently gained considerable interest, since they allow elegant solutions to various problems arising in conventional relational databases. In this paper update transactions operating on marked databases are investigated. The first focus of this study is on transaction optimization and equivalence; the second is on correctness criteria for corresponding schedules which describe the concurrent execution of multiple transactions. In particular, a sequence of increasingly weaker notions of correctness is presented, which exhibits interesting and novel properties of a variety of classes of schedules on marked databases. These notions range from state-based serializability, which here can be decided in polynomial time even in the absence of syntactic restrictions (like conflict relations), to the recently proposed goal-correctness. The results provide further evidence that marked databases are valuable generalization of relational databases. (orig.)Available from TIB Hannover: RO 7057(1995,13) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekSIGLEDEGerman