BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-81-847
       ENTRY:: June 05, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: The optimal locking problem in a directed acyclic graph
        TYPE:: Technical Report
      AUTHOR:: Korth, Henry F.
        DATE:: March 1981
       PAGES:: 7
    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.
       NOTES:: [Adminitrivia V1/Prg/19950605]
         END:: STAN//CS-TR-81-847