Concepte de Baza

Prezentarea Conceptelor de Baza este organizata in jurul a trei opozitii de termeni cu care opereaza fecvent Bazele de Date:

o        Multimi si Relatii - ca elemente fundamentale de descriere a existentei

o        Informatie si Data - ca forme de reprezentare a Semnificatului si Semnificandului in SBD

o        Data si Procedura - ca mijloace de descriere a Starilor si Transformarilor unui Sistem

Termenii introdusi sunt apoi folositi pentru descrierea Structurilor de Informatii, Date si Proceduri, notiuni pe care se bazeaza construirea si utilizarea Sistemelor cu Baze de Date.

Multimi si Relatii

Inceperea prezentarii Conceptelor de Baza cu care opereaza disciplina de Baze de Date prin reamintirea unor notiuni fundamentale legate de Multimi si Relatii aduce urmatoarele beneficii:

Permite raportarea conceptelor proprii disciplinei, precum si a terminologiei de specialitate la notiuni consistente

Inlesneste intelegerea evolutiei modelelor utilizate in diferite etape de dezvoltare a disciplinei

Permite orientarea in perspectivele de dezvoltare ale modelelor promovate si utilizate in SBD

Faciliteaza compararea si evaluarea conceptelor din domeniu, prin raportarea lor la cele din domeniile inrudite (Programare Clasica, Programare Obiectuala, Ingineria Programarii Instrumente CASE etc.)

Multimi

Multimea - poate fi privita ca o colectie de Elemente distincte (concrete sau abstracte), ce au o proprietate comuna.

Definitia lui Cantor: "O multime este rezultatul cuprinderii intr-un singur tot a unor obiecte determinate ale perceperii sau gandirii noastre; aceste obiecte se numesc elemente ale multimii."

Multimea si Elementul sunt notiuni primare si nu pot ca urmare sa fie definite in plan abstract (ex.: intr-un sistem formalizat).

Avand in vedere utilitatea proprietatilor generale ale multimilor pentru tratarea Colectiilor de Informatii si Date cu care opereaza SBD, se retranscriu in continuare Caracteristicile de Baza ale Multimii. Se va observa in cele ce urmeaza ca ele vor fi preluate ca Restrictii implicite ale Modelului Relational de Date.

Caracteristicile de baza ale Multimii

o        Individualitatea Elementului - Fiecare Element al Multimii trebuie sa se deosebeasca de celelalte.

Orice Colectie de Date privita ca o Multime trebuie sa contina aceasta prima proprietate si sa asigure posibilitatea ca fiecare element din colectie (articol, inregistrare, tupla etc.) sa fie referit unic. De aici deriva necesitatea existentei unui Identificator pentru toate colectiile de date care, intrand in relatii reciproce, constituie un tot unitar si consistent.

o        Individualitatea Multimii - Fiecare Multime se individualizeaza prin existenta unei Proprietati Comune, definitorie pentru multime (multimea sa fie Bine Definita)

Proprietatea de Multime Bine Definita poate interveni doar in cazul Colectiilor de Date ce sunt definite intensional in cadrul Bazelor de Cunostinte sau a Bazelor de Date Deductive.

o        Asemanarea Elementelor (Echivalenta Elementelor Din punctul de vedere al Proprietatii Comune nu exista Element Privilegiat si ca urmare nu exista nici Ordine a Elementelor (aceasta fiind o proprietate nespecificata in Proprietatea Comuna).

Evidentiata in special de modelul Relational de date, caracteristica de Asemanare e prezenta prin modul de definire a Relatiei (Tabelei) ca si colectie de tuple sau randuri care initial apar in Ordine Naturala (ordinea cronologica de inregistrare in colectie), ceea ce corespunde inexistentei unui element privilegiat, nici macar in ceea ce priveste Ordinea in Colectie, care survine doar ulterior in prelucrare, prin atasarea explicita a unui Criteriu de Ordonare si a unei Ordini introduse de o Tabela de Index.

o        Unitatea Elementelor - Proprietatea Comuna permite ca Multimea sa fie privita si tratata ca un nou Element (o noua entitate), care in aceasta calitate poate participa in alta Multime.

Esenta prelucrarilor in sistemele cu Baze de Date este capacitatea de generare a unor noi Colectii de Date prin Regrupare sau Combinare de multimi. Fiecare noua colectie trebuie sa fie Identificabila (printr-un Nume, printr-o Proprietate sau printr-un Proprietar) si prin aceasta sa fie recunoscuta ca un Element intr-o noua Colectie de Colectii de Date.

Legatura intre Element si Multime este realizata prin proprietatea de Apartenenta, care va sta la baza Relatiei de Echivalenta.

Incluziunea Multimilor

Fie M ₁ si M ₂ doua multimi.

Se zice:

M ₂ M ₁ (M ₂ e Inclus in M ₁ sau M ₂ e Parte Proprie a lui M ₁)

daca: x I M ₂ T x I M ₁

Prima forma de legatura intre Multimi este realizata prin proprietatea de Incluziune si e bazata pe generarea de noi multimi prin Regrupare de Elemente. (Cea de a doua forma de legare a multimilor va fi introdusa odata cu prezentarea Relatiei.).

Identitatea Multimilor

Fie M ₁ si M ₂ doua multimi.

Se zice:

M ₁ = M ₂ (M ₁ , M ₂ identice sau egale)

daca:

x I M ₁ x I M ₂

sau:

x I M ₁ T x I M ₂

x I M ₂ T x I M ₁

O multime de multimi se numeste Clasa sau Familie. Notiunile de Clasa de Entitati si Clasa de Obiecte isi au originea in notiunea de Clasa, atat Entitatea Notiune cat si Entitatea Obiect fiind privite ca Mutimi de Caracteristici, respectiv Multimi de Tuple de Valori.

Analiza: Simboluri chimice - element chimic se numeste simbol chimic Referat: Determinarea energiei de activare Arrhenius - reactia tiosulfatul de sodiu cu acidul sulfuric

Multimea Totala

Multimea Totala este multimea constituita pe baza unei Proprietati Fundamentale (Primare) a unor Elemente.

Toate celelalte proprietati care pot fi recunoscute pentru elementele unei Multimi Totale se adauga Proprietatii Primare purtand numele de Proprietati Secundare. Proprietatile secundare definesc in multimea totala Parti ale acestei multimi.

Referitor la o Multime Totala exista trei categorii de Proprietati:

Echivalente - definesc Multimea Totala (Multimea Plina), fiind echivalente din acest punct de vedere cu proprietatea fundamentala

Straine - definesc Multimea Vida a Multimii Totale

Restrictive - definesc Submultimi Parti ale Multimii Totale

Proprietatile Restrictive sunt cele care asigura generarea de noi multimi prin Regruparea Elementelor unei Multimi date.

Fiind data o Multime Totala M, se definesc:

P(M) - Multimea Partilor lui M care contine

Submultimile lui M

Multimea Vida

Multimea Plina

P*(M) - Multimea Partilor Nevide ale lui M care contine

Submultimile lui M

Multimea Plina

Exista expresia de legatura:

P*(M) = P(M)

Fiind data o Multime M, Familia tuturor Submultimilor lui M e o Familie Bine Definita de multimi numita Familia Partilor Multimii M.

Numararea Partilor unei Multimi Totale

Pentru o Multime M avand n Elemente P(M) va avea 2 ⁿ Elemente (reprezentate de Multimile Parti).

Pentru o Multime M avand definite n Submultimi (Multimi Parti) oarecare (nedisjuncte) acestea genereaza in multimea data:

C _n⁰ + C _n¹ + C _n² + . + C _nⁿ = 2 ⁿ

Parti Disjuncte (obtinute prin Intersectia Submultimilor Oarecare pentru fiecare Combinatie de Submultimi)

(C⁰₂) ⁿ  + (C¹₂) ⁿ + (C³₂) ⁿ + . + (Cⁿ₂) ⁿ = (2 ⁿ ) ⁿ

Parti Disjuncte si Nedisjuncte (obtinute prin Reuniunea Submultimilor Disjuncte pentru fiecare Combinatie de Submultimi)

Pentru n=9 Submultimi rezulta un Numar de Parti mai mare decat numarul estimat al electronilor si protonilor din univers, de unde si puterea de generare de noi multimi prin Regrupare de Elemente (Partitii sau Acoperiri), procedeu mult utilizat in generarea de noi colectii de date.

Notiunea de Multime Totala corespunde notiunii de Univers de Discurs din Calculul Predicatelor si notiunii de Univers din unele Sisteme Formale Axiomatizate. In domeniul Bazelor de Date ea poate fi atasata fie unei Baze de Date (Logice sau Fizice) sau chiar unei Relatii (Tabele) care, fiind Bine Definite pot conduce la generarea unor numeroase Medii de Lucru (Colectii de Date) prin simpla adaugare de Filtre de Selectie (Proprietati Secundare).

Operatii Booleene pe Multimea Partilor unei Multimi Totale

Fie M Multimea Totala si M _i I P (M), pentru i I

Complementara unei multimi

M ₁^C =

Reuniunea multimilor

M ₁ M ₂ =

"sau" e inclusiv

Intersectia multimilor

M ₁ M ₂ =

Diferenta multimilor

M ₁ M ₂ =

Diferenta simetrica a multimilor

M ₁ D M ₂ =

Multimi disjuncte

M ₁ M ₂ sunt disjuncte pentru M ₁ M ₂ =

Acoperire si Partitie

Fig. 3.1.1.7.1. Submultimi in Relatie de Acoperire

Multimile Parti M ₁, M ₂, M ₃, .. , M _n formeaza o Acoperire pe M pentru:

M ₁ M ₂ M ₃ .. M _n = M

Fig. 3.1.1.7.2. Submultimi in Relatei de Partitie

Multimile Parti M ₁, M ₂, M ₃, .. , M _n formeaza o Partitie Neordonata pe M pentru:

M ₁ M ₂ = pentru i , j I si i j

Relatii intre Multimi

Exista doua metode de a genera noi multimi pornind de la multimi date prin:

Regrupare de Elemente - operatie intalnita la stabilirea Multimilor Parti (de tip Partitie sau Acoperire) prin definirea de Proprietati Secundare

Combinare de Elemente - operatie intalnita la efectuarea Produsului Cartezian a multimilor

Combinarea de elemente se realizeaza cu ajutorul notiunii de Cuplu

Fiind date multimile M ₁ si M ₂ , perechea ordonata (m ₁ , m ₂) cu m ₁ I M ₁ si m ₂ I M ₂ poarta numele de Cuplu. Se observa ca notiunea de Cuplu introduce pentru prima data in discutie problema Ordinii in multimile de elemente, prin aceea ca termenul "perechea ordonata (m ₁ , m ₂)" este folosit, intr-un sens intuitiv, ca o alaturare a elementelor m ₁ si m ₂ astfel incat m ₁ poate fi perceput ca un Element Aparte (Primul Element) al perechii ordonate (m ₁ , m ₂) si m ₂ ca Celalalt Element (al Doilea Element).

Faptul ca definirea formalizata a relatiilor de Ordine pe multimi apeleaza la conceptul de Cuplu, ne face sa consideram Ordinea, alaturi de Multime si Element, ca o notiune primara.

Pentru aceeasi idee pledeaza si definirea in cadrul Teoriei Multimii a notiunii de Pereche Ordonata, nu pur si simplu ca , ci prin postularea urmatoarei egalitati prin definitie:

(m ₁ , m ₂) = _def , }

inteleasa in modul ca, daca m ₁ m ₂ membrul stang al perechii ordonate (m ₁ , m ₂) este elementul multimii formate dintr-un singur element, pe cand membrul drept este constituit cu elementul ce nu se gaseste in aceasta multime. Definitia folosita extrage elementul m ₁ din multime eliberandu-l de proprietatea de echivalenta si acordandu-i o proprietate noua, pe cea de Pozitie in multime pe care se bazeaza de fapt conceptul de Ordine. Se mai poate remarca si faptul ca daca, prin reducere la absurd, consideram:

(m ₁ , m ₂) = , } = , }

rezulta:

m ₁ = m ₂

Din aceasta definitie se poate deriva si urmatoarea proprietate fundamentala a perechilor ordonate, cunoscuta si sub numele de Axioma Cuplului si care se enunta astfel:

(x , y ) = (x' , y') T x = x' si y = y' ,

Acesta definitie subliniaza o data in plus faptul ca modul de enumerare (pozitia in multime), care pana acum era indiferenta incepe deja sa conteze.

Notiunea de Cuplu se generalizeaza pentru n multimi, M ₁, M ₂, M ₃, .., M _n, primind denumirea de n-TUPLU (sau n-UPLU) si avand forma:

(m ₁, m ₂, m ₃, .. , m _n).

Produs Cartezian de multimi

Produsul Cartezian a n multimi M ₁ , M ₂ , M ₃ , .. , M _n se defineste ca fiind multimea:

M ₁ x M ₂ x M ₃ x .. x M _n = P M _i = { (m ₁ , m ₂ , m ₃ , .. , m _n) | m _i I M _i pentru i I

Pentru M ₁ = M ₂ = M ₃ = .. = M _n = M , Produsul Cartezian a n multimi se transforma in Puterea Carteziana a unei multimi, notata M ⁿ.

Relatia n-ara

O Relatie n-ara R pe multimile nevide M ₁ , M ₂ , M ₃ , .. , M _n se defineste ca o Submultime a Produsului Cartezian M ₁ x M ₂ x M ₃ x .. x M _n . Deci:

R M ₁ x M ₂ x M ₃ x .. x M _n

Cu alte cuvinte, orice Multime Parte a unui Produs Cartezian e o Relatie.

Numarul Multimilor pe care e definit Produsul Cartezian confera Gradul Relatiei, in speta n, cu conditia impusa n . (Orice Relatie implica minimum doua Domenii, nu neaparat Distincte.)

Relatia e deci o multime si are ca urmare o Propritate Definitorie, care e valabila pentru toate n-Tuplele Relatiei. Intrucat fiecare n-tupla contine mai multe elemente primare m_i, provenind din multimile de definitie M _i , Proprietatea Definitorie a relatiei poate fi privita ca un Predicat Polinar;

P (m ₁ , m ₂ , m ₃ , .. , m _n).

In definirea unei Relatii se pot recunoaste cele doua forme de definitie ale unei multimi:

Intensionala - prin:

P (m ₁ , m ₂ , m ₃ , .. , m _n) = 'adevarat'

pe multimea Produsului Cartezian M ₁ x M ₂ x M ₃ x .. x M _n , privit ca Multime Totala

Extensionala - prin:

{ (m ₁ , m ₂ , m ₃ , .. , m _n) | m _i I M _i pt. i I si (m ₁ , m ₂ , m ₃ , .. , m _n) I R }

Conditia ca Multimile de Definitie M _i sa nu fie vide se motiveaza prin necesitatea ca fiecare n-tuplu sa contina in mod constant n elemente, absenta unuia din elementele n-tuplului distrugand ideea de Ordine pe care n-tuplul trebuie sa o instituie intrre elementele sale. Relatia poate insa sa fie Vida , fiind in acest caz reprezentata de Submultimea Vida a Produsului Cartezian M ₁ x M ₂ x M ₃ x .. x M _n, care semnifica faptul ca Proprietatea Definitorie, in acest caz, este o Proprietate Straina (neindeplinita de nici o combinatie de elemente din Multimile de Definitie).

Pentru n = 2 se obtin Relatiile Binare , relatii foarte utile pentru descrierea naturii legaturilor intre Multimi, dar si intre Elementele Multimilor (in speta Atributele unei Relatii din Modelul Relational de Date).

Pentru relatiile binare se folosesc doua conventii de notatie echivalente:

x R y (x , y) I R

Fiind data o relatie binara R definita pe o singura multime M se pot defini notiunile:

Domeniul de Definitie al Relatiei (numit si Suport), reprezentat de Proiectia de Rang ₁ a Puterii Carteziene M x M

DD _R = P _{R , 1}

Domeniul de Valori al Relatiei (numit si Codomeniu), reprezentat de Proiectia de Rang ₂ a Puterii Carteziene M x M:

DV _R  = P _{R , 2}

Domeniul Relatiei , reprezentat de Reuniunea Domeniului de Definitie cu Domeniul de Valori

DR _R = DD _R DV _R

De unde rezulta:

DD _R   DR _R

si

DV_R   DR _R

Relatii de Ordine

Relatia de Ordine este o Relatie Binara cu urmatoarele proprietati:

Reflexivitate

Antisimetrie

Tranzitivitate

Importanta relatiilor de Ordine consta in faptul ca ele permit introducerea conceptului de Multime Ordonata, definita ca o pereche ordonata:

Multime - M

Relatie de Ordine - O

M _o  s ( M , O )

Acest concept este preluat de Modelul Relational de organizare a datelor prin urmatoarele restrictii implicite:

o        Orice Colectie de Date este privita ca o Multime (de tuple, sau inregistrari), deci neordonata

o        Cu ajutorul acestor Colectii de Date, care constituie Structura de Baza a Modelului de Date, se poate construi, utilizand conceptul de Relatie, orice structura de date oricat de complexa

o        Toti Operatorii implementati pe aceasta Structura de Baza nu pretind existenta prealabila a unei Ordini

o        Ordonarea Colectiilor de Date se face prin adaugarea unor Structuri Auxiliare de date (Indecsi), care folosesc exclusiv pentru ridicarea performantelor de prelucrare (la Identificare, Acces sau Ordonare) si nu la construirea structurilor de date

o        Unei Colectii de Date i se pot adauga oricati Indecsi transformand-o in tot atatea Colectii Ordonate, care dispar odata cu eliminarea structurilor auxiliare atasate, ceea ce confera un caracter dinamic procesului de ordonare

o        Procesul de Navigare in aceste Colectii de Date ramane si el dinamic prin posibilitatea modificarii Ordinii de Inspectie prin simpla inlocuire a Indexului Activ pe parcursul navigarii.