Query processing in DBMS

  • Thread starter momentum
  • Start date
  • #1
111
0
This is written in my book.

Can you please reply to these queries in Q1 & Q2.

4Gl3cAB.jpg


I'm stuck on those
 

Attachments

  • 4Gl3cAB.jpg
    4Gl3cAB.jpg
    97 KB · Views: 491

Answers and Replies

  • #2
.Scott
Homework Helper
2,679
989
1) A and B are attributes of relations R and S respectively. If you are thinking in terms of a spread sheet, then you could call them columns. If you are thinking of the relation as files and records, then they would be fields.
2) A DBMS is implemented as file(s). The records in those files is in some order - sorted or not.

For example:
R may be a relation that lists your customer and S may be a relation that is a phone directory.
R is implemented as a file named RF with records ordered by the "customer number" field.
S is implemented as a file names SF with records ordered by the "last name" and "first name" fields.

And say we want to do a "EQUIJOIN" between relation R, attribute "business phone" and relation S, attribute "number".
So this is what we do:
1a) If we already have an index into file RF that is sorted by "business phone", then we skip to step 2.
1b) We build an index into the records in RF that includes field "business phone".
1c) We sort that index by "business phone".

2a) If we already have an index into file SF that is sorted by "number", then we skip to step 3.
2b) We build an index into the records in SF that includes field "number".
2c) We sort that index by "number".

3) We step through those two sorted indexes looking for matches.

Relational terms: relation, tuple, attribute
File terms: file, record, fields.
Spreadsheet terms: sheet, row, column
 
Last edited:
  • #4
111
0
1) A and B are attributes of relations R and S respectively. If you are thinking in terms of a spread sheet, then you could call them columns. If you are thinking of the relation as files and records, then they would be fields.
2) A DBMS is implemented as file(s). The records in those files is in some order - sorted or not.

For example:
R may be a relation that lists your customer and S may be a relation that is a phone directory.
R is implemented as a file named RF with records ordered by the "customer number" field.
S is implemented as a file names SF with records ordered by the "last name" and "first name" fields.

And say we want to do a "EQUIJOIN" between relation R, attribute "business phone" and relation S, attribute "number".
So this is what we do:
1a) If we already have an index into file RF that is sorted by "business phone", then we skip to step 2.
1b) We build an index into the records in RF that includes field "business phone".
1c) We sort that index by "business phone".

2a) If we already have an index into file SF that is sorted by "number", then we skip to step 3.
2b) We build an index into the records in SF that includes field "number".
2c) We sort that index by "number".

3) We step through those two sorted indexes looking for matches.

Relational terms: relation, tuple, attribute
File terms: file, record, fields.
Spreadsheet terms: sheet, row, column

okay. But it says "Pair of file blocks" (marked in red) . What is this ? Could you please elaborate this part a bit


T6yz7ID.jpg
 

Attachments

  • T6yz7ID.jpg
    T6yz7ID.jpg
    89.5 KB · Views: 141
  • #5
.Scott
Homework Helper
2,679
989
okay. But it says "Pair of file blocks" (marked in red) . What is this ? Could you please elaborate this part a bit
What I described was an index sort. In their description, they are creating two files, one from relation R the other from S. Both are sorted.
They are then reading from each of these files, a block at a time. Blocks are the smallest unit that can be read from the file system - typically 512, 1K, 2K, or 4K bytes. So it will read one block from R and one block from S - thus a pair.
 
  • #6
111
0
What I described was an index sort. In their description, they are creating two files, one from relation R the other from S. Both are sorted.
They are then reading from each of these files, a block at a time. Blocks are the smallest unit that can be read from the file system - typically 512, 1K, 2K, or 4K bytes. So it will read one block from R and one block from S - thus a pair.

Okay. this is better.

Some more doubts on this.

They also said

"blocks are copied into memory in order " ---------> what does it mean by in order here ? Is not they are copied separately

"
records are scanned ....... each for matching with the other file" -------> does it mean only the matching records (i.e output from join) are copied ? Not the entire R & S is copied ?
 
  • #7
2,006
288
"blocks are copied into memory in order " ---------> what does it mean by in order here ? Is not they are copied separately

First the first block of R is read into memory. Once it's clear that there are no more mathches with S possible for this block, the next block is read from the file.

"records are scanned ....... each for matching with the other file" -------> does it mean only the matching records (i.e output from join) are copied ? Not the entire R & S is copied ?

Only the matching records are copied. Thats is the idea with an equi-join.

The whole description of a merge-join looks like something of 50 years ago, with tape drives and very small memories. The only thing that seems to be relevant for the runtime, is the time to read or write a block. Nowadays you try to read as much as possible of the files into memory while sorting them. A temporary index will likely be created instead of sorting the files themselves, because only the index column would have to be loaded into memory.
 
  • #8
jtbell
Mentor
15,752
3,950
"blocks are copied into memory in order " ---------> what does it mean by in order here ?
It probably means "in sequence". That is, blocks are read from each file in the same (linear) sequence in which they are stored: record #1, record #2, record #3, etc.
 
  • #9
111
0
Thanks . That was very much helpful.

Please see this below.

KAqzdDC.jpg
 

Attachments

  • KAqzdDC.jpg
    KAqzdDC.jpg
    103.6 KB · Views: 117

Related Threads on Query processing in DBMS

  • Last Post
Replies
5
Views
635
  • Last Post
Replies
6
Views
726
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
3
Views
3K
Replies
4
Views
1K
  • Last Post
Replies
4
Views
6K
  • Last Post
Replies
6
Views
899
Replies
0
Views
2K
Replies
2
Views
2K
Top