Data Storage

Question 1

Describe features of primary storage

Answer 1

<ul>
<li>Fast</li>
<li>Expensive</li>
<li>Volatile</li>
</ul>

Question 2

What does primary storage hold?

Answer 2

Data that needs to be operated on

Question 3

Describe features of secondary storage

Answer 3

<ul>
<li>Moderately fast</li>
<li>Cheaper</li>
<li>Non-volatile</li>
</ul>

Question 4

What does secondary storage hold?

Answer 4

Data that is not currently being operated on

Question 5

Describe features of tertiary storage

Answer 5

<ul>
<li>Slow</li>
<li>Cheap</li>
<li>Non-volatile</li>
<li>Durable</li>
</ul>

Question 6

What does tertiary storage hold?

Answer 6

Archival data, long term back ups

Question 7

What is a block?

Answer 7

Unit of storage allocation and of data transfer between secondary and primary storage
Continguous sequence of sectors from a single track

Question 8

What is a typical block size today?

Answer 8

Between 4 and 8 kilobytes

Question 9

What is the formula for a cost of a block access?

Answer 9

access time + (block size/data transfer rate)

Question 10

What are the assumptions for a fixed length record?

Answer 10

<ul>
<li>Record size is fixed</li>
<li>Each file has records of one particular type only</li>
<li>Different files are used for different relations</li>
<li>Each record is entirely contained in a single block</li>
<li>No record is larger than a block</li>
</ul>

Question 11

Describe the simple approach to storing fixed length records

Answer 11

Attributes are stored in order, store record i starting from byte n x i where n is the size of each record

Question 12

What are the problems with the simple approach for storing fixed length records?

Answer 12

<ul>
<li>Need maximum allocation per field, wasteful</li>
<li>Block size unlikely to be multiple of record size</li>
</ul>

Question 13

What are the three ways deletion can be dealt with in fixed length record storage?

Answer 13

<ol>
<li>Compact records by shifting them left</li>
<li>Move record n into the gap</li>
<li>Fill the gap on the next insertion</li>
</ol>

Question 14

What are free lists?

Answer 14

A way to arrange the data structure to hold where the deleted records are

Question 15

How do free lists work?

Answer 15

Store the address of the first deleted record in the file header, then the first deleted record stores the address of the second deleted record and so on

Question 16

How does insertion work with a free list data structure?

Answer 16

Use the pointer from the header, then change the header to point to the next one

Question 17

Describe a variable length record

Answer 17

The length of the record varies depending on how much data must be stored

Question 18

What can variable length records be used to store?

Answer 18

<ul>
<li>Multiple record types in a file</li>
<li>Record types that allow for variable lengths</li>
<li>Record types that allow for repeating fields</li>
</ul>

Question 19

What is the main problem to think about when looking at storage of variable length records?

Answer 19

How do we make sure we can quickly look at the right part of the file to find the information that we want

Question 20

How is a single variable length record storage?

Answer 20

Attributes are stored in order, variable length attribute allocated enough bytes to store an offset and a length. Actual data is stored after all fixed length attributes at specificed attributes

Question 21

What does the slotted page header contain when storing variable length records?

Answer 21

<ul>
<li>Number of record entries</li>
<li>End of free space in the block</li>
<li>Location and size of each record</li>
</ul>

Question 22

What happens when a new record is added to a block storing variable length records?

Answer 22

<ol>
<li>Insert the record at the end of free space</li>
<li>Update the header, add one to list of entries, take away from end of free space and insert location and size into block header</li>
</ol>

Question 23

What are the three main ways you can organise storing records?

Answer 23

<ol>
<li>Sequential</li>
<li>Heap</li>
<li>Hashing</li>
</ol>

Question 24

Describe sequential record organisation

Answer 24

Store records in sequential order, based on the value of the search key of each record

Question 25

Describe heap record organisation

Answer 25

A record can be placed anywhere in the file where there is space

Question 26

Describe hashing record organisation

Answer 26

A hash function is computed on some attribute of each record and the result is used to tell where file is placed

Question 27

What kind of files would require sequential record organisation?

Answer 27

Applications that require sequential processing of the entire file

Question 28

How does insertion work in sequential file organisation?

Answer 28

Locate the position where the record is to be inserted, if there is free space, insert there. if no free space, insert the record in an overflow block

Question 29

Why do we need to sometimes reorganise sequential files?

Answer 29

To minimise hops around blocks and to restore sequential order, with respect to the overflow block

Question 30

What is the vision of heap files?

Answer 30

Just insert record wherever there is space according to the free list

Question 31

Describe the compromised version of heap files

Answer 31

<ol><li>Insert records in the correct block (according to search key order)</li><li>Within that block, insert the record wherever there is space according to the header's free list</li><li>Within block, chain inserted records together to indicate search key order </li></ol>

Question 32

Describe multi-table clustering and where it might be useful

Answer 32

Store several relations in one file with pointer chains to link records of a particular relation

Good for queries involving both relations, but bad for single relation queries

Question 33

What are some examples of metadata that the data dictionary stores

Answer 33

<ul>
<li>Information about relations (schema)</li>
<li>User data</li>
<li>Statistical and descriptive data for each block/relation</li>
<li>Physical file organisation information</li>
<li>Information about indices</li>
</ul>

Question 34

What is another name for the data dictionary

Answer 34

System catalog

Question 35

What is the buffer?

Answer 35

A portion of main memory availabile to store copies of disk blocks

Question 36

What is the buffer manager?

Answer 36

Subsystem responsible for allocating buffer space in main memory

Question 37

What happens when a program calls on the buffer manager for a certain block and it isn’t in the buffer?

Answer 37

<ol>
<li>Allocates space in the buffer for the block</li>
<li>Reads the block from the disk to the buffer</li>
<li>Returns the address of the block in main memory to requester</li>
</ol>

Question 38

How do most operating systems choose with block to place back into memory if the buffer is full?

Answer 38

Least Recently Used (LRU) strategy

Question 39

What is the main idea behind LRU stategy?

Answer 39

Use past pattern of block references as a predictor of future refereces

Question 40

When can LRU be a bad strategy?

Answer 40

When database is accessing repeated scans of data (i.e. when computing the join of two relations)

Question 41

State some alternative buffer replacement strategies?

Answer 41

<ul>
<li>Toss immediate strategy</li>
<li>Most recently used strategy</li>
</ul>

Question 42

Describe the toss immediate strategy

Answer 42

Frees the space occupied by a block as soon as the final tuple of that block has been processed

Question 43

Describe the most recently used strategy

Answer 43

After the final block of the just processed tuple is finished, block is unpinned and it is discarded

Question 44

What is the length of a null bitmap?

Answer 44

1 byte