Relational Algebra

วิดีโอที่เกี่ยวข้อง:

3.1ทำไมต้องเรียน Relational Algebra

เกิดอะไรขึ้นเมื่อเรารัน SQL

SELECT name FROM instructor WHERE salary > 90000;

↓ Parser แปลเป็น relational algebra

Π _name ( σ _{salary > 90000} ( instructor ) )

↓ Optimizer เลือกแผนที่ถูกที่สุดจากนิพจน์ที่สมมูลกัน

↓ Execution engine คืนผลลัพธ์

3.26 Basic Operators — ลองกดเล่นได้

1 · Select — σ (sigma)

เป็น operation ที่ใช้บ่อยที่สุด: เลือก tuple จาก relation เดียวที่ทำให้ predicate เป็นจริง

σ _p (r)

• p เรียกว่า selection predicate
• ใช้ตัวเปรียบเทียบได้: = ≠ > ≥ < ≤
• รวมหลายเงื่อนไขด้วย ∧ (and) · ∨ (or) · ¬ (not)
• เปรียบเทียบระหว่าง attribute สองตัวได้ เช่น σ dept_name = building (department) = หาแผนกที่ชื่อตรงกับชื่อตึก

σ dept_name='Physics' (instructor)
σ dept_name='Physics' ∧ salary > 90000 (instructor)

2 · Project — Π (pi)

unary operation (= operation ที่รับ relation เข้าไปตัวเดียว ตรงข้ามกับ binary ที่รับสองตัวอย่าง ∪ หรือ ×) ซึ่งคืน relation เดิมโดยตัด attribute บางตัวออก

Π _{A₁, A₂, …, Ak} (r)

3–5 · Set operations — ∪, −, (∩)

เงื่อนไขที่ต้องเป็นจริงก่อนใช้ set operation:

1. r และ s ต้องมี arity เท่ากัน (จำนวน attribute เท่ากัน)
2. domain ของ attribute ต้องเข้ากันได้ — คอลัมน์ที่ 2 ของ r ต้องเป็นข้อมูลชนิดเดียวกับคอลัมน์ที่ 2 ของ s

Fall 2017 เปิด {CS-101, CS-347, PHY-101} · Spring 2018 เปิด {CS-101, CS-315} → ∪ = {CS-101, CS-347, PHY-101, CS-315} · ∩ = {CS-101} · − (Fall ลบ Spring) = {CS-347, PHY-101}

-- วิชาที่เปิดสอน Fall 2017 หรือ Spring 2018 หรือทั้งสอง
Π course_id (σ semester='Fall' ∧ year=2017 (section))
  ∪ Π course_id (σ semester='Spring' ∧ year=2018 (section))

-- วิชาที่เปิดสอนทั้งสองภาค
… ∩ …

-- วิชาที่เปิด Fall 2017 แต่ไม่เปิด Spring 2018
… − …

6 · Cartesian product — ×

รวมข้อมูลจาก relation สองตัว โดยสร้าง tuple ผลลัพธ์จากทุกคู่ที่เป็นไปได้ ผลลัพธ์มีคอลัมน์ของทั้งสองตารางต่อกัน และมีจำนวนแถว = (แถวของ r) × (แถวของ s)

ข้อมูลตัวอย่างที่ใช้ทั้งหัวข้อนี้ (จากสไลด์ university database):

สังเกตว่า teaches.ID คือ FK ที่ชี้ไปหา instructor.ID — Mozart (15151) ไม่มีแถวใน teaches เลย แปลว่าเทอมนี้เขาไม่ได้สอน

เนื่องจาก ID เป็นชื่อคอลัมน์ที่ปรากฏในทั้งสอง relation พอเอามาต่อกันแล้วจะมีคอลัมน์ชื่อ ID สองอัน เราจึงต้องแยกความต่างด้วยการเติมชื่อ relation นำหน้า: instructor.ID (รหัสอาจารย์จากตารางซ้าย) และ teaches.ID (รหัสอาจารย์จากตารางขวา)

สรุป: × ให้ “ทุกความเป็นไปได้” ซึ่งรวมทั้งที่จริงและที่มั่ว — งานของเราคือกรองเฉพาะที่จริงออกมา ซึ่งก็คือ join ในหัวข้อถัดไป

Join — ⋈ (derived)

เพื่อเก็บเฉพาะ tuple ที่อาจารย์กับวิชาที่เขาสอนตรงกันจริง เราใช้ σ กรองผลของ ×

σ _{instructor.ID = teaches.ID} ( instructor × teaches )

นิพจน์นี้เรียกว่า equi-join — ยังไม่ใช่ instructor ⋈ teaches เป๊ะ ๆ เพราะผลลัพธ์ยังมีคอลัมน์ ID อยู่ สองอัน · ต้อง project ทิ้งอันหนึ่งก่อนถึงจะเท่ากัน:
instructor ⋈ teaches = Π_{ID, name, dept_name, salary, course_id, sec_id, semester, year} ( σ_{instructor.ID = teaches.ID} ( instructor × teaches ) )

σ ตัวนี้ทำหน้าที่ “เก็บเฉพาะ 3 แถวสีเขียวในตารางข้างบน ทิ้ง 6 แถวขยะ” ผลลัพธ์คือ:

Mozart หายไป เพราะไม่มีแถวใน teaches ที่ ID = 15151 → เขาไม่มีคู่ให้ join ด้วย (นี่คือพฤติกรรมของ inner join)

Natural join (⋈) จับคู่ tuple ที่มีค่าเท่ากันบน attribute ร่วมทุกตัว (ในที่นี้คือ ID ตัวเดียว) และเก็บคอลัมน์ร่วมไว้ชุดเดียว — ต่างจากบรรทัดบนที่มี ID โผล่มา 2 คอลัมน์ instructor ⋈ teaches จะเหลือ ID แค่คอลัมน์เดียว

Rename — ρ (rho) และ Assignment (←)

ผลลัพธ์ของนิพจน์พีชคณิตไม่มีชื่อให้เราอ้างถึง จึงมี rename operator

ρ x (E)                    -- ตั้งชื่อผลของ E ว่า x
ρ x(A₁, A₂, …, Aₙ) (E)       -- ตั้งชื่อทั้ง relation และ attribute
ρ ชื่อใหม่ ← ชื่อเดิม (E)       -- เปลี่ยนชื่อ "แค่คอลัมน์เดียว"

-- ตัวอย่าง ρ: Inventory(ISBN, StockQuantity) → Inventory(ISBN, AvailableStock)
ρ AvailableStock ← StockQuantity (Inventory)

Assignment (←) ช่วยให้เขียน query ยาว ๆ เป็นลำดับขั้นเหมือนโปรแกรม

Physics ← σ dept_name='Physics' (instructor)
Music   ← σ dept_name='Music'   (instructor)
Physics ∪ Music

3.3การประกอบ operator เข้าด้วยกัน

ผลลัพธ์ของทุก operation คือ relation ดังนั้นเราเอาผลลัพธ์ไปเป็น input ของ operation ถัดไปได้ แทนที่จะใส่ชื่อ relation เป็นอาร์กิวเมนต์ของ Π เราใส่นิพจน์ที่ให้ผลเป็น relation แทนได้เลย

ตัวอย่างจากสไลด์ต่อจากนี้อ้างภาค Physics ซึ่งไม่มีในตาราง 3 แถวข้างบน — ให้คิดว่าตารางเต็มของตำรามีแถวนี้อยู่ด้วย: (22222, Einstein, Physics, 95000)

-- ชื่อของอาจารย์ทุกคนในภาควิชา Physics
Π name ( σ dept_name='Physics' (instructor) )

3.4Equivalent Queries และ Query Optimization

query หนึ่งเขียนได้หลายแบบ — ตัวอย่างจากสไลด์: หาข้อมูลอาจารย์ในภาค Physics ที่เงินเดือนเกิน 90,000

สองนิพจน์นี้ ไม่เหมือนกัน (not identical) แต่ สมมูลกัน (equivalent) — คือให้ผลลัพธ์เดียวกันบนฐานข้อมูลทุกชุดที่เป็นไปได้

คู่ที่ “ไม่” สมมูลกัน — โจทย์ Part C จากแบบฝึกหัด

ข้อพวกนี้ใช้ schema จากใบงานสัปดาห์ที่ 3: Student(student_id, name, major, gpa) — ข้อมูลจริง 5 แถวอยู่ใน §3.5 ด้านล่าง

3.5ฝึกจากโจทย์จริงในคาบ

ใช้ schema นี้ (จากใบงาน Relational Algebra สัปดาห์ที่ 3):

Student(student_id, name, major, gpa)
Course(course_id, title, credits, dept_name)
Enrollment(student_id, course_id, semester, year, grade)

Part A — อ่านนิพจน์ แล้วเขียนตารางผลลัพธ์

Part B — เขียนนิพจน์เอง

σ dept_name='CoE' ∧ credits=3 (Course)

Π name, major ( σ gpa > 2.X (Student) )

Π course_id ( σ year=2026 (Enrollment) )
   −
Π course_id ( σ year=2025 (Enrollment) )

Π name ( Student ⋈ σ course_id='EN813304' (Enrollment) )

Π name ( σ Student.student_id = Enrollment.student_id
       ( Student × σ course_id='EN813304' (Enrollment) ) )

3.6ตัวอย่างจากสไลด์เพิ่มเติม

a) หนังสือราคาเกิน $20        σ Price > 20 (Books)
b) เฉพาะชื่อเรื่องกับผู้แต่ง   Π Title, Author (Books)
c) ISBN ที่อยู่ใน Books หรือ Inventory
   Π ISBN (Books) ∪ Π ISBN (Inventory)
d) ISBN ที่อยู่ใน Books แต่ไม่อยู่ใน Inventory
   Π ISBN (Books) − Π ISBN (Inventory)
e) เปลี่ยนชื่อ StockQuantity เป็น AvailableStock
   ρ AvailableStock ← StockQuantity (Inventory)

a) ออเดอร์เกิน $100 ของลูกค้าใน New York
   σ TotalAmount>100 (Orders)
     ⋈ σ Address LIKE '%New York%' (Customers)
b) ชื่อลูกค้ากับวันที่สั่งซื้อ
   Π Name, OrderDate (Customers ⋈ Orders)
c) รวม CustomerID จากทั้งสองตาราง
   Π CustomerID (Customers) ∪ Π CustomerID (Orders)
d) ลูกค้าที่ไม่เคยสั่งซื้อเลย
   Π CustomerID (Customers) − Π CustomerID (Orders)
e) ทุกคู่ที่เป็นไปได้        Customers × Orders
f) เปลี่ยนชื่อ TotalAmount   ρ OrderValue ← TotalAmount (Orders)

3.7ตารางแปลง SQL ↔ Relational Algebra