Fizikai terv + Költségvetés reinvent

Optimális logikai terv

• RelAlg kifejezés
• műveletekből áll
• Ha minden műveletnek ismerjük a költségét, akkor a fa költsége is kiszámolható

Műveletek

• Kiválasztás: \(\sigma\)
  • szekvenciális, index, rendezés
• Vetítés: \(\Pi\)
• Unió: \(\cup\)
• Különbség: \(-\)
• (Descartes) Szorzat: \(\times\)
• Átnevezés \(\rho\)
  • Nem vesszük figyelembe, mert nincs költsége
• Összekapcsolás: \(\Join\)
  • Származtatott, de fontos/gyakori

Kiértékelés meghatározása

• Több lehetőség van egy művelet végrehajtására
  • \(\sigma_{\text{name=Paul}}(\text{student})\)
    • Fájl szekvenciális keresés
    • Másodlagos index a student.name mezőn
• Több elérési útvonal
  • Elérési útvonal: amivel a rekordot elérni
    • pl.: indexek

Költségbecslés

Ahol \(\blue{K_n}\) számítási költség

és \(\green{O_n}\) outputméret adott \(n\) műveletre

• Mit kell számításba venni
  • Lemez I/O
    • Szekvenciális
    • Indexelt kezelés
  • CPU idő
    • (elhanyagolható)
  • Hálózati kommunikáció
    • Csak osztott adatbázisok esetén
• Mit fog ea figyelembe venni:
  • Lemez I/O
    • Lapok (blokkok) olvasása, írása
  • Elhanyagoljuk a végeredemény kiírási költségeit
    • \(\blue{K_1+K_2+\cdots+K_n}\) elég lesz ide

Költségek

\(N_R\)

• R rekordjainak száma

korábban T(R)

\(L_R\)

-R egy rekordjának mérete

korábban L(R)

\(F_R\)

• Blokkolási tényező
• Egy lapon, blokkokban levő rekordok száma

Korábban bf(R)

\(B_R\)

• R reláció tárolásához szükséges lapok, blokkok száma

\(V(A,R)\)

• Az A mező különböző értékeinek száma R-ben
• Képméret

Korábban \(I_{R.A}\)

\(SC(A,R)\)

• Az A mező kiválasztási számossága R-ben
• Szelektivitás
  • Hány darab A=a értékű rekord van
    • Egyenletességgel számolva oc
• Ha A kulcs:
  • \(SC(A,R) = 1\)
• Ha A nem kulcs:
  • \(SC(A, R) = \dfrac{N_R}{V(A,R)}\)

\(HT_i\)

• Az i index szintjeinek száma
• A törteket és logaritmusokat felfelé kerekítjük