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