Computing number of block reads given relational algebra statement

Question

So I'm just starting to learn about query processing and such in databases and I'm having some trouble. I don't really understand how to compute the minimum number of block reads given a relation and a query I guess you could say. If anyone could help me out, it'd be much appreciated. Here is an example that I'm working on:

• R1(A,B,C) A is a primary key and C is a foreign key to R2.C
• R2(C,D,E) C is a primary key
• R1 has 20,000 records, with 200 records per block. There is a primary B+-tree index on A with height h = 3
• R2 has 45,000 records, with 4,500 records per block. There is a primary B+-tree index on C with height hC = 3 and a secondary B+-tree index on D with height hD = 2.

Find the minimum number of block reads for each statement. I can only hold one block of memory for each relation at a time.

• Where B=1(R1)
• Where C=1(R2)

I'm not looking for answers. I'm looking for explanation of how to actually do it and guide me along the way. Aka equations, etc. It's kind of difficult to find anything beneficial online at all.

Answer 1

select * from R1 Where B=1

You don't have any index on a search field (B), hence you have to do a full table scan. It means that you fetch all relation's blocks one by one and take the records which satisfy the condition B=1. (Cost - 200000/200 = 200 blocks)

select * from R2 Where C=1

There is not enough information - you have to know(at least approximately) how many records in R2 satisfy the condition C=1. For example in case that all the records in R2 have C=1 you'll do the full table scan like above (cost - 45000/4500 = 10 blocks) On the other hand if you have only one record with C=1 you'll read 3 blocks of index and another one from disk(cost 3 + 1 = 4 blocks)