Ask Question, Ask an Expert

+1-415-315-9853

info@mywordsolution.com

Ask Programming Language Expert

1 Introduction

In this assignment, you will carry out a number of exercises to investigate the creation and searching of heap and sorted files.

General Requirements

This section contains information about the general requirements that your assignment must meet. Please read all requirements carefully before you start.

1. You must implement your programs in C. Your programs must be well written, using good coding style and including appropriate use of comments.

2. Your programs may be developed on any machine, but must compile and run on yallara.

3. Any code you submit must be able to be built using a single Makefile with the command:

> make all

Tasks

a) Writing a heap file

prepare a program to create a heap file that holds the records currently in the file /scratch/ DatabaseSystems/DATA/data 2012 on yallara. The source records are variable-length. However, the heap file should hold fixed-length records. Create the new records according to the schema given in Table 1. All attributes with Unsigned Int type must be stored in binary, e.g. if the value of ID is equal to 70, it must be stored as 70 (in decimal) or 46 (in hexadecimal; in C: 0x46). It must not be stored as the string “70”, occupying two bytes. Your heap file is therefore a binary file. For simplicity, the heap file does not need a header (containing things like the number of records in the file or a free space list). The file should be packed, i.e. there is no gap between 2 records.

Table : Relation schema.

Attribute name          Data type           Size (bytes)
NAME                        Char                      13
RACE                         Unsigned Int             2
CLASS                       Unsigned Int             2
ID                             Unsigned Int             4
GUILD                          Char                     30
Total size:                                               51

Note that you will need to ensure that the size of each record matches the size shown in Table . To ensure that records are correctly packed in memory, you may need to use the following directive in your code before you define your structure:

#pragma pack(1)

The executable name of this program must be wHeap and should be executed using the command:
> ./wHeap data_2012 heap pagesize

where data 2012 is the input file, heap is an output file to which your converted data is written, and pagesize is an integer specifying how many records fit into a “page” of your file.

Your program should prepare out one “page” of the file at a time (for ex, with a pagesize of 100, you would prepare out 100 records to disk at a time). Your wHeap program must not output anything to stdout.

b) Search on a heap file

Look at the file /scratch/DatabaseSystems/DATA/search 2012. This is a text file containing search key values; each entry is a particular ID (in the schema given above). You are to simulate searching over a heap file, with different assumptions for the size of file pages.

prepare a program to perform equality search operations on the heap file produced by your wHeap program in Section a. The executable name of this program must be sHeap and it must be able to be executed using the command:

> ./sHeap search_2012 heap pagesize

where search 2012 is the name of the file containing the keys to be searched for; heap is the output file of our wHeap program; and pagesize is an integer value that specifies the size of the disk page that you are simulating.

Your program should read in the file, one “page” at a time. For ex, if the pagesize parameter is 100, your program should read in the first 100 records from disk. These can then be scanned, in-memory, for a match. If a match is found, print the matching record to stdout.
You should assume that ID is a primary key. If no match is found, read in the next pagesize records of the file. The process should continue until either a matching record is found, or there are no more records in the file to process.

If a match is found, the program must print the matching record to stdout. If no match is found, a suitable message should be printed. In addition, the program must always output the total time taken to do all the search operations in milliseconds to stdout. For ex, if the time taken to do the reading is 123.45 ms, the output would be:

Time: 123.45 ms

c) Writing a sorted file

prepare a program to create a sorted file that stores the records currently in the file /scratch/ DatabaseSystems/DATA/data 2012 on yallara. You may modify your code from Section

Records should use the same fixed-length schema given previously, and should again be written in binary. When inserting the records into your new file, they should be sorted on an appropriate attribute. You will need to choose a sensible sorting algorithm, appropriate to the data that you are dealing with. You should implement this sorting algorithm yourself.

The executable name of this program must be wSort and it must be able to be executed using the command:

> ./wSort data_2012 sorted pagesize

where data 2012 is the input file; sorted is an output file to which your converted data is written; and pagesize is an integer specifying the size of a page of the file (that is, the number of records that can be stored per page).

Like wHeap, your wSort program must not output anything to stdout.

d) Search on a sorted file

prepare a program to simulate searching over a sorted file, with different assumptions for the size of file pages. prepare a program to perform equality search operations on the sorted file produced by your wSort program in Section c. The executable name of this program must be sSort and it must be able to be executed using the command:

> ./sSort search_2012 sorted pagesize

where search 2012 is the name of the file containing the ID keys to be searched for; sorted is the output file of our wSort program; and pagesize is an integer value that specifies the size of the disk page that you are simulating.

Your program must take advantage of the assumption that sorted is a file whose structure has been created by sorting on the ID key. Your program should read in required parts of the file, one “page” at a time. For ex, if the pagesize parameter is 100, your program should fetch 100 records in a single read from disk. These can then be scanned, in-memory, for a match.

If a match is found, the program must print the matching record to stdout. If no match is found, a suitable message should be printed. In addition, the program must output the total time taken to do all the search operations in milliseconds to stdout. For ex, if the time taken to do the reading is 123.45 ms, the output would be:

Time: 123.45 ms

Experiments and Analysis

In this section, you will be asked to carry out a number of experiments and to analyse your results. Create a file called report.txt. Use this file to record your answers to the following problems:

a) Searching with a heap file

• Put a heading “Equality search (heap file)” in your report.

• Run your sHeap program with pagesize settings of: 100; 1,000; 10,000. For each of these pagesize settings, run your program 10 times. Create a table in your report, and record the timing results, including the date and time of each run.

• find out the average and standard deviation of the running times for each pagesize, and record them in your report.

b)Searching with a sorted file

• Put a heading “Equality search (sorted file)” in your report.

• Run your sSort program with pagesize settings of: 100; 1,000; 10,000. For each of these pagesize settings, run your program 10 times. Record the timing results in a table in your report, including the date and time of each run.

• find out the average and standard deviation of the running times, for each pagesize, and record them in your report.

c) Comparison of approaches

• Put a heading “Comparison of approaches” in your report.

• With reference to your experimental results above, discuss the advantages and disadvantages of the heap and sorted file organisations. Do the trends change for different page sizes? Are the results what you would have expected to see based on your theoretical understanding of these file organisations? Why or why not? Limit your discussion to half a page.

d) Theory

• Answer the following problems.

1. Suppose that instead of equality searches, you were carrying out range searches. Would you expect your results to change? Which of the file organisations would you prefer? As part of your discussion, you should demonstrate your understanding of the properties of the file organisations. Limit your discussion to half a page.

2. Now, suppose that instead of equality searches, you were inserting new records into the file. Which of the file organisations would you prefer? As part of your discussion, you should demonstrate your understanding of the properties of the file organisations.

Programming Language, Programming

  • Category:- Programming Language
  • Reference No.:- M91943

Have any Question? 


Related Questions in Programming Language

Assignmentwrite a program to converts temperatures between

Assignment Write a program to converts temperatures between Fahrenheit and Celsius. Your program should print a brief message describing what it does, and then prompt the user to enter "1" if they would like to convert a ...

The program will store the realty listings data as a

The program will store the realty listings data as a dynamically allocated LINKED LIST, instead of an array of records. The program will allow the realtors to both maintain and use the listings data. 1. Again, begin the ...

Assignment introduction to computer sciencepart a this

Assignment: Introduction to Computer Science Part A: This question is to be submitted to the instructor in the form of a Word (or OpenOffice) document containing the Java code and appropriate screen capture(s) of the out ...

Write a program which1 asks the user to enter a positive

Write a program which: 1. Asks the user to enter a positive integer greater than or equal to 0 2. Validates that the entry is a positive integer 3. Outputs the digits in reverse order with a space separating the digits 4 ...

Develop a program that displays information about a family

Develop a program that displays information about a family member or friend. This program should print out information about what you like best about him or her. You might even describe your pet, if you have one. Present ...

Computer science assignmnetuse this Computer Science Assignmnet use this program

Computer Science Assignmnet use this program http://snap.berkeley.edu/snapsource/snap.html# The assignment is to create a block to simulate coin tosses in snap. The block should take in 2 parameters, the number of coin t ...

Project on grammarsnbspcourseist 230cmpsc

PROJECT ON GRAMMARS   Course: IST 230/CMPSC 360   Deadline: see the calendar in Canvas for the deadline   Objective: To acquire a comprehensive understanding of the application of grammars and formal language theory to c ...

Now consider the outer loop of given figure consisting of

Now consider the outer loop of given figure, consisting of blocks B2, B3, B4, and B5. Let g be the transfer function for the loop body, from the entry of the loop at B2 to its exit at B5. Let i measure the number of iter ...

Assignment1 you are a manager who is employed by a game

Assignment 1. You are a manager who is employed by a game production company. Your team is responsible for coding one of the game modules. You have two newly hired programmers working for you who believe that the followi ...

Assignmentin this assignment you will implement a

Assignment In this assignment, you will implement a simplified gradebook. Your application should: Ask for a student's name. Ask for how many letter grades will be inputted. After all of the valid letter grades are enter ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

Section onea in an atwood machine suppose two objects of

SECTION ONE (a) In an Atwood Machine, suppose two objects of unequal mass are hung vertically over a frictionless

Part 1you work in hr for a company that operates a factory

Part 1: You work in HR for a company that operates a factory manufacturing fiberglass. There are several hundred empl

Details on advanced accounting paperthis paper is intended

DETAILS ON ADVANCED ACCOUNTING PAPER This paper is intended for students to apply the theoretical knowledge around ac

Create a provider database and related reports and queries

Create a provider database and related reports and queries to capture contact information for potential PC component pro

Describe what you learned about the impact of economic

Describe what you learned about the impact of economic, social, and demographic trends affecting the US labor environmen