Serializability test by pebbling

Technical Report

Public Deposited

Citeable URL: https://ir.library.oregonstate.edu/concern/technical_reports/m613n5919

Descriptions

Attribute Name	Values
Creator	Minoura, Toshimi
Abstract	An execution of a database system is considered correct if its net effect is as if transactions were executed serially, and such an execution is called serializable. In this short paper we show that the serializability test problem can be reduced to a simple pebbling problem. Our characterization is intuitive and can handle uniformly both multi-versions and replicated data. A polynomial-time version of our method is also discussed. Key Words and Phrases: database system, concurrency control, serializability test, pebbling, NP-complete problem
Resource Type	Technical Report
Academic Affiliation	Computer Science
Series	Technical report (Oregon State University. Department of Computer Science)
Rights Statement	In Copyright
Publisher	Oregon State University. Department of Computer Science
Peer Reviewed	No
Language	English [eng]
File Format	pdf

Thumbnail	Title	Date Uploaded	Visibility	Actions
	Minoura_Toshimi_86_60_11.pdf	2023-01-31	Public	Download