Useless Actions Make a Difference
Ravi Sethi · Journal of the ACM · 1982
When several transactions read and write ~tems in a database, the question of consistency of the database arises.Consistency ~s maintained if transacUons are serial, the read and write acuons of a transacuon execute complete!ybefore the actions of the next transaction begin A particular history of interleaved read and write actions belonging to several transactions ~s correct if it ~s equivalent to a serial history.Since senahzablhty of hlstones is known to be NP-complete, subclasses of senahzable histories have been stu&ed.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 there ~s a read step followed by a wnte step Each step revolves some subset of the items m the database.W~th mulustep transactions stnct senahzabd~ty ~s NP-complete even ff there are no useless actions Categories and Subject Descriptors F.