{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T10:40:03Z","timestamp":1739443203265,"version":"3.37.0"},"reference-count":16,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2007,9,5]],"date-time":"2007-09-05T00:00:00Z","timestamp":1188950400000},"content-version":"vor","delay-in-days":6456,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems &amp;amp; Computers in Japan"],"published-print":{"date-parts":[[1990,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Conventional concurrency control schedulers are used to increase concurrency to avoid transaction rollbacks, and it is widely accepted that a scheduler is effective if it can provide more concurrency. However, transaction rollbacks seldom occur in a practical transaction processing system. The performance of a scheduler should be evaluated by how efficient a schedule it can generate in such a situation. We select the number of secondary storage accesses to process a given schedule as such an efficient criterion.<\/jats:p><jats:p>A schedule is regarded as a page reference string and the memory cost of the schedule is defined by the cost to process the schedule by an optimal paging algorithm. Then we consider the minimum memory cost scheduling problem for a given set of transactions. The problem is shown to be NP hard in the general case. Thus we turn our attention to: (1) a restriction of the transaction model to construct an optimal schedule in a linear time; and (2) a nearly optimal solution to the given problem under a general transaction model. The nearly optimal scheduling problem is shown to be rather difficult.<\/jats:p>","DOI":"10.1002\/scj.4690210308","type":"journal-article","created":{"date-parts":[[2009,11,19]],"date-time":"2009-11-19T23:17:03Z","timestamp":1258672623000},"page":"76-86","source":"Crossref","is-referenced-by-count":0,"title":["Optimal Concurrency Control Schedulers in Terms of Secondary Storage Access"],"prefix":"10.1002","volume":"21","author":[{"given":"Tetsuro","family":"Kakeshita","sequence":"first","affiliation":[]},{"given":"Yahiko","family":"Kambayashi","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2007,9,6]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/32204.32220"},{"volume-title":"Concurrency Control and Recovery in Database Systems","year":"1987","author":"Bernstein P. A.","key":"e_1_2_1_3_2"},{"key":"e_1_2_1_4_2","unstructured":"M. J.CareyandM. R.Stonebraker The performance of concurrency control for database management systems. Proc. VLDB pp.107\u2013118(1984)."},{"volume-title":"Operating Systems Theory","year":"1973","author":"Coffman E. G.","key":"e_1_2_1_5_2"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1994.2022"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/360363.360369"},{"volume-title":"Computers and Intractability: A Guide to the Theory of NP Completeness","year":"1979","author":"Garey M. R.","key":"e_1_2_1_8_2"},{"key":"e_1_2_1_9_2","unstructured":"T.KakeshitaandY.Kambayashi An optimal secondary storage scheduler for transaction processing. SIGDBS Record 64\u20108 IPSJ (March1988)."},{"key":"e_1_2_1_10_2","unstructured":"Kondoh Y. Kambayashi andS.Yajima A method for concurrency control utilizing dependency among fundamental operations. Memoirs of the Research Institute for Mathematical Science Kyoto University No. 494 pp.90\u2013101(June1983)."},{"key":"e_1_2_1_11_2","doi-asserted-by":"crossref","unstructured":"R.KrishnamurthyandU.Dayal Theory of serializability for a parallel model of transactions. Proc. PODS pp.293\u2013305(1983).","DOI":"10.1145\/588111.588158"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00263925"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322158"},{"volume-title":"The Theory of Database Concurrency Control","year":"1986","author":"Papadimitriou C. H.","key":"e_1_2_1_14_2"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/360051.360231"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/322169.322176"},{"volume-title":"Locking Performance in Centralized Databases","year":"1987","author":"Tay Y. C.","key":"e_1_2_1_17_2"}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690210308","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690210308","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T09:56:35Z","timestamp":1739440595000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690210308"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,1]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1990,1]]}},"alternative-id":["10.1002\/scj.4690210308"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690210308","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"type":"print","value":"0882-1666"},{"type":"electronic","value":"1520-684X"}],"subject":[],"published":{"date-parts":[[1990,1]]}}}