Question

Suppose that a disk unit has the following parameters: seek time \(s=20\) msec; rota tional delay \(r d=10 \mathrm{msec} ;\) block transfer time \(b t t=1 \mathrm{msec} ;\) block size \(B=2400\) bytes; interblock gap size \(G=600\) bytes. An EMPLOYEE file has the following fields: \(\mathrm{SSN}, 9\) bytes; LASTNAME, 20 bytes; fIRSTNAYE, 20 bytes; MIDOLE INIT\(, 1\) byte; BIRTHOATE, 10 bytes; ADDRESS, 35 bytes; PHONE, 12 bytes; SUPERVISORSSN, 9 bytes; DEPARTMENT, 4 bytes; JOBCODE, 4 bytes; deletion marker, 1 byte. The EMPLOYEE file has \(r=30,000\) records, fixed-length format, and unspanned blocking. Write appropriate formulas and cal. culate the following values for the above eMPLoyee file: a. The record size \(R\) (including the deletion marker), the blocking factor \(b f r,\) and the number of disk blocks \(b\) b. Calculate the wasted space in each disk block because of the unspanned orga nization. c. Calculate the transfer rate \(t r\) and the bulk transfer rate brr for this disk unit (see Appendix B for definitions of tr and btr). d. Calculate the average number of block accesses needed to search for an arbitrary record in the file, using linear search. e. Calculate in msec the average time needed to search for an arbitrary record in the file, using linear search, if the file blocks are stored on consecutive disk blocks and double buffering is used. f. Calculate in msec the average time needed to search for an arbitrary record in the file, using linear search, if the file blocks are not stored on consecutive disk blocks. g. Assume that the records are ordered via some key field. Calculate the average number of block accesses and the average time needed to search for an arbitrary record in the file, using binary search.

Short answer

The detailed calculations discussed indicate that the record size is \(R = 125\) bytes, the blocking factor is \(bfr = 19\), and the number of blocks needed is \(b = 1579\). There is a wasted space of \(525\) bytes due to unspanned organization. The disk has a transfer rate of \(2400\) bytes/msec and a bulk transfer rate of \(19\) records/msec. The average number of block accesses for a linear search is \(790\), and the average time for such a search is \(820\) msec with consecutive disk blocks and double buffering, and \(24310\) msec without. Considering a binary search, the average number of block accesses is \(11\), and the average time for such a search is \(341\) msec.

Step-by-step solution

Calculate Record Size, Blocking Factor, and Block Number

First, calculate the record size \(R\) by adding the size of each field in the EMPLOYEE file, including the deletion marker. This gives \(R = 9 + 20 + 20 + 1 + 10 + 35 + 12 + 9 + 4 + 4 + 1 = 125\) bytes. Next, calculate the blocking factor, which is the number of records per block. This equals the block size divided by the record size, or \(B/R\). Using the given values, \(B/R = (2400 bytes) / (125 bytes/record) = 19\) records/block. The number of blocks needed equals the number of records divided by the blocking factor, or \(r/bfr\). This gives \(r/bfr = 30000/19 = 1579\) blocks, rounded up to the nearest whole number.

Calculate Wasted Space

The wasted space in each disk block due to unspanned organization equals the block size minus the size of the number of records that can fit in a block. This value is \(B - (R × bfr) = 2400 – (19 × 125) = 525\) bytes.

Calculate Transfer Rate and Bulk Transfer Rate

The transfer rate \(tr\) equals the block size divided by the block transfer time, or \(B/btt = 2400/1 = 2400\) bytes/msec. The bulk transfer rate \(btr\) is calculated as \(bfr\) records per block divided by the block transfer time, or \(bfr/btt = 19/1 = 19\) records/msec.

Calculate Average Block Accesses for Linear Search

The average number of block accesses needed in a linear search equals half the total number of blocks, or \(b/2 = 1579/2 = 790\) accesses.

Calculate Average Time for Linear Search with Consecutive Disk Blocks and Double Buffering

The average time for a linear search involves the seek time \(s\), rotational delay \(rd\) and the transfer time for half the blocks. This equals \(s + rd + ((b/2) × btt) = 20 + 10 + (790 × 1) = 820\) msec.

Calculate Average Time for Linear Search with Non-Consecutive Disk Blocks

The average time for a linear search with non-consecutive disk blocks includes the seek time, rotational delay, and the transfer time for half the blocks, for each block. This equals \((b/2) × (s + rd + btt) = 790 × (20 + 10 + 1) = 24310\) msec.

Calculate Average Block Accesses and Time for Binary Search

For a binary search, the average number of block accesses equals \(log2(b)\), or \(log2(1579) = 11\) accesses, rounded up. The average time for a binary search involves the seek time, rotational delay, and the block transfer time for each access. This equals \(log2(b) × (s + rd + btt) = 11 × (20 + 10 + 1) = 341\) msec.

Key concepts

Disk Block Calculation

Understanding how data is stored on disk is crucial for database management. To store records efficiently, it's necessary to know the disk block size and how many records each block can hold.

In the given exercise, we calculated the record size (R) by summing up the sizes of all the fields in an EMPLOYEE record, and we got R = 125 bytes. The blocking factor (bfr) indicates how many of these records can fit into a single disk block. With a block size (B) of 2400 bytes, we determined the blocking factor to be 19 records per block. It is important because it directly influences the number of disk blocks (b) needed to store the entire EMPLOYEE file. With 30,000 records to store, and 19 records per block, we need approximately 1579 blocks.

When determining the requirements for storage, we look to minimize the number of disk blocks as it can optimize the storage space and potentially reduce the time to access data. It can be particularly beneficial in systems where disk IO (input/output) operations are a bottleneck.

Unspanned Organization

In databases, unspanned organization refers to the method of storing records in disk blocks in such a way that a single record does not span across multiple blocks. That is, each record is completely contained within one block.

This approach simplifies record management, but can lead to wasted space. For instance, if a block can hold 19 records and each record is 125 bytes, but the total block size is 2400 bytes, there will be 525 bytes of unused space per block since the size of 19 records is 2375 bytes and we can't fit another whole record in the remaining space.

This wasted space is a trade-off for the simplicity of an unspanned organization. When evaluating storage solutions, it is crucial to balance the necessity for efficient space usage with the ease of implementation and potential performance implications. Typically, database systems need to strike this balance based on the specific use case and performance requirements.

Linear and Binary Search Access Time

When searching for a specific record in a database, the efficiency of the search method significantly impacts access time. Linear search goes through each block sequentially and is quite straightforward, but it can be time-consuming for large datasets.

The solution presented in the exercise indicates that the average number of block accesses needed for a linear search is half the number of blocks, which in our case is approximately 790 accesses. If the blocks are stored on consecutive disk blocks, the average search time improves significantly, especially when using optimizations like double buffering. However, if blocks are scattered, the average time per access increases due to additional seek and rotational delays encountered with each new block accessed.

Binary search, on the other hand, is much more efficient for ordered data since it repeatedly divides the search interval in half. It requires about log2(b) accesses, which comes to about 11 for our dataset. Binary search significantly reduces the average search time because less block accesses are needed, but it is only applicable when records are ordered by some key field. Both methods show a trade-off between organization and performance that database designers and users must understand for effective utilization.