43:
220:
The corresponding transaction "reads" object X (i.e., it retrieves the data stored at X). This is done so that it can modify the data (e.g., X=X+4) during a "write" operation rather than merely overwrite it. When the schedule is represented as a list rather than a grid, the action is represented as
1857:
These schedules are recoverable. The schedule F is recoverable because T1 commits before T2, that makes the value read by T2 correct. Then T2 can commit itself. In the F2 schedule, if T1 aborted, T2 has to abort because the value of A it read is incorrect. In both cases, the database is left in a
1497:
Notice that the above example (which is the same as the example in the discussion of conflict-serializable) is both view-serializable and conflict-serializable at the same time. There are however view-serializable schedules that are not conflict-serializable: those schedules with a transaction
1358:
To quickly analyze whether two schedules are view-equivalent, write both schedules as a list with each action's subscript representing which view-equivalence condition they match. The schedules are view equivalent if and only if all the actions have the same subscript (or lack thereof) in both
467:
In this example, the columns represent the different transactions in the schedule D. Schedule D consists of three transactions T1, T2, T3. First T1 Reads and Writes to object X, and then
Commits. Then T2 Reads and Writes to object Y and Commits, and finally, T3 Reads and Writes to object Z and
745:
Serializability is used to keep the data in the data item in a consistent state. It is the major criterion for the correctness of concurrent transactions' schedule, and thus supported in all general purpose database systems. Schedules that are not serializable are likely to generate erroneous
825:
on the operation's object, held by another transaction, or when writing to a transaction's temporary private workspace and materializing, copying to the database itself, upon commit; as long as a requested/issued conflicting operation is not executed upon the database itself, the conflict is
1861:
Schedule J is unrecoverable because T2 committed before T1 despite previously reading the value written by T1. Because T1 aborted after T2 committed, the value read by T2 is wrong. Because a transaction cannot be rolled-back after it commits, the schedule is unrecoverable.
845:
Both schedules have the same set of conflicting pairs (such that the actions in each conflicting pair are in the same order). This is equivalent to requiring that all conflicting operations (i.e., operations in any conflicting pair) are in the same order in both
1989:
In this example, although F2 is recoverable, it does not avoid cascading aborts. It can be seen that if T1 aborts, T2 will have to be aborted too in order to maintain the correctness of the schedule as T2 has already read the uncommitted value written by T1.
749:
If any specific order between some transactions is requested by an application, then it is enforced independently of the underlying serializability mechanisms. These mechanisms are typically indifferent to any specific order, and generate some unpredictable
850:
Equivalently, two schedules are said to be conflict equivalent if and only if one can be transformed to another by swapping pairs of non-conflicting operations (whether adjacent or not) while maintaining the order of actions for each transaction.
873:
is acyclic when only committed transactions are considered. Note that if the graph is defined to also include uncommitted transactions, then cycles involving uncommitted transactions may occur without conflict serializability violation.
854:
Equivalently, two schedules are said to be conflict equivalent if and only if one can be transformed to another by swapping pairs of non-conflicting adjacent operations with different transactions.
279:
The corresponding transaction "writes" to object X (i.e., it modifies the data stored at X). When the schedule is represented as a list rather than a grid, the action is represented as
821:
if the requested conflicting operation is actually executed: in many cases a requested/issued conflicting operation by a transaction is delayed and even never executed, typically by a
337:
This represents a "commit" operation in which the corresponding transaction has successfully completed its preceding actions, and has made all its changes permanent in the database.
2069:
operation of T2 (either read or write), then the commit or abort event of T1 also precedes that conflicting operation of T2. For example, the schedule F3 above is strict.
2053:
Note that this
Schedule would not be serializable if T1 would be committed. Cascading aborts avoidance is sufficient but not necessary for a schedule to be recoverable.
1715:
1688:
1661:
1634:
1127:
1100:
1070:
1043:
1013:
986:
309:
251:
60:
329:
271:
1351:
Failed the second condition of view equivalence because T2 read the value written by T1 for B in S1 and S2, but T1 read the value written by T2 for B in S3.
1586:
The above example is not conflict-serializable, but it is view-serializable since it has a view-equivalent serial schedule <T1,| T2,| T3>.
1133:
Additionally, two view-equivalent schedules must involve the same set of transactions such that each transaction has the same actions in the same order.
542:
if the executed transactions are non-interleaved (i.e., a serial schedule is one in which no transaction starts until a running transaction has ended).
1993:
The following is a recoverable schedule which avoids cascading abort. Note, however, that the update of A by T1 is always lost (since T1 is aborted).
659:
In schedule E, the order in which the actions of the transactions are executed is not the same as in D, but in the end, E gives the same result as D.
1881:
occur when one transaction's abort causes another transaction to abort because it read and relied on the first transaction's changes to an object. A
501:
when the operations of transactions in a schedule interleave (i.e., when the schedule is conflict-serializable but not serial). The schedule is in
2424:
2107:
1348:
Failed the first condition of view equivalence because T1 read the initial value for B in S1 and S2, but T2 read the initial value for B in S3.
2360:
2329:
2304:
2279:
107:
814:
Reducing conflicts, such as through commutativity, enhances performance because conflicts are the fundamental cause of delays and aborts.
79:
1354:
Failed the third condition of view equivalence because T2 did the final write for B in S1 and S2, but T1 did the final write for B in S3.
1344:
The conditions for S3 to be view-equivalent to S1 and S2 were not satisfied at the corresponding superscripts for the following reasons:
942:
1458:
if it is view-equivalent to some serial schedule. Note that by definition, all conflict-serializable schedules are view-serializable.
86:
2214:
2189:
937:
Conflict serializability can be enforced by restarting any transaction within the cycle in the precedence graph, or by implementing
126:
167:
that are executed together in the system. If the order in time between certain operations is not determined by the system, then a
1136:
In the example below, the schedules S1 and S2 are view-equivalent, but neither S1 nor S2 are view-equivalent to the schedule S3.
842:
Both schedules S1 and S2 involve the same set of transactions such that each transaction has the same actions in the same order.
2419:
93:
838:
The schedules S1 and S2 are said to be conflict-equivalent if and only if both of the following two conditions are satisfied:
492:
64:
2204:
2072:
Any strict schedule is cascade-less, but not the converse. Strictness allows efficient recovery of databases from failure.
2429:
2120:
762:
Two actions are said to be in conflict (conflicting pair) if and only if all of the 3 following conditions are satisfied:
188:
theory. In practice, most general purpose database systems employ conflict-serializable and strict recoverable schedules.
75:
2232:
Proceedings of the 20th annual international symposium on
Computer architecture (ISCA '93). Volume 21, Issue 2, May 1993.
2414:
527:
484:
526:
or commit action for each of its transactions. A transaction's last action is either to commit or abort. To maintain
521:
53:
2324:. Pearson international edition (2nd ed.). Upper Saddle River, NJ: Pearson/Prentice Hall. pp. 891–892.
789:
2404:
1873:(a.k.a, "Avoiding Cascading Aborts (ACA) schedules") are schedules which avoid cascading aborts by disallowing
174:
1874:
785:
781:
1605:, transactions only commit after all transactions whose changes they read have committed. A schedule becomes
822:
178:
100:
2141:
507:
when the operations of transactions in a schedule do not interleave (i.e., when the schedule is serial).
482:
Usually, for the purpose of reasoning about concurrency control in databases, an operation is modelled as
343:
144:
31:
156:
488:, occurring at a point in time, without duration. Real executed operations always have some duration.
2155:
777:
181:, locking, etc. Often, only a subset of the transaction operation types are included in a schedule.
164:
957:
Two schedules S1 and S2 are said to be view-equivalent when the following conditions are satisfied:
495:), but time orders between operations in each transaction must remain unchanged. The schedule is in
877:
The schedule K is conflict-equivalent to the serial schedule <T1,T2>, but not <T2,T1>.
185:
2245:
2179:
173:
is used. Examples of such operations are requesting a read operation, reading, writing, aborting,
2409:
2135:
2131:
946:
2356:
2325:
2300:
2275:
2210:
2185:
2125:
938:
870:
491:
Operations of transactions in a schedule can interleave (i.e., transactions can be executed
1693:
1666:
1639:
1612:
1105:
1078:
1048:
1021:
991:
964:
282:
224:
2225:
2151:
2106:
2085:
2081:
2080:
The following expressions illustrate the hierarchical (containment) relationships between
2095:
Serial ⊂ strict ⊂ cascadeless (ACA) ⊂ recoverable ⊂ all schedules
2200:
2175:
746:
outcomes; which can be extremely harmful (e.g., when dealing with money within banks).
314:
256:
2398:
2373:
830:; non-materialized conflicts are not represented by an edge in the precedence graph.
751:
503:
497:
348:
169:
2092:
Serial ⊂ conflict-serializable ⊂ view-serializable ⊂ all schedules
1885:
occurs when a transaction reads data from uncommitted write in another transaction.
2100:
353:
1888:
The following examples are the same as the ones in the discussion on recoverable:
2353:
Proceedings of the 2008 ACM SIGMOD international conference on
Management of data
780:. Equivalently, two actions are considered conflicting if and only if they are a
2348:
1590:
1499:
754:
that is typically compatible with multiple serial orders of these transactions.
42:
30:
This article is about databases and transaction processing. For other uses, see
17:
776:
Equivalently, two actions are considered conflicting if and only if they are
2299:. Computer science series (2nd ed.). Boston: McGraw-Hill. p. 540.
2230:
Transactional memory: architectural support for lock-free data structures.
2065:
if for any two transactions T1, T2, if a write operation of T1 precedes a
866:
when the schedule is conflict-equivalent to one or more serial schedules.
140:
988:
in S1 reads an initial value for object X, so does the same transaction
2274:(Seventh ed.). New York, NY: McGraw-Hill Education. p. 814.
1102:
in S1 does the final write for object X, so does the same transaction
471:
The schedule D above can be represented as list in the following way:
869:
Equivalently, a schedule is conflict-serializable if and only if its
2320:
Garcia-Molina, Hector; Ullman, Jeffrey D.; Widom, Jennifer (2009).
2105:
163:
of operations (actions) ordered by time, performed by a set of
2270:
Silberschatz, Abraham; Korth, Henry F.; Sudarshan, S. (2020).
159:
in a set of transactions running in the system. Often it is a
36:
1589:
Since determining whether a schedule is view-serializable is
656:
if it is equivalent (in its outcome) to a serial schedule.
530:, a transaction must undo all its actions if it is aborted.
155:) of a system is an abstract model to describe the order of
27:
Order of execution of transactions in transaction processing
2110:
Venn diagram for serializability and recoverability classes
1045:
reads a value (for an object X) written by the transaction
803:
While the following sets of actions are not conflicting:
2184:(free PDF download), Addison Wesley Publishing Company,
474:
D = R1(X) W1(X) Com1 R2(Y) W2(Y) Com2 R3(Z) W3(Z) Com3
1593:, view-serializability has little practical interest.
1696:
1669:
1642:
1636:
reads and relies on changes from another transaction
1615:
1108:
1081:
1051:
1024:
994:
967:
317:
285:
259:
227:
2347:
Michael J. Cahill, Uwe Röhm, Alan D. Fekete (2008):
2181:
Concurrency
Control and Recovery in Database Systems
341:
Alternatively, a schedule can be represented with a
331:
is a number corresponding to a specific transaction.
273:
is a number corresponding to a specific transaction.
2103:(below) illustrates the above clauses graphically.
772:
The actions access the same object (read or write).
67:. Unsourced material may be challenged and removed.
1709:
1682:
1655:
1628:
1121:
1094:
1064:
1037:
1007:
980:
323:
303:
265:
245:
769:At least one of the actions is a write operation.
2349:"Serializable isolation for snapshot databases"
545:Schedule D is an example of a serial schedule:
209:The time order of operations (a.k.a., actions).
184:Schedules are fundamental concepts in database
2295:Ramakrishnan, Raghu; Gehrke, Johannes (2000).
2355:, pp. 729-738, Vancouver, Canada, June 2008,
795:The following set of actions is conflicting:
766:The actions belong to different transactions.
519:is one that contains either an abort (a.k.a.
8:
2178:, Vassos Hadzilacos, Nathan Goodman (1987):
2343:
2341:
365:The following is an example of a schedule:
203:The different transactions in the schedule.
2148:and its proposed solutions are described.
1701:
1695:
1674:
1668:
1647:
1641:
1620:
1614:
1113:
1107:
1086:
1080:
1056:
1050:
1029:
1023:
999:
993:
972:
966:
799:R1(X), W2(X), W3(X) (3 conflicting pairs)
347:(or DAG) in which there is an arc (i.e.,
316:
284:
258:
226:
127:Learn how and when to remove this message
1995:
1890:
1719:
1504:
1460:
1138:
879:
661:
547:
367:
2168:
2132:Making snapshot isolation serializable
7:
2240:
2238:
65:adding citations to reliable sources
2322:Database systems: the complete book
2076:Serializability Class Relationships
2246:"Conflict Serializability in DBMS"
25:
2206:Transactional Information Systems
41:
2126:Strong strict two-phase locking
947:serializable snapshot isolation
76:"Database transaction schedule"
52:needs additional citations for
2425:Distributed computing problems
2363:(SIGMOD 2008 best paper award)
2146:Global serializability problem
298:
292:
240:
234:
213:Operations (a.k.a., actions):
1:
2121:Schedule (project management)
478:Duration and order of actions
2154:, a more general concept in
147:(transaction management), a
2297:Database management systems
2203:, Gottfried Vossen (2001):
2446:
29:
1896:
1893:
1728:
1725:
1722:
1147:
1144:
1141:
862:A schedule is said to be
2272:Database system concepts
2128:(SS2PL or Rigorousness).
1072:in S1, it must do so S2.
2420:Transaction processing
2228:and J. Eliot B. Moss.
2142:Global serializability
2111:
1711:
1684:
1657:
1630:
1123:
1096:
1066:
1039:
1009:
982:
344:directed acyclic graph
325:
305:
267:
247:
145:transaction processing
32:scheduling (computing)
2374:"Cascadeless in DBMS"
2109:
1871:Cascadeless schedules
1712:
1710:{\displaystyle T_{j}}
1685:
1683:{\displaystyle T_{i}}
1658:
1656:{\displaystyle T_{j}}
1631:
1629:{\displaystyle T_{i}}
1124:
1122:{\displaystyle T_{i}}
1097:
1095:{\displaystyle T_{i}}
1067:
1065:{\displaystyle T_{j}}
1040:
1038:{\displaystyle T_{i}}
1010:
1008:{\displaystyle T_{i}}
983:
981:{\displaystyle T_{i}}
864:conflict-serializable
858:Conflict-serializable
326:
306:
304:{\displaystyle Wi(X)}
268:
248:
246:{\displaystyle Ri(X)}
2430:NP-complete problems
2156:concurrent computing
1694:
1667:
1640:
1613:
1603:recoverable schedule
1406:, W1(B), Com1, R2(B)
1371:, W1(B), Com1, R2(A)
1106:
1079:
1049:
1022:
992:
965:
834:Conflict equivalence
315:
283:
257:
225:
61:improve this article
2415:Concurrency control
2176:Philip A. Bernstein
1998:
1507:
1463:
1075:If the transaction
1018:If the transaction
961:If the transaction
882:
810:R1(X), W2(Y), R3(X)
807:R1(X), R2(X), R3(X)
758:Conflicting actions
664:
550:
370:
186:concurrency control
2136:Snapshot isolation
2112:
1996:
1858:consistent state.
1707:
1680:
1653:
1626:
1505:
1461:
1119:
1092:
1062:
1035:
1005:
978:
943:timestamp ordering
880:
662:
548:
368:
321:
301:
263:
243:
2361:978-1-60558-102-6
2331:978-0-13-187325-4
2306:978-0-07-232206-4
2281:978-1-260-08450-4
2051:
2050:
1987:
1986:
1855:
1854:
1609:if a transaction
1584:
1583:
1495:
1494:
1456:view-serializable
1450:View-serializable
1342:
1341:
939:two-phase locking
935:
934:
743:
742:
645:
644:
517:complete schedule
511:Types of schedule
465:
464:
324:{\displaystyle i}
266:{\displaystyle i}
139:In the fields of
137:
136:
129:
111:
16:(Redirected from
2437:
2389:
2388:
2386:
2385:
2370:
2364:
2345:
2336:
2335:
2317:
2311:
2310:
2292:
2286:
2285:
2267:
2261:
2260:
2258:
2257:
2242:
2233:
2223:
2217:
2198:
2192:
2173:
1999:
1891:
1879:Cascading aborts
1720:
1716:
1714:
1713:
1708:
1706:
1705:
1689:
1687:
1686:
1681:
1679:
1678:
1662:
1660:
1659:
1654:
1652:
1651:
1635:
1633:
1632:
1627:
1625:
1624:
1508:
1464:
1139:
1128:
1126:
1125:
1120:
1118:
1117:
1101:
1099:
1098:
1093:
1091:
1090:
1071:
1069:
1068:
1063:
1061:
1060:
1044:
1042:
1041:
1036:
1034:
1033:
1014:
1012:
1011:
1006:
1004:
1003:
987:
985:
984:
979:
977:
976:
953:View equivalence
883:
871:precedence graph
828:non-materialized
817:The conflict is
665:
551:
371:
330:
328:
327:
322:
310:
308:
307:
302:
272:
270:
269:
264:
252:
250:
249:
244:
132:
125:
121:
118:
112:
110:
69:
45:
37:
21:
2445:
2444:
2440:
2439:
2438:
2436:
2435:
2434:
2405:Data management
2395:
2394:
2393:
2392:
2383:
2381:
2372:
2371:
2367:
2346:
2339:
2332:
2319:
2318:
2314:
2307:
2294:
2293:
2289:
2282:
2269:
2268:
2264:
2255:
2253:
2244:
2243:
2236:
2226:Maurice Herlihy
2224:
2220:
2199:
2195:
2174:
2170:
2165:
2152:Linearizability
2117:
2082:serializability
2078:
2059:
1868:
1697:
1692:
1691:
1670:
1665:
1664:
1643:
1638:
1637:
1616:
1611:
1610:
1599:
1452:
1442:
1438:
1434:
1428:
1424:
1420:
1413:
1409:
1405:
1401:
1397:
1393:
1386:
1382:
1378:
1374:
1370:
1366:
1109:
1104:
1103:
1082:
1077:
1076:
1052:
1047:
1046:
1025:
1020:
1019:
995:
990:
989:
968:
963:
962:
955:
860:
836:
760:
650:
536:
513:
480:
363:
357:of operations.
351:) between each
313:
312:
281:
280:
255:
254:
223:
222:
196:Grid notation:
194:
177:, requesting a
133:
122:
116:
113:
70:
68:
58:
46:
35:
28:
23:
22:
18:Serializability
15:
12:
11:
5:
2443:
2441:
2433:
2432:
2427:
2422:
2417:
2412:
2407:
2397:
2396:
2391:
2390:
2365:
2337:
2330:
2312:
2305:
2287:
2280:
2262:
2234:
2218:
2201:Gerhard Weikum
2193:
2167:
2166:
2164:
2161:
2160:
2159:
2149:
2139:
2129:
2123:
2116:
2113:
2097:
2096:
2093:
2086:recoverability
2077:
2074:
2061:A schedule is
2058:
2055:
2049:
2048:
2045:
2042:
2041:
2039:
2035:
2034:
2031:
2028:
2027:
2025:
2021:
2020:
2018:
2014:
2013:
2010:
2007:
2006:
2003:
1985:
1984:
1981:
1979:
1976:
1973:
1972:
1970:
1967:
1965:
1961:
1960:
1957:
1955:
1952:
1949:
1948:
1945:
1943:
1940:
1937:
1936:
1934:
1931:
1929:
1925:
1924:
1922:
1919:
1917:
1913:
1912:
1909:
1906:
1903:
1899:
1898:
1895:
1867:
1864:
1853:
1852:
1850:
1847:
1844:
1842:
1839:
1836:
1835:
1832:
1830:
1828:
1825:
1823:
1819:
1818:
1815:
1813:
1810:
1808:
1805:
1802:
1801:
1798:
1796:
1793:
1791:
1788:
1785:
1784:
1782:
1779:
1777:
1774:
1772:
1768:
1767:
1765:
1762:
1760:
1757:
1755:
1751:
1750:
1747:
1744:
1741:
1738:
1735:
1731:
1730:
1727:
1724:
1704:
1700:
1677:
1673:
1650:
1646:
1623:
1619:
1598:
1595:
1582:
1581:
1578:
1576:
1573:
1572:
1569:
1567:
1564:
1563:
1561:
1559:
1555:
1554:
1552:
1550:
1546:
1545:
1543:
1540:
1537:
1536:
1534:
1531:
1528:
1527:
1525:
1523:
1519:
1518:
1515:
1512:
1493:
1492:
1490:
1486:
1485:
1482:
1479:
1478:
1476:
1472:
1471:
1468:
1454:A schedule is
1451:
1448:
1447:
1446:
1440:
1436:
1435:, W2(B), R1(B)
1432:
1426:
1422:
1421:, W1(A), R2(A)
1418:
1415:
1411:
1407:
1403:
1399:
1395:
1394:, W1(A), R2(A)
1391:
1388:
1384:
1380:
1376:
1372:
1368:
1367:, W1(A), R1(B)
1364:
1356:
1355:
1352:
1349:
1340:
1339:
1336:
1334:
1331:
1329:
1326:
1323:
1322:
1320:
1317:
1314:
1312:
1309:
1306:
1305:
1303:
1300:
1297:
1295:
1292:
1289:
1288:
1286:
1283:
1281:
1278:
1275:
1272:
1271:
1268:
1266:
1264:
1261:
1258:
1255:
1254:
1251:
1249:
1247:
1244:
1242:
1238:
1237:
1234:
1232:
1229:
1227:
1225:
1221:
1220:
1217:
1215:
1212:
1210:
1208:
1204:
1203:
1201:
1198:
1196:
1193:
1191:
1187:
1186:
1184:
1181:
1179:
1176:
1174:
1170:
1169:
1166:
1163:
1160:
1157:
1154:
1150:
1149:
1146:
1143:
1131:
1130:
1116:
1112:
1089:
1085:
1073:
1059:
1055:
1032:
1028:
1016:
1002:
998:
975:
971:
954:
951:
933:
932:
929:
926:
925:
922:
919:
918:
916:
912:
911:
909:
905:
904:
901:
898:
897:
895:
891:
890:
887:
859:
856:
848:
847:
843:
835:
832:
812:
811:
808:
801:
800:
778:noncommutative
774:
773:
770:
767:
759:
756:
741:
740:
737:
734:
730:
729:
726:
724:
721:
720:
718:
715:
712:
711:
709:
707:
703:
702:
699:
697:
694:
693:
691:
688:
685:
684:
682:
680:
676:
675:
672:
669:
652:A schedule is
649:
646:
643:
642:
639:
637:
634:
633:
630:
628:
625:
624:
621:
619:
616:
615:
613:
610:
607:
606:
604:
601:
598:
597:
595:
592:
589:
588:
586:
584:
580:
579:
577:
575:
571:
570:
568:
566:
562:
561:
558:
555:
538:A schedule is
535:
532:
512:
509:
479:
476:
463:
462:
459:
457:
454:
453:
450:
448:
445:
444:
441:
439:
436:
435:
433:
430:
427:
426:
424:
421:
418:
417:
415:
412:
409:
408:
406:
404:
400:
399:
397:
395:
391:
390:
388:
386:
382:
381:
378:
375:
362:
359:
339:
338:
332:
320:
300:
297:
294:
291:
288:
274:
262:
242:
239:
236:
233:
230:
211:
210:
204:
193:
190:
135:
134:
49:
47:
40:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
2442:
2431:
2428:
2426:
2423:
2421:
2418:
2416:
2413:
2411:
2408:
2406:
2403:
2402:
2400:
2379:
2378:GeeksforGeeks
2375:
2369:
2366:
2362:
2358:
2354:
2350:
2344:
2342:
2338:
2333:
2327:
2323:
2316:
2313:
2308:
2302:
2298:
2291:
2288:
2283:
2277:
2273:
2266:
2263:
2251:
2250:GeeksforGeeks
2247:
2241:
2239:
2235:
2231:
2227:
2222:
2219:
2216:
2215:1-55860-508-8
2212:
2208:
2207:
2202:
2197:
2194:
2191:
2190:0-201-10715-5
2187:
2183:
2182:
2177:
2172:
2169:
2162:
2157:
2153:
2150:
2147:
2143:
2140:
2137:
2133:
2130:
2127:
2124:
2122:
2119:
2118:
2114:
2108:
2104:
2102:
2094:
2091:
2090:
2089:
2087:
2083:
2075:
2073:
2070:
2068:
2064:
2056:
2054:
2046:
2044:
2043:
2040:
2037:
2036:
2032:
2030:
2029:
2026:
2023:
2022:
2019:
2016:
2015:
2011:
2009:
2008:
2004:
2001:
2000:
1994:
1991:
1982:
1980:
1977:
1975:
1974:
1971:
1968:
1966:
1963:
1962:
1958:
1956:
1953:
1951:
1950:
1946:
1944:
1941:
1939:
1938:
1935:
1932:
1930:
1927:
1926:
1923:
1920:
1918:
1915:
1914:
1910:
1907:
1904:
1901:
1900:
1892:
1889:
1886:
1884:
1880:
1876:
1872:
1865:
1863:
1859:
1851:
1848:
1845:
1843:
1840:
1838:
1837:
1833:
1831:
1829:
1826:
1824:
1821:
1820:
1816:
1814:
1811:
1809:
1806:
1804:
1803:
1799:
1797:
1794:
1792:
1789:
1787:
1786:
1783:
1780:
1778:
1775:
1773:
1770:
1769:
1766:
1763:
1761:
1758:
1756:
1753:
1752:
1748:
1745:
1742:
1739:
1736:
1733:
1732:
1721:
1718:
1702:
1698:
1675:
1671:
1648:
1644:
1621:
1617:
1608:
1607:unrecoverable
1604:
1596:
1594:
1592:
1587:
1579:
1577:
1575:
1574:
1570:
1568:
1566:
1565:
1562:
1560:
1557:
1556:
1553:
1551:
1548:
1547:
1544:
1541:
1539:
1538:
1535:
1532:
1530:
1529:
1526:
1524:
1521:
1520:
1516:
1513:
1510:
1509:
1503:
1501:
1498:performing a
1491:
1488:
1487:
1483:
1481:
1480:
1477:
1474:
1473:
1469:
1466:
1465:
1459:
1457:
1449:
1444:
1437:written by T2
1423:written by T1
1416:
1408:written by T1
1396:written by T1
1389:
1381:written by T1
1373:written by T1
1362:
1361:
1360:
1353:
1350:
1347:
1346:
1345:
1337:
1335:
1332:
1330:
1327:
1325:
1324:
1321:
1318:
1315:
1313:
1310:
1308:
1307:
1304:
1301:
1298:
1296:
1293:
1291:
1290:
1287:
1284:
1282:
1279:
1276:
1274:
1273:
1269:
1267:
1265:
1262:
1259:
1257:
1256:
1252:
1250:
1248:
1245:
1243:
1240:
1239:
1235:
1233:
1230:
1228:
1226:
1223:
1222:
1218:
1216:
1213:
1211:
1209:
1206:
1205:
1202:
1199:
1197:
1194:
1192:
1189:
1188:
1185:
1182:
1180:
1177:
1175:
1172:
1171:
1167:
1164:
1161:
1158:
1155:
1152:
1151:
1140:
1137:
1134:
1114:
1110:
1087:
1083:
1074:
1057:
1053:
1030:
1026:
1017:
1000:
996:
973:
969:
960:
959:
958:
952:
950:
948:
944:
940:
930:
928:
927:
923:
921:
920:
917:
914:
913:
910:
907:
906:
902:
900:
899:
896:
893:
892:
888:
885:
884:
878:
875:
872:
867:
865:
857:
855:
852:
844:
841:
840:
839:
833:
831:
829:
824:
820:
815:
809:
806:
805:
804:
798:
797:
796:
793:
791:
787:
783:
779:
771:
768:
765:
764:
763:
757:
755:
753:
752:partial order
747:
738:
735:
732:
731:
727:
725:
723:
722:
719:
716:
714:
713:
710:
708:
705:
704:
700:
698:
696:
695:
692:
689:
687:
686:
683:
681:
678:
677:
673:
670:
667:
666:
660:
657:
655:
647:
640:
638:
636:
635:
631:
629:
627:
626:
622:
620:
618:
617:
614:
611:
609:
608:
605:
602:
600:
599:
596:
593:
591:
590:
587:
585:
582:
581:
578:
576:
573:
572:
569:
567:
564:
563:
559:
556:
553:
552:
546:
543:
541:
533:
531:
529:
525:
523:
518:
510:
508:
506:
505:
500:
499:
498:partial order
494:
489:
487:
486:
477:
475:
472:
469:
460:
458:
456:
455:
451:
449:
447:
446:
442:
440:
438:
437:
434:
431:
429:
428:
425:
422:
420:
419:
416:
413:
411:
410:
407:
405:
402:
401:
398:
396:
393:
392:
389:
387:
384:
383:
379:
376:
373:
372:
366:
360:
358:
356:
355:
350:
349:directed edge
346:
345:
336:
333:
318:
295:
289:
286:
278:
275:
260:
237:
231:
228:
219:
216:
215:
214:
208:
205:
202:
199:
198:
197:
191:
189:
187:
182:
180:
176:
172:
171:
170:partial order
166:
162:
158:
154:
150:
146:
142:
131:
128:
120:
117:November 2012
109:
106:
102:
99:
95:
92:
88:
85:
81:
78: –
77:
73:
72:Find sources:
66:
62:
56:
55:
50:This article
48:
44:
39:
38:
33:
19:
2382:. Retrieved
2380:. 2019-08-06
2377:
2368:
2352:
2321:
2315:
2296:
2290:
2271:
2265:
2254:. Retrieved
2252:. 2015-12-29
2249:
2229:
2221:
2209:, Elsevier,
2205:
2196:
2180:
2171:
2145:
2144:, where the
2101:Venn diagram
2098:
2079:
2071:
2066:
2062:
2060:
2052:
1992:
1988:
1887:
1882:
1878:
1870:
1869:
1860:
1856:
1690:commits and
1606:
1602:
1600:
1588:
1585:
1496:
1455:
1453:
1433:initial read
1430:
1419:initial read
1404:initial read
1392:initial read
1369:initial read
1365:initial read
1357:
1343:
1135:
1132:
956:
936:
876:
868:
863:
861:
853:
849:
837:
827:
819:materialized
818:
816:
813:
802:
794:
775:
761:
748:
744:
658:
654:serializable
653:
651:
648:Serializable
544:
539:
537:
520:
516:
514:
502:
496:
493:concurrently
490:
483:
481:
473:
470:
466:
364:
354:ordered pair
352:
342:
340:
334:
276:
217:
212:
206:
200:
195:
183:
168:
165:transactions
160:
152:
148:
138:
123:
114:
104:
97:
90:
83:
71:
59:Please help
54:verification
51:
2067:conflicting
1875:dirty reads
1866:Cascadeless
1663:, and then
1597:Recoverable
1591:NP-complete
1500:blind write
1441:final write
1427:final write
1412:final write
1400:final write
1385:final write
1377:final write
1359:schedules:
790:write-write
504:total order
2399:Categories
2384:2023-11-29
2256:2023-11-27
2163:References
1883:dirty read
1445:Com1, Com2
846:schedules.
792:conflict.
786:write-read
782:read-write
175:committing
157:executions
87:newspapers
2410:Databases
2088:classes:
1417:S3: R1(A)
1390:S2: R1(A)
1363:S1: R1(A)
528:atomicity
468:Commits.
141:databases
2115:See also
1717:aborts.
522:rollback
201:Columns:
192:Notation
149:schedule
2047:Commit
1439:, W1(B)
1425:, W2(A)
1410:, W2(B)
1402:, R1(B)
1398:, W2(A)
1383:, W2(B)
1379:, R2(B)
1375:, W2(A)
361:Example
153:history
101:scholar
2359:
2328:
2303:
2278:
2213:
2188:
2063:strict
2057:Strict
2038:Abort
1983:Abort
1969:Abort
1849:Abort
1846:Abort
1827:Abort
1414:, Com2
1387:, Com2
1129:in S2.
1015:in S2.
540:serial
534:Serial
485:atomic
311:where
253:where
103:
96:
89:
82:
74:
2033:W(A)
2024:W(A)
2017:R(A)
2012:R(A)
1978:Com.
1964:Com.
1959:W(A)
1954:W(A)
1947:R(A)
1942:R(A)
1933:W(A)
1928:W(A)
1921:R(A)
1916:R(A)
1841:Com.
1834:Com.
1822:Com.
1817:W(A)
1812:W(A)
1807:W(A)
1800:R(A)
1795:R(A)
1790:R(A)
1781:W(A)
1776:W(A)
1771:W(A)
1764:R(A)
1759:R(A)
1754:R(A)
1601:In a
1580:Com.
1571:W(A)
1558:Com.
1549:W(A)
1542:Com.
1533:W(A)
1522:R(A)
1489:W(B)
1484:R(A)
1475:R(A)
1431:R2(B)
1338:Com.
1333:Com.
1328:Com.
1319:Com.
1316:W(B)
1311:W(B)
1302:W(B)
1299:R(B)
1294:R(B)
1285:R(B)
1280:Com.
1277:W(A)
1270:W(B)
1263:W(B)
1260:R(A)
1253:R(B)
1246:R(B)
1241:Com.
1236:W(A)
1231:W(A)
1224:W(B)
1219:R(A)
1214:R(A)
1207:R(B)
1200:W(A)
1195:W(A)
1190:W(A)
1183:R(A)
1178:R(A)
1173:R(A)
945:, or
931:Com.
924:W(A)
915:Com.
908:W(B)
903:R(A)
894:R(A)
788:, or
739:Com.
736:Com.
733:Com.
728:W(Z)
717:W(Y)
706:W(X)
701:R(Z)
690:R(Y)
679:R(X)
641:Com.
632:W(Z)
623:R(Z)
612:Com.
603:W(Y)
594:R(Y)
583:Com.
574:W(X)
565:R(X)
461:Com.
452:W(Z)
443:R(Z)
432:Com.
423:W(Y)
414:R(Y)
403:Com.
394:W(X)
385:R(X)
335:Com.:
277:W(X):
218:R(X):
207:Rows:
108:JSTOR
94:books
2357:ISBN
2326:ISBN
2301:ISBN
2276:ISBN
2211:ISBN
2186:ISBN
2099:The
2084:and
823:lock
179:lock
161:list
151:(or
143:and
80:news
2134:in
2005:T2
2002:T1
1997:F3
1911:T2
1908:T1
1905:T2
1902:T1
1897:F2
1749:T2
1746:T1
1743:T2
1740:T1
1737:T2
1734:T1
1726:F2
1517:T3
1514:T2
1511:T1
1470:T2
1467:T1
1168:T2
1165:T1
1162:T2
1159:T1
1156:T2
1153:T1
1148:S3
1145:S2
1142:S1
889:T2
886:T1
674:T3
671:T2
668:T1
560:T3
557:T2
554:T1
380:T3
377:T2
374:T1
63:by
2401::
2376:.
2351:,
2340:^
2248:.
2237:^
1894:F
1877:.
1729:J
1723:F
1506:H
1502::
1462:G
1429:,
949:.
941:,
881:K
784:,
663:E
549:D
515:A
369:D
2387:.
2334:.
2309:.
2284:.
2259:.
2158:.
2138:.
1703:j
1699:T
1676:i
1672:T
1649:j
1645:T
1622:i
1618:T
1443:,
1115:i
1111:T
1088:i
1084:T
1058:j
1054:T
1031:i
1027:T
1001:i
997:T
974:i
970:T
524:)
319:i
299:)
296:X
293:(
290:i
287:W
261:i
241:)
238:X
235:(
232:i
229:R
130:)
124:(
119:)
115:(
105:·
98:·
91:·
84:·
57:.
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
