Showing posts with label Disk Storage Access Exercises. Show all posts
Showing posts with label Disk Storage Access Exercises. Show all posts

Friday, October 29, 2021

Relational database management systems mcq quiz with answers 22

MCQ on various aspects in DBMS including cost for reading disk block pages, count the number of disk pages required to store a table, inner join, functional dependency, RDBMS Multiple Choice Questions with Answers

Database management systems - MCQ exam questions

1. Let us consider blocks of size 4KB to store variable-length records. Each block has a fixed 32 byte header used to store information including the number of records in the block. In addition to this fixed header, the header contains variable number of 2 byte pointers to each record in the block. Records can start at any byte offset and are packed as densely as possible. What would be the free space available in a single block after storing 10 records of size 400 bytes each?

a) 40 bytes

b) 44 bytes

c) 48 bytes

d) 10 bytes

Answer: (b) 44 bytes

We can calculate the available initial free space for storing N records as follows;

Free space = Block size (in bytes) – header size (in bytes) – 2 bytes * N

                        = 4096 – 32 – (2 * N) bytes

                        = 4096 – 32 – (2 * 10) bytes

                        = 4044 bytes

Memory required to store our records = 10 * 400 = 4000 bytes

Free space after storing records = 4044 – 4000 = 44 bytes.

 

2. Which of the following is NOT a valid non-trivial functional dependency for the given instance of relation R(A, B, C)?

A

B

C

a2

b2

c1

a1

b1

c3

a1

b1

c2

a3

b3

c1

 

a) A B

b) AC B

c) AB C

d) BC A

Answer: (c) AB C

The combination of attributes A and B does not uniquely determine C.

Functional dependency states that the left hand side attributes must uniquely determine the right hand side attributes. For a given LHS values, there should be only one RHS value. That is, if the LHS value is repeated in some records, then the same RHS value should appear in all those records. For a functional dependency, A B, if t1[A] = t2[A] then t1[B] must be equal to t2[B]. If such a condition is violated for at least a record in the table, then we can say that the FD does not hold in that table. In simpler terms, if I write an SQL query with LHS attribute(s) in the WHERE condition, then I must get 0 or 1 record for any value of LHS attribute.

In the given table, the FD AB C is violated for the second and third tuples. For the combination (a1, b1) of attributes A and B, we have two different C values c3 and c2.

 

3. Suppose that a relation R has n tuples and S has m tuples. Assume that the attribute A is the primary key of R and the attribute D is the foreign key in S which refers R(A). If we execute an inner join between R and S on R.A = S.D, what will be the maximum number of tuples that can be output?

a) n

b) m

c) n + m

d) n * m

Answer: (b) m

Maximum of m rows would be included in the result set.

From the question, it is understood that the attribute A cannot have duplicates (primary key) and D can have duplicate values. But D cannot have any values which is not part of A. Hence, the number of records in S decides the count of result set.

For example, R.A may have 10 values (unique) and S.D can have values from R.A of these 10 records only. Single value of R.A may be included many times in S.D but S.D cannot have values which is not part of R.A.

 

************************
Related posts:


Quiz questions with answers on DBMS concepts

calculate blocking factor

cost for reading disk block pages for variable length records

What is recoverable schedule?

What will be the maximum number of records that would result from an inner join operation?

What is non-trivial functional dependency 

Wednesday, December 9, 2020

Relational database management systems mcq quiz with answers 20

MCQ on various aspects in DBMS including database disk access and querying, what is blocking factor, cost for reading disk block pages, count the number of disk pages required to store a table, sequential index scan, RDBMS Multiple Choice Questions with Answers

Database management systems - MCQ exam questions 

Let us suppose that we have a retail database with two tables, FIRM(FID, FName, Addr, Contact, Manager) and CUSTOMER(CID, CName, Phone). The records of both the tables are fixed length. The length of each record of FIRM and CUSTOMER are 84 bytes and 30 bytes respectively. FIRM has 30000 records and CUSTOMER has 100000 records. The disk page size is 512 bytes. Use this data to answer the following questions:

1. What are the blocking factors (bfr) for relations FIRM and CUSTOMER?

a) 6, 17

b) 84, 30

c) 58, 195

d) 17, 6

Answer: (a) 6, 17

Blocking factor bfr = floor(block size/record size)

bfr(FIRM) = floor(512/84) = floor(6.1) = 6

bfr(CUSTOMER) = floor(512/30) = floor(17.06) = 17

 

2. Let us suppose that FIRM is sorted on FID attribute and there is no index. What is the cost (in terms of page reads) for finding the FIRM with FID “1” using binary search?

a) 30000

b) 5000

c) 13

d) 59

Answer: (c) 13

To find the required number of pages reads, we need to first find the number of pages occupied by the relation FIRM.

Number of disk pages for FIRM,     N     = Number of records/bfr

                                                                        = 30000/6 = 5000 pages.

 

Cost for reading disk pages using binary search = Ceiling(log2N) = Ceiling(log25000)

                                                                                        = Ceiling(12.29) = 13

 

3. Let us suppose that FIRM is sorted on FID attribute and there is no index. What is the cost (in terms of page reads) for finding the FIRM with FName “ABC Agencies”?

a) 30000

b) 5000

c) 512

d) 13

Answer: (b) 5000

Table FIRM is not sorted on FName attribute. Hence, to find the firm “ABC agencies”, we need to perform SEQUENTIAL SCAN (ie., scan each record one by one from the first record).

Number of page reads = number of disk pages occupied by FIRM = 5000

 

4. Let us suppose that the relation CUSTOMER is sorted on CID attribute and there is no index. Also, the disk block size is 1024 bytes. What is the cost (in terms of page reads) for finding the CUSTOMER with customer ID “C101” using binary search?

a) 13

b) 12

c) 512

d) 59

Answer: (b) 12

Blocking factor bfr(CUSTOMER) = floor(1024/30) = floor(34.13) = 34.

Number of disk pages for CUSTOMER,     N     = Number of records/bfr

                                                                                    = 100000/34 = 2942 pages.

 

Cost for reading disk pages using binary search = Ceiling(log2N) = Ceiling(log22942)

                                                                                        = Ceiling(11.52) = 12

 

5. Let us suppose that all the records of FIRM relation are stored sequentially based on the FID attribute. Also, the FID values are 1, 2, 3, …, 30000. Let us suppose that we create an index IDX1 on FID. If each index block can store 50 entries, how many blocks must the system read to retrieve the contents of the record with id = 2527?

a) 50

b) 51

c) 52

d) 100

Answer: (c) 52

Number of blocks    = Ceiling(Record position/50) + 1

                                    = Ceiling(2527/50) + 1 = Ceiling(50.54) + 1 = 52

That is, 51 index block reads + 1 record block read.

 

************************
Related posts:


Quiz questions with answers on DBMS concepts

calculate blocking factor

cost for reading disk block pages using binary search

how many disk blocks required to store a database file of fixed size records with no spanning of records

Number of page reads required to access the entire table

Cost for sequential scan of entire database table

Wednesday, March 28, 2018

Memory required for external sorting in DBMS

Memory required for external sorting in DBMS


Question:
Let us suppose that you have a file with 150000 pages and 45 available buffer pages. If you use external sorting to sort the above said file, answer the following questions;
a) How many runs will you produce in the first pass?
b) To sort the entire file, how many passes do you need?
c) How much is involved in terms of I/O cost to sort the file?
d) If you like to sort the file in just two passes, then what is the number of buffer pages you need?

Solution:
a) If Nf is the number of file pages and Nb is the number of available buffer pages then the first pass requires Nf/Nb [ceiling(Nf/Nb)] sorted runs.
For our case,
Number of file pages, Nf = 150000
Number of available buffer pages, Nb = 45
The number of sorted runs in the first pass = ⌈150000/45⌉ = 3334 runs

b) The number of passes required to sort the entire file can be calculated using the equation ⌈logNb-1Nf/Nb⌉⌉+1.
Number of passes to sort complete file = ⌈log2⌈150000/45⌉⌉+1
                                                                   = ⌈log23334⌉+1 = 13 passes

c) Since each page is read and written once per pass, the total number of page I/Os for sorting the file is 2 * Nf * (#passes):
Total I/O cost for sorting the file = 2 * 150000 * 13 = 39,00,000

d) In Pass 0, Nf/Nbruns are produced. In Pass 1, we must be able to merge this many runs; i.e., Nb − 1 ≥ Nf/Nb. This implies that Nb must at least be large enough to satisfy Nb * (Nb − 1) ≥ Nf; this can be used to guess at Nb, and the guess must be validated by checking the first inequality. Thus;
With 150000 pages in the file, Nb = 388 satisfies both inequalities, but Nb = 387 does not. So we need 388 buffer pages to sort the entire file in just two passes.
[Note: to find the value of Nb, factorize the equation Nb * (Nb-1) = Nf which can be written as a quadratic equation Nb2-Nb-Nf = 0. The equation to be solved is Nb2 - Nb - 8500 = 0]

*********




buffer pages required for external sorting
number of passes required to complete sorting of a file using external sorting
external sorting technique in database 
number of runs required for each pass in external sorting
I/O cost involved in sorting the entire file
 




Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents

data recovery