Sadrˇ

zaj

UVOD U BAZE PODATAKA

1.1

Osnovni pojmovi vezani uz baze podataka . . . . . . . . . . . . . . . . . . . . . . . . . .

1.1.1

Baza podataka, DBMS, model podataka . . . . . . . . . . . . . . . . . . . . . . .

1.1.2

Ciljevi koji se nastoje posti´

ci koriˇ

stenjem baza podataka . . . . . . . . . . . . . .

1.1.3

Arhitektura baze podataka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.1.4

Jezici za rad s bazama podataka . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.1.5

Poznati softverski paketi za rad s bazama podataka

. . . . . . . . . . . . . . . .

1.2

Zivotni ciklus baze podataka

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.1

Analiza potreba

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.2

Modeliranje podataka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.3

Implementacija . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.4

Testiranje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2.5

Odrˇ

zavanje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

MODELIRANJE PODATAKA

2.1

Modeliranje entiteta i veza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.1

Entiteti i atributi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.2

Veze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.3

Prikaz ER-sheme pomo´

cu dijagrama . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.4

Sloˇ

zenije veze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2

Relacijski model

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.1

Relacija, atribut, n-torka, kljuˇ

c . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.2

Pretvaranje ER-sheme u relacijsku . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.3

Usporedba relacijskog modela s mreˇ

znim i hijerarhijskim . . . . . . . . . . . . . .

2.3

Normalizacija relacijske sheme

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.1

Funkcionalna ovisnost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.2

Druga normalna forma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.3

Tre´

ca normalna forma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.4

Boyce-Codd-ova normalna forma . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3.5

Viˇ

seznaˇ

cna ovisnost i ˇ

cetvrta normalna forma . . . . . . . . . . . . . . . . . . . .

2.3.6

Razlozi zbog kojih se moˇ

ze odustati od normalizacije . . . . . . . . . . . . . . . .

JEZICI ZA RELACIJSKE BAZE PODATAKA

3.1

Relacijska algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.1

Skupovni operatori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.2

Selekcija . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.3

Projekcija . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.4

Kartezijev produkt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.5

Prirodni spoj . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.6

Theta-spoj

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.7

Dijeljenje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1.8

Vanjski spoj . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2

Relacijski raˇ

cun . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2.1

Raˇ

cun orijentiran na n-torke

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2.2

Raˇ

cun orijentiran na domene . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

SADR ˇ

ZAJ

3.3

Jezik SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.1

Postavljanje upita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.2

Aˇ

zuriranje relacija . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4

Optimizacija upita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4.1

Odnos izmedu relacijske algebre i raˇ

cuna . . . . . . . . . . . . . . . . . . . . . . .

3.4.2

Osnovna pravila za optimizaciju

. . . . . . . . . . . . . . . . . . . . . . . . . . .

FIZI ˇ

CKA GRADA BAZE PODATAKA

4.1

Elementi fiziˇ

cke grade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.1.1

Vanjska memorija raˇ

cunala . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.1.2

Datoteke

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.1.3

Smjeˇ

staj datoteke u vanjskoj memoriji . . . . . . . . . . . . . . . . . . . . . . . .

4.1.4

Pointeri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.1.5

Fiziˇ

cka grada cijele baze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2

Pristup na osnovu primarnog kljuˇ

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2.1

Jednostavna datoteka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2.2

Hash datoteka

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2.3

Datoteka s indeksom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2.4

B-stablo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3

Pristup na osnovu drugih podataka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3.1

Invertirana datoteka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3.2

Viˇ

sestruke vezane liste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3.3

Podijeljena hash funkcija

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

IMPLEMENTACIJA RELACIJSKIH OPERACIJA

5.1

Implementacija prirodnog spoja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.1.1

Algoritam ugnijeˇ

zdenih petlji . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.1.2

Algoritam zasnovan na sortiranju i saˇ

zimanju . . . . . . . . . . . . . . . . . . . .

5.1.3

Algoritam zasnovan na indeksu . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.1.4

Algoritam zasnovan na hash funkciji i razvrstavanju . . . . . . . . . . . . . . . .

5.2

Implementacija selekcije, projekcije i ostalih operacija

. . . . . . . . . . . . . . . . . . .

5.2.1

Implementacija selecije . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.2.2

Implementacija projekcije . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.2.3

Implementacija ostalih operacija. . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.3

Optimalno izvrednjavanje algebarskog izraza

. . . . . . . . . . . . . . . . . . . . . . . .

INTEGRITET I SIGURNOST PODATAKA

6.1

Cuvanje integriteta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.1.1

Ograniˇ

cenja kojima se ˇ

cuva integritet domene . . . . . . . . . . . . . . . . . . . .

6.1.2

Ograniˇ

cenja kojima se ˇ

cuva integritet unutar relacije . . . . . . . . . . . . . . . .

6.1.3

Ograniˇ

cenja kojima se ˇ

cuva referencijalni integritet . . . . . . . . . . . . . . . . .

6.2

Istovremeni pristup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.2.1

Transakcije i serijalizabilnost . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.2.2

Lokoti i zakljuˇ

cavanje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.2.3

Dvofazni protokol zakljuˇ

cavanja . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.2.4

Vremenski ˇ

zigovi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.3

Oporavak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.3.1

Rezervna kopija baze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.3.2

Zurnal datoteka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.3.3

Neutralizacija jedne transakcije . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.3.4

Ponovno uspostavljanje baze

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.4

Zaˇ

stita od neovlaˇ

stenog pristupa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.4.1

Identifikacija korisnika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.4.2

Pogledi kao mehanizam zaˇ

stite . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.4.3

Ovlaˇ

stenja

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1. UVOD U BAZE PODATAKA

1.1.2

Ciljevi koji se nastoje posti´

ci koriˇ

stenjem baza podataka

Spomenuli smo da baze podataka predstavljaju viˇ

su razinu rada s podacima u odnosu na klasiˇ

cne

programske jezike. Ta viˇ

sa razina rada oˇ

cituje se u tome ˇ

sto tehnologija baza podataka nastoji (i u

velikoj mjeri uspijeva) ispuniti sljede´

ce ciljeve.

Fiziˇ

cka nezavisnost podataka.

Razdvaja se logiˇ

cka definicija baze od njene stvarne fiziˇ

cke grade.

Znaˇ

ci, ako se fiziˇ

cka grada promijeni (na primjer, podaci se prepiˇ

su u druge datoteke na drugim

diskovima), to ne´

ce zahtijevati promjene u postoje´

cim aplikacijama.

Logiˇ

cka nezavisnost podataka.

Razdvaja se globalna logiˇ

cka definicija cijele baze podataka od

lokalne logiˇ

cke definicije za jednu aplikaciju. Znaˇ

ci, ako se logiˇ

cka definicija promijeni (na primjer

uvede se novi zapis ili veza), to ne´

ce zahtijevati promjene u postoje´

cim aplikacijama. Lokalna

logiˇ

cka definicija obiˇ

cno se svodi na izdvajanje samo nekih elemenata iz globalne definicije, uz

neke jednostavne transformacije tih elemenata.

Fleksibilnost pristupa podacima.

U starijim mreˇ

znim i hijerarhijskim bazama, staze pristupanja

podacima bile su unaprijed definirane, dakle korisnik je mogao pretraˇ

zivati podatke jedino onim

redoslijedom koji je bio predviden u vrijeme projektiranja i implementiranja baze. Danas se
zahtijeva da korisnik moˇ

ze slobodno prebirati po podacima, te po svom nahodenju uspostavljati

veze medu podacima. Ovom zahtjevu zaista zadovoljavaju jedino relacijske baze.

Istovremeni pristup do podataka.

Baza mora omogu´

citi da ve´

ci broj korisnika istovremeno koristi

iste podatke. Pritom ti korisnici ne smiju ometati jedan drugoga, te svaki od njih treba imati
dojam da sam radi s bazom.

Cuvanje integriteta.

Nastoji se automatski saˇ

cuvati korektnost i konzistencija podataka, i to u

situaciji kad postoje greˇ

ske u aplikacijama, te konfliktne istrovremene aktivnosti korisnika.

Mogu´

cnost oporavka nakon kvara.

Mora postojati pouzdana zaˇ

stita baze u sluˇ

caju kvara hard-

vera ili greˇ

saka u radu sistemskog softvera.

Zaˇ

stita od neovlaˇ

stenog koriˇ

stenja.

Mora postojati mogu´

cnost da se korisnicima ograniˇ

ce prava

koriˇ

stenja baze, dakle da se svakom korisniku reguliraju ovlaˇ

stenja ˇ

sto on smije a ˇ

sto ne smije

raditi s podacima.

Zadovoljavaju´

ca brzina pristupa.

Operacije s podacima moraju se odvijati dovoljno brzo, u skladu

s potrebama odredene aplikacije. Na brzinu pristupa moˇ

ze se utjecati odabirom pogodnih fiziˇ

ckih

struktura podataka, te izborom pogodnih algoritama za pretraˇ

zivanje.

Mogu´

cnost podeˇ

savanja i kontrole.

Velika baza zahtijeva stalnu brigu: pra´

cenje performansi, mi-

jenjanje parametara u fiziˇ

ckoj gradi, rutinsko pohranjivanje rezervnih kopija podataka, reguliranje

ovlaˇ

stenja korisnika. Takoder, svrha baze se vremenom mijenja, pa povremeno treba podesiti i

logiˇ

cku strukturu. Ovakvi poslovi moraju se obavljati centralizirano. Odgovorna osoba zove

administrator

baze podataka. Administratoru trebaju stajati na raspolaganju razni alati i

pomagala.

1.1.3

Arhitektura baze podataka

Arhitektura baze podataka sastoji se od tri “sloja” i suˇ

celja medu slojevima, kao ˇ

sto je prikazano na

Slici 1.1. Rijeˇ

c je o tri razine apstrakcije

Fiziˇ

cka razina

odnosi se na fiziˇ

cki prikaz i raspored podataka na jedinicama vanjske memorije. To je

aspekt kojeg vide samo sistemski programeri (oni koji su razvili DBMS). Sama fiziˇ

cka razina moˇ

se dalje podijeliti na viˇ

se pod-razina apstrakcije, od sasvim konkretnih staza i cilindara na disku,

do ve´

c donekle apstraktnih pojmova datoteke i zapisa kakve susre´

cemo u klasiˇ

cnim programskim

jezicima.

Raspored pohranjivanja

opisuje kako se elementi logiˇ

cke definicije baze preslikavaju

na fiziˇ

cke uredaje.

Globalna logiˇ

cka razina

odnosi se na logiˇ

cku strukturu cijele baze. To je aspekt kojeg vidi projek-

tant baze odnosno njen administrator. Zapis logiˇ

cke definicije naziva se

shema

(engleski takoder

schema). Shema je tekst ili dijagram koji definira logiˇ

cku strukturu baze, i u skladu je sa zadanim

1.1. OSNOVNI POJMOVI VEZANI UZ BAZE PODATAKA

modelom. Dakle imenuju se i definiraju svi tipovi podataka i veze medu tim tipovima, u skladu
s pravilima koriˇ

stenog modela. Takoder, shema uvodi i ograniˇ

cenja kojim se ˇ

cuva integritet

podataka.

Lokalna logiˇ

cka razina

odnosi se na logiˇ

cku predodˇ

zbu o dijelu baze kojeg koristi pojedina aplikacija.

To je aspekt kojeg vidi korisnik ili aplikacijski programer. Zapis jedne lokalne logiˇ

cke definicije

zove se

pogled

(engleski view) ili pod-shema. To je tekst ili dijagram kojim se imenuju i definiraju

svi lokalni tipovi podataka i veze medu tim tipovima, opet u skladu s pravilima koriˇ

stenog modela.

Takoder, pogled zadaje preslikavanje kojim se iz globalnih podataka i veza izvode lokalni.

Aplikacijski

program 1

Aplikacijski

program 2

Aplikacijski

program 3

Pogled 1

Pogled 2

Pogled 3

Shema

Raspored

pohranjivanja

Datoteke

Lokalna

logiˇ

cka

razina

Globalna

logiˇ

cka

razina

Fiziˇ

cka

razina

Slika 1.1: Arhitektura baze podataka

Za stvaranje baze podataka potrebno je zadati samo shemu i poglede. DBMS tada automatski

generira potrebni raspored pohranjivanja i fiziˇ

cku bazu. Administrator moˇ

ze samo donekle utjecati na

fiziˇ

cku gradu baze, podeˇ

savanjem njemu dostupnih parametara.

Programi i korisnici ne pristupaju izravno fiziˇ

ckoj bazi, ve´

c dobivaju ili pohranjuju podatke posred-

stvom DBMS-a. Komunikacija programa odnosno korisnika s DBMS-om obavlja se na lokalnoj logiˇ

ckoj

razini.

1.1.4

Jezici za rad s bazama podataka

Komunikacija korisnika odnosno aplikacijskog programa i DBMS-a odvija se pomo´

cu posebnih jezika.

Ti jezici tradicionalno se dijele na sljede´

ce kategorije.

Jezik za opis podataka

(Data Description Language - DDL). Sluˇ

zi projektantu baze ili administra-

toru u svrhu zapisivanja sheme ili pogleda. Dakle tim jezikom definiramo podatke i veze medu
podacima, i to na logiˇ

ckoj razini. Koji puta postoji posebna varijanta jezika za shemu, a posebna

za poglede. Naredbe DDL obiˇ

cno podsije´

caju na naredbe za definiranje sloˇ

zenih tipova podataka

u jezicima poput COBOL, PL/I, C, Pascal.

Jezik za manipuliranje podacima

(Data Manipulation Language - DML). Sluˇ

zi programeru za

uspostavljanje veze izmedu aplikacijskog programa i baze. Naredbe DML omogu´

cuju “manevri-

ranje” po bazi, te jednostavne operacije kao ˇ

sto su upis, promjena, brisanje ili ˇ

citanje zapisa. U

nekim softverskim paketima, DML je zapravo biblioteka potprograma: “naredba” u DML svodi
se na poziv potprograma. U drugim paketima zaista se radi o posebnom jeziku: programer tada
piˇ

se program u kojem su izmijeˇ

sane naredbe dvaju jezika, pa takav program treba prevoditi s

dva prevodioca (DML-precompiler, obiˇ

cni compiler).

1.2. ˇ

ZIVOTNI CIKLUS BAZE PODATAKA

Proizvodaˇ

Produkt

Operacijski sustav

Jezici

IBM Corporation

DB2

Linux, UNIX (razni),

SQL,

MS Windows NT/2000/XP,

COBOL,

VMS, MVS, VM, OS/400

Java, . . .

Oracle Corporation

Oracle

MS Windows (razni),

SQL,

Mac OS, UNIX (razni),

Java i

Linux i drugi

drugi

IBM Corporation

Informix

UNIX (razni), Linux,

SQL,

(prije : Informix

MS Windows NT/2000/XP

Java i

Software Inc.)

drugi

Microsoft

MS SQL Server

MS Windows NT/2000/XP

SQL,
C++, . . .

MySQL AB

MySQL

Linux, UNIX (razni),

SQL,

MS Windows (razni), Mac OS

C, PHP, . . .

Sybase Inc.

Sybase

MS Windows NT/2000, OS/2,

SQL,

SQL Server

Mac, UNIX (razni), UNIXWare

COBOL, . . .

Hewlett Packard Co.

Allbase/SQL

UNIX (HP-UX)

SQL,
4GL, C, . . .

Cincom

Supra

MS Windows NT/2000, Linux,

SQL,

Systems Inc.

UNIX (razni), VMS, MVS, VM

COBOL, . . .

Microsoft Corporation

MS Access

MS Windows (razni)

Access
Basic,
SQL

Tabelarni prikaz 1.1: Poznati softverski paketi za rad s bazama podataka

1.2.2

Modeliranje podataka

Razliˇ

citi pogledi na podatke, otkriveni u fazi analize, sintetiziraju se u jednu cjelinu - globalnu shemu.

Precizno se utvrduju tipovi podataka. Shema se dalje dotjeruje (“normalizira”) tako da zadovolji neke
zahtjeve kvalitete. Takoder, shema se prilagodava ograniˇ

cenjima koje postavlja zadani model podataka,

te se dodatno modificira da bi bolje mogla udovoljiti zahtjevima na performanse. Na kraju se iz sheme
izvode pogledi (pod-sheme) za pojedine aplikacije (grupe korisnika).

1.2.3

Implementacija

Na osnovu sheme i pod-shema, te uz pomo´

c dostupnog DBMS-a, fiziˇ

cki se realizira baza podataka

na raˇ

cunalu. U DBMS-u obiˇ

cno postoje parametri kojima se moˇ

ze utjecati na fiziˇ

cku organizaciju

baze. Parametri se podeˇ

savaju tako da se osigura efikasan rad najvaˇ