The complexity of strict serializability revisited |
| |
| Affiliation: | 1. Department of Materials and Life Science, Faculty of Science and Technology, Seikei University, 3-3-1 Kichijoji Kitamachi, Musashino-shi, Tokyo 180-8633, Japan;2. Area in Advanced Materials Science, Department of Engineering and Design, Faculty of Engineering and Design, Kagawa University, 2217-20 Hayashicho, Takamatsu-shi, Kagawa 761-0396, Japan;1. University of Wisconsin at Madison, USA;2. Syracuse University, USA;3. Old Dominion University, USA;1. EPFL, Switzerland;2. University of Sydney, Australia;3. MIT, USA |
| |
| Abstract: | A well-known result by Sethi (1982) states that strict view- and final-state serializability are NP-complete in general, but decidable in polynomial time if useless values are absent. This paper falsifies one of these claims by proving that the absence of useless values is not sufficient to make strict final-state serializability decidable in polynomial time. Moreover, we show that a slightly stronger condition is sufficient, namely the absence of dead values. All claims refer to the two-step transaction model which is used by Bernstein et al. (1979), Kelter (1985, 1986) and Papadimitriou (1979). These results give new insights into the differences between strict view- and final-state serializability and between uselessness and deadness of values. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
