İlişkisel cebir: birleştirmeler, bölme ve gruplama

Geçen hafta altı temel operatörle her sorguyu yazabileceğini gördün. Ama $\sigma(R \times S)$ kalıbını her seferinde yazmak hem uzun hem hataya açık. Bu hafta kısaltmalar geliyor: birleştirmeler (join), dış birleştirmeler (outer join), bölme (division) ve gruplama (aggregation). Sınavda en çok puan getiren iki kalıp burada: çok tablolu birleştirme ve “for every” = bölme.

Altın kurallar:

1. Doğal birleştirme aynı adlı bütün sütunları eşitler. Sadece istediğini değil.
2. NULL hiçbir değere eşit değildir. İç birleştirmede NULL’lu satır kaybolur; dış birleştirme geri getirir.
3. “Every / all” gördüğün an bölme düşün.
4. Gruplama sadece var olan değerlerden grup kurar. Hiç geçmeyen değer 0 ile çıkmaz.

Tablolar geçen haftanın örnek veritabanı: student, course, takes, instructor, department, teaches.

Theta birleştirme ve eşit birleştirme

Theta birleştirme (theta join), çarpım ve seçmenin tek işaretle yazılmış hâlidir:

$R \bowtie_{\theta} S = \sigma_{\theta}(R \times S)$

$\theta$ herhangi bir koşul olabilir ($<, \neq, \ge$ …). Koşul sadece eşitliklerden oluşuyorsa adı eşit birleştirme (equijoin) olur.

Örnek: aynı bölümde, diğerinden daha çok kazanan hoca çiftleri. Tabloyu kendisiyle birleştirdiğimiz için ρ şart:

$\pi_{i.name,\, j.name}(\rho_{i}(instructor) \bowtie_{i.dept\_name = j.dept\_name \land i.salary > j.salary} \rho_{j}(instructor))$

EE ve BIO’da tek hoca olduğu için çift çıkmaz. $>$ yerine $\neq$ yazsaydın her çift iki kez gelirdi: (Aksoy, Demir) ve (Demir, Aksoy).

Doğal birleştirme: ⋈

Doğal birleştirme (natural join) $R \bowtie S$ üç şey yapar:

1. $R \times S$ al,
2. aynı adı taşıyan her sütun çifti için eşitlik seç,
3. tekrar eden sütunları bir kez bırak.

$instructor \bowtie teaches$: ortak sütun sadece inst_id.

6 satır, 5 sütun. Yildiz (I6) eşleşmediği için yok. Ortak sütun hiç yoksa doğal birleştirme düz çarpıma dönüşür.

TUZAK · istemediğin ortak sütun. $student \bowtie takes \bowtie course$ yazınca student.dept_name ile course.dept_name da eşitlenir. Sonuç 14 kayıt değil 9: sadece öğrencilerin kendi bölümünden aldığı dersler kalır. Ada’nın MA101’i, Cem’in MA101 ve CS101’i, Defne’nin CS305’i, Gizem’in her şeyi kaybolur. Çözüm: birleştirmeden önce $\pi_{course\_id,\, title,\, credits}(course)$ ile fazla sütunu at, ya da açık bir theta koşulu yaz.

Doğal birleştirme değişmeli ve birleşmelidir: $(R \bowtie S) \bowtie T = R \bowtie (S \bowtie T)$. Sütun sırası değişebilir, içerik aynı kalır.

Zincir birleştirme

Galata binasındaki bölümlerin derslerini veren hocalar: teaches → course (course_id) → department (dept_name).

$\pi_{inst\_id}(teaches \bowtie \pi_{course\_id,\, dept\_name}(course) \bowtie \sigma_{building = \text{'Galata'}}(department))$

Galata’da CS ve EE var. Bu bölümlerin derslerini I1, I2 ve I3 veriyor.

Dış birleştirmeler

İç birleştirme eşi olmayan satırı atar. Bazen o satır tam olarak istediğin şeydir: “ders vermeyen hocalar da listede görünsün”. Dış birleştirme (outer join) eşleşmeyen satırları korur, eksik sütunları NULL ile doldurur.

instructor ⟕ teaches (sütunların bir kısmı):

teaches ⟖ course ise BI100’ü (inst_id = NULL) getirir. Sağ dış birleştirme, tarafları değiştirilmiş sol dış birleştirmedir: R ⟖ S = S ⟕ R (sütun sırası hariç).

student ⟗ department (dept_name üzerinde):

Gizem solda eşsiz kaldı (NULL bölüm), BIO sağda eşsiz kaldı (öğrencisi yok). 6 + 1 + 1 = 8 satır.

TUZAK · SQL lehçeleri. Standart SQL’de FULL OUTER JOIN var. SQLite bunu 3.39 sürümünden beri destekliyor; daha eski SQLite ve MySQL desteklemez. O zaman sol dış birleştirmeyi, sağ taraftaki eşsiz satırlarla UNION yaparak taklit edersin. Bu sayfadaki sonuç iki yolla da doğrulandı.

Bölme: ÷

Bölme (division) şu soruyu cevaplar: “B’deki her değerle eşleşen A değerleri hangileri?” $R(A, B) \div S(B)$ sonucu, $S$‘deki her $b$ için $(a, b) \in R$ olan $a$‘lardır.

Örnek: bütün CS derslerini alan öğrenciler.

$\pi_{stu\_id,\, course\_id}(takes) \div \pi_{course\_id}(\sigma_{dept\_name = \text{'CS'}}(course))$

Bölen {CS101, CS201, CS305}. Sonuç: S1. Bora CS305’i, Ece CS201 ve CS305’i almadığı için elenir.

Temel operatörlerle türetme

Bölme temel değildir:

$R \div S = \pi_{A}(R) - \pi_{A}((\pi_{A}(R) \times S) - R)$

Fikir: herkes eksi “en az bir eksiği olanlar”. Adım adım ($T = \pi_{stu\_id, course\_id}(takes)$, $CS$ = CS dersleri):

1) π_stu_id(T)                   = {S1, S2, S3, S4, S5, S7}       aday öğrenciler
2) π_stu_id(T) × CS              = 6 · 3 = 18 satır               herkes her CS dersini alsaydı
3) (2) − T                       = 10 satır                        eksik kalan (öğrenci, ders) çiftleri
     S2-CS305  S3-CS201  S3-CS305  S4-CS101  S4-CS201
     S5-CS201  S5-CS305  S7-CS101  S7-CS201  S7-CS305
4) π_stu_id(3)                   = {S2, S3, S4, S5, S7}           eksiği olanlar
5) (1) − (4)                     = {S1}

Aynı sorguyu SQL’de çift NOT EXISTS ile yazarsın (“almadığı bir CS dersi bulunmayan öğrenci”). 7. haftada göreceksin.

TUZAK · bölünenin sütunları. $R$‘de sadece $A$ ve $B$ sütunları olmalı. $takes \div ...$ yazıp grade’i bırakırsan $A$ = (stu_id, grade) olur ve sorgu bambaşka bir şey sorar. Bölmeden önce mutlaka $\pi$ ile daralt.

Atama: ←

Uzun ifadeleri parçalamak için geçici ilişki tanımlarsın:

cs_courses ← π_course_id(σ_{dept_name='CS'}(course))
enrol      ← π_stu_id,course_id(takes)
result     ← enrol ÷ cs_courses

Atama (assignment) yeni güç eklemez; okunabilirlik kazandırır. Sınavda karmaşık sorularda kullanmak puan kaybettirmez, çoğu zaman hata yapmanı engeller.

Genelleştirilmiş izdüşüm

Genelleştirilmiş izdüşüm (generalized projection), π listesinde aritmetik ifadelere izin verir. MATH hocalarına %10 zam:

$\pi_{name,\; salary \cdot 1.1}(\sigma_{dept\_name = \text{'MATH'}}(instructor))$

Sonuç: Sahin 77000, Celik 79200.

Gruplama ve toplu fonksiyonlar: 𝒢

Toplu fonksiyonlar (aggregate functions) bir değer kümesinden tek değer üretir: count, sum, avg, min, max. Gruplama (grouping) işareti:

${}_{G_1, \dots, G_n}\mathcal{G}_{F_1(A_1), \dots}(E)$

Soldaki alt simge gruplama sütunları, sağdaki toplu fonksiyonlar. Bazı kaynaklar $\gamma$ harfini kullanır, anlamı aynı.

Bölüm başına ortalama maaş ve hoca sayısı:

${}_{dept\_name}\mathcal{G}_{\text{avg}(salary),\ \text{count}(inst\_id)}(instructor)$

Gruplama sütunu yazmazsan bütün tablo tek grup olur: $\mathcal{G}_{\text{sum}(salary),\ \text{max}(salary)}(instructor)$ = (462000, 95000).

Kurallar:

• Toplu fonksiyonlar NULL değerleri atlar. $\mathcal{G}_{\text{count}(dept\_name)}(student)$ = 6, tabloda 7 satır var.
• Grup sonucu üzerinde koşul (SQL’deki HAVING) için gruplamanın üstüne σ yazarsın. Bunun için toplu sonuca as ile ad ver: $\sigma_{avg\_sal > 75000}({}_{dept\_name}\mathcal{G}_{\text{avg}(salary) \text{ as } avg\_sal}(instructor))$ → CS, EE.
• Girdide hiç geçmeyen bir değer için grup oluşmaz.

Hangi soruya hangi operatör

Sık yapılan hatalar