Query processing in DBMS

  • Thread starter momentum
  • Start date
  • #1
102
0

Main Question or Discussion Point

This is written in my book.

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

4Gl3cAB.jpg


I'm stuck on those
 

Attachments

Answers and Replies

  • #2
.Scott
Homework Helper
2,464
861
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:
  • #3
PeterDonis
Mentor
Insights Author
2019 Award
28,311
8,069
  • #4
102
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

  • #5
.Scott
Homework Helper
2,464
861
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
102
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
1,943
241
"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,519
3,358
"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
102
0
Thanks . That was very much helpful.

Please see this below.

KAqzdDC.jpg
 

Attachments

Related Threads on Query processing in DBMS

  • Last Post
Replies
5
Views
560
  • Last Post
Replies
6
Views
634
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
3
Views
3K
Replies
4
Views
919
  • Last Post
Replies
4
Views
6K
  • Last Post
Replies
6
Views
764
Replies
0
Views
2K
Replies
2
Views
2K
Top