İlişkisel cebir: temel operatörler

İlişkisel cebir (relational algebra), ilişkiler (tablolar) üzerinde çalışan ve sonucu yine ilişki olan küçük bir operatör kümesidir. SQL’in arkasındaki matematik budur. Veritabanı motoru senin SQL sorgunu önce buna benzer bir ifadeye çevirir, sonra optimize eder. Sınavda iki tip soru çıkar: “Write a relational algebra expression for …” ve “Give the result of this expression”. İkisi için de bu sayfadaki altı temel operatörü bilmek yeter.

Altın kurallar:

1. σ satır, π sütun seçer. Karıştıran en kolay puanı kaybeder.
2. Her sonuç bir küme. Tekrar eden satır olmaz; π tekrarları siler.
3. ∪, −, ∩ sadece birleşim uyumlu (union-compatible) ilişkiler arasında yapılır.
4. × tek başına neredeyse hiç işe yaramaz. Arkasından bir σ ile eşleşme koşulu gelir.
5. İfadeyi içten dışa oku. En içteki parantez önce hesaplanır.

Örnek veritabanı

Bütün dönem aynı küçük üniversite veritabanını kullanıyoruz. Bu sayfada en çok şu tablolar lazım.

student

course

takes (S6 hiç ders almamış, S3’ün CS101 notu henüz yok)

instructor ve department

teaches(inst_id, course_id): (I1, CS101), (I1, CS305), (I2, CS201), (I3, EE210), (I4, MA101), (I5, MA202). I6 ders vermiyor, BI100’ü kimse vermiyor.

Seçme: σ

Seçme (selection) $\sigma_{p}(R)$, $R$‘nin $p$ koşulunu sağlayan satırlarını döndürür. Sütunlar aynen kalır. Koşulda karşılaştırma operatörleri ($=, \neq, <, \le, >, \ge$) ve mantıksal bağlaçlar ($\land$ ve, $\lor$ veya, $\lnot$ değil) kullanılır.

$\sigma_{dept\_name = \text{'CS'}}(student)$

İki koşul aynı satırı ilgilendiriyorsa tek seçmede birleşir: $\sigma_{dept\_name = \text{'CS'} \land tot\_cred > 20}(student)$ sonucu S1 (Ada) ve S2 (Bora).

Seçme sırası önemli değildir: $\sigma_{p}(\sigma_{q}(R)) = \sigma_{q}(\sigma_{p}(R)) = \sigma_{p \land q}(R)$.

İzdüşüm: π

İzdüşüm (projection) $\pi_{A_1, \dots, A_k}(R)$, sadece listelenen sütunları bırakır. İlişki bir küme olduğu için tekrar eden satırlar silinir.

$\pi_{dept\_name}(student)$

7 öğrenci var ama sonuç 4 satır. SQL’de SELECT dept_name FROM student 7 satır döndürür; ilişkisel cebirle aynı sonucu almak için SELECT DISTINCT yazman gerekir. SQL çoklu küme (multiset) semantiği kullanır, cebir küme semantiği.

TUZAK · π satır sayısını küçültebilir. “How many tuples?” sorusunda tabloyu sayıp geçme. İzdüşümden sonra aynı görünen satırları tek say.

Bileşim (composition)

Her operatörün sonucu bir ilişki olduğu için operatörler iç içe yazılır. 75000’den fazla kazanan hocaların adları:

$\pi_{name}(\sigma_{salary > 75000}(instructor)) = \{\text{Aksoy}, \text{Demir}, \text{Kaya}\}$

Sıra önemli: önce σ, sonra π. Tersini yazarsan ($\sigma_{salary > 75000}(\pi_{name}(instructor))$) ifade geçersiz olur, çünkü izdüşümden sonra salary sütunu artık yok.

Küme işlemleri: ∪, −, ∩

Üçü de iki ilişkinin birleşim uyumlu olmasını ister:

• aynı derece (arity), yani aynı sütun sayısı,
• $i$. sütunların alanları (domain) aynı.

Sütun adlarının aynı olması gerekmez, sonuç soldaki ilişkinin adlarını alır.

S1’in ve S4’ün aldığı derslerle çalışalım: $A = \pi_{course\_id}(\sigma_{stu\_id = \text{'S1'}}(takes))$ = {CS101, CS201, CS305, MA101}, $B = \pi_{course\_id}(\sigma_{stu\_id = \text{'S4'}}(takes))$ = {MA101, MA202, CS305}.

Fark değişmeli değildir: $A - B \neq B - A$. Kesişim temel operatör sayılmaz, çünkü farkla yazılabilir: $A \cap B = A - (A - B)$.

Fark ile “hiç” soruları. Hiçbir öğrencinin almadığı dersler:

$\pi_{course\_id}(course) - \pi_{course\_id}(takes) = \{\text{BI100}\}$

Öğrencisi ve hocası olan bölümler ise kesişimdir: $\pi_{dept\_name}(student) \cap \pi_{dept\_name}(instructor)$ = {CS, EE, MATH}. BIO’nun öğrencisi yok, NULL’un hocası yok.

Kartezyen çarpım: ×

$R \times S$, $R$‘nin her satırını $S$‘nin her satırıyla yan yana koyar. Satır sayısı $|R| \cdot |S|$, sütun sayısı derece toplamı. Aynı adlı sütunlar tablo adıyla ayrılır.

$instructor \times department$: $6 \cdot 4 = 24$ satır, $4 + 3 = 7$ sütun (instructor.dept_name ve department.dept_name ayrı).

Bu 24 satırın çoğu anlamsızdır: Aksoy’u BIO binasıyla eşleştirir. Anlamlı olanları seçmeyle tutarsın:

$\pi_{name,\, building}(\sigma_{instructor.dept\_name = department.dept\_name}(instructor \times department))$

24 satırdan 6’sı kaldı, her hocaya kendi bölümü. Bu “çarp, sonra eşitlikle seç” kalıbı birleştirmenin (join) tanımıdır. Haftaya ⋈ ile kısaltacağız.

TUZAK · eşleşme koşulunu unutmak. Çarpımdan sonra σ yazmazsan “her hoca her binada” gibi sahte satırlar sonuca girer. Çarpım gören her ifadede “tabloları hangi sütun bağlıyor?” diye sor.

Yeniden adlandırma: ρ

$\rho_{x}(E)$, $E$ ifadesinin sonucuna $x$ adını verir. $\rho_{x(A_1, \dots, A_n)}(E)$ sütunları da yeniden adlandırır. Asıl işi: bir tabloyu kendisiyle karşılaştırmak. İki kopyaya farklı ad vermeden $instructor \times instructor$ içinde hangi salary’nin hangi kopyadan geldiğini söyleyemezsin.

Örnek: en yüksek maaş (toplu fonksiyon kullanmadan). Fikir: en yüksek maaş, kendisinden daha yüksek bir maaş bulunmayan maaştır.

1) ρ_i(instructor) × ρ_j(instructor)          36 satır
2) σ_{i.salary < j.salary}(...)               i'den fazla kazanan bir j var
3) π_{i.salary}(...)                           = {80000, 85000, 70000, 72000, 60000}
4) π_salary(instructor) − (3)                  = {95000}

$\pi_{salary}(instructor) - \pi_{i.salary}(\sigma_{i.salary < j.salary}(\rho_{i}(instructor) \times \rho_{j}(instructor))) = \{95000\}$

Koşulu $>$ yaparsan aynı kalıp en düşük maaşı (60000) verir.

Temel ve türetilmiş operatörler

Altı temel (fundamental) operatör: $\sigma, \pi, \cup, -, \times, \rho$. Bunlarla her ilişkisel cebir sorgusu yazılabilir. $\cap$, birleştirmeler ve bölme bu altısından türetilir; sadece kısaltmadır.

Sorgu ağacı (query tree)

Bir ifade ağaç olarak çizilir: yapraklar tablolar, iç düğümler operatörler, kök sonuç. Hocaların bina sorgusu için:

              π name, building
                    |
   σ instructor.dept_name = department.dept_name
                    |
                    ×
                  /   \
         instructor   department

Ağaç aşağıdan yukarı hesaplanır. Optimizasyon haftasında (13. hafta) aynı sorgunun farklı ağaçlarını karşılaştırıp σ’yı çarpımın altına itmenin neden ucuz olduğunu göreceğiz.

Soru çözme yöntemi

“Write the relational algebra” sorusunda şu sırayı izle:

1. Hangi tablolar lazım? Birden fazlaysa çarp ve bağlayan sütunları eşitle.
2. Satır koşullarını σ’ya yaz.
3. İstenen sütunları en dışta π ile al.
4. Soruda “both / every / never / only” varsa küme işlemine ihtiyaç var: “both” → ∩, “never” → fark.

Örnek: kendi bölümü dışından ders alan öğrencilerin adları. Üç tablo lazım, iki eşleşme koşulu ve bir farklılık koşulu:

$\pi_{s.name}(\sigma_{s.stu\_id = t.stu\_id \land t.course\_id = c.course\_id \land s.dept\_name \neq c.dept\_name}(\rho_{s}(student) \times \rho_{t}(takes) \times \rho_{c}(course)))$

Çarpım $7 \cdot 14 \cdot 7 = 686$ satır, seçmeden sonra Ada, Cem ve Defne kalır. Gizem’in bölümü NULL olduğu için $\neq$ karşılaştırması doğru çıkmaz, satır elenir.

Sık yapılan hatalar