Number of records fit into a disk block and number of disk blocks required in DBMS

Find the number of disk blocks to store certain number of records, find the number of records that fit into one block in DBMS,  blocking factor, number of records without spanning, number of records with spanning

Exercise:

Suppose we have blocks of size 2048 bytes that we use to store fixed-length records. Each block has a 32 byte header used to store information including the number of records in the block.

(a) Suppose we have records consisting of a 20 byte header, and 3 columns of size 15 bytes, 6 bytes and 12 bytes respectively. Within each record, fields can start at any byte. How many records can fit in a block?

(b) Suppose that we have records each with a 20 byte header and 500 bytes of data. How many blocks will we need to store 4 records if no spanning is allowed?

 

Solution:

As each block has a 32 byte header, the available space for storing records is,

Available space = Block size – Header size = 2048 – 32 = 2016 bytes

(a) The space required to store each record (fixed length) is the sum of the record’s header and the column sizes.

Record size = Header size + column size = 20 + 15 + 6 + 12 = 53 bytes.

The number of records that can fit in each block is,

Blocking factor = Block size / record size = 2016 / 53 = 38 records

 

Blocking factor is a measure to count the number of records that can fit into a disk block. The block size is divided by the record size in case of fixed length records, to calculate the blocking factor. The average of record size may be used if the records are variable length.

 

(b) If no spanning is allowed, we cannot store partial records into disk blocks. We can only store full length record in any disk block. If a record doesn’t fit entirely into the remaining space of a disk block, we need to move that record into the next block.

Available block space = 2016 bytes

Record size = 20 + 500 = 520 bytes per record.

We like to store 4 such records, hence 520 * 4 = 2080 bytes.

As spanning is not permitted, only 3 records of 520 byte each can fit into a single block. The fourth record has to be stored in the next block. Hence, we need 2 blocks to store 4 records.

 

********************

Related posts:

• Go to Multiple Choice Questions in DBMS home

• Go to Normalization - MCQs page

• Go to General Mixed Quiz in all topics of DBMS page

• Go to Advanced DBMS Concepts page

Query processing and optimization exercise in DBMS

DBMS solved exercises, database query processing and optimization solved exercises, how to find the query IO cost for natural join

Question:

Consider doing a natural join operation on two relations R(A, B) and S(B, C). Assume that the tuples of R are stored contiguously on 400 disk blocks,  while the tuples of S are stored contiguously on 1000 blocks. Each block holds 20 tuples (same for R as for S). There are 51 memory blocks available.

Calculate the I/O cost for iteration join (assume that R and S are not sorted), and sort-merge join (assume that R and S are sorted on attribute B) algorithms. Ignore the I/O cost of writing the final output to disk.

 

Solution:

Given,

Total disk blocks for R, B(R) = 400

Total disk block for S, B(S) = 1000

Iteration join:

We have only 51 blocks are available in main memory. The iteration join algorithm can read 50 R blocks into memory, and all blocks of S (1 block at a time) into memory at a time, to join S with R. The process is repeated until all outputs are generated.

Number of IOs to read R into memory = 400, (ie., 50 * 8)

Number of IOs to read S into memory = for each of 50 R blocks we need 1000 IOs to read S

Total number of IOs required = 400 + 1000 * 8 = 8400

Merge join:

Given,

          Both R and S are sorted on the join attribute B.

Merge join: Both sorted files are scanned concurrently in order of the join attributes, matching the records that have the same values for A and B.

Cost of merging R and S = B(R) + B(S) = 400 + 1000 = 1400

 

**************

Go to Normalization - Solved Exercises page

Go to Advanced DBMS Concepts page

Go to Solved exercises in DBMS page

Go to Multiple Choice Questions (MCQ) in DBMS home

 

How many disk block accesses required to search for a record 01

MCQ in database management systems, quiz questions with answers in data storage and access.

How many disk block accesses required to search for a record in a sorted file?

Suppose we have a database file of 10,000 records, each record is of size 100 bytes. If the disk blocks are 512 bytes long, block addresses are 4 bytes long (i.e., to specify address to a block requires 4 bytes), pointers to records are 4 bytes long (i.e., a pointer which specifies address of the record in the block needs 5 bytes), and the records are sorted in search key order, what would be the number of disk accesses to do a successful lookup for a record?

a) 11

b) 5

c) 100

d) 256

Answer: (a) 11 Given,             Number of records = 10000             Record size = 100 bytes             Disk block size = 512 bytes; Therefore number of records per block (blocking factor) is 512/100 = 5.  Since 5 records per block, then we have file size N=  10,000/5 = 2,000 disk blocks. Searching in a sorted file The file has 2000 blocks and binary search will take log2N = log22000 = 11 disk block accesses.

 

************************

Related posts:

• Go to Multiple Choice Questions in DBMS home

• Go to Normalization - MCQs page

• Go to General Mixed Quiz in all topics of DBMS page

• Go to Advanced DBMS Concepts page

Quiz questions with answers on DBMS introduction concepts

Solved quiz questions on disk and storage access in DBM

How to measure the number of disk accesses required in DBMS

How to search for a record in a sorted database file

Schedules that are conflict serializable - solved examples

Given schedule is conflict serializable or not exercise, Conflict serializability exercise, how to find whether a schedule is conflict serializable? conflict serializability example

 

Conflict Serializable Schedule - Solved Exercise

Question:

Consider the following schedule;

Schedule S: r1(X), r2(X), r3(X), r1(Y), w2(Z), r3(Y), w3(Z), w3(Y)

Here, r1(X) denotes that transaction 1 read data item X, w2(z) denotes that transaction 2 writes data item Z, and so on. Is the given schedule a conflict serializable schedule? If yes, what is the equivalent serial schedule?

 

Solution:

Conflict serializable schedule: A schedule is conflict serializable if it can be transformed into an equivalent serial schedule by swapping pairs of non-conflicting instructions. Two instructions conflict if they involve the same data item and at least one of them is a WRITE.

 

To find whether the given schedule is conflict serializable or not, we can draw precedence graph. Precedence graph can be constructed by carefully analyzing the conflicting instructions. For every conflicting instruction, an edge can be inserted into the precedence graph. At the end, if the graph has not formed a cycle, then we would say that the schedule S is conflict serializable, otherwise not.

 

Is the schedule a conflict serializable schedule?

YES. The precedence graph of this S does no consist of a cycle.

The precedence graph includes an edge from T2 to T3 due to the conflict between the instructions w2(Z) and w3(Z). There will be another edge from T1 to T3 due to the conflict between instructions r1(Y) and w3(Y).

The precedence graph for S is as follows;

 

What is the equivalent serial schedule?

Equivalent serial schedule to S is (T2, T1, T3). Another equivalent schedule is (T1, T2, T3)

 

*****************************

 

Go to Define Serializability page

Go to Conflict Serializability explained with example page

Go to Solved exercises in DBMS page

Conflict serializability solved exercise

conflict serializable schedule example

how to find whether a schedule is conflict serializable or not?

how to check a schedule is serializable or not?

use precedence graph for checking serializability

serializability solved exercise

concurrency and serializability