Descompunerea relațiilor

Construcția unui model SADT începe cu reprezentarea întregului sistem sub forma celei mai simple componente - un bloc și arce care ilustrează interfețe cu funcții în afara sistemului. Deoarece un singur bloc reflectă sistemul ca întreg, numele specificat în bloc este generic. Acest lucru este valabil și pentru arcurile de interfață - ele corespund și setului complet interfețe externe sisteme ca un întreg. Blocul care reprezintă sistemul ca un singur modul este apoi detaliat într-o altă diagramă folosind mai multe blocuri conectate prin arcuri de interfață. Aceste blocuri definesc principalele subfuncții ale funcției originale. Această descompunere dezvăluie Set complet subfuncții, fiecare dintre acestea fiind afișată ca un bloc, ale căror limite sunt definite de arcuri de interfață. Fiecare dintre aceste subfuncții poate fi descompusă într-un mod similar pentru mai multe detalii.

În toate cazurile, fiecare subfuncție poate conține doar acele elemente care sunt incluse în funcția originală. În plus, modelul nu poate omite niciun element, adică. bloc părinte iar interfețele sale oferă context. Nimic nu poate fi adăugat la el, nimic nu poate fi eliminat din el.

Modelul SADT este o serie de diagrame cu documentație însoțitoare care se defalcă obiect complexîn părți componente, care sunt descrise ca blocuri. Detaliile fiecăruia dintre blocurile principale sunt prezentate ca casete în celelalte diagrame. Fiecare diagramă de detaliu este o descompunere a unui bloc din diagrama de nivel anterioară. La fiecare pas de descompunere se numeste diagrama nivelului anterior părintească pentru o diagramă mai detaliată.

Arcuri care intră și ies dintr-un bloc într-o diagramă nivel superior, sunt aceleași cu arcele care intră și ies din diagrama de nivel inferior, deoarece blocul și diagrama descriu aceeași parte a sistemului. Un exemplu de model funcțional (3 nivele) este prezentat în figurile 13-15.

Figura 13 - Model funcțional domeniul subiectului « Salon de mobila" Diagrama de nivel 0

Figura 14 - Modelul funcțional al domeniului tematici „Showroom de mobilă”. Diagrama nivelului 1

Figura 15 - Modelul funcțional al domeniului tematici „Showroom de mobilă”. Diagrama nivelului 2

7.2.2 Proiectare folosind metoda entitate-relație

La scenă design conceptual Pe baza modelului funcțional dezvoltat se construiește un model informațional al bazei de date. Scopul modelării informaționale este de a oferi dezvoltatorului sistemelor informaționale economice o schemă conceptuală a bazei de date sub forma unui model sau mai multor modele locale, care poate fi reflectată relativ ușor în orice sistem de baze de date.

Fiecare sistem informatic, în funcție de scopul său, se ocupă de o parte a lumii reale, care este de obicei numită domeniul (software) al sistemului. Software-ul se poate aplica oricărui tip de organizație: bancă, universitate, fabrică, magazin etc.

Noțiuni de bază proiectarea folosind metoda „entitate-relație” sunt: ​​entitate, relație, atribut.

Entitate– un obiect real sau imaginar care este semnificativ pentru domeniul subiectului luat în considerare. Este necesar să se facă distincția între concepte precum tipul de entitate și instanța entității. Conceptul de „tip de entitate” se referă la un set de indivizi omogene, obiecte, evenimente sau idei care acționează ca un întreg. O instanță de entitate se referă la un anumit lucru dintr-un set. De exemplu, tipul de entitate poate fi CITY, iar instanța poate fi Moscova, Kiev etc. Domeniul subiectului Sistem informatic este o colecție de obiecte reale (entități) care sunt de interes pentru utilizatori.

Fiecare entitate trebuie să aibă identificator unic. Fiecare instanță a unei entități trebuie să fie identificabilă în mod unic și distinctă de toate celelalte instanțe de acest tip esență. Fiecare entitate trebuie să aibă anumite proprietăți:

· avea nume unic; aceeași interpretare trebuie aplicată aceluiași nume; nu se poate aplica aceeași interpretare nume diferite, cu excepția cazului în care sunt pseudonime;

· au unul sau mai multe atribute care fie aparțin entității, fie sunt moștenite printr-o relație;

· au unul sau mai multe atribute care identifică în mod unic fiecare instanță a unei entități.

Fiecare entitate poate avea orice număr de conexiuni cu alte entități din model.

Relaţie– o asociere denumită între două entități care este semnificativă pentru domeniul în cauză. O relație este o asociere între entități în care fiecare instanță a acestei entități este asociată cu un număr arbitrar (inclusiv zero) de instanțe ale celei de-a doua entități și invers.

Entitățile acoperite de o relație sunt numite participanți la acea relație. Numărul de participanți la comunicare determină gradul tipului de comunicare. Tipurile de comunicare sunt împărțite după grad în:

· bidirecțional – o relație la care participă două entități;

· tripartit – se referă la relații complexe, care implică trei entități;

· patrulater – se referă la conexiuni complexe, în el sunt implicate patru entități;

· recursiv – o relație în care aceleași entități participă de mai multe ori în roluri diferite. În aceste cazuri, relațiilor li se pot atribui nume de rol.

Cea mai comună comunicare este bidirecțională. Relațiile bidirecționale sunt de obicei denumite unu-la-unu (1:1), unu-la-mulți (1:M) sau mulți-la-mulți (M:M).

1:1 – relație unu-la-unu, adică pe ambele părți ale link-ului, există o singură intrare pentru orice valoare din argumentul link-ului. De exemplu: un reprezentant administrativ conduce un departament.

1:M – pe de o parte a relației, pentru unele valori din câmpul asociat pot exista mai multe înregistrări, pe de altă parte - doar una. Exemplu: un grup de studenți dintr-o universitate include mai mulți reprezentanți ai studenților.

M:M – valorile din câmpurile de conexiune apar în mod repetat în înregistrările uneia sau altei entități aferente. Exemplu: profesorii predau elevii.

Relația poate fi definită în continuare prin specificare gradul sau puterea de comunicare(numărul de instanțe de entitate copil care pot exista pentru fiecare instanță de entitate părinte). La proiectarea folosind metoda entitate-relație se pot exprima următoarele puteri de conectare:

Fiecare instanță de entitate părinte poate avea zero, una sau mai multe instanțe de entitate copil asociată cu ea;

· fiecare instanță de entitate părinte trebuie să aibă cel puțin o instanță de entitate copil asociată cu ea;

· fiecare instanță a unei entități-mamă nu trebuie să aibă mai mult de o instanță a unei entități copil asociată cu ea;

· fiecare instanță a unei entități părinte este asociată cu un anumit număr fix de instanțe ale unei entități copil.

Atribut– orice caracteristică a unei entități care este semnificativă pentru domeniul în cauză și are scopul de a califica, identifica, clasifica, cuantifica sau exprima starea entității. Un atribut reprezintă un tip de caracteristici sau proprietăți asociate unui set de obiecte reale sau abstracte (oameni, locuri, evenimente, stări, idei, obiecte etc.). O instanță de atribut este o caracteristică specifică element individual mulţimi. O instanță de atribut este definită de tipul caracteristicii și valoarea acesteia, numită valoare de atribut. Într-o diagramă entitate-relație, atributele sunt asociate cu entități specifice. Astfel, o instanță de entitate trebuie să aibă o singură valoare definită pentru atributul asociat.

Domeniul de atribut- trusa valori acceptabile unul sau mai multe atribute. De exemplu: o adresă de domeniu poate fi utilizată pentru a determina adresa unui angajat, furnizor sau consumator al unui produs.

Atributele pot fi împărțite în:

· simplu – un atribut format dintr-o componentă cu existență independentă. Atributele simple sau elementare nu pot fi împărțite în componente mai mici. De exemplu: salariu, nume, funcție;

· compozit – un atribut format din mai multe componente, fiecare dintre acestea fiind caracterizată de existență independentă. De exemplu: adresa;

· cu o singură valoare – un atribut care conține o valoare pentru fiecare instanță de entitate anumit tip. De exemplu: data nașterii;

· multi-valoare – un atribut care conține mai multe valori pentru fiecare instanță a unei entități de un anumit tip. De exemplu: numere de telefon la care puteți contacta angajatul;

· derivat – un atribut care reprezintă o valoare derivată din valoarea unui atribut asociat sau a unui set de atribute aparținând unui tip de entitate (nu neapărat dat). De exemplu: calculul pe lună a rambursării creditului.

Fiecare entitate trebuie să aibă un identificator sau cheie unică, care este o caracteristică sau un atribut al entității. Cheile pot fi împărțite în:

cheie potențială – atribut sau set minim atribute care identifică în mod unic fiecare instanță a unei entități. O cheie candidată trebuie să conțină valori care sunt unice pentru fiecare instanță individuală a unei entități de un anumit tip și nu poate conține NULL. De exemplu: Cod de poziție în entitatea Poziții;

· cheie primară – o cheie potențială care este aleasă pentru a identifica în mod unic fiecare instanță a unei entități de un anumit tip. De exemplu: fiecare angajat are un număr unic de personal, precum și un număr unic de card de asigurări de stat (TIN). Oricare dintre aceste atribute poate fi selectat ca cheie primară, cea rămasă poate fi considerată o cheie alternativă;

· cheie compusă – o cheie potențială care constă din unul sau mai multe atribute. De exemplu: entitatea Bunuri Sosire poate fi identificată prin atributul Cod produs și Data sosirii.

Esență tip puternic sau independent de identificatori, este numită dacă fiecare instanță a unei entități poate fi identificată în mod unic fără a specifica relațiile sale cu alte entități. Esență tip slab sau În funcție de identitate numită dacă identificarea unică a unei instanțe a unei entități depinde de relația acesteia cu o altă entitate.

Entitățile de tip slab sunt numite dependente de copil sau subordonate, iar entitățile de tip puternic sunt numite entități părinte, proprietare sau dominante.

7.2.3 Tranziția de la modelul ER la cel relațional

În prezent, ultimele două etape de proiectare sunt reduse semnificativ prin utilizarea instrumentelor de proiectare asistată de calculator. Trecerea la model informativ baza de date, iar apoi la designul fizic al bazei de date vă permite să implementați diverse software: IDEF0, ERWin, UML.

Reguli de conversie a modelului:

1. Fiecare entitate simplă se transformă într-un tabel. O entitate simplă este o entitate care nu este un subtip și nu are subtipuri. Numele entității devine numele tabelului.

2. Fiecare atribut devine o posibilă coloană cu același nume; se poate selecta un format mai precis. Nu se potrivesc coloanele atribute obligatorii, poate conține valori nedefinite; coloanele corespunzătoare atributelor obligatorii nu pot.

3. Componentele identificatorului unic al entității sunt transformate în cheia primară a tabelului. Dacă există mai mulți identificatori unici posibili, se selectează cel mai utilizat. Dacă identificatorul unic include relații, o copie a identificatorului unic al entității de la capătul îndepărtat al relației este adăugată la numărul de coloane de cheie primară (acest proces poate continua recursiv). Aceste coloane sunt denumite folosind nume de sfârșit de relație și/sau nume de entități.

4. Relațiile multi-la-unu (și unu-la-unu) devin chei străine, adică o copie a identificatorului unic este făcută de la sfârșitul relației unu-la-unu și coloane corespunzătoare constituie o cheie străină. Relațiile opționale corespund coloanelor nullabile; relații obligatorii - pentru coloanele care nu permit valori nule.

5. Sunt creați indecși pentru cheia primară (index unic), chei externeși acele atribute pe care se presupune că se bazează în principal interogările.

6. Dacă subtipurile au fost prezente în schema conceptuală, atunci există două moduri posibile de a converti modelul într-un tabel fizic: toate subtipurile într-un singur tabel(a) sau pentru fiecare subtip - masa separata (b). Metoda (a) creează un tabel pentru supertipul cel mai exterior, iar vizualizările pot fi create pentru subtipuri. Adăugat la tabel de macar o coloană care conține codul tipului; devine parte a cheii primare. Când se utilizează metoda (b), pentru fiecare subtip al primului nivel (pentru cele inferioare - reprezentări), supertipul este recreat folosind reprezentarea UNION (din toate tabelele de subtipuri, coloane comune- coloane de supertip).

7. Există două moduri de a lucra cu relații exclusive: domeniu generic(a) și chei externe explicite(b). Dacă cheile străine rămase sunt toate în același domeniu, de ex. au un(e) format(e) comun(e), apoi sunt create două coloane: identificatorul relației și identificatorul entității. Coloana ID link este folosită pentru a distinge legăturile acoperite de arcul de excludere. Coloana de identificare a entității este utilizată pentru a stoca valorile identificatorului unic ale entității la capătul îndepărtat al relației corespunzătoare. Dacă cheile străine rezultate nu aparțin aceluiași domeniu, atunci sunt create coloane de chei străine explicite pentru fiecare relație acoperită de arcul de excludere; toate aceste coloane pot conține valori nule.

Unul dintre obiective proiectarea bazelor de date relaționale este construcția de 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 o mulțime de submulțimi R astfel încât

Înainte de a trece la studiul metodei de descompunere a schemelor de relații, luați în considerare problema legături relaționale la despicare relație universală. Când înlocuim relația originală 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 modalitate de a afla dacă proiecțiile rezultate conțin aceeași informație ca relația inițială este de a o reconstrui făcând legătura naturală proiecții 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ă ne uităm la un exemplu descompunere cu pierdere informație.

Exemplu. Descompunere cu pierdere informație

Atributele A și B sunt independente funcțional de atributul C.

Se spune că o descompunere a unei scheme a unei relații r are proprietatea unei conexiuni fără pierderi în raport cu un set de legi fizice D dacă fiecare relație R care satisface D poate fi reprezentată ca:

Lăsa Apoi, următoarele proprietăți sunt valabile pentru mapările proiecție-unire:

Aceste proprietăți rezultă din definiția unui compus natural. Prima proprietate este utilizată atunci când se verifică dacă descompunerea are proprietatea conexiunii fără pierderi în raport cu un anumit set de FS.

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=(R 1 , R 2 , ..., R k ). ieșire: variabilă booleană adevărată sau falsă.

Algoritm

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, B - adresa, C - produs, D - cost, în acest caz există legi federale

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

Diagrama relațiilor

Deoarece acesta este cazul și cele două șiruri coincid în A, atunci putem identifica simbolurile lor pentru A: b 22 cu a 2. Drept urmare, avem un tabel

A	B	C	D
a 1	a 2	b 13	b 14
a 1	a 2	a 3	a 4

Concluzie. Descompunerea d are proprietatea de îmbinare fără pierderi.

Când descompuneți o schemă de relație în alte două scheme de relație, mai mult simpla verificare: descompunerea are proprietatea conexiunii fără pierderi, dacă numai O astfel de FZ trebuie să aparțină lui 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 funcționale F pentru schema de relații r să fie deductibil din proiecțiile pe schemele R i .

Să introducem următoarea definiție.

Definiție 2. Proiecția mulțimii de FD-uri F pe mulțimea de atribute X, notat cu mulțimea de FD-uri în F+, astfel încât

Ei spun că o descompunere are proprietatea de a păstra o funcție fizică dacă toate dependențele din F decurg logic din unirea tuturor legilor fizice care îi aparțin.

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, FL are loc Descompunerea diagramei acestei relații ABC în AC și BC are proprietatea unei conexiuni fără pierderi, deoarece FL este adevărată pe AC dă FL și FL banal. Dependența nu rezultă din FS Prin urmare, această descompunere nu păstrează FS, deși are proprietatea unei conexiuni fără pierderi.

Axioma reflexivității. Dacă Y este în X și X este în U, (Y X U), atunci X Y decurge logic din F. Această regulă produce dependențe banale, deoarece în aceste dependențe partea dreaptă este conținută în partea stângă.

Axioma reaprovizionării. Dacă X Y și Z este o submulțime a lui U , atunci XZ YZ . În acest caz, dependența funcțională X Y a fost fie conținută în setul original F, fie poate fi derivată din F folosind axiomele descrise.

Axioma tranzitivității. Dacă X Y și Y Z, atunci X Z.

Următoarea teoremă este adevărată. Axiomele lui Armstrong sunt complete și de încredere.

Aceasta înseamnă că, folosindu-le, vom deriva toate dependențele funcționale posibile care decurg logic din F și nu vom deriva dependențe inutile.

Există câteva alte reguli de inferență care decurg din

Axiomele lui Armstrong.
Regula de autodeterminare. X
Regula de asociere. Daca X	Y și X	Z, apoi X	Y Z.
Regula pseudotranzitivității. Daca X			Y și		Z, atunci
X W Z.
Regula de compunere. Daca X	Y și Z	W, apoi X W		Y W.
Regula de descompunere. Daca X	Y și Z sunt incluse în Y, apoi X

Trebuie remarcat faptul că calcularea închiderii unui set dependențe funcționale este o sarcină intensivă în muncă, cu un număr suficient de mare de atribute (datorită scrierii unui număr mare de dependențe triviale).

4.4.3. Descompunerea schemei de relații

Tranziția consecutivă de la o formă normală la alta la normalizarea schemelor de relații se realizează folosind descompunerea. Operația principală prin care se realizează descompunerea este proiecția.

Descompunerea schemei de relații R = (A 1, A 2,...A n) este înlocuirea acesteia cu o mulțime de submulțimi R, astfel încât unirea lor să dea R. În acest caz, este permis ca submulțimile să se intersecteze.

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. Corespunzător

Condiția corespunzătoare va fi îndeplinită dacă fiecare tuplu al relației R poate fi reprezentat ca o uniune naturală a proiecțiilor sale pe fiecare dintre submulțimi. În acest caz, se spune că descompunerea are proprietatea de îmbinare fără pierderi.

Algoritmul de descompunere se bazează pe următoarea teoremă. teorema lui Fagin. Fie R (A, B, C) o relație, A, B, C un atribut

Dacă R satisface dependența A B , atunci R este egal cu uniunea 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. Pentru a verifica dacă descompunerea are această proprietate, se folosește un algoritm special de verificare. Algoritmul este după cum urmează.

Să existe o schemă de relații R = A 1 ...A n , o mulțime de dependențe funcționale F și o oarecare descompunere (R 1 ,...R k ) a circuitului original, constând din k subcircuite.

Trebuie să construiți un tabel cu n coloane și k rânduri. Coloana j corespunde atributului A j , rândul k corespunde schemei de relații R k . La intersecția rândului i și coloanei j plasăm simbolul a j dacă A j aparține lui R i . În caz contrar, vom plasa acolo simbolul b ij.

Luăm în considerare fiecare dependență din mulțimea F până când este imposibil să facem modificări în tabel. Ori de câte ori ne uităm la o dependență X Y , căutăm rânduri care se potrivesc cu toate coloanele corespunzătoare atributelor lui X . Când sunt detectate astfel de rânduri, identificăm caracterele din coloanele corespunzătoare atributelor din Y . Dacă unul dintre simbolurile identificate este egal cu a j , atunci îl echivalăm pe celălalt cu a j . În cazul în care sunt egale cu b ij și b lj, le facem pe ambele egale cu b ij sau b lj la discreția noastră.

După modificarea rândurilor tabelului în modul de mai sus, puteți descoperi că un anumit rând a devenit egal cu 1 ...a k . Atunci descompunerea are proprietatea conexiunii fără pierderi. Dacă o astfel de linie nu poate fi obținută, atunci descompunerea nu are această proprietate.

Descompunerea circuitului ABCD în AB și ACD.

A B,AC D (AC este o abreviere pentru A C).

Deoarece o linie este formată din tot a, atunci descompunerea noastră are proprietatea unei îmbinări fără pierderi.

A doua cea mai importantă proprietate dezirabilă a descompunerii este proprietatea de a păstra dependențele funcționale.

Este firesc să dorești descompunerea pentru a păstra dependențele. Dependențe funcționale sunt unele restricții ale datelor. Dacă descompunerea nu are această proprietate, atunci pentru a verifica dacă datele introduse încalcă condițiile de integritate (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 conexiunii fără pierderi și este de dorit ca acestea să aibă proprietatea de a păstra dependențele funcționale.

4.4.4. Selectarea unui set rațional de modele 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 cheia primară (nu depinde de o parte a cheii).

Pentru a converti o relație la 2NF, este necesar, folosind operația de proiecție, să o descompunem în mai multe relații, după cum urmează:

1) construiți o proiecție fără atribute care sunt parțial dependente funcțional de cheia primară;

2) construiți proiecții pe părți ale unei chei compuse și atribute 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ă

A treia formă normală elimină redundanța și anomaliile de includere și ștergere. 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 aparține lui 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.

Exemplu. Programul consultațiilor. Fiecare grup poate veni la consultație o dată pe zi. Pentru a efectua o consultare sau consultări, profesorului i se oferă o audiență într-o anumită zi. Această clasă poate fi folosită de diferiți profesori pe parcursul zilei.

PROGRAM DE CONSULTARE (Grup, Data, Ora, Profesorul, Publicul)

Am ales „Grup, dată” ca cheie principală. Chei potențiale:

„Grup, întâlnire”. „Profesor, dată, oră”. „Public, dată, oră”.

			Profesor	Public
			Vizgunov
			Vizgunov
			Trifonov
			Vizgunov

Astăzi, într-o eră în schimbare rapidă lumea digitală Este greu să ții pasul cu ritmul evenimentelor. Pentru a finaliza totul, trebuie să stabiliți corect sarcini, obiective, să distribuiți și să delegați puteri. Logica și analiza sunt cele mai bune ajutoare în rezolvarea problemelor complexe. Unul dintre instrumentele pentru construcția logică este descompunerea. Să ne uităm la asta în detaliu.

Definiție

ÎN sens general descompunerea este împărțirea unui întreg în componentele sale. Aceasta este o tehnică destul de simplă și simplă, care vă ajută să rezolvați probleme complexe în fiecare zi, prezentându-le ca suma părților lor. În sistemul construcțiilor logice, descompunerea este o tehnică științifică care rezolvă o problemă mare prin înlocuirea acesteia cu câteva probleme mici și mai simple.

De regulă, descompunerea se efectuează folosind „arborele problemelor”, „arborele obiectivelor”, „arborele de decizie”, „arborele de lucru”, atunci când este construită, se formează o structură ierarhică clară, inclusiv subordonare și feedback vertical și orizontal.

Particularități

Baza oricărei descompunere este subordonarea structurală la toate regulile metodei. Regulile fundamentale care guvernează întregul sistem includ următoarele:

1) Sistemul de niveluri trebuie urmat întotdeauna.

Metoda de descompunere se bazează pe subordonarea unui nivel inferior unuia superior. Acest lucru se realizează prin construirea unei structuri ierarhice folosind așa-numiții „arbori”.

Este obișnuit să construiți mai întâi un arbore de probleme și un arbore de obiective pentru a reprezenta clar și vizual toate sarcinile care există pe acest moment. În același timp, subordonarea ar trebui să arate astfel încât sarcinile de un nivel inferior să dezvăluie esența sarcinilor de la un nivel superior. nivel inalt, iar toate subsarcinile au reprezentat întregul proiect. Înțelegerea imaginii exacte și complete a procentului de finalizare a unui proiect de descompunere vine doar atunci când arborele obiectivului este 100% complet.

Ghidați de algebră și logică formală simplă, puteți construi, de asemenea, „arbori ȘI” și „arbori SAU”.

2) Împărțirea întregului în părți ar trebui să aibă loc după un singur criteriu.

Acest principiu implică faptul că toate sarcinile secundare vor fi subordonate unei singure idei și scop. Un exemplu de descompunere ar putea fi un proiect de construcție. Dacă un semn funcțional este luat ca semn principal al partiționării, atunci proiectul este împărțit în secțiuni. De exemplu, acestea ar putea fi următoarele secțiuni principale: structuri din beton armat (RC), soluții arhitecturale (AR), structuri metalice (CM), încălzire și ventilație (HV) etc. La rândul lor, aceste secțiuni ar trebui, de asemenea, împărțite în funcție de criterii funcționale, adică esența obiectivelor principale ar trebui să fie prezentată în sub-obiectivele de la nivelul următor. De exemplu, secțiunea de încălzire și ventilație (HV) este împărțită într-o notă explicativă, desene, proiectare, trecerea controlului standard și control tehnic, eliberarea documentației, supravegherea proiectantului, ajustări în funcție de comentarii etc.

Ca caracteristică, puteți utiliza, de asemenea, intervale de timp (termene limită), caracteristici ale subiectului, caracteristici structurale, caracteristicile tehnologice si altii.

3) Toate subsistemele de descompunere trebuie să dezvăluie esența sistemului.

Dacă vă imaginați că sarcina principală este 100%, atunci toate subsarcinile ar trebui să însumeze același 100%. Mai mult, fiecare subsarcină a primului nivel conține propriul procentaj, reprezentând suma subsarcinilor din al doilea nivel.

Este important să înțelegem că toate subsarcinile divizate de același nivel ar trebui să fie independente unele de altele, în timp ce ierarhia sarcinilor de-a lungul unei ramuri ar trebui să se bazeze pe principiul dependenței și părere: O sarcină de nivel superior depinde de subsarcina ei și invers.

4) Studiul adâncimii de descompunere ar trebui determinată în stadiul inițial.

Înainte de a crea o structură ierarhică, trebuie să decideți care va fi ultimul nivel de subsarcini. În unele cazuri, nu este necesar să se creeze mai multe niveluri, deoarece scopul descompunerii este claritatea. În cazul în care se creează o ierarhie pentru calcule precise, numărul de niveluri ar trebui să fie astfel încât să dezvăluie subiectul cât mai detaliat posibil.

Clasificare

Astăzi se cunosc mai multe tipuri de descompunere. De asemenea, puteți crea propriile tehnici pentru un anumit proiect. Cu toate acestea, într-o măsură sau alta, ele se vor referi la principalele tipuri, și anume: descompunerea obiectivelor (primul și fundamental tip), sistemele (procesul de împărțire a sistemului în subsisteme pentru a lucra și a obține un rezultat mai bun) , proces, lucru (întocmirea unei ierarhii a muncii care să desemneze punctele slabe și evidențierea principalelor și primare).

De regulă, totul procesele enumerate sunt interconectate și reprezintă în general o structură completă de descompunere.

Pentru a începe, sunt compilate un arbore de probleme și un arbore de obiective. Arborele problemelor este problema principală, împărțită în probleme de nivel al doilea și al treilea. În această formă, ele devin mult mai ușor de rezolvat. După analiză detaliată probleme, este compilat un arbore de obiective, care reprezintă un arbore de probleme rezolvate. Adică pentru fiecare problemă se propune o soluție. În același timp, structura gata făcută și interdependențele subsarcinilor sunt păstrate.

Analiza acțiunii

Defalcarea muncii este construcție logică, care începe atunci când toate scopurile și problemele sunt identificate și reprezintă o structură ierarhică a tuturor acțiunilor care trebuie efectuate pentru a rezolva o anumită problemă.

Astfel de circuit logic vă permite să identificați acele etape de lucru în care au apărut probleme. Deoarece sarcinile secundare depind de sarcini de nivel înalt, arborele de lucru vă permite să vedeți unde există probleme și deficiențe. Adesea, munca la niveluri inferioare suferă din cauza slăbiciunilor din primul nivel de descompunere.

De exemplu, dacă cumpărătorul nu a depus o cerere de șuruburi autofiletante, atunci departamentul de contabilitate nu a procesat facturile și nu le-a achiziționat. La un șantier, totul se oprește deoarece instalatorii nu au suficiente șuruburi autofiletante pentru lucrare.

Tehnica clasică

Pentru a efectua o analiză mai detaliată a structurilor, a identifica punctele lor slabe, obiectivele și direcțiile principale, sarcinile, proiectele și lucrările, se efectuează o descompunere a sistemelor.

Sistemul este împărțit atât pe orizontală, cât și pe verticală în niveluri. Ele ar trebui să formeze o imagine de ansamblu a structurii. Descompunerea sistemelor este exemplu general ierarhie pentru orice tip de descompunere.

Aplicație în afaceri

Pentru a descrie și analiza activitățile companiilor, se utilizează de obicei descompunerea procesului. Folosind ierarhia, puteți identifica punctele dure ale companiei, zonele în care apar eșecurile.

Procesele sunt reduse la schema generalași analizate, după care se întocmește un raport detaliat despre activitățile companiei.

Ca exemplu, luați în considerare un proiect pentru construcția unei instalații de construcție capitală. Dezvoltarea se realizează în 2 etape: documentație de lucru și documentație de proiectare. Acestea vor fi subsarcinile de primul nivel. Lucrarea va fi prezentată cu estimări și proiecte. La fel este și în faza de lucru. Acestea sunt subsarcini de nivel al doilea. De exemplu, un proiect este de obicei prezentat în următoarele părți:

• notă explicativă generală;
• solutii arhitecturale;
• soluții constructive și de amenajare a spațiului.

• sistem de alimentare cu energie;
• Sistem de alimentare cu apă;
• sistem de scurgere;
• incalzire, ventilatie si aer conditionat, retele de incalzire;
• rețele de comunicații;
• sistem de alimentare cu gaz;
• solutii tehnologice.

Secțiunile și subsecțiunile de proiectare și documentație de lucru sunt subsarcini de al treilea nivel.

Fiecare secțiune este formată din anumite etape și trebuie să conțină informații în conformitate cu standardele de stat. De exemplu, secțiunea soluție trebuie să includă o parte de text cu descriere detaliata diagrama tehnologica si echipamentele acceptate, partea grafica (planuri, sectiuni, diagrame), lista echipamentelor, vizite la fata locului, control normativ si tehnic, eliberare documentatie.

La fiecare nivel sunt numiți performeri responsabili, de la care apoi se solicită rezultate. În acest exemplu de descompunere, performanții primului nivel sunt șefii departamentului de proiectare, al doilea - al treilea sunt ingineri de proiectare.

Pe scurt despre principalul lucru

Descompunerea este o metodă de logică practică formală care implică o elaborare de înaltă calitate sarcina principala conform abordării principale Această abordare asigură implicarea personalului la toate nivelurile pentru rezolvarea problemelor pe mai multe niveluri. Acest lucru permite ca proiectul să fie derulat cel mai eficient, cu cele mai mici investiții financiare și costuri cu forța de muncă.

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 despre 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, adică. 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ă o relație include toate atributele din domeniul bazei de date, este apelată 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 modele logice baze de date relaționale date. 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 conexiunii 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 modalitate de a afla dacă proiecțiile rezultate conțin aceeași informație ca relația inițială este de a o reconstrui prin realizarea unei conexiuni naturale a proiecțiilor rezultate. Dacă relația rezultată din îmbinare nu se potrivește cu relația inițială, atunci este imposibil de spus 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 diagramă de relații în alte două diagrame de relații, se folosește un test mai simplu: descompunerea are proprietatea unei îmbinări 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 - adresă, C - cod poștal, în acest caz există 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 posibile (vezi elementul de antrenament " Model relațional date") sunt identificate prin găsirea setului minim de valori ale atributelor care determină valorile tuturor celorlalte atribute din relație. Reamintim conceptul unei posibile chei de relație ca atribut sau atribute ale unei relații date care pot fi selectate ca primar într-o relaţie dată.

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, atunci când se descompun relații, 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, putem formula un algoritm general pentru 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. Întrucât BCNF poate să nu existe într-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 efectuează unirea relației 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 să adăugați un subcircuit care conține cheia universală și să efectuați unirea 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 încheie după căutări 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 corecte 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ă căutări prin 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 neajunsuri ale metodei de descompunere și au ca scop 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 se raportează la esența Subiectului prin conexiunea Citirea. Î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 alegerea 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 care cheia principala Relația 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ă: datele despre elementele care nu sunt citite în prezent nu pot fi introduse î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 de date î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 curs de citire.

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 - câte 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 duplicarea ș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 cheia primară compusă a relației pentru conexiune.

Pentru o relație cu trei sau mai multe sensuri, 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 de mai sus sunt construite una câte una principiu general: fiecare atribut non-cheie are propria relație, adică 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, principiul general al regulilor de transformare este că 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 comună printr-un atribut comun de domeniu, în acest caz un număr 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 training 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ța dependențelor funcționale (FD) î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 FZ pentru realizarea proiecției relației 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.