Dalībnieka diskusija:Kristaps.jaunzems

--Kristaps.jaunzems 19:40, 21 oktobrī, 2010 (UTC)

Datu bāzu projektēšana

Datu bāzu projektēšana ir process, kurā tiek radīts detalizēts datu modelis. Šis loģiskais datu modelis ietver visas nepieciešamās loģiskās un fiziskās dizaina iespējas, kas vajadzīgas, lai radītu dizainparaugu Data Definition Language (Datu Definīcijas Valodā), ko pēc tam izmanto datu bāzes izveidošanā. Pienācīgi aprīkots datu modelis satur detalizētu informāciju par katru entītiju.

Termins datu bāzu projektēšana, var tikt izmantots, lai aprakstītu dažādus projektēšanas procesus kopējā datu bāzu sistēmā. Galvenokārt, to var uzlūkot kā datu bāzes loģiskās struktūras izstrādi. Objektorientētā datu bāzes modelī entītijas un relācijas pievienojas objektu klasēm un nosauktajām attiecībām. Tomēr terminu datu bāzu projektēšana var arī attiecināt uz visu datu bāzes projektēšanas procesu kopumu, kas ir daļa no datu bāzu lietojumprogrammu kopuma datu bāzu menedžmenta sistēmā (DBMS).

Datu bāzu projektēšanas process sastāv no vairākiem soļiem, kurus izpilda attiecīgais datu bāzu projektētājs. Parasti ir jāizpilda šādi soļi:

• Jānosaka attiecības starp atšķirīgajiem datu elementiem;
• Jāizveido loģiskā struktūra balstoties uz datiem un attiecībām starp tiem.

ER diagramma (Entītiju - relāciju diagrammas)

Vienkārša entītiju-relāciju diagramma

Daļa no datu bāzu projektēšanas ir arī Entītiju - relāciju diagrammas. ER diagrammas palīdz projektēt datu bāzi efektīvā un viegli saprotamā veidā (kā konceptuālu shēmu).

Īpašības ER diagrammās tiek attēlotas kā ovālas ģeometriskas figūras, kas ar līnijām savienotas ar attiecīgo entītiju vai relāciju un ietver īpašības nosaukumu.

Relāciju modeļa veidošanas procesā pēdējais solis var tikt sadalīts divos atsevišķos - nosaka galvenos objektus, par kuriem informācija tiek glabāta un nosaka attiecības kādas pastāv starp šiem objektiem. Šis solis nav nepieciešams objektu datu bāzēs.

Datu bāzes projektēšanas process

Projektēšanas procesa soļi:

1. Nosaka galveno pielietojumu datu bāzei.
2. Iegūst un sakārto nepieciešamo informāciju - savāc visu nepieciešamo informāciju ierakstīšanai datu bāzē, piemēram, produkts un pasūtījums.
3. Sadala informāciju tabulās - Sadala informāciju galvenajās entītijās. Rezultātā katra entītija kļūst par tabulu, piemēram, produkti un pasūtījumi.
4. Sadala informācijas objektus kolonnās - Izlemj, kādu informāciju ir nepieciešams glabāt katrā tabulā. Katrs objekts kļūst par lauku un tiek attēlots kā kolonna tabulā. Piemēram, nodarbinātā tabulā tiktu iekļauti lauki kā "Uzvārds" un "Nolīgšanas datums".
5. Nosaka primārās atslēgas - Izvēlas katras tabulas primāro atslēgu. Primārā atslēga ir kolonna, kas ir unikāla norāde, kas identificē katru rindu. Piemēram, Produkta ID vai Pieprasījuma ID.
6. Izveido tabulu attiecības - Apskata katru tabulu un secina, kā dati vienā tabulā ir saistīti ar datiem, kas glabājas citās tabulās. Pievieno laukus tabulām, ja nepieciešams precizēt to attiecības, saistību.
7. Optimizē datu bāzes dizainu - Analizē datus, lai novērstu kļūdas iespējas. Izveido tabulas un pievieno dažus datu laukus piemēram. Novērtē, vai tiek sasniegts vēlamais rezultāts, ko dod tabulu dati un noformējums, lai pēc iespējas precīzāk izpildītu nepieciešamos uzdevumus rezultāta sasniegšanai.
8. Pielieto nepieciešamos normalizācijas likumus - Pielieto datu normalizācijas likumus, lai novērtētu, vai dati ir pareizi strukturēti.

Izmantojamo datu noteikšana

Lielākoties, persona, kas projektē attiecīgo datu bāzi ir arī speciālists nozarē, ar kuru datu bāzes dati ir saistīti, vismaz projektētājam vajadzētu konsultēties ar nozares speciālistu, kurš ir saistīts un ieinteresēts datu bāzes izveidē. Piemēram, ekonomika, fizika, medicīna utt.

Šis process ir viena no galvenajām datu analīzes sastāvdaļām, kas prasa datu bāzes projektētājam spēju izdibināt nepieciešamo informāciju no personas ar nozares specialitāti, tāpēc, ka bieži nākas sastapties ar speciālistiem, kuriem ir grūtības skaidri un nepieciešamā sapratnes līmenī izklāstīt informāciju par saglabājamiem datiem.

Normalizācija

Relāciju datu bāzēs normalizācija ir sistemātisks ceļš, kā pārliecināties par to, vai datu bāzes struktūra ir piemērota galvenajam nolūkam un ir ievēroti drošības pasākumi, lai izvairītos no kolīzijām, kas var novest pie datu zudumiem.

Viens no galvenajiem ieteikumiem datu bāzu projektēšanā ir tas, ka projektētājam vajadzētu izveidot pilnīgi normalizētu datu bāzes dizainu, kurā var tikt izmantota arī denormalizācija ar mērķi paaugstināt datu bāzes veiktspēju. Tomēr daži projektēšanas priekšnosacījumi, piemēram, dimensionālās modelēšanas pieeja datu glabātuves dizainam, skaidri rekomendē ne-normalizētus datu bāzu projektus, tas ir, projektus, kas lielākoties neievēro 3NF.

Datu bāzu dizainu tipi

Konceptuāla shēma

Tikko kā datu bāzes projektētājs ir lietas kursā par datiem, kas jāievieto datu bāzē, jānosaka, kādas ir datu savstarpējās saistības un atkarības. Dažkārt izmainot vienus datus, neapzināti tiek izmainīti arī citi atkarīgi dati. Piemēram, personu vārdu un adrešu sarakstā, pieņemot iespējamu situāciju, ka vairākām personām var būt viena dzīvesvietas adrese, bet vienai personai nevar būt vairākas adreses, vārdi ir atkarīgi no adresēm, tāpēc ka, ja adrese tiek izmainīta, tad arī vārdi tiek mainīti. Tomēr citā situācijā notikumi ir atšķirīgi. Vienus datus izmainot, citi no šīs darbības netiek ietekmēti.

(PIEZĪME: Pierasts pārpratums ir, ka relāciju modelis šādi tiek saukts par godu attiecību veidošanai starp datiem. Šis pieņēmums ir aplams. Relāciju modelis šādi ticis nosaukts tāpēc, ka tas ir bāzēts uz matemātiskām struktūrām, sauktām par relācijām.)

Loģiski strukturēti dati

Līdzko ir noteiktas attiecības un atkarības starp dažādiem datiem, ir iespējams sakārtot tos loģiskā struktūrā, kas pēc tam tiek attēlota datu bāzu menedžmenta sistēmas nodrošinātos datu objektos. Šie objekti ir tabulas, kurās tiek glabāti dati rindās un kolonnās. Katra tabula var kalpot kā loģisku objektu vai attiecību vienots eksemplārs no viena vai vairākiem loģiskiem objektiem. Attiecības starp tabulām var tikt glabātas kā saites, kas savieno "bērnu" tabulas ar "vecāku" tabulām. Kopš sarežģītas loģiskās attiecības pašas par sevi ir tabulas, tām būs saites uz vairākām ne tik uz vienu "vecāku" tabulu. Objektu datubāzē saglabājamie objekti tieši atbilst objektiem, kas izmantoti objektorientētās programmēšanas valodās, kas tiek pielietotas, lai rakstītu lietojumprogrammas, kas tiks izmantotas darbā ar datiem.

Fiziskais datu bāzes dizains

Fiziskais datu bāzes dizains apraksta, veido fizisko datu bāzes konfigurāciju datu glabāšanas ierīcē. Tajā tiek iekļauta detalizēta informācija par datu elementiem, tipiem, indeksēšanas iespējām un citiem parametriem, kas atrodami DBMS datu vārdnīcā. Tas ir detalizēts dizains sistēmai, kurā ietverti moduļi, datu bāzes lietojumprogrammu un uzglabāšanas ierīču specifikācija.

Radix sort kārtošanas algoritms

Radix kārtošanas algoritms pirmoreiz minēts jau tik nesenajā 1887. gadā Herman Hollerith darbā par tabulācijas mašīnām. Vēlāk jau Radix sort tika izmantots perfokaršu kārtošanā milzīgās, šim nolūkam specializētās mašīnās. Datoru algoritms, kas balstīts uz Radix Sort tika izgudrots 1954. gadā MIT (Massachusetts Institute of Technology).

Algortima apraksts

Radix sort – lineāra laika kārtošanas algoritms - tiek izmantots dažāda tipa datu kārtošanai. Šī kārtošanas metode atšķiras no citām kārtošanas metodēm ar to, ka elementus savā starpā nesalīdzina, bet elementu sakārtošana ir aizstāta ar citu algoritmu, parasti counting sort (skatīšanas kārtošanas metode) vai spaiņa kārtošanas metodi (Bucket sort). Radix ir ātrs un stabils kārtošanas algoritms, kuru var izmantot, lai sakārtotu ierakstus, kas tiek identificēti ar unikālām atslēgām. Tas neaprobežojas tikai ar integer tipu, bet tiek lietots string, char tipu un arī skaitļu ar peldošo punktu kārtošanai. Radix sort skaitļus sakārto augošā secībā un simbolus vai simbolu virknes sakārto leksikogrāfiskā secībā. Ierakstu sakārtošanai Radix sort nepieciešamas O(n · log n) salīdzināšanas, n – kārtojamo ierakstu skaits. Radix nereti tiek izmantots, lai sakārtotu informācijas ierakstus, kas sastāv no vairākiem laukiem. Piemēram, ir nepieciešams sakārtot datus pēc trim pazīmēm vai atslēgām: gada, mēneša un dienas. Mēs varam izmantot kārtošanas algoritmu ar salīdzināšanas funkciju, kas salīdzina gadus un, ja tie atkārtojas, tad salīdzina mēnešus, savukārt, ja tie atkārtojas, tad salīdzina dienas (tas būtu Radix MSD). Pastāv arī alternatīva kārtot informāciju trīs reizes izmantojot stabilu kārtošanu, vispirms kārtojot dienas, tad mēnešu un pēc tam gadus (Radix LSD). Radix sort iedalās divās kārtošanas metodēs:

1. LSD – least significant digit;
2. MSD – most significant digit

Radix sort darbības princips

Galvenie LSD Radix sort darbības soļi:

1. Ņem vismazāk nozīmīgo skaitļa ciparu, vai simbolu virknes simbolu (piemēram, skaitlim 681 tas būtu cipar 1, bet simbolu 1. virknei „abc” tas būtu „c”);
2. Kārto elementu sarakstu, salīdzinot katra elementa attiecīgo nozīmīgo ciparu vai burtu. Tiek saglabāta elementu kārtība, ja to atslēgu vērtības ir vienādas (piemēram, kārtojot pēc mazākā nozīmīgā cipara skaitļus 356 ar 426 (6=6), sakārtotajā sarakstā tiktu saglabāta to kārtība pirms kārtošanas, bet, protams, ka kārtojot pēc nākošā mazāk nozīmīgā cipara, tie tiks sakārtoti augošā kārtībā (5 > 2));
3. Tiek atkārtota otrā darbība ar nozīmīgākiem elementu cipariem.

MSD darbojas pretējā virzienā – sāk kārtot skaitļus, salīdzinot to nozīmīgākās pozīcijas ciparus un turpina salīdzināšanu ar mazāk nozīmīgo pozīciju cipariem. MSD priekšrocības veiksmīgā gadījumā varētu būt tas, ka nav jāsalīdzina visas noteiktas nozīmības atslēgas, ja tas vairs nav nepiecišams, jo atsevišķi elementi jau ir savā vietā.

Most Significant Digit

Most Significant Digit

Radix sort pseido kods

Radix-Sort (A,d) 1. for i ←1 do d 2. do use a stable sort to sort array A on digit i

Radix sort analīze

Šajā pseidokodā pieņemts, ka katrs kārtojamais elements n-elementu masīvā A sastāv no d cipariem, kur pirmais (1) cipars ir vismazāk nozīmīgais (kreisākais) cipars un attiecīgi d ir cipars ar vislielāko nozīmību. Doti d – ciparu skaitļi, kuriem var būt k iespējamas vērtības, Radix sort šos skaitļus sakārto Θ(d(n+k )) laikā. Radix sort darbības laiks ir atkarīgs no tā, kāds starp kārtošanas algoritms tiek izmantots. Ja katrs cipars ir intervālā no 0 līdz k-1 un k nav pārāk liels, tad skaitīšanas kārtošanas algoritms (Counting Sort) ir acīmredzama izvēle. Katrs solis, kas nepieciešams n d-ciparu skaitlim aizņem Θ(n+k ) laiku. Tā kā šeit ir d skaits soļu, tad pavisam Radix kārtošanas algoritmam ir nepieciešams laiks, kas ir Θ(d(n+k )). Kad d ir konstants un k= 0(n), tad Radix darbojas lineārā laikā. Doti n b–bitu skaitļi un jebkāds pozitīvs integer tipa skaitlis r ≤ b, tad Radix sakārto šos skaitļus Θ((b/r)(n+2r)) laikā. Pierādījums: vērtībai r ≤ b tiek apskatīta katra atslēga, kur katrs d =[b/r] satur ciparus no r bitiem. Tā kā katrs cipars ir skaitlis, kas atrodas intervālā no 0 līdz 2r-1, tad mēs varam izmantot skaitīšanas kārtošanas algoritmu (Counting Sort), kur k=2r-1. (Piemēram, mēs varam apskatīt 32 bitu vārdu kā četrus 8 bitīgus ciparus, sekojoši sanāk b=32, r= 8, k=2r-1=28-1=255 un d=b/r=4. Katrs solis ko veic skaitīšanas kārtošanas metode (Counting Sort) tiek veikts laikā, ko aprēķina pēc Θ(n+k)= Θ (n+2r), bet tā, kā ir d skaits soļu, tad kopējais izpildes laiks ir Θ(d(n+2r)) = Θ((b/r)(n+2r)). Dotajām n un b vērtībām mēs izvēlamies kādu r vērtību, kas ir r ≤ b, tas vēl samazina izteiksmi ((b/r)(n+2r)) . Ja b < [lg n], tad jebkādai r ≤ b vērtībai ir spēka, ka (n+2r)= Θ(n). Ja izvēlamies iespēju, ka r=b, tad izpildes laiks ((b/b)(n+2b))= Θ(n). Ja b ≥ [lg n] un izvēloties, ka r=[lg n], tad tas dod pašu labāko izpildes laiku pie nemainīga faktora. Izvēloties r=[lg n] rezultātu, tad darbības laiks ir (bn/lg n). Tā kā mēs iepriekš palielinājām r virs [lg n] vērtībām, tad 2r skaitītājā pieaug straujāk nekā r, kas atrodas saucējā. Tad tā, kā palielinājām r virs [lg n] vērtībām, tad darbības laiks ir Ω(bn/lg n). Pretēji, ja mēs gribējām samazināt r zem [lg n] vērtībām, tad nosacījums b/r palielinās un n+2r ir spēkā Θ(n). Vai Radix kārtošanas algoritms ir lietderīgāks par uz salīdzināšanu balstītiem algoritmiem, kā, piemēram, ātro kārtošanas metodi? Ja b= 0(lg n), kā tas parasti arī ir un r ≈lg n, tad Radix kārtošanas algoritma darbības laiks ir Θ(n) , kas ir labāks nekā ātrās kārtošanas (Quick sort) vidēji uzrādītais laiks, kas ir Θ(n lg n). Kaut gan Radix izdara mazāk soļu nekā ātrā kārtošanas (Quick Sort) metode kārtojot n atslēgas, Radix laiks katra izdarītā soļa veikšanai ir lielāks. Kurš kārtošanas algoritms ir labāks, tas ir atkarīgs no izpildīšanas īpašībām, izmantojamās mašīnas (ātrā kārtošana parasti izmanto daudz efektīvāk kešatmiņu nekā Radix Sort), kā arī no ievades datiem. Daudz vairāk, Radix kārtošanas versija, kas kā stabilu starpkārtošanas algoritmu izmanto skaitīšanas metodi, nekārto pēc skaitļu vietām, kā citi Θ(n lg n) laika salīdzināšanas algoritmi.