The Optimal Locking Problem in a Directed Acyclic Graph,

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1981
Accession Number
ADA324623

Entities

People

  • Henry F. Korth

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Air Force
  • Computer Programming
  • Computer Programs
  • Computer Science
  • Computers
  • Data Management
  • Database Management Systems
  • Databases
  • Operating Systems
  • Polynomials
  • Scientific Research
  • Universities

Fields of Study

  • Computer science

Readers

  • Database Systems and Applications
  • Mathematical Modeling and Probability Theory.