Testing for Serializability

By -

Testing for Serializability

When designing concurrency control schemes, we must show that schedules generated by the scheme are serializable. To do that, we must first understand how to determine, given a particular schedule S, whether the schedule is serializable.

We now present a simple and efficient method for determining conflict serializ- ability of a schedule. Consider a schedule S. We construct a directed graph, called a precedence graph, from S. This graph consists of a pair G = (V, E), where V is a set of vertices and E is a set of edges. The set of vertices consists of all the transactions participating in the schedule. The set of edges consists of all edges Ti → Tj for which

one of three conditions holds:

1. Ti executes write(Q) before Tj executes read(Q).

2. Ti executes read(Q) before Tj executes write(Q).

3. Ti executes write(Q) before Tj executes write(Q).

image

If an edge Ti → Tj exists in the precedence graph, then, in any serial schedule S1 equivalent to S, Ti must appear before Tj .

For example, the precedence graph for schedule 1 in Figure 15.15a contains the single edge T1 → T2, since all the instructions of T1 are executed before the first instruction of T2 is executed. Similarly, Figure 15.15b shows the precedence graph for schedule 2 with the single edge T2 → T1, since all the instructions of T2 are executed before the first instruction of T1 is executed.

The precedence graph for schedule 4 appears in Figure 15.16. It contains the edge T1 → T2, because T1 executes read(A) before T2 executes write(A). It also contains the edge T2 → T1, because T2 executes read(B) before T1 executes write(B).

If the precedence graph for S has a cycle, then schedule S is not conflict serializable. If the graph contains no cycles, then the schedule S is conflict serializable.

A serializability order of the transactions can be obtained through topological sorting, which determines a linear order consistent with the partial order of the precedence graph. There are, in general, several possible linear orders that can be obtained through a topological sorting. For example, the graph of Figure 15.17a has the two acceptable linear orderings shown in Figures 15.17b and 15.17c.

Thus, to test for conflict serializability, we need to construct the precedence graph and to invoke a cycle-detection algorithm. Cycle-detection algorithms can be found in standard textbooks on algorithms. Cycle-detection algorithms, such as those based on depth-first search, require on the order of n2 operations, where n is the number of vertices in the graph (that is, the number of transactions). Thus, we have a practical scheme for determining conflict serializability.

Returning to our previous examples, note that the precedence graphs for schedules 1 and 2 (Figure 15.15) indeed do not contain cycles. The precedence graph for schedule 4 (Figure 15.16), on the other hand, contains a cycle, indicating that this schedule is not conflict serializable.

Testing for view serializability is rather complicated. In fact, it has been shown that the problem of testing for view serializability is itself NP-complete. Thus, almost certainly there exists no efficient algorithm to test for view serializability. See

image

image

the bibliographical notes for references on testing for view serializability. However, concurrency-control schemes can still use sufficient conditions for view serializability. That is, if the sufficient conditions are satisfied, the schedule is view serializable, but there may be view-serializable schedules that do not satisfy the sufficient conditions.

Comments

Post a Comment

Popular posts from this blog

Concurrency Control:Shadow Paging

By -
Image
Shadow Paging An alternative to log-based crash-recovery techniques is shadow paging . The shadow-paging technique is essentially an improvement on the shadow-copy technique that we saw in Section 15.3. Under certain circumstances, shadow paging may require fewer disk accesses than do the log-based methods discussed previously. There are, however, disadvantages to the shadow-paging approach, as we shall see, that limit its use. For example, it is hard to extend shadow paging to allow multiple transactions to execute concurrently. As before, the database is partitioned into some number of fixed-length blocks, which are referred to as pages . The term page is borrowed from operating systems, since we are using a paging scheme for memory management. Assume that there are n pages, numbered 1 through n . (In practice, n may be in the hundreds of thousands.) These pages do not need to be stored in any particular order on disk (there are many reasons why they do not, as we saw in Chapter 1
Read more

Entity-Relationship Model part2

By -
Image
Refining the COMPANY database schema by introducing relationships By examining the requirements, six relationship types are identified. All are binary relationships( degree 2) Listed below with their participating entity types: WORKS_FOR (between EMPLOYEE, DEPARTMENT) MANAGES (also between EMPLOYEE, DEPARTMENT) CONTROLS (between DEPARTMENT, PROJECT) WORKS_ON (between EMPLOYEE, PROJECT) SUPERVISION (between EMPLOYEE (as subordinate), EMPLOYEE (as supervisor)) DEPENDENTS_OF (between EMPLOYEE, DEPENDENT) ER DIAGRAM – Relationship Types are: WORKS_FOR, MANAGES, WORKS_ON, CONTROLS, SUPERVISION, DEPENDENTS_OF R elationship Types In the refined design, some attributes from the initial entity types are refined into relationships: Manager of DEPARTMENT -> MANAGES Works_on of EMPLOYEE -> WORKS_ON Department of EMPLOYEE -> WORKS_FOR etc In general, more than one relationship type can exist between the same participating entity types MANAGES and WORKS_FOR are distinct relationshi
Read more

XML Document Schema

By -
Image
XML Document Schema Databases have schemas, which are used to constrain what information can be stored in the database and to constrain the data types of the stored information. In contrast, by default, XML documents can be created without any associated schema: An el- ement may then have any subelement or attribute. While such freedom may occasionally be acceptable given the self-describing nature of the data format, it is not generally useful when XML documents must be processesed automatically as part of an application, or even when large amounts of related data are to be formatted in XML. Here, we describe the document-oriented schema mechanism included as part of the XML standard, the Document Type Definition , as well as the more recently defined XML S chema . Document Type Definition The document type definition ( D TD ) is an optional part of an XML document. The main purpose of a DTD is much like that of a schema: to constrain and type the information present in the docume
Read more