4. Query Optimization

Question 1

Equivalence Rules 1
Conjunctive selection operations can be deconstructed into a
___ of individual ___

Answer 1

Sequence

Selections

Question 2

Equivalence Rules 2

Selection operations are ___

Answer 2

Commutative

Question 3

Equivalence Rules 3

Only the last in a sequence of ___ is needed, the others can be ___.

Answer 3

Projection operations

Omitted

Question 4

Equivalence Rules 4

Selections can be combined with ___ and ___.

Answer 4

Cartesian products

Theta joins

Question 5

Equivalence Rules 5

Theta-join operations (and natural joins) are ___.

Answer 5

Commutative

Question 6

Equivalence Rules 6
Natural join operations are ___. Theta joins too in a special manner
(E1 ⨝[theta 12] E2) ⨝[theta 13 ^ theta 23] E3
≡ E1 ⨝[theta 12 ^ theta 13] (E2 ⨝[theta 23] E3)

Answer 6

Associative

Question 7

Equivalence Rules 7
The selection operation distributes over the theta join operation under the following two conditions

a) sigma_theta 1 (E1 ⨝_theta E2)
≡ (sigma_theta 1 (E1)) ⨝_theta E2

b) sigma_[theta 1 ^ theta 2] (E1 ⨝_theta E2)
≡ (sigma_theta 1 (E1)) ⨝_theta E2 (sigma_theta 2 (E2))

Answer 7

…

Question 8

Equivalence Rules 8
produtorio_[L1 U L2] (E1 ⨝_theta E2)
≡ produtorio_L1 (E1) ⨝ produtorio_L2 (E2)

Answer 8

…

Question 9

Equivalence Rules 9/10/11

The set of operations Union and Intersection are ___ and ___. Also they distribute over ___, ___ and ___

Answer 9

Commutative
Associative
U, Inverse U and -

Question 10

Equivalence Rules 12

The Projection Operation distributes over ___

Answer 10

Union

Question 11

Equi-depth histograms break up range such that each range has (approximately) ___

Answer 11

The same number of tuples

Question 12

Size Estimation for Selection

a) If the selection of atribute A equal to value v in relation then size estimate is equal to ___
b) If A <=v then c=___ if v= max(A,r)
c) c is assumed to be ___ in the absence of statistical information

Answer 12

1
0
nr
nr/2

Question 13

Size Estimation for Join
a) if every tuple t in R procuces tuples in R ⨝ S
\_\_\_
b) If the reverse is true
\_\_\_
Choose the lowest of this estimates

Answer 13

nr * ns / V(A,s) [distinct values of A in s]

nr * ns / V(A,r)

Question 14

Size Estimation for Projection
produtorio A (r) = \_\_\_

Answer 14

V(A,r)

Question 15

Cost-Based Optimization

Instead of generating all ___ find the best join order for every __ by finding the best order for ___ recursively

Answer 15

Join orders
Subset
Each subset of every subset

Question 16

Heuristics-based optimization
Heuristic optimization transforms the ___ using the following rules:
1- Perform ___ and ___ early
2- Perform most restrictive ___ and ___ operations (with smallest result size) before other similar operations

Answer 16

Query-tree
Selection and Projection
Selection and Join

Question 17

Memoization
Store the best ___ for a ___ the first time it is optimized, and reuse it on repeated ___ calls on the same subexpression

Answer 17

Plan
Subexpression
Optimization

Question 18

Plan Caching

___ previously computed plan if query is ___

Answer 18

Reuse

Resubmitted

Question 19

A materialized view is a view whose contents are ___ and ___.

Answer 19

Computed

Stored

Question 20

Materialized view maintenance is the task of keeping the materialized view ___

a) recompute on every update
b) use incremental view maintenance (changes to relation updates view)

Answer 20

Up-to-tade

Question 21

Query Optimization with Materialized Views

a) View v = r ⨝ s / User submits r ⨝ s ⨝ t / Query equal to ___
b) View v = r ⨝ s / User sumbits select A=10 (v) / r has an index on A while s has an index on the common attribute / Best plan ___

Answer 21

a) v ⨝ t

b) select A=10(r) ⨝ s