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 fixed-length record?

Answer 7

They are faster to process since the exact position of the record is known.

This is because all records are the same length, therefore you are able to jump to the desired record.

Question 8

What are Variable-Length records?

Answer 8

Where the length of each record varies according to the data it holds.

Question 9

What is an advantage of variable-length records?

Answer 9

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

Question 10

What is a serial file?

Answer 10

A serial file is where records are stored one after the other, in no particular order (records are added to the end of a file)

Can be used with either tape or disk storage

Question 11

What is the main use of a serial file?

Answer 11

A transaction file

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

Question 12

What is an advantage of a serial file?

Answer 12

Adding records is very straightforward and fast

Question 13

What are the disadvantages of a serial file?

Answer 13

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 14

What is a sequential file?

Answer 14

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 15

What is a sequential file often used as?

Answer 15

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

Question 16

What are the advantages of a sequential file?

Answer 16

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 17

What is the disadvantage of a sequential file?

Answer 17

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

Question 18

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

Answer 18

You open the file

Record is added to the end of the file

You close the file

Question 19

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

Answer 19

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 20

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

Answer 20

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 21

What is a block?

Answer 21

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 22

What does a disk contain?

Answer 22

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

Question 23

What does a block contain?

Answer 23

each disk block could hold several records

Question 24

What is an indexed sequential file?

Answer 24

An indexed sequential file is a sequential file so therefore has all advantages associated:

-able to update quickly when modifying large numbers of records in key field order.

However it also contains an index file:

-allows records to be directly searched for very quickly without having to read through all other records in the list.
(similar to a book which can be read through but has an index to skip to the desired page)

considered the ‘jack of all trades’, having the properties of a sequential file but also allowing very quick direct access via the index to go straight to the record. However it is not as fast as Random (Direct) Access files.

Indexed sequential files will not work on tape storage as there is no way to directly go to a record without reading through all the previous records.

The indexes are set up so that each block will only be partially filled with records so that there is room for new records to be added in future.

Question 25

What is overflow?

Answer 25

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

Question 26

How do we deal with overflow?

Answer 26

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 27

What are the problems associated with overflow?

Answer 27

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 28

How do we reorganise Indexed sequential files?

Answer 28

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 29

How do you delete records in an indexed sequential file?

Answer 29

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 30

What is a multi-level index?

Answer 30

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 31

What do Random (Direct) Access files do?

Answer 31

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 32

What is the most commonly used hashing algorithm?

Answer 32

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

Disk Address = (Key_Field MOD Maximum_No_Records) + 1

Question 33

What are the signs of a good hashing algorithm?

Answer 33

• Executes quickly

- Distributes keys equitably

Question 34

What is a collision?

Answer 34

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 35

Name the two ways you can handle collisions?

Answer 35

Linear Probing

Overflow (Flagging)

Question 36

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

Answer 36

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 37

What do you do in Overflow to handle a collision?

Answer 37

• 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