Useless Actions Make a Difference: Strict Serializability of Database Updates

When several transactions read and write tems in a database, the question of consistency of the database arises. Consistencys maintained if transacUons are serial, the read and write acuons of a transacuon execute completely before the actions of the next transaction begin A particular history of interleaved read and write actions belonging to several transactionss correct if its equivalent to a serial history. Since senahzablhty of hlstones is known to be NP-complete, subclasses of senahzable histories have been stu. One such class consists of htstones senahzable in a strict sense, transacuons that are already m serial in a history must remain m the same relative order When there are no useless actions m a history, it is shown that strict sermlizabdity can be determined m polynomial time If useless actions are permitted, then strict serializabihty becomes NP-complete The above results apply to two-step transactions m which theres a read step followed by a wnte step Each step revolves some subset of the items m the database. With mulustep transactions stnct senahzabdtys NP-complete even ff there are no useless actions.