For the following system configuration, please compute the solutions to each (a

Question

For the following system configuration, please compute the solutions to each (a – g) along with their sub-parts.

Consider a disk with block size B=512 bytes. A block pointer is P=6 bytes long, and a record pointer is PR =6 bytes long. A file has r=50,000 EMPLOYEE records of fixed-length. Each record has the following fields: NAME (50 bytes), SSN (10 bytes), DEPARTMENTCODE (9 bytes), ADDRESS (40 bytes), PHONE (10 bytes) BIRTHDATE (8 bytes), SEX (1 byte), JOBCODE (4 bytes), INFO (1 bytes),SALARY (2 bytes).

(a) Calculate the record size R in bytes.
(b) Calculate the blocking factor bfr and the number of file blocks b assuming an unspanned organization.

(c) Suppose the file is ordered by the key field SSN and we want to construct a primary index on SSN. Calculate (i) the index blocking factor bfr i (which is also the index fan-out fo); (ii) the number of first-level index entries and the number of first-level index blocks; (iii) the number of levels needed if we make it into a multi-level index; (iv) the total number of blocks required by the multi-level index; and (v) the number of block accesses needed to search for and retrieve a record from the file--given its SSN value--using the primary index.

(d) Suppose the file is not ordered by the key field SSN and we want to construct a secondary index on SSN. Repeat the previous exercise (part c) for the secondary index and compare with the primary index.

(e) Suppose the file is not ordered by the non-key field DEPARTMENTCODE and we want to construct a secondary index on DEPAERTMENT_CODE using Option 3 of Section 17.1.3 and Fig 17.5 (see text), with an extra level of indirection that stores record pointers. Assume there are 1000 distinct values of DEPARTMENTCODE, and that the EMPLOYEE records are evenly distributed among these values. Calculate (i) the index blocking factor bfr i (which is also the index fan- out fo); (ii) the number of blocks needed by the level of indirection that stores record pointers; (iii) the number of first-level index entries and the number of first-level index blocks; (iv) the number of levels needed if we make it a multi-level index; (v) the total number of blocks required by the multi-level index and the blocks used in the extra level of indirection; and (vi) the approximate number of block accesses needed to search for and retrieve all records in the file having a specific DEPARTMENTCODE value using the index.

(f) Suppose the file is ordered by the non-key field DEPARTMENTCODE and we want to construct a clustering index on DEPARTMENTCODE that uses block anchors (every new value of DEPARTMENTCODE starts at the beginning of a new block). Assume there are 1000 distinct values of DEPARTMENTCODE, and that the EMPLOYEE records are evenly distributed among these values. Calculate (i) the index blocking factor bfr i (which is also the index fan-out fo); (ii) the number of first-level index entries and the number of first-level index blocks; (iii) the number of levels needed if we make it a multi-level index; (iv) the total number of blocks required by the multi-level index; and (v) the number of block accesses needed to search for and retrieve all records in the file having a specific DEPARTMENTCODE value using the clustering index (assume that multiple blocks in a cluster are either contiguous or linked by pointers).

(g) Suppose the file is not ordered by the key field Ssn and we want to construct a B + Tree access structure (index) on SSN. Calculate (i) the orders p and p leaf of the B + tree; (ii) the number of leaf level blocks needed if blocks are approximately 69% full (rounded up for convenience); (iii) the number of levels needed if internal nodes are also 69% full (rounded up for convenience); (iv) the total number of blocks required by the B + -tree; and (v) the number of block accesses needed to search for and retrieve a record from the file--given its SSN value using the B + -tree.

Explanation / Answer

Consider a disk with block size B=512 bytes. A block pointer is P=6 bytes long,
and a record pointer is PR =6 bytes long. A file has r=50,000 EMPLOYEE records
of fixed-length. Each record has the following fields: NAME (50 bytes), SSN (10
bytes), DEPARTMENTCODE (9 bytes), ADDRESS (40 bytes), PHONE (10 bytes),
BIRTHDATE (8 bytes), SEX (1 byte), JOBCODE (4 bytes), INFO (1 bytes),SALARY (2 bytes). -chegg

Consider a disk with block size B=512 bytes. A block pointer is P=6 bytes long,
and a record pointer is P R =7 bytes long. A file has r=30,000 EMPLOYEE records
of fixed-length. Each record has the following fields: NAME (30 bytes), SSN (9
bytes), DEPARTMENTCODE (9 bytes), ADDRESS (40 bytes), PHONE (9 bytes),
BIRTHDATE (8 bytes), SEX (1 byte), JOBCODE (4 bytes), SALARY (4 bytes, real
number). An additional byte is used as a deletion marker.

(a) Record length R = (50 + 10 + 9 + 40 + 10 + 8 + 1 + 4 + 1 + 2) + 1 = 136 bytes

(b) Blocking factor bfr = floor(B/R) = floor(512/136) = 3 records per block
Number of blocks needed for file = ceiling(r/bfr) = ceiling(50000/3) = 16666

(c) (i). Index record size R i = (V SSN + P) = (10 + 6) = 16 bytes
Index blocking factor bfr i = fo = floor(B/R i ) = floor(512/16) = 32

(c) (ii). Number of first-level index entries r 1 = number of file blocks b = 16666 entries
Number of first-level index blocks b 1 = ceiling(r 1 /bfr i ) = ceiling(16666/32)
= 521 blocks

(c) (iii). We can calculate the number of levels as follows:
Number of second-level index entries r 2 = number of first-level blocks b 1
= 521 entries
Number of second-level index blocks b 2 = ceiling(r 2 /bfr i ) = ceiling(521/32)
= 17 blocks
Number of third-level index entries r 3 = number of second-level index blocks b 2
= 17 entries
Number of third-level index blocks b 3 = ceiling(r 3 /bfr i ) = ceiling(17/16) =
= 1 entries
Since the third level has only 1 block, it is the top index level.
Hence, the index has x = 3 levels

(c)(iv). Total number of blocks for the index b i = b 1 + b 2 + b 3 = 521 + 17 + 1
= 539 blocks

(c)(v) Number of block accesses to search for a record = x + 1 = 3 + 1 = 4

(d) (i). Index record size R i = (V SSN + P) = (10 + 6) = 16 bytes
Index blocking factor bfr i = (fan-out) fo = floor(B/R i ) = floor(16666/16)
= 32 index records per block
(This has not changed from part (c) above)
(Alternative solution: The previous solution assumes that leaf-level index blocks contain
block pointers; it is also possible to assume that they contain record pointers, in
which case the index record size would be V SSN + P R = 10 + 6 = 16 bytes. In this
case, the calculations for leaf nodes in (i) below would then have to use R i = 16
bytes rather than R i = 15 bytes, so we get:
Index record size R i = (V SSN + P R ) = (10 + 6) = 15 bytes
Leaf-level ndex blocking factor bfr i = floor(B/R i ) = floor(512/16)
= 32 index records per block
However, for internal nodes, block pointers are always used so the fan-out for
internal nodes fo would still be 34.)

d(ii). Number of first-level index entries r 1 = number of file records r = 50000
Number of first-level index blocks b 1 = ceiling(r 1 /bfr i ) = ceiling(16666/32)
= 521 blocks
(Alternative solution:
Number of first-level index entries r 1 = number of file records r = 50000
Number of first-level index blocks b 1 = ceiling(r 1 /bfr i ) = ceiling(50000/32)
= 521 blocks)

(d)
iv. Total number of blocks for the index b i = b 1 + b 2 + b 3 = 521 + 17 + 1 = 539
(Alternative solution:
Total number of blocks for the index b i = b 1 + b 2 + b 3 = 521 + 17 + 1 = 539)
v. Number of block accesses to search for a record = x + 1 = 3 + 1 = 4

(e) i. Index record size R i = (V DEPARTMENTCODE + P) = (9 + 6) = 15 bytes
Index blocking factor bfr i = (fan-out) fo = floor(B/R i ) = floor(512/15)
= 34 index records per block
ii. There are 1000 distinct values of DEPARTMENTCODE, so the average number of
records for each value is (r/1000) = (50000/1000) = 50
Since a record pointer size P R = 6 bytes, the number of bytes needed at the level
of indirection for each value of DEPARTMENTCODE is 6 * 50 =300 bytes, which
fits in one block. Hence, 1000 blocks are needed for the level of indirection.
iii. Number of first-level index entries r 1
= number of distinct values of DEPARTMENTCODE = 1000 entries
Number of first-level index blocks b 1 = ceiling(r 1 /bfr i ) = ceiling(1000/32)
= 32 blocks
iv. We can calculate the number of levels as follows:
Number of second-level index entries r 2 = number of first-level index blocks b 1
= 32 entries
Number of second-level index blocks b 2 = ceiling(r 2 /bfr i ) = ceiling(32/32) = 1
Hence, the index has x = 2 levels
v. total number of blocks for the index b i = b 1 + b 2 + b indirection
= 32 + 1 + 1000 = 1033 blocks
vi. Number of block accesses to search for and retrieve the block containing the
record pointers at the level of indirection = x + 1 = 2 + 1 = 3 block accesses
If we assume that the 32 records are distributed over 32 distinct blocks, we need
an additional 32 block accesses to retrieve all 32 records. Hence, total block
accesses needed on average to retrieve all the records with a given value for
DEPARTMENTCODE = x + 1 + 32 = 35

(f) i. Index record size R i = (V DEPARTMENTCODE + P) = (9 + 6) = 15 bytes
Index blocking factor bfr i = (fan-out) fo = floor(B/R i ) = floor(512/15)
= 34 index records per block
ii. Number of first-level index entries r 1
= number of distinct DEPARTMENTCODE values= 1000 entries
Number of first-level index blocks b 1 = ceiling(r 1 /bfr i )
= ceiling(1000/32) = 32 blocks
iii. We can calculate the number of levels as follows:
Number of second-level index entries r 2 = number of first-level index blocks b 1
= 32 entries
Number of second-level index blocks b 2 = ceiling(r 2 /bfr i ) = ceiling(32/32) = 1
Since the second level has one block, it is the top index level.
Hence, the index has x = 2 levels
iv. Total number of blocks for the index b i = b 1 + b 2 = 32 + 1 = 33 blocks
v. Number of block accesses to search for the first block in the cluster of blocks
= x + 1 = 2 + 1 = 3
The 32 records are clustered in ceiling(32/bfr) = ceiling(32/4) = 8 blocks.
Hence, total block accesses needed on average to retrieve all the records with a given
DEPARTMENTCODE = x + 8 = 2 + 8 = 10 block accesses

(g): This is a big question to answer. Time is insufficient to answer remaining question. So please understand.
I will answer to this part again. please email me at "manohar.siripurapu" this is google account.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.