SQL and Algorthim Question: Can someone please answer these question with regard

Question

SQL and Algorthim Question: Can someone please answer these question with regards to A and B as well as a through explanation. I will give good ratings for an correct answer.

1. Compute the IO cost of the external merge sort algorithm given a 10,000 page file, given 33 available buffer pages in the two cases: a. Using 2-may merging. b. Using optimized B-way merging. 2. For problem in exercise 1, how would the IO cost change if repacking was used? 3. When constructing a B+ tree for an attribute containing "long double" values, what is the maximum degree of the tree given blocks of size a. 2A12 b. 2A16

Explanation / Answer

1.a) N=10,000 page file

B=33 buffer pages

For each pass, we will read and write every page in N.

N=10,000 page size. B=33 buffer size

All available buffer pages will be used in the first pass..
In the next pass,Pass 1,B-1 pages are loaded into the available buffers.

Complexity:The number of I/Os is the factor considered. Let N be the number of pages. Each run will cost 2N.
We will read the page and then write the page.

Let B be the number of buffer pages and N be the count of pages in page file.
There will be ceil(log B-1(ceil(N/B))) passes. Each pass will have 2N I/Os. So,time complexity will be of the order of O(nlogn).

Pass0: ceil(10,000 / 33) = 303, 33 pages per run
Pass1: ceil(303 / 32) = 10, 1056 pages per run
Pass2: ceil(10/ 32 ) = 1,done ,1 run of 10,000 pages per run

Total IO cost=2N*(log2 N +1)=2*10,000(log2 10^4 +1)

=20,000*(4*log2 10+1)

=20,000*(4*3.321928 +1)

=20,000*14=2,80,000 units.

2)

For our problem , if repacking technique is to be used ,we need to create larger initial runs for optimizing our algorithm.

•We load the unsorted pages and write the next large values in our page files.

•Additionally, there is a pointer for each row which points to the next child page.

We have, Memory M, block size B, problem size N
basic operations:
Let us compare with other merge algorithms,
Standard merge sort based on linear scans: T(N) = 2T(N/2)+O(N/B) =O((N/B) log N)
•We can improve by using more memory , we use M/B-way merge
First, keep head block of each of M/B lists in memory and then keep emitting smallest item
After we emit B items, we write a block and when block empties, we read next block of that list
• Time complexity T(M) = O(N/B) + (M/B)T(N/(M/B)) = O((N/B) logM/B N/B)
Let us consider the following criteria,
•Size of RAM = M items
•Size of a disk page = B items
•In one I/O operation, we can read or write one page
•Complexity of an algorithm =number of I/Os used

•We can perform sorting with k-way merging afre repacking as follows:
1. Create N/M sorted lists of length M
2. At round h = 1, 2, …
Merge k sorted list of length k ^ h-1 M,
forming a sorted list of length k ^h M
# rounds = logk (N/M)

Lets assume M=512 bytes
Total I/O = O( (N/B) logk(N/M) )

=O(10,000/33)log 3(10,000/M)

=O(303)log(10,000/512)

=(303)*1.29

=390.87=391units


C)
Degree represents the minimum number of children possible. Order is max number number of children.

By the formula for internal node of B+-tree
b=index pointer size
k=variable length=8 bytes
Degree=n
(n-1) k+ n b = block size
(n-1) * 8 + n*4=2^12
8n-8+4n=4096
12n=4096+8=4104

n=342

Similarly,

(n-1) k+ n b = block size
(n-1) * 8 + n*4=2^16

8n-8+4n=65536

12n=65536+8=65544

n=5462

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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