Query Processing

Question 1

What are the three basic steps in query processing?

Answer 1

<ol>
<li>Parser and translator</li>
<li>Optimiser</li>
<li>Evaluation</li>
</ol>

Question 2

What happens at the parser and translator stage in query processing?

Answer 2

<ul>
<li>Syntax is checked and referenced relations are verified</li>
<li>Query parsed and translated into relational algebra</li>
</ul>

Question 3

What happens at the optimiser stage in query processing?

Answer 3

<ul>
<li>Query converted to more efficient form</li>
<li>Query evaluation plan is created</li>
</ul>

Question 4

What happens in the evaluation stage in query processing?

Answer 4

Query evaluation plan is executed and the answer is returned

Question 5

What is contained within a query evaluation plan?

Answer 5

Evaluation primitives which are relational algebra operations annotated with execution guidance

Question 6

What are the cost of execution plans estimated using?

Answer 6

Statistical information/estimation for

<ul>
<li>the data dictionary (number of tuples etc)</li>
<li>intermediate results for complex expressions</li>
<li>evaluation estimation</li>
</ul>

Question 7

What is a theta join?

Answer 7

Cartestian product combined with a select statement

Question 8

What are the heuristics for getting a sensible equivalent SQL statement?

Answer 8

<ol>
<li>Perform selections as early as possible</li>
<li>Change conjunctive selection to nested selections</li>
<li>Perform projections as early as possible</li>
<li>Re-order joins to minimise intermediate data</li>
</ol>

Question 9

What is conjunctive selection?

Answer 9

Where two predicates are applied as an and statement, as opposed to applying one predicate then applying the next

Question 10

What are the two factors in estimating query sizes?

Answer 10

<ul>
<li>Size of relations</li>
<li>Distribution of values in tuples</li>
</ul>

Question 11

What statistics stored in the systems catalogue can be useful for estimating the query size?

Answer 11

<ul>
<li>Number of tuples in a relation</li>
<li>Size of a tuple in a relation</li>
<li>Number of distinct values appearing for an attribute</li>
</ul>

Question 12

How do we find the size of a cartesian product?

Answer 12

(number of tuples in q and r) times (the bytes per tuple for each table)

Question 13

How do we estimate the size of a selection?

Answer 13

(number of tuples)/(number of values they can taken)

Question 14

What does the estimation of size of selection assume?

Answer 14

Uniform distribution of values that the attributes do take

Question 15

What is the estimation of size of a natural join of two relations if they have no overlapping elements?

Answer 15

The size of their relations multipled together

Question 16

What is the estimation of the size of a natural join of two relations if the common elements is a key for the first relation?

Answer 16

No more tuples than in the other relation

Question 17

What is the estimation of the size of a natural join of two relations if none of the clever conditions apply (no overlap or overlap is key of a relation)?

Answer 17

Number of tuples in one relation times number of tuples in the othr all divided by the number of values the attribute that is the common attribute can take

Question 18

What is cost generally measured as when looking at queries?

Answer 18

Total elapsed time for answering the query

Question 19

What is taken into account when looking at access costs?

Answer 19

<ul>
<li>Number of seeks * average seek cost</li>
<li>Number of blocks read * average block read cost</li>
<li>Number of blocks written * average block write cost</li>
</ul>

Question 20

What is tT?

Answer 20

Time to transfer one block

Question 21

What is tS?

Answer 21

Time for one seek

Question 22

What is br?

Answer 22

The number of blocks containing tuples of relation r

Question 23

What is fr?

Answer 23

The number of tuples of relation r that fit into one block (blocking factor)

Question 24

What is hi?

Answer 24

The height of the index

Question 25

What is the cost estimate for direct selections where the attribute does not have an index on it?

Answer 25

The time to seek a block + time to transfer a block * number of blocks needed

Question 26

What is the cost estimate for direct selections where the attribute does have a primary index on it and the attribute is a key?

Answer 26

(The height of the index plus one) times (the time to transfer + the time to seek a block)

Question 27

What is the cost estimate for direct selections where the attribute does have a primary index on it but the attribute is not a key?

Answer 27

(the height of the index)*(time to transfer + time to seek) + time to seek + (number of blocks with matching records * time to transfer)

Question 28

What is the cost estimate for direct selections where there is a secondary index on the attribute?

Answer 28

(height of the index + number of matching records) * (time to transfer + time to seek)

Question 29

How are comparison selections performed when there is no index on A?

Answer 29

Each block is scanned and all records are tested by the condition

Question 30

How are comparison selections performed when there is a primary index on A?

Answer 30

Scan sequentially from either the start ()

Question 31

How are comparison selections performed when there is a secondary index on A?

Answer 31

Linear file scan might be cheaper but find the index pointing to a record where the first of the condition holds then scan the INDEX sequentially from there

Question 32

What are evaluation primitives?

Answer 32

Relational algebra operations annotated with execution guidance