469,578 Members | 1,214 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,578 developers. It's quick & easy.

please solve this problem

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).
assume that the cycle in the graph between no more than 2 transactions
Using Command Line Prompt to Run Programs

1. From inside .NET, create a new Windows Console Application and choose it to be a "Hello World" project.
2. You will have something that looks like:

#include "stdafx.h"

int main(int argc, char* argv[])
{
printf("Hello World!\n");
return 0;
}
argc is the number of arguments you passed in the command line.
argv is an array of the arguments you passed in the command line.
Your input file name is in argv[1].

3. You should do the following at the very beginning of your program:
char inFileName[100];
if (argc < 2)
{
printf("Please enter an input file name\n");
exit(1);
}
strcpy(inFileName,argv[1]);

4. Program your assignment by first reading from file inFileName.
5. After you are done programming, from inside .NET, compile and build your program. You will have an executable file (.exe) in the DEBUG directory under your project directory.
6. From Windows start menu, choose Run.
7. In the window that appears, write cmd. A black window appears. This is called command line. Here you use DOS to do things.
8. Type cd to go to you project directory.
cd My Documents
cd myProject
cd DEBUG

9. Now, you are in the directory where the executable is. Type dir at the command prompt and you should find CSR.exe and also your input text file (where the schedule you are testing is saved). Say you named your input file input1.txt.
10. To run the file, type
CSR input1.txt


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.
Nov 17 '06 #1
0 1743

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

28 posts views Thread by stu_gots | last post: by
23 posts views Thread by Jason | last post: by
5 posts views Thread by CoreyWhite | last post: by
5 posts views Thread by settyv | last post: by
1 post views Thread by shapper | last post: by
6 posts views Thread by shapper | last post: by
4 posts views Thread by guiromero | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.