Serializability of Concurrent Data Base Updates
A sequence of interleaved user transactions in a data base system may not be serializable, i.e., equivalent to some sequential execution of the individual transactions. Using a simple transaction model we show that recognizing the transaction histories which are serializable is an NP-complete probl...
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149497 |
| _version_ | 1826216662704062464 |
|---|---|
| author | Papadimitriou, Christos H. |
| author_facet | Papadimitriou, Christos H. |
| author_sort | Papadimitriou, Christos H. |
| collection | MIT |
| description | A sequence of interleaved user transactions in a data base system may not be serializable, i.e., equivalent to some sequential execution of the individual transactions. Using a simple transaction model we show that recognizing the transaction histories which are serializable is an NP-complete problem. |
| first_indexed | 2024-09-23T16:51:24Z |
| id | mit-1721.1/149497 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T16:51:24Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1494972023-03-30T03:03:00Z Serializability of Concurrent Data Base Updates Papadimitriou, Christos H. A sequence of interleaved user transactions in a data base system may not be serializable, i.e., equivalent to some sequential execution of the individual transactions. Using a simple transaction model we show that recognizing the transaction histories which are serializable is an NP-complete problem. 2023-03-29T15:02:49Z 2023-03-29T15:02:49Z 1979-03 https://hdl.handle.net/1721.1/149497 MIT-LCS-TR-210 application/pdf |
| spellingShingle | Papadimitriou, Christos H. Serializability of Concurrent Data Base Updates |
| title | Serializability of Concurrent Data Base Updates |
| title_full | Serializability of Concurrent Data Base Updates |
| title_fullStr | Serializability of Concurrent Data Base Updates |
| title_full_unstemmed | Serializability of Concurrent Data Base Updates |
| title_short | Serializability of Concurrent Data Base Updates |
| title_sort | serializability of concurrent data base updates |
| url | https://hdl.handle.net/1721.1/149497 |
| work_keys_str_mv | AT papadimitriouchristosh serializabilityofconcurrentdatabaseupdates |