Accession Number : ADA324623

Title :   The Optimal Locking Problem in a Directed Acyclic Graph,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Korth, Henry F.

PDF Url : ADA324623

Report Date : MAR 1981

Pagination or Media Count : 7

Abstract : We assume a multiple granularity database locking scheme similar to that of Gray, et al. 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.

Descriptors :   *DATA BASES, OPTIMIZATION, DATA MANAGEMENT, GRAPHS, COMPILERS.

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE