Organisation And Structure Of Data

Question 1

What does the MOD function do?

Answer 1

the MOD function returns the remainder

e.g. 10 MOD 3 = 1 (3+3=9, remainder 1)

Question 2

What does the DIV function do?

Answer 2

the DIV function returns the amount of times one number goes into another

e.g. 10 DIV 3 = 3

Question 3

What is a transaction file and what does it do?

Answer 3

A transaction file is a temporary file.

It collects data over a short period of time (e.g. a month).

At the end of the timescale, the data from the transaction file is copied to the master file, often using batch processing.

Question 4

What is a master file?

Answer 4

at the end of a transaction files timescale, the data from it is copied over to the master file (batch processing)

Master files will store all of the data required to perform batch processing operations such as generating bills etc.

Question 5

What happens to both a master and transaction file before performing the update?

Answer 5

The transaction file will be sorted in the same primary key order as the master file

This is to speed up the update as both files only have to be read through once to perform the update

Question 6

What are fixed length records?

Answer 6

Where all records are exactly the same length

When using fixed-length records, you need to make the record length equal to the length of the longest possible record.

Question 7

What is an advantage of a variable-length record?

Answer 7

Using variable-length records usually enables you to save disk space.

Question 8

What is a serial file?

Answer 8

A transaction file

e.g. recording sales in a shop “clocking in”

Question 9

What are the disadvantages of a serial file?

Answer 9

Very slow to search

This is because as the records are stored one after the other in no order there is no choice there is no other option other than to search one-by-one to find an item. This is a serial search.

Question 10

What is an advantage of a serial file?

Answer 10

Adding records is very straightforward and fast

Question 11

What is a sequential file?

Answer 11

A sequential file had records stored one after the other in order of a key field (e.g. employee ID)

can be used with either tape of disk storage

Question 12

What is a sequential file often used as?

Answer 12

A sequential file is often used as a master file to allow records to be searched via key field.

Question 13

What are the advantages of a sequential file?

Answer 13

If performing a batch update, it can be quicker to perform the update if the master file and also the file being updated from are in sequential order.

When searching for a record that doesn’t exist, it will be quicker to spot that it isn’t there.

Easier to program than methods such as indexed sequential.

Question 14

What is the disadvantage of a sequential file?

Answer 14

Can be slow to add records as they need to be added in the correct place

Question 15

What is the process of adding a record to a serial file?

Answer 15

You open the file

Record is added to the end of the file

You close the file

Question 16

What is the process of adding records to a sequential file?

Answer 16

1. First, a new file is created
2. Each record is copied from the old file to the new file until a record with primary key greater than the new record being added is found;
3. The new record is being added to the file;
4. All the remaining records are copied over to the new file.

(lesson 2 slide 8 for diagram)

Question 17

What is the process of deleting a record from a serial or sequential file?

Answer 17

1. A new file is created
2. Every record is copied from the old file to the new file apart from the record(s) to be deleted

(lesson 2 slide 9 for diagram)

Question 18

What is a block?

Answer 18

A block is where a track and a sector intersect.

A computer reads and writes blocks of data at a time, it is the smallest unit of transfer.

Question 19

What does a disk contain?

Answer 19

thousands of concentric circles called tracks and a number of sectors.

Question 20

What does a block contain?

Answer 20

each disk block could hold several records

Question 21

What is an indexed sequential file?

Answer 21

Records are stored in key field order in the file

The index allows the data to be accessed directly

Question 22

What is overflow?

Answer 22

If there is not enough space in the block where the record should be written, then this is known as an ‘overflow’.

Question 23

How do we deal with overflow?

Answer 23

There are a number of blocks set aside in an indexed sequential file known as the “overflow area”.

When an overflow occurs:

• the record is written into the overflow area
• a pointer is left in the block where it was supposed to be stored
• to indicate in which block in the overflow area it can be found

Question 24

What are the problems associated with overflow?

Answer 24

The more records added to the overflow, the time taken to search for records increases

This is because:

1. The index is searched which indicates the block where the record should be
2. The block is located (requiring disk read/write heads to move)
3. If there is a tag/pointer, it now needs to find the lock in the overflow area. Adding an extra step.

Question 25

How do we reorganise Indexed sequential files?

Answer 25

As records are also deleted from files, there may now be room for some of the overflowed records in their home blocks. Therefore we can:

periodically (nightly, weekly etc.) a file reorganisation program is run. This reads each record sequentially through the file, writing it back into its correct home location.

Question 26

How do you delete records in an indexed sequential file?

Answer 26

1. A record to be deleted is searched for using the index and then marked as deleted (to speed up the process)
2. New records added will be able to overwrite the deleted records

A special character (“e.g. $”) denotes that the record can be overwritten.

Question 27

What is a multi-level index?

Answer 27

In a multi-level index there is one main index.

The entries in this index refer to more indexes. These in turn refer to more indexes and so on.

(example of 3 level index on slide 13 and 14 lesson 3)

Question 28

What do Random (Direct) Access files do?

Answer 28

When a file is searched using a key field, using a random access file provides the fastest method.

It uses a hashing algorithm to generate a disk address from the key field of the record being searched for.

e.g. John Smith hashed generates disk address 873

Question 29

What is the most commonly used hashing algorithm?

Answer 29

The most commonly used hashing algorithm is known as the division/remainder method.

Disk Address = (Key_Field MOD Maximum_No_Records) + 1

Question 30

What are the signs of a good hashing algorithm?

Answer 30

• Executes quickly

- Distributes keys equitably

Question 31

What is a collision?

Answer 31

A collision is when two keys have the same hash value. So when the element to be inserted hashes out to be stored in an array position, it is already occupied.

Question 32

Name the two ways you can handle collisions?

Answer 32

Linear Probing

Overflow (Flagging)

Question 33

What do you do in Linear Probing to handle a collision?

Answer 33

You search sequentially for an unoccupied position
-uses a wraparound (circular) array

1. Apply Hashing Algorithm
2. Examine the result
3. Check to see if the index is free
4. If free, store the value
5. If not free, move sequentially to the next free slot

Question 34

What do you do in Overflow to handle a collision?

Answer 34

• a tag/pointer should be left in the block to indicate an overflow has occurred
• the record is added to the overflow area

1. Apply Hashing Algorithm
2. Examine the Result
3. Check to see if the index is free
4. If free, store the value
5. If not free, add flag pointing to the overflow
6. Add the record to the next free slot in the overflow

Question 35

What is an advantage of indexed sequential files over standard sequential files

Answer 35

Allows faster access because it can move directly to individual records

Question 36

Draw a three level index

Answer 36

3 tables

Main index, index 02, and index 03, then actual data