Global serializability
   HOME

TheInfoList



OR:

In
concurrency control In information technology and computer science, especially in the fields of computer programming, operating systems, multiprocessors, and databases, concurrency control ensures that correct results for concurrent operations are generated, while ...
of ''
database In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases s ...
s'', ''
transaction processing Transaction processing is information processing in computer science that is divided into individual, indivisible operations called ''transactions''. Each transaction must succeed or fail as a complete unit; it can never be only partially compl ...
'' (''transaction management''), and other transactional distributed applications, global serializability (or modular serializability) is a property of a ''global schedule'' of transactions. A global schedule is the unified schedule of all the individual database (and other
transactional object Transaction or transactional may refer to: Commerce * Financial transaction, an agreement, communication, or movement carried out between a buyer and a seller to exchange an asset for payment *Debits and credits in a Double-entry bookkeeping sys ...
) schedules in a multidatabase environment (e.g.,
federated database A federated database system (FDBS) is a type of meta-database management system (DBMS), which transparently maps multiple autonomous database systems into a single federated database. The constituent databases are interconnected via a computer netwo ...
). Complying with global serializability means that the global schedule is '' serializable'', has the ''
serializability In concurrency control of databases, Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman (1987)''Concurrency Control and Recovery in Database Systems''(free PDF download), Addison Wesley Publishing Company, Gerhard Weikum, Gottfried Vossen (20 ...
'' property, while each component database (module) has a serializable schedule as well. In other words, a collection of serializable components provides overall system serializability, which is usually incorrect. A need in correctness across databases in multidatabase systems makes global serializability a major goal for '' global concurrency control'' (or ''modular concurrency control''). With the proliferation of the
Internet The Internet (or internet) is the global system of interconnected computer networks that uses the Internet protocol suite (TCP/IP) to communicate between networks and devices. It is a '' network of networks'' that consists of private, pub ...
,
Cloud computing Cloud computing is the on-demand availability of computer system resources, especially data storage ( cloud storage) and computing power, without direct active management by the user. Large clouds often have functions distributed over mu ...
, Grid computing, and small, portable, powerful computing devices (e.g.,
smartphone A smartphone is a portable computer device that combines mobile telephone and computing functions into one unit. They are distinguished from feature phones by their stronger hardware capabilities and extensive mobile operating systems, whic ...
s), as well as increase in systems management sophistication, the need for atomic distributed transactions and thus effective global serializability techniques, to ensure correctness in and among distributed transactional applications, seems to increase. In a
federated database system A federated database system (FDBS) is a type of meta- database management system (DBMS), which transparently maps multiple autonomous database systems into a single federated database. The constituent databases are interconnected via a computer netw ...
or any other more loosely defined multidatabase system, which are typically distributed in a communication network, transactions span multiple (and possibly
distributed Distribution may refer to: Mathematics *Distribution (mathematics), generalized functions used to formulate solutions of partial differential equations *Probability distribution, the probability of a particular value or value range of a varia ...
) databases. Enforcing global serializability in such system, where different databases may use different types of
concurrency control In information technology and computer science, especially in the fields of computer programming, operating systems, multiprocessors, and databases, concurrency control ensures that correct results for concurrent operations are generated, while ...
, is problematic. Even if every local schedule of a single database is serializable, the global schedule of a whole system is not necessarily serializable. The massive communication exchanges of conflict information needed between databases to reach conflict serializability globally would lead to unacceptable performance, primarily due to computer and communication latency. Achieving global serializability effectively over different types of concurrency control has been
open Open or OPEN may refer to: Music * Open (band), Australian pop/rock band * The Open (band), English indie rock band * ''Open'' (Blues Image album), 1969 * ''Open'' (Gotthard album), 1999 * ''Open'' (Cowboy Junkies album), 2001 * ''Open'' ( ...
for several years. ''
Commitment ordering Commitment ordering (CO) is a class of interoperable '' serializability'' techniques in concurrency control of databases, transaction processing, and related applications. It allows optimistic (non-blocking) implementations. With the proliferation ...
'' (or Commit ordering; CO), a serializability technique publicly introduced in 1991 by
Yoav Raz Joab (Hebrew Modern: ''Yōʼav'', Tiberian: ''Yōʼāḇ'') the son of Zeruiah, was the nephew of King David and the commander of his army, according to the Hebrew Bible. Name The name Joab is, like many other Hebrew names, theophoric - deri ...
from
Digital Equipment Corporation Digital Equipment Corporation (DEC ), using the trademark Digital, was a major American company in the computer industry from the 1960s to the 1990s. The company was co-founded by Ken Olsen and Harlan Anderson in 1957. Olsen was president un ...
(DEC), provides an effective general solution for global (
conflict Conflict may refer to: Arts, entertainment, and media Films * ''Conflict'' (1921 film), an American silent film directed by Stuart Paton * ''Conflict'' (1936 film), an American boxing film starring John Wayne * ''Conflict'' (1937 film) ...
) serializability across any collection of database systems and other
transactional object Transaction or transactional may refer to: Commerce * Financial transaction, an agreement, communication, or movement carried out between a buyer and a seller to exchange an asset for payment *Debits and credits in a Double-entry bookkeeping sys ...
s, with possibly different concurrency control mechanisms. CO does not need the distribution of conflict information, but rather utilizes the already needed (unmodified)
atomic commitment Atomic may refer to: * Of or relating to the atom, the smallest particle of a chemical element that retains its chemical properties * Atomic physics, the study of the atom * Atomic Age, also known as the "Atomic Era" * Atomic scale, distances comp ...
protocol messages without any further communication between databases. It also allows
optimistic Optimism is an attitude reflecting a belief or hope that the outcome of some specific endeavor, or outcomes in general, will be positive, favorable, and desirable. A common idiom used to illustrate optimism versus pessimism is a glass filled ...
(non-blocking) implementations. CO generalizes '' strong strict two phase locking'' (SS2PL), which in conjunction with the ''
two-phase commit In transaction processing, databases, and computer networking, the two-phase commit protocol (2PC) is a type of atomic commitment protocol (ACP). It is a distributed algorithm that coordinates all the processes that participate in a distributed ...
'' (2PC) protocol is the
de facto standard A ''de facto'' standard is a custom or convention that has achieved a dominant position by public acceptance or market forces (for example, by early entrance to the market). is a Latin phrase (literally " in fact"), here meaning "in practice b ...
for achieving global serializability across (SS2PL based) database systems. As a result, CO compliant database systems (with any, different concurrency control types) can transparently join existing SS2PL based solutions for global serializability. The same applies also to all other multiple (transactional) object systems that use atomic transactions and need global serializability for correctness (see examples above; nowadays such need is not smaller than with database systems, the origin of atomic transactions).


Benefits of CO for global serializability

#Seamless, low overhead integration with any concurrency control mechanism, with neither changing any transaction's operation scheduling or blocking it, nor adding any new operation. #
Heterogeneity Homogeneity and heterogeneity are concepts often used in the sciences and statistics relating to the uniformity of a substance or organism. A material or image that is homogeneous is uniform in composition or character (i.e. color, shape, siz ...
: Global serializability is achieved across multiple transactional objects (e.g., database management systems) with different (any) concurrency control mechanisms, without interfering with the mechanisms' operations. # Modularity: Transactional objects can be added and removed transparently. # Autonomy of transactional objects: No need of conflict or equivalent information distribution (e.g., local precedence relations, locks, timestamps, or tickets; no object needs other object's information). #
Scalability Scalability is the property of a system to handle a growing amount of work by adding resources to the system. In an economic context, a scalable business model implies that a company can increase sales given increased resources. For example, a ...
: With "normal" global transactions,
computer network A computer network is a set of computers sharing resources located on or provided by network nodes. The computers use common communication protocols over digital interconnections to communicate with each other. These interconnections are ...
size and number of transactional objects can increase unboundedly with no impact on performance, and #Automatic global deadlock resolution. All these aspects, except the first two, are also possessed by the popular SS2PL, which is a (constrained, blocking) special case of CO and inherits many of CO's qualities.


The global serializability problem


Problem statement

The difficulties described above translate into the following problem: :Find an efficient (high-performance and
fault tolerant Fault tolerance is the property that enables a system to continue operating properly in the event of the failure of one or more faults within some of its components. If its operating quality decreases at all, the decrease is proportional to the ...
) method to enforce ''Global serializability'' (global conflict serializability) in a heterogeneous distributed environment of multiple autonomous database systems. The database systems may employ different
concurrency control In information technology and computer science, especially in the fields of computer programming, operating systems, multiprocessors, and databases, concurrency control ensures that correct results for concurrent operations are generated, while ...
methods. No limitation should be imposed on the operations of either local transactions (confined to a single database system) or global transactions (span two or more database systems).


Quotations

Lack of an appropriate solution for the global serializability problem has driven researchers to look for alternatives to
serializability In concurrency control of databases, Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman (1987)''Concurrency Control and Recovery in Database Systems''(free PDF download), Addison Wesley Publishing Company, Gerhard Weikum, Gottfried Vossen (20 ...
as a correctness criterion in a multidatabase environment (e.g., see '' Relaxing global serializability'' below), and the problem has been characterized as difficult and ''
open Open or OPEN may refer to: Music * Open (band), Australian pop/rock band * The Open (band), English indie rock band * ''Open'' (Blues Image album), 1969 * ''Open'' (Gotthard album), 1999 * ''Open'' (Cowboy Junkies album), 2001 * ''Open'' ( ...
''. The following two quotations demonstrate the mindset about it by the end of the year 1991, with similar quotations in numerous other articles: *"Without knowledge about local as well as global transactions, it is highly unlikely that efficient global concurrency control can be provided... Additional complications occur when different component DBMSs atabase Management Systemsand the FDBMSs ederated Database Management Systemssupport different concurrency mechanisms... It is unlikely that a theoretically elegant solution that provides conflict serializability without sacrificing performance (i.e., concurrency and/or response time) and
availability In reliability engineering, the term availability has the following meanings: * The degree to which a system, subsystem or equipment is in a specified operable and committable state at the start of a mission, when the mission is called for at ...
exists."
Commitment ordering Commitment ordering (CO) is a class of interoperable '' serializability'' techniques in concurrency control of databases, transaction processing, and related applications. It allows optimistic (non-blocking) implementations. With the proliferation ...
, publicly introduced in May 1991 (see below), provides an efficient
elegant Elegance is beauty that shows unusual effectiveness and simplicity. Elegance is frequently used as a standard of tastefulness, particularly in visual design, decorative arts, literature, science, and the aesthetics of mathematics. Elegant t ...
general solution, from both practical and
theoretical A theory is a rational type of abstract thinking about a phenomenon, or the results of such thinking. The process of contemplative and rational thinking is often associated with such processes as observational study or research. Theories may be ...
points of view, to the global serializability problem across database systems with possibly different concurrency control mechanisms. It provides conflict serializability with no negative effect on availability, and with no worse performance than the
de facto standard A ''de facto'' standard is a custom or convention that has achieved a dominant position by public acceptance or market forces (for example, by early entrance to the market). is a Latin phrase (literally " in fact"), here meaning "in practice b ...
for global serializability, CO's special case strong strict two-phase locking (SS2PL). It requires knowledge about neither local nor global transactions. *"Transaction management in a heterogeneous, distributed database system is a difficult issue. The main problem is that each of the local database management systems may be using a different type of concurrency control scheme. Integrating this is a challenging problem, made worse if we wish to preserve the local autonomy of each of the local databases, and allow local and global transactions to execute in parallel. One simple solution is to restrict global transactions to retrieve-only access. However, the issue of reliable transaction management in the general case, where global and local transactions are allowed to both read and write data, is still open." The commitment ordering solution comprises effective integration of autonomous database management systems with possibly different concurrency control mechanisms. This while local and global transactions execute in parallel without restricting any read or write operation in either local or global transactions, and without compromising the systems' autonomy. Even in later years, after the public introduction of the Commitment ordering general solution in 1991, the problem still has been considered by many unsolvable: *"We present a transaction model for multidatabase systems with autonomous component systems, coined heterogeneous 3-level transactions. It has become evident that in such a system the requirements of guaranteeing full ACID properties and full local autonomy can not be reconciled..." The quotation above is from a 1997 article proposing a relaxed global serializability solution (see '' Relaxing global serializability'' below), and referencing
Commitment ordering Commitment ordering (CO) is a class of interoperable '' serializability'' techniques in concurrency control of databases, transaction processing, and related applications. It allows optimistic (non-blocking) implementations. With the proliferation ...
(CO) articles. The CO solution supports effectively both full ACID properties and full local autonomy, as well as meeting the other requirements posed above in the ''
Problem statement A problem statement is a concise description of an issue to be addressed or a condition to be improved upon. It identifies the gap between the current (problem) state and desired (goal) state of a process or product. Focusing on the facts, the prob ...
'' section, and apparently has been misunderstood. Similar thinking we see also in the following quotation from a 1998 article: *"The concept of serializability has been the traditionally accepted correctness criterion in database systems. However in multidatabase systems (MDBSs), ensuring global serializability is a difficult task. The difficulty arises due to the heterogeneity of the concurrency control protocols used by the participating local database management systems (DBMSs), and the desire to preserve the autonomy of the local DBMSs. In general, solutions to the global serializability problem result in executions with a low degree of concurrency. The alternative, relaxed serializability, may result in data inconsistency."Sharad Mehrotra, Rajeev Rastogi, Henry Korth,
Abraham Silberschatz Avi Silberschatz (born in Haifa, Israel) is an Israeli computer scientist and researcher. He graduated in 1976 with a Ph.D. in Computer Science from the State University of New York (SUNY) at Stony Brook. He became the Sidney J. Weinberg Profe ...
(1998)
"Ensuring Consistency in Multidatabases by Preserving Two-Level Serializability"
''ACM Transactions on Database Systems'' (TODS), Vol. 23, No. 2, pp. 199-230, June 1998 (quotation from the article's Abstract)
Also the above quoted article proposes a relaxed global serializability solution, while referencing the CO work. The CO solution for global serializability both bridges between different concurrency control protocols with no substantial concurrency reduction (and typically minor, if at all), and maintains the autonomy of local DBMSs. Evidently also here CO has been misunderstood. This misunderstanding continues to 2010 in a textbook by some of the same authors, where the same relaxed global serializability technique, ''Two level serializability'', is emphasized and described in detail, and CO is not mentioned at all. Avi Silberschatz, Henry F Korth, S. Sudarshan (2010)
''Database System Concepts''
6th Edition, McGraw-Hill,
On the other hand, the following quotation on CO appears in a 2009 book: Philip A. Bernstein, Eric Newcomer (2009)
''Principles of Transaction Processing'', 2nd Edition
, Morgan Kaufmann (Elsevier), June 2009, (quotation from page 145)
*"Not all concurrency control algorithms use locks... Three other techniques are timestamp ordering, serialization graph testing, and commit ordering. Timestamp ordering assigns each transaction a timestamp and ensures that conflicting operations execute in timestamp order. Serialization graph testing tracks conflicts and ensures that the serialization graph is acyclic. Commit ordering ensures that conflicting operations are consistent with the relative order in which their transactions commit, which can enable interoperability of systems using different concurrency control mechanisms." :Comments: #Beyond the common locking based algorithm SS2PL, which is a CO variant itself, also additional variants of CO that use locks exist, (see below). However, generic, or "pure" CO does not use locks. #Since CO mechanisms order the commit events according to conflicts that already have occurred, it is better to describe CO as "Commit ordering ensures that the relative order in which transactions commit is consistent with the order of their respective conflicting operations." The characteristics and properties of the CO solution are discussed below.


Proposed solutions

Several solutions, some partial, have been proposed for the global serializability problem. Among them: * ''Global conflict graph'' (serializability graph, precedence graph) ''checking'' * ''Distributed Two phase locking'' (Distributed 2PL) * ''Distributed Timestamp ordering'' * ''Tickets'' (local logical timestamps which define local total orders, and are propagated to determine global partial order of transactions) * ''Commitment ordering''


Technology perspective

The problem of global serializability has been a quite intensively researched subject in the late 1980s and early 1990s. ''Commitment ordering'' (CO) has provided an effective general solution to the problem, insight into it, and understanding about possible generalizations of '' strong strict two phase locking'' (SS2PL), which practically and almost exclusively has been utilized (in conjunction with the ''
Two-phase commit protocol In transaction processing, databases, and computer networking, the two-phase commit protocol (2PC) is a type of atomic commitment protocol (ACP). It is a distributed algorithm that coordinates all the processes that participate in a distributed ...
'' (2PC) ) since the 1980s to achieve global serializability across databases. An important side-benefit of CO is the automatic ''global deadlock'' resolution that it provides (this is applicable also to distributed SS2PL; though global deadlocks have been an important research subject for SS2PL, automatic resolution has been overlooked, except in the CO articles, until today (2009)). At that time quite many commercial database system types existed, many non-relational, and databases were relatively very small. Multi database systems were considered a key for database scalability by database systems interoperability, and global serializability was urgently needed. Since then the tremendous progress in computing power, storage, and communication networks, resulted in
orders of magnitude An order of magnitude is an approximation of the logarithm of a value relative to some contextually understood reference value, usually 10, interpreted as the base of the logarithm and the representative of values of magnitude one. Logarithmic dis ...
increases in both centralized databases' sizes, transaction rates, and remote access to database capabilities, as well as blurring the boundaries between centralized computing and distributed one over fast, low-latency local networks (e.g.,
Infiniband InfiniBand (IB) is a computer networking communications standard used in high-performance computing that features very high throughput and very low latency. It is used for data interconnect both among and within computers. InfiniBand is also use ...
). These, together with progress in database vendors' distributed solutions (primarily the popular SS2PL with 2PC based, a
de facto standard A ''de facto'' standard is a custom or convention that has achieved a dominant position by public acceptance or market forces (for example, by early entrance to the market). is a Latin phrase (literally " in fact"), here meaning "in practice b ...
that allows interoperability among different vendors' (SS2PL-based) databases; both SS2PL and 2PC technologies have gained substantial expertise and efficiency),
workflow A workflow consists of an orchestrated and repeatable pattern of activity, enabled by the systematic organization of resources into processes that transform materials, provide services, or process information. It can be depicted as a sequence o ...
management systems, and
database replication Replication in computing involves sharing information so as to ensure consistency between redundant resources, such as software or hardware components, to improve reliability, fault-tolerance, or accessibility. Terminology Replication in comp ...
technology, in most cases have provided satisfactory and sometimes better
information technology Information technology (IT) is the use of computers to create, process, store, retrieve, and exchange all kinds of Data (computing), data . and information. IT forms part of information and communications technology (ICT). An information te ...
solutions without multi database atomic
distributed transaction A distributed transaction is a database transaction in which two or more network hosts are involved. Usually, hosts provide transactional resources, while the transaction manager is responsible for creating and managing a global transaction that enc ...
s over databases with different concurrency control (bypassing the problem above). As a result, the sense of urgency that existed with the problem at that period, and in general with high-performance distributed atomic transactions over databases with different concurrency control types, has reduced. However, the need in concurrent distributed atomic transactions as a fundamental element of reliability exists in distributed systems also beyond database systems, and so the need in global serializability as a fundamental correctness criterion for such transactional systems (see also Serializability#Distributed serializability, Distributed serializability in Serializability). With the proliferation of the
Internet The Internet (or internet) is the global system of interconnected computer networks that uses the Internet protocol suite (TCP/IP) to communicate between networks and devices. It is a '' network of networks'' that consists of private, pub ...
,
Cloud computing Cloud computing is the on-demand availability of computer system resources, especially data storage ( cloud storage) and computing power, without direct active management by the user. Large clouds often have functions distributed over mu ...
, Grid computing, small, portable, powerful computing devices (e.g.,
smartphone A smartphone is a portable computer device that combines mobile telephone and computing functions into one unit. They are distinguished from feature phones by their stronger hardware capabilities and extensive mobile operating systems, whic ...
s), and sophisticated systems management the need for effective global serializability techniques to ensure correctness in and among distributed transactional applications seems to increase, and thus also the need in Commitment ordering (including the popular for databases special case SS2PL; SS2PL, though, does not meet the requirements of many other transactional objects).


The commitment ordering solution

Commitment ordering
Yoav Raz Joab (Hebrew Modern: ''Yōʼav'', Tiberian: ''Yōʼāḇ'') the son of Zeruiah, was the nephew of King David and the commander of his army, according to the Hebrew Bible. Name The name Joab is, like many other Hebrew names, theophoric - deri ...
(1992)
"The Principle of Commitment Ordering, or Guaranteeing Serializability in a Heterogeneous Environment of Multiple Autonomous Resource Managers Using Atomic Commitment"
, ''Proc. of the Eighteenth Int. Conf. on Very Large Data Bases'' (VLDB), pp. 292-312, Vancouver, Canada, August 1992. (also DEC-TR 841,
Digital Equipment Corporation Digital Equipment Corporation (DEC ), using the trademark Digital, was a major American company in the computer industry from the 1960s to the 1990s. The company was co-founded by Ken Olsen and Harlan Anderson in 1957. Olsen was president un ...
, November 1990)
Yoav Raz (1994)
"Serializability by Commitment Ordering"
''Information Processing Letters''

pp. 257-264, September 1994. (Received August 1991)
(or Commit ordering; CO) is the only high-performance,
fault tolerant Fault tolerance is the property that enables a system to continue operating properly in the event of the failure of one or more faults within some of its components. If its operating quality decreases at all, the decrease is proportional to the ...
, conflict serializability providing solution that has been proposed as a fully distributed (no central computing component or data-structure are needed), general mechanism that can be combined seamlessly with any local (to a database)
concurrency control In information technology and computer science, especially in the fields of computer programming, operating systems, multiprocessors, and databases, concurrency control ensures that correct results for concurrent operations are generated, while ...
mechanism (see Commitment ordering#Summary, technical summary). Since the CO property of a schedule is a necessary condition for global serializability of Commitment ordering#CO is a necessary condition for global serializability across autonomous database systems, ''autonomous databases'' (in the context of concurrency control), it provides the only general solution for autonomous databases (i.e., if autonomous databases do not comply with CO, then global serializability may be violated). Seemingly by sheer luck, the CO solution possesses many attractive properties: #does not interfere with any transaction's operation, particularly neither block, restrict nor delay any data-access operation (read or write) for either local or distributed transaction, global transactions (and thus does not cause any extra aborts); thus allows seamless integration with any concurrency control mechanism. #allows
optimistic Optimism is an attitude reflecting a belief or hope that the outcome of some specific endeavor, or outcomes in general, will be positive, favorable, and desirable. A common idiom used to illustrate optimism versus pessimism is a glass filled ...
implementations (''non-blocking'', i.e., non data access blocking). #allows heterogeneity: Global serializability is achieved across multiple transactional objects with different (any) concurrency control mechanisms, without interfering with the mechanisms' operations. #allows modularity: Transactional objects can be added and removed transparently. #allows full ACID transaction support. #maintains each database's Commitment ordering#CO is a necessary condition for global serializability across autonomous database systems, autonomy, and does not need any concurrency control information distribution (e.g., local precedence relations, locks, timestamps, or tickets). #does not need any knowledge about the transactions. #requires no communication overhead since it only uses already needed, unmodified ''
atomic commitment Atomic may refer to: * Of or relating to the atom, the smallest particle of a chemical element that retains its chemical properties * Atomic physics, the study of the atom * Atomic Age, also known as the "Atomic Era" * Atomic scale, distances comp ...
'' protocol messages (any such protocol; using
fault tolerant Fault tolerance is the property that enables a system to continue operating properly in the event of the failure of one or more faults within some of its components. If its operating quality decreases at all, the decrease is proportional to the ...
atomic commitment protocols and database systems makes the CO solution fault tolerant). #automatically resolves global deadlocks due to lock (computer science), locking. #Scalability, scales up effectively with
computer network A computer network is a set of computers sharing resources located on or provided by network nodes. The computers use common communication protocols over digital interconnections to communicate with each other. These interconnections are ...
size and number of databases, almost without any negative impact on performance, since each global transaction is typically confined to certain relatively small numbers of databases and network nodes. #requires no additional, artificial transaction access operations (e.g., "take Timestamp-based concurrency control, timestamp" or "take ticket"), which typically result in additional, artificial conflicts that reduce concurrency. #requires low overhead. The only overhead incurred by the CO solution is locally detecting conflicts (which is already done by any known serializability mechanism, both pessimistic and optimistic) and locally ordering in each database system both the (local) commits of local transactions and the voting for atomic commitment of global transactions. Such overhead is low. The net effect of CO may be some delays of commit events (but never more delay than SS2PL, and on the average less). This makes CO instrumental for global concurrency control of multidatabase systems (e.g.,
federated database system A federated database system (FDBS) is a type of meta- database management system (DBMS), which transparently maps multiple autonomous database systems into a single federated database. The constituent databases are interconnected via a computer netw ...
s). The underlying ''Theory of Commitment ordering'',Yoav Raz (2009)
Theory of Commitment Ordering - Summary
GoogleSites - Site of Yoav Raz. Retrieved 1 Feb, 2011.
part of Serializability theory, is both sound and Scientific method#Hypothesis development, elegant (and even Mathematical beauty, "mathematically beautiful"; referring to structure and dynamics of conflicts, graph cycles, and deadlocks), with interesting implications for transactional distributed applications. All the qualities of CO in the list above, except the first three, are also possessed by SS2PL, which is a special case of CO, but blocking and constraining. This partially explains the popularity of SS2PL as a solution (practically, the only solution, for many years) for achieving global serializability. However, property 9 above, automatic resolution of global deadlocks, has not been noticed for SS2PL in the database research literature until today (2009; except in the CO publications). This, since the phenomenon of voting-deadlocks in such environments and their automatic resolution by the
atomic commitment Atomic may refer to: * Of or relating to the atom, the smallest particle of a chemical element that retains its chemical properties * Atomic physics, the study of the atom * Atomic Age, also known as the "Atomic Era" * Atomic scale, distances comp ...
protocol has been overlooked. Most existing database systems, including all major commercial database systems, are ''serializability#Common mechanism - SS2PL, strong strict two phase locking (SS2PL)'' based and already CO compliant. Thus they can participate in a commitment ordering#Summary, CO based solution for global serializability in multidatabase environments without any modification (except for the popular ''Multiversion concurrency control, multiversioning'', where additional CO aspects should be considered). Achieving global serializability across SS2PL based databases using atomic commitment (primarily using ''two phase commit, 2PC'') has been employed for many years (i.e., using the same CO solution for a specific special case; however, no reference is known prior to CO, that notices this special case's automatic global deadlock resolution by the atomic commitment protocol's commitment ordering#Exact characterization of voting-deadlocks by global cycles, augmented-conflict-graph global cycle elimination process). Virtually all existing distributed transaction processing environments and supporting products rely on SS2PL and provide 2PC. As a matter of fact SS2PL together with 2PC have become a
de facto standard A ''de facto'' standard is a custom or convention that has achieved a dominant position by public acceptance or market forces (for example, by early entrance to the market). is a Latin phrase (literally " in fact"), here meaning "in practice b ...
. This solution is a homogeneous concurrency control one, suboptimal (when both Serializability and Schedule (computer science)#Strict, Strictness are needed; see Commitment ordering#Strict CO (SCO), Strict commitment ordering; SCO) but still quite effective in most cases, sometimes at the cost of increased computing power needed relatively to the optimum. (However, for better performance Serializability#Relaxing serializability, relaxed serializability is used whenever applications allow). It allows inter-operation among SS2PL-compliant different database system types, i.e., allows heterogeneity in aspects other than concurrency control. SS2PL is a very constraining schedule property, and "takes over" when combined with any other property. For example, when combined with any Concurrency control#Concurrency control mechanisms, optimistic property, the result is not optimistic anymore, but rather characteristically SS2PL. On the other hand, CO does not change data-access scheduling patterns at all, and ''any'' combined property's characteristics remain unchanged. Since also CO uses atomic commitment (e.g., 2PC) for achieving global serializability, as SS2PL does, any CO compliant database system or transactional object can transparently join existing SS2PL based environments, use 2PC, and maintain global serializability without any environment change. This makes CO a straightforward, natural generalization of SS2PL for any conflict serializability based database system, for all practical purposes. Commitment ordering has been quite widely known inside the ''
transaction processing Transaction processing is information processing in computer science that is divided into individual, indivisible operations called ''transactions''. Each transaction must succeed or fail as a complete unit; it can never be only partially compl ...
'' and ''
database In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases s ...
s'' communities at ''
Digital Equipment Corporation Digital Equipment Corporation (DEC ), using the trademark Digital, was a major American company in the computer industry from the 1960s to the 1990s. The company was co-founded by Ken Olsen and Harlan Anderson in 1957. Olsen was president un ...
'' (DEC) since 1990. It has been under ''company confidentiality'' due to patentingYoav Raz (1990)
''On the Significance of Commitment Ordering''
- Call for patenting, Memorandum,
Digital Equipment Corporation Digital Equipment Corporation (DEC ), using the trademark Digital, was a major American company in the computer industry from the 1960s to the 1990s. The company was co-founded by Ken Olsen and Harlan Anderson in 1957. Olsen was president un ...
, November 1990.
Yoav Raz: US patent
5,504,899
[http://patft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=1&u=%2Fnetahtml%2FPTO%2Fsearch-bool.html&r=1&f=G&l=50&co1=AND&d=PTXT&s1=%22commitment+ordering%22.TI.&OS=TTL/ 5,701,480]
processes. CO was disclosed outside of DEC by lectures and technical reports' distribution to database researches in May 1991, immediately after its first patent filing. It has been misunderstood by many database researchers years after its introduction, which is evident by the quotes above from articles in 1997-1998 referencing Commitment ordering articles. On the other hand, CO has been utilized extensively as a solution for global serializability in works on Transactional processes, and more recently in the related Re:GRIDiT, Laura Cristiana Voicu and Heiko Schuldt (2009)
"How Replicated Data Management in the Cloud can benefit from a Data Grid Protocol — the Re:GRIDiT Approach"
''Proceedings of the 1st International Workshop on Cloud Data Management (CloudDB 2009)'', Hong Kong, China, 2009/11.
which is an approach for transaction management in the converging Grid computing and
Cloud computing Cloud computing is the on-demand availability of computer system resources, especially data storage ( cloud storage) and computing power, without direct active management by the user. Large clouds often have functions distributed over mu ...
. See more in ''The History of Commitment Ordering''.


Relaxing global serializability

Some techniques have been developed for relaxed global serializability (i.e., they do not guarantee global serializability; see also ''Serializability#Relaxing serializability, Relaxing serializability''). Among them (with several publications each): * ''Quasi serializability''Weimin Du and Ahmed K. Elmagarmid (1989)
"Quasi Serializability: a Correctness Criterion for Global Concurrency Control in InterBase"
, ''Proceedings of the Fifteenth International Conference on Very Large Data Bases'' (VLDB), August 22–25, 1989, Amsterdam, The Netherlands, pp. 347-355, Morgan Kaufmann,
* ''Two-level serializability'' While local (to a database system) relaxed serializability methods compromise ''serializability'' for performance gain (and are utilized only when the application can tolerate possible resulting inaccuracies, or its integrity is unharmed), it is unclear that various proposed ''relaxed global serializability'' methods which compromise ''global serializability'', provide any performance gain over ''commitment ordering'' which guarantees global serializability. Typically, the declared intention of such methods has not been performance gain over effective global serializability methods (which apparently have been unknown to the inventors), but rather correctness criteria alternatives due to lack of a known effective global serializability method. Oddly, some of them were introduced years after CO had been introduced, and some even quote CO without realizing that it provides an effective global serializability solution, and thus without providing any performance comparison with CO to justify them as alternatives to global serializability for some applications (e.g., ''Two-level serializability''). ''Two-level serializability'' is even presented as a major global concurrency control method in a 2010 edition of a text-book on databases (authored by two of the original authors of Two-level serializability, where one of them, Avi Silberschatz, is also an author of the original ''The History of Commitment Ordering#AESO is modified to Strong recoverability (CO), Strong recoverability'' articles). This book neither mentions CO nor references it, and strangely, apparently does not consider CO a valid ''Global serializability'' solution. Another common reason nowadays for Global serializability relaxation is the requirement of
availability In reliability engineering, the term availability has the following meanings: * The degree to which a system, subsystem or equipment is in a specified operable and committable state at the start of a mission, when the mission is called for at ...
of internet products and Internet service provider, services. This requirement is typically answered by large scale data Replication (computer science), replication. The straightforward solution for synchronizing replicas' updates of a same database object is including all these updates in a single atomic
distributed transaction A distributed transaction is a database transaction in which two or more network hosts are involved. Usually, hosts provide transactional resources, while the transaction manager is responsible for creating and managing a global transaction that enc ...
. However, with many replicas such a transaction is very large, and may span several computers and computer network, networks that some of them are likely to be unavailable. Thus such a transaction is likely to end with abort and miss its purpose. Consequently, Optimistic replication (Lazy replication) is often utilized (e.g., in many products and services by Google, Amazon.com, Amazon, Yahoo, and alike), while global serializability is relaxed and compromised for eventual consistency. In this case relaxation is done only for applications that are not expected to be harmed by it. Classes of schedules defined by ''relaxed global serializability'' properties either contain the global serializability class, or are incomparable with it. What differentiates techniques for ''relaxed global conflict serializability'' (RGCSR) properties from those of ''relaxed conflict serializability'' (RCSR) properties that are not RGCSR is typically the different way ''global cycles'' (span two or more databases) in the ''global conflict graph'' are handled. No distinction between global and local cycles exists for RCSR properties that are not RGCSR. RCSR contains RGCSR. Typically RGCSR techniques eliminate local cycles, i.e., provide ''local serializability'' (which can be achieved effectively by regular, known
concurrency control In information technology and computer science, especially in the fields of computer programming, operating systems, multiprocessors, and databases, concurrency control ensures that correct results for concurrent operations are generated, while ...
methods); however, obviously they do not eliminate all global cycles (which would achieve global serializability).


References

{{DEFAULTSORT:Global Serializability Data management Databases Transaction processing Concurrency control