PODATKOVNE ZBIRKE Tatjana WELZER TEHNIŠKA FAKULTETA MARIBOR UDK: 681.3.016 POVZETEK - Referat opisuje različne strukture podatkovnih zbirk in njihovo oblikovanje. Opisana je drevesna, mrežna in relacijska struktura zbirke ter metoda za njeno oblikovanje. DATA BASES: This paper describeš different structures of data bases and data bases design. Tree, network and relation data bases and a method for data base design are described. 1. UVOD Sirjenje distribuiranih računalniških sistemov in njihovo povezovanje v lokalne in javne računalniške mreže, omo- goča novo in boljšo organiziranost splošnih informacijskih sistemov. Zgradba uspešnih računalniško podprtih siste- mov temelji na organiziranih podatkovnih zbirkah. Podat- kovne zbirke so lahko centralizirane ali distribuirane. V centralizirani podatkovni zbirki se vsi podatki (trenutne vrednosti) nahajajo na eni lokaciji. Distribuirana podat- kovnezbirka pa predvideva podatkovno zbirko, ki se tekoče obnavlja. Razdeljena je na več delov z ločenim, vendar enakovrednim upravljanjem. Uporabnik se bo avtomatsko povezal s tisto enoto, kjer so zahtevani podatki. 2. PODATKOVNE ZBIRKE Podatkovno zbirko definiramo kot neredundantno zbirko vzajemno povezanih podatkov, ki jih uporabljamo za izva- janje ene ali več apltkacij ali pa kot zbirko podatkov, ki so medsebojno povezani brez nepotrebne redundance in omogočajo optimalno izvajanje najrazličnejših aplikacij. Podatkovno zbirko lahko definiramo še na vec načinov, bi- stvo vseh definicij pa je, da nam podatkovna zbirka pred- stavlja skladišče informacij, ki jih uporabljamo za izva- janje posameznih aplikacij. V razvoju podatkovnih zbirk od njihovega nastanka do da- nes so se izoblikovale tri osnovne strukture: hierarhična ali drevesna, mrežna in relacijska struktura. 2.1. DREVESNA STRUKTURA Drevo je zgrajeno hierarhično iz elementov imenovanih segmenti, med katerimi veljajo naslednji odnosi: 1. Najvišji nivo v hirerarhiji ima le en segment, kj ga imenujemo koren. 2. Vsi segmenti razen korena so povezani z enim in to samo enim segmentom na višjem nivoju, gledano s stališča danega nivoja. Segment na višjem nivoju imenujemo starši, segmenti na danem nivoju so otroci. Posamezen element lahko isto- časno opravlja nalogo staršev in otrok. Drevesna struktura-je lahko uravnotežena ali neuravnote- žena. Pri uravnoteženem drevesu ima vsak segment enako število vej. Razvoj drevesa pri tem poteka od vrha proti dnu in od leve proti desni. Poseben primer uravnoteže- nega drevesa je binarno drevo, pri katerem iz vsakega segmenta izhajata natanko dve veji ali nobena veja. Ob binarnem drevesu poznamo še B-drevo. B-drevo je uravnoteženo, vendar organizirano v vejah končne dol- žine, ki lahko vsebujejo le določeno število informacij. Ko vejo napolnimo z elementi, se preprosto razcepi v dve novi veji ha istem nivoju. 2.2. STRUKTURA MREŽE Če ima otrok več staršev in povezave ne moremo opisati s pomočjo drevesa, govorimo o mrežni strukturi. V njej je lahko vsak segment povezan z vsakim segmentom. Vsa- ko mrežno strukturo je možno poenostaviti, tako da jo prevedemo v preprostejšo drevesno strukturo. To poeno- stavitev izvedemo s pomočjo redundance(v zapletenejših primerih se zato poenostavitvi odpovemo). 2.3. STRUKTURA RELACIJE Pri klasični strukturi podatkovne zbirke (drevesna in mrežna struktura), najpogosteje naletimo na naslednje probleme: podatkovne strukture na logičnem nivoju so zapletene, ni podatkovne neodvisnosti v smeri fizično - - logično, manjka preprost mehanizem za dostop do po- datkov na logičnem nivoju, programer pa je prisiljen upo- rabljati vnaprej definirane fizične poti. Rešitev teh pro- blemov predstavlja relacljska podatkovna zbirka. V njej so vsi podatki eksplicitno predstavljeni kot vrednosti v ta- belah-relacijah, ki so osnova relacijske strukture. S ta- belami zelo enostavno prikažemo relacije - povezave med posameznimi podatki. PREDMETI PŠTEV PIME PLET PŠTEVILO Pl OSNOVE ELEKTR. 1 90 P2 MATEMATIKA 3 60 P3 ELEKTRONIKA 2 75 P4 REGULACIJE 2 75 P5 FIZIKA 1 45 158 UČITELJI UŠTEV UIME NAZIV KRAJ Ošl OŠ2 OŠ3 NOVAK PETAN KOREN DOC R. PROF V. PRED MARIBOR LJUBLJANA KRANJ RAZPOREDITEV ' UŠTEV PŠTEV DATUM ŠT. TEDNOV . Ošl OŠ2 OŠ3 OŠ3 P4 Pl P2 P5 05.10.83 18.02.84 15.11.83 05.10.83 10 in 10 Ofi Vsaka tabela ima svoje ime. V našem primeru so to PRED- METI, UČITELJI in RAZPOREDITEV. Vsaka vrstlca nam opi- suje eno skupino podatkov. Posamezne lastnosti so opisa- ne v stolpcih, katerih imena imenujemo atribute. Množico vseh vrednosti, ki nastopi v posameznem stolpcu pa ime- • nujemo domena. V tabeli PREDMETI so atributi PŠTEV, PIME, PLET in PŠTEVILO UR. Ti atributi opisujejo zn vsak predmet: njegovo številko oziroma oznako, ime, letnik v katerem se predmet predava in število ur. Če želimo ime stolpca ločiti od morebitnega' istega imena v kakšni drugi tabeli, mu kot predpono dodamo ime tabele s piko (PRED- METl.PLET). Podatku, ki nedvoumno določa vrstico v tabeli pravimo ključ. Lahko je enostaven, če je v enem stolpcu, oziroma sestavljen, £e ga določa več stolpcev. Ključa PŠTEV v ta- beli PREDMETI in UŠTEV v tabeli UČITELJI sta enostavna. V tabeli RAZPOREDITEV pa je ključ lahko sestavljen iz UŠTEV, PŠTEV in DATUM. Iz opisanih primerov lahko spoznamo tudi bistvene last- nosti relacij: V posamezni tabeli nimatno podvojenih vrstic, niti podvo- jenih stolpcev. Vrstni red vrstic in stolpcev ni pomemben. Med različnimi tabelami ni vidnih vezi, saj povezave med njimi dosežemo s primerjanjem vrednosti v posameznih stolpcih. 2.3.1. OPERACIJE V RELACIJSKIH MODELIH Osnovne relacije so podane v tabelah, iz katerih lahko s primernimi relacijskimi operatorji gradimo nove relacije - tabele (relacija in tabela sta sinonima). Pravila delovanja relacijskih operatorjev nam pojasnjuje relacijska algebra. Operatorji (unija, presek, razlika in kartezični produkt) so sposojeni iz teorije množic. Ob njih v relacijski algebri srečamo še druge operatorje med katerimi so najpomembnejši selekcija, projekcija in zdru- žitev. Selekcija S tem operatorjem dobimo iz tabele A tabelo B tako, da iz prve tabele prenesemo v drugo tabelb samo tiste vrstice, ki ustrezajo nekemu pogoju. Projekcija Operator projekcije prenese iz osnovne tabele samo dolo- čene stolpce. Pri tem se lahko zgodi, da dobimo v novi ta- beli dve ali več enakih vrstic. Redundančne vrstice izloči- mo in s tem izpolnimo zahtevani pogoj za relacijsko struk- turo. Združitev Pod tem imenom srečamo več različnih operatorjev: zdru- žitev po enakosti, naravno združitev in zunanjo naravno združitev. Imejmo relaciji R in S, ki imata skupno domeno D. Z A in B označimo atributa v relacijah R in S in oba definira- mo nad D. Združitev po enakosti relacije RnaAz relacijo S na B je takšna podmnožica kartezičnega produkta RxS, kjer ima vsaka vrstica iste vrednosti v stolpcih A in B. O naravni združitvi govorimo, kadar obdržimo samo en stolpec. Ta se zgodi, če imamo po združitvi po enakosti dva stolpca z istimi vrednostmi. Zunanja naravna zdru- žitev pa nam omogoča, da v relacijo uvrstitno tudi tisie vrstice iz združenih tabel, ki nimajo ustreznega para v drugi tabeli. Opisane operatorje lahko med seboj tudi po- vežemo in dobimo povezane operatorje. 3. OBUKOVANJE PODATKOVNIH ZBIRK Z razvojem podatkovnih zbirk se je močno spremetiilo tu- di njihovo oblikovanje. Sprva je bil precejšen del obliko- vanja povezan s fizično lokacijo pomnenja podatkov, z nji- hovim nalaganjem in dostopom do sekundarnega pomnilni- ka. Te naloge je danes v glavnem prevzel sistem za uprav- ljanje podatkovne zbirke, tendenca oblikovanja podatkov- nih zbirk pa je v optimizaciji logičnih modelov podatkovnih zbirk. Pri oblikovanju podatkovne zbirke najprej analiziramo ogrodje (obstoječ sistem), nato pa postopoma prehajamo do posameznih nalog, podnalog in podatkovnih elementov, ki nas zanimajo. Nalogo opravimo postopoma v štirih fazah: 1. V analizi okolja zahtev zbiramo informacije, ki so po- trebrie za izvajanje naslednjih korakov. Osnovne leh- nike za pridobivanje potrebnih informacij so prebira- nje dokumentov in drugih pisanih virov, izpraševanje ljudi in analiziranje anket. To je istočasno tudi vhod v prvo fazo, njen izhod pa predstavlja uporabna specifi- kacija v obliki diagrama poteka, ki nam predstavi naj- pomembnejše aktivnosti sistema in njihove medsebojne povezave. 2. V drugi fazi analiziramo in specificiramo sistem. Iz- hajamo iz obstoječega diagrama, ki natn zagotavlja do- bro poznavanje ciljnega sistema. Vsako aktivnost di- agrama hierarhično razdelimo v več posameznih in delnih nalog. Pri tem procesu pride tudi do delitve po- datkov, ki pripadajo posamezni aktivnosti. Razdelimo jih v podatkovne elemente ali pa v podmnožice le teh. Delitev aktivnosti in podatkov poteka tako dolgo, da imamo samo še enostavne in razumljive naloge ter po- datkovne elemente. Končni rezultat je diagram poteka, ki je tokrat podrobneje razdelan. Temu prvemu delu faze sledi še specifikacija nalog, podatkov (dokumentov) in uporabniških programov. 3. Cilj zasnove modela je prenos znanja, ki smo ga zbra- li v 1. in 2. fazi, v določenen prikaz. Za uspešno mo- deliranje uporabljamo različne jezike ( CSDL, Taxis, D-graphs, E-R model). 4. V zadnji fazi oblikujemo logično shemo. Izvesti mo- ramo naslednje naloge: Izdelamo natančni model podatkovne zbirke na osnovi koncepta modela, cjeneriramo bazično logično shemo, 159 integriramo novo shemo, ki predstavlja model povezav in njihovo komunikacijsko težo, optitniziratno shemo in realiziramo logično shemo ob pomoči optimizacij- ske sheme. Ko uspešno zaključimo zadnjo nalogo četrte faze, je po- datkovna zbirka pripravljena za izvajanje operacijske fa- ze. 4. ZAKLJUČEK Pregled razvoja, struktur in oblikovanja podatkovnih zbirk je pokazal, da so na tem področju spremembe pogoste. Tak.o so na področju podatkovnih zbirk trenutno izredno popularne" relacijske zbirke, ki tudi nepoznavalcem orga- nizacije podatkovne zbirke omogočajo aktivno vključeva- nje v oblikovanje le te. Kot pomoč pri oblikovanju in delu z relacijskimi podatkov- nimi zbirkami pa je nadvse pomembna tudi umetna inteli- genca in njeni jeziki (LISP, PROLOG, POP, micro LISP, micro PROLOG...). Prolog lahko direktno uporabimo kol interpreter za relacijski model podatkovne zbirke. Še boljše pogoje za dela pa daje POPLOG- programirano okolje v katerem so združeni LISP, PROLOG in POP. 5. LITERATURA 1. S. Algič: Relacione baze podataka, Sarajevo 1984 2. D. N. Chorafas: Database for networks and mini- computers, New York 1982 3. J. Martin: Computer Data-Base Organization, New Yersey 1975 4. G. Wiederhold: Database Design, Tokyo 1981 5. G. Wiederhold: Knowledge and Database Management, IEEE Software januar 1984