Özyinelemeli Sorgular

Önceki ders, ortak tablo ifadesinin yalnız kendinden önce tanımlananlara başvurabildiğini söyledi ve tek istisnayı belirtti: bir ifade kendine başvurabilir. Bu istisna, SQL’in ifade gücünü niteliksel olarak büyütür.

Şubelerin ağaç biçiminde örgütlendiği bir kütüphane düşünülsün: her şubenin bir üst şubesi vardır, kökte merkez durur. “Merkezin altındaki tüm şubeler” sorusu, ağacın derinliği bilinmeden yazılamaz — üç seviye için üç birleştirme, dört seviye için dört birleştirme gerekir. Oysa derinlik veriye bağlıdır ve zamanla değişir. Sabit sayıda birleştirmeyle ifade edilemeyen bu tür hesaplar özyinelemeli ortak tablo ifadesiyle yazılır.

İki Adımlı Yapı

Özyinelemeli ifade WITH RECURSIVE ile başlar ve gövdesi UNION ALL ile ayrılmış iki parçadan oluşur:

• Taban adımı: ifadeye başvurmayan sorgu. Başlangıç satırlarını üretir.
• Özyineleme adımı: ifadenin kendisine başvuran sorgu. Bir önceki turda üretilen satırlardan yenilerini türetir.

Değerlendirme şöyle ilerler: taban adımı çalıştırılır ve sonucu bir çalışma kümesine konur. Sonra özyineleme adımı, yalnız son turda eklenen satırlar üzerinde çalıştırılır; ürettiği satırlar sonuca eklenir ve bir sonraki turun girdisi olur. Yeni satır üretilmeyen turda işlem durur. Bu, Veri Yapıları kursundaki enine aramanın sorgu dilindeki karşılığıdır: seviye seviye ilerlenir.

Şube ağacında kökten aşağı inmek, derinlik ve yol hesaplamak bu yapıyla yazılır:

sqlite3 -box -header <<'SQL'
CREATE TABLE sube(id INTEGER PRIMARY KEY, ad TEXT NOT NULL, ust_id INT REFERENCES sube(id));
INSERT INTO sube VALUES (1,'Merkez',NULL),(2,'Anadolu',1),(3,'Avrupa',1),
  (4,'Kadikoy',2),(5,'Uskudar',2),(6,'Besiktas',3),(7,'Moda',4),(8,'Bostanci',4);

WITH RECURSIVE agac(id, ad, derinlik, yol) AS (
  SELECT id, ad, 0, ad FROM sube WHERE ust_id IS NULL
  UNION ALL
  SELECT s.id, s.ad, a.derinlik + 1, a.yol || ' > ' || s.ad
  FROM sube s JOIN agac a ON s.ust_id = a.id
)
SELECT derinlik, ad, yol FROM agac ORDER BY yol;
SQL

┌──────────┬──────────┬───────────────────────────────────────┐
│ derinlik │    ad    │                  yol                  │
├──────────┼──────────┼───────────────────────────────────────┤
│ 0        │ Merkez   │ Merkez                                │
│ 1        │ Anadolu  │ Merkez > Anadolu                      │
│ 2        │ Kadikoy  │ Merkez > Anadolu > Kadikoy            │
│ 3        │ Bostanci │ Merkez > Anadolu > Kadikoy > Bostanci │
│ 3        │ Moda     │ Merkez > Anadolu > Kadikoy > Moda     │
│ 2        │ Uskudar  │ Merkez > Anadolu > Uskudar            │
│ 1        │ Avrupa   │ Merkez > Avrupa                       │
│ 2        │ Besiktas │ Merkez > Avrupa > Besiktas            │
└──────────┴──────────┴───────────────────────────────────────┘

Taban adımı kökü seçer: üst şubesi olmayan satır, derinlik sıfır. Özyineleme adımı, o ana kadar bulunmuş her düğüm için çocuklarını bulur, derinliği bir artırır ve yol dizgisini uzatır. Derinlik ve yol, tabloda bulunmayan ama gezinme sırasında biriken değerlerdir; özyinelemeli ifadenin asıl gücü budur.

Sıralama ORDER BY yol ile yapıldığı için çıktı ağaç düzeninde okunur: her düğümün hemen altında kendi alt ağacı gelir. Derinlik sütunu artıp azalarak ilerler, çünkü sıralama ölçütü derinlik değil yoldur.

Yukarı Gezinme

Aynı yapı ters yönde de kurulur. Birleştirme koşulunun yönü değiştirilirse bir düğümden köke doğru yürünür; bu, “bu şube hangi bölgeye bağlı” sorusunun yanıtıdır:

sqlite3 -box -header <<'SQL'
CREATE TABLE sube(id INTEGER PRIMARY KEY, ad TEXT NOT NULL, ust_id INT REFERENCES sube(id));
INSERT INTO sube VALUES (1,'Merkez',NULL),(2,'Anadolu',1),(3,'Avrupa',1),
  (4,'Kadikoy',2),(5,'Uskudar',2),(6,'Besiktas',3),(7,'Moda',4),(8,'Bostanci',4);

WITH RECURSIVE ust_zincir(id, ad, ust_id, adim) AS (
  SELECT id, ad, ust_id, 0 FROM sube WHERE ad = 'Moda'
  UNION ALL
  SELECT s.id, s.ad, s.ust_id, z.adim + 1
  FROM sube s JOIN ust_zincir z ON s.id = z.ust_id
)
SELECT adim, ad FROM ust_zincir ORDER BY adim;
SQL

┌──────┬─────────┐
│ adim │   ad    │
├──────┼─────────┤
│ 0    │ Moda    │
│ 1    │ Kadikoy │
│ 2    │ Anadolu │
│ 3    │ Merkez  │
└──────┴─────────┘

Tek fark birleştirme koşulundadır: aşağı inerken s.ust_id = a.id, yukarı çıkarken s.id = z.ust_id yazılır. Zincir kökte durur, çünkü kökün üst şubesi boş değerdir ve hiçbir satırla eşleşmez.

Alt Ağaç Üzerinde Toplama

Özyinelemeli ifadenin sonucu bir tablodur; başka tablolarla birleştirilebilir, gruplanabilir. “Her şubenin kendi alt ağacındaki toplam ödünç sayısı” sorusu, önce her düğüm için alt ağacındaki düğümleri üretip sonra bu eşleştirme üzerinden toplayarak yanıtlanır:

sqlite3 -box -header <<'SQL'
CREATE TABLE sube(id INTEGER PRIMARY KEY, ad TEXT NOT NULL, ust_id INT REFERENCES sube(id));
INSERT INTO sube VALUES (1,'Merkez',NULL),(2,'Anadolu',1),(3,'Avrupa',1),
  (4,'Kadikoy',2),(5,'Uskudar',2),(6,'Besiktas',3),(7,'Moda',4),(8,'Bostanci',4);
CREATE TABLE uye(id INTEGER PRIMARY KEY, ad TEXT, sube_id INT);
CREATE TABLE odunc(id INTEGER PRIMARY KEY, kitap_id INT, uye_id INT, alis TEXT, iade TEXT);
INSERT INTO uye VALUES (1,'Ayse',7),(2,'Burak',8),(3,'Ceren',5),(4,'Deniz',5),
                       (5,'Emre',6),(6,'Fatma',6),(7,'Gokhan',7),(8,'Hale',5);
INSERT INTO odunc VALUES
  (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'),
  (3,5,1,'2024-03-04','2024-03-18'),(4,7,1,'2024-03-11',NULL),
  (5,9,1,'2024-03-18','2024-03-29'),(6,2,2,'2024-03-01','2024-03-12'),
  (7,4,2,'2024-03-06','2024-03-25'),(8,6,2,'2024-03-11','2024-03-19'),
  (9,8,2,'2024-03-21',NULL),(10,1,3,'2024-03-04','2024-03-10'),
  (11,3,3,'2024-03-06','2024-03-27'),(12,10,3,'2024-03-13','2024-03-22'),
  (13,2,3,'2024-03-25',NULL),(14,5,4,'2024-03-04','2024-03-09'),
  (15,7,4,'2024-03-13','2024-03-26'),(16,4,4,'2024-03-20',NULL),
  (17,6,5,'2024-03-06','2024-03-14'),(18,9,5,'2024-03-11','2024-03-23'),
  (19,1,5,'2024-03-25','2024-03-28'),(20,8,6,'2024-03-04','2024-03-17'),
  (21,10,6,'2024-03-13','2024-03-21'),(22,3,6,'2024-03-20',NULL),
  (23,2,7,'2024-03-11','2024-03-16'),(24,5,7,'2024-03-18','2024-03-24'),
  (25,4,8,'2024-03-13','2024-03-24');

WITH RECURSIVE altagac(kok_id, id) AS (
  SELECT id, id FROM sube
  UNION ALL
  SELECT a.kok_id, s.id FROM sube s JOIN altagac a ON s.ust_id = a.id
)
SELECT k.ad AS sube, COUNT(o.id) AS altagac_toplami
FROM altagac a
JOIN sube k ON k.id = a.kok_id
LEFT JOIN uye u ON u.sube_id = a.id
LEFT JOIN odunc o ON o.uye_id = u.id
GROUP BY a.kok_id, k.ad
ORDER BY altagac_toplami DESC, k.ad;
SQL

┌──────────┬─────────────────┐
│   sube   │ altagac_toplami │
├──────────┼─────────────────┤
│ Merkez   │ 25              │
│ Anadolu  │ 19              │
│ Kadikoy  │ 11              │
│ Uskudar  │ 8               │
│ Moda     │ 7               │
│ Avrupa   │ 6               │
│ Besiktas │ 6               │
│ Bostanci │ 4               │
└──────────┴─────────────────┘

Taban adımı burada tek bir kök değil, her şubeyi kendi alt ağacının kökü olarak alır. Sonuç, “hangi düğüm hangi alt ağaca ait” eşleştirmesidir. Sayılar iç tutarlıdır: Kadıköy’ün 11 işlemi, Moda’nın 7’si ile Bostancı’nın 4’ünün toplamıdır; Anadolu’nun 19’u, Kadıköy’ün 11’i ile Üsküdar’ın 8’inin toplamıdır. Kökteki 25, tablodaki tüm işlemlerdir.

Döngü Koruması Olmadan

Şube ağacının gerçekten ağaç olduğu, verinin doğruluğuna bağlıdır. Bir güncelleme yanlışlıkla bir üst şubeyi kendi alt şubesine bağlarsa yapı çevrimli bir çizgeye dönüşür ve özyineleme durmaz: her tur aynı düğümleri yeniden üretir.

Aşağıdaki blok bu durumu bilerek üretir — Anadolu, kendi torunu olan Moda’ya bağlanır. Sorgunun sonsuza kadar çalışmaması için özyineleme adımına bir derinlik sınırı konur; sınır, döngüyü çözmez, yalnızca sonucu görülebilir kılar:

sqlite3 -box -header <<'SQL'
CREATE TABLE sube(id INTEGER PRIMARY KEY, ad TEXT NOT NULL, ust_id INT REFERENCES sube(id));
INSERT INTO sube VALUES (1,'Merkez',NULL),(2,'Anadolu',1),(3,'Avrupa',1),
  (4,'Kadikoy',2),(5,'Uskudar',2),(6,'Besiktas',3),(7,'Moda',4),(8,'Bostanci',4);
UPDATE sube SET ust_id = 7 WHERE id = 2;

WITH RECURSIVE agac(id, ad, derinlik) AS (
  SELECT id, ad, 0 FROM sube WHERE id = 4
  UNION ALL
  SELECT s.id, s.ad, a.derinlik + 1
  FROM sube s JOIN agac a ON s.ust_id = a.id
  WHERE a.derinlik < 7
)
SELECT derinlik, id, ad FROM agac ORDER BY derinlik, id;
SQL

┌──────────┬────┬──────────┐
│ derinlik │ id │    ad    │
├──────────┼────┼──────────┤
│ 0        │ 4  │ Kadikoy  │
│ 1        │ 7  │ Moda     │
│ 1        │ 8  │ Bostanci │
│ 2        │ 2  │ Anadolu  │
│ 3        │ 4  │ Kadikoy  │
│ 3        │ 5  │ Uskudar  │
│ 4        │ 7  │ Moda     │
│ 4        │ 8  │ Bostanci │
│ 5        │ 2  │ Anadolu  │
│ 6        │ 4  │ Kadikoy  │
│ 6        │ 5  │ Uskudar  │
│ 7        │ 7  │ Moda     │
│ 7        │ 8  │ Bostanci │
└──────────┴────┴──────────┘

Kadıköy üçüncü ve altıncı derinlikte, Moda birinci, dördüncü ve yedinci derinlikte yeniden görünüyor. Örüntü üç adımda bir tekrar ediyor: 4 → 7 → 2 → 4. Sınır kaldırılsaydı sorgu durmayacak, bellek ya da geçici disk alanı tükenene kadar satır üretecekti.

Doğru çözüm, gezilen düğümleri takip edip yeniden ziyareti engellemektir. İzlenen yol bir dizgide biriktirilir ve özyineleme adımı, yolda zaten geçmiş bir düğümü ikinci kez almayı reddeder:

sqlite3 -box -header <<'SQL'
CREATE TABLE sube(id INTEGER PRIMARY KEY, ad TEXT NOT NULL, ust_id INT REFERENCES sube(id));
INSERT INTO sube VALUES (1,'Merkez',NULL),(2,'Anadolu',1),(3,'Avrupa',1),
  (4,'Kadikoy',2),(5,'Uskudar',2),(6,'Besiktas',3),(7,'Moda',4),(8,'Bostanci',4);
UPDATE sube SET ust_id = 7 WHERE id = 2;

WITH RECURSIVE agac(id, ad, derinlik, yol) AS (
  SELECT id, ad, 0, '/' || id || '/' FROM sube WHERE id = 4
  UNION ALL
  SELECT s.id, s.ad, a.derinlik + 1, a.yol || s.id || '/'
  FROM sube s JOIN agac a ON s.ust_id = a.id
  WHERE a.yol NOT LIKE '%/' || s.id || '/%'
)
SELECT derinlik, id, ad, yol FROM agac ORDER BY derinlik, id;
SQL

┌──────────┬────┬──────────┬───────────┐
│ derinlik │ id │    ad    │    yol    │
├──────────┼────┼──────────┼───────────┤
│ 0        │ 4  │ Kadikoy  │ /4/       │
│ 1        │ 7  │ Moda     │ /4/7/     │
│ 1        │ 8  │ Bostanci │ /4/8/     │
│ 2        │ 2  │ Anadolu  │ /4/7/2/   │
│ 3        │ 5  │ Uskudar  │ /4/7/2/5/ │
└──────────┴────┴──────────┴───────────┘

Sorgu beş satırda durdu. Kadıköy’e ikinci kez ulaşılabilecek olan /4/7/2/4/ adımı, yolda /4/ zaten geçtiği için elendi. Kimlikler eğik çizgi arasına alınarak yazılıyor; böylece /4/ örüntüsü /14/ ya da /41/ ile karışmaz.

Bu koruma her düğümü yol başına bir kez ziyaret eder; genel bir çizgede aynı düğüme farklı yollardan ulaşılabildiği için satır sayısı yine büyüyebilir. Her düğümü tümüyle bir kez ziyaret etmek gerekiyorsa UNION ALL yerine yinelenenleri eleyen UNION kullanılır; bunun bedeli, her turda tekillik denetimidir.

Hiyerarşi Dışında

Özyinelemeli ifadenin taban adımı bir tablodan gelmek zorunda değildir. Sabit bir satırdan başlayıp bir kural uygulayarak dizi üretilebilir. Bunun tipik kullanımı, verinin olmadığı günleri raporda sıfırla göstermektir:

sqlite3 -box -header <<'SQL'
CREATE TABLE odunc(id INTEGER PRIMARY KEY, kitap_id INT, uye_id INT, alis TEXT, iade TEXT);
INSERT INTO odunc VALUES
  (1,1,1,'2024-03-01','2024-03-15'),(2,3,1,'2024-03-01','2024-03-20'),
  (3,5,1,'2024-03-04','2024-03-18'),(6,2,2,'2024-03-01','2024-03-12'),
  (10,1,3,'2024-03-04','2024-03-10'),(14,5,4,'2024-03-04','2024-03-09');

WITH RECURSIVE gun(tarih) AS (
  SELECT '2024-03-01'
  UNION ALL
  SELECT date(tarih, '+1 day') FROM gun WHERE tarih < '2024-03-06'
)
SELECT g.tarih, COUNT(o.id) AS islem
FROM gun g LEFT JOIN odunc o ON o.alis = g.tarih
GROUP BY g.tarih ORDER BY g.tarih;
SQL

┌────────────┬───────┐
│   tarih    │ islem │
├────────────┼───────┤
│ 2024-03-01 │ 3     │
│ 2024-03-02 │ 0     │
│ 2024-03-03 │ 0     │
│ 2024-03-04 │ 3     │
│ 2024-03-05 │ 0     │
│ 2024-03-06 │ 0     │
└────────────┴───────┘

Yalnız odunc tablosu gruplansaydı 2 ve 3 Mart satırları hiç görünmezdi; boş günler raporda kaybolurdu. Üretilen takvim, sol dış birleştirmenin sol tarafını oluşturarak eksik günleri sıfırla doldurur. Tarih işlevlerinin adı motora göre değişir; değişmeyen, taban adımı ile durma koşulundan oluşan yapıdır.

Durma koşulunun özyineleme adımının içinde olması zorunludur. Koşul dışarıdaki WHERE yan tümcesine yazılırsa üretim durmaz; dış süzgeç yalnızca üretilmiş satırları eler. Bu, özyinelemeli sorgu yazarken en sık yapılan hatadır.

Özet

• Özyinelemeli ortak tablo ifadesi, taban adımı ile kendine başvuran özyineleme adımının UNION ALL ile birleşmesinden oluşur; yeni satır üretilmeyen turda durur.
• Derinlik, yol ve sıra numarası gibi değerler tabloda bulunmaz, gezinme sırasında birikir.
• Birleştirme koşulunun yönü değiştirilerek aynı yapı hem alt ağacı hem üst zinciri gezer.
• Veride çevrim varsa özyineleme durmaz; ziyaret edilen düğümleri yolda biriktirip yinelenen adımı elemek, sorguyu sonlandıran korumadır.
• Taban adımı sabit bir satır olabilir; bu, raporlarda eksik günleri dolduran takvim üretiminin standart yoludur.

Sonraki Adım

Bu dersteki hesapların ortak yanı, sonucun satır kümesini değiştirmesiydi: gezinme yeni satırlar üretti, gruplama satırları teke indirdi. Bazı sorularda ise satırlar korunmalı, her satırın yanına komşularına bakan bir değer eklenmelidir — bir üyenin işleminin yanında o üyenin o güne kadarki toplamı gibi. Gruplama bunu yapamaz, çünkü gruplama satırları yutar. Sonraki ders, satırları koruyarak komşu satırlar üzerinde hesap yapan pencere işlevlerini tanıtacak ve çerçeve tanımının aynı sorguda sonucu nasıl değiştirdiğini gösterecek.