Solved

conflict-serializbility\recoverability checker

Posted on 2006-10-31
1
727 Views
Last Modified: 2012-06-27
Overview
A conflict-serializbility\recoverability checker, SCR, is a program that takes in a schedule and outputs 2 decisions: Conflict serialzable or Not confilict serializable AND Recoverable or Not recoverable. The following is a detailed description of the program.

Input
The input to SCR should be a schedule of operations. It should be in a text file (.txt) where each line is in the following format:

Operation TransactionNum [DataItemNum]

Operation is the operation to be performed. It is one of the following:
•      begin      indicates the beginning of a transaction.
•      read      indicates a read operation on a data item by a transaction.
•      write      indicates a write operation on a data item by a transaction.
•      Commit      indicates an end of a transaction.

TransactionNum  is the number of the transaction performing the operation. It is a non-negative integer.

DataItemNum        is the number of the data item the operation is performed on. It is a non-negative integer.

Sample Input Lines
begin 4            means that T4 has started.
read 8 5            means that T8 is reading X5.
write 20 3      means that T20 is writing X3.

Sample Input File  input1.txt
begin 1
read 1 3
write 1 3
begin 2
read 2 4
begin 3
read 3 6
commit 3
read 2 3
write 2 3
read 1 4
write 1 4
commit 1
commit 2

Note: All input is in lowercase.
Output
CSR produces output in a file residing in the same directory as CSR. The file should have the following name result_X.txt. X is the input file name for which this output is produced. The system produces exactly 2 lines (all in lowercase):

LINE 1: If the input schedule is conflict serializable, then the output file should contain in the first line the following sentence:
schedule is conflict serializable.  
Otherwise, the output file should contain the following sentence:
schedule is not conflict serializable.

LINE 2: If the input schedule is recoverable, then the output file should contain in the second line the following sentence:
schedule is recoverable.  
Otherwise, the output file should contain the following sentence:
schedule is not recoverable.

Sample Output File for input1.txt  output file name: result_input1.txt
schedule is not conflict serializable.
schedule is recoverable.



Implementation Details

1.      CSR needs to build a wait-for graph (WFG) to decide whether or not the schedule is recoverable. Implement a graph using any of the data structures you learned in previous programming courses. After building the WFG, lock for a cycle, if you find one then the schedule is not conflict serializable. Otherwise, it is conflict serializable.

2.      CSR should check every write followed by a read of the same data item by a different transaction in the schedule. If the commit of the first precedes the commit of the second, then the schedule is recoverable. Otherwise, it is not recoverable.
 
Assignment

1-      Implement CSR described above using C++.
a.      The program should be a Windows 32 console application.
b.      Name your program CSR.
c.      Your program should take from the command line one argument which is the input file name.
d.      The output of your program is a text file named inputFileName_result.txt. Where inputFileName is the name of the input file without the extension.
e.      You need to follow the input\output format very carefully. Grading will be done automatically so any difference in formatting may lead to errors and therefore you getting a zero.
f.      Hand in the source code of your program on a CD along with an executable. So, we need the source code and the executable (.exe).

2-      Answer the following questions:
a.      Which of the following databases uses this technique to check for conflict serializability:
i.      Oracle.
ii.      Access.
iii.      SQL server.
b.      What is the advantage of recoverable schedules?
c.      If a schedule was found to be not conflict serializable, does this mean it is view serializable? Explain.
0
Comment
Question by:suliman_222
1 Comment
 
LVL 18

Accepted Solution

by:
JoseParrot earned 500 total points
ID: 17847555
Hi,

I'm not sure if I am understanding the question. Are you waiting for the program code as in 1? Or for answers to the 3 questions in 2?

Also, is it an assignment at your course? If so, we are not of help in solving YOUR assignment, but we would be glad in supporting you with OUR best efforts.

Jose
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
sumDigits  challenge 7 75
stringclean challenge 26 71
pairs challenge 5 66
"Black Box" Testing of Control System Software 2 26
Here we come across an interesting topic of coding guidelines while designing automation test scripts. The scope of this article will not be limited to QTP but to an overall extent of using VB Scripting for automation projects. Introduction Now…
This is about my first experience with programming Arduino.
In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable …
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…

867 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

22 Experts available now in Live!

Get 1:1 Help Now