Precedence graph for testing conflict serializability

Java

The idea is to read a schedule from the user and to test it if it is conflict serializable or not and to draw its precedence graph

in a simple manner ( T1---->T3------>T2 or T1---->T3------>T1 etc...).

I need a simple program in Java without interfaces(GUI).

SC383 Programming Project

C o n fl i c t S e r i a l i z a b i l i t y i n

T r a n s a c t i o n s .

College of Computer and Information Sciences

King Saud University

S p r i n g 2 0 1 8

1 Introduction

A transaction, in the context of a database, is a logical unit that is independently executed for data retrieval or updates. In

relational databases, database transactions must be atomic, consistent, isolated and durable--summarized as the ACID

acronym. Two schedules are conflict-equivalent if one can be reached from the other through a series of swaps of adjacent

operations, where no swap falls into one of the following patterns:

 the operations are by the same transaction

 the operations use the same database element, and at least one is a write

A schedule is conflict-serializable if it is conflict-equivalent to some serial schedule.

Your goal in this project is to implement a Conflict Serializable Checker with two basic operations: test for conflict

Serializability and draw a simple precedence graph. Your program should be linked with a main program in-order to test

its functionality. Note: you should choose the appropriate data structure for the program.

2 Requirements In this project you are required to implement a Conflict Serializable Checker to fulfill the

following requirements:

1. Read the size of the schedule from the user.

2. The program takes a schedule from the user in this form: : "r1x", "r2z", "r1z", "r3y",

"r3y",...

The first instruction “r1x” means: r = read, 1 = the transaction, x is the element

Let x be an arbitrary instruction, then:

x[0]: can take the form of r (read) or w (write) to set the operation

x[1]: can take the form of 1,2,3,...,n to set the transaction

x[2]: can take the form of a,b,c,...,z to set the element

3. Test for conflict Serializability.

4. Draw a simple precedence graph

3 Deliverable and Rules

The submission deadline is 07/05/2018 at 12:00 PM before the final Exam, you

should deliver:

1. A report written.

2. T h e Source code on a CD.

You have to read and follow the following rules:

1. This assignment is to be conducted by groups of exactly three students.

2. The students can implement their own data structures; use Java collections, or

any other library to achieve assignment’s requirements.

3. Every group member should participate in all parts of the assignment: de-

signing, programming, and writing the program and report. Members of the same

group may receive different marks according to their participation in the work.

4. The submitted program will be evaluated in a demonstration which all the group

members should attend.

5. Any member of the group who fails to attend the demonstration without a

proper excuse shall receive 0 in the demo mark.

6. In accordance with the university regulation, cheating in the project will be

penalized by the mark 0 in the project.

4 Appendix 1. Create a schedule: String[] schedule = {"r1x", "r2z", "r1z", "r3y", "r3y", "w1x", "w3y",

"r2y", "w2z", "w2y"};

2. Create an instance of Schedule: Schedule obj = new Schedule(schedule);

3. Can call one of three methods: o obj.getSchedule(): returns the schedule

o obj.precedenceGraph(): returns a graphical representation of the precedence graph

o obj.conflictSerializable(): returns information on the schedule

Input: String[] schedule = {"r1x", "r2z", "r1z", "r3y", "r3y", "w1x", "w3y", "r2y", "w2z", "w2y"};

Schedule obj = new Schedule(schedule);

System.out.println(obj.getSchedule());

System.out.println(obj.precedenceGraph());

System.out.println(obj.conflictSerializable());

Output: //getSchedule()

r1x, r2z, r1z, r3y, r3y, w1x, w3y, r2y, w2z, w2y,

//precedenceGraph()

3 -> 2

1 -> 2

//conflictSerializable()

Is Schedule Conflict-Serializable: True, Schedule is acyclic, thus it's conflict serializable.