Query Optimizationتحسين الاستعلامات
مقدمة الفصل
ماذا ستتعلم في هذا الفصل
- Relational algebra and its five basic operations: selection, projection, cross-product, set-difference, union.
- Joins: natural join and theta join.
- Equivalent relational expressions and the equivalence rules.
- Transforming expressions: performing selections early and choosing a join order.
أقسام الفصل
- 1Relational algebra: the five basic operationsالجبر العلائقي: العمليات الخمس الأساسية
- 2Selection, projection and nesting (sailing database)الاختيار والإسقاط والتداخل (قاعدة الإبحار)
- 3Union, set difference and cross-productالاتحاد والفرق والضرب الديكارتي
- 4Joins: natural join and theta joinالربط: الطبيعي وربط ثيتا
- 5Equivalent relational expressionsالتعبيرات العلائقية المتكافئة
- 6Equivalence rules 1–6قواعد التكافؤ 1–6
- 7Equivalence rules 7–12قواعد التكافؤ 7–12
- 8Transformation examples and join orderingأمثلة التحويل وترتيب الربط
تلميح: استخدم أسهم لوحة المفاتيح للتنقل بين الشرائح.
Relational algebra: 5 basic operationsالعمليات الأساسية
Relational algebra: the five basic operations
A formal language used to query and manipulate relational databases — selection, projection, union, join, … — very useful for representing execution plans.
| Operation | Symbol | What it does (slide 3) |
|---|---|---|
| Selection | σ | Selects a subset of rows from a relation (horizontal) |
| Projection | π | Retains the required columns from a relation (vertical) |
| Cross-product | × | Allows us to combine two relations |
| Set-difference | − | Tuples in r1, but not in r2 |
| Union | ∪ | Tuples in r1 and/or in r2 |
- Each operation returns a relation, so operations can be composed — the algebra is "closed".
Selection and projectionالاختيار والإسقاط
Selection, projection and nesting (sailing database)
| sid | sname | rating | age |
|---|---|---|---|
| 28 | yuppy | 9 | 35.0 |
| 31 | lubber | 8 | 55.5 |
| 44 | guppy | 5 | 35.0 |
| 58 | rusty | 10 | 35.0 |
Rows that satisfy the condition; schema of the result is the same as the input. σ rating>8 (S2) = yuppy (9), rusty (10).
Exactly the fields in the projection list; has to eliminate duplicates (real systems typically don't, unless the user asks). π age (S2) = 35.0, 55.5.
An operator's result is a relation, so it can feed another: π sname,rating (σ rating>8 (S2)) = (yuppy, 9), (rusty, 10).
Union, set difference and cross-productالاتحاد والفرق والضرب
| sid | sname | rating | age |
|---|---|---|---|
| 22 | dustin | 7 | 45.0 |
| 31 | lubber | 8 | 55.5 |
| 58 | rusty | 10 | 35.0 |
- S1 ∪ S2: dustin, lubber, rusty, guppy, yuppy — 5 tuples (common tuples appear once).
- S1 − S2 = (22, dustin, 7, 45.0). S2 − S1 = (28, yuppy), (44, guppy).
- S1 × R1: each row of S1 paired with each row of R1.
Joinsالربط
Natural join R ⋈ S, conceptually (slide 13)
- 1
Compute R × S.
- 2
Select rows where attributes that appear in both relations have equal values.
- 3
Project all unique attributes and one copy of each of the common ones.
- Joins are compound operators (cross product, selection, sometimes projection) — usually done much more efficiently than this.
- Useful for putting "normalized" relations back together.
Equivalent expressionsالتعبيرات المتكافئة
Equivalent relational expressions
Two relational algebra expressions that generate the same set of tuples on every legal database instance (order of tuples is irrelevant); they have the same set of attributes and the same set of tuples.
Says that expressions of two forms are equivalent: replace the first form by the second, or vice versa.
Equivalence rules 1–6القواعد 1–6
تذكّر القاعدة قبل الكشف.
- 1Conjunctive selection
σ θ1∧θ2 (E) = σ θ1 (σ θ2 (E)) — deconstructed into a sequence of individual selections.
- 2Selection is commutative
σ θ1 (σ θ2 (E)) = σ θ2 (σ θ1 (E)).
- 3Sequence of projections
Only the last is needed: π L1 (π L2 (… (π Ln (E)))) = π L1 (E).
- 4Selection with × and theta join
σ θ (E1 × E2) = E1 ⋈ θ E2; σ θ1 (E1 ⋈ θ2 E2) = E1 ⋈ θ1∧θ2 E2.
- 5Joins are commutative
E1 ⋈ θ E2 = E2 ⋈ θ E1.
- 6Joins are associative
(E1 ⋈ E2) ⋈ E3 = E1 ⋈ (E2 ⋈ E3); for theta joins, θ2 must involve attributes from only E2 and E3.
Equivalence rules 7–12القواعد 7–12
تذكّر القاعدة قبل الكشف.
- 7Selection distributes over the theta join
(a) θ0 involves only E1's attributes: σ θ0 (E1 ⋈ θ E2) = (σ θ0 (E1)) ⋈ θ E2. (b) θ1 only E1, θ2 only E2: σ θ1∧θ2 (E1 ⋈ θ E2) = (σ θ1 (E1)) ⋈ θ (σ θ2 (E2)).
- 8Projection distributes over the theta join
(a) If θ involves only L1 ∪ L2: π L1∪L2 (E1 ⋈ θ E2) = (π L1 (E1)) ⋈ θ (π L2 (E2)); (b) otherwise keep the join attributes L3, L4 in the inner projections.
- 9Union and intersection are commutative
E1 ∪ E2 = E2 ∪ E1; E1 ∩ E2 = E2 ∩ E1 — set difference is not commutative.
- 10Union and intersection are associative
(E1 ∪ E2) ∪ E3 = E1 ∪ (E2 ∪ E3); likewise for ∩.
- 11Selection distributes over ∪, ∩ and −
σ θ (E1 − E2) = σ θ (E1) − σ θ (E2); also σ θ (E1 − E2) = σ θ (E1) − E2.
- 12Projection distributes over union
π L (E1 ∪ E2) = (π L (E1)) ∪ (π L (E2)).
Transformation examplesأمثلة التحويل
- Schema: branch(branch_name, branch_city, assets); account(account_number, branch_name, balance); depositor(customer_name, account_number); …
المسألة
Names of all customers with an account at some branch located in Brooklyn (slides 25–26).
خطوات الحل
- π customer_name (σ branch_city="Brooklyn" (branch ⋈ (account ⋈ depositor)))
- Rule 7a: the condition involves only branch's attributes
النتيجة
π customer_name ((σ branch_city="Brooklyn" (branch)) ⋈ (account ⋈ depositor)) — performing the selection as early as possible reduces the size of the relation to be joined.
المسألة
… and whose account balance is over $1000 (slides 27–28).
خطوات الحل
- π customer_name (σ branch_city="Brooklyn" ∧ balance>1000 (branch ⋈ (account ⋈ depositor)))
- Rule 6a (join associativity): π customer_name ((σ branch_city="Brooklyn" ∧ balance>1000 (branch ⋈ account)) ⋈ depositor)
- Now "perform selections early" applies
النتيجة
σ branch_city="Brooklyn" (branch) ⋈ σ balance>1000 (account) — a sequence of transformations can be useful.
Join orderingترتيب الربط
For all relations r1, r2, r3: (r1 ⋈ r2) ⋈ r3 = r1 ⋈ (r2 ⋈ r3). If r2 ⋈ r3 is quite large and r1 ⋈ r2 is small, we choose (r1 ⋈ r2) ⋈ r3, so that we compute and store a smaller temporary relation.
الخلاصة
أنهيت الدرس
الخطوة التالية: ثبّت المعلومات بالبطاقات، ثم اختبر نفسك بالأسئلة.
ما راجعته في هذا الدرس
- Relational algebra: the five basic operationsالجبر العلائقي: العمليات الخمس الأساسية
- Selection, projection and nesting (sailing database)الاختيار والإسقاط والتداخل (قاعدة الإبحار)
- Union, set difference and cross-productالاتحاد والفرق والضرب الديكارتي
- Joins: natural join and theta joinالربط: الطبيعي وربط ثيتا
- Equivalent relational expressionsالتعبيرات العلائقية المتكافئة
- Equivalence rules 1–6قواعد التكافؤ 1–6
- Equivalence rules 7–12قواعد التكافؤ 7–12
- Transformation examples and join orderingأمثلة التحويل وترتيب الربط