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

Questioncomplete tutorial 10 case problem 2 - ridgewood

Question: Complete Tutorial 10 Case Problem 2 - Ridgewood Herald Tribune found on pages 734-736 of your textbook. Complete the entire website assignment and upload your files to your 000WebHost account. After uploading t ...

You must do this assignment correctly as described

You must do this assignment correctly as described below.  If you do not follow the directions or break the rules you will receive a 0 score. Simulation of checking tic-tac-toe board for wins by counting X and O in rows, ...

Computerscienceprogram-writeallofthefollowingmainprogramcall

Computer Science Program- Write all of the following: main program: Call a function to open an input file. Call a function to read 3 integers in from the input file. Call a function that will find 3 normalized doubles, g ...

Pair programming phase 1talent agency user stories1 user

Pair Programming Phase 1 Talent Agency User Stories 1. User Story 1 As a head office administrator I want to be able to produce formatted output of all the information about our talent agencies so that I can easily incor ...

Add a swift class file to the project that illustrates and

Add a SWIFT class file to the project that illustrates and contains the following: • The class name is 'Calculator' • Has public variables of the type float called numerator, denominator and total. • Has a method called ...

Programming lab assignment set awhat to submitcomplete

Programming Lab Assignment (Set A) What to Submit Complete Problem Solving Steps 1 - 3 (check plan, data analysis, initial algorithm, and refinement algorithm) for the following programs. 1. (Name: lab1a-1.cpp) Write a p ...

Engineering programmingi need this now please accurate

Engineering programming I need this now please accurate answers and must be high rated Problem #1 Write a program that asks the user to input the number of miles and convert the miles to kilometers, and then print the ou ...

Cp1404cp5632 2016 sp22252 assignment 1 - shopping list

CP1404/CP5632 2016 SP2/22/52 Assignment 1 - Shopping List 1.0 Task: You are to plan and then code a console-based program in Python 3, as described in the following information and sample output. This assignment will hel ...

Csis program homeworkwrite a program where the user will

CSIS program homework Write a program where the user will enter a number between 1 and 50 representing a state. The program should display the full name of that state. Assume the states are in alphabetical order, that is ...

Electrical engineering computer methods assignmentq1 write

Electrical Engineering Computer Methods Assignment Q1. Write a program that given the following array, reverses all array elements and then prints them. int x[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; Q2. Write a program to d ...

  • 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

A cola-dispensing machine is set to dispense 9 ounces of

A cola-dispensing machine is set to dispense 9 ounces of cola per cup, with a standard deviation of 1.0 ounce. The manuf

What is marketingbullwhat is marketing think back to your

What is Marketing? • "What is marketing"? Think back to your impressions before you started this class versus how you

Question -your client david smith runs a small it

QUESTION - Your client, David Smith runs a small IT consulting business specialising in computer software and techno

Inspection of a random sample of 22 aircraft showed that 15

Inspection of a random sample of 22 aircraft showed that 15 needed repairs to fix a wiring problem that might compromise

Effective hrmquestionhow can an effective hrm system help

Effective HRM Question How can an effective HRM system help facilitate the achievement of an organization's strate