209 - 293: Query Optimization Flashcards
What is a Query Graph?
A query graph is an undirected graph where relations are vertices and predicates between attributes of relations form edges.
What is the advantage of unnesting dependent joins?
A) Avoids the need for hash joins.
B) Reduces data redundancy.
C) Enables the use of alternate join implementations.
D) Increases query complexity.
C) Enables the use of alternate join implementations.
What is the Catalan Number’s relevance to join ordering?
A) Counts possible nested queries.
B) Gives the number of query graph edges.
C) Indicates the number of possible binary join trees.
D) Measures join selectivity.
C) Indicates the number of possible binary join trees.
What is the Principle of Optimality?
An optimal join tree’s subtrees are also optimal join trees for their respective relations.
What are Randomized Approaches in Optimization?
Methods like hill climbing or simulated annealing explore alternatives to avoid exhaustive enumeration of join trees.
What is Query Unnesting?
Unnesting transforms nested subqueries into equivalent joins or simplified queries for efficiency.
What are Cost Functions for Joins?
Nested Loops Join:|R1|x|R2|
Hash Join: 1.2 * |R1|
Sort-Merge Join: |R1|log|R1|+|R2|log|R2|
Which join tree type allows cross products?
A) Left-deep
B) Right-deep
C) Zigzag
D) Bushy
D) Bushy
Dynamic Programming in Query Optimization
Dynamic programming avoids redundant computations by reusing results of sub-problems to build optimal join trees incrementally.
Greedy Operator Ordering (GOO)
GOO selects join trees or relations to combine based on minimizing the size of intermediate results.
What is the primary reason for optimizing join order?
A) To increase query graph complexity.
B) To reduce the cost of intermediate results.
C) To avoid cyclic dependencies in the query graph.
D) To increase the size of the result set.
B) To reduce the cost of intermediate results.
What is a Join Tree?
A join tree is a binary tree used in query plans, where:
Leaf nodes are relations.
Inner nodes are join operators.
Cardinality of Join Trees
if T is leaf relation R:
|T|= |R|
if T= T1 join T2:
|T|=Product_(Ri e T1, Rj e T2) of f_i,j * |T1|*|T2|
Join Selectivity Formula f_i,j
f_i,j = |Ri Join_pi, j Rj| / |Ri|x|Rj|
What is a Materialized View?
A materialized view is a database object where the results of a query are precomputed and stored. Updates to the underlying tables require updates to the materialized view.
What is denormalization in database schema design?
Denormalization is the process of intentionally introducing redundancy into a database schema to improve query performance by reducing joins.
What is the tradeoff of using denormalization in a database schema?
Denormalization improves query performance but introduces redundancy, which can complicate updates and increase storage costs.
Which of the following statements about Materialized Views is correct?
a) The query result is computed at runtime.
b) They are automatically updated without user intervention.
c) They store precomputed query results.
d) They cannot be used for optimization.
c) They store precomputed query results.
