|
Since determining whether a schedule is view-serializable is [[NP-complete]], view-serializability has little practical interest.{{citation needed|date=April 2015}}
==== Relaxed serializability ====
'''Relaxed serializability''' allows controlled serializability violations in order to achieve higher performance. Higher performance means better transaction execution rate and shorter average transaction response time (transaction duration). Relaxed serializability is used when absolute correctness is not needed from recently modified data (such as when retrieving a list of products). ''[[Snapshot isolation]]'' is a common relaxed serializability method.
Relaxing distributed serializability is often necessary for efficient large-scale data [[Replication (computer science)|replication]] because using a single atomic [[distributed transaction]] for synchronizing multiple replicas is likely to have unavailable [[computer]]s and [[Computer network|networks]] which would cause aborts.<ref name="Gray1996">{{cite conference |author=Gray, J. |author-link=Jim Gray (computer scientist) |author2=Helland, P. |author3=O’Neil, P. |author3-link=Patrick O'Neil |author4=Shasha, D. |author4-link=Dennis Shasha |year=1996 |title=The dangers of replication and a solution |url=ftp://ftp.research.microsoft.com/pub/tr/tr-96-17.pdf |conference=Proceedings of the 1996 [[ACM SIGMOD International Conference on Management of Data]] |pages=173–182 |doi=10.1145/233269.233330}}{{dead link|date=May 2018|bot=InternetArchiveBot|fix-attempted=yes}}</ref> [[Optimistic replication]] is a common distributed serializability relaxation method which compromises [[eventual consistency]].
Classes of schedules defined by ''relaxed serializability'' properties either contain the serializability class, or are incomparable with it.
==== Distributed serializability ====
'''Distributed serializability''' is the serializability of a schedule of a transactional [[Distributed computing|distributed system]] (e.g., a [[distributed database]] system). Such a system is characterized by ''[[distributed transaction]]s'' (also called ''global transactions''), i.e., transactions that span computer processes (a process abstraction in a general sense, depending on computing environment; e.g., [[operating system]]'s [[Thread (computer science)|thread]]) and possibly network nodes. A distributed transaction comprises more than one of several ''local sub-transactions'' that each has states as described above for a [[database transaction]]. A local sub-transaction comprises a single process, or more processes that typically fail together (e.g., in a single [[processor core]]). Distributed transactions imply a need for an [[atomic commit]] protocol to reach consensus among its local sub-transactions on whether to commit or abort. Such protocols can vary from a simple (one-phase) handshake among processes that fail together to more sophisticated protocols, like [[Two-phase commit protocol|two-phase commit]], to handle more complicated cases of failure (e.g., process, node, communication, etc. failure). Distributed serializability is a major goal of [[distributed concurrency control]] for correctness. With the proliferation of the [[Internet]], [[cloud computing]], [[grid computing]], and small, portable, powerful computing devices (e.g., [[smartphone]]s,) the need for effective distributed serializability techniques to ensure correctness in and among distributed applications seems to increase.
Distributed serializability is achieved by implementing distributed versions of the known centralized techniques.<ref name="Bernstein872"/><ref name="Weikum012"/> Typically, all such distributed versions require utilizing conflict information (of either materialized or non-materialized conflicts, or, equivalently, transaction precedence or blocking information; conflict serializability is usually utilized) that is not generated locally, but rather in different processes, and remote locations. Thus information distribution is needed (e.g., precedence relations, lock information, timestamps, or tickets). When the distributed system is of a relatively small scale and message delays across the system are small, the centralized concurrency control methods can be used unchanged while certain processes or nodes in the system manage the related algorithms. However, in a large-scale system (e.g., ''grid'' and ''cloud''), due to the distribution of such information, a substantial performance penalty is typically incurred, even when distributed versions of the methods (vs. the centralized ones) are used, primarily due to computer and communication [[Latency (engineering)|latency]]. Also, when such information is distributed, related techniques typically do not scale well. A well-known example with respect to scalability problems is a [[distributed lock manager]], which distributes lock (non-materialized conflict) information across the distributed system to implement locking techniques.
===Recoverable===<!-- This section is linked from [[Concurrency control]] -->
The following expressions illustrate the hierarchical (containment) relationships between [[serializability]] and [[Serializability#Correctness - recoverability|recoverability]] classes:
* Serial ⊂ commitment-ordered ⊂ conflict-serializable ⊂ view-serializable ⊂ all schedules
* Serial ⊂ strict ⊂ cascadeless (ACA) ⊂ recoverable ⊂ all schedules
|
