Să luăm în considerare un exemplu de relație care conține date despre studentul universitar Ivanov (Tabelul 7.1).

Tabelul 7.1. Detalii student
Număr	Nume de familie	Proiecte de curs	Articole	Nota	Cameră	tel.
1000	Ivanov		Matematică		417	51-11
		Compilatoare	Programarea sistemului	5/4
			Fizică
		Oxidarea sulfului	Chimie	5/5

Exemplu. Atitudine universală.

Se poate observa că datele conțin mai multe câmpuri, de ex. atributele sunt non-atomice. Duplicarea datelor în atribute vă permite să prezentați date despre un student sub forma unei relații (Tabelul 7.2).

Tabelul 7.2. Atitudine STUDENT
Număr	Nume de familie	Proiecte de curs	Articole	Nota	Cameră	Tel.
1000	Ivanov	Nu	Matematică		417	51-11
1000	Ivanov	Compilatoare	Programarea sistemului	5/4	417	51-11
1000	Ivanov	Nu	Fizică		417	51-11
1000	Ivanov	Oxidarea sulfului	Chimie	5/5	417	51-11

Dacă relația include toate atributele de la domeniul subiectului baza de date, se numește atitudine universală. Relația universală este în 1NF. După cum se știe, relația în 1NF generează multe anomalii în prelucrarea datelor (actualizare, ștergere, adăugare, redundanță). Pentru a plasa o relație universală într-o bază de date, aceasta trebuie normalizată - împărțită într-un set de relații mai mici. Acest lucru ridică următoarele trei întrebări:

1. recunoașteți relațiile care trebuie rupte?

2. Cum se efectuează partiţionarea?

3. Când ar trebui finalizat procesul de partiţionare?

Analiza anomaliilor în prelucrarea datelor arată că soluția la primele două întrebări este strâns legată de determinarea cheii primare, recunoașterea fenomenelor de duplicare și redundanță, duplicare și neredundanță a datelor. Toate aceste fenomene se bazează pe conceptul de drept federal. CU punct practicÎn termeni de vedere, sensul Legii federale este următorul: dacă apare, atunci fiecare dintre tupluri având aceeași valoare A, trebuie să aibă aceeași valoare B. Modificarea valorilor A și Bîn timp nu ar trebui să încalce Legea federală.

Cum să recunoaștem legea federală în practică? Legea federală este determinată în fiecare situație specifică de analiză detaliată proprietățile tuturor atributelor relației și formând concluzii despre tipurile de relații dintre ele. FZ-urile nu pot fi identificate analizând o singură instanță a unei relații și găsind două atribute care au aceleași valori în tupluri diferite. FL-urile trebuie obținute din proprietățile atributelor domeniului bazei de date. O viziune relațională este o definiție formală a relațiilor funcționale posibile, dar nu reale.

După ce ați determinat toate legile federale inerente domeniului de bază a bazei de date, puteți începe procesul de distrugere a relațiilor, numit descompunerea schemelor de relaţii. Descompunerea diagramelor de relații este una dintre principalele metode de construire a modelelor logice ale bazelor de date relaționale. Utilizare relație universală vă permite să aveți punct de start descompunerea relaţiilor de baze de date. Rezultatul descompunerii este un model de date normalizat.

Descompunerea diagramelor de relații, proprietățile de conexiune fără pierderi și păstrarea legilor fizice

Unul dintre scopurile proiectării unei baze de date relaționale este de a construi o descompunere (partiție) relație universală la un ansamblu de relaţii care satisfac cerinţele formelor normale.

Să introducem definiția descompunerea schemei de relaţii.

Definiție 1. Descompunerea unei diagrame de relații este înlocuirea acesteia cu un set de submulțimi R .

Înainte de a trece la studiul metodei de descompunere a schemelor de relații, să luăm în considerare problema relațiilor de conectare la împărțirea unei relații universale. Când înlocuim relația inițială cu alte două relații înrudite, este rezonabil să presupunem că aceste relații vor reprezenta proiecții ale relației originale asupra atributelor corespunzătoare. Singura cale aflați dacă proiecțiile primite conțin aceeași informație ca relația inițială - restaurați-o prin realizarea unei conexiuni naturale a proiecțiilor primite. Dacă relația rezultată din îmbinare nu se potrivește cu relația inițială, atunci este imposibil să spunem care dintre ele este relația originală pentru un circuit dat. Deci problema este că atunci când vă alăturați, este posibil să pierdeți existente sau să obțineți tupluri false inexistente anterior. Să luăm în considerare un exemplu de descompunere cu pierdere de informații.

Să luăm în considerare un algoritm pentru verificarea proprietății fără pierderi a unei conexiuni.

Algoritm. Testarea descompunerii pentru proprietatea de îmbinare fără pierderi

intrare: schema de relații R(A 1, A 2, ..., A k), set de legi federale F,

descompunerea d=(R1, R2, ..., Rk).

ieșire: variabilă booleană adevărată sau falsă.

Algoritm

1. Să construim o masă cun coloane şi krânduri, unde coloanăjse potrivește cu atributulA j, și linia i- diagrama relațiilorR i. La intersecția linieii si coloana jpune un simbolaj, dacă atributul A j aparține R i. În caz contrar, plasăm simbolulb ij.

2. Revizuim în mod repetat fiecare lege federală dinF, până când modificarea tabelului devine imposibilă. Privind prin dependență, căutăm rânduri care se potrivesc cu toate coloanele corespunzătoare atributelor de laX. Când sunt detectate astfel de șiruri, identificăm caracterele acestora în coloanele corespunzătoare atributelor de laY, conform regulii a j la a j, b ij la b ij.

3. Dacă, după modificarea rândurilor tabelului, rezultă că un anumit rând este egal cua 1 , a 2 , ..., a k, atunci descompunerea d are proprietatea conexiunii fără pierderi. În caz contrar, descompunerea d nu are această proprietate.

Algoritmul prezentat vă permite să determinați corect dacă descompunerea are proprietatea unei conexiuni fără pierderi.

Să luăm în considerare un exemplu de aplicare a algoritmului folosind relația DE LIVRARE (Furnizor, Adresă, Produs, Cost). Să notăm atributele sale ca: A- furnizor, ÎN- abordare, C- produs, D- cost, în acest caz se aplică legile federale.

Când descompuneți o schemă de relații în alte două scheme de relații, mai mult simpla verificare: Descompunerea are proprietatea de îmbinare fără pierderi, dacă numai. O astfel de lege federală trebuie să aparțină F+.

Proprietatea de îmbinare fără pierderi asigură că orice relație poate fi recuperată din proiecțiile sale. Este clar că la descompunerea structurii fizice a diagramei originale, relațiile sunt distribuite peste relații noi. Prin urmare, este important ca în timpul descompunerii, setul de legi fizice F pentru diagrama de relații r a fost deductibil din proiecții pe diagrame R i.

Să introducem următoarea definiție.

Definiția 2. Proiecția setului de limite fizice F pentru multe atribute X , notat cu, se numește ansamblul legilor federale în F+ , astfel încât.

Se spune că o descompunere are proprietatea de a păstra o lege fizică dacă unirea tuturor legilor fizice care îi aparțin urmează logic toate dependențele din F.

Luați în considerare relația (oraș, adresă, cod poștal). Să notăm atributele sale ca: A - oraș, B - adresa, C - cod poștal, în acest caz, au loc legi federale. Descompunerea diagramei acestei relații ABC pe A.C.Și B.C. are proprietatea unei conexiuni fără pierderi, deoarece Legea federală este adevărată. Cu toate acestea, proiecția pe B.C. oferă doar dependențe banale, proiecție pe AC dă FZ și trivial FZ. Dependența nu rezultă din Legea federală. Prin urmare, această descompunere nu păstrează structura fizică, deși are proprietatea unei conexiuni fără pierderi.

Să luăm în considerare un exemplu de încălcare a Legii federale în timpul descompunerii.

Exemplu. Încălcarea legii federale în timpul descompunerii

R1 (B, C) R2 (A, C)

Lesnaya, 6 132432 Chernogolovka, MO 132432

Lesnaya, 6 132431 Chernogolovka, MO 132431

R(A, B, C)

Chernogolovka, MO 132432 Lesnaya, 6

Chernogolovka, MO 132431 Lesnaya, 6

R = R1 >< R 2 , для R 2 справедлива С \to А, для R не справедлива АВ \ to С.

Astfel, din punctul de vedere al teoriei bazelor de date relaționale schema buna relațiile de baze de date relaționale ar trebui, acolo unde este posibil, să îndeplinească următoarele cerințe:

· elimina dublarea excesivă;

· eliminarea potențialelor inconsecvențe ale datelor;

· au proprietatea conexiunii fără pierderi;

· au proprietatea de a păstra Legea Federală.

În procesul de normalizare a schemei iniţiale de relaţii specificate model informativ date, trebuie obținute diagrame de relații care să îndeplinească cerințele de mai sus.

Metode de proiectare bazate pe descompunerea relațiilor

Conceptul metodelor de descompunere a relațiilor

Să presupunem că schema bazei de date conține dependențe F. Din prevederile teoriei F-dependențelor rezultă că dacă relațiile bazei de date sunt în formă normală Boyce-Codd (BCNF), atunci proiectarea modelului logic al bazei de date poate fi considerată completă în această clasă de dependențe. După cum puteți vedea, teoria oferă un criteriu util (!) pentru oprirea proiectării.

Să formulăm un criteriu vizual care ne permite să stabilim dacă o relație se află în BCNF. Pentru a face acest lucru, introducem următorul concept auxiliar.

Definiția 3. Fie dat FS: , și B este independent funcțional de orice submulțime A, atunci A se numește determinantul lui B.

Determinanții în relație sunt atributele părților din stânga ale Legii Federale. Cheile candidate (vezi tutorialul Modelului de date relaționale) sunt identificate prin găsirea setului minim de valori ale atributelor care definesc valorile tuturor celorlalte atribute din relație. Să ne amintim conceptul unei posibile chei de relație ca atribut sau atribute această relație, care pot fi alese ca fiind primare în acest sens.

Apoi, criteriul Codd, care ne permite să determinăm dacă o relație este în BCNF, poate fi formulat după cum urmează:

O relație este în BCNF dacă și numai dacă fiecare determinant al relației este o cheie posibilă.

Astfel, la descompunerea relațiilor, este necesar să se construiască liste de posibile chei și determinanți și să le compare pentru potriviri. Cu majoritatea anomaliilor potențiale astfel eliminate, proiectarea poate fi finalizată.

Acum știm de unde să începem normalizarea - cu relație universală; ce trebuie verificat - găsirea relației inițiale în BCNF; ce trebuie făcut - descompunerea relației inițiale în alte două relații; și când să se oprească - toate relațiile de baze de date în BCNF. Astfel, se poate formula algoritm general proiectarea unui model logic al unei baze de date relaționale folosind metoda de descompunere:

Algoritmul metodei de descompunere a relațiilor

Algoritm

1. Dezvoltarea unei relații universale pentru baza de date.

2. Definirea tuturor legilor federale între atributele relației.

3. Stabilirea dacă relația este în BNF. Dacă da, atunci finalizați designul; în caz contrar, relația trebuie împărțită în alte două relații.

4. Se repetă punctele 2 și 3 pentru fiecare relație nouă obținută ca urmare a descompunerii.

Să clarificăm câteva aspecte ale metodei de descompunere.

În primul rând, cum se descompune o relație în două relații. Lasă atitudinea R(A, B, C, D, ...) conține legea federală și, prin urmare, nu se află în NFBC. Atribut CU este determinant, dar nu o posibilă cheie. Pentru a efectua descompunerea relației R se creează două relaţii R1 (A, B, C, ...)Și R2 (C, D), dintre care unul este alocat Legii federale. Această descompunere este descompunere fără pierderi cu legătură naturală. În continuare, din aceleași poziții, se iau în considerare relațiile R1 și R2.

În al doilea rând, care este criteriul de alegere a unei funcții fizice pentru efectuarea proiecției (vom vedea mai târziu cât de semnificativ poate fi aceasta). Este clar că FS cu determinanți în partea stângă ar trebui selectate ca candidați pentru proiecție. Cu toate acestea, dependențele cu determinanți pot fi de natură tranzitivă și aici este util să se aplice prima regulă generală pentru alegerea unei funcții fizice pentru efectuarea unei proiecții - „regula lanțului”. Regula lanțului este următoarea:

Dacă, atunci dependența cea mai din dreapta sau „sfârșitul lanțului” este folosită ca FZ pentru a implementa proiecția.

Metode de proiectare bazate pe sinteza relațiilor

Câteva probleme ale metodei de descompunere

Algoritmul metodei de descompunere a relațiilor nu este perfect. Lumea dreptului federal este foarte diversă. Este un instrument de lucru bun și, ținând cont de tipurile de legi federale, poate fi îmbunătățit. Să fim atenți la două situatii problematice legate de utilizarea metodei de descompunere. Să existe o relație R(A, B, C, D, ...) din exemplul de mai sus.

Prima situație: în procesul de descompunere se pierde Legea federală, iar dacă relația R1 și R2 va fi folosit pentru crearea unei baze de date, nu se poate garanta că relațiile dintre aceste atribute vor fi introduse corect în baza de date. Aceasta conduce la a doua regulă empirică pentru selectarea unui FL pentru efectuarea unei proiecții: nu ar trebui să utilizați un FL ca FL pentru efectuarea unei proiecții dacă partea stângă a acestuia este determinantă pentru un alt FL. Această problemă este rezolvată prin aplicarea regulii de înlănțuire.

A doua situație: un atribut depinde de doi determinanți - o cheie posibilă (A, C) si doi determinant AȘi CU. Această situație este mai critică. Relația nu este în BCNF; nu există lanțuri de legi federale în relație, iar regula lanțului nu este aplicabilă acesteia. Această problemă nu este rezolvată de metoda standard descompunere. Soluția este de a descompune relația inițială în două relații, care se bazează pe afirmația că toate legile federale cu aceiași determinanți trebuie separate în grupuri separate și fiecărui astfel de grup trebuie să i se atribuie propria relație. Relațiile rezultate ar trebui verificate pentru conformitatea cu BCNF. Această abordare a proiectării unui model logic al unei baze de date relaționale se numește metoda de sinteză. Metoda de sinteză poate fi utilizată fie independent, fie în combinație cu metoda de descompunere prin proiecție. Exemplele oferite oferă o perspectivă asupra unui număr de deficiențe potențiale ale descompunere ca metodă de proiectare a modelelor logice ale bazelor de date relaționale.

Înainte de a trece la studiul metodei de sinteză, să luăm în considerare utilizarea elementelor de sinteză în descompunere. După cum puteți vedea, descompunerea devine mai complicată în prezența legilor fizice tranzitive. O caracteristică a unei legi federale tranzitive este redundanța acesteia. O lege federală este, în general, considerată redundantă dacă conține informații care pot fi obținute din alte legi federale din baza de date. Excluderea FZ tranzitivă redundantă din baza de date se poate face fără a afecta negativ rezultatele acesteia. Redundanța este inerentă nu numai legilor fizice tranzitive și, prin urmare, este recomandabil să excludeți legile fizice redundante înainte de a aplica algoritmul de descompunere.

Conceptul de metode de sinteză a relaţiilor

Puteți elimina redundanța în setul original de legi funcționale prin aplicarea regulilor de deducere a legilor fizice (Vezi elementul de antrenament „Dependențe funcționale”). După cum se știe, pentru clasa de dependențe F este suficient să folosiți șase astfel de reguli. În acest caz, criteriul de oprire a procedurii de excludere poate fi primirea acoperirii minime set original Lege federala.

Neunicitatea acoperirilor minime indică faptul că ordinea în care sunt eliminate FD redundante poate avea un impact asupra rezultatelor obținute. Regula generală urmează:

Excesul de FZ trebuie eliminat unul câte unul, analizând de fiecare dată setul rezultat de FZ pentru redundanță.

În concluzia studiului algoritmilor bazați pe descompunerea relațiilor, trebuie subliniate două circumstanțe, dintre care prima indică avantajul metodelor bazate pe sinteza relaţiilor, iar al doilea este un dezavantaj al ambelor abordări.

Primul. Dacă o relaţie universală conţine un numar mare de atribute, de exemplu, mai mult de trei duzini, apoi proiectarea manuală devine intensivă în muncă și poate, pe de o parte, să conducă la mult timp și, pe de altă parte, să genereze un număr inacceptabil de relații în baza de date pentru practică. Prin urmare, în acest caz, ar trebui să vă gândiți la automatizarea procesului de proiectare, adică. creați un program de proiectare a schemei bazei de date.

Al doilea. Procesul de proiectare a bazelor de date relaționale este caracterizat de o natură matematică complexă. Se arată că problema de proiectare este o problemă NP-hard, adică. Este imposibil să se construiască un algoritm de descompunere universal - un algoritm pentru „toate cazurile de viață”, a cărui execuție ar dura mai puțin decât timpul exponențial, cu un număr de pași proporțional cu e N, Unde N- numărul de atribute.

În plus, sarcina de a aduce relațiile originale la BCNF poate să nu fie fezabilă. Acest fapt a avut loc în practica de proiectare. Deoarece BCNF poate să nu existe pe un anumit set de legi federale, ar fi logic să renunțăm la cerința de a aduce relațiile cu bazele de date în acest formular. Această situație este susținută și teoretic: pentru orice set dat de dependențe F peste circuit r Puteți construi o schemă de bază de date în 3NF.

Astfel, ne vom limita la căutarea 3NF în timpul aplicării metodei de sinteză, în timp ce rămân probleme asociate cu efectuarea operațiilor asupra datelor.

Algoritmul metodei sintezei relaţiilor

ÎN aceasta sectiune oferă doar o privire de ansamblu asupra algoritmului sinteza relaţiilor.

Am analizat deja exemple de descompunere cu pierderea limitelor fizice. Motivul pierderii unei funcții fizice este o anumită funcție fizică care nu poate fi exclusă din setul de dependențe F asociate relațiilor rezultate. R1 sau R2. Astfel, esența problemei se rezumă la încălcarea închiderii operațiunilor relaționale cu privire la Legea federală privind schema bazei de date rezultată. Pentru a o rezolva, este necesar să se reînnoiască acoperirea minimă a Legii federale sau, după cum se spune, să se întărească acoperirea minimă.

Pentru a rezolva această problemă, ar fi bine să întărim toate legile federale, legându-le cu chei unice, să zicem, prin descrierea de indici unici pentru ele. Apoi puteți monitoriza integritatea bazei de date. Pentru a face acest lucru, trebuie să întăriți acoperirea minimă. În linii mari, puterea acoperirii minime înseamnă că a fost identificat un set de chei primare și toate legile federale din acoperirea minimă au fost revizuite în prisma acestui set din punctul de vedere al deductibilității legilor federale ale baza de date în cauză.

Să introducem o definiție.

Definiție 4. O bază de date relațională se numește completă dacă:

· toate FZ-urile sunt întărite cu chei;

· toate relațiile sunt în 3NF;

· Nu există nicio opțiune de bază de date cu mai puține scheme care să satisfacă proprietățile de mai sus.

Aproape întotdeauna în domeniul subiectului unei baze de date este posibil să se identifice un set de relații care au proprietatea de completitudine. Teorema [Meyer] a fost demonstrată că există un algoritm care derivă o bază de date completă dintr-un set de legi fizice date.

Deoarece un astfel de algoritm construiește o schemă de bază de date direct dintr-un set dat de legi federale, este numit algoritm de sinteză a bazei de date. În acest caz, problema reprezentării corecte a relației cu o schemă dată prin proiecțiile ei vine în prim-plan, i.e. conexiunile din schema de bază de date rezultată pot fi false. Cu toate acestea, dacă acoperirea minimă a setului inițial de legi federale este consolidată, atunci acest fenomen poate fi evitat.

Exemplu. Cheie universală și conexiuni false

Lasă atitudinea R are tupluri:

1 1 1 1

4 1 2 2

Cazul 1: Fără conexiuni false

Împărțirea în relații

R1 =ABC și R2 =BCD

1 1 1	1 1 1
4 1 2	1 2 2

nu oferă conexiuni false.

Cazul 2. Prezența conexiunilor false

Împărțirea în relații

R1 = AB și R2 = BCD

1 1	1 1 1
4 1	1 2 2

oferă conexiuni false

ABCD

1 1 1 1	1 1 2 2
4 1 1 1	4 1 2 2

Din moment ce, puteți rezolva problema introducând cheia universală(A,C). Apoi puteți adăuga relația la diagrama originală

A.C.

1 1

1 2

și efectuați o unire de relație AB, BCD și AC , care va restabili raportul inițial ABCD .

Rețineți că atributul A acționează ca o cheie în aproape toate legile federale. Un atribut selectat sau adăugat care are o proprietate similară se numește cheie universală. Deci, soluția la problema îmbinărilor false este adăugarea unui subcircuit care conține cheia universală și efectuarea îmbinării folosindu-l.

Acum putem trece la o prezentare generală a algoritmului de sinteză a bazei de date relaționale.

Teoretic, se arată că pentru a sintetiza o bază de date completă, este necesar să se construiască o acoperire minimă inelă pentru setul original de FD.

Să introducem o notație. O lege federală compusă se numește lege federală: , unde Y poate fi goală. Fiecare componentă a legii federale poate fi asociată cu un set de legi federale: . Fie C un set de legi federale compuse, fd(C)- ansamblul tuturor legilor federale asociate cu legile federale din S.

În notația acceptată, principalele etape ale algoritmului sinteza relaţiilor sunt date mai jos.

Algoritm pentru sinteza pas cu pas a relațiilor

Intrare: F- set de legi federale ale domeniului subiect al bazei de date

Ieșire: Schemă completă a bazei de date

Etapa 1. Găsirea acoperirii neredundante F 1 pentru F

Pentru fiecare lege federală din F se verifică dacă o anumită lege federală poate fi derivată din celelalte legi federale. Dacă da, atunci Legea federală este ștearsă. Etapa se termină după ce ai căutat prin toate legile federale din F. În urma acestei etape, se obține un set de legi federale F 1.

Etapa 2: Elemente reducătoare din stânga F 1

Atributele sunt eliminate succesiv unul după altul din părțile din stânga ale Legii Federale F 1; se verifică dacă FL rezultat poate fi derivat din FL original F 1 F 1 F 2.

Etapa 3. Reducerea elementelor din dreapta F 2

Atributele Legii Federale sunt eliminate succesiv una după alta din părțile drepte ale Legii Federale. F 2; se verifică dacă Legea federală inițială poate fi derivată din Legea federală primită și din legile federale existente F 2. Dacă da, atunci legea federală inițială este înlocuită cu o nouă lege federală. Etapa se termină după ce ai căutat toate legile federale F 2. Rezultatul este o multitudine de legi federale F 3.

Aceasta încheie reducerea Legii federale. Nu există redundanță. Este necesar să începeți construirea unei acoperiri minime.

Etapa 4. Separarea F 3 la clasele de echivalență din partea dreaptă

Se construiește partiția F 3în grupuri: două FZ aparțin aceluiași grup dacă și numai dacă părțile lor din dreapta sunt echivalente. Rezultatul este un set de clase de echivalență ale legilor federale.

Etapa 5. Înlăturarea legilor federale redundante în clasele de echivalență

Pentru toate perechile de legi federale fd iȘi fd j din aceeași grupă, se verifică dacă FZ din partea stângă fdj din partea dreapta fd j să fie eliminate din acest grup de legi federale. Dacă da, atunci de la fd j FZ este eliminat și adăugat la partea dreapta această lege federală la dreapta fd i. Noua lege federală va fi în același grup cu legea federală inițială. Rezultatul este numărul minim de legi federale F 5, acoperire F 3.

Etapa 6. Obținerea claselor de echivalență din partea stângă F 5și legile federale constitutive C 1

Pentru fiecare set de FD-uri cu părțile stângi echivalente de la F 5 se creează o lege federală compozită. Dacă vreun atribut din Y este in X i, atunci acest atribut este eliminat. Rezultatul este un set de legi federale compuse C 1.

Pasul 7: Eliminați dependențele redundante din C 1

Pentru fiecare lege federală compusă din C 1și pentru fiecare atribut X i atributele din partea stângă a lui C sunt mutate în partea dreaptă. Rezultatul este un set de legi federale compuse CU". Dacă fd(C") echivalent fd(C 1), Acea C 1 este înlocuit cu CU". Rezultatul este o multitudine de legi federale C 2.

Etapa 8. Formarea unei acoperiri minime inelare

Pentru fiecare lege federală compusă c din C 2și fiecare atribut A atributul este eliminat din partea dreaptă a c A. Rezultatul este CU", constând din Cu". Dacă fd(C") echivalent fd(C 2), Acea C 2 este înlocuit cu CU". Rezultatul este o multitudine de legi federale C 3.

Etapa 9. Formarea unei scheme complete de bază de date

Pentru fiecare componentă a legii federale Cu din C 3 se formează un tabel de atribute care apar în Cu. Cheile pentru acest tabel sunt Xi din partea stângă Cu. Tabelul va servi la consolidarea Legii Federale în F.

Algoritm pas cu pas sinteza relaţiilor are convergenta buna, este indicat sa il folosesti in forma programata. Pentru aceasta puteți deja folosi program gata făcut, sau scrieți propriul program ținând cont de specificul sarcinilor dvs., apelând la monografia lui D. Meyer.

Crearea unui model logic al unei baze de date relaționale folosind metoda de descompunere: transformare ER-diagrame în relaţiile de baze de date

Practica proiectării bazelor de date relaționale folosind metoda de descompunere a relațiilor a arătat o serie de dezavantaje asociate cu pierderea datelor în timpul conexiunilor și pierderea legilor fizice. Cu toate acestea, metoda de descompunere este destul de simplu de înțeles, vizuală și ușor de implementat în instrumental CAZ-instrumente de proiectare și este în prezent cel mai des folosit în proiectarea bazelor de date.

Pentru a construi modele logice ale bazelor de date relaționale folosind metoda descompunerii, au fost formulate o serie de reguli, numite reguli pentru conversia diagramelor ER în relații de bază de date. Regulile elimină potențialele deficiențe ale metodei de descompunere și vizează aducerea diagramei relațiilor bazei de date la forme normale.

Să luăm în considerare regulile de transformare folosind exemplul unei baze de date a profesorilor care susțin prelegeri la un institut. Esența Profesorului este legată de esența Subiectului prin legătura Lecturii. În acest caz, sunt posibile următoarele opțiuni de comportament pentru acest domeniu:

1. fiecare profesor predă un singur curs, iar fiecare curs este predat de un singur profesor, adică. sunt necesare clasele de membru ale ambelor entități;

2. fiecare profesor predă un singur curs, iar fiecare curs este predat de cel mult un profesor, adică. clasa de membru a primei entități este obligatorie, iar clasa de membru a celei de-a doua entități este opțională;

3. fiecare profesor nu preda mai mult de un curs, iar fiecare curs este predat de cel mult un profesor, i.e. Clasele de membru ale ambelor entități sunt opționale;

4. Fiecare profesor nu predă mai mult de un curs, iar fiecare curs este predat de un singur profesor.

Sunt posibile opțiuni cu un grad diferit de conexiune, de exemplu, atunci când fiecare profesor poate preda mai multe cursuri.

Fiecare dintre aceste opțiuni poate fi reprezentată printr-o diagramă ER. Cu toate acestea, trebuie amintit că fiecare diagramă ER reprezintă propriul set de reguli de comportament de domeniu și doar una dintre ele poate fi adevărată în orice moment.

Dacă se determină gradul de relație binară, atunci relațiile preliminare pot fi obținute prin vizualizarea mai multor alternative și selectarea opțiunii care este cea mai potrivită în ceea ce privește regulile de domeniu și preferințele personale ale designerului. Caracteristicile definitorii ale alegerii unuia dintre opțiuni alternative Reprezentările relațiilor sunt gradul de conexiune și clasa de membru al entității.

Să formulăm prima regulă.

Regula 1. Dacă gradul unei relații binare este 1:1 și clasa de apartenență a ambelor entități este obligatorie, atunci este necesară construirea unei singure relații. În acest caz, cheia primară a unei relații poate fi cheia oricărei entități.

Relația inițială este în același timp relația finală.

Regula 2. Dacă gradul unei relații binare este 1:1 și clasa de membru a unei entități este obligatorie, iar cealaltă entitate este opțională, atunci este necesară construirea a două relații - una pentru fiecare entitate. În acest caz, cheia primară a fiecărei relații este cheia entității sale, iar cheia entității cu clasa de apartenență opțională este adăugată la relația pentru entitatea cu clasa de membru necesară ca atribut (migrarea cheii).

Această regulă poate fi aplicată în a doua opțiune, când relația inițială necesită deja descompunere. Atitudine inițială PROFESOR_1 conține o problemă de valoare nulă: date despre articol care nu pot fi citite acest moment, nu poate fi introdus în baza de date.

Relația rezultată PROFESOR_2 nu are problema valorilor nule. Relația ITEMS rezultată elimină această problemă prin definirea unei valori implicite speciale, nevide pentru un articol care nu este în prezent citit. Migrarea cheii este necesară pentru a restabili relația inițială. Astfel, migrarea cheii în metoda de descompunere este transferul cheii primare a unei relații la o altă relație pentru a preveni pierderea datelor în timpul îmbinării.

Să formulăm a treia regulă.

Regula 3. Dacă gradul unei relații binare este 1:1 și clasa de apartenență a ambelor entități nu este obligatorie, atunci este necesară construirea a trei relații - una pentru fiecare entitate obiect și una pentru relația de legătură. În acest caz, cheia fiecărei entități este cheia primară a relației corespunzătoare și o relație pentru relație, cu cheia primară compusă din cheile entităților obiect. Această regulă poate fi aplicată în a treia variantă a comportamentului domeniului, când relația inițială trebuie împărțită în trei relații. Împărțirea în două relații nu va elimina problema valorilor nule. În cazul a trei relații, această problemă este eliminată: relația ITEMS definește o valoare implicită nevidă pentru un articol care nu este în prezent citit.

Să formulăm a patra regulă.

Regula 4. Dacă gradul unei conexiuni binare 1:N , iar clasa de membru a unei entități n-conectate este obligatorie, atunci este suficient să construiți două relații - una pentru fiecare entitate. În acest caz, cheia fiecărei entități este cheia primară a relației corespunzătoare, iar cheia entității legate de 1 este adăugată la relația pentru n -entitate conectată ca atribut.

Să formulăm a cincea regulă.

Regula 5. Dacă gradul unei conexiuni binare este 1:N și clasa de membru al unei entități n-conectate nu este obligatorie, atunci este necesar să se construiască trei relații - câte una pentru fiecare entitate. În acest caz, cheia fiecărei entități este cheia primară a relației corespunzătoare și o relație pentru conexiune. Cheile de entitate trebuie să fie atribute ale ultimei relații.

Rețineți că dacă gradul unei conexiuni binare 1:N, atunci factorul care determină alegerea uneia dintre reguli (regulile 4, 5) este clasa de membru al entității n-conectate. Clasa de membru a unei entități conectate 1 nu afectează rezultatul final al descompunerii. În situația regulii 4, există o problemă de valori nule pentru atributul Subiect, în situația regulii 5, există o problemă de valori nule pentru atributele Subiect și Profesor. Prin urmare, pentru a evita duplicarea și valorile nule în situația regulilor 4 și 5, este necesar să se construiască două, respectiv trei relații rezultate. Se efectuează o migrare a cheii de entitate cu 1 legătură pentru a restabili relația de alăturare inițială.

Dacă gradul de conexiune binară N:M, apoi pentru a evita dublarea și valorile nule, este întotdeauna necesar să construiți trei relații. Să formulăm a șasea regulă.

Regula 6. Dacă gradul unei conexiuni binare M:N , atunci este necesar să se construiască trei relații - una pentru fiecare entitate și o relație pentru conexiune. În acest caz, cheia fiecărei entități este cheia primară a relației corespunzătoare și este inclusă în compozit cheia principala relatie pentru comunicare.

Pentru o relație cu trei sau mai multe, sunt necesare cel puțin patru relații pentru a evita redundanța și valorile nule. Să formulăm a șaptea regulă.

Regula 7. Dacă relația este trilaterală, este necesar să se construiască patru relații - câte una pentru fiecare entitate. În acest caz, cheia fiecărei entități este cheia primară a relației corespunzătoare și o relație pentru conexiune. Cheile de entitate trebuie să fie atribute ale ultimei relații.

În mod similar, o relație cu n căi necesită construcția n+1 relatii.

Rețineți că toate regulile formulate mai sus sunt construite pe un principiu general: fiecare atribut non-cheie are propria sa relație, de exemplu. migrarea atributelor non-cheie este interzisă.

Trebuie amintit că după partiționarea preliminară a relației originale, este necesar să se arate, folosind cheile FZ și relația, că schema de bază de date relațională rezultată este în Boyce-Codd NF (BCNF) (sau 3NF). Numai atunci schema de relații rezultată poate fi considerată finală. De obicei, proiectanții de baze de date nu efectuează astfel de acțiuni atunci când folosesc metoda de descompunere, deoarece în majoritatea cazurilor (dar nu întotdeauna!) aplicarea regulilor de transformare produce BCNF.

În unele cazuri, se poate dovedi că entitățile și relațiile existente nu sunt suficiente pentru a crea un model logic al domeniului bazei de date. Una dintre ele este situația în care instanțe ale aceleiași entități joacă roluri diferite (supertip/subtip) în domeniul bazei de date. Acest lucru se datorează prezenței unei ierarhii sau a unei relații de agregare incluziune între instanțe de entitate. În acest caz, entitatea este o mulțime cu o relație de ordine asupra instanțelor, ceea ce duce la prezența unor clase de echivalență care au interpretări semantice diferite în domeniul subiectului.

De exemplu, baza de date a unei secții de institut conține două categorii de angajați - profesori și șeful de catedre. Seful de catedra poate si prelegeri pe subiecte, dar de obicei primeste un salariu fix; Profesorii au o rată de plată pe oră. Să încercăm să prezentăm informații despre angajații departamentului într-un mod mai adecvat. Să selectăm o entitate separată pentru fiecare categorie de angajați ai departamentului și să luăm în considerare diagrama ER a șefului. Departamentul supraveghează profesorii.

În acest caz, cheia fiecărei entități va fi numărul de personal al angajatului. Pentru că Communication Guides are o diplomă 1:N, iar clasa de apartenență a ambelor entități este obligatorie, atunci conform regulii 4 este suficient să construim două relații preliminare. Deoarece atributele non-cheie Nume și Adresă_Angajat sunt plasate în ambele relații preliminare, conform principiului general al regulilor de transformare, ele trebuie să fie suprascrise pentru una dintre relații. Redenumirea atributelor într-una dintre relații ridică problema răspunsului la interogare: pentru a găsi telefon fix angajat specific, este necesar să se reconsidere ambele relații și să construiască o uniune a rezultatelor vizionarii. Astfel, redenumirea atributelor, la care designerii recurg uneori în grabă, nu este o soluție bună.

Să luăm în considerare o altă opțiune pentru prezentarea datelor despre angajații departamentului. Să considerăm că șeful de departament și profesorii sunt angajați și să ne imaginăm funcțiile lor ca roluri pe care le poate juca un anumit angajat. Atunci relația ANGAJAT este o relație părinte - un supertip pentru două relații subordonate - subtipuri MANAGER. CATEA și PROFESOR, care sunt conectate prin conexiunea Supervizează.

Relația părinte - supertip - conține atribute comune relațiilor subtipului subordonat. Relații subordonate - subtipurile conțin informații specifice rolurilor lor. Fiecare relație generată de un rol este conectată la o relație generală printr-un atribut al domeniului general, în acest caz numărul de personal. Setul final de relații va consta din trei relații.

Relații rezultate:

ANGAJAT (#angajat, atribute comune pentru toți angajații)

MANAGER (#manager, ....)

PROFESOR (#profesor, ..., #șef)

Rețineți că relația care leagă două roluri ale unei entități originale se numește recursivă (angajați care gestionează angajați). O relație care conectează rolurile a două entități diferite nu este recursivă.

Pentru a evita căutarea pentru a identifica tipul de job al unui angajat, puteți introduce un atribut suplimentar în relația generică care specifică cine este angajatul. În ciuda faptului că din punctul de vedere al teoriei bazelor de date relaționale, această tehnică duce la redundanța datelor, se recurge la ea pentru a crește performanța sistemului.

Să formulăm a opta regulă.

Regula 8. Entitatea originală servește ca sursă pentru generarea unei relații. Cheia de entitate este cheia de relație. Entitățile subordonate (elementele de rol) și conexiunile care le conectează generează un număr de relații care sunt determinate de un set de reguli 1-7, iar fiecare element de rol este tratat ca o entitate obișnuită.

Exemplu de conversie a diagramelor ER în relații cu baze de date

Să demonstrăm aplicarea metodei descompunere (fără pierderi cu conexiune naturală) să creeze un model logic și o bază de date care să susțină activitățile unei mici firme de consultanță. Compania oferă consultanță și instruire clienților săi obișnuiți; datele clienților stocate în baza de date vor fi folosite de consultanții firmei pentru a desfășura seminarii, orele practice si consultatii.

Primul pas în proiectarea bazei de date este identificarea tuturor entităților din domeniu, atributele acestora și relațiile dintre atributele entităților. Analiza informațiilor de domeniu acest exemplu vă permite să definiți următoarele atribute relație universalăși trageți o concluzie despre prezență dependențe funcționale(FZ) între ele:

1. Fiecare client are propriul său număr de înregistrare (denumit în continuare numărul). Toate numerele de clienți sunt unice și diferite. Numărul determină în mod unic Numele de familie, dar nu invers. .

2. Fiecare client se află la o anumită adresă, la care pot fi localizați mai mulți clienți. .

3. Să presupunem că un singur telefon este asociat cu o anumită adresă. .

4. Fiecărui client i se poate atribui un număr de telefon. .

5. Pentru fiecare client, se stabilește un rating (activitate, frecvența solicitărilor etc.) pentru perioada pe o anumită temă. Evaluarea clientului este determinată în mod unic de numărul său.

6. Consultările sunt de natură tematică. Fiecare subiect are propriul său ID.

7. Perioada reprezintă perioada de timp în care s-a desfășurat consultarea tematică. Pentru a fi concret, să numim această perioadă un semestru.Să enumerăm legile federale ale domeniului subiect al bazei de date:

Sa luam in considerare determinanți si posibile chei ale relatiei de CONSULTANT.

Chei posibile	Determinanți
(număr, subiect, semestru)	(număr, subiect, semestru)
	(Număr)
	(Telefon)
	(Abordare)

Conform criteriului lui Codd, deoarece nu orice determinant dintr-o relație este o cheie posibilă, relația nu este în BCNF. Să descompunem relația CONSULTANT R0 (Număr, Subiect, Semestru, Prenume, Adresă, Telefon, Rating). Următoarele legi federale sunt candidate pentru proiecție:

Atenţie! În practică, nu există unicitate în reprezentarea relațiilor de baze de date, datorită alegerii legii federale la ruperea relațiilor. Alegerea lui FZ pentru a efectua proiecția relațională este foarte pas importantîn proiectarea unui model logic al unei baze de date relaţionale. Alegerea FZ-urilor alternative pentru a efectua proiecția poate avea ca rezultat diferite baze de date!

Să verificăm dacă relația R2 este în BCNF.

Relația R2 este în BCNF.

Să verificăm dacă relația R1 este în BCNF.

Chei posibile	Determinanți
(număr, subiect, semestru)	(număr, subiect, semestru)
	(Număr)
	(Abordare)

Relația R1 nu este în NFDB este necesar să se continue descompunerea acesteia. Să selectăm Legea federală și să împărțim R1 în R3 (Număr, Subiect, Semestru, Evaluare) și R4 (Număr, Nume, Adresă).

Să verificăm dacă relația R3 este în BCNF.

Chei posibile	Determinanți
(număr, subiect, semestru)	(număr, subiect, semestru)

Relația R3 este în BCNF.

Să verificăm dacă relația R4 este în BCNF.

Chei posibile	Determinanți
(Număr)	(Număr)

Relația R4 este în BCNF. Descompunerea este completă.

Rețineți că dacă inițial, în exemplul nostru, FL ar fi fost ales ca FZ pentru a efectua proiecția, atunci ca rezultat am fi avut un set complet diferit (!) de relații.

Descompunerea diagramelor de relații

Una dintre modalitățile de a reduce o relație arbitrară la forma formelor normale (cu excepția 1 NF) este descompunerea relațiilor.

· Descompunerea unei scheme de relații R este înlocuirea acesteia cu un set de scheme r=(R 1 , R 2 , ... , R K), unde R i Ì R și R i astfel încât R 1 ÈR 2 È... ÈR K = R, în acest caz, nu este necesar ca R i Ç R j =Æ, deși acest lucru este permis.

Efectuarea descompunerii conduce la faptul că relația nou obținută va fi proiecții ale relației inițiale pe noi scheme de relații din mulțimea r.

Înainte de a efectua descompunerea, trebuie să vă asigurați că conectarea noilor relații va da relația originală.

Proiectarea bazei de date include construirea de diagrame conceptuale și logice, precum și rezolvarea unui număr de probleme, dintre care cea mai importantă este problema asociată cu afișarea și menținerea corectă a unei baze de date semantice (problema de integritate).

Problema de integritate este asociată cu asigurarea fiabilității datelor în posibile situații de urgență și utilizare rațională resurse de calcul pentru a asigura o eficiență ridicată a interacțiunii cu baza de date Eficiența presupune asigurarea cantității necesare de stocare a informațiilor și a timpului de interacțiune cu baza de date.

Integritatea în baza de date este reflectată prin construirea unei diagrame logice.

Un circuit logic este exprimat în termeni obiecte sau entitatiși legăturile dintre ele. Conexiuni pot fi interpretate și ca obiecte de altă natură, iar în acest sens, atât entitățile, cât și conexiunile din modelele relaționale sunt exprimate în mod egal sub formă de relații. În acest caz, vorbim despre obiecte - entități și obiecte - conexiuni. Setul de relații care alcătuiesc baza de date și depind unele de altele reflectă semantica (sensul) datelor din domeniul de studiu.

· Dacă starea bazei de date nu corespunde semanticii relațiilor dintre date, atunci acest fenomen se numește încălcarea datelor sau a integrității bazei de date.

Pentru a asigura integritatea datelor, este necesar să se asigure integritatea obiectelor și integritatea referințelor la aceste obiecte. În plus, obiectele din baza de date trebuie să fie unice (nerepetate) și recunoscute, iar referințele la obiecte nu trebuie să existe fără obiecte.

Pe lângă restricțiile naturale care nu depind de o anumită aplicație, integritatea bazei de date este determinată de restricțiile asociate cu aplicație specifică. se numesc restricţii de acest fel limitări de integritate a aplicației. Ele sunt exprimate ca un set de afirmații care surprind modul în care sunt utilizate datele într-un anumit domeniu.

Restricțiile de aplicare sunt împărțite în:

Constrângeri statice și de tranziție;

Restricții la tupluri și seturi;

Constrângeri de integritate amânate și imediate.

· Restricții statice - acele restricții care sunt satisfăcute indiferent de starea bazei de date.

· Sunt denumite constrângerile plasate între vechile și noile valori ale atributelor restricții de tranziție.

Exemplu : La actualizarea valorii atributului „presiune”, noua valoare nu trebuie să difere de cea veche cu mai mult de 20%.

· Constrângeri de tuplu- acele restrictii pentru care verificarea indeplinirii lor se realizeaza folosind un singur tuplu al relatiei.

Un caz special al unei astfel de limitări este constrângere de atribut.

· Restricție pentru seturi - dacă reprezintă o constrângere asupra unei valori rezultate rezultate din utilizarea unei colecţii de tupluri.

Exemplu : la măsurarea temperaturii, următoarea valoare nu trebuie să difere de media mobilă Mx (așteptările matematice curente) cu o anumită valoare e. Toate valorile care nu se încadrează în intervalul [ M x - e, M x + e] sunt eliminate.

· Restricții urgente se numesc cele care permit posibile verificări executarea lor concomitent cu modificarea valorilor datelor din relație.

· Restricții amânate Acestea sunt restricții pentru care verificarea îndeplinirii lor are sens după finalizarea următorului set de operațiuni.

Pentru o constrângere amânată, următorul concept este relevant:

· Element logic muncă - gestionarea continuă a datelor, în care baza de date este transferată dintr-o stare integrală în alta stare integrală. Această tehnică se mai numește și tranzacție.

Conceptul de tranzacție este strâns legat de fiabilitatea datelor. În timpul tranzacției pot apărea erori hardware sau software. Dacă o tranzacție nu este finalizată ca urmare a unor eșecuri, atunci integritatea bazei de date este încălcată. Pentru a asigura integritatea bazei de date sub constrângeri amânate, utilizați metode de rollback. Esența lor este că o tranzacție începută, dar neterminată este anulată, iar baza de date este transferată starea initiala, de la care a început tranzacția (astfel are loc un rollback).

Descompunerea diagramei de relații R = (A 1, A 2, ..., A n) înlocuirea lui cu o colecție de submulțimi se numește R, astfel încât combinarea lor dă R. În acest caz, este permis ca submulțimile să se intersecteze.

Algoritmul de descompunere se bazează pe următoarea teoremă.

Teorema de descompunere. Lăsa R(A, B, C) – atitudine, A, B, C - atribute.

Dacă R satisface dependenţele A->B Acea R este egală cu unirea proiecțiilor sale A, B Și A, C

R(A, B, C) = R(A, B), R(A, C)

La normalizare, este necesar să alegeți descompuneri care au proprietatea conexiunii fără pierderi. În acest caz, descompunerea trebuie să asigure că interogările (eșantionarea datelor în funcție de condiție) la relația inițială și relațiile obținute ca urmare a descompunerii vor da același rezultat. Condiția corespunzătoare va fi îndeplinită dacă fiecare relație de tuplu R poate fi reprezentat ca legătura naturală proiecțiile sale pe fiecare dintre submulțimi. Pentru a verifica dacă descompunerea are această proprietate, se folosesc algoritmi speciali descriși în literatură (nediscutați în această carte).

A doua cea mai importantă proprietate dezirabilă a descompunerii este proprietatea de a păstra dependențele funcționale. Dorința de descompunere pentru a păstra dependențele este firească. Dependențe funcționale sunt câteva restricții asupra datelor. Dacă descompunerea nu are această proprietate, atunci pentru a verifica dacă condițiile de integritate nu sunt încălcate la introducerea datelor ( dependențe funcționale), trebuie să conectăm toate proiecțiile.

Astfel, pentru o proiectare a bazei de date construită corect, este necesar ca descompunerea să aibă proprietatea de îmbinări fără pierderi și este de dorit ca acestea să aibă proprietatea de a păstra dependențele funcționale.

8.4 Selectarea unui set rațional de scheme de relații prin normalizare

A doua formă normală (2NF)

O relație este în 2NF dacă este în 1NF și fiecare atribut non-cheie depinde de întreaga cheie primară (nu depinde de o parte a cheii).

Pentru a converti o relație în 2NF, trebuie să utilizați operația de proiecție, descompuneți-l în mai multe relații după cum urmează:

1. construiți o proiecție fără atribute situate în dependență funcțională parțială de la cheia primară;
2. construiți proiecții în părți cheie compusăși atributele care depind de aceste părți.

A treia formă normală (3NF)

O relație este în 3NF dacă este în 2NF și fiecare atribut al cheii este dependent intransitiv de cheia primară.

O relație este în 3NF dacă și numai dacă toate atributele non-cheie ale relației sunt reciproc independente și complet dependente de cheia primară.

Se pare că orice schemă de relații poate fi redusă la 3NF prin descompunere, care are proprietățile conexiunii fără pierderi și păstrarea dependenței..

Motivația pentru a treia formă normală

Al treilea forma normala elimină redundanța și anomaliile de includere și eliminare.

Din păcate, 3NF nu previne toate anomaliile posibile.

Forma normală Boyce-Codd (NFBF)

Dacă în R pentru fiecare dependență X->A , Unde A nu apartin X, X include o cheie, atunci se spune că această relație este în forma normala Boyce-Codd.

Determinantul unei dependențe funcționale este un grup minim de atribute de care depinde un alt atribut sau grup de atribute, iar această dependență este netrivială..

O relație este în BCNF dacă și numai dacă fiecare dintre determinanții săi este o cheie potențială.

BCNF este o versiune mai strictă a 3NF. Cu alte cuvinte, orice relație care este în BCNF este în 3NF. Reversul nu este adevărat.

Motivația pentru forma normală Boyce-Codd

ÎN forma normala Boyce-Codd nu există redundanțe și anomalii de includere, ștergere și modificare. Rezultă că orice schemă de relații poate fi redusă la formă normală Boyce-Codd în așa fel încât descompunerea să aibă proprietatea conexiunii fără pierderi. Cu toate acestea, o schemă de relație poate fi ireductibilă în BCNF, păstrând în același timp dependențele. În acest caz, trebuie să vă mulțumiți cu al treilea forma normala.

8.5. Exemplu de normalizare la 3NF

Pentru a îmbunătăți structura unei baze de date relaționale (eliminarea eventualelor anomalii), este necesar să aduceți toate tabelele bazei de date la a treia forma normala sau într-o formă superioară (dacă este posibil). Astfel, sarcina se rezumă la verificarea normalizării tuturor entităților mapate la tabelele bazei de date. Dacă tabelul care rezultă dintr-o entitate nu este tabelul din a treia forma normala, apoi trebuie înlocuit cu mai multe tabele situate în al treilea forma normala.

Să luăm în continuare exemplul cu relația RAPORT DE EXAMINARE

La începutul acestei prelegeri am dat relația cu primul forma normala.

Cod student	Nume de familie	Cod de examen	Articol	Data	Nota
1	Sergheev	1	Matematică	5.08.03	4
2	Ivanov	1	Matematică	5.08.03	5
1	Sergheev	2	Fizică	9.08.03	5
2	Ivanov	2	Fizică	9.08.03	5

Cheia acestei relații va fi un set de atribute – Codul studentului și Codul examenului.

Pentru o descriere mai concisă a procesului de normalizare, introducem următoarea notație:

KS – cod student, EC – cod examen, F – prenume, P – subiect, D – data, O – nota.

O vom scrie dependențe funcționale

KS, KE -> F, P, D, O KS, KE -> F KS, KE -> P KS, KE -> D KS, KE -> O CE -> P CE -> D KS -> F

Conform definiției, relația este în a doua forma normala(2NF), dacă este în 1NF și fiecare atribut non-cheie depinde de cheia primară și nu depinde de o parte a cheii. Aici atributele P, D, F depind de o parte a cheii. Pentru a scăpa de aceste dependențe, este necesară descompunerea relației. Pentru a face acest lucru, folosim teorema de descompunere.

Avem relația R(KS, F, CE, P, D, O). Să luăm dependența KS -> Ф în conformitate cu formularea teoremei, relația inițială este egală cu combinația proiecțiilor sale R1(KS, Ф) și R2(KS, CE, P, D, O).

În raport cu R1(KS, Ф) există dependenta functionala KS -> Ф, cheia KS este un atribut compus, non-cheie Ф nu depinde de o parte a cheii. Această relație este în 2NF. Deoarece nu există dependențe tranzitive în această relație, relația R(KS, Ф) este în 3NF, după cum este necesar.

Se consideră relația R2(KS, CE, P, D, O) cu cheia compusă KS, CE. Există o dependență aici KE -> P, KE -> D, KE -> P, D. Atributele P, D depinde de o parte a cheii, prin urmare

Nu există anomalii de redundanță sau includere, ștergere sau modificare în forma normală Boyce-Codd.. Rezultă că orice diagramă de relații poate fi redusă la forma normală Boyce-Codd în așa fel încât descompunerea să aibă proprietatea conexiunii fără pierderi. Cu toate acestea, o schemă de relație poate fi ireductibilă în BCNF, păstrând în același timp dependențele. În acest caz, trebuie să ne mulțumim cu a treia formă normală.

8.5. Exemplu de normalizare la 3NF

Pentru a îmbunătăți structura unei baze de date relaționale (eliminarea eventualelor anomalii), este necesar să aduceți toate tabelele bazei de date la a treia formă normală sau la o formă superioară (dacă este posibil). Astfel, sarcina se reduce la verificarea normalizării tuturor entităților mapate la tabelele bazei de date. Dacă tabelul rezultat dintr-o entitate nu este un tabel în a treia formă normală, atunci acesta trebuie înlocuit cu mai multe tabele care sunt în a treia formă normală.

Să luăm în continuare exemplul cu relația RAPORT DE EXAMINARE

La începutul acestei prelegeri am adus relația cu prima formă normală.

Cheia acestei relații va fi un set de atribute – Codul studentului și Codul examenului.

Pentru a scrie mai pe scurt procesul de normalizare, introducem următoarea notație:

KS – codul studentului, EC – codul examenului, F – numele de familie, P – subiectul, D – data, nota O.

Să notăm dependențele funcționale

KS, CE la F, P, D, O

KS, KE la F

KS, CE la P

KS, KE la D

KS, CE à O

Prin definiție, o relație este în a doua formă normală (2NF) dacă este în 1NF și fiecare atribut non-cheie depinde de cheia primară și este independent de partea cheie. Aici atributele P, D, F depind de o parte a cheii. Pentru a scăpa de aceste dependențe, este necesară descompunerea relației. Pentru a face acest lucru, folosim teorema de descompunere.

Avem o atitudine R(KS, F, CE, P, D, O). Să luăm dependența KS à Ф în conformitate cu formularea teoremei: relația inițială este egală cu combinația proiecțiilor sale R 1(KS, F) și R 2(KS, CE, P, D, O).

Într-o relație R 1(KS, F) există o dependență funcțională KS à F, cheia KS este un atribut compus non-cheie F nu depinde de o parte a cheii. Această relație este în 2 NF. Deoarece nu există dependențe tranzitive în această relație, relația R(KS, F) este în 3NF, după cum este necesar.

Luați în considerare relația R 2(KS, KE, P, D, O) cu o cheie compusă KS, KE. Aici există o dependență CE à P, CE à D, CE à P, D. Atributele P, D depind de o parte a cheii, prin urmare relația nu este în 2NF. În conformitate cu teorema de descompunere, relația inițială (folosim dependența funcțională FE à P, D) este egală cu legătura proiecțiilor R 3(KE, P, D), R 4(KS, CE, O). Într-o relație R 3(KE, P, D) există dependențe funcționale ale KE à P, KE à D, KE à P, D. Nu există dependențe ale atributelor non-cheie pe o parte a cheii, prin urmare relația este în 2NF. De asemenea, nu există dependențe tranzitive în această relație, prin urmare relația este în 3NF.

Astfel, relația inițială este redusă la trei relații, fiecare dintre ele fiind în a treia formă normală R 1(KS, F), R 3(KE, P, D), R 4(KS, CE, O).

Rețineți că în ceea ce privește R 4 atribute KS, CE sunt chei externe folosite pentru a stabili conexiuni cu alte relații. Să prezentăm modelul rezultat sub forma unei diagrame obiect-relație (diagrama ER). Pentru claritate și posibilitatea programării ulterioare, să trecem la nume englezești obiecte (relaţii) şi atribute.

Atitudine R 1 reprezintă un obiect student cu atribute id_st (cheie primară), nume.

Atitudine R 3 reprezintă obiectul exam_st cu atributele id_ex (cheie primară), subiect, dată.

Atitudine R 4 reprezintă un obiect mark_st cu atributele id_st (cheie externă), id_ex (cheie externă), mark. Cheia primară aici este id_st, id_ex.

Diagrama ER corespunzătoare este prezentată în Fig. 8.1.

Orez. 8.1. Diagrama ER reprezentând fragmentul considerat al domeniului subiectului.

8.6. Parte integrantă model relațional.
Implementarea condițiilor de integritate a datelor în SGBD modern

Să reamintim că integritatea bazei de date înseamnă că aceasta conține informații complete, consecvente și care reflectă în mod adecvat subiectul (corecte). Menținerea integrității în bazele de date relaționale se bazează pe îndeplinirea următoarelor cerințe.

1. Se numește prima cerință cerința integrității entității. Un obiect sau o entitate a lumii reale din bazele de date relaționale corespunde tuplurilor de relații. În mod specific, cerința este ca orice tuplu al oricărei relații să se distingă de orice alt tuplu al acelei relații, adică, cu alte cuvinte, orice relație trebuie să aibă o anumită cheie primară. Această cerință este satisfăcută automat dacă proprietățile de bază ale relațiilor nu sunt încălcate în sistem.

2. Se numește a doua cerință Cerința de integritate referențială. Evident, dacă relațiile sunt normalizate, entitățile complexe ale lumii reale sunt reprezentate într-o bază de date relațională sub forma mai multor tupluri ale mai multor relații. Comunicarea între relații se realizează folosind migrarea cheilor.

Exemplu cheie externă.

ELEV (Cod Elev, Nume) susține EXAMEN (Cod Elev, Materia, Notă).

Este apelat atributul Student Code al entității EXAMEN cheie externă , deoarece valorile sale caracterizează în mod unic entitățile reprezentate de tupluri ale unei alte relații - relația Student (presupunem că câmpul Cod student este cheia relației Student).

O relație în care este definită o cheie străină se spune că face referire la o relație corespunzătoare în care același atribut este cheia primară.

Cerința de integritate referențială sau cerința cheii străine este aceea că pentru fiecare valoare a cheii străine din relația de referință, trebuie să existe un tuplu în relația la care se face referire cu aceeași valoare a cheii primare, sau valoarea cheii străine trebuie să fie nedefinită (adică nu indica orice).

Constrângerile privind integritatea entității și referențiale trebuie să fie suportate de SGBD. Pentru a menține integritatea entității, este suficient să ne asigurăm că nu există tupluri cu aceeași valoare a cheii primare în orice relație. (În Access, o implementare specială a unui câmp întreg este concepută pentru aceasta - un câmp de tip „Contor”.) Cu integritate referențială, lucrurile sunt ceva mai complicate.

Este clar că atunci când actualizați o relație de referință (inserarea de noi tupluri sau modificarea unei valori a cheii străine în tuplurile existente), este suficient să vă asigurați că nu apar valori incorecte ale cheii străine.

Dar ce zici de eliminarea unui tuplu dintr-o relație de referință?

Există trei abordări aici, fiecare dintre ele susținând integritatea referențială. Prima abordare este de a interzice ștergerea unui tuplu referit (adică trebuie să ștergeți mai întâi tuplurile de referință sau să modificați valorile cheii străine ale acestora în consecință). În a doua abordare, atunci când un tuplu referit este șters, valoarea cheii externe din toate tuplurile de referință devine automat nedefinită. În cele din urmă, a treia abordare (ștergerea în cascadă) este aceea că atunci când un tuplu este șters dintr-o relație de referință, toate tuplurile de referință sunt șterse automat din relația de referință.

În SGBD-urile relaționale mature, este de obicei posibil să alegeți cum să mențineți integritatea referențială pentru fiecare situație individuală de definire a cheii externe. Desigur, pentru a lua o astfel de decizie, este necesar să se analizeze cerințele unui anumit domeniu de aplicare.

Rețineți că toate SGBD-urile moderne acceptă atât integritatea entității, cât și integritatea referențială, dar permit utilizatorilor să dezactiveze aceste restricții și astfel să construiască baze de date care nu sunt conforme cu modelul relațional. Experiența arată că o abatere de la prevederile de bază ale modelului relațional duce la un câștig pe termen scurt - algoritmii devin mai simpli, dar ulterior complică serios sarcina, în special întreținerea acesteia.

Rezumat scurt: Prelegerea este dedicată optimizării schemelor de relații (structura unei baze de date relaționale) pe baza metodelor formale ale teoriei bazelor de date relaționale. Aici luăm în considerare o serie de concepte necesare pentru aceasta (dependență funcțională, forme normale, descompunerea schemelor de relații). Este analizat un exemplu de reducere a unui tabel la a treia formă normală, care este optimă în ceea ce privește un număr de indicatori (excluzând anomaliile de redundanță, includere și ștergere). Sunt luate în considerare problemele implementării integrității datelor în SGBD relațional.

Prelegerea discută despre utilizarea aparatelor formale pentru optimizarea schemelor de relații. Se formulează problema alegerii schemelor relaționale raționale și a modului de implementare a unei astfel de alegeri prin normalizare (transformarea secvențială a schemei relaționale într-un număr de forme normale). Pentru a descrie formal procesul corespunzător, se definesc conceptul de dependență funcțională (dependența între atributele unei relații), o cheie, se formulează regulile pentru derivarea unui set de dependențe funcționale și conceptul de descompunere a unei diagrame de relații. Sunt definite prima, a doua, a treia formă normală și forma normală Boyce-Codd. Este dat un exemplu de normalizare la 3NF. Sunt luate în considerare aspectele implementării condițiilor de integritate a datelor în SGBD-urile relaționale.

Problemele acestei prelegeri sunt discutate în.

Teste de referință

Sarcina 1. Care este sarcina de a alege modele raționale de relații?

Opțiunea 1.

Ce probleme sunt eliminate prin alegerea modelelor de relații raționale?

ð+ duplicare

ð+ potenţială controversă

ð+ pierderi potențiale de informații

ð+ posibilitatea ca informațiile să nu fie incluse în baza de date

ð creșterea numărului de scheme de relații

Opțiunea 2.

Ce cauzează principala duplicare a informațiilor într-o bază de date relațională?

ð cu repetare linii identiceîntr-un singur tabel

ð cu repetarea coloanelor identice într-un singur tabel

ð+ cu repetarea valorilor identice ale atributelor într-un singur tabel

ð cu repetarea valorilor de atribute identice în mese diferite

Opțiunea 3.

Ce anomalii trebuie abordate la proiectarea unei baze de date relaționale?

ð creare

ð+ îndepărtare

ð+ actualizări

ð+ includere

ð închide

Sarcina 2. Cum este folosit mecanismul pentru a selecta modele raționale de relații?

Opțiunea 1.

Cum se realizează alegerea schemelor de relații raționale?

ð+ prin normalizare

ð+ prin transformarea secvenţială a relaţiilor într-un număr de forme normale

ð prin combinarea schemelor de relaţii

ð+ prin descompunerea modelelor de relaţii

Opțiunea 2.

Ce este normalizarea?

ð+ transformarea secvenţială a relaţiilor într-un număr de forme normale

ð o asociere specifică a modelelor relaționale

ð+ o anumită descompunere a schemelor de relaţii

ð transformarea relaţiilor folosind operaţii de algebră relaţională

Opțiunea 3.

Care este prima formă normală?

ð+ valorile tuturor atributelor relației sunt simple

ð+ valorile tuturor atributelor relației sunt indivizibile

ð+ valorile tuturor atributelor relației sunt atomice

ð valorile tuturor atributelor relației sunt tupluri

ð valorile unor atribute de relație sunt atomice

ð valorile unor atribute de relație sunt tupluri

Sarcina 3. Descrie dependențe funcționale.

Opțiunea 1.

Ce s-a întâmplat X definește funcțional Y?

ð+ fiecare valoare a setului X Y

ð+ X Y

ð Y este o funcție X

ð Y depinde de X

ð fiecare valoare a setului Y asociat cu o valoare a setului X

ð dacă două tupluri au aceleași valori Y, atunci ele coincid în valori X

Opțiunea 2.

Ce caracterizează dependențele funcționale?

ð diagrama relațiilor

ð+ Toate valori posibile relaţie

ð+ toate valorile posibile ale șirurilor de relații

ð+ relația ca variabilă

Opțiunea 3.

Cum puteți utiliza dependențe funcționale pentru securitate integritate logică Bază de date?

ð+ ca constrângeri de integritate

ð+ pentru a verifica dacă o dependență funcțională este satisfăcută la actualizarea datelor

ð pentru a verifica funcționarea corectă programe de aplicație

ð pentru generarea automată a datelor relevante

Sarcina 4. Cum se realizează normalizarea tiparelor de relație?

Opțiunea 1.

Ce este descompunerea schemei de relații?

ð înlocuirea schemei de relații R = {A 1 , A 2 , …A n) un set de submulţimi R: R 1, R 2 astfel încât R = R 1 Ç R 2

ð+ înlocuirea schemei de relații R = {A 1 , A 2 , …A n) un set de submulţimi R: R 1, R 2 astfel încât R = R 1 È R 2

ð înlocuirea schemei de relații R = {A 1 , A 2 , …A n)un set de submulţimi R: R 1, R 2 astfel încât R = R 1 R 2

ð înlocuirea schemei de relații R = {A 1 , A 2 , …A n)un set de submulţimi R: R 1, R 2 astfel încât R = R 1 + R 2

Opțiunea 2.

Cum este formulată teorema de descompunere?

ð+ Dacă R(A, B, C) satisface dependenţele Aà B, Acea R egală cu legătura proiecţiilor

R(A, B), R(A, C)

ð Dacă R(A, B, C) satisface dependenţele Aà B, Acea R egală cu legătura proiecţiilor

R(A, B), R(B, C)

ð Dacă R(A, B, C) satisface dependenţele Aà B, Acea R egală cu legătura proiecţiilor

R(A, C), R(B, C)

ð+ Dacă R(A, B, C) satisface dependenţele Aà B, Acea R egală cu legătura proiecţiilor

R(A, C), R(A, B)

Opțiunea 3.

Ce proprietăți ar trebui să aibă descompunerea în timpul normalizării?

ð+ păstrarea dependențelor funcționale

ð+ conexiuni fără pierderi

ð partiţionare fără pierderi

ð salvând cheia

Sarcina 5. Reducere la a doua formă normală.

Opțiunea 1.

În ce condiții este o relație în a doua formă normală?

ð+ dacă este în prima formă normală și fiecare atribut non-cheie depinde de întreaga cheie primară

ð dacă este în prima formă normală și fiecare atribut non-cheie depinde de o parte a cheii primare

ð dacă este în prima formă normală și fiecare atribut non-cheie este independent de cheia primară

ð+ dacă este în prima formă normală și fiecare atribut non-cheie este independent de partea cheie primară

Opțiunea 2.

Cum se realizează reducerea la a doua formă normală?

ð+

ð mai întâi diagrama de relații este redusă la prima formă normală

ð descompunerea se realizează folosind o dependență funcțională în care un atribut non-cheie depinde de întreaga cheie primară

ð descompunerea se realizează folosind o dependență funcțională în care un atribut non-cheie depinde de un atribut non-cheie

Opțiunea 3.

Ce anomalii sunt eliminate prin a doua formă normală?

ð îndepărtare

ð redundanţă

ð actualizări

ð includere

ð+ nici unul

Sarcina 6. Reducere la a treia formă normală.

Opțiunea 1.

În ce condiții este o relație în a treia formă normală?

ð dacă este în a doua formă normală și fiecare atribut non-cheie depinde de întreaga cheie primară

ð dacă este în a doua formă normală și fiecare atribut non-cheie este dependent în mod intransitiv de o parte a cheii primare

ð+ dacă este în a doua formă normală și fiecare atribut care nu este cheie este dependent în mod intransitiv de cheia primară

ð dacă este în a doua formă normală și fiecare atribut non-cheie este independent de partea cheie primară

Opțiunea 2.

Cum se realizează reducerea la a treia formă normală?

ð descompunerea se realizează folosind o dependență funcțională în care un atribut non-cheie depinde de o parte a cheii primare

ð+ mai întâi diagrama de relații este redusă la a doua formă normală

ð+ descompunerea se realizează folosind o dependență funcțională în care un atribut non-cheie depinde în mod tranzitiv de cheia primară

ð descompunerea se realizează folosind o dependență funcțională în care un atribut non-cheie depinde intransitiv de cheia primară

Opțiunea 3.

Ce anomalii sunt eliminate prin a treia formă normală?

ð îndepărtare

ð+ redundanţă

ð actualizări

ð+ includere

ð+ nici unul

Sarcina 7. Analiza dependențelor funcționale ale următoarei relații.

Opțiunea 1.

Care dintre următoarele dependențe există în acest sens?

ð+ Cod student →Nume

ð+ Subiect→Data

ð+ Cod examen →Data

ð Cod elev→Notă

Opțiunea 2.

Care dintre următoarele dependențe nu există în acest sens?

ð Cod student, Nume→Nume

ð Subiect→Data

ð Cod examen →Data

ð+ Cod elev→Notă

ð Cod student, Subiect→Notare

Opțiunea 3.

În ce dependență este definită cheia primară a relației?

ð Cod student, Nume→Nume, Subiect

ð Subiect→Data

ð Cod examen →Data

ð Cod elev→Notă

ð Cod student, Subiect→Notare

ð+ Cod student, cod subiect →Data, nota

Sarcina 8. Cum este menținută integritatea datelor în SGBD-urile relaționale?

Opțiunea 1.

Ce cerințe trebuie îndeplinite pentru a menține integritatea datelor în SGBD-urile relaționale?

ð+ unicitatea oricărui tuplu de relație

ð+ orice relație are o cheie primară

ð+

ð

Opțiunea 2.

Care sunt constrângerile de entitate și de integritate referențială?

ð+ Pentru fiecare valoare de cheie străină din relația de referință, trebuie să existe un tuplu cu aceeași valoare de cheie primară în relația de referință.

ð pentru fiecare valoare a cheii primare din relația de referință, trebuie să existe un tuplu cu aceeași valoare a cheii străine în relația de referință

ð trebuie să existe instanțe de entități

ð+ instanțele de entitate trebuie să fie identificate în mod unic

Opțiunea 3.

Ce opțiuni pentru susținerea constrângerilor de integritate referențială sunt utilizate în SGBD-urile moderne?

ð+ este interzisă ștergerea unui tuplu care este referit.

ð+ Când un tuplu referit este șters, valoarea cheii externe din toate tuplurile de referință este înlocuită cu nedefinit

ð+ Când un tuplu referit este șters, toate tuplurile de referință sunt eliminate din relația de referință

ð la ștergerea unui tuplu care este referit, relația de referință este ștearsă

Literatură

1. Karpova T. Baze de date. Modele, dezvoltare, implementare. – Sankt Petersburg: Peter, 2001. – 304 p.

2. Connolly T., Begg K., Strachan A. Baze de date: proiectare, implementare și întreținere. Teorie și practică. Ed. a II-a: Trad. din engleza – M.: Editura„Williams”, 2000. – 1120 p.

3. Ullman J.D., Widom J. Introducere în sistemele de baze de date: Trans. din engleza – M.: Lori, 2000. – 374 p.

4. Khomonenko A.D., Tsygankov V.M., Maltsev M.G. Baze de date: manual pentru universități. – Sankt Petersburg: print CORONA, 2000. – 416 p.

5. Tolstobrov A.P. Management de date. Tutorial. Voronej: Editura Universității de Stat Voronezh, 2007 – 205 p.

6. Hansen G., Hansen J. Baze de date: dezvoltare și management: Trad. din engleza – M.: ZAO „Editura „BINOM”, 1999. – 704 p.

7. Data K.J. Introducere în sistemele de baze de date: Transl. din engleza – Ed. a VI-a. – K.: Dialectică, 1998. – 784 p.

8. Shvetsov V.I., Vizgunov A.N., Meerov I.B. Bază de date. Tutorial. Nijni Novgorod: Editura Universității de Stat Nijni Novgorod, 2004. 271 p.

Curs 9. Modele de date fizice
(nivel intern)

Prelegerea este dedicată problemelor de organizare fizică a datelor în memoria computerului. Aici este descrisă structura memoriei computerului și, ținând cont de caracteristicile acesteia, structurile de stocare a datelor în operaționale și memorie externa.

Termeni cheie: modele fizice de date, structuri de stocare, reprezentare a datelor în memoria computerului, înregistrare fizică, fișier secvenţial, structură listă, B-tree, funcție hash, indexare.

Scopul prelegerii: dați o idee despre principal metode standard organizarea datelor în memoria computerului într-un SGBD cu evaluarea modelelor corespunzătoare din punct de vedere al timpului de acces la datele din baza de date și al cantității de memorie ocupată.

După cum sa menționat deja, schema conceptuală specificată pentru SGBD este mapată automat în structura de stocare de către programele SGBD. Este posibil ca un utilizator extern să nu știe nimic despre modul în care vizualizarea lor asupra datelor este organizată fizic în memorie sistem de calcul. Cu toate acestea, timpul necesar pentru rezolvarea problemelor aplicate depinde în mod semnificativ de plasarea fizică a datelor în memoria computerului. În acest sens, chiar și pe una dintre etapele inițiale proiectarea bazei de date - etapa de selectare a unui SGBD, este recomandabil să se cunoască capabilitățile structurilor fizice de stocare reprezentate de SGBD-uri specifice și să se evalueze caracteristicile de sincronizare ale bazei de date proiectate ținând cont de aceste capacități.

Metodele de organizare fizică a datelor în diferite SGBD sunt de obicei diferite și sunt determinate de tipul de computer utilizat, mijloace instrumentale Dezvoltarea SGBD, precum și criteriile care ghidează dezvoltatorii SGBD atunci când aleg metodele de stocare a datelor și modalitățile de acces la aceste date. Rețineți că cel mai comun criteriu este timpul de acces la date, dar criteriul poate fi ales, de exemplu, prin complexitatea implementării metodelor corespunzătoare.

Această prelegere va discuta modele fizice tipice de organizare a datelor în SGBD-uri specifice.

Modelele de date fizice sunt folosite pentru a afișa modele de date. Principalele concepte ale modelului de date sunt câmp, înregistrare logică, fișier logic. Cuvântul „logic” este introdus pentru a distinge conceptele legate de modelul de date logic de conceptele legate de model fizic date. Conceptele de bază ale modelului de date fizice utilizate pentru a reprezenta modelul de date logic sunt câmp, înregistrare fizică, fișier fizic. În special, o înregistrare logică constând din câmpuri poate fi reprezentată ca o înregistrare fizică (din aceleași câmpuri), un fișier logic - ca dosar fizic. Înainte de a specifica conceptele legate de modelul fizic de date, să luăm în considerare structura memoriei computerului.

9.1. Structura memoriei computerului

Cea mai importantă caracteristică Memoria computerului, care determină în mare măsură metodele de organizare a datelor și de accesare a acestora, este eterogenitatea acesteia. Sunt două tipuri diferite memorie – RAM (RAM) și memorie externă (EP), iar procesorul funcționează numai cu date din RAM (Fig. 9.1.).

Orez. 9.1. Diagrama de funcționare a computerului

După cum s-a menționat de multe ori, bazele de date sunt create pentru a lucra cu acestea volume mari date, ceea ce necesită utilizarea memoriei externe. Prin urmare, organizarea datelor și accesul la acestea trebuie să țină cont atât de specificul fiecărui tip de memorie, cât și de metodele de interacțiune a acestora.

Să notăm principalele proprietăți ale RAM:

· unitatea de memorie este un octet;

· memoria este direct adresabilă (fiecare octet are o adresă);

· Procesorul selectează datele necesare procesării prin adresarea directă a secvenței de octeți care conțin aceste date.

Să notăm principalele proprietăți ale memoriei externe:

· unitatea minimă adresabilă este o înregistrare fizică;

· pentru prelucrarea ulterioară (de exemplu, lucrul cu câmpuri), înregistrarea trebuie citită RAM;

· timpul de citire a unei înregistrări în OP (scrierea unei înregistrări din OP în VP) este cu câteva ordine de mărime mai mare decât timpul în care procesorul procesează o înregistrare din OP;

· organizarea schimbului se realizează pe porţiuni, deoarece Este imposibil să citiți întreaga bază de date simultan.

9.2. Reprezentare logică a instanței de înregistrare

O înregistrare logică este reprezentată în RAM după cum urmează:

Adresarea directă pe octeți permite procesorului să selecteze câmpul dorit pentru procesare.

Rețineți că această reprezentare nu face diferența între înregistrările din rețea, modelele ierarhice și relaționale. În cazul modelelor de rețea și ierarhice, unele câmpuri pot fi pointeri, apoi secvența de octeți utilizată pentru stocarea acestor câmpuri conține adresa de început a secvenței de octeți corespunzătoare înregistrării membru al relației.

Majoritatea SGBD-urilor moderne folosesc un format de înregistrare cu lungime fixă. În acest caz, toate înregistrările au aceeași lungime, determinată de lungimea totală a câmpurilor care compun înregistrarea. În SGBD-uri, alte formate de înregistrare (lungime variabilă, lungime nedefinită) sunt mult mai puțin comune, astfel încât aceste formate nu sunt discutate în această carte. Rețineți că câmpurile înregistrării care iau valori în mod semnificativ lungimi diferiteîn diferite cazuri de înregistrări în domeniul subiectului ele apar destul de des. Un exemplu ar fi câmpul CV-ul din înregistrarea ANGAJAT. Un CV poate fi o jumătate de pagină de text, o pagină etc. Problema care apare este cum să reprezinte această informație cu lungime variabilă într-o înregistrare cu lungime fixă. Opțiune posibilă este de a seta dimensiunea câmpului corespunzător la valoarea maximă. În acest caz, pentru multe cazuri de înregistrare, câmpul specificat nu va fi completat complet și, astfel, memoria computerului va fi utilizată ineficient. O metodă mai eficientă și mai frecvent utilizată în SGBD pentru organizarea unor astfel de înregistrări este următoarea. În loc de un câmp (câmpuri) care iau valori de lungimi semnificativ diferite, înregistrarea include un câmp indicator către zona de memorie în care va fi localizată valoarea câmpului original. De obicei, această zonă este o zonă de memorie externă acces direct. În procesul de introducere a valorii corespunzătoare, în zona alocată este ocupată atâta memorie cât lungimea acestei valori.

În fig. 9.2 oferă un exemplu de reprezentare de mai sus a instanțelor de înregistrare din N câmpuri, iar câmpul N ia valori de lungimi în mod corespunzător diferite pentru diferite cazuri de înregistrare.

Orez. 9.2. Reprezentarea câmpurilor cu lungime variabilă

O implementare specifică a unei astfel de scheme este un câmp de tip MEMO într-un SGBD (dBase III+, FoxPro, Access etc.).

9.3. Organizarea schimburilor între operaționale
și memorie externă

Unitatea de schimb de date dintre RAM și memoria externă este o înregistrare fizică. Înregistrare fizică citit (scris) într-un singur acces la memoria externă. În special, o înregistrare fizică poate corespunde unei instanțe a unei înregistrări logice. Numărul de accesări la memorie externă atunci când se lucrează cu baza de date determină timpul de răspuns al sistemului. În acest sens, pentru a reduce numărul de accesări la baza de date atunci când lucrați cu aceasta, lungimea înregistrării fizice este mărită (mai multe instanțe de înregistrări logice sunt combinate într-o singură înregistrare fizică). În acest caz, înregistrarea fizică se mai numește și bloc, numărul k de copii ale înregistrărilor logice care alcătuiesc înregistrarea fizică se numește coeficient de blocare.

Introducerea datelor inițiale în baza de date se efectuează după cum urmează:

· k instanţe de înregistrări logice (tupluri) sunt introduse secvenţial în OP;

· k instanțe introduse sunt combinate într-o înregistrare fizică (bloc);

· înregistrarea fizică este stocată în memoria externă.

Introduceți k instanțe ale înregistrărilor tabelului sursă care alcătuiesc i-a fizicăînregistrare, prezentată în fig. 9.3.

Orez. 9.3. Schemă pentru înregistrarea înregistrărilor în memoria externă

Datele stocate în memoria externă sunt procesate după cum urmează:

· o înregistrare fizică (bloc) este citită în RAM;

· sunt procesate cazuri de înregistrări logice din interiorul blocului (se selectează câmpurile necesare, se compară câmpul cheie cu valoare dată, se ajustează câmpurile, se efectuează operațiuni de ștergere etc.).

În unele SGBD (de exemplu, MS SQL Server) unitatea de schimb dintre RAM și memoria externă este o pagină (un tip de înregistrare fizică, a cărei dimensiune este fixă ​​și nu depinde de lungimea înregistrării logice). Organizarea schimbului dintre RAM și memoria externă în acest caz este similară cu cea descrisă mai sus. Diferența aici va fi că cazurile de înregistrări logice sunt formate într-un buffer de dimensiunea unei pagini) dacă dimensiunea paginii nu este un multiplu al lungimii înregistrării logice, pagina poate fi completată incomplet, înregistrarea fizică pe medii externe, în consecință, nu va fi complet completat).

9.4. Structuri de stocare a datelor în memoria externă a computerului

În SGBD-urile moderne, modelele de date tabulare sunt cele mai răspândite. În acest sens, dar și pentru o mai mare claritate, în această secțiune vom vorbi despre structurile de stocare pentru modelul tabelar. Cu toate acestea, rețineți că unele dintre structurile de stocare discutate mai jos pot fi utilizate și pentru a reprezenta modele de rețea și ierarhice.

Ca memorie externă o considerăm cea mai comună în calculatoare moderne memorie cu acces direct. Memoria cu acces direct face posibilă accesarea oricărei înregistrări dacă adresa acesteia este cunoscută. Pentru a simplifica prezentarea, nu vom specifica un număr de câmpuri de serviciu pe care le conține o înregistrare fizică și vom omite luarea în considerare a acestora.

9.4.1. Amplasarea secvenţială a înregistrărilor fizice

În această structură de stocare, înregistrările sunt plasate secvenţial una după alta în memorie. După cum sa menționat deja, presupunem că toate înregistrările sunt de lungime egală. Adresa fizică a unei înregistrări poate fi calculată cu ușurință din numărul înregistrării (pentru a o calcula, trebuie să cunoașteți formatul înregistrării fizice corespunzătoare).

Fișă fizică cu număr eu conține înregistrări logice cu numere

(eu– 1) k+1

(eu– 1) k+2

(eu– 1) k+k

eu = 1, 2, …, ;

semnul denotă cel mai apropiat număr întreg mai mare sau egal cu N/k, numărul întreg de mai sus.

Să ne uităm la modul în care operațiile elementare de bază ale modelului de date sunt implementate în această structură de stocare și să estimăm numărul acestor operații. Să reamintim că din punctul de vedere al utilizatorului în modelul de date tabelar, aceste operații sunt operații pe rândurile (coloanele) tabelului.

Normalizarea și descompunerea relațiilor

Anomalii de modificare a datelor

După întocmirea unei diagrame conceptuale (logice) a bazei de date, este extrem de important să se verifice absența anomaliilor de modificare a datelor. Cert este că dacă schema bazei de date este proiectată incorect, pot apărea anomalii în executarea operațiunilor de modificare a datelor. Aceste anomalii se datorează structurii limitate a RMD (absența agregatelor etc.).

Să luăm în considerare aceste anomalii folosind exemplul unei relații cu următoarele atribute (atributele incluse în cheie sunt subliniate):

LIVRARE ( Numărul de livrare, Numele produsului, Prețul produsului, Cantitatea, Data livrării, Numele furnizorului, Adresa furnizorului)

Există trei tipuri de anomalii: anomalii de actualizare, ștergere și adăugare. O anomalie de actualizare poate apărea atunci când informațiile sunt duplicate. Alte anomalii apar atunci când două sau mai multe entități sunt combinate într-o relație. De exemplu:

1. Actualizare anomalie: într-o relație LIVRA poate apărea dacă adresa unui furnizor s-a schimbat. Trebuie făcute modificări la toate tuplurile corespunzătoare livrărilor de la acest furnizor; altfel datele vor fi inconsecvente.
2. Anomalie de ștergere: Când ștergeți înregistrările tuturor livrărilor de la un anumit furnizor, toate datele despre acest furnizor se vor pierde.
3. Anomalie de adaos: în exemplul nostru, va apărea dacă s-a încheiat un acord cu furnizorul, dar nu au fost încă livrări de la acesta. Informațiile despre un astfel de furnizor nu pot fi introduse în tabel. LIVRA , deoarece o cheie (numărul de livrare și numele produsului) și alte atribute necesare nu sunt definite pentru aceasta.

Pentru a rezolva problema anomaliilor de modificare a datelor la proiectarea unei baze de date relaționale, relațiile sunt normalizate.

În cadrul modelului de date relaționale, E.F. Codd a dezvoltat un aparat pentru normalizarea relațiilor și a propus un mecanism care permite ca orice relație să fie convertită la a treia formă normală. Normalizarea unei scheme de relații se realizează prin descompunerea schemei.

Descompunerea unei scheme de relaţii R se numeşte de obicei înlocuirea ei printr-un set de scheme de relaţii A i astfel încât

şi nu se cere ca relaţiile Ai să fie disjunse. Descompunerea relației nu ar trebui să ducă la pierderea dependențelor dintre atributele entității. Pentru descompunere, trebuie să existe o operație de algebră relațională, a cărei aplicare ne va permite să restabilim relația inițială.

Să demonstrăm normalizarea folosind exemplul relației CĂRȚI (Tabelul 8.1):

ID	- identificator (cheie primară),
Cod	- codul antetului (conform BBK - bibliotecă și clasificare bibliografică),
Temă	- titlul secțiunii (conform BBK),
Titlu	- titlul cartii,
Autor	- autori),
Editor	- editor(i),
Tip	- tipul publicației (manual, tutorial, colecție etc.),
An	- anul publicării
pg	- număr de pagini

Tabelul 8.1. Atitudine inițială CĂRȚI

Normalizarea și descompunerea relațiilor - concept și tipuri. Clasificarea și caracteristicile categoriei „Normalizarea și descompunerea relațiilor” 2017, 2018.