Report Number: CS-TR-81-847
Institution: Stanford University, Department of Computer Science
Title: The optimal locking problem in a directed acyclic graph
Author: Korth, Henry F.
Date: March 1981
Abstract: We assume a multiple granularity database locking scheme similar to that of Gray, et al. [197S] in which a rooted directed acyclic graph is used to represent the levels of granularity. We prove that even if it is known in advance exactly what database references the transaction will make, it is NP-complete to find the optimal locking strategy for the transaction.
http://i.stanford.edu/pub/cstr/reports/cs/tr/81/847/CS-TR-81-847.pdf