Member Avatar for unknown.zed

Consider the relation R(A,B,C,D), consisting of 100,000 tuples. Each page contains 10 tuple entries. R is saved as a heap with dense secondary indexes on B. Data is distributed randomly. The attribute B lies densely in [1, 100,000] i.e., each value in [0, 100,000] occurs in B. Consider these three methods of access:
A1.reading the entire heap file for R (no index)
A2.access by means of a B+ Tree on B.
A3.access by means of a hash-index on B
(extensible hash, directory in main memory)

(i) Assume that the application uses mainly point queries regarding attribute B. Estimate the minimal and the maximal number of block accesses that each of the methods A1, A2, and A3 need for point queries. Explain your answers. Which method requires the smallest number of accesses for the minimal case and which for the maximal case?

(ii) Assume that the application uses mainly range queries. Estimate the minimal and the maximal number of block accesses that each of the methods A1, A2, and A3 need for range queries. Explain your answers. Which method requires the smallest number of accesses for the minimal case and which for the maximal case?

  • 2 Contributors
  • 1 Reply
  • 89 Views
  • 17 Hours Discussion Span
  • Latest Post Latest Post by tesuji
Member Avatar for tesuji

Hi,

Once I had heard of all of them, well 10 years ago, when I finished Uni. So let me take a try:

A1. worst case requires O(N)reads, where N= 100000/10 = 10,000 pages to read. Best case is 1 read. (Efforts for page scanning in main memory ignored.)

A2. B+ requires O(log n) reads. Because of dense indexes retrieving one tuple requires log(100,000) + 1 reads = 17+1 = 18 reads (worst case). Best case is one read for getting the key + 1 read for tuple, makes 2 reads.

A3. If directory is in main memory, there is only one read to get the bucket where hash B points to. Effort for bucket scan to retrieve the key ignored. Finally tuple is read, therefore 2 reads. Best case also 2 reads.

These should be for point queries (one tuple per select). As for range queries I have no ideas.

I hope above approach to your problem isn't that completely wrong, at least it could inspire and direct you a little.

Please, let me know the correct result.

-- tesu

Edited by tesuji because: n/a
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.