Çizge Veritabanları

Önceki üç ailede sorgunun konusu kaydın kendisiydi: anahtar biliniyorsa değer gelir, bir alan üzerinde koşul varsa dizin kurulur, bir aralık isteniyorsa yerleşim ona göre seçilir. Kütüphane verisinde bazı sorular ise kayıtlarla değil, kayıtlar arasındaki bağlarla ilgilidir: bu kitabı ödünç alanların ayrıca aldığı kitaplar, iki üye arasındaki en kısa ortak okuma zinciri. İlişkisel modelde bu bağ bir birleştirme tablosudur ve her adım yeni bir birleştirmedir. Çizge veritabanı ise bağı birinci sınıf bir nesne yapar. Bu ders modeli node ile kurar, aynı sorunun iki modelde dokunduğu kayıt sayısını derinliğe göre ölçer ve derinliğin önceden bilinmediği bir soruda dolaşmanın bedelini sayar.

Bağın Kendisi Bir Kayıt

Model özellikli çizgedir (property graph): veri düğümlerden ve kenarlardan oluşur, her düğümün ve her kenarın kendi özellikleri vardır. Kütüphanede düğümler kitap ve üyedir; ödünç bir satır değil, bir kenardır ve ödüncün tarihi ile süresi o kenarın üstünde durur. Erişim yolu da farklıdır: bir düğümün komşuları o düğümün yanında tutulan bir listedir — komşuluk listesi (adjacency list). Bir düğümden komşularına yürümenin adı dolaşmadır (traversal); ağaç ve çizge veri yapılarında gezinme adıyla geçen kavramla aynı şeydir, bu kursta dolaşma biçimi kullanılır.

NS3: veri 20.000 üye, 5.000 kitap ve üye başına 2–12 ödünçten üretilir; kitap seçimi çarpık bir dağılımdan gelir, yani birkaç kitap çok, çoğu kitap az ödünç alınır. Üreteç kendi yazılır, tohum kodda görünür. NS4: ödünç kenarı yönsüzdür, iki yönde de aynı kenardan yürünür.

// cizge/model.mjs — ozellikli cizge: dugum ve kenar, her ikisinde ozellik. Komsuluk listesi
// gercek bir veri yapisidir; kenar ozelligi kenarin ustunde durur, ayri bir tabloda degil.
// Uretec disari acilir: sonraki bloklar ayni kumeyi kurar.
const TOHUM = 20240517, UYE = 20_000, KITAP = 5_000;
function* akis(t) { let x = t >>> 0; for (;;) { x = (Math.imul(x, 1103515245) + 12345) >>> 0; yield x / 4294967296; } }
export function oduncler() {                 // deterministik odunc listesi, tohum yukarida
  const r = akis(TOHUM), c = [];
  for (let u = 1; u <= UYE; u += 1) {
    const n = 2 + Math.floor(r.next().value * 11), gorulen = new Set();
    for (let j = 0; j < n; j += 1) {
      const p = r.next().value, k = 1 + Math.floor(KITAP * p * p);   // carpik populerlik
      if (gorulen.has(k)) continue; gorulen.add(k);
      c.push({ uye: u, kitap: k, gun: 1 + Math.floor(r.next().value * 364),
               sure: 3 + Math.floor(r.next().value * 40) });
    }
  }
  return c;
}

class OzellikliCizge {
  #dugum = new Map(); #komsu = new Map();
  dugum(id, ozellik) { this.#dugum.set(id, ozellik); this.#komsu.set(id, []); }
  kenar(a, b, ozellik) {                     // yonsuz: iki komsuluk listesine de yazilir
    this.#komsu.get(a).push({ hedef: b, ...ozellik });
    this.#komsu.get(b).push({ hedef: a, ...ozellik });
  }
  ozellik(id) { return this.#dugum.get(id); }
  komsular(id, sart) { const l = this.#komsu.get(id) ?? []; return sart ? l.filter(sart) : l; }
  derece(id) { return (this.#komsu.get(id) ?? []).length; }
}

if (import.meta.main) {                      // dogrudan calistirildiginda olcum basilir
  const g = new OzellikliCizge(), H = "kitap:2500", veri = oduncler();
  for (let k = 1; k <= KITAP; k += 1) g.dugum(`kitap:${k}`, { tur: "kitap", baslik: `Kitap ${k}`, yil: 1960 + (k % 65) });
  for (let u = 1; u <= UYE; u += 1) g.dugum(`uye:${u}`, { tur: "uye", ad: `Uye ${u}`, sube: 1 + (u % 9) });
  for (const o of veri) g.kenar(`uye:${o.uye}`, `kitap:${o.kitap}`, { tur: "odunc", gun: o.gun, sure: o.sure });

  let enYuksek = null, e = 0, toplam = 0;
  for (let k = 1; k <= KITAP; k += 1) { const d = g.derece(`kitap:${k}`); toplam += d;
    if (d > e) { e = d; enYuksek = `kitap:${k}`; } }
  console.log(`${KITAP + UYE} dugum (${KITAP} kitap + ${UYE} uye), ${veri.length} kenar (odunc)`);
  console.log(`ortalama derece: kitap ${(toplam / KITAP).toFixed(1)}, uye ${(veri.length / UYE).toFixed(1)}; ` +
    `en yuksek ${enYuksek} ${e}`);

  const hepsi = g.komsular(H), uzun = g.komsular(H, (k) => k.sure > 21);
  console.log(`\n${H} (${g.ozellik(H).baslik}, ${g.ozellik(H).yil}): komsuluk listesi ${hepsi.length} kenar, ` +
    `kenar ozelligiyle sure>21 olan ${uzun.length}`);
  console.log(`  ilk uc kenar: ${hepsi.slice(0, 3).map((k) => `${k.hedef}(gun ${k.gun}, sure ${k.sure})`).join(", ")}`);
}

25000 dugum (5000 kitap + 20000 uye), 139504 kenar (odunc)
ortalama derece: kitap 27.9, uye 7.0; en yuksek kitap:1 1825

kitap:2500 (Kitap 2500, 1990): komsuluk listesi 22 kenar, kenar ozelligiyle sure>21 olan 11
  ilk uc kenar: uye:202(gun 157, sure 19), uye:3845(gun 73, sure 25), uye:4394(gun 21, sure 11)

Sayılar ölçüm sınıfındadır. Kenar özelliği bir yan tabloda değil kenarın kendisindedir: süresi 21 günü aşan ödünçler, komşuluk listesi üzerinde tek süzgeçle 22 kenardan 11’ine iniyor — dolaşma sırasında kenar da bir koşul taşıyabilir. Derece dağılımı ise çarpıktır: kitap düğümünde ortalama derece 27,9 iken en yüksek derece 1.825’tir; bu sayı dersin sonunda geri gelecek.

Burada henüz bir üstünlük yoktur. Bir kitabın ödünç alanlarını bulmak çizgede 22 kenar okumaktır; ilişkisel modelde aynı iş, kitap_id üzerinde dizinli bir aramayla 22 satır okumaktır. Birinci derecede iki model aynı işi yapar. Fark ikinci adımda başlar.

Aynı Soru, İki Model

Soru şudur: bir kitabı ödünç alan üyelerin ayrıca aldığı kitaplar — ve aynı sorunun daha derin dereceleri. İlişkisel modelde bu, ödünç tablosunun kendisiyle art arda birleştirilmesidir ve her derece bir birleştirme daha ekler; çizgede aynı soru komşuluk listesinde bir adım daha yürümektir.

Ölçü iki tarafta da dokunulan ara kayıttır ve birikimlidir: birleştirmede her katmanın ürettiği satır, dolaşmada geçilen kenar. NS5: ilişkisel taraf kitap_id ve uye_id üzerinde dizinlidir; birleştirme tam tarama yapmaz, ölçülen fark dizin yokluğundan gelmez.

// cizge/iki-model.mjs — ayni soru iki modelde: iliskisel tarafta birlestirme tablosu
// (node:sqlite, iki dizinli), cizge tarafinda komsuluk listesinde dolasma. Dokunulan ara kayit
// iki tarafta da birikimli sayilir. Sayilarin hepsi kosumdan bagimsizdir.
import { DatabaseSync } from "node:sqlite";
import { oduncler } from "./model.mjs";      // ayni veri kumesi, ayni tohum
const H = 2500, veri = oduncler();

const db = new DatabaseSync(":memory:");
db.exec("CREATE TABLE odunc(uye_id INT, kitap_id INT, gun INT, sure INT)");
const ekle = db.prepare("INSERT INTO odunc VALUES(?,?,?,?)");
db.exec("BEGIN"); for (const o of veri) ekle.run(o.uye, o.kitap, o.gun, o.sure); db.exec("COMMIT");
db.exec("CREATE INDEX i_kitap ON odunc(kitap_id)"); db.exec("CREATE INDEX i_uye ON odunc(uye_id)");

function birlestirme(d) {                    // d katmanli birlestirme; COUNT(*) = d adimlik yol sayisi
  let sql = `SELECT COUNT(*) ara, COUNT(DISTINCT o${d}.${d % 2 ? "uye_id" : "kitap_id"}) tekil FROM odunc o1`;
  for (let i = 2; i <= d; i += 1)
    sql += i % 2 === 0 ? ` JOIN odunc o${i} ON o${i}.uye_id = o${i - 1}.uye_id`
                       : ` JOIN odunc o${i} ON o${i}.kitap_id = o${i - 1}.kitap_id`;
  return db.prepare(`${sql} WHERE o1.kitap_id = ?`).get(H);
}

const komsu = new Map();                     // komsuluk listesi: dugum -> komsu dizisi
const bagla = (a, b) => { if (!komsu.has(a)) komsu.set(a, []); komsu.get(a).push(b); };
for (const o of veri) { bagla(`k:${o.kitap}`, `u:${o.uye}`); bagla(`u:${o.uye}`, `k:${o.kitap}`); }

function dolasma(d) {                        // katman katman; her katman tekil dugum kumesidir
  let kat = new Set([`k:${H}`]), dugum = 0, kenar = 0;
  for (let i = 1; i <= d; i += 1) { const yeni = new Set();
    for (const v of kat) { dugum += 1; for (const w of komsu.get(v)) { kenar += 1; yeni.add(w); } }
    kat = yeni; }
  return { dugum, kenar, tekil: kat.size };
}

console.log(`${veri.length} odunc kaydi; baslangic kitap:${H}, derecesi ${komsu.get(`k:${H}`).length}\n`);
console.log("derinlik  birlestirme satiri   ziyaret edilen dugum   gecilen kenar   tekil sonuc");
let birikim = 0;
for (const d of [1, 2, 3, 4, 5]) {
  const b = birlestirme(d), c = dolasma(d); birikim += b.ara;
  if (b.tekil !== c.tekil) throw new Error(`sonuclar ayristi: ${b.tekil} != ${c.tekil}`);
  console.log(String(d).padStart(5) + String(birikim).padStart(19) + String(c.dugum).padStart(23) +
    String(c.kenar).padStart(16) + String(c.tekil).padStart(14));
}
let adim = new Set([H]), ara = 0;            // iliskisel tarafta adim adim tekillestirme
for (let i = 1; i <= 5; i += 1) {
  const alan = i % 2 ? "uye_id" : "kitap_id", giren = i % 2 ? "kitap_id" : "uye_id";
  const r = db.prepare(`SELECT ${alan} a FROM odunc WHERE ${giren} IN (${[...adim].map(() => "?").join(",")})`).all(...adim);
  ara += r.length; adim = new Set(r.map((x) => x.a));
}
console.log(`\nadim adim tekillestirilen birlestirme: ${ara} satir, ${adim.size} tekil sonuc, bes ayri ifade`);

139504 odunc kaydi; baslangic kitap:2500, derecesi 22

derinlik  birlestirme satiri   ziyaret edilen dugum   gecilen kenar   tekil sonuc
    1                 22                      1              22            22
    2                218                     23             218           166
    3              13200                    189           11219          8295
    4             122105                   8484           78082          4996
    5           14190839                  13480          217544         20000

adim adim tekillestirilen birlestirme: 217544 satir, 20000 tekil sonuc, bes ayri ifade

İki modelin sonucu her derinlikte birebir aynıdır; kod bunu her satırda sınıyor ve ayrışsaydı hata verirdi. Aynı olmayan şey maliyettir.

Birinci ve ikinci derecede iki taraf da aynı sayıya dokunuyor: 22 ve 218. Ayrışma üçüncü derecede başlıyor (13.200’e karşı 11.219), dördüncüde açılıyor (122.105’e karşı 78.082) ve beşincide bambaşka bir ölçeğe geçiyor: 14.190.839 satıra karşı 217.544 kenar, altmış beş kat. Nedeni tek cümledir: birleştirmenin bir katmanı yol sayar, dolaşmanın bir katmanı düğüm sayar. Bir kitaba yüz farklı yoldan varılıyorsa birleştirme o kitabın komşularını yüz kez üretir; dolaşma o kitabı katmanın kümesine bir kez koyar ve komşularına bir kez bakar. Sonuçtaki DISTINCT yalnızca en sonda temizlik yapar, ara satırları üretilmekten kurtarmaz.

Son satır sınırın nerede olduğunu söylüyor. İlişkisel motor bu işi dolaşma gibi de yapabilir: her adımda ara sonucu tekilleştirip bir sonrakine yalnız tekil kümeyi vermek 217.544 satır okuyor — dolaşmanın geçtiği kenar sayısıyla birebir aynı. Eksik olan veriyi tutma biçimi değil, sorgunun biçimidir: sorgu tek ifade olmaktan çıkıp beş ayrı ifadeye bölünür ve her yeni derece bir ifade daha ister. Çizge deposunun yaptığı tam olarak budur; farkı, sorguyu yazanın yapmamasıdır. Veri Katmanı Ölçekleme kursunda aynı karşıtlık istek sayısı üzerinden ölçülmüştü; buradaki ölçü dokunulan kayıttır.

Tablonun son sütunu ise dolaşmanın kendi sınırıdır: dördüncü derecede sonuç 4.996 kitap, beşincide 20.000 üye — neredeyse bütün katalog ve bütün üye kütüğü. Sorgu, pahalılaşmadan önce anlamını yitiriyor.

En Kısa Zincir

Bazı sorularda derinlik önceden bilinmez: iki üye arasındaki en kısa ortak okuma zinciri kaç adımdır? Bu soru sabit sayıda birleştirmeyle yazılamaz, çünkü kaç birleştirme yazılacağı cevabın kendisidir. Dolaşmanın iki biçimi vardır: tek uçtan yürümek ya da iki uçtan yürüyüp buluşmak.

// cizge/zincir.mjs — iki uye arasindaki en kisa ortak okuma zinciri: derinlik onceden
// bilinmez. Dolasma tek uctan ve iki uctan yurutulur, ziyaret edilen dugum sayilir.
import { oduncler } from "./model.mjs";      // ayni veri kumesi, ayni tohum

const komsu = new Map();
const bagla = (a, b) => { if (!komsu.has(a)) komsu.set(a, []); komsu.get(a).push(b); };
for (const o of oduncler()) { bagla(`k:${o.kitap}`, `u:${o.uye}`); bagla(`u:${o.uye}`, `k:${o.kitap}`); }

function tekUctan(a, b) {                    // en kisa yolda bir dugume ikinci kez ugranmaz
  const uzak = new Map([[a, 0]]); let kat = [a], dugum = 0, kenar = 0, enCok = [null, 0];
  const dur = () => ({ uzunluk: uzak.get(b), dugum, kenar, enCok });
  while (kat.length) { const yeni = [];
    for (const v of kat) { dugum += 1; const d = komsu.get(v).length;
      if (d > enCok[1]) enCok = [v, d];
      for (const w of komsu.get(v)) { kenar += 1;
        if (uzak.has(w)) continue; uzak.set(w, uzak.get(v) + 1);
        if (w === b) return dur(); yeni.push(w); } }
    kat = yeni; }
  return null;
}
function ikiUctan(a, b) {                    // her turda kucuk olan cephe genisletilir
  const uA = new Map([[a, 0]]), uB = new Map([[b, 0]]);
  let cA = [a], cB = [b], dugum = 0, kenar = 0;
  while (cA.length && cB.length) {
    const ileri = cA.length <= cB.length;
    const kat = ileri ? cA : cB, bu = ileri ? uA : uB, karsi = ileri ? uB : uA, yeni = [];
    for (const v of kat) { dugum += 1;
      for (const w of komsu.get(v)) { kenar += 1;
        if (bu.has(w)) continue; bu.set(w, bu.get(v) + 1);
        if (karsi.has(w)) return { uzunluk: bu.get(w) + karsi.get(w), dugum, kenar }; yeni.push(w); } }
    if (ileri) cA = yeni; else cB = yeni; }
  return null;
}

console.log(`${"uye cifti".padEnd(22)}${"zincir".padStart(7)}${"tek uctan dugum".padStart(17)}${"iki uctan dugum".padStart(17)}${"kazanc".padStart(8)}`);
for (const [a, b] of [[7, 19_842], [1_337, 15_004], [42, 9_999]]) {
  const t = tekUctan(`u:${a}`, `u:${b}`), i = ikiUctan(`u:${a}`, `u:${b}`);
  if (t.uzunluk !== i.uzunluk) throw new Error(`uzunluklar ayristi: ${t.uzunluk} != ${i.uzunluk}`);
  console.log(`uye:${a} — uye:${b}`.padEnd(22) + String(t.uzunluk).padStart(7) +
    String(t.dugum).padStart(17) + String(i.dugum).padStart(17) +
    `${(t.dugum / i.dugum).toFixed(1)}x`.padStart(8));
}

const t7 = tekUctan("u:7", "u:19842");       // aramada en cok kenar katan dugum
const [ad, derece] = t7.enCok;
console.log(`\nilk aramada en cok kenar katan dugum ${ad}, derecesi ${derece}: gecilen ` +
  `${t7.kenar} kenarin %${(100 * derece / t7.kenar).toFixed(1)}'i tek bu dugumden gecti`);

uye cifti              zincir  tek uctan dugum  iki uctan dugum  kazanc
uye:7 — uye:19842           4              426               11   38.7x
uye:1337 — uye:15004        2                8                2    4.0x
uye:42 — uye:9999           4              227                7   32.4x

ilk aramada en cok kenar katan dugum k:3, derecesi 611: gecilen 9477 kenarin %6.4'i tek bu dugumden gecti

İki yürüyüş de aynı uzunluğu buluyor ve kod bunu her çiftte sınıyor. Ziyaret edilen düğüm ise dört adımlık zincirlerde 426’ya karşı 11 ve 227’ye karşı 7 — otuz ila kırk kat. Neden yapısaldır: her katman bir öncekinden ortalama derece katı büyür, dolayısıyla maliyet son katmandadır. İki uçtan yürümek dört adımı iki artı iki yapar ve iki küçük katmanın toplamı bir büyük katmandan küçüktür. Zincir iki adım olduğunda kazanç 4,0 kata iniyor: bölünecek bir derinlik yoktur.

Son satır dolaşmanın kendi bedelini gösteriyor. Aramada en çok kenar katan düğüm 611 dereceli bir kitaptır ve geçilen 9.477 kenarın %6,4’ünü tek başına o üretmiştir. Derece dağılımının çarpıklığı burada maliyete dönüşüyor: bu ailede erişim ucuzdur, ama yüksek dereceli bir düğümden geçen her dolaşma o düğümün derecesi kadar iş yapar — katalogdaki en yüksek derece 1.825’tir ve bedeli o düğüme uğrandığı anda tek adımda ödenir. Çözüm modelin dışındadır: kenarın türüne ya da özelliğine göre süzmek, ya da o düğümü dolaşmaya hiç sokmamak.

Özet

• Özellikli çizgede veri düğüm ve kenardır, özellik her ikisinin üstünde durur ve komşuluk listesi düğümün yanında tutulan gerçek bir veri yapısıdır: ödüncün süresi kenarın özelliğidir ve 22 kenardan 21 günü aşan 11’i tek süzgeçle ayrılıyor.
• Birinci ve ikinci derecede iki model aynı sayıya dokunuyor (22 ve 218); ayrışma üçüncü derecede başlıyor (13.200’e karşı 11.219), dördüncüde 122.105’e karşı 78.082 oluyor ve beşincide 14.190.839 satıra karşı 217.544 kenara çıkıyor — altmış beş kat.
• Fark veriyi tutma biçiminden değil sorgu biçiminden gelir: birleştirmenin katmanı yol sayar, dolaşmanınki düğüm sayar. Aynı iş ilişkisel tarafta adım adım tekilleştirilirse 217.544 satıra iner, ama sorgu tek ifade olmaktan çıkıp beş ayrı ifade olur.
• Derinliği önceden bilinmeyen sorular sabit sayıda birleştirmeyle yazılamaz. En kısa zincirde iki uçtan dolaşma tek uçtandan 38,7 ve 32,4 kat az düğüm ziyaret ediyor; zincir kısaldığında kazanç 4,0 kata düşüyor.
• Dolaşmanın bedeli derece dağılımına bağlıdır: geçilen 9.477 kenarın %6,4’ü 611 dereceli tek bir düğümden geçiyor, katalogdaki en yüksek derece ise 1.825’tir.

Sonraki Adım

Dört ailenin dördü de bir şeyi paylaşıyor: verinin bir kimliği var — anahtar, belge kimliği, satır anahtarı, düğüm kimliği. Sorgu her durumda bir kimlikten başlıyor ya da bir kimliğe varıyor. Kütüphanenin işletme verisinde ise kimliği olmayan bir akış vardır: her dakika ölçülen raf sıcaklığı, saatlik kapı geçiş sayacı, ödünç işlemlerinin dakikalık sayımı. Tekil bir ölçüm tek başına sorulmaz; sorular aralıklar üzerinedir, veri yalnız eklenir ve hiç güncellenmez, eskiyen kısmı bir noktada tam çözünürlükte tutulmaz. Sonraki ders bu erişim örüntüsünün depoya ne yaptığını ölçüyor: zamana göre yerleşimin aralık sorgusunda okuduğu blok, sıralı ölçümlerin sıkıştırmada kazandırdığı yer, ve saklama politikasının hangi soruyu cevaplanamaz hâle getirdiği.