Implementarea Sub Sistemului de Import Relational al Matbase
CUPRINS
Introducere
MatBase este un sistem de gestiune a bazelor de date (bd) și cunoștiințe (SGBDC) [0,2,4] prototip, care oferă utilizatorilor săi posibilitatea de a proiecta și întreține (deci modifica) scheme de bd deductiv deterministe [4,8,15], precum și aplicații de gestiune a actualizărilor și interogare construite pe baza acestora [1,3,4], folosind simultan mai multe modele ale datelor: matematic elementar (MMED) [2,4, 5,6,7,8,10,11,12,13,14,15,16,17], logic (MLD, bazat pe limbajul Datalog) [4,8,15,16], entități-asociații (MEA, grafic) [0,2,4,6,17] și relațional (MRD, pe care se bazează implementarea tuturor celorlalte) [0,1,2,3,4,5,7,9].
MMED și MatBase sunt proprietate intelectuală a lui Christian Mancaș și comercială a companiei sale, DATASIS ProSoft srl (www.datasis.ro). Există două implementări prototip ale MatBase: versiunea 4.2.2 Access (2003) și versiunea 6.0 C#.NET + MS SQL Server.
Pe lângă posibilitatea de a crea și modifica scheme de bd și aplicații asupra acestora (cu cod automat generat pentru impunerea constrângerilor), este normal și util ca MatBase să ofere utilizatorilor săi și facilitatea de a importa bd relaționale (bdr) existente (care nu au fost automat create de MatBase, ci manual, cu ajutorul altor SGBD relaționale, precum MS Access și SQL Server, IBM DB/2, Oracle etc.). Un asemenea demers are mai multe scopuri importante:
Analiza corectitudinii proiectării și implementării relaționale a bdr importate
Corectarea eventualelor lor erori de proiectare și implementare
Optimizarea acestor bdr
Decriptarea semanticii bdr (reverse engineering), atât la nivel macroscopic, grafic, prin intermediul Diagramelor Entități-Asociații (DE-A), cât și la cel microscopic, riguros, prin intermediul schemelor matematice (în MMED).
Algoritmii folosiți de sub-sistemul de import MatBase au fost introduși și publicați în [5]. În esență, un prim algoritm importă orice bdr adaptând-o (și, apoi, optimizând-o) conform standardele relaționale ale MatBase, mult mai înalte decât cele uzuale; de exemplu:
Fiecare tabelă are o cheie primară surogat (cu auto-numărare, de câte ori acest lucru este posibil; se exclud deci cheile primare semantice, cu atât mai mult deci cele alcătuite dintr-un produs de atribute), cel puțin o cheie semantică (cu excepția tabelelor modelând submulțimi) și cel puțin un atribut ce nu admite nuluri.
Orice cheie corespunde sau unei funcții injective sau unui produs de funcții minimal injectiv; deci, în particular, nici o cheie nu poate include vreo altă cheie (i.e. supercheile nu pot fi declarate drept chei).
În nici o tabelă cu r atribute semantice (i.e. cu excepția cheii surogat, considerată sintactică) nu pot exista mai mult de chei semantice (i.e. + 1, inclusiv cea primară) [1,2,5, 12,13].
Orice cheie străină este formată cu un singur atribut (se exclud deci cele formate cu produse de atribute) și referă exclusiv o cheie primară (se exclud deci cele care referă atribute semantice).
Modelarea incluziunii mulțimilor se face exclusiv prin declararea cheii primare a tabelei corespunzând submulțimii (care, evident, nu poate fi cu auto-numărare) drept cheie străină în tabela corespunzând mulțimii.
Un al doilea algoritm traduce apoi schema relațională astfel obținută într-o schemă matematică în MMED echivalentă (care, ulterior, poate fi desigur nu doar analizată, ci și modificată de utilizator cu ajutorul MatBase). În esență, acesta generează pentru fiecare tabelă o mulțime de obiecte (de tip entități), pentru fiecare coloană ce nu este cheie străină o funcție de tip atribut (definită pe mulțimea de obiecte respectivă și cu valori în mulțimea de valori corespunzătoare domeniului atributului), pentru fiecare cheie străină o funcție de tip structural (definită pe mulțimea de obiecte respectivă și cu valori în mulțimea de obiecte corespunzătoare tabelei referite), pentru fiecare cheie (relațională) o cheie (matematică) și pentru fiecare constrângere tuplu o constrângere obiect [2,4,16] corespunzătoare.
Un al treilea algoritm traduce schema relațională obținută de primul într-o DE-A echivalentă (care și ea, ulterior, poate fi desigur nu doar analizată, ci și modificată de utilizator cu ajutorul MatBase). În esență, acesta generează pentru fiecare tabelă un dreptunghi, pentru fiecare cheie străină o săgeată (dublă dacă cheia străină respectivă este și cheie), iar pentru fiecare atribut ce nu este cheie străină o elipsă.
Opțional, dacă utilizatorul dorește, pe parcursul importului pot fi apelați și algoritmii de asistența proiectării cheilor [1,2,5,12,13], respectiv a analizării buclelor închise [2,6].
Tema acestui proiect o constituie implementarea primilor doi algoritmi de import pentru versiunea MatBase 6.0 C#.NET + MS SQL Server și bdr MS SQL Server.
I.1 Tehnologii folosite
MatBase a avut mai multe versiuni, de la primele (folosind Borland Paradox, apoi MS C și Borland Paradox Engine, MS C++ și Access 97), la cele două recente, încă în dezvoltare: una în MS Access 2003/2007, cealaltă în MS .NET 2005, C#, XML și SQL Server 2005.
Implementarea de față a fost făcută în cea mai nouă versiune, cea .NET.
I.2 Configurație necesară
Pentru dezvoltare este necesară o stație de lucru de tip PC, preferabil Pentium IV (quad sau măcar dual core) în jur de 3GHz, minim 1GB DDRAM-2 (preferabil 4GB), HDD S-ATA de 7500rpm cu măcar 10 GB spațiu liber, echipat cu măcar MS Windows XP Pro, Visual Studio .NET 2005 (pentru rulare este suficient .NET Framework 2.0, descărcabil gratuit de pe sit-ul Microsoft) și MS SQL Server 2005 (pentru rulare este suficientă versiunea sa gratuită Express), preferabil cu acces la internet (cel puțin la MSDN).
I.3 Structura lucrării
Acest capitol introductiv se încheie cu o succintă definiție a MRD [0,1].
Capitolul 1 prezintă esențialul teoriei MMED și MatBase, inclusiv, la final, algoritmii importului relațional și teoremele lor de caracterizare; prezentarea folosește [2,4,5]. Capitolul 2 descrie arhitectura generală a MatBase, precum și pe cea particulară a sub-sistemului său de import relațional. Capitolul 3 constituie un ghid de utilizare al acestui sub-sistem. Capitolul 4 prezintă trei exemple de import relațional: meta-catalogul MS Access 2003, respectiv cel al MatBase, precum și bd Northwind (oferită gratuit drept exemplu de către Microsoft). Lucrarea se încheie cu concluzii, mulțumiri și referințe bibliografice.
În Anexe este prezentată schema MMED a meta-catalogului MatBase, așa cum a rezultat în urma exportului bd de după importul meta-catalogul său, plus codul implementării realizate (pe CD). De notat că schema MMED a meta-catalogului MatBase are și o mare importanță în sine, deoarece reprezintă și modelul MMED în MMED.
I.4 Modelul relațional al datelor (MRD)
Definiția I.1 Se zice schemă a unei baze de date relaționale (bdr) un triplet S = (R, A, C) cu:
R o mulțime finită nevidă de scheme de relații;
A o mulțime finită nevidă de atribute;
C o mulțime finită nevidă de constrângeri.
Definiția I.2 Se zice schemă a unei relații o pereche R = (AR, CR) unde:
AR este submulțimea atributelor lui R;
CR este submulțimea constrângerilor lui R.
Definiția I.3 Se zice instanță (conținut) a(l) unei relații R (sau, prin abuz de notație, relație) imaginea produsului tuturor atributelor AR.
Definiția I.4 Se zice instanță (conținut) a(l) unei bdr BDR de schemă S (sau, prin abuz de notație, bază de date) reuniunea imaginilor produselor tuturor atributelor AR pentru toate relațiile R ale S.
Definiția I.5 O instanță se zice validă (consistentă, integră, corectă) dacă nu violează nici o constrângere a bdr respective (sau satisface toate constrângerile corespunzătoare), respectiv invalidă (inconsistentă, non-integră, incorectă) dacă violează (nu satisface) cel puțin una dintre constrângeri.
Observația I.6 Considerăm relațiile drept mulțimi (finite), atributele unei relații drept funcții discrete definite pe mulțimea respectivă, iar constrângerile unei relații drept formule închise dintr-o logică a predicatelor de ordin I cu egalitate restrânsă, în care predicatele sunt doar cele matematice standard (<, <=, =, , >, >=) și cele de apartenență a elementelor la relații. AR sunt partițiile lui A conform relației de echivalență dom (i.e. două atribute fac parte din aceeași clasă de echivalență dacă și numai dacă, prin definiție, sunt definite pe aceeași relație, deci au același domeniu); similar, C este reuniunea tuturor CR, iar orice constrângere se referă strict la o relație (i.e. toate constrângerile sunt intra-relaționale; nu există constrângeri inter-relaționale). Datorită finitudinii instanțelor, precum și a caracterului discret al atributelor, cea mai naturală reprezentare a relațiilor este cea tabelară, în care elementele acestora sunt linii, iar atributele sunt coloane, memorând proprietățile de interes ale acestora. Desigur că interesează doar instanțele valide (de notat că, deși acestea sunt corecte sintactic, i.e. din punct de vedere al constrângerilor, semantic ele sunt doar plauzibile, căci corectitudinea semantică nu poate fi garantată de nici un formalism: nici oamenii nu știu exact, de exemplu, care este înălțimea unui munte sau ziua în care s-a născut Euclid…).
Definiția I.7 Orice atribut A : R S, unde S este o relație se zice cheie străină (a lui R în S).
Definiția I.8 Orice mulțime D cu proprietatea că nu este o relație și că există un atribut A : R D se zice domeniu (de valori) al R (și deci al bdr din care R face parte).
Observația I.9 Atributele oricărei bdr se împart, conform tipului codomeniului lor, în două clase: chei străine și atribute de valuare (ce nu sunt chei străine).
Definiția I.10 Constrângerile MRD pot fi doar de unul din următoarele tipuri:
Domeniu
Totalitate
Chei
Chei străine
Tuplu.
Definiția I.11 Precizarea faptului că o mulțime M este codomeniu al unui atribut A se zice constrângere de domeniu (atașată A).
Definiția I.12 Fie NULL o mulțime discretă infinită disjunctă de orice relație, precum și de orice tip de date cunoscut (e.g. naturali, întregi, raționali, booleni, șiruri de caractere, date calendaristice etc.); orice atribut A : R C cu proprietatea că C NULL = se zice total (definit) sau că nu admite nuluri; constrângerea C NULL = se zice constrângere de totalitate (atașată A).
Definiția I.13 Orice atribut injectiv sau orice produs de atribute minimal injectiv (al unei relații R) se zice cheie (a R).
Definiția I.14 Orice predicat de ordin I ce include doar atribute ale unei relații R și referă doar o linie (oarecare) a sa se zice constrângere tuplu (atașată R).
Observația I.15 Evident că orice constrângere de oricare din primele patru tipuri se poate exprima sub forma unei constrângeri tuplu, dar se preferă folosirea constrângerilor tuplu numai pentru restul constrângerilor, în același spirit în care, de exemplu, oricine preferă să spună pur și simplu că o mulțime este inclusă în alta sau că o funcțe este injectivă, în loc să folosească definițiile logico-algebrice ale incluziunii, respectiv injectivității. În practică, sistemele de gestiune a bdr (SGBDR) admit drept constrângeri tuplu formule extrem de restrictive, de obicei cu o singură variabilă (implicită) implicit cuantificată universal. Teoria MRD a introdus de-a lungul timpului și alte tipuri de constrângeri (e.g. dependențe funcționale, multi-valuate, join etc.) exclusiv însă în încercarea de a fundamenta algoritmi de proiectare a unor scheme relaționale cu proprietăți dezirabile (e.g. formele normale 2,3,4,5, Boyce-Codd etc.), care nu au fost deci niciodate implementate de vreun SGBDR (și care, de altfel, s-au dovedit foarte puțin utile și în proiectare, căci cea mai înaltă formă normală, domenii-chei, nu folosește decât constrângerile de tip domeniu și pe cele de tip cheie).
Definiția I.16 Orice cheie totală (a unei relații) poate fi aleasă drept cheie primară (a acelei relații); orice relație poate avea cel mult o cheie primară.
Observația I.17 Adăugarea la schema oricărei relații a unui ata la schema oricărei relații a unui atribut luând valori întregi, injectiv, total și fără nici o altă semantică decât numerotarea unică a liniilor instanțelor relației respective (motiv pentru care el este numit de obicei cheie surogat) și declararea acestuia drept cheie primară este cea mai bună soluție cu putință din foarte multe puncte de vedere. În plus, cu excepția relațiilor modelând sub-mulțimi, este de dorit ca aceste chei surogat să fie declarate cu auto-numărare (tip de date întreg oferit de mai toate SGBDR, care generează pentru ele automat numere unice). Valorile acestor chei surogat pot fi privite drept cele ale liniei x pentru orice atribut A al oricărei relații R (i.e. pe orice linie a R cheia surogat memorează valoarea lui x, iar celula de la intersecția liniei x cu coloana A memorează valoarea A(x)).
1. Modelul matematic elementar al datelor (MMED)
Modelul matematic elementar al datelor (MMED) este bazat pe teoria algebrică elementară a mulțimilor, relațiilor și funcțiilor, ca și pe logica predicatelor de ordin întâi cu egalitate. MMED a pornit de la interpretări funcționale și logice ale MRD, precum și de la o formalizare a MEA, incorporând în timp din ce în ce mai multe tipuri de constrângeri, dar și de la puterea inferențelor oferită de Datalog. Drept urmare, MMED este un instrument de modelare conceptuală a bazelor de date deductive definite (bddd).
MatBase este un sistem de gestiune prototip al bazelor de cunoștințe (SGBC) bazate în primul rând pe MMED, dar și pe MEA, MRD și Datalog. MatBase este de asemenea folosit atât pentru a ilustra modelarea și interogarea conceptuală a datelor și cunoștințelor, MMED, MRD, Datalog și conceptele cheie aferente (e.g. tranzacții, trăgaciuri, evenimente, concurență, distribuire, închideri tranzitive, semantica celor mai mici puncte fixe etc.), cât și programarea în SQL, Datalog, ADO și Access VBA, respectiv C#.NET.
MMED permite modelarea orientată obiect a datelor. Rigoarea sa matematică sporită (în raport, de exemplu, cu MRD, MEA, MFD) conferă schemelor de bd în MMED o mult mai mare naturalețe și putere de exprimare atât semantică, cât și sintactică.
Prima secțiune a acestui capitol prezintă definiția schemelor de bd în accepțiunea MMED.
Cea de-a doua introduce colecția mulțimilor (de valori ale atributelor, respectiv de obiecte). Subsecțiunea 1.2.2 introduce clasa mulțimilor de obiecte cu cele două subclase ale sale, entitățile și asociațiile. În legătură cu acestea din urmă sunt discutate pentru început doar grafurile și ierarhiile de asociații.
Secțiunea 1.3 discută funcțiile (atât cele de tip atribut, cât și cele structurale), tipurile de obiecte (echivalentul fișierelor abstracte din modelarea funcțională), corespondența lor cu relațiile din MRD, conținutul bd, cheile și atributele calculate. Cheile sunt studiate în subsecțiunea 1.3.5, înaintea tuturor celorlalte tipuri de constrângeri, nu doar pentru că sunt cele mai importante dintre toate, dar și pentru că pe teoria lor se bazează tot restul teoriei MMED. Subsecțiunea 1.3.6 este dedicată caracterizării funcțiilor structurale: se demonstrează că aceste funcții sunt reprezentanți ai claselor de echivalență ale funcțional dependențelor din MRD. Este formalizat apoi în 1.3.7 și principiul propagării cheilor, pe baza căruia sunt implementate aceste funcții în modelul relațional.
Secțiunea 1.4 prezintă cele 17 clase ale constrângerilor de integritate exprimabile în MMED: constrângerile obiect (extensia constrângerilor tuplu), constrângerile de domeniu, de existență, minimal injectivitățile (dependențele cheie), incluziunea, egalitatea, reuniunea, disjuncția și partiționarea mulțimilor, surjectivitatea, idempotența și egalitatea funcțiilor, sistemele de reprezentanți, precum și reflexivitatea, simetria, antisimetria, tranzitivitatea și aciclicitatea grafurilor de asociații binare.
Secțiunea 1.5 conține teoria asociațiilor: sunt definite, studiate și caracterizate formal funcționalitățile interne și cheile structurale ale asociațiilor. În final, este propus și evaluat un algoritm eficient de asistență a proiectării schemelor de asociații. Astfel echipate, asociațiile se dovedesc un substitut mult mai puternic, riguros, natural și elegant oferit de MMED în locul dependențelor multivaluate și join din modelul relațional.
Secțiunea 1.6 definește întâi noțiunea de constrângere primitivă, care înglobează în MMED 16 din cele 17 tipuri (excepția fiind constituită de cele obiect). Pe baza unei noi accepțiuni a compatibilității semantice (orientată obiect), sunt reformalizate în consecință anomaliile de actualizare a datelor, descrierile fundamentale și complete ale obiectelor.
În fine, Secțiunea 1.7 prezintă algoritmii de import implementați, teoremele lor de caracterizare, precum și teoremele care dovedesc faptul că diagramele funcționale corespunzătoare diverselor traduceri inter-modele ale MatBase comută.
1.1 Schemele bazelor de date în MMED
Definiția 1.1. Schema oricărei bd în MMED este un cvadruplu (S, M, C, P ), unde:
(S , ) este un poset nevid de mulțimi;
M S S este o mulțime finită nevidă de funcții parțial definite;
C este o mulțime finită de clauze Horn închise numite constrângeri;
P este o mulțime finită de programe Datalog.
Semnificația simbolurilor S, M, C, P utilizate în definiția 1.1 de mai sus provine de la denumirea engleză a noțiunilor de mulțime, funcție, constrângere, respectiv program, și anume: Set, Mapping, Constraint, Program.
MatBase este un sistem de gestiune a bazelor de date și de cunoștințe (SGBDC). Ecranul cu care debutează aplicația corespunzătoare, afișând meniul principal, este prezentat în figura 1.
Fig. 1.1: Meniul principal al MatBase
1.2 Reprezentarea mulțimilor în MMED
Definiția 1.2. La rândul său, S = V C {}, unde:
(, ) este un poset nevid de mulțimi de obiecte;
(V, ) este un poset nevid de mulțimi de valori;
(C, ) este un poset nevid de mulțimi calculate;
este mulțimea vidă.
Exemplul E1.1: {PERSOANE, LOCALITĂȚI, ȚĂRI} , {NAT, RAT, BOOL, CHAR, DATE} V, unde: NAT este mulțimea numerelor naturale, RAT a celor raționale, BOOL={adevărat, fals}‚ CHAR este monoidul liber generat peste un alfabet oarecare (în general ANSI extins sau UNICODE), iar DATE este mulțimea datelor calendaristice.
Ecranul afișând meniul mulțimilor dintr-o bd MatBase, care se obține selectând „Sets” din meniul principal, este cel prezentat în figura 1.2.
Fig. 1.2: Meniul mulțimilor MatBase
1.2.1 Valori
Orice bd sau bază de cunoștințe și deci model al datelor manipulează valori: numere, șiruri de caractere, date calendaristice, constante booleene etc. MMED are încorporată, ca atare, o colecție finită nevidăV de mulțimi de valori, parțial ordonată prin incluziune. (V , ) este deci un poset. Mulțimile dinV sunt, în general, infinite (deși orice implementare se va rezuma, desigur, la submulțimi finite).
Uzual,V include: BOOL = adevărat, fals, NAT INT RAT (naturalii, întregii, raționalii), PREȚ RAT (prețurile, i.e. submulțimea tuturor numerelor raționale pozitive cu 2 zecimale), CHAR* (monoidul liber generat peste un alfabet oarecare fixat CHAR – în general ANSI extins sau UNICODE), DATA (mulțimea datelor calendaristice), TIMP (mulțimea valorilor de timp într-o interpretare oarecare fixată, de exemplu secunde) etc.
Aceste mulțimi de valori fundamentale nu pot fi niciodată modificate sau eliminate din MatBase. Cel puțin o submulțime a NAT face întotdeauna parte dinV.
MMED oferă în plus trei constructori de mulțimi, ce pot fi aplicați și pentru a defini noi mulțimi de valori și anume:
Enum, care presupune enumerarea elementelor mulțimii;
ASet, care este un evaluator de operații algebrice cu mulțimi și
PSet, care este un evaluator de mulțimi definite cu predicate de ordin întâi.
Exemplul 1.2: Enum(CULORI)= 'roșu','oranj','galben','verde','albastru'
Exemplul 1.3: ASet(A) = A B C
Exemplul 1.4: PSet(AN_ȘCOLAR_2003) = xDATA01.10.03 x 30.06.04
Ecranul afișând colecția mulțimilor de valori dintr-o bd MatBase, care se obține selectând „Values” din meniul „Sets”, este prezentat în figura 1.3.
Fig. 1.3: Colecția mulțimilor de valori pentru o bd MatBase
1.2.2 Obiecte
MMED include și o colecție finită nevidă de mulțimi de obiecte, parțial ordonată prin incluziune, despre care interesează memorarea de date; (, ) este deci tot un poset.
Definiția 1.3. este partiționată în două clase = E Æ, unde:
E este o clasă nevidă de mulțimi de entități, iar
Æ este o clasă de mulțimi de asociații,
corespunzând mulțimilor „atomice” precum persoane, cărți, opusuri muzicale, idei etc., respectiv produselor carteziene (i.e., în particular, relațiilor matematice, cu excepția celor binare funcționale, care sunt modelate, vezi 1.3.2, cu ajutorul funcțiilor structurale), precum relațiile de prietenie, împrumuturile de la o bibliotecă, interpretările muzicale, teoriile formale, stocurile, zborurile aeriene etc.
Colecțiile mulțimilor de valori, respectiv de obiecte sunt disjuncte prin definiție.
Exemplul 1.5: dacă, de exemplu, s-ar dori memorarea de date despre culori, altele decât numele lor (de exemplu: lungimea de undă, temperatura, poziția în spectru etc.), trebuie declarată o mulțime de culori în , care nu ar avea nici o legătură cu CULORI definită mai sus înV prin enumerare.
Și mulțimile de obiecte pot fi teoretic infinite, deși practic ele vor fi întotdeauna finite. nu poate fi vidă: ea trebuie să includă cel puțin o mulțime de entități.
Ecranul afișând colecția mulțimilor de obiecte dintr-o bd MatBase, care se obține selectând „All Objects” din meniul „Sets”, este prezentat în figura 1.4.
În MatBase există peste 60 de mulțimi de obiecte sistem, majoritatea transparente pentru proiectantul sau utilizatorul de bd, dar necesare sistemului pentru gestionarea utilizatorilor, a drepturilor lor de acces, a schemelor de bd și tranzacțiilor definite de aceștia etc.
În funcție de drepturile de acces pe care le au, ei pot (explicit sau implicit) să modifice, adauge și/sau să șteargă elemente în/din ele.
Exemplul 1.6: UTILIZATORI, TIP_ACCES, CONCEPTE, ACCES_CON-CEPT, IDENTIFICATORI, SINONIME, BAZE_DATE, MULȚIMI, ENTI-TĂȚI, FUNCȚII, STRUCT_PROD_FUNCT, ASOCIAȚII, SORTURI_ASOC, ATRIBUTE, CHEI, CONSTRÂNGERI sunt toate obiecte sistem, fie ele mulțimi de entități sau mulțimi de asociații.
1.2.2.1 Entități
Exemplul 1.7: {UTILIZATORI, CONCEPTE, TIP_ACCES, SINONIME, BAZE_DATE, ENTITĂȚI, MULȚIMI, FUNCȚII, ASOCIAȚII, ATRIBUTE, CHEI, CONSTRÂNGERI} E, adică aparțin clasei mulțimilor de entități.
Evident că utilizatorii MatBase nu pot șterge nici una din cele peste 65 mulțimi de entități sistem, dar le pot modifica conținutul odată cu declararea de noi scheme de bd sau cu ocazia actualizării schemelor existente.
Desigur că și utilizatorii MatBase pot defini mulțimi de entități.
Ecranul afișând colecția mulțimilor de entități dintr-o bd MatBase, care se obține selectând „Entities” din meniul „Sets”, este prezentat în figura 1.5.
Exemplul 1.8: PERSOANE, CADRE_DIDACTICE, ANGAJAȚI, STUDENȚI, CURSURI, FACULTĂȚI, UNIVERSITĂȚI sunt entități definite de utilizator.
1.2.2.2 Asociații
Mulțimile de obiecte sunt interconectate și ierarhizate în aproape orice subunivers de interes nu doar cu ajutorul incluziunii, ci și cu ajutorul relațiilor (matematice).
Definiția 1.4. Orice asociație A Æ este o pereche A = (SA, GA), unde:
SA = (MSA ;MKA) este schema asociației;
GA este graful asociației.
Fig. 1.4: Colecția mulțimilor de obiecte pentru o bd MatBase
În mod evident, asociațiile nu sunt concepte fundamentale, ci derivate: orice asociație poate fi înlocuită cu o mulțime de entități, plus o mulțime de funcții structurale (corespunzătoare proiecțiilor sale canonice, al căror produs are imaginea egală cu graful asociației) și una de constrângeri de tip cheie (i.e. minimal injectivități). Pentru teoria asociațiilor, a se vedea 1.5.
Exemplul 1.9: În MatBase, UTILIZATORI, CONCEPTE și TIP_ACCES sunt suporții asociației ternare ACCES_CONCEPT, care memorează diversele drepturi de acces (e.g. citire, scriere, creare, ștergere etc.) pe care le au utilizatorii la conceptele gestionate de sistem (e.g. bd, entități, asociații, atribute, funcții, constrângeri etc.). Un triplet oarecare (u, c, a) al acesteia memorează faptul că utilizatorul u are asupra conceptului c dreptul a.
Fig. 1.5: Colecția mulțimilor de entități pentru o bd MatBase
Exemplul 1.10: Într-o bd universitară, ABSOLVIRE ar putea fi o asociație binară definită peste STUDENȚI și CURSURI. O pereche oarecare (s, c) a ei memorează faptul că studentul s a absolvit disciplina predată la cursul c.
Colecția tuturor relațiilor matematice de interes, definite peste mulțimi de obiecte din și care nu sunt funcții alcătuiesc clasa asociațiilor, notată Æ. Orice bd „reală” include cel puțin o asemenea mulțime, deși acest lucru nu este obligatoriu.
Evident că utilizatorii MatBase nu pot șterge nici una din cele peste 10 mulțimi de asociații sistem oferite, dar pot să le modifice conținutul odată cu declararea de noi scheme de bd sau cu ocazia actualizării schemelor existente.
1.2.2.2.1 Schemele asociațiilor
Definiția 1.5. Schema unei asociații A este o pereche SA = (MSA ;MKA), cu:
MSA o mulțime nevidă de suporți;
MKA P (MSA) o mulțime nevidă de chei structurale.
Exemplul 1.11: Asociația ÎMPRUMUTURI_CĂRȚI are schema (CĂRȚI, CITITORI, DATE-ÎMPRUMUTURI; {CĂRȚI, DATE_ÎMPRUMUTURI}).
Denumirea de „cheie structurală” provine din faptul că fiecărei asemenea submulțimi de suporți îi corespunde biunivoc produsul minimal injectiv al proiecțiilor carteziene canonice ale suporților respectivi.
1.2.2.2.2 Grafurile asociațiilor
Definiția 1.6. Graful asociației GA este o submulțime nevidă a produsului cartezian a mulțimilor din MSA (i.e. a suporților).
Din definiția relațiilor matematice, ne reamintim că acestea sunt privite pur și simplu ca submulțimi ale produsului cartezian peste mulțimile suport. Relațiile matematice „generează” deci noi mulțimi. În MMED, aceste noi mulțimi se numesc grafuri de asociații și sunt evident considerate tot mulțimi de obiecte.
Vom vedea însă, în secțiunea 1.5.1, că grafurile asociațiilor nu sunt doar mulțimi „amorfe” de obiecte, ci ele sunt structurate de funcționalități interne, exprimabile cu ajutorul constrângerilor de tip minimal injectivități.
MMED păstrează pentru asociații definiția alternativă a relațiilor matematice din modelul relațional, unde ordinea suporților este înlocuită cu „roluri” (i.e. nume unice).
Desigur că același lucru s-ar putea obține considerând o relație de echivalență adecvată peste mulțimea tuturor produselor carteziene posibile (peste o mulțime de suporți oarecare), echivalență care să partiționeze produsele în clase conținând elemente echivalente ce diferă între ele doar printr-o permutare a suporților. Esențială însă în orice asemenea abordare „imună” la permutări este, evident, cerința unicității numelor suporților oricărei asociații.
Exemplul 1.12: Într-o bd universitară, ar putea fi nevoie de asociația COND_ÎNSCRIERE care să memoreze, pentru fiecare curs, submulțimea cursurilor a căror absolvire prealabilă condiționează înscrierea la acel curs. Matematic, această relație este deci definită peste CURSURI CURSURI. În bd însă, trebuie asociat un „rol” cel puțin uneia dintre cele două apariții ale CURSURI, pentru a putea distinge unic suporții prin nume. De exemplu, COND_ÎNSCRIERE ar putea fi definită peste CURSURI (la care se permite înscrierea) și PRECONDIȚII CURSURI (a căror absolvire condiționează înscrierea).
Ecranul afișând colecția mulțimilor de asociații dintr-o bd MatBase, care se obține selectând „Relationships” din meniul „Sets”, este prezentat în figura 1.6.
În MatBase, nu doar pentru a permite unicitatea numelor suporților oricărei asociații, ci și pentru a da utilizatorilor posibilitatea de a defini sinonime pentru oricare dintre conceptele manipulate, sunt oferite trei mulțimi de entități și două funcții sistem dedicate acestui scop și anume:
Fig. 1.6: Colecția mulțimilor de asociații pentru o bd MatBase
CONCEPTE, o reuniune a mulțimilor de entități de tip (scheme de) bd, entități, asociații, atribute, funcții, constrângeri etc., adică a orice este identificat prin (unul sau mai multe) nume.
SINONIME, ale cărei elemente sunt toate numele de concepte cunoscute sistemului.
IDENTIFICATORI, care este mulțimea cât a SINONIME factorizată de relația de echivalență „sinonimie” (două sinonime sunt echivalente dacă și numai dacă denumesc același concept).
Sinonimie : SINONIME IDENTIFICATORI, surjecția canonică asociată relației de echivalență „sinonimie”.
Identificare : IDENTIFICATORI CONCEPTE, surjecția de identificare.
De remarcat că IDENTIFICATORI este un sistem de reprezentanți pentru SINONIME, adică IDENTIFICATORI SINONIME, iar Sinonimie este idempotentă.
1.2.2.2.3 Ierarhii de asociații
MMED încurajează în mod natural construcția ierarhică de asociații peste grafuri ale altor asociații, fără nici o restricție de adâncime a „încuibării” lor una în alta. Aceasta permite atât o proiectare structurată a schemei bd, cât și garantarea menținerii implicite a unor constrângeri (ce nu mai trebuie deci explicitate). O factorizare corectă a schemei de bd cu ajutorul ierarhizării asociațiilor asigură, în plus, „normalitatea” schemei și evită anomaliile de actualizare.
Exemplul 1.13: Fie LOC mulțimea de localități în care, de-a lungul timpului, au fost găzduite concursuri olimpice, iar PROBE mulțimea acestor concursuri ce constituie olimpiadele sportive. Pentru a memora date despre desfășurarea concursurilor, trebuie definită și o asociație LOCALIZ_CONCURS peste cele două mulțimi de entități suport de mai sus (LOC și PROBE, vezi DE-A din figura 1.7 și bd relațională din figura 1.8).
O pereche oarecare (l, c) LOCALIZ_CONCURS memorează faptul că în localitatea l a avut loc un concurs olimpic c. Această asociație binară nu este evident funcțională, deoarece unele concursuri se desfășoară în mai multe localități, iar într-o localitate se organizează adesea mai multe concursuri. Dacă s-ar dori și informații privind participarea sportivilor la aceste concursuri, cea mai naturală modelare ar considera o relație binară PARTICIPĂRI, definită peste mulțimea de entități SPORTIVI și peste graful asociației LOCALIZ_CONCURS.
O pereche oarecare (s, (l, c)) PARTICIPĂRI memorează faptul că sportivul s a luat parte la concursul (l, c). Nici această asociație nu este funcțională, deoarece un sportiv poate participa la mai multe concursuri, iar concursurile, evident, nu sunt organizate pentru un singur sportiv!
Schema MMED a acestei bd, simplificată pentru a furniza doar numele diverselor tipuri de entități precum și definiția tipurilor de asociații implicate, este deci următoarea:
LOC
PROBE
SPORTIVI
LOCALIZ_CONCURS = (LOC, PROBE)
PARTICIPARI = (SPORTIVI, LOCALIZ_CONCURS)
Desigur că PARTICIPĂRI ar putea fi definită direct peste cele trei mulțimi de entități suport, chiar dacă acest lucru este nenatural. O asemenea modelare „nenormalizată” ar putea însă da naștere la redundanțe inutile și deci la anomalii de actualizare: de exemplu, dacă ar interesa și data de început, de sfârșit (ori durata) concursurilor, bugetul lor, sau arbitrii ori numărul de spectatori etc., aceste informații ar fi evident multiplicate inutil pentru fiecare dintre sportivii participanți la concursuri!
PARTICIPĂRI
SPORTIVI LOCALIZ_CONCURS
PROBE LOC
Fig. 1.7: Un exemplu de ierarhie de asociații
1.2.3 Mulțimi calculate
În general, construcția acestor mulțimi se face enumerativ, deși sunt cazuri în care este nevoie și de constructorii ASet și PSet pentru aceasta.
Exemplul 1.14:
ASet(PERSOANE) = CADRE_DIDACTICE ANGAJAȚI STUDENȚI
PSet(PROFESORI) = x CADRE_DIDACTICE Titlu(x) 'profesor'.
1.3 Funcții
Definiția 1.7. Mulțimea funcțiilor M este suma directă M = A F CM, unde:
A V este o mulțime finită nevidă de funcții parțiale numite atribute;
F este o mulțime finită de funcții parțiale numite funcții structurale;
CM S – S – este o mulțime finită de funcții parțiale calculate cu ajutorul celor din A și/sau F.
Ecranul afișând meniul funcțiilor dintr-o bd MatBase, care se obține selectând „Mappings” din meniul principal, este cel prezentat în figura 1.9.
1.3.1 Atribute
În orice bd sau bc, obiectele prezintă interes în special prin prisma proprietăților lor.
Exemplul 1.15: despre PERSOANE interesează, de obicei, numele, prenumele, sexul, data nașterii, un cod de identificare (codul numeric personal, numărul dosarului de asigurare socială etc.), domiciliul, numărul de telefon, adresa e-mail etc. Aceste proprietăți descriu, caracterizează și disting unic obiectele.
Și în MMED, la fel ca și în MRD, proprietățile fundamentale ale obiectelor sunt formalizate cu ajutorul atributelor. Ca atare, MMED oferă și o mulțime finită nevidă de atribute A.
Definiția 1.8. Un atribut este o funcție, în general parțială, definită pe o mulțime de obiecte O și cu valori într-o mulțime de valori V V , i.e. A V .
Exemplul 1.16: Iată câteva exemple de atribute:
Nume : PERSOANE ASCII(64)
Sex : PERSOANE 'F', 'M'
DataNaștere : PERSOANE DATA
Localitate : LOCALITĂȚI ASCII (32) etc.
Ecranul afișând mulțimea atributelor dintr-o bd MatBase, care se obține selectând „Attributes” din meniul „Mappings”, este prezentat în figura 1.10.
De notat că, datorită necesității de a permite valori nule, total definirea funcțiilor este privită și în MMED ca o constrângere, exact ca în MRD (și anume, trivial, drept un caz particular al constrângerilor de existență).
Exemplul 1.17: dacă atributul Nume de mai sus nu trebuie să admită valori nule (i.e. trebuie să fie total definit), acest lucru trebuie explicit specificat și se face, de exemplu, astfel: Nume : PERSOANE CHAR(64), total.
MMED acceptă următoarea prescurtare convenabilă pentru definiția atributelor: dacă ea este plasată imediat după cea a mulțimii de obiecte domeniu corespunzătoare (deci nici o ambiguitate nu este posibilă) atunci domeniul poate fi omis, fiind subînțeles.
Exemplul 1.18: următoarele definiții sunt echivalentele abreviate ale celor de mai sus: PERSOANE
Nume CHAR(64), total
Sex 'F', 'M'
DataNaștere DATA
Exemplul 1.19: În MatBase, A este inițializată cu peste 70 de atribute sistem, dintre care, de exemplu:
Parola : UTILIZATORI ASCII(16)
Den_tip_acces : TIP_ACCES 'interzis', 'citire', 'inserție', 'ștergere',
'modif.', 'cit.struct.', 'act.struct.', 'creare bd'
Aritate_asoc : ASOCIAȚII NAT.
Fig. 1.8: O bd cu o ierarhie de asociații
Fig. 1.9: Meniul funcțiilor MatBase
Desigur că aceste atribute pot fi cel mult vizualizate de utilizatori (dacă au acest drept de acces) dar în nici un caz șterse, deși valorile lor sunt modificate explicit sau implicit odată cu definirea de noi (scheme de) bd sau actualizarea bd existente.
De remarcat că nici MMED nu permite atribute „nenormalizate”, adică cu valori în produse carteziene de mulțimi de valori, cu excepția celor luând valori în mulțimile sistem DATA sau TIMP (căci, trivial, ambele aceste mulțimi de valori sunt, de fapt, produse carteziene).
Este naturală și obligatorie însă asigurarea posibilității de a defini atribute și pe grafuri de asociații.
Exemplul 1.20: revenind la Exemplul 1.11, s-ar putea dori adăugarea următoarelor atribute definite pe asociația ABSOLVIRE:
DataAbsolvirii DATA
Nota NAT.
Exemplul 1.21: similar, referindu-ne de această dată la Exemplul 1.14, s-ar putea defini pe asociația LOCALIZ_CONCURS atributele:
Data_început DATA
Data_sfârșit DATA
Încasări PREȚ
TotalSpectatori NAT.
Fig. 1.10: Mulțimea atributelor pentru o bd MatBase
1.3.1.1 Identificatori de obiecte
MMED furnizează automat pentru orice mulțime de obiecte un identificator de obiect (idob), folosit exclusiv pentru identificarea (sintactică) unică și minimală a obiectelor și tipurilor în bd. Notată cu numele mulțimii de obiecte prefixat de caracterul '#', o asemenea cheie este întotdeauna peste tot definită (i.e. nu admite valori nule), are codomeniul NAT și nu face decât să „numeroteze” obiectele în mod unic (în cadrul mulțimii de obiecte respective):
#O : O NAT, #O injectivă, deci cheie.
Cum cheile sunt echivalente, din considerații legate de optimizarea procesării legăturilor între tipuri, navigării prin schema bd și interogărilor, MMED distinge unic cu ajutorul identificatorilor de obiect și tipurile de obiecte.
Exemplul 1.22: #PERSOANE: PERSOANE NAT este identificatorul de obiect atașat mulțimii PERSOANE.
De remarcat că MMED adaugă câte un identificator de obiect și grafurilor de asociații, în primul rând pentru evitarea anomaliilor de actualizare.
Exemplul 1.23: Revenind la Exemplul 1.14, identificatorul de obiect atașat asociației LOCALIZ_CONCURS este:
#Localiz_Concurs : LOCALIZ_CONCURS NAT
Evident că, în cursul traducerii schemelor MMED în MRD, identificatorii de obiect sunt implementați prin chei surogat.
De remarcat abrevierea standard pentru funcțiile (minimal) injective folosind dubla săgeată:
Exemplul 1.24: Definiția de mai sus este echivalentă cu:
cheie #Localiz_Concurs : LOCALIZ_CONCURS NAT.
1.3.2 Funcții structurale
În componența MMED intră și o mulțime finită de funcții structurale F (prescurtat funcții).
Definiția 1.9. O funcție structurală este o funcție, în general parțială, definită pe o mulțime de obiecte O1 și cu valori într-o mulțime de obiecte O2.
Orice asemenea funcție structurează suplimentar posetul (, ). Nici F nu este niciodată vidă în vreo implementare, chiar dacă schema bd utilizator nu ar conține funcții, căci MatBase are nevoie de peste 60 de funcții sistem.
Exemplul 1.25:
Sinonimie : SINONIME IDENTIFICATORI,
Proprietar_BD : BAZE_DATE UTILIZATORI,
Domeniu : FUNCȚII OBIECTE,
Codomeniu : FUNCȚII MULȚIMI F.
Desigur că nici aceste funcții nu pot fi eliminate din model de nici un utilizator, dar, în funcție de drepturile de acces pe care le au, utilizatorii pot (explicit sau implicit) să adauge sau să șteargă elemente în/din ele.
Proiectanții / utilizatorii bd pot defini și ei funcții în MMED.
Exemplul 1.26: Exemple de funcții structurale definite de utilizator sunt:
Înscriere : STUDENȚI CURSURI
Curs : CURSURI FACULTĂȚI
Predare : CURSURI CADRE_DIDACTICE
LocMuncă : CADRE_DIDACTICE CATEDRE
Organizare : CATEDRE FACULTĂȚI
Decan : FACULTĂȚI CADRE_DIDACTICE.
Formal, F , adică F este inclusă în mulțimea tuturor funcțiilor definite pe și cu valori în mulțimi din . Evident că funcțiile sunt un caz particular de relații, deci de asociații (și anume, asociații binare funcționale). Spre deosebire de acestea însă, funcțiile nu „generează” noi mulțimi de obiecte (ci doar stabilesc „pointeri” între obiecte existente) și nici nu au o structură internă complexă, așa cum vom vedea că este, în general, cazul asociațiilor. Din acest punct de vedere, desigur, am putea considera funcțiile ca fiind niște asociații binare „degenerate”.
Ecranul afișând mulțimea funcțiilor structurale dintr-o bd MatBase, care se obține selectând „Structural functions” din meniul „Mappings”, este prezentat în figura 1.11.
1.3.2.1 Funcții unitate
Definiția 1.10: O funcție 1M : M M definită astfel: 1M(x) = x ,xM, se numește funcție unitate.
Exemplul 1.27: Pentru mulțimea ȚĂRI, din figura 1.8, 1ȚĂRI(2) = 2.
Fig. 1.11: Mulțimea funcțiilor structurale pentru o bd MatBase
Evident că, astfel definite, funcțiile unitate sunt funcții structurale.
Matematic, pot fi desigur definite funcții unitate și pe mulțimi de valori, însă acestea nu au nici o relevanță din punctul de vedere al bazelor de date.
1.3.3 Tipuri de obiecte
Definiția 1.11. Definim următoarea relație de echivalență („egalitatea domeniilor”): orice funcții f, gM sunt echivalente dacă și numai dacă, prin definiție, au același domeniu (i.e. dom(f) = dom(g)).
M este canonic partiționată de această relație de echivalență, care grupează toate funcțiile definite pe o aceeași mulțime de obiecte, iar mulțimea cât astfel obținută este evident izomorfă cu .
Definiția 1.12. Reprezentanții claselor de echivalență alcătuind această mulțime cât se numesc tipuri (de obiecte). Ca atare, tipul de obiecte corespunzător unei mulțimi fixate oarecare de obiecte O este: = f M dom(f) = O M .
Notația folosită pentru tipuri este deci cea standard în matematică pentru clasele de echivalență: numele reprezentantului clasei căruia i se adaugă „căciula”. Desigur că, prin abuz notațional, ca și în matematică, căciula poate fi omisă atunci când nu este nici un pericol de ambiguitate.
Tipurile de obiecte sunt adesea interpretate drept produsul familiei tuturor atributelor definite pe mulțimea respectivă de obiecte:
=
Definiția 1.13. Valoarea pentru un element oarecare oO, constituie descrierea fundamentală (primitivă) a acelui obiect în bd („fundamentală” doar, deoarece o descriere completă trebuie să includă și legăturile sale cu alte obiecte prin intermediul asociațiilor).
Exemplul 1.28: Orice persoană ar putea fi descrisă de tipul de obiecte:
= #Persoane, Nume, Prenume, Sex, DataNașterii, LocNaștere, e-mail,
notat alternativ cu:
= #PersoaneNumePrenumeSexDataNașteriiLocNaștere e-mail.
De notat că tipul asociațiilor conține implicit toate proiecțiile canonice aferente, deoarece altfel nu ar putea fi distinse elementele asociate.
Exemplul 1.29: Revenind la Exemplul 1.14 (a se vedea figura 1.5), tipul corespunzător asociației PARTICIPĂRI include proiecțiile canonice:
Sportiv = prSPORTIVIPARTICIPĂRI și
LocConcurs = prLOCALIZ_CONCURSPARTICIPĂRI.
În absența oricăreia dintre ele, evident că nu am putea stabili graful acestei asociații. În concluzie, orice participare ar putea fi descrisă de tipul de obiecte:
= #ParticipăriSportivLocConcursPrezențe.
Similar, tipul corespunzător asociației LOCALIZ_CONCURS include proiecțiile canonice: Loc = prLOC LOCALIZ_CONCURS și
Concurs = prPROBELOCALIZ_CONCURS.
Orice localizare a concursurilor ar putea fi descrisă de tipul de obiecte:
= #LocConcursLocConcursDataInc.DataSf.Spect.Încasări.
1.3.4 Instanțe
Dată fiind orice funcție : A B, ne reamintim că imaginea ei este mulțimea valorilor calculate de funcție: Im() = (A) = y Bx A, y = (x) B.
Exemplul 1.30: În bd din figura 1.5, imaginea atributului Țara (definit pe ȚĂRI) este {’RO’,’USA’,’F’,’CAN’,’BR’,’S’,’AG’}, în timp ce imaginea funcției structurale Țara (definită pe LOC) este {2,3}.
Definiția 1.14. Pentru orice mulțime de obiecte O¸ Im(Ô) se numește instanță (sau conținut) a(l) mulțimii; se numește instanță (sau conținut) a(l) unei bd reuniunea imaginilor tuturor tipurilor definite în schema acelei bd. Dacă este colecția tuturor mulțimilor de obiecte, atunci instanța bd este notată, prin extensie, cu:
Im() = O Im(Ô).
Exemplul 1.31: În bd din figura 1.5, instanța mulțimii de obiecte PARTICIPĂRI este exact conținutul tabelei omonime, adică mulțimea liniilor sale; instanța întregii bd este reuniunea conținuturilor tuturor celor opt tabele ale sale.
1.3.5 Chei
Definiția 1.15. Orice (sub)produs K al unui tip oarecare se numește cheie (a lui O) dacă și numai dacă (privit ca un produs de funcții) K este minimal injectivă (adică dacă este injectivă și nici o submulțime proprie a sa nu este injectivă).
Evident că orice atribut injectiv sau funcție structurală injectivă este cheie și că orice tip poate avea mai multe chei simultan. Trivial, doar valorile cheilor identifică unic obiectele în bd.
Exemplul 1.32: Capitala : ȚĂRI LOCALITĂȚI este injectivă, deci cheie; produsul SerieBINrCI : PERSOANE CHAR(2)NAT(6) este minimal injectiv, deci cheie.
Definiția 1.16. Orice submulțime S a unui tip oarecare se numește supercheie (a lui O) dacă și numai dacă (privită ca un produs de funcții) S este injectivă (dar nu neapărat minimal injectivă). Evident, orice cheie este o supercheie și orice funcție injectivă este supercheie.
Propoziția 1.17. Orice tip de obiecte minus identificatorul de obiect corespunzător este supercheie.
Corolarul 1.18. Orice tip de obiecte ce nu este o submulțime a altui tip minus identificatorul de obiect corespunzător are cel puțin o cheie.
Se observă că orice tip poate avea mai multe chei (întotdeauna cel puțin două: identificatorul de obiect al mulțimii și însuși tipul minus identificatorul de obiect corespunzător sau o submulțime a acestuia, cu excepția submulțimilor – care pot să nu aibă drept cheie decât identificatorul de obiect, căci moștenesc toate cheile mulțimilor ce le includ).
Definiția 1.19. În cazul asociațiilor, cheile formate numai din proiecțiile canonice se numesc chei structurale.
Exemplul 1.33: MagazieProdus este cheia structurală a asociației STOCURI (unde Magazie și Produs sunt abrevieri ale prMAGAZIISTOCURI, respectiv prPRODUSESTOCURI).
1.3.6 Caracterizarea funcțiilor structurale
Funcțiile structurale pot fi privite drept reprezentanți ai unor clase de echivalență alcătuite din funcțional dependențe.
Definiția 1.20. Fie S o mulțime și f o funcție definită pe S; definim relația nucleu atașată funcției f prin: Kerf = {(x,y)SSf(x)=f(y)}.
Definiția 1.21. Fie S o mulțime și f, g două funcții total definite pe S; spunem că g depinde funcțional de f (sau f determină funcțional g) și notăm cu f g dacă și numai dacă Kerf Kerg. Relația f g se numește funcțional dependență (fd).
Exemplul 1.34: Fie S = PERSOANE, f = CNP, g = Nume; evident că între aceste două atribute există fd CNP Nume.
Propoziția 1.22.(caracterizarea fd): f g ! h: Imf Img a.î. g = h f.
Demonstrație:
() Fie funcția h : Imf Img a.î. yImf, h(y) = z, unde y = f(x) și z = g(x).
Demonstrăm că h este total definită: yImf, xS, y = f(x); cum g este total definită,
xS, zImg, z = g(x) yImf, h(y) = z.
Demonstrăm că h este bine definită: fie t, uImf, t = u; din definiția lui h , x,yS a.î. h(t) = v, unde t=f(x), v=g(x), iar h(u)=w, unde u=f(y) și w=g(y); t=u f(x) = f(y) (x,y)Kerf; dar Kerf Kerg (x,y)Kerg g(x) = g(y) v = w h(t) = h(u).
Demonstrăm că g = h f; xS, notăm z = g(x)Img și y = f(x)Imf; conform definiției lui h, h(y) = z h(f(x)) = g(x) h f = g.
Demonstrăm că h este unică: presupunem că h' : Imf Img a.î h' f = g xImf, yS, x = f(y) a.î. h'(f(y)) = g(y); conform definiției lui h, h(x) = g(y) h(x) = h'(x) h h'.
() Presupunem prin reducere la absurd că: f g; Kerf Kerg (x,y)Kerf a.î. (x,y)Kerg (x,y)S2, f(x) = f(y) și g(x) g(y); cum h este funcție, din f(x) = f(y) h(f(x)) = h(f(y)); conform definiției lui h g(x) = g(y) contradicție cu presupunerea făcută f g. Q.e.d.
Propoziția 1.34. (caracterizarea funcțiilor structurale) : F, o funcție : A B unde A,B și kAcu proprietatea că kA este cheie și burmătoarele două afirmații sunt adevărate:
(i) kA b
(ii) există o unică funcție fd : ImkA Imb a.î. fd kA = b .
A B
kA b
ImkA Imb
fd
Demonstrație:
(i) Fie (x,y)KerkA; cum kA este cheie kA injectivă
x = y b(x) = b(y) (x,y)Kerb.
(ii) Definim fd : ImkA Imb a.î. yImkA, fd(y) = z, unde y = kA(x) și z = b(x).
Demonstrăm că fd este total definită: yImkA, xA, y = kA(x); cum bd este total definită, xA, zImb, z = bd(x).
Demonstrăm că fd este bine definită: fie t, uImkA, t = u; conform definiției lui fd, x,yA a.î. fd(t) = v, unde t = kA(x), v = b(x) și fd(u) = w, unde u = kA(y) și w = b(y);
t = u kA(x) =kA(y) x = y (kA este cheie, deci injectivă) bd(x) = bd(y) v = w fd(t) = fd(u).
Demonstrăm că b = fdkA; xA, notăm z = b(x)Imb și y = kA(x)ImkA; conform definiției lui fd, fd(y) = z fd(kA(x)) = b(x) fd kA = b.
Demonstrăm că fd este unică: presupunem că fd' : ImkA Imb a.î. fd' kA = b; xImkA, yA, x = kA(y) a.î. fd'(kA(y)) = b(y); conform definiției lui fd, fd(x) = b(y) fd(x) = fd'(x) fdfd'. Q.e.d.
Observația 1.35:
m 2, căci orice tip are, pe lângă identificatorul de obiect, cel puțin o cheie.
Dacă m este numărul cheilor tipului iar n este cardinalul tipului , atunci este reprezentantul clasei de echivalență a celor mn funcțional dependențe de forma kA i bj, kA i
kA i cheie, bj .
Utilizatorul MMED nu are nevoie să specifice nici o FD „inter-tipuri”; specificarea funcțiilor din F este suficientă în acest sens.
Comparativ cu fd, funcțiile structurale sunt, d.p.d.v. semantic, mult mai naturale, iar d.p.d.v. sintactic mai compacte.
Coroborând subpunctul de mai sus cu observația (5.4.b), rezultă că în MMED nu este nevoie de specificarea nici unei FD între atributele din A .
De notat și că, exact ca în cazul atributelor, pentru a permite valori nule, total definirea funcțiilor structurale este de asemenea considerată ca fiind o constrângere.
1.3.7 Formalizarea principiului propagării cheilor
Evident că, atunci când traducem funcțiile structurale în MRD, ar fi o risipă de spațiu să le implementăm printr-o tabelă; mult mai economic, ele pot fi implementate ca atribute, conform așa numitului “principiu al propagării cheilor”, formalizat de următoarea teoremă:
Teorema 1.36.(„principiul propagării cheilor”): pentru orice funcție : A B F, și pentru orice cheie k, k , există o unică funcție p a.î. p = k .
A B
p k
Imk
Demonstrație: Definim p: A Imk a.î. xA, p(x) = y, unde y = k(x).
Demonstrăm că p este total definită: xA, yImk, y = k(x) = p(x).
Demonstrăm că p este total definită: fie x,yA, x = y; conform definiției lui k, k(x) = =k(y) p(x) = p(y).
Demonstrăm că p = k f: xA, notăm prin y = k(x)Imk; conform definiției lui p,
p(x) = y k(f(x)) = p(x) k f = p.
Demonstrăm că p este unică: presupunem că p' : A Imk a.î. k f = p' xA, k(f(x)) =p'(x); conform definiției lui p,
p(x) = k(x) p(x) = p'(x) p p'. Q.e.d.
Corolarul 1.37. injectivă p injectivă.
Demonstrație: Fie x,yA, a.î. p(x) = p(y); presupunem că xy; cum f este injectivă f(x) f(y); cum k este injectivă, k(f(x)) k(f(y)) p(x) p(y), contradicție. Q.e.d.
De observat în modelul relațional kp se numește cheie străină, iar comutativitatea diagramei de mai sus trebuie explicit asertată în schema bd printr-o dependență de incluziune, în timp ce MMED garantează automat validitatea oricărei asemenea incluziuni.
Observația 1.38.
Dacă p nu este cheie, atunci MMED nu trebuie să adauge nici o FD la schema bd, deoarece singurele FD în care p este implicată sunt cele triviale și cele „acoperite” de principiul funcțiilor structurale (care sunt reprezentate prin cheia străină propagată).
Nici dacă p este cheie nu trebuie adăugată explicit de utilizatorii MMED nici o constrângere suplimentară, întrucât sistemul adaugă automat dependența de cheie corespunzătoare.
Având în vedere a) și b) de mai sus, observația 1.11.c) rămâne validă și în prezența funcțiilor structurale.
Prezentăm în continuare un exemplu de aplicare a propagării cheilor în MMED:
Exemplul 1.36 : Fie tipurile de obiecte
LOCALITĂȚI = #Loc, Localitate și
JUDEȚE = #Jud, Județ, CodAuto, PrefixTel.
Fie funcția JudLoc : LOCALITĂȚI JUDEȚE, care precizează cărui județ îi aparține fiecare localitate în parte. Un posibil conținut al acestei bd, inclusiv graful JudLoc, este prezentat în figura 1.12.
Propagarea cheii Județ = #Jud JudLoc în tipul LOCALITĂȚI, care va avea deci structura LOCALITĂȚI = #Loc, Localitate, Județ, permite eliminarea tabelei corespunzătoare tipului de asociații „degenerat” JudLoc din schema bd. Conținutul noii bd astfel obținute este prezentat în figura 1.13.
Dacă îmbogățim această bd cu mulțimile de obiecte PERSOANE și ȚĂRI și cu funcțiile structurale LocNaștere : PERSOANE LOCALITĂȚI și ȚaraJud : JUDEȚE ȚĂRI se obține, similar, schema relațională din figura 1.14.
1.3.8 Funcții calculate
Definiția 1.39. Se numește funcție calculată o funcție ale cărei valori se pot obține oricând din evaluarea unei expresii de calcul.
Pentru o mai ușoară monitorizare a schemei și conținutului bd gestionate, metacatalogul MMED înglobează și peste 20 de atribute sistem calculate.
Exemplul 1.37: Tipul de entități BAZE_DATE include și atributele calculate *Nr_concepte (ce memorează cardinalul CONCEPTE pentru fiecare bd în parte), *Nr_obiecte (ce memorează suma cardinalelor tuturor elementelor din MULȚIMI pentru fiecare bd) și *Koct_ocup (ce ține minte totalul spațiului ocupat cu memorarea schemei și conținutului fiecărei bd).
La rândul lor, tipurile ASOCIAȚII și CHEI au fiecare câte un atribut calculat numit *Aritate (ce memorează aritatea fiecărei asociații, respectiv chei, i.e. numărul de suporți, respectiv de atribute implicate).
Desigur că MMED permite și utilizatorilor definirea de atribute calculate, pentru care trebuie precizate, nu doar numele, ci și formula de calcul corespunzătoare fiecăruia în parte; actualizarea valorilor acestor atribute este făcută de sistem, ori de câte ori se impune acest lucru.
Exemplul 1.38: *Vârsta = azi() – DataNașterii
*TVA = Coef_TVA x Valoare
*DePlată = Total – Achitat etc.
De remarcat că numele atributelor calculate este întotdeauna prefixat de caracterul ‚*’.
Evident, atributele calculate au menirea de a mări viteza de răspuns la interogări; prețul plătit în schimb este, pe de-o parte, spațiul de memorare suplimentar implicat, iar, pe de alta, obligativitatea actualizării permanente și protejării valorilor calculate, care trebuie să fie accesibile utilizatorilor bd numai în citire, pentru a menține integritatea bd. În plus, trebuie întotdeauna avute în vedere particularitățile exploatării bd: dacă costuri le calculării și memorării acestor atribute derivate sunt sensibil mai mari decât câștigurile de viteză aferente, trivial, trebuie renunțat la introducerea lor în schemă.
De exemplu, dacă volumul și frecvența actualizării datelor implicate sunt mult mai mari față de totalul timpului de interogare câștigat (pentru că, desigur, contează mult și frecvența acestor interogări, nu doar timpul necesar unei singure execuții), atunci introducerea de atribute calculate în schemă are efect contrar celui scontat, i.e. degradarea performanțelor bd.
Sunt însă desigur cazuri în care câștigurile sunt substanțiale; de exemplu, în bd cu frecvență și volum de actualizări a datelor reduse, în timp ce interogările sunt extrem de frecvente și altfel (i.e. în absența unor atribute calculate) costisitoare. Figura 1.15 prezintă un asemenea exemplu convingător. În concluzie, redundanța datelor indusă de atributele calculate trebuie să fie întotdeauna atât justificată, cât și strict controlată.
Exact ca și în cazul atributelor, MMED permite natural și definirea de funcții structurale calculate.
Exemplul 1.39: *ȚaraNaștere=ȚaraJudJudLocLocNaștere : PERSOANE ȚĂRI
Fig. 1.12 O bd înainte de propagarea cheii pentru o funcție structurală
Fig. 1.13 Bd din figura 1.12 după propagarea cheii pentru funcția structurală
Fig. 1.14 O bd obținută în urma propagării cheilor pentru trei funcții structurale
Figura 1.15 prezintă tabela PERSOANE a bd de mai sus, căreia i s-a adăugat însă, pentru mărirea vitezei interogărilor, funcția calculată *ȚaraNaștere. Se observă că memorarea ei scutește două joinuri, „scurtcircuitând” tabelele LOCALITĂȚI și JUDEȚE.
Fig. 1.15 Tipul PERSOANE al bd din figura 1.14 îmbogățit cu atributul calculat *ȚaraNaștere
În plus, dacă în general este adevărat că pentru aceste funcții se memorează doar expresia de calcul (precum în cazul procedurilor catalogate SQL), mult mai adesea totuși decât în cazul atributelor calculate este aleasă soluția duală, a memorării și actualizării permanente a valorilor aferente, pentru că, după reuniune, în ciuda algoritmilor extrem de performanți la dispoziție, joinul rămâne cel mai scump operator relațional; ca atare, economisirea în acest mod a calculării frecvente a unui lung lanț de joinuri (în special pentru tabele cu cardinalitate foarte mare) este spectaculoasă (mai ales că ea este adesea făcută cu un cost aproape insesizabil).
1.4 Constrângeri
Pentru a permite o modelare a datelor cât mai corectă, orice model al datelor include posibilitatea asertării explicite a unor clase de constrângeri. În MMED, sunt permise 18 asemenea clase, care sunt detaliate în această secțiune:
constrângeri de domeniu (i.e., de fapt, codomeniu al atributelor)
constrângeri obiect (i.e. extinderea constrângerilor tuplu la obiecte)
constrângeri de existență (i.e. de domeniu a funcțiilor atribut și / sau structurale)
incluziunea, egalitatea, reuniunea, disjuncția și partiționarea mulțimilor (de obiecte sau valori)
minimal injectivitatea, surjectivitatea, egalitatea și idempotența funcțiilor (atribute sau funcții structurale)
sisteme de reprezentanți
reflexivitatea, simetria, antisimetria, tranzitivitatea și aciclicitatea grafurilor de relații binare.
Deci MMED include în definiția sa și o mulțime finită C de constrângeri de integritate. Sintactic, acestea ar putea fi exprimate cu ajutorul formulelor calculului predicativ de ordin întâi. Practic însă, doar primele două clase (domeniu și obiect) folosesc această sintaxă. Toate celelalte 16 clase beneficiază de abrevieri sintactice consacrate (standard în matematică, ori de câte ori posibil pe calculator) pentru tipurile particulare respective de asemenea formule logice.
Ecranul afișând meniul constrângerilor dintr-o bd MatBase, care se obține selectând „Constraints” din meniul principal, este cel prezentat în figura 1.16.
Fig. 1.16: Meniul constrângerilor MatBase
Ecranul afișând mulțimea tuturor constrângerilor dintr-o bd MatBase, care se obține selectând „All constraints” din meniul „Constraints”, este prezentat în figura 1.17.
Fig. 1.17: Mulțimea tuturor constrângerilor dintr-o bd MatBase
De remarcat că în MMED nu este nevoie și nici nu este permisă specificarea de FD, DMV sau DJ. DMV și DJ sunt formalizate cu ajutorul asociațiilor, iar singurele FD implicit manipulate de MMED sunt cele induse de chei și de funcțiile structurale.
Observația 1.40:
De fapt, MMED folosește din modelul relațional doar constrângerile de existență, dependențele de domeniu, de cheie, precum și pe cele de incluziune, adică exact ce este necesar pentru FNDC și pentru manipularea valorilor nule.
Lucrul cel mai important de remarcat însă este că, așa cum vom dovedi rând pe rând în subsecțiunile următoare, considerarea acestor clase de constrângeri nu este o chestiune de „gust”: ignorarea lor poate conduce la grave anomalii de actualizarea datelor. Ca atare, MMED le include printre constrângerile primitive și modifică corespunzător accepțiunea relațională a noțiunilor de constrângere primitivă, compatibilitate semantică și anomalie de actualizare.
1.4.1 Constrângeri provenite din modelul relațional
Nu vom mai rediscuta în detaliu tipurile de constrângeri binecunoscute din modelul relațional, care sunt preluate și de MMED, cu minore diferențe. De remarcat că dependențele de incluziune au fost generalizate ca incluziuni de mulțimi, cele tuplu au fost generalizate în constrângeri obiect și că nu există chei străine.
1.4.1.1 Constrângeri de domeniu
Ne reamintim că prin constrângeri de domeniu, MRD înțelege de fapt specificarea codomeniilor atributelor. Am definit până acum în MMED aceste codomenii mai degrabă generic: este momentul să intrăm în detalii, deoarece, pe de-o parte, astfel vom putea modela mult mai apropiat de realitate orice subunivers, iar pe de alta, resursele de memorie ale calculatoarelor sunt limitate și nici „inteligența” lor nu strălucește încă măcar în această privință.
În subsecțiunea 1.2.2.1 am prezentat cei trei constructori de mulțimi la dispoziție, precum și (pentru Enum și PSet) două exemple de mulțimi de valori construite cu aceștia (CULORI, respectiv EXERC_FINANCIAR), submulțimi, evident, prima din ele a tipului CHAR*, iar cea de-a doua a tipului DATE.
Pe lângă acești constructori, MMED oferă încă un tip de abrevieri standard pentru specificarea mulțimilor de valori: NAT(n) NAT, n NAT, semnifică submulțimea naturalilor cu cel mult n cifre (de exemplu, dacă n = 2, a naturalilor x cu proprietatea că 0 x 99).
Similar, se admit în MMED prescurtări de tipul INT(n), RAT(n), PREȚ(n). CHAR(n) semnifică submulțimea șirurilor cu cel mult n simboluri ai alfabetului CHAR. DATE(d,e), respectiv TIME(s,t) semnifică submulțimile datelor calendaristice cuprinse (inclusiv) între datele d e, respectiv ale momentelor de timp dintre s t.
Exemplul 1.40: În loc de Nume : PERSOANE CHAR*, este uzuală modelarea de tip Nume : PERSOANE CHAR(32) (dacă numele persoanelor poate avea cel mult 32 de caractere în contextul respectiv). Similar, în loc de o definiție generică de tip DataNașterii : PERSOANE DATA, este preferabilă una mai precisă, de forma DataNașterii : PERSOANE DATA(1.1.1900,31.12.2000) (admițând că interesează doar persoanele născute în secolul XX), iar în loc de Nivel : DIRECTOARE NAT, ceva de forma Nivel : DIRECTOARE NAT(4) (admițând că maximum posibil de nivele în ierarhia directoarelor este de 10.000).
Desigur că, în general, se pot defini constrângeri de domeniu suplimentare, exprimabile tot cu ajutorul clauzelor Horn din logica de ordin întâi, la fel ca și în cazul constrângerilor obiect, doar că strict referind mulțimi de valori și elemente ale acestora (și nu obiecte).
Exemplul 1.41: card(CULORI) > 2 sau pentru VÂRSTA NAT(3), (xVÂRSTA)(x<150).
De notat că, parțial, în limitele oferite de unealta de implementare a SGBD bazat pe MMED (fie că este vorba, de exemplu, doar de un limbaj de programare, doar de un motor relațional sau de o combinație a acestora), majoritatea constrângerilor de domeniu nu trebuie explicitate decât mai degrabă generic, fiind implicit presupuse. Desigur însă că atât ultimele două exemple furnizate, dar și cele, de exemplu, de tip DATE(d,e) trebuie explicitate în schema MMED corespunzătoare.
Evident și această subclasă este o mulțime, deci nu admite duplicate; mai mult, toate considerentele de la sfârșitul subsecțiunii dedicate constrângerilor obiect se aplică desigur, mutatis mutandis și constrângerilor de domeniu explicite.
1.4.1.2 Chei
Minimal injectivitatea funcțiilor se exprimă prin constrângeri cheie astfel:
pentru orice atribut (produs de atribute) injectiv a, prin declarația „cheie a” sau prin folosirea în definiție a dublei săgeți „“, în loc de cea simplă, „“, obișnuită
pentru orice funcție structurală injectivă , prin folosirea în definiția funcției a dublei săgeți (MMED adăugând implicit în schema bd atât cheia propagată kp corespunzătoare, cât și declarația „cheie kp” aferentă)
pentru orice cheie structurală ks a unei asociații, prin includerea ei în lista cheilor structurale din definiția asociației (MMED adăugând implicit în schema bd declarația „cheie ks”).
Exemplul 1.42: Fie din nou bd din exemplele 1.11 și 1.12; este evident că ea satisface dependențele cheie cheie #Dir și cheie TataDirector. Uzual însă, prima se scrie, odată cu definiția #Dir, sub forma abreviată:
DIRECTOARE
#Dir NAT(8).
Deși nu este uzual, a doua dependență de cheie se poate și ea scrie alternativ sub forma:
TataDirector : DIRECTOARE DIRECTOARE ASCII(256).
Exemplul 1.43: Similar, reconsiderând, bd din figura 1.8 (exemplul 1.9), dacă ar fi nevoie și de adăugarea capitalelor (la țări), formalizarea cea mai elegantă s-ar obține evident cu ajutorul unei funcții structurale injective (căci nu doar fiecare țară are o unică capitală, ci, mai mult, nici o localitate nu poate fi simultan capitală a mai multor țări)
Capitala : ȚĂRI LOCALITĂȚI.
Exemplul 1.44: În sfârșit, rămânând la același exemplu, dar revenind și la observația 1.27b, notăm că declarația tipului de asociații CODIF_POȘTALĂ = (CODURI_POȘTA, LOCALITĂȚI, ADRESE, CODURI_POȘTA, LOCALITĂȚI, LOCALITĂȚI, ADRESE) conține implicit următoarele două dependențe cheie, induse de cele două chei structurale ale sale și anume: cheie prCODURI_POȘTACODIF_POȘTALĂ prLOCALITĂȚICODIF_POȘTALĂ
și cheie prADRESECODIF_POȘTALĂ prLOCALITĂȚICODIF_POȘTALĂ, în timp ce declarația STOCURI = (MAGAZII , PIESE) conține implicit dependența cheie prMAGAZIISTOCURI prPIESESTOCURI (conform lemei 1.6, observației 1.27c și algoritmului 1.31).
De remarcat că produsele minimal injective de funcții pot fi inclusiv mixte, adică alcătuite atât din atribute, cât și din funcții structurale. Pe lângă condiția de minimalitate ce trebuie îndeplinită de orice cheie produs de funcții, este evident și că domeniul tuturor funcțiilor alcătuind un produs trebuie să fie același (i.e. toate trebuie să aparțină aceluiași tip de obiecte).
1.4.1.3 Constrângeri de existență
Constrângerile de existență (CE) beneficiază în MMED de două tipuri de sintaxă:
una proprie, pentru subclasa total definirilor, i.e. pentru cele de forma ├ , unde : D C este o funcție structurală sau atribut și anume: : D C, totală.
cea uzuală în MRD, pentru subclasa celor generale, de tipul X├ Y, unde X și Y sunt, în general, produse de funcții structurale și/sau atribute, i.e. X,Y P(A F ).
Exemplul 1.45: (sintaxa proprie) Fie din nou bd din exemplul 1.11; evident că, în general, funcția Tata trebuie să admită valori nule (pentru directoarele rădăcină), deci ea nu trebuie să fie total definită. În schimb, trivial, nici unul dintre cele trei atribute ale tipului DIRECTOARE nu trebuie să admită valori nule, deci toate trebuie să fie total (i.e. peste tot) definite.
Deoarece, prin definiție (vezi 1.3.3.1), toți identificatorii de obiect sunt implicit funcții totale, nu este nevoie ca acest lucru să fie explicitat pentru #Dir; definițiile corecte ale Director și Nivel trebuie însă să fie de forma:
Director : DIRECTOARE ASCII(256), total
Nivel : DIRECTOARE NAT(4), total
Exemplul 1.46: (sintaxa uzuală) Fie următorul fragment al schemei bd „Bibliotecar”:
EXEMPLARE={#Exemplar, NrInventar, DataÎmprumut},
PERSOANE={#Persoana, Prenume, Nume, Împrumută},
Împrumutător : EXEMPLARE PERSOANE.
Constrângerea „pentru orice exemplar, valorile acestor două funcții pot fi ori ambele nule, ori ambele nenule (i.e. este interzis ca pentru vreun exemplar una dintre ele să fie definită, iar cealaltă nu)” se formalizează evident cu ajutorul următoarelor două constrângeri de existență:
DataÎmprumut ├ Împrumutător
Împrumutător ├ DataÎmprumut
Evident că nu are rost memorarea în vreo bd nici a aceleiași constrângeri de existență de mai multe ori (i.e. submulțimea CE a constrângerilor este o mulțime), nici a CE triviale de tip X├ X sau X├ .
1.4.1.4 Constrângeri obiect
Constrângerile obiect constituie o extensie naturală a constrângerilor tuplu, de la linii de tabele la obiecte. Ca atare, cum obiectele sunt din punct de vedere matematic elemente ale unor mulțimi, orice formulă logică de ordin întâi referind doar mulțimi din V, atribute din A și funcții structurale din F este o constrângere obiect.
Exemplul 1.47: Fie o bd cu schema DIRECTOARE = {#Dir,Director,Nivel}, Tata : DIRECTOARE DIRECTOARE; constrângerea obiect „dacă un director are tată, atunci nivelul acestuia (de adâncime, în arborele de directoare) trebuie să fie cu 1 mai mic decât al său” poate fi formalizată cu ajutorul predicatului: (xDIRECTOARE) (yDIRECTOARE)(y=Tata(x))(NivelTata(x)=Nivel(x) – 1)
Evident că puterea deosebită a logicii de ordin întâi poate conduce, teoretic, la formularea unei mulțimi de constrângeri obiect incoerentă (i.e. pentru care să nu existe nici un conținut valid al bd respective) sau care să inducă anomalii de actualizare; chiar și constrângerile de domeniu, pot conduce la situații limită, în care doar conținutul vid să fie consistent.
În practică însă, în primul rând, proiectanții bd au misiunea de a modela exact domeniile de interes; în prezența vreuneia din situațiile de mai sus, ei pot decide dacă este vorba de vreo eroare de modelare, sau dacă însuși domeniul de interes modelat este de vină. Primul caz, desigur, poate fi rezolvat de proiectant singur; în cel de-al doilea, evident, trebuie încunoștințați responsabilii domeniului respectiv (mergând, dacă este cazul, până la Legiuitor!) pentru relaxarea constrângerilor în cauză.
În al doilea rând, implementarea MMED poate restrânge drastic subclasa de propoziții logice acceptate drept constrângeri obiect, astfel încât asemenea riscuri să fie aproape eliminate (majoritatea SGBD operaționale fac acest lucru). Ca atare, pentru a evita nedecidabilitatea, orice constrângere obiect trebuie exprimată sub forma unei clauze Horn.
Subclasa constrângerilor obiect fiind o mulțime, ea nu admite duplicate (i.e. nu ar avea nici un rost memorarea de mai multe ori în vreo bd a unei aceleiași constrângeri). De notat însă că această constrângere este mult mai ușor de implementat pur sintactic, decât și semantic, deoarece echivalența semantică a două propoziții din logica de ordin întâi (fie ele doar de tip clauze Horn) necesită recursul la un demonstrator logic de teoreme sofisticat, scump și, cel mai adesea, nu suficient de performant.
1.4.2 Constrângeri asociate mulțimilor
1.4.2.1 Incluziunea
AtâtV cât și sunt poset-uri (mulțimi parțial ordonate de incluziuni). Ar putea deci fi nevoie, în schema unei bd, de o constrângere de incluziune între mulțimi de valori.
Exemplul 1.48: SPECTRU CULORI.
Mult mai interesante sunt însă incluziunile între mulțimi de obiecte care modelează ierarhii (laticeale), de tip generalizare (IS-A), ale mulțimilor de obiecte și care permit în MMED moștenirea atributelor și cheilor.
Exemplul 1.49: CADRE_DIDACTICE ANGAJAȚI PERSOANE sau STUDENȚI PERSOANE.
Constrângerile de tip incluziune sunt implementate de MMED tot cu ajutorul DIN din modelul relațional.
Din punctul de vedere al incluziunii (dar și egalității, i.e. dublei incluziuni a) mulțimilor, este evident că, pentru a evita anomaliile de actualizare, este suficientă relaxarea definiției constrângerilor primitive prin includerea printre acestea și a dependențelor de incluziune.
De notat că dacă partea stângă a unei asemenea incluziuni este necunoscută în momentul asertării constrângerii respective, atunci aceasta servește și de definiție a noii mulțimi corespunzătoare.
Exemplul 1.50 : În schema:
CURSURI
#Curs NAT(8)
Curs CHAR(256), total
PRECONDIȚII CURSURI
COND_ÎNSCRIERE = (CURSURI, PRECONDIȚII)
mulțimea de obiecte PRECONDIȚII este și automat definită de MMED în momentul întâlnirii constrângerii PRECONDIȚII CURSURI.
Evident că, exact ca și în cazul tuturor celorlalte tipuri de constrângeri, subclasa dependențelor de incluziune fiind o mulțime nu admite nici ea duplicate (i.e. nu are rost memorarea în vreo bd de mai multe ori a unei aceleiași incluziuni). Mai mult însă, clasa dependențelor de incluziune trebuie să mai satisfacă și următoarele (meta)constrângeri:
Nu are rost (deci trebuie interzisă) memorarea incluziunilor triviale de tip M, oricare ar fi mulțimea M, deoarece ele sunt trivial deductibile.
Idem a celor duale (i.e. de tip M , care nu afirmă decât că M trebuie să fie mereu vidă), deoarece, trivial, în bd nu sunt interesante mulțimile ce trebuie mereu să fie vide (evident, cu excepția mulțimii vide însăși), fie ele de obiecte sau de valori.
Idem a celor de tip M M și ele fiind trivial deductibile (de notat că aceasta înseamnă, aparent paradoxal, că în bd incluziunile nu trebuie să fie reflexive!
Idem a celor de tip M N, unde M și N aparțin însă unor subclase de mulțimi diferite, deoarece, evident, (deși netriviale) ele sunt excluse prin definiție în MMED (fiindcăV, E și Æ sunt toate disjuncte între ele două câte două).
Evident, orice mulțime de incluziuni trebuind, prin definiție, să fie tranzitivă, nu are rost nici (deci trebuie interzisă și) memorarea de incluziuni tranzitiv deductibile din cele deja existente (e.g., dacă o mulțime de dependențe de incluziune conține M N și N Q, atunci trebuie interzisă memorarea și a M Q, oricare ar fi mulțimile M, N, Q.
Aparent la fel de paradoxală ca și precedenta (care, în fond, impune în bd non-tranzitivitatea incluziunilor ce sunt matematic, prin definiție, tranzitive) este și metaconstrângerea ce impune oricărei mulțimi de incluziuni să fie aciclică (în caz contrar, desigur, procesul de impunere al unor asemenea incluziuni ar putea bucla la infinit).
În fine, o ultimă asemenea metaconstrângere este naturală: cum incluziunile și disjuncțiile (acelorași perechi de mulțimi) se exclud reciproc, orice incluziune M N interzice coexistența unei disjuncții omonime M N = (ca și a simetricei sale N M = ), oricare ar fi mulțimile M, N.
1.4.2.2 Egalitatea
Pe lângă incluziune, chiar dacă nu la fel de frecvent, este nevoie adesea în modelarea datelor de a impune egalitatea (i.e. dubla incluziune) între mulțimi. Egalitatea este folosită în special pentru a defini asociații, sinonime și partiții în schema bd, dar nu numai.
Exemplul 1.51: Egalitatea COND_ÎNSCRIERE= (CURSURI, PRECONDIȚII) definește asociația binară COND_ÎNSCRIERE (în același spirit în care sunt definite relațiile matematice: de exemplu, R=(M1, M2, GR)).
Exemplul 1.52: În schimb, pentru a putea defini tipul de asociații MIȘCĂRI_ PIESE (respectând condiția ca numele suporților să fie unici), următoarele două constrângeri definesc, de fapt, două sinonime pentru tipul de entități MAGAZII:
MAGAZII
#Mag NAT(4)
Mag CHAR(64), total
MAGAZII_SURSĂ = MAGAZII
MAGAZII_DESTINAȚIE = MAGAZII
PIESE
#Piesa NAT(16)
DenPiesa CHAR(32), total
DOCUMENTE
#Doc NAT(16)
TipDoc CHAR(2), total
DataDoc DATE(1.1.2002, azi()), total
MIȘCĂRI_PIESE = (MAGAZII_SURSĂ, MAGAZII_DESTINAȚIE, PIESE, DOCUMENTE).
Exemplul 1.53: În fine, în schema următoare (în care, în momentul asertării constrângerii de egalitate, ambele mulțimi implicate sunt deja definite), egalitatea este o pură constrângere:
AEROPORTURI
#A NAT(16)
CodAeroport CHAR(8), total
Aeroport CHAR(64), total
AEROP_SURSĂ AEROPORTURI
AEROP_DESTINAȚIE AEROPORTURI
AEROP_SURSĂ = AEROP_DESTINAȚIE
De notat că, așa cum este de așteptat, MMED nu memorează constrângerile de egalitatea mulțimilor ca atare, ci folosește pentru aceasta dublele incluziuni corespunzătoare.
1.4.2.3 Reuniunea
Câteodată este nevoie de a impune și constrângeri conținând reuniuni între mulțimi.
Exemplul 1.54: PERSOANE = STUDENȚI ANGAJAȚI impune excluderea oricărui alt tip de persoane într-o bd universitară, cu excepția studenților și angajaților.
1.4.2.4 Disjuncția
Pe lângă incluziuni, MMED include printre constrângerile primitive relative la mulțimi și disjuncția acestora.
Exemplul 1.55: Exemple de disjuncții apar chiar în definiția MMED, precum V = , E Æ = sau F Æ = , în timp ce altele pot fi deduse din ea, precum F A = (trivială, din definiția celor două clase de funcții și fiindcă V = ).
Evident că și modelarea uzuală în bd are nevoie de acest tip de constrângeri; exemplu: SENATORI DEPUTAȚI = .
Similar cazului incluziunilor, pe lângă faptul că și subclasa disjuncțiilor este o mulțime (care deci nu admite duplicate) ea trebuie să se mai supună unui set de metaconstrângeri similare și anume:
Nu are rost (deci trebuie interzisă) memorarea disjuncțiilor triviale de tip M = sau M = , oricare ar fi mulțimea M, deoarece ele sunt trivial deductibile.
Idem pentru disjuncțiile imposibile de tip M M = , oricare ar fi mulțimea M, deoarece, trivial, M M = M (de notat că aceasta înseamnă că în bd disjuncțiile nu trebuie să fie vreodată reflexive, ceea ce, de această dată este consistent cu definiția lor matematică).
Idem a celor simetrice (i.e. de tip N M = , atunci când este deja memorată în bd simetrica sa M N = , oricare ar fi mulțimile M și N), deoarece acestea sunt trivial deductibile (de notat că aceasta înseamnă, aparent paradoxal, că în bd disjuncțiile nu trebuie să fie simetrice).
Idem a celor de tip M N = , unde M și N aparțin însă unor subclase de mulțimi diferite, deoarece, evident, (deși netriviale matematic) ele sunt triviale prin definiție în MMED (fiindcăV, E și Æ sunt toate disjuncte între ele două câte două).
În fine, o ultimă asemenea metaconstrângere (duală ultimei de la incluziuni) este naturală: cum incluziunile și disjuncțiile (acelorași perechi de mulțimi) se exclud reciproc, orice disjuncție M N = interzice coexistența incluziunilor simetrice „omonime” M N și M N, oricare ar fi mulțimile M, N.
1.4.2.5 Partiționarea
Deși nu sunt constrângeri primitive (ele putând fi trivial înlocuite cu conjuncții de incluziuni, reuniune și disjuncții), MMED oferă, pentru comoditate și eleganță sporită în proiectare și o subclasă de constrângeri de tip partiționarea mulțimilor. Evident că cel mai uzual exemplu de partiționare îl oferă clasele de echivalență.
Exemplul 1.56: Conform definiției, în MMED are evident loc constrângerea de partiționare =E Æ.. Mai mult, pentru o modelare elegantă unitară a funcțiilor (indiferent că sunt atribute sau funcții structurale) și constrângerilor, este convenabilă adăugarea la model a unei „supermulțimi” S partiționată în trei blocuri: S = V {} (de notat, în legătură cu al treilea bloc, faptul evident că, pe de-o parte, este neapărată nevoie în modelare de mulțimea vidă, dar pe de alta, că nu interesează mulțimi vide nici de obiecte, nici de valori). Această partiționare corespunde desigur claselor de echivalență induse de valorile atributului TipM : S ’V’,’E’,‘A’,‘N’,’C’, total.
Exemplul 1.57: O altă partiționare sistem evidentă în MMED este cea a mulțimii constrângerilor:
CONSTRÂNGERI = MINIMAL_INJ EGALITĂȚI_ FUNCȚII CONSTR_EXISTENȚĂ INCLUZIUNI DISJUNCȚII SIST_REPREZ CONSTR_OBIECT CONSTR_DOMENIU.
Exemplul 1.58 : Desigur că există și subuniversuri de interes utilizator care pot beneficia în modelare de acest tip de constrângeri, precum, de exemplu următorul:
CETĂȚENI = VOTANȚI NEVOTANȚI
VOTANȚI = CANDIDAȚI NECANDIDAȚI
CANDIDAȚI = ALEȘI NEALEȘI
ALEȘI = PARLAMENTARI ALEȘI_LOCALI
PARLAMENTARI = SENATORI DEPUTAȚI
PARLAMENTARI = GRUPURI_P INDEPENDENȚI
FSN = PSD PRM PD
GRUPURI_P = FSN UDMR PNL MINORITAȚI
1.4.3 Constrângeri asociate funcțiilor
Fie că este vorba de funcții structurale, de atribute sau de produse ori compuneri ale acestora (mixte sau nu), adesea, inclusiv în cazuri de modelare extrem de simple, egalitatea funcțiilor este foarte frecvent întâlnită. Chiar dacă mult mai rar în asemenea exemple, vom vedea totuși că idempotența și surjectivitatea sunt la rândul prețioase pentru modelarea cu acuratețe a datelor.
1.4.3.1 Egalitatea
Precum în cazul general al oricărui fel de egalitate, egalitatea funcțiilor poate fi folosită în MMED pentru a defini sinonime pentru funcții. Revenind la exemplul 1.10, acesta este cazul pentru declarația: Județ = #Jud Apart_Jud.
Mult mai importantă însă este egalitatea funcțiilor ce impune comutativitatea diagramelor de funcții.
Exemplul 1.59: Revenind la exemplul 1.10, trebuie remarcat în legătură cu modelarea sa relațională de către Ullman, că este obligatorie adăugarea la schema bd a constrângerii de comutativitate a următoarei diagrame de funcții (unde k1 este funcționalitatea corespunzătoare cheii structurale Localități, Adrese, iar prLOCALITĂȚI este proiecția CODIF_POȘTA pe LOCALITĂȚI):
ADRESE LOCALITĂȚI
k1 prLOCALITĂȚI
Loc_Codif
CODURI_POȘTA LOCALITĂȚI
Formalizarea acestei constrângeri în MMED este, evident, următoarea: Loc_Codif k1 = prLOCALITĂȚI.
Similar, ar mai trebui adăugată schemei și constrângerea de același tip Localiz_Adresa k2 = prLOCALITĂȚi, unde k2 este funcționalitatea corespunzătoare cheii structurale LOCALITĂȚI, CODURI_POȘTA.
De notat că, prin „tranzitivitate”, aceste două constrângeri garantează și pe următoarea (unde prADRESE este proiecția CODIF_POȘTA pe ADRESE): Loc_Codif k1 = Localiz_ Adresa prADRESE
O modelare neatentă ar putea totuși s-o includă în schemă, deși ea este implicată; de remarcat că, deși echivalentă, chiar modelarea incluzând această ultimă constrângere în locul oricăreia dintre primele două ar fi o soluție mai ineficientă și mai puțin elegantă, căci astfel ar trebui calculată o compunere de funcții în plus!
MMED distinge între cele două semantici posibile ale unei egalități de funcții astfel: dacă toate funcțiile implicate sunt deja cunoscute sistemului, atunci este vorba de o constrângere de tip comutativitate de diagrame de funcții; dacă una dintre funcții este necunoscută, atunci MMED consideră egalitatea ca fiind definiția acestei funcții (astfel calculate).
Formalizarea relațională a conceptului de anomalie de actualizare se limitează la inserție (de tupli compatibili) și ștergere, deoarece modificarea unui tuplu într-o relație poate fi asimilată cu succesiunea ștergere și apoi inserție. Din acest punct „sintactic” de vedere, constrângerile de tip comutativitate de diagrame de funcții nu pot conduce la anomalii de actualizare.
Semantic însă, evident că sunt posibile anomalii; referindu-ne din nou la exemplul din figurile 1.6, 1.7 și 1.8, modificarea valorii Loc_Codif(2), de pildă, din valoarea 1 în orice altă valoare ar viola constrângerea: Loc_Codif k1 = prLOCALITATI (unde, în terminologia mai precisă a figurilor sus-menționate, k1= CODURI_POȘTA, iar prLOCALITATI = LOCALITĂȚI).
Și constrângerile de tip egalitate de funcții sunt însă considerate primitive în MMED.
1.4.3.2 Idempotența
Am menționat deja (exemplul 1.4) că funcția SINONIMIE este idempotentă. Evident că idempotența este un caz particular al egalității de (compuneri de) funcții. Fiind însă extrem de importantă în modelarea sistemelor de reprezentanți, MMED oferă sintaxa specializată: idemp .
Exemplul 1.60: Fie o bd având schema {PIESE, Echivalența : PIESE PIESE} și constrângerea suplimentară naturală „orice piesă aleasă pentru a echivala alte piese își este propriul echivalent”.
Evident că cea mai elegantă modelare a acestei constrângeri o constituie: idemp Echivalența.
Nefiind fundamentale, așa cum este de așteptat, MMED nu memorează constrângerile de tip idempotențe ca atare, ci folosește pentru aceasta compunerea și egalitatea funcțiilor.
1.4.3.3 Surjectivitatea
Duală injectivității și total definirii, surjectivitatea are, în sine, suficientă importanță pentru a o scoate din anonimatul constrângerilor obiect.
Exemplul 1.61: Revenind la bd din exemplul 1.10, pentru a ne asigura că este întotdeauna memorat codul poștal al oricărei localități, este obligatorie surjectivitatea funcției structurale Loc_Codif : CODURI_POȘTA LOCALITĂȚI.
În plus, surjectivitățile canonice au o importanță covârșitoare în modelarea sistemelor de reprezentanți.
Sintaxa „surj “ este folosită în MMED pentru a include în schema bd constrângerea „ este surjectivă”.
Evident că, în accepțiune relațională, includerea acestui tip de constrângere în schema unei bd poate conduce la anomalii de actualizare. Referindu-ne la exemplul din Figurile 1.6, 1.7 și 1.8, ștergerea din tabela CODURI_POȘTA a oricărui tuplu cu excepția celui de-al doilea sau al treilea ar viola constrângerea „surj Loc_Codif”.
În accepțiunea MMED însă, constrângerile primitive includ și surjectivitățile.
Acest tip de constrângere trebuie însă mereu inclus în schema unei bd după o analiză foarte atentă, deoarece, în caz contrar, impunerea unei surjectivități poate conduce, în cel mai bun caz, la necesitatea proiectării unor interogări speciale pentru introducerea și actualizarea datelor, care trebuie să forțeze o anumită ordine de operare, iar în cel mai rău caz, chiar la imposibilitatea actualizării datelor implicate.
Exemplul 1.62: Reconsiderând exemplul 1.20, evident că toate cele trei funcții structurale trebuie să fie surjective (deoarece: nu există șef fără subordonat, în cel mai rău caz șeful fiindu-și unicul subordonat; nu există departament fără angajați și nici fără șef).
Să presupunem bd vidă și conținând numai una din aceste constrângeri, de exemplu surj LocMuncă. Evident că dacă am încerca să introducem întâi departamentele și apoi angajații, această constrângere ne-ar împiedica să procedăm în această ordine încă de la primul departament introdus, obligându-ne să introducem simultan cel puțin un angajat cu locul de muncă în acel departament, plus această informație; chiar dacă am încerca în schimb să introducem întâi angajații, tot n-am putea însă introduce departamentele decât simultan cu specificarea locului de muncă a cel puțin unui angajat din acel departament (deci și ordinea de introducere a angajaților ar fi obligatoriu de sincronizat cu cea a departamentelor).
Mai rău, dacă toate cele trei surjectivități ar fi impuse de la început se poate demonstra imediat că bd ar rămâne veșnic vidă, fiindcă interacțiunea dintre ele conduce la un așa numit „blocaj fatal”.
În general deci, surjectivitatea este genul de constrângere ce trebuie impusă mai degrabă bd „statice” (de tip geologic, geografic, astronomic etc.), după terminarea completării lor cu date, pentru a preîntâmpina apoi ștergerea sau modificarea eronată a acestora și nu la început, înaintea populării bd cu toate datele implicate în surjectivități.
1.4.3.4 Sisteme de reprezentanți
Nevoia de a utiliza sisteme de reprezentanți în proiectarea bd apare frecvent. De exemplu, „piesele de tip t sunt echivalente cu cele de tip s, putând deci fi substituite una alteia în subansamblele ce necesită asemenea piese”; „facilitățile de tip f sunt echivalente cu cele de tip g, putând fi deci substituite una alteia în procesul de instruire”; „sinonimele sunt echivalente între ele, putând fi deci interșanjabil folosite pentru numirea conceptelor” etc.
Exemplul 1.63 : Reconsiderând exemplul 1.20, este evident că ȘEFI este un sistem de reprezentanți pentru ANGAJAȚI, iar Șef este surjecția canonică asociată.
Aparent, modelarea sistemelor de reprezentanți se poate face în MMED foarte simplu, incluzând în schema bd mulțimile de entități M și M~, constrângerea M~ M și funcția structurală . Dar lucrurile se complică întrucâtva atunci când realizăm că graful nu poate fi aciclic! Din fericire, următoarea propoziție simplifică mult modelarea sistemelor de reprezentanți:
Propoziția 1.41: (ciclicitatea sistemelor de reprezentanți) Graful oricărei surjecții canonice asociate unui sistem de reprezentanți este ciclic.
Demonstrație:
Fie idemp și să presupunem prin absurd că graful este aciclic; din definiție, xM~ ( (x)) = (x), deci există cel puțin câte o buclă per reprezentant în graful , ceea ce înseamnă că presupunerea făcută este într-adevăr absurd. Q.e.d.
Ca atare, pentru modelarea unui sistem de reprezentanți pentru o mulțime de obiecte oarecare M, MMED oferă sintaxa prescurtată de tip „SRM = reprez M”, cu înțelesul că se adaugă la schema bd următoarele:
un nou tip de obiecte (mai exact, entități) cu numele SRM
o nouă funcție structurală: SRM : M SRM
trei constrângeri: SRM M, surj SRM și idemp SRM.
Exemplul 1.64: Revenind din nou la exemplul 1.20, este acum evident de ce Echivalența trebuie să fie idempotentă.
1.4.4 Constrângeri asupra grafurilor de relații binare
Evident că subsecțiunile anterioare oferă deja suficiente motive pentru îndreptățirea includerii printre constrângerile primitive ale MMED tuturor acestor subclase. Înainte de a analiza și altele, este însă nevoie să începem această subsecțiune prin a preciza exact ce înțelegem prin „grafuri de relații binare”. Așa cum ne vor demonstra exemplele din subsecțiunile următoare, este nevoie să numim astfel în mod generic de fapt trei tipuri distincte de concepte matematice și anume:
grafuri propriu-zise de asociații binare (i.e. nefuncționale)
grafuri de funcții structurale (înțelese ca mulțimi de perechi de forma (x, f (x)))
produse binare de funcții structurale (înțelese ca mulțimi de perechi de forma (f (x), g(x))).
Desigur că, în fiecare din ultimele două subcazuri, pentru a putea vorbi despre oricare din aceste cinci proprietăți ale relațiilor binare, este necesară îndeplinirea câte unei condiții suplimentare (de omogenitate) și anume:
în subcazul doi, Im(f ) dom(f ) (imaginea f trebuie să fie o submulțime a domeniului ei)
în subcazul trei, codom(f ) = codom(g) (codomeniile celor două funcții trebuie să fie aceleași).
Ca atare, prin abuz de notație, vom vorbi, de exemplu, despre aciclicitatea unei funcții, dar și a unui produs de două funcții, exact ca despre cea a unei relații binare și vom scrie, corespunzător: aciclic A=(B,C), aciclic f : B C, respectiv aciclic fg, unde f, g : B C.
1.4.4.1 Reflexivitatea
Privite drept constrângeri de bd, nici incluziunile, nici disjuncțiile nu trebuie să fie reflexive. Chiar dacă întâlnit mai rar în modelare, acest tip de constrângeri este totuși indispensabil (mai ales sub formă negată) modelării corecte a unei clase de subuniversuri de interes uzuale.
Sintaxa acestui tip de constrângeri este de tip „reflexiv x”.
Exemplul 1.65: Fie orice competiție sportivă cu doi adversari (e.g. scrimă, tenis, fotbal etc.). Evident că niciodată, nimeni (fie el sportiv sau echipă) nu va juca împotriva lui însuși, deci orice asemenea graf nu trebuie să fie reflexiv.
Exemplu 1.66: Fie o bd pentru un campionat (local, național sau internațional) de fotbal și următorul extras al schemei sale: GAZDE ECHIPE, EDIȚII, MECIURI = (GAZDE, ECHIPE, EDIȚII), Scor : MECIURI NAT(2).
Pentru o modelare corectă, această schemă trebuie în mod trivial să includă și constrângerea:
(reflexiv prGAZDEMECIURI prECHIPEMECIURI).
Ca atare, MMED include și reflexivitatea printre constrângerile sale primitive.
1.4.4.2 Simetria
Privite drept constrângeri de bd, disjuncțiile nu trebuie să fie simetrice. Chiar dacă întâlnit rar, și acest tip de constrângeri este totuși indispensabil unei modelări corecte a unei întregi clase de subuniversuri de interes uzuale.
Sintaxa acestui tip de constrângeri este de tip „simetric x”.
Exemplul 1.67a: Revenind la exemplul anterior, este evident, datorită algoritmului de tip tur-retur, că în orice ediție, orice pereche posibilă de echipe trebuie să joace două meciuri, alternând între ei postura de gazdă, deci orice asemenea subgraf trebuie să fie simetric. Ca atare, pentru o modelare corectă, această schemă trebuie în mod trivial să includă și constrângerea: xIm(prEDIȚIIMECIURI)
(simetric prGAZDEMECIURI(x)prECHIPEMECIURI(x))
În consecință, MMED include și simetria printre constrângerile sale primitive.
1.4.4.3 Antisimetria
Chiar dacă constrângerile de antisimetrie sunt mult mai rar întâlnite în modelarea datelor, totuși și ele trebuie incluse printre constrângerile primitive ale MMED.
Sintaxa acestui tip de constrângeri este de tip „antisimetric x”.
Exemplul 1.67b: Graful funcției Șef trebuie să fie antisimetric: dacă un angajat este șeful altuia, iar acela este șeful său, atunci nu poate fi vorba decât de el însuși, adică: (x,y ANGAJAȚI)(x=Șef(y) y=Șef(x) x=y). Ca atare, pentru o modelare corectă, orice schemă ce include această funcție trebuie în mod trivial să includă și constrângerea: antisimetric Șef.
1.4.4.4 Tranzitivitatea
Privite drept constrângeri de bd, incluziunile nu trebuie să fie tranzitive. Chiar dacă nu foarte des întâlnită în modelare, acest tip de constrângeri este totuși indispensabil (mai ales sub formă negată) modelării corecte a unor subuniversuri de interes uzuale.
Sintaxa acestui tip de constrângeri este de tip „tranzitiv x”.
Exemplul 1.68: Revenind la exemplul 1.25, este evident, datorită algoritmului de tip „fiecare-cu-fiecare și în tur și în retur”, că în orice ediție, dacă o pereche oarecare de echipe (e,f) joacă între ele, iar f joacă și cu o altă echipa g, atunci și f trebuie să joace cu g, deci orice asemenea subgraf trebuie să fie tranzitiv. Ca atare, pentru o modelare corectă, această schemă trebuie în mod trivial să includă și constrângerea:
(xIm(prEDIȚIIMECIURI))(tranzitiv prGAZDEMECIURI(x) prECHIPEMECIURI(x)).
Ca atare, MMED include și tranzitivitatea printre constrângerile sale primitive.
1.4.4.5 Aciclicitatea
Este foarte adesea nevoie de impunerea aciclicității grafurilor de relații binare omogene, pentru a evita ori buclarea la infinit, ori imposibilitatea de a intra într-o buclă.
Aciclicitățile grafurilor se pot formaliza matematic tot cu ajutorul formulelor calculului predicativ de ordin întâi. Notația însă ar fi mult mai greoaie decât prescurtarea oferită de MMED și care este de tip „aciclic x”.
Exemplul 1.69: Modelării relaționale propuse de Ullman pentru exemplul 1.3 îi lipsește pentru a fi corectă tocmai constrângerea ca graful asociației COND_ÎNSCRIERE = (CURSURI, PRECONDIȚII) să fie aciclic: în absența unei asemenea constrângeri, conținutul acestei relații ar putea include simultan tuplii (c,c') și (c',c), ceea ce ar împiedica orice student să se înscrie vreodată la cursurile c sau c'!
Problema aciclicității grafurilor este, desigur, mult mai complicată decât în contraexemplul de mai sus, deoarece trebuie interzise ciclurile de orice lungime și nu doar cele de lungime 2.
Exemplul 1.70 : COND_ÎNSCRIERE nu ar trebui să poată memora simultan nici tuplii (c,c'), (c',c''), (c'',c), căci și aceștia formează un ciclu (de lungime 3) și așa mai departe. Ca atare, modelarea corectă în MMED a acestui exemplu include și constrângerea aciclic COND_ÎNSCRIERE.
Evident că și ignorarea acestui tip de constrângeri conduce la anomalii de actualizare: de exemplu, inserția unui tuplu compatibil în accepțiune relațională cu un conținut valid al COND_ÎNSCRIERE care închide vreo buclă în graful acestei asociații, conduce la o anomalie de inserție.
În consecință, MMED include și aciclicitatea printre constrângerile primitive. De remarcat că aciclicitatea este o generalizare recursivă a non-reflexivității.
1.4.5 Teoria buclelor închise
Privite drept grafuri, DEA pot prezenta bucle închise. Câteodată, acestea sunt complet neinteresante. De cele mai multe ori însă, buclele închise constituie adevărate „capcane” în modelarea datelor, căci ori „ascund” constrângeri, ori dezvăluie necesitatea simplificării modelului prin renunțarea la una dintre funcțiile care închid bucla. Concluzia acestei subsecțiuni trebuie să fie aceea că orice buclă închisă trebuie riguros analizată, trebuie desfăcută dacă acest lucru este cu putință, iar dacă nu, completată cu toate constrângerile necesare.
1.4.5.1 Bucle simple
Aparent, pentru a modela structura de directoare a unei partiții, este suficientă definirea unei submulțimi DIRECTOARE FIȘIERE și a unei funcții Tata, conform următoarei DEA:
DIRECTOARE Tata
După cum știm însă, există două constrângeri adiționale: „nici un director nu-și poate fi strămoș” și “directorul rădăcină nu are tată”.
Prima dintre ele se poate modela simplu, folosind aciclicitatea; pentru a doua, este necesară o constrângere obiect. Ca atare, modelul corect este următorul:
DIRECTOARE FIȘIERE
Submulțimea fișierelor de tip director (ale partiției curente).
Tata : DIRECTOARE DIRECTOARE, aciclic
Nici un director nu-și poate fi strămoș (ierarhia directoarelor este arborescentă).
PropDirRădăcină : (xDIRECTOARE)(Tata(x)=NULL)
Există un unic director (rădăcina arborelui) care nu are tată.
De remarcat că, în prezența partițiilor, constrângerea PropDirRădăcină poate fi înlocuită elegant folosind imagini de funcții:
PARTIȚII
Mulțimea partițiilor de interes.
DIRECTOARE FIȘIERE
Submulțimea fișierelor de tip director.
Rădăcini : PARTIȚII DIRECTOARE, total
Fiecărei partiții îi corespunde un unic director rădăcină.
Tata : DIRECTOARE Im(Rădăcini) DIRECTOARE, total, aciclic
Nici un director nu-și poate fi strămoș (ierarhia directoarelor este arborescentă); directoarele rădăcină nu au tată.
Desigur că acest exemplu nu constituie vreo excepție, căci sunt multe cazuri de asemenea funcții care trebuie să fie aciclice, precum, de exemplu:
Șef : ANGAJAT ANGAJAT, aciclic
Strămoș : PERSOANE PERSOANE, aciclic
În mod trivial, trebuie analizate cu aceeași atenție și buclele simple închise definite de asociații: exemplul 1.70 ne-a arătat deja că trebuie să adăugăm constrângerea aciclic COND_ÎNSCRIERE următoarei DEA:
COND_ÎNSCRIERE
PRECONDIȚII CURSURI
Modelul corect pentru ea este deci următorul:
PRECONDIȚII CURSURI
Submulțimea cursurilor a căror absolvire condiționează înscrierea la alte cursuri.
COND_ÎNSCRIERE = (PRECONDIȚII, CURSURI) aciclic
Mulțimea condițiilor de înscriere la cursuri.
De remarcat că, în mod evident, nici o buclă simplă nu ar putea fi eliminată fără a se pierde informații.
1.4.5.2 Diagrame comutative de funcții
Diagramele comutative de funcții pot fi trivial modelate cu ajutorul constrângerilor de tip egalități de funcții. De exemplu, pentru următoarea DEA (modelând o mulțime de baze de date locale, nedistribuite și nereplicate) există evident constrângerea „orice fișier memorând o parte a unei bd trebuie să aparțină unui director de pe calculatorul găzduind server-ul de bd ce gestionează acea bd”:
Director
FIȘIERE DIRECTOARE Calculator
Bd CALCULATOARE
BDATE SERVERE Gazdă
Server
Schema MMED corespunzătoare trebuie deci să includă și constrângerea ComutFișiere: Gazdă Server Bd = Calculator Director, unde:
Director : FIȘIERE DIRECTOARE, total
Calculator : DIRECTOARE CALCULATOARE, total
Bd : FIȘIERE BDATE
Server : BDATE SERVERE, total
Gazdă : SERVERE CALCULATOARE, total
De remarcat că această buclă nu poate fi deschisă fără a pierde informații, căci nici una dintre funcțiile de mai sus nu este calculabilă din celelalte (nici una nu admite inversă). Acest lucru este natural, deoarece partea stângă a egalității de funcții modelează metacataloagele serverelor de bd, în timp ce partea dreaptă modelează structura directoarelor sistemelor de operare.
Desigur că, în general, implementarea unei astfel de constrângeri este costisitoare, atât în termenii efortului de programare necesar, cât și în cei ai performanței aplicației de bd corespunzătoare. Ca atare, atunci când desființarea buclei este posibilă, acest lucru trebuie obligatoriu făcut, mai ales că și modelul echivalent rezultat este mai simplu.
De foarte multe ori, din egalitatea de funcții aferentă comutativității se poate calcula una dintre ele în funcție de celelalte; în asemenea cazuri, această funcție trebuie eliminată din model (sau păstrată doar ca funcție calculată), iar egalitatea aferentă de funcții se va transforma astfel dintr-o constrângere într-o interogare. De exemplu, următoarea DEA prezintă un asemenea caz tipic:
CLIENȚI
LocCli ȚaraCli
LOCALITĂȚI ȚĂRI
Țara
CLIENȚI CLIENȚI
LocCli ȚaraCli LocCli *ȚaraCli
Țara Țara
LOCALITĂȚI ȚĂRI LOCALITĂȚI ȚĂRI
LocCli: CLIENȚI LOCALITĂȚI LocCli: CLIENȚI LOCALITĂȚI
Țara : LOCALITĂȚI ȚĂRI, total Țara : LOCALITĂȚI ȚĂRI, total
ȚaraCli : CLIENȚI ȚĂRI *ȚaraCli = Țara LocCli
ȚaraCli = Țara LocCli
De remarcat că egalitatea de funcții este o constrângere în modelul din stânga (formalizând: „orice client este localizat în țara căreia îi aparține localitatea în care el este localizat”), pentru că topate funcțiile implicate sunt definite ca fundamentale, în timp ce în partea dreaptă ea constituie definiția funcției calculate *ȚaraCli. Așa cum este întotdeauna de așteptat în asemenea cazuri, soluția alternativă de modelare este mai bună nu doar la nivelurile relațional și fizic (atât în termenii spațiului de memorare, cât și în cei ai timpilor de execuție), ci și la nivel conceptual, deoarece este mai naturală și deci elegantă.
1.4.5.3 Comutativități locale
Chiar dacă o diagramă închisă nu comută, ea nu trebuie considerată ca fiind neinteresantă fără o analiză mai aprofundată. Primul lucru ce mai trebuie investigat în acest caz este eventuala comutare prin intermediul unei funcții unitate. Figura următoare prezintă o asemenea diagramă: deși necomutativă, ea are evident nevoie de o constrângere care să asigure plauzibilitatea datelor valide și anume “capitala oricărei țări trebuie să fie un oraș din aceea țară”.
ȚĂRI 1ȚĂRI
Capitala Țara
Județ
ORAȘE JUDEȚE
Capitala : ȚĂRI ORAȘE
Județ : ORAȘE JUDEȚE, total
Țara : JUDEȚE ȚĂRI, total
1ȚĂRI : ȚĂRI ȚĂRI, total
C1 : Țara Județ Capitala = 1ȚĂRI
Fig. 12: Exemplu de diagramă local comutativă
În MMED, comutativitățile implicând funcții unitate se zic locale. De remarcat că nu este nevoie de vreo declarație explicită în model pentru aceste funcții (exact ca și în cazul altor funcții standard în matematică precum incluziunile sau proiecțiile Carteziene canonice, imaginile și preimaginile funcțiilor etc.).
Fiind bijective, funcțiile unitate pot fi privite în asemenea cazuri ca închizând comutativ în sens convențional diagrame echivalente, în care bucla lor este desfășurată prin instanțierea separată a domeniului și codomeniului, ca în figura următoare:
ȚĂRI 1ȚĂRI ȚĂRI
Capitala Țara
ORAȘE Județ JUDEȚE
Fig. 13: Transformarea într-o comutativitate convențională
Evident, spre deosebire de cazul comutativităților standard, nu există pentru cele locale nici o soluție alternativă de modelare (căci funcțiile unitate nu pot fi ignorate și nici nu poartă vreo semantică). Trivial, comutativitățile locale trebuie luate în considerare și în cazul celor convenționale, deoarece se poate întâmpla ca o diagramă să comute atât în sens clasic, cât și local.
1.4.5.4 Comutativități generalizate
În 1.6.2.2, sunt prezentate exemple de diagrame comutative implicând nu doar funcții, dar și asociații. Figura 15 prezintă o subdiagramă de acest tip.
De remarcat cheile structurale ale celor două asociații, ROUTE_CONFIGS și FLIGHTS: cum rutele aeriene nu pot închide bucle (re-aterizând pe un același aeroport), urmează că ROUTES AIRPORTS este cheie; cum, în mod trivial, pe orice rută,orice escală se face de către orice avion pe un unic aeroport, rezultă că și ROUTES POSITIONS este cheie. Similar, ROUTES TAKEOFFTIMES este cheie în FLIGHTS, deoarece, evident, pentru orice rută, în orice moment, există un unic avion ce o deservește; și cum un avion nu poate zbura la un moment dat decât pe o unică rută, rezultă în mod trivial că și PLANES TAKEOFFTIMES este cheie.
De remarcat și funcția structurală Flight, definită pe asociația FLIGHTS, care modelează o ierarhie mixtă de tipuri de obiecte.
Constrângerea C1 formalizează comutativitatea sub-diagramei din Fig. 15 (“orice zbor trebuie asigurat cu un tip de avion ce are toate tipurile de locuri rezervate de biletele emise pentru acel zbor”; i.e., de exemplu, o instanță a bd în care un bilet pentru locul nr. 21 la clasa ‘Business’ a fost eliberat pentru un avion care are doar 20 de locuri la aceasta clasă sau nu are de loc asemenea locuri ar trebui evident respinsă ca invalidă). Desigur că singurul lucru ce diferă în acest exemplu față de cele din subsecțiunile precedente este acela că este în plus implicată și o proiecție Carteziană canonică (și anume prPLANES(FLIGHTS)), ceea ce ar face ca ruperea buclei să fie și mai costisitoare.
Constrângerea C2 este impusă de analiza sub-diagramei închise din Fig. 16: „pe orice bilet, aeroporturile de îmbarcare și destinație trebuie să aparțină rutei pentru care s-a cumpărat / rezervat biletul și, mai mult, poziția în rută a celui de îmbarcare trebuie să fie strict mai mică decât a celui de destinație”.
De notat că această constrângere nu este nici ea de tip convențional, ci este o comutativitate generalizată: în asemenea comutativități, cel puțin un graf implicat este al unei asociații (deci relații nonfuncționale). Trivial, asemenea bucle închise nu pot fi niciodată rupte, deci singura soluție de modelare cu putință este adăugarea constrângerii respective la schema bd.
Comutativitățile locale trebuie evident verificate și în cazul celor generalizate.
ROUTE_CONFIGS = (ROUTES, POSITIONS, AIRPORTS; {ROUTES, POSITIONS},
{ROUTES, AIRPORTS})
FLIGHTS = (ROUTES, PLANES, TAKEOFFTIMES;
{ROUTES, TAKEOFFTIMES}, {PLANES, TAKEOFFTIMES})
Source : TICKETS AIRPORTS, total
Destination : TICKETS AIRPORTS, total
Seat : TICKETS SEATS, total
PlaneType : PLANES PLANE_TYPES, total
PlaneTypeConfig : SEATS PLANE_TYPES, total
Flight : TICKETS FLIGHTS, total
C1: PlaneType prPLANES(FLIGHTS) Flight = PlaneTypeConfig Seat
C2: (tTICKETS)(x,yROUTE_CONFIGS)
(prROUTES(ROUTE_CONFIGS)(x) = prROUTES(ROUTE_CONFIGS)(y) =
= prROUTES(FLIGHTS)(Flight(t))
(Source(t) = prAIRPORTS(ROUTE_CONFIGS)(x)
Destination(t) = prAIRPORTS(ROUTE_CONFIGS)(y)
prPOSITIONS(ROUTE_CONFIGS)(x) < prPOSITIONS(ROUTE_CONFIGS)(y)
Source(t) = prAIRPORTS(ROUTE_CONFIGS)(y)
Destination(t) = prAIRPORTS(ROUTE_CONFIGS)(x)
prPOSITIONS(ROUTE_CONFIGS)(y) < prPOSITIONS(ROUTE_CONFIGS)(x)))
Fig. 14: Subschemă MMED a unei bd simple pentru rezervarea de bilete aeriene
PlaneType prPLANES(FLIGHTS)
PLANE_TYPES PLANES FLIGHTS
PlaneTypeConfig
Flight
Seat
SEATS TICKETS
Fig. 15: Subdiagrama închisă a cărei analiză duce la formalizarea constrîngerii C1
1.4.5.5 Bucle închise neinteresante
Din fericire, nu toate sub-diagramele închise conțin asemenea constrângeri suplimentare. Fig. 17 și 18 prezintă un asemenea exemplu. În mod evident, în această diagramă Proprietar Utilizator Gazdă (căci utilizatorul curent al unui calculator ce găzduiește și niște bd nu este în general proprietarul vreuneia dintre ele) și nu există nici o comutativitate locală (cât despre cele generalizate, nici nu se poate pune problema în absența oricărei asociații).
Flight
TICKETS FLIGHTS ROUTES
Source
ROUTE_CONFIGS POSITIONS
Destination
AIRPORTS
Fig. 16: Subdiagrama închisă a cărei analiză duce la formalizarea constrîngerii C2
PERSOANE Gazdă : BDs CALCULATOARE, total
Proprietar : BDs PERSOANE, total
Proprietar Utilizator Utilizator:CALCULATOAREPERSOANE
BDs Gazdă CALCULATOARE
Fig. 17: Exemplu de diagramă închisă „neinteresantă” Fig. 18: Schema MMED corespunzătoare
Cu toate acestea, nici o diagramă închisă nu trebuie declarată ca fiind „neinteresantă” decât după o analiză aprofundată, pentru care recomandăm următorul algoritm de asistență a modelării buclelor închise.
1.4.5.6 Algoritmul de asistența analizei buclelor închise
Algoritmul 1.42 (asistența modelării buclelor închise)
Intrare: o diagramă E-A
Ieșire: mulțimea tuturor constrângerilor implicate de buclele închise ale diagramei
Strategie:
for (toate sub-diagramele închise) {
if (sub-diagrama este o buclă simplă) {
verifică dacă bucla nu trebuie să fie aciclică, cheie, surjectivă,
idempotentă, reflexivă, tranzitivă, simetrică, antisimetrică,
surjecția canonică a unui sistem de reprezentanți și/sau impli-
cată în vreo constrângere obiect;
} elseif (sub-diagrama comută convențional) {
formalizează constrângerea de comutativitate corespunzătoare;
analizează dacă bucla poate fi ruptă sau nu;
if (bucla se poate rupe)
simplifică schema eliminând funcția calculabilă;
eventual, dacă considerente de performanță o impun, adaugă la
schemă funcția calculată corespunzătoare;
} elseif (asociații non-funcționale implicate în buclă)
for (toate nodurile buclei) //nodurile sunt mulțimi de obiecte
verifică dacă există vreo comutativitate generalizată asociată
nodului current;
în caz afirmativ, formalizează constrângerea obiect corespunzătoare;
for (toate nodurile buclei) // nodurile sunt mulțimi de obiecte
verifică dacă există vreo comutativitate locală asociată
nodului current;
în caz afirmativ, formalizează constrângerea obiect corespunză-
toare;
};
adaugă toate constrângerile suplimentare găsite aplicând algoritmul la schema bd;
};
SfAlgoritm 1.42
Fig. 19: Algoritmul de asistență a modelării buclelor închise
1.5 Teoria asociațiilor
1.5.1 Structura asociațiilor
Pentru a putea defini corect elementele grafului unei asociații este desigur nevoie mai întâi de identificarea unică a elementelor asociate din fiecare mulțime suport a asociației. MMED folosește pentru aceasta tocmai identificatorii de obiect ai suporților.
Fie un tip oarecare fixat de asociații A Æ, fie r aritatea sa (i.e. numărul mulțimilor suport pe care este definită asociația), fie S1, S2,…, Sr suporții lui A, iar #S1, #S2,… ,#Sr identificatorii de obiect ai suporților. Extindem canonic identificatorii de obiect #Si, 1 i r, de la suporți la graful asociației A astfel:
Ai : A NAT, Ai(o1,…, oi,…, or) = #Si(oi), oj, 1 i, j r.
Propoziția 1.42 : Extensiile canonice Ai, 1 i r, nu sunt în general injective.
Dem : Fie asociația STOCURI, iar A1 și A2 proiecțiile sale canonice pe PRODUSE și MAGAZII. Dacă A1 ar fi injectivă, ar însemna că orice produs ar necesita o magazie proprie pentru a fi stocat; dacă A2 ar fi injectivă, ar însemna că nici o magazie n-ar putea stoca mai mult de un singur produs. Mai mult, dacă ambele ar fi injective, atunci orice magazie ar putea stoca un singur produs și orice produs n-ar putea fi stocat în mai mult de o magazie. Evident, aceste situații nu sunt în general plauzibile, deci, A1 și A2 nu sunt injective.
Lema 1.43 Produsul = al tuturor extensiilor canonice de mai sus este întotdeauna injectiv.
Dem: Prin definiție, mulțimile nu admit duplicate. Cum graful asociației este o mulțime, este injectivă .
Corolar 5.44 card r.
Observația 5.45
Această lemă sugerează faptul că orice tip de asociații conține obligatoriu extensiile canonice la graful asociației ale identificatorilor de obiect ai suporților acesteia. Produsul , zis suportul grafului asociației, identifică unic elementele mulțimii de asociații, ca și tipul însuși.
Notând cu A0 = #A identificatorul de obiect al lui A, rezultă că:
= A0, A1,…, Ar,…, An = A0 Ar+1,…, An, r n,
unde atributele de la r + 1 la nNAT sunt eventualele atribute explicit definite de proiectantul bd pe graful asociației A.
Privind dual, este evident că proiecțiile canonice ale grafului unei asociații pe suporți sunt exact extensiile canonice corespunzătoare: prSi A = Ai, i, 1 i r.
Exemplul 1.71 Revenind la exemplul 1.69 de mai sus (îmbogățit de exemplul 1.70) și precizând câteva atribute naturale suplimentare definite peste cele cinci mulțimi de entități și trei de asociații implicate, se poate obține bd prezentată în figura 1.1.
Identificatorii de obiect pentru fiecare mulțime în parte sunt, evident: #Loc, #Țara, #Discipl., #Olimp., #Proba, #LocConcurs, #Sp. și #Part. În PROBE, Disciplina și Olimp. sunt extensiile canonice ale #Discipl., respectiv #Olimp.; similar, în LOCALIZ_CONCURS, Loc și Concurs extind canonic #Loc, respectiv #Proba; în PARTICIPĂRI, Sportiv extinde #Sp., iar LocConcurs pe #LocConcurs; se poate observa că nici una dintre aceste extensii nu este injectivă, dar produsul lor corespunzător două câte două este injectiv (identificând unic programul olimpiadelor, localizarea desfășurării concursurilor, respectiv participarea sportivilor la ele). De exemplu, tipul LOCALIZ_CONCURS = {#LocConcurs, Loc, Concurs, DataInc., DataSf., Spect., Încasări} are două chei: #LocConcurs și {Loc, Concurs}.
Ca atare, de exemplu, cel de-al cincilea tuplu al acestei relații memorează informația că la San Francisco, între 18.06.96 și 10.07.96, s-a desfășurat o parte a turneului olimpic de fotbal (organizat în cadrul Jocurilor Olimpice 1996), la care au asistat 150.000 spectatori, ce au asigurat încasări de 100.000$.
Similar, de exemplu, ultimii doi tupli ai PARTICIPĂRI memorează informația că Michael Nylander a participat la turneul de hochei din cadrul Jocurilor Olimpice 1994, jucând de 4 ori la Albertville și de 2 ori la Grenoble.
De remarcat, în plus, importanța deosebită a identificatorilor de obiect pentru grafurile asociațiilor: de exemplu, sintactic, PARTICIPĂRI ar fi putut fi la fel de corect definită și în absența #LocConcurs, extinzând canonic în schimb Loc și Concurs (cheile fiind echivalente).
Această soluție ar fi condus însă la o gravă anomalie de actualizare: dacă în LOCALIZ_CONCURS se actualizează vreuna din valorile Loc sau Concurs ale unui tuplu referit în PARTICIPĂRI, exact aceeași modificare ar fi trebuit făcută în toți tuplii PARTICIPĂRI implicați!
Iar dacă, recursiv, PARTICIPĂRI n-ar avea identificatorul de obiect #Part și ar fi la rândul ei suportul unei alte asociații ierarhic superioară, anomalia de actualizare semnalată s-ar propaga până la rădăcina acestui arbore de ierarhizări! Evident însă că, în prezența identificatorilor de obiect #LocConcurs și #Part (care „izolează” sintactic între ele nivelurile ierarhiei de asociații), schema de bd nu prezintă nici o asemenea anomalie.
1.5.1.1 Funcționalitățile grafurilor de asociații
Ca și relațiile matematice din care provin, grafurile de asociații pot avea funcționalități interne. Exemplele cele mai convingătoare le constituie, desigur, grafurile relațiilor binare funcționale, pentru care sunt posibile 3 cazuri: nici o funcționalitate (relații binare oarecari), o funcționalitate (funcții oarecari) sau două funcționalități (funcții injective). Asemenea funcționalități pot exista însă și în cazul general al relațiilor n-are, n > 2.
Altfel spus, revenind la lema 1.43, este natural să ne întrebăm dacă suportul grafului oricărei asociații este nu doar injectiv, ci minimal injectiv. Următorul exemplu ne arată că acest lucru nu este în general adevărat.
Exemplul 1.72 Fie o bd poștală cu următoarele tipuri de obiecte:
LOCALITĂȚI = #Loc, Den_Loc, Județ, CODURI_POȘTA = #Cod și ADRESE = #Adr, Adresa, Loc, Careu, Descr_imobil, unde Adresa memorează numele străzii și numărul imobilului, Loc este cheie străină propagată de funcția Localiz_Adresa : ADRESE LOCALITĂȚI, iar Careu memorează coordonatele careului în care se află localizat imobilul de la adresa curentă (în paginile unui ghid cu hărți caroiate ale tuturor localităților).
Peste aceste trei tipuri de entități este definit tipul de asociații CODIF_POȘTALĂ=(CODURI_POȘTA,LOCALITĂȚI,ADRESE), care memorează codificarea poștală a adreselor din fiecare localitate, după următoarele reguli:
( i) codurile poștale sunt toate distincte între ele
( ii) pentru unele localități (mici) există câte un singur cod poștal, indiferent de adresa imobilelor în cadrul localității
(iii) în alte localități (foarte mari) fiecare imobil (sau grup de imobile adiacente) are asociat un unic cod poștal.
Figura 1.10 prezintă un posibil conținut al acestei bd (din care am selectat doar atributele relevante în contextul discuției).
Ullman [337] formalizează constrângerile (i) și (ii) prin #Cod Loc, iar (iii) prin Loc Adr #Cod. În plus, este evident că (iii) implică și Loc #Cod Adr. Aceste FD pun în evidență faptul că, astfel definit, graful CODIF_POȘTALĂ are trei funcționalități interne.
Definiția 1.46 Fie suportul grafului unei asociații oarecari A Æ ; A se zice funcțional (sau având o funcționalitate internă) de la X la Y, X, Y (X, Y ), dacă X Y.
Fie r aritatea lui .
Propoziția 1.47: poate avea cel mult (2r-1)2 funcționalități.
Dem:
Fie 1 i, j n; numărul tuturor funcționalităților ce au i suporți în partea stângă și j în cea dreaptă este .Deci, numărul tuturor funcționalităților lui este:
Figura 1.10 Un exemplu de graf al unei asociații ternare cu funcționalități interne
Propoziția 1.48 nu este întotdeauna minimal injectiv.
Dem.: Într-adevăr, revenind la exemplul 1.10, se observă că atât LocAdr, cât și Loc#Cod sunt minimal injective, deci chei în = LocAdr#Cod, care e doar supercheie.
Includerea în schema asociațiilor a tuturor cheilor suportului grafului este crucială; în caz contrar, s-ar permite memorarea de informații invalide.
Exemplul 1.73: nespecificarea celor două chei de mai sus ar permite existența simultană în graful CODIF_POȘTA a tuplilor aberanți (c, l, a) și (c', l, a), cu c c', ceea ce ar însemna că imobilului situat la adresa a în localitatea l îi corespund două coduri poștale distincte!
Evident însă că nu orice funcționalitate a unui graf de asociații ne dezvăluie o cheie a sa. Contraexemplul „clasic” îl oferă chiar #Cod Loc din exemplul 1.10: datorită faptului că pentru majoritatea localităților există câte un singur cod poștal pentru toate adresele din fiecare localitate, #Cod nu este o cheie a CODIF_POȘTALĂ. Din acest motiv, Ullman propune CODIF_POȘTALĂ drept exemplul clasic de relație care este în FN3, dar nu și în FNBC.
Observația 1.59
Teorema 1.58 caracterizează doar cheile , zise chei structurale ale asociației. Cum pe graful oricărei asociații se pot defini oricâte atribute, este posibil ca asociația să mai aibă și alte chei în afara celor structurale.
Cheile structurale se declară în MMED odată cu asociația; exemplificăm sintaxa folosită tot cu ajutorul exemplului 5.10:
CODIF_POȘTALĂ = (CODURI_POȘTA, LOCALITĂȚI, ADRESE,
CODURI_POȘTA, LOCALITĂȚI, LOCALITĂȚI, ADRESE).
Colecția suporților grafului este deci urmată de mulțimea cheilor structurale.
Lema 1.42 ne asigură că conține întotdeauna cel puțin o cheie; dacă este cheie, atunci lista cheilor structurale poate fi vidă, MMED completând-o implicit cu
1.5.2 Proiectarea asistată de calculator a schemelor de asociații
Teorema 1.58 oferă și instrumente sintactice suficient de puternice pentru a permite proiectarea unui algoritm de asistență a specificării tuturor cheilor structurale ale unei asociații.
Să observăm însă întâi că, în cazul particular al asociațiilor ternare, din cele 49 de funcționalități posibile, 19 sunt triviale, încă 18 sunt redundante, iar alte 6 nu sunt pline. Rămân deci 6 funcționalități, din care, simultan, doar maxim 3 pot fi datorate cheilor. În total însă, există 18 combinații posibile de chei. Similar, în cazul asociațiilor cuaternare, rămân 14 funcționalități pline, neredundante, din care, simultan, pot coexista maxim 6 chei.
Corolar 1.60
(i) Eliminând din mulțimea tuturor funcționalităților posibile ale unui graf de asociații orice funcționalitate trivială, redundantă sau non-plină, din funcționalitățile rămase încă se mai pot depista toate cheile structurale ale asociației.
Dacă K este cheie structurală a unei asociații , atunci, S K, KS nu poate fi cheie în .
Fie r = card.
Propoziția 1.61 are cel mult 2r-2 funcționalități pline și neredundante.
Dem: Fie 1 i < n. Există cel mult funcționalități pline și neredundante care au i suporți în partea stângă . Cum = 1, i{1,…,n}, atunci numărul tuturor funcționalităților pline și neredundante sunt este:
2n – 2.
Propoziția 1.62 are cel mult chei structurale.
Demonstrația acestei propoziții este similară cu demonstrația lemei lui Sperner.
Pe baza 1.60, 1.61 și 1.62 se poate proiecta algoritmul 1.63 de asistare a specificării cheilor structurale ale oricărei asociații (vezi figura 1.11).
Teorema 1.64 (Caracterizarea algoritmului 1.63):
(i) Complexitatea algoritmului este O(2n)
(ii) Algoritmul 1.63 este solid și complet.
Algoritmul 1.63 este optimal, i.e. pune proiectantului schemei de bd numărul minim cu putință de întrebări necesare pentru a specifica toate cheile asociațiilor.
Dem: (i) Trivial, deoarece algoritmul conține 3 bucle, toate finite, prima depinzând de n, dar împreună cu a doua având 2n-2 număr maxim de pași, iar cea de-a treia având cel multde pași.
(ii) Se observă că algoritmul generează toate cheile posibile, deoarece sunt generate, în cazul cel mai defavorabil, toate cele 2n-2 submulțimi ale oricărui tip de cardinal n, respectiv toate cele maxim chei posibile simultan. Mai mult, cum se verifică întâi minimalitatea fiecăreia din ele și abia apoi se întreabă proiectantul dacă produsul curent este sau nu cheie, rezultă că algoritmul calculează la fiecare pas doar cheile posibile în acel moment.
(iii) În cel mai rău caz (i.e. toate răspunsurile proiectantului sunt nu) trebuie desigur puse 2n-2 întrebări (deoarece sunt excluse atât mulțimea vidă, cât și), adică exact numărul întrebărilor generate de algoritm, întrucât nici o posibilă cheie nu este procesată mai mult de o singură dată. În toate celelalte cazuri, deoarece algoritmul începe cu proiecțiile atomice și adaugă produselor la fiecare buclă exterioară câte o nouă proiecție (până la n-1), rezultă că fiecare cheie în parte elimină numărul maxim posibil de întrebări ulterioare.
Observația 1.65
Desigur că algoritmul 1.63 nu poate garanta decât corectitudinea „sintactică” a structurii cheilor unei asociații; răspunderea pentru corectitudinea „semantică” nu poate reveni decât proiectantului schemei bd! Algoritmul 1.63 asistă însă riguros și eficient proiectarea căci:
pornește cu posibilele chei de aritate minimă (1), care sunt și cel mai ușor de „descoperit” (validat) de către proiectant și care, dacă se vădesc a fi chei structurale, elimină din cursă cele mai multe dintre restul de posibilități rămase;
nu se termină înainte de epuizarea tuturor posibilităților de a mai descoperi / valida încă o cheie structurală;
nu propune pentru validare decât posibile chei structurale;
se termină de îndată ce au fost validate numărul maxim de chei posibile simultan;
dacă nu a fost validată nici o posibilă cheie structurală, adaugă automat la schema asociației cheia maximală formată din toți suporții asociației;
în general, pentru orice asociație definită în schema bd și pentru orice cheie structurală a unei asociații, algoritmul adaugă schemei bd dependența de cheie corespunzătoare.
1.6 Normalitatea versus corectitudinea schemelor
1.6.1 Descrierea obiectelor
Chiar și incluziunile, egalitățile și disjuncțiile pot conduce la anomalii de actualizare în accepțiunea relațională. De exemplu, ștergerea tuplului corespunzător unei persoane dintr-o bd memorând ierarhia CADRE_DIDACTICE ANGAJAȚI PERSOANE poate conduce la un conținut invalid (dacă acea persoană este, de exemplu, cadru didactic).
De aceea, MMED consideră o abordare orientată obiect a noțiunilor de constrângere primitivă, compatibilitate semantică și anomalie de actualizare. Astfel, pe lângă descrierea primitivă (fundamentală) a obiectelor memorată de tipul corespunzător de obiecte, orice obiect beneficiază în MMED de o descriere completă: completând descrierea primitivă, aceasta include și mulțimea tuturor legăturilor sale cu alte obiecte (nu neapărat de același tip), adică, în fond, mulțimea tuturor acestor obiecte.
Formal, descrierea primitivă a oricărui obiect este dată de imaginea tipului de obiect corespunzător (aici interpretat ca produsul familiei tuturor atributelor definite pe mulțimea respectivă de obiecte, vezi 1.3.2) pentru mulțimea formată din acel obiect; descrierea completă a obiectului include și imaginea, pentru aceeași mulțime, a tuturor funcțiilor structurale definite pe respectiva mulțime de obiecte, ca și a tuturor suporților de grafuri ale asociațiilor care sunt construite și peste mulțimea respectivă de obiecte.
Algoritm 1.63
Intrări: mulțimea suporților unei asociații oarecare ( și r = card)
Ieșiri: mulțimea cheilor structurale ale asociației (K, k = cardK).
Procedeu: (bazat pe corolarul 6.28 și propozițiile 6.29 și 6.30)
K =; k = 0;
repetă până la specificarea a maxim chei structurale sau
până la epuizarea celor maxim 2r-2 funcționalități pline și neredundante;
dacă partea stângă (ps) a funcționalității curente nu include nici o cheie structurală
atunci propune proiectantului ps drept cheie structurală;
dacă proiectantul validează minimal injectivitatea ps
atunci K = K {ps}; k = k + 1;
sfdacă;
sfdacă;
sfrepetă;
dacă k == 0 // nici o cheie structurală; doar este cheie!
atunci k = 1; K = {};
sfdacă;
Program abstract:
k = 0; kmax = ; i = 1;
dowhile i r – 1 and k kmax
j = 1; jmax = ;
dowhile j jmax
generează Ti, j, a j-a submulțime cu i elemente a lui ;
l = 1; supercheie = fals;
dowhile l k and not supercheie
if K(l)
then supercheie = adevărat;
else l = l + 1;
endif
enddowhile;
if not supercheie
then întreabă proiectantul schemei asociației
dacă Ti, j este cheie structurală;
if răspunsul este afirmativ
then k = k + 1; K(k) = Ti, j;
endif
endif;
j = j + 1;
enddowhile;
i = i + 1;
enddowhile;
if k == 0 // nici o cheie structurală; doar este cheie!
then k = 1; K(1) = ;
endif;
Sfârșit algoritm 1.63
Fig. 5.12 Algoritmul de asistența specificării cheilor structurale
Exemplul 1.74 Revenind la exemplul 1.7 și figura 1.1, descrierea primitivă a obiectului x „localitatea cu numele Grenoble” este Localitate(x) = „Grenoble”, în timp ce descrierea sa completă este:
Localitate(x) = „Grenoble”,
Țara(x) = „F”,
LOCALIZ_CONCURS(x,) = Concurs() = 5,
PARTICIPARE(,x) = Sportiv() = 1, Sportiv() = 2, Sportiv() = 4 .
1.6.2 Constrângeri primitive
În accepția MMED, o constrângere se numește primitivă dacă ea este constrângere de domeniu sau dependență cheie sau dependență tipată de incluziune sau disjuncție de mulțimi sau surjectivitate de funcții sau egalitate de funcții sau aciclicitate de graf de asociații.
Evident că egalitatea mulțimilor este acoperită de (duble) incluziuni, idempotența de egalitatea funcțiilor, iar sistemele de reprezentanți de incluziuni, surjectivități și idempotențe. Ca atare, deși nu sunt primitive nici în MMED, toate constrângerile de tip egalitate de mulțimi, idempotență a funcțiilor și sisteme de reprezentanți sunt implicate de constrângeri primitive.
1.6.3 Compatibilitate semantică
Simpla lărgire a clasei constrângerilor primitive (în raport cu modelul relațional) nu este suficientă pentru a putea oferi definiția și caracterizarea unei „forme normale semantice” în MMED. Pentru aceasta, este nevoie și de modificarea accepțiunii pentru compatibilitate de la cea „sintactică” relațională, implicând un tuplu și o relație, la una „semantică”, implicând obiecte și o bază de date în ansamblul ei.
În MMED, un obiect (entitate sau asociație) se zice compatibil (semantic) cu o bază de date dacă el nu violează constrângerile primitive (în accepția MMED) asociate schemei acelei bd.
1.6.4 Anomalii de actualizare a datelor
Despre o schemă de bd în MMED se spune că are o anomalie de inserție, dacă există
un conținut valid al schemei și
un obiect compatibil cu acest conținut
astfel încât adăugarea obiectului la bd conduce la un conținut invalid.
Despre o schemă de bd în MMED se spune că are o anomalie de ștergere, dacă:
există un conținut valid al schemei și
un obiect al acestui conținut
astfel încât ștergerea obiectului din bd conduce la un conținut invalid.
Similar, despre o schemă de bd în MMED se spune că are o anomalie de modificare, dacă există
un conținut valid al schemei și
un obiect al acestui conținut
astfel încât modificarea descrierii complete a obiectului conduce la un conținut invalid.
În concluzie, o schemă de relație în MMED se zice a avea o anomalie de actualizare a datelor dacă ea are vreo anomalie de inserție, de ștergere sau de modificare.
1.6.5 Descrierile fundamentală și completă a obiectelor
Chiar și incluziunile, egalitățile și disjuncțiile pot conduce la anomalii de actualizare în accepțiunea relațională. De exemplu, ștergerea tuplului corespunzător unei persoane dintr-o bd memorând ierarhia CADRE_DIDACTICE ANGAJAȚI PERSOANE poate conduce la un conținut invalid (dacă acea persoană este, de exemplu, cadru didactic).
De aceea, MMED consideră o abordare orientată obiect a noțiunilor de constrângere primitivă, compatibilitate semantică și anomalie de actualizare. Astfel, pe lângă descrierea primitivă (fundamentală) a obiectelor memorată de tipul corespunzător de obiecte, orice obiect beneficiază în MMED de o descriere completă: pe lângă descrierea primitivă, aceasta include și mulțimea tuturor legăturilor sale cu alte obiecte (nu neapărat de același tip), adică, în fond, mulțimea tuturor acestor obiecte.
Formal, descrierea primitivă a oricărui obiect este dată de imaginea tipului de obiect corespunzător (aici interpretat ca produsul familiei tuturor atributelor definite pe mulțimea respectivă de obiecte, vezi 1.3.2) pentru mulțimea formată din acel obiect; descrierea completă a obiectului include și imaginea, pentru aceeași mulțime, a tuturor funcțiilor structurale definite pe respectiva mulțime de obiecte, ca și a tuturor suporților de grafuri ale asociațiilor care sunt construite și peste mulțimea respectivă de obiecte.
De exemplu, revenind la exemplul 1.7 și figura 1.1, descrierea primitivă a obiectului x „localitatea cu numele Grenoble” este Localitate(x) = „Grenoble” în timp ce descrierea sa completă este:
Localitate(x) = „Grenoble”,
Țara(x) = „F”,
LOCALIZ_CONCURS(x,) = Concurs() = 5,
PARTICIPARE(,x) = Sportiv() = 1, Sportiv() = 2, Sportiv() = 4 .
1.7 Importul bazelor de date relaționale în MatBase
Orice bază de date MatBase MBDB are cinci componente integrate [0]: o bd relațională MBR (stocată momentan de catre o instanță MS SQL Server, dar stocabilă pe orice alt tip de SGBDR), o mulțime de diagrame Entități-Asociații MBE, o schemă în MMED MBM (care include și o schemă logică Datalog MBD) și o aplicație (.NET C#) MBA construită peste MBR și MBD, care oferă utilizatorilor posibilitatea de a-i actualiza instanța fără a încălca vreo constrângere a MBM, precum și posibilitatea de a o interoga folosind atât QBE, SQL, cât și Datalog.
Pe scurt, MBDB = (MBR, MBE, MBM, MBD, MBA). Această secțiune prezintă și caracterizează algoritmii de traducere din MRD în MRD, MEA și MMED folosiți de subsistemul de import al MatBase.
Algoritmul de import relațional MatBase:
IN: o bază de date relațională non-MatBase
OUT: baza de date corespunzătoare MatBase
MBR = R-R(RDB) // import relațional optimizat
MBM = R-M(MBR) // traducere MMED
MBE = R-ER(MBR) // traducere DE-A
if utilizatorul dorește și acest lucru then begin
detectează toate buclele închise ale MBE;
apelează algoritmul prezentat în [13] pentru analiza buclelor închise;
repeat for all mulțimile de obiecte din ale MBM
apelează algoritmul prezentat în [10] pentru asistența proiectării cheilor
end repeat;
end;
generează aplicația MBA;
end algoritm
1.7.1 Algoritmul MatBase R-R de import din MRD în MatBase MRD
IN: o bază de date relațională (SQL Server, Access, Oracle etc.) RDB
OUT: o bază de date MatBase corespunzatoare de tip relațional MBR
// copiere scheme și instanțe tabele din RDB în MBR; convertire MBR la standard MatBase
// pasul 1: importă și convertește fără dependințe de incluziune
repeat for all tabelele RRDB, în ordinea top-down a referințelor cheilor străine
crează tabela R cu toate atributele și constrângerile sale, cu excepția integrității
referințelor;
copiază datele instanței R;
if cheia primară referă altă cheie primară key then // R este o submulțime a unei mulțimi S
if cheia primară nu este o coloană memorând întregi then
begin
adaugă o coloană de întregi #R;
generează pentru ea valori corespunzătoare din cheia primară a tabelei referite S;
șterge toate coloanele cheii primare ce nu fac parte din alte chei și/sau chei străine;
înlocuiește cheia primară cu #R și declară #R și cheie străină referind S;
end;
else // R nu este o submulțime
if nu există nici o coloană auto-number în R then
begin if există o cheie primară then transform-o într-o cheie oarecare (ne-primară);
adaugă o cheie primară auto-number #R;
end
else if coloana auto-number A nu este cheie primară then
begin if există o cheie primară then transform-o într-o cheie oarecare (ne-primară);
declară A drept cheie primară a R;
end;
end repeat;
// pasul 2: importă și convertește dependențele de incluziune
repeat for all tabelele R
repeat for all cheie străină fk a R (referind S)
if fk este un atribut f then
if f nu referă cheia primară #S a S then înlocuiește valorile f cu cele #S corespunzătoare
(schimbând, desigur, tipul domeniului său în întregi, dacă este cazul);
forțează integritatea referințelor f;
else // fk este un produs de atribute
begin
adaugă o coloană de întregi fk la tabela R;
completeaz-o cu valorile corespunzătoare ale #S (din join-ul R și S pe coloanele
corespunzătoare fk);
if fk nu admite null-uri (i.e. nici una dintre coloanele componente nu admite null-uri)
then adaugă constrângerea fk not null;
if fk este cheie then
begin adaugă constrângerea fk unique;
șterge constrângerea de unicitate pentru produsul fk (fosta cheie străină);
end;
forțează integritatea referințelor fk;
end;
end repeat;
repeat for all cheile străine de tip produse de atribute
șterge toate constrângerile de tip chei străine corespunzătoare;
șterge toate coloanele cheii străine ce nu fac parte din alte chei și/sau chei străine;
end repeat;
// pasul 3: forțăm existența a cel puțin unei chei semantice
if dacă nu există nici o cheie în R cu excepția celei auto-number then
begin
încearcă forțarea cheii a1 … an (a1, …, an fiind toate atributele R cu excepția cheii
sale primară auto-number);
if forțarea nu reușește then
begin // instanța R nu este o mulțime!
adaugă la R o nouă coloană numerică an+1, cu null-uri pentru liniile ce nu sunt duble
și cu valori distincte 1,2, etc. pentru cele duble (peste a1 … an);
adaugă constrângerea de unicitate asupra a1 … an+1;
adaugă la tabelele MatBase de logare a erorilor mesajul “R nu este mulțime; a fost
adăugată la ea o nouă coloană an+1 cu valori ce o transformă într-o mulțime.”;
end;
end;
// pasul 4: forțăm existența a cel putin unui atribut semantic nenul
if nu există nici un atribut semantic non-null then
begin
întreabă utilizatorul ce atribut semantic nu ar trebui să accepte null-uri;
if atributul A ales de utilizator are null-uri then
înlocuiește-le cu o valoare non-nulă precizată de utilizator
(implicit: 0, spațiu, false, data curenta etc.);
adaugă la R constrângerea A not null.;
end;
end repeat;
End Algoritm R-R.
Teorema 1 (caracterizarea R-R):
(i) R-R este liniar;
(ii) R-R este o funcție bine definită;
(iii) R-R este surjectiv;
(iv) R-R nu este injectiv;
(v) R-R este solid;
(vi) R-R este complet.
Demonstrație:
(i) Este evident că R-R nu buclează la infinit, deoarece orice schemă și instanță relațională a ei sunt finite, deci algoritmul se va opri cu siguranță în cele din urmă, după ce va procesa toate tabelele, coloanele, liniile și constrângerile. Fie orice bd relațională R; notăm cu k cardinalul ei, k = r + a + t + c, unde r, a, t și c sunt cardinalele mulțimilor tabelelor, coloanelor, tuplilor și respectiv constrângerilor; evident, complexitatea R-R este O(k).
(ii) Fie R1 și R2 două relații astfel încât R1 = R2. Presupunem prin absurd că R-R(R1) ≠ R-R(R2); conform R-R, cel putin o tabelă, un atribut, un tuplu, sau o constrângere trebuie sa difere între R1 și R2, ceea ce este, evident, imposibil; rezultă ca presupunerea R-R(R1) ≠ R-R(R2) este falsă.
(iii) Fie R orice bd relațională MatBase; evident că ea poate fi stocată de orice alt SGBDR și că R-R(R) = R.
(iv) Fie RDB1 ≠ RDB2 două bd relaționale identice, mai putin două relații R1 ≠ R2 care diferă doar prin structura cheilor străine fk1 (din R1) și fk2 (din R2), ambele acestea fiind produse de atribute și referind o relație oarecare S; de exemplu, presupunem că fk1 are două atribute, în timp ce fk2 are trei; inspectând pasul 2 al algoritmului R-R, observăm că ambele tabele vor fi convertite la o aceeași tabelă R.
(v) Evident, din proiectare, pentru orice bază de date relațională, ieșirea corespunzătoare R-R este o bază de date relațională validă, conform standardelor MatBase.
(vi) Evident, tot din proiectare, orice bază de date relațională MatBase poate fi obținută cu ajutorul R-R. Q.e.d.
1.7.2 Algoritmul MatBase R-M de traducere a MRD în MMED
Algoritm R-M:
IN: o schemă relațională MatBase MBR
OUT: schema corespunzătoare MBM în MMED
// pasul 1: traducerea tabelelor în obiecte MMED
repeat for all tabelele R ale MBR, în ordinea top-down a referințelor cheilor străine
adaugă la E o mulțime numită R
if #R referă tabela S then adaugă la C constrângerea R S;
repeat for all atributele a ale R (luând valori în domeniul V) care nu sunt chei străine
if V nu aparține deja lui V then adaugă V la V ;
adaugă la A un atribut a : R → V;
if a nu admite null-uri then adaugă în loc a : R → V, total;
if a este unic then adaugă la C constrângerea “key a”;
end repeat;
end repeat;
// pasul 2: traducerea cheilor străine în funcții structurale
repeat for all tabelele R ale MBR
repeat for all cheile străine f ale R (referind S)
adaugă la F o funcție structurală f : R → S;
if f nu admite null-uri then adaugă în loc f : R → S, total;
if f este unic then adaugă la C constrângerea “key f”;
end repeat;
end repeat;
// pasul 3: traducerea cheilor compuse în minimal injectivități
repeat for all tabelele R ale MBR
repeat for all cheile k = a1 … an, în ordinea crescătoare a cardinalităților acestora
if k nu include nici o altă cheie
then adaugă la C constrângerea “key a1 … an”;
else begin adaugă k la tabelele de logare erori MatBase (mesaj: „supercheia k eronat
declarată cheie”);
șterge constrângerea de unicitate asociată k;
end;
end repeat;
end repeat;
// pasul 4: traducerea constrângerilor tuplu în constrângeri obiect
repeat for all tabelele R ale MBR
repeat for all constrângerile tuplu tc ale R
adaugă la C constrângerea obiect corespunzătoare tc;
end repeat;
end repeat;
End Algoritm R-M.
Teorema 2 (caracterizarea R-M):
(i) R-M este linear;
(ii) R-M este o funcție bine definită;
(iii) R-M nu este surjectiv;
(iv) R-M este injectiv;
(v) R-M este solid;
(vi) R-M nu este complet.
Demonstrație:
(i) Este evident că R-M nu buclează la infinit, deoarece orice schemă și instanță relațională este finită, deci el se va opri în cele din urmă după ce va procesa toate tabelele, coloanele, liniile și constrângerile. Oricare ar fi o bd relațională, notăm cu k cardinalul ei, k = r + a + c, unde r, a și c sunt cardinalele mulțimilor tabelelor, coloanelor și respectiv constrângerilor; evident, complexitatea R-M este O(k).
(ii) Fie R1 și R2 oricare două scheme relaționale identice (R1 = R2). Presupunem că R-M(R1) ≠ R-M(R2); inspectând R-M se observă că cel puțin o tabelă sau un atribut (de la pasul 1) sau cel puțin o cheie străină (de la pasul 2) sau o cheie (de la pasul 3) sau o constrîngere tuplu (de la pasul 4) diferă între R1 și R2, ceea ce este absurd; rezultă că presupunerea R-M(R1) ≠ R-M(R2) este falsă, deci R-M(R1) = R-M(R2).
(iii) Fie M = (S, M, C, P ) o schemă oarecare având fie P ≠ Ø și/sau C conținând o constrângere non-relațională; evident că nu există nici o bază de date relațională care ar putea fi tradusă de R-M în M.
(iv) Demonstrația este lungă, anostă, dar simplă, deci rămâne ca exercițiu pentru cititor; pe scurt, se consideră oricare două bd relaționale distincte D1 și D2 și se demonstrează că R-M generează două scheme corespunzătoare MMED distincte; acest lucru se face prin inspectarea tuturor cazurilor posibile de diferențe între D1 și D2 (fie ele relații, atribute și/sau constrângeri). Se observă că, evident, injectivitatea este garantată modulo cheile primare surogat (pe măsură ce R-M le adaugă peste tot unde acestea nu există).
(v) Evident, prin proiectare, pentru orice bază de date relațională ieșirea corespunzătoare R-M este o bază de date relațională MMED validă.
(vi) Modulo toate cele 13 tipuri de constrângeri MMED care nu există în MRD, constrângerile obiect care implică funcții definite pe diferite mulțimi ce nu sunt incluse una în cealaltă sau având multiple apariții ale variabilelor, modulo asociații și programe Datalog¬, R-M ar fi complet; dar in prezența acestora, evident, R-M nu poate fi complet. Q.e.d.
Observație: schemele calculate cu R-M nu au asociații (Æ = Ø și O = E ), ceea ce nu ar trebui să fie de mirare: MRD nefiind orientat obiect, nu se poate deduce sintactic dacă o tabelă corespunde unei mulțimi de entități sau uneia de asociații. Oricum, aceasta nu este o problemă deoarece modelul entități-asociații este echivalent cu modelul funcțional al datelor, iar singurul tip fundamental de relație este cel funcțional [16].
1.7.3 Algoritmul Matbase R-ER de traducere din MRD în ME-A
Algoritm R-ER:
IN: o schemă relațională MatBase MBR
OUT: diagrama E-A MBE corespunzătoare
// pasul 1: traducerea tabelelor în dreptunghiuri și a atributelor non chei străine în elipse
repeat for all tabelele R ale MBR
adaugă la MBE un dreptunghi etichetat R;
repeat for all atributele a ale R ce nu sunt chei străine
adaugă la R o elipsă etichetată a
end repeat;
end repeat;
// pasul 2: traducerea cheilor străine în săgeți
repeat for all tabelele R ale MBR
repeat for all cheile străine f ale R (referind S)
adaugă o săgeată etichetată f de la R la S;
if f este unică then săgeata trebuie să fie dublă;
else if f este și cheie primară then săgeata trebuie să fie de tip incluziune canonică;
end repeat;
end repeat;
End Algoritm R-ER.
Teorema 3 (caracterizarea R-ER):
(i) R-ER este liniar;
(ii) R-ER este o funcție bine definită;
(iii) R-ER nu este surjectiv;
(iv) R-ER nu este injectiv;
(v) R-ER este solid;
(vi) R-ER nu este complet.
Demonstrație:
(i) Este evident că R-ER nu buclează la infinit, deoarece orice schemă și instanță relațională este finită, deci el se va opri în cele din urmă după ce va procesa toate tabelele, coloanele, liniile și constrângerile. Oricare ar fi o bază de date relațională, notăm cu k cardinalul ei, k = r + a + c, unde r, a și c sunt cardinalele mulțimilor tabelelor, coloanelor și respectiv constrângerilor; evident, complexitatea R-M este O(k).
(ii) Fie R1 și R2 oricare două scheme relaționale astfel încât R1 = R2. Presupunem că R-ER(R1) ≠ R-ER(R2); inspectând R-ER, se observă că cel puțin o tabelă sau un atribut (de la pasul 1) sau o cheie străină (de la pasul 2) diferă între R1 și R2, ceea ce este absurd; rezultă că presupunerea ER(R1) ≠ R-ER(R2) este falsă, deci ER(R1) = R-ER(R2).
(iii) Fie D o DE-A oarecare ce conține cel puțin un romb; evident că nu există nici o bd relațională care poate fi tradusă cu R-ER în D.
(iv) Fie BD1 ≠ BD2 două bdr diferind doar prin tipul produselor de atribute alcătuind o cheie a unei tabele R; evident, R-ER va traduce ambele în aceeași DE-A.
(v) Evident, prin proiectare, pentru orice schemă relațională, R-ER va genera la ieșire o DE-A corespunzătoare validă.
(vi) Deoarece nu generează romburi, R-ER nu este complet. Q.e.d.
1.7.4 Algoritmul MatBase M-R de traducere a MMED în MRD
Fundamentat de teoria MMED, algoritmul M-R de translație a schemelor de bd din MMED în model relațional prezentat în continuare generează scheme relaționale înalt normalizate.
Din punct de vedere „sintactic”, se poate ușor demonstra următoarea teoremă:
Teorema 4 (caracterizarea M-R)
(normalitatea schemelor de bd traduse din MMED în model relațional)
Schemele de bd relaționale generate de algoritmul M-R din scheme MMED sunt în FNDC.
b) (proprietățile aplicației de traducerea schemelor MMED în modelul relațional)
Aplicația stabilită de traducerea schemelor MMED în modelul relațional prin algoritmul M-R este surjectivă, dar neinjectivă.
Algoritmul M-R (traducerea schemelor de bd din MMED în modelul relațional)
Intrări: o schemă de bd în MMED;
Ieșiri: schema echivalentă în model relațional.
Program abstract:
Repetă pentru fiecare dintre mulțimile de entități ale schemei
generează cheia surogat a tipului (injectivă; cardinalul codomeniului ei este egal cu cel specificat de
proiectantul schemei MMED pentru mulțimea de entități curentă) din identificatorul de o-
biect aferent;
generează o schemă de relație conținând toate atributele definite pe mulțimea de entități curentă;
pentru fiecare dintre aceste atribute în parte adaugă o constrângere de domeniu corespunză-
toare (domeniul atributului relațional = codomeniul atributului MMED corespunzător)
Sfrepetă; // generare relații corespunzătoare tipurilor de entități
Repetă pentru fiecare dintre mulțimile de asociații ale schemei
generează cheia surogat a tipului (injectivă; cardinalul codomeniului ei este egal cu produsul cardi-
nalelor specificate de proiectantul schemei MMED pentru mulțimile suport ale asociației)
din identificatorul de obiect aferent;
generează suportul grafului asociației (extinzând canonic identificatorii de obiect ai tuturor
suporților asociației curente);
generează o schemă de relație conținând toate atributele definite pe mulțimea de asociații cu-
rentă;
pentru fiecare dintre aceste atribute în parte adaugă o constrângere de domeniu corespunză-
toare (domeniul atributului relațional = codomeniul atributului MMED corespunzător)
dacă asociația nu are chei structurale explicite
atunci generează o cheie structurală cu toate atributele formând suportul grafului asociației;
sfdacă;
Sfrepetă; // generare relații corespunzătoare tipurilor de asociații
Repetă pentru fiecare dintre funcțiile structurale : A B ale schemei
adaugă la schema relației corespunzătoare mulțimii de obiecte A un atribut cu numele ;
adaugă o constrângere de domeniu de tip: dom() = dom(#B), unde #B este identificatorul de
obiect al B (dom() este domeniul relațional al atributului );
adaugă o dependență de incluziune de tip RA() RB(#B), unde RA și RB sunt schemele de re-
lație generate pentru mulțimile de obiecte A, respectiv B;
Sfrepetă; // propagarea cheilor
Repetă pentru toate funcțiile injective j din schema MMED (fie ele atribute, identificatori de
obiect sau funcții structurale)
adaugă o dependență de cheie de tip „cheie(j)”;
Sfrepetă;
Repetă pentru toate celelalte constrângeri de integritate explicite
tradu fiecare tip de constrângere conform implementării MMED (de exemplu, absolut toate
în constrângeri tuplu);
Sfrepetă;
Sfârșit algoritm M-R;
1.7.5 Compunerea algoritmilor de traducere ai MatBase
Adăugarea R-M și R-ER la diagrama din [12] conduce la obținerea diagramei din Figura 1.
Fig. 1: Diagrama algoritmilor MatBase de traducere inter-modele
Teorema 4 (Comutativitatea diagramei din Figura 1):
R-M ER-R = ER-M.
Demonstrație:
Fie oricare ar fi DE-A D, S = R-M(ER-R(D)) și S’ = ER-M(D). Presupunem că S ≠ S’; rezultă că fie colecția mulțimilor de obiecte sau mulțimea funcțiilor sau cardinalul mulțimilor de constrângeri diferă sau că exista cel puțin o funcție sau o constrângere care diferă între ele.
Dacă diferă cardinalele, atunci fie S are cel puțin o mulțime de obiecte sau o funcție sau o constrângere în plus față de S’ sau vice-versa; fie primul caz (cel de-al doilea fiind similar): conform Teoremei 2, rezultă că schema relațională ER-R(D) conține o relație sau o cheie străină în plus față de dreptunghiurile, romburile, respectiv săgețile lui D; de aici rezultă că ER-R generează o relație sau o cheie străină care nu are corespondent în D, ceea ce este evident imposibil (conform teoremei de caracterizare a ER-R); cum reciproca este în mod trivial falsă, rezultă că S și S’ sunt echipotente. Presupunem acum că există cel puțin o funcție sau o constrângere care diferă între cele două, de exemplu f și f’, respectiv c și c’. Dacă f ≠ f’, atunci domeniile și/sau codomeniile diferă; să presupunem întâi că diferă domeniile: de aici rezultă că fie R-M, fie ER-M calculează greșit domeniile funcțiilor, ceea ce este imposibil (conform teoremelor de caracterizare corespunzătoare); dacă diferă codomeniile, lucrurile sunt similare și rezultă în final că f = f’. Dacă c ≠ c’, atunci lucrurile sunt iar similare, indiferent că acestea ar fi de tip cheie, totalitate sau obiect. Q.e.d.
Teorema 5 (Comutativitatea duală din figura 1):
R-ER ° M-R = M-ER.
Demonstrație:
Fie M o schemă MMED oarecare, D = R-ER(M-R(M)) și D’ = M-ER(M). Să presupunem că D ≠ D’; cum nici R-ER, nici M-ER nu generează romburi, rezultă că fie cardinalele mulțimilor dreptunghuirilor sau elipselor sau săgeților lor diferă, fie există cel puțin un dreptunghi (cu elipsele sale asociate) sau o săgeată care diferă între ele. Dacă cardinalele diferă, atunci fie D are un dreptunghi, elipsă, ori săgeată în plus, fie vice-versa; presupunem primul caz (al doilea fiind similar): conform Teoremei 3, schema relațională M-R(M) conține o relație, atribut sau cheie străină în plus față de M; de aici rezultă că M-R a generat o relație, atribut sau cheie străină care nu există în M, ceea ce este evident imposibil (conform teoremei sale de caracterizare); cum și reciproca este falsă, rezultă că D și D’ sunt echipotente. Presupunem că există cel puțin un dreptunghi sau o săgeată care diferă între ele, de exemplu r și r’ respectiv a și a’; dacă a ≠ a’, atunci domeniile și/sau codomeniile lor diferă; să presupunem mai întâi că domeniile diferă: rezultă că fie R-ER, fie M-ER calculează greșit domeniile funcțiilor, ceea ce nu este posibil (conform teoremelor lor de caracterizare); și în cazul codomeniilor, lucrurile sunt similare și, deci, a și a’ nu pot să difere. Presupunem acum că r ≠ r’, ceea ce înseamnă că diferă și cardinalele elipselor: fie r are cel puțin o elipsă în plus, fie vice-versa; presupunem primul caz (cel de-al doilea fiind similar): conform teoremei de caracterizare a M-R, schema relațională R rezultată din M-R(M) conține un atribut corespunzător în plus față de cele atașate mulțimii de obiecte R a lui M, ceea ce este evident imposibil; rezultă că r și r’ sunt echipotente. Q.e.d.
2. Arhitectura MatBase și a sub-sistemului său de import
2.1 Arhitectura MatBase
Arhitectura MatBase este structurată pe cinci niveluri (figura 2.1): nivelul interfață utilizator, nivelul MatBase Business Objects, nivelul Data Base Manager, nivelul librăriilor și nivelul SQL Server.
Fig. 2.1: Arhitectura MatBase
Interfața cu utilizatorul este realizată în C#, aplicația fiind prietenoasă, ușor de folosit de către utilizatori, dotată și cu opțiune de Help. Aplicația permite accesul atât la bd aflate pe serverul local, cât și la bd aflate pe alte servere active conectate în rețea. De asemenea, interfața este realizată în mod multilingv, utilizatorului fiindu-i permis în orice moment schimbarea limbii curente (dintre, în acest moment, engleză, franceză, română, italiană, spaniolă, germană) fără a fi nevoie să restarteze aplicația, sau să închidă fereastra curentă de lucru. Limba implicită de lucru pentru aplicație este limba engleză. Oricând se pot adăuga noi limbi și/sau șterge limbi existente (cu excepția englezei).
Nivelul MatBase Business Objects este reprezentat de colecții de clase care implementează algoritmii folosiți de diferitele componente MatBase.
Nivelul Data Base Manager este reprezentat de componenta MSSQL_DBManager, care face legătura cu SGBDR MS SQL Server, gestionând conexiunile între meta-catalogul MatBase, cel al SQL Server, bazele de date utilizator și aplicație.
Nivelul librăriilor este reprezentat de două categorii de librării: cele care sunt folosite de întreaga aplicație, precum PlatformExceptionLibrary, Translations, FileUtils și cele folosite doar de o anumită componentă, precum DBServerUtils (folosită exclusiv de MSSQL_DBManager).
Meta-catalogul MatBase este implementat de bd MatBase, a cărei arhitectură se împarte la rândul ei în tabele, view-uri, proceduri catalogate etc. Orice modificare adusă schemei oricărei baze de date prin intermediul aplicației este memorată în tabelele bd MatBase; desigur că acestea sunt acceptate de aplicație numai dacă nu încalcă nici o constrângere a schemei MMED a MatBase.
2.2 Arhitectura subsistemului de import relațional
Implementarea subsistemului de import relațional MatBase respectă, desigur, întocmai arhitectura întregii aplicații, folosind atât clase și metode din nivelul MatBase Business Objects, cât și proceduri catalogate SQL, precum și, evident, Data Base Manager (pentru a izola operațiile cu bd, astfel încât MS SQL Server să poată fi oricând ușor înlocuit cu orice alt SGBDR, precum, de exemplu, Oracle sau IBM DB/2).
Subsistemul de import permite accesul la orice bază de date, fie ea de tip MatBase sau relațională (în acest moment doar MS SQL Server, dar, potențial, gestionată de orice alt SGBDR). Pentru o bd de tip MatBase, importul se rezumă la o banală copiere a tabelelor cu date, constrângeri, relații, etc. În cazul importului unei bdr oarecare, non-MatBase, subsistemul apelează la algoritmii de conversie MRD MMED și MRD MEA, aducând baza de date relaționala la formatul MatBase.
Arhitectura meta-catalogului MatBase este foarte complexă, fiind alcătuită dintr-un număr foarte mare de tabele și o multitudine de relații între acestea. Însă, din punct de vedere al importului bazelor de date în MatBase, doar câteva dintre aceste tabele prezintă interes.
În primul rând, tabelele SERVERS și DATABASES sunt cele în care aplicația stochează informațiile despre toate bazele de date gestionate de diverse instanțe de SGBDR. Structura celor două tabele este următoarea: SERVERS = { #SRV, ServerName, Active, DBMSVersion }, DATABASES = { #DB, DataBaseName, Server, DatabaseSemantics } cu Server cheie străină în DATABASES (luând valori din coloana #SRV a tabelei SERVERS), iar DBMSVersion cheie străină într-o tabelă DBMSVersions.
Orice server găsit în rețea este adăugat automat în tabela SERVERS. În coloana Active, aplicația setează valoarea 1 în dreptul fiecărui server găsit activ și, astfel, pot fi accesate de către utilizator, în orice moment, toate serverele active din rețea. Dacă un server devine inactiv, câmpul Active ia valoarea 0 și deci aplicația nu mai încearcă accesarea acelui server, până când el nu re-devine activ. Evident că în coloana ServerName este memorat numele (instanțelor) serverelor cunoscute. Coloana #SRV asociază fiecărui server câte un id unic, fiind totodată și cheia pimară a tabelei.
În tabela DATABASES, coloana Server indică instanța serverului pe care se află baza de date respectivă, #DB asociază un id unic fiecărei baze de date, DataBaseName este coloana care memorează numele bazelor de date, iar DatabaseSemantics este o coloană în care se pot păstra informații suplimentare despre bazele de date gestionate de MatBase.
Observație: Bazele de date non-MatBase gestionate de instanțele serverelor active devin vizibile utilizatorului doar în cazul în care se dorește importul unei baze de date în MatBase. Subsistemul de import folosește tabela SERVERS doar în citire. Evident că, pentru fiecare bd importată, se adaugă o linie corespunzătoare în tabela DATABASES.
O primă tabelă esențială în timpul importului este SETS, care are următoarea structură: SETS = { #S, SetName, SetType, ObjectId, FactPredicate, *card, Synonim, Relationship?, SetSemantics, Database, SetCategory, SetCategOrdinal } și în care se memorează, așa cum am văzut în subsecțiunea 1.2.1.1, toate mulțimile (fie ele sistem, ale meta-catalogului MatBase sau ale bd utilizator gestionate de acesta). Oricărei tabele importate în MatBase i se asociază o entitate cu același nume, care este memorată de o linie a tabelei Sets.
#S este un id unic asociat fiecărei mulțimi; SetName este numele mulțimii; SetType este tipul mulțimii (doar de entități în cazul oricărei tabele importate, dar putînd fi, în general și de asociații, de valori sau mulțimea vidă); ObjectId este cheie străină în tabela FUNCTIONS (despre care vom vorbi în aliniatul următor); FactPredicate este cheie străină în tabela PREDICATES; *card este cardinalul mulțimii (deci numărul de linii ale tabelei importate); Relationship? este fals pentru orice mulțime atomică (iar importul nu poate presupune niciodată altceva), respectiv true pentru orice mulțime non-atomică (i.e. de fapt o mulțime de asociații, pentru care însă proiectantul schemei de bd respective a ales modelarea echivalentă alternativă cu o mulțime de entități și câte o funcție structurală pentru fiecare proiecție canonică corespunzătoare, ignorând deci structura internă a elementelor mulțimii); SetSemantics este o coloană în care se pot memora informații suplimentare despre mulțimea respectivă (de exemplu, pentru mulțimea DATE se poate stoca informația “mulțimea datelor calendaristice”); DataBase este cheia străină în DATABASES ce memorează baza de date de care aparține mulțimea respectivă; SetCategory trebuie să aibă pentru orice tabelă importată valoarea 6 (corespunzând categoriei „Utilizator”); iar SetCategOrdinal este un natural generat de subsistemul de import crescător, începând de la 1, unic pentru fiecare tabelă (și pe care utilizatorul îl va putea oricând modifica ulterior pentru a schimba ordinea în care sunt exportate mulțimile corespunzătoare).
Cea de-a patra tabelă care prezintă interes este tabela FUNCTIONS, în care se memorează coloanele fiecărei tabele importate. Structura tabelei FUNCTIONS este următoarea : FUNCTIONS = { #F, FunctionName, Domain, Codomain, Attribute, Injective, Total, Projection?, Acyclic, Idempotent, Surjective, Reflexive, Transitive, Symmetric, Antisymmetric, DomConstr, Position, DefaultValue, Renaming, FunctionSemantics }. Coloana #F este id-ul asociat fiecărei funcții, FunctionName este numele funcției (coloanei importate), Domain este domeniul de definiție al funcției, Codomain este codomeniul funcției, iar coloana Attribute este setată la true dacă funcția nu este structurală, ci de tip atribut (ceea ce, în cazul importului relațional, corespunde coloanelor de importat ce nu sunt chei străine). Desigur Total trebuie setat la true dacă funcția este peste tot definită (deci coloana importată corespunzătoare nu admite nuluri).
Diagrama tabelelor mai sus menționate este prezentată în figura 2.2:
Fig. 2.2: Structura sub-meta-catalogului MatBase relevantă sub-sistemului de import relațional
2.3 Probleme survenite în cursul implementării și soluțiile adoptate
O primă problemă apărută în construirea și utilizarea sub-sistemului de import MatBase, a fost conectarea la serverele din rețea. Utilizând metoda clasică de conectare a unei aplicații C# la un server SQL, cu ajutorul unui string de conectare cu autentificare Windows, aplicația funcționa perfect pe orice SQL Server 2003, însă nu se putea conecta la serverele SQL 2005, care, conform noului standard, cereau implicit autentificare de tip SQL, cu user și parolă.
Astfel, aplicația a trebuit modificată, prin adăugarea unei noi ferestre de dialog cu utilizatorul, care apare de fiecare dată când se dorește conectarea la un nou server, fie el cel local sau oricare alt server din rețea. Această nouă fereastră, ilustrată în Fig. 2.3, așteaptă un cont de utilizator și o parolă cu care se dorește conectarea la serverul în cauză. Deoarece aplicația poate rula și de pe un alt calculator decât cel pe care se află baza de date MatBase, chiar la pornirea aplicației se solicită numele contului de utilizator și parola de acces la serverul pe care se află meta-catalogul MatBase, indiferent că aceasta se găsește sau nu pe serverul local.
Fig. 2.3: Fereastra MatBase permițând conectarea la instanțe de servere necesitând autentificare SQL
O a doua problemă care a intervenit în cursul dezvoltării sub-sistemului de import MatBase, a fost faptul că aplicația ignoră orice bază de date pe care nu o gestionează și, deci, orice bază de date care nu se află înregistrată în tabelele MatBase, nu era vizibilă utilizatorului în momentul în care acesta dorea să facă un import. De aceea, sub-sistemul de import, pe lânga conexiunea la server, interoghează tabela sistem sys.databases a MS SQL Server, pentru a putea afișa lista completă a bazelor de date de pe serverul curent.
O altă problemă apărută în cazul importului, a fost utilizarea procedurilor catalogate. Pe orice bază de date se pot defini proceduri catalogate ce pot fi apelate de fiecare dată când este nevoie. Problema în sine era că sub-sistemul de import trebuia să lucreze simultan cu cele trei baze de date: baza sursă, baza destinație și meta-catalogul MatBase. Datorită incapacității C#-ului de a menține deschise mai multe conexiuni către SQL simultan, procedurile catalogate definite pe o bază de date (de exemplu MatBase), nu puteau fi apelate și executate pe celalte două baze de date cu care se lucra.
De aceea am apelat la soluția generării unui fișier script sql, care, în momentul apelării sub-sistemului de import, creează atât pe baza sursă cât și pe cea destinație un set de proceduri catalogate, necesare algoritmului de import, care, după efectuarea importului sau în caz de eroare, sunt șterse și din baza sursă și din cea destinație. Odată create procedurile, am recurs la simularea menținerii în permanență a celor trei conexiuni necesare, prin închiderea și deschiderea fiecărei conexiuni în parte, în funcție de necesitatea utilizării uneia dintre ele.
Soluția alternativă (însă mult mai ineficientă) ar fi fost utilizarea string-urilor de comandă sql hardcodate în codul C#, lucru care ar fi crescut însă foarte mult timpul de execuție și, în cazul în care ar fi trebuit efectuată vreo modificare a vreunei comnezi, codul ar fi trebuit modificat la fiecare apelare a stringului de comandă. Această soluție a fost totuși aplicată acolo unde nu exista altă variantă (spre exemplu, în cazul în care comanda ce trebuia trimisă către SQL conținea foarte mulți parametrii ce variau în funcție de un număr foarte mare de condiții ce trebuiau determinate în C#).
O altă dificultate întâmpinată pe parcursul implementării sub-sistemului de import a constat în nepotrivirea dintre tipurile de date ale SQL Server-ului și cele ale .NET C#. Deoarece C# nu recunoaște tipuri de date existente în SQL Server precum binary, varbinary sau image, transferul de date fiind realizat prin intermediul unei clase generice a C# denumită object, datele provenite din tabelele importate care aparțineau unuia din cele trei tipuri menționate mai sus au trebuit citite octet cu octet și memorate în vectori de octeți la nivelul C#, după care convertite în format hexa, reconcatenate ca șir de caractere precedat de identificatorul “0x” și trimise înapoi către SQL pentru a fi inserate în baza destinație.
Acesta este unul din cazurile în care nu s-au putut folosi proceduri catalogate, deoarece, de cele mai multe ori, dimensiunea șirului de caractere depășea dimensiunea maximă admisă de SQL pentru o variabilă de tip șir de caractere (8000 de caractere) și deci acea valoare nu putea fi trimisă ca parametru pentru o procedură catalogată. Astfel, pentru a putea introduce un baza de date o înregistrare ce conține o astfel de valoare, am apelat la executarea în mod direct a întregului șir de caractere folosind instrucțiunea T-SQL “EXEC()”.
În fine, există și o problemă pentru care nu am găsit încă nici o soluție: tabelele sistem generate de către SQL Server pentru orice bază de date, deși au fost importate în mod corect din punct de vedere al datelor, iar algoritmii de conversie R-R și R-M nu modifică deloc structura acestora, își pierd din “atribuțiile” de tabelă sistem (spre exemplu, tabela sysdiagrams în care se memorează marea majoritate a datelor legate de diagramele create de către utilizator, o dată ce a fost importată, nu mai poate reface diagramele ce au fost salvate pe baza destinație, însă în cazul în care se dorește realizarea unei noi diagrame prin intermediul strict al SQL Server-ului, acest lucru ramâne posibil).
Din fericire, această problemă este minoră, întru-cât diagramele sunt generabile automat de către SQL Server, iar MatBase oricum generează DE-A echivalente.
O altă problemă întâmpinată pe parcursul dezvoltării a fost aceea că algoritmii de import, mai ales R-R, modifică structura bazei de date, în special a tabelelor, în mod considerabil, iar SQL Server-ul nu detine, în multe cazuri, instructiunile necesare modificarilor. Un exemplu ar fi înlaturarea constrângerii NOT NULL de pe o coloană a unei tabele, deoarece nu exista posibilitatea de a înlătura aceasta constrângere cu ajutorul unui querry SQL.
Problema mentionata mai sus, împreună cu problema conexiunilor simultane și cu faptul că SQL Server-ul nu permite crearea de tabele care să nu contină nici o coloană (acest lucru ar fi fost necesar datorită caracterului general al creării tabelelor în Import provenit din faptul că la momentul creării unei tabele pe baza destinatie, aceasta poate avea sau nu o cheie primara generata de catre algoritm) au dus la renuntarea la lucrul permanent cu baza de date. Astfel am creat o structură interna la nivelul C# formată din patru obiecte de tip DataTable. Obiectele de acest tip sunt un echivalent al tabelelor SQL care permit parcurgeri, căutări, adăugari și ștergeri de rânduri (înregistrări), modificări în cadrul înregistrărilor deja existente, etc…
Despre structura internă vom discuta mai pe larg în secțiunea 3.
3. Ghid utilizare sub-sistem import relațional MatBase
Sub-sistemul de import MatBase poate fi apelat pentru orice bază de date, de tip MatBase sau nu, fie ea nou creată sau deja existentă, fie că are sau nu tabele deja create, proceduri catalogate, diagrame definite de utilizator etc. Desigur că interesant este doar cazul bdr non-MatBase (pentru că în cazul celor deja gestionate de MatBase au loc pure copieri, fără nici o traducere din MRD în MMED și MEA).
Sub-sistemul de import poate fi apelat de către utilizatori din meniul Tools, selectând opțiunea Import Data. În fig. 3.1 este prezentată fereastra principală a meniului de import.
După cum se poate observa, în antetul ferestrei principale este specificată destinația importului, adică baza de date curentă (în figură: Server = HERA\VLAD; Database = TestImport), iar în cele două combobox-uri din fereastra de import utilizatorul poate alege orice bază de date aflată pe oricare server activ din rețea drept sursă a importului. În cazul figurii, testul de import este făcut chiar din meta-catalogul MatBase (Server: HERA\VLAD; Database: MatBase).
Se mai pot remarca în partea inferioară a ferestrei de import cele două butoane denumite „Copy all database” și „Select Objects”. Aceste butoane permit utilizatorului să aleagă între a importa întreaga bază de date sursă sau numai anumite tabele ale ei, ce pot fi alese după bunul plac al utilizatorului.
Fig. 3.1: Primul ecran al sub-sistemului de import
În cazul în care utilizatorul alege opțiunea „Select Objects” și apasă butonul „OK” (amplasat în partea din dreapta jos a ferestrei) se deschide o nouă fereastră cu două câmpuri, care permite alegerea tabelelor dorite. Figura 3.2 prezintă această fereastră, pentru un exemplu în care baza de date sursă este baza sistem master a SQL Server-ului, iar baza de date destinație este o bază de tip MatBase, denumită TestImport.
Fig. 3.2: Al doilea ecran al sub-sistemului de import
În câmpul din stânga, utilizatorul primește lista cu toate tabelele din baza de date sursă. Selectând una dintre tabele, butonul “>>” devine activ și, prin apasarea acestuia, tabela selectată trece în câmpul din partea dreaptă denumit “Selected Objects”, dispărând totodată din lista din partea stângă. Dacă utilizatorul dorește să renunțe la unul din obiectele pe care le-a ales, poate selecta obiectul respectiv în câmpul “Selected Objects” și în acest moment butonul “<<” devine activ. Prin apăsarea butonului “<<” tabela selectată este ștearsă din lista “Selected Objects” și reintrodusă în lista “All Tables” (cea din partea stângă).
Dacă utilizatorul dorește schimbarea bazei de date sau a serverului sursă sau pur și simplu dorește revenirea la fereastra principală de import, poate folosi butonul “Back”. În cazul în care se dorește anularea importului, utilizatorul poate folosi butonul “Cancel”. Dacă se dorește începerea importului cu tabelele selectate, butonul „OK” va lansa în execuție algoritmii sub-sistemul de import.
Trebuie menționat că, în ambele cazuri, butonul „OK” nu devine activ decât în momentul în care utilizatorul a completat toate celelalte câmpuri disponibile în fereastră.
Prima etapă a importului este apelarea algoritmului R-R, care începe prin a creea structura internă formată din cele patru DataTable-uri despre care am menționat în secțiunea 2.3. Aceste DataTable-uri sunt: “dtFKOrder” ce conține două coloane: Level care este de tip întreg, și în care se stochează nivelul pe care se află tabela respectivă din punct de vedere al parcurgerii cheilor străine în ordine inversă și TableName care este de tip string și în care se memorează numele tabelei de pe nivelul curent; “dtTables” ce conține coloanele: TableName de tip string cu numele tabelelor, ColumnName tot de tip string cu numele coloanelor fiecărei tabele și o serie de coloane de tip boolean în care se înregistrează diferitele caracteristici ale coloanelor astfel: PrimaryKey este 1 (true) pentru coloanele cheie primară, ForeignKey este 1 pentru toate coloanele care sunt cheie străină în alte tabele, PrimaryKeyChanged este 1 pentru toate coloanele care au fost chei primare în baza inițială, dar, nesatisfăcând standardele MatBase, au fost retrogradate la statutul de cheie, Deleted este 1 pentru coloanele care au fost șterse, AutoNumber este 1 pentru coloanele de tip int autoincrement, Attribute este 1 pentru coloanele care nu sunt chei straine în alte tabele, NotNull este 1 pentru coloanele care nu accepta null, Unique este 1 pentru coloanele pe care este definit un index unic, NewColumn este 1 dacă coloana a fost creată pe parcursul algoritmului și UserNotNull care devine 1 dacă utilizatorul alege ca acea coloană să nu accepte null; “dtAllIndexesPerColumn” ce conține coloanele: TableName în care se stochează numele tabelei pe care e definit indexul, IndexName este numele indexului, IndekKeys conține numele coloanelor care compun indexul, IndexDescr conține informații despre fiecare index (dacă este unic, dacă este cheie primară, etc…), IndexSize conține dimensiunea indexului și Deleted care este 1 dacă indexul a fost șters; cel de-al patrulea DataTable este “dtAllForeignKeys” care conține coloanele: PKTableName care memorează numele tabelei părinte, PKColumnName este numele coloanei părinte, FKTabelName este numele tabelei care referă (copil), FKColumnName este coloana copil, FKName este numele cheii străine, Deleted este 1 dacă, în urma prelucrărilor, cheia a fost ștearsă, iar NewForeignKey este 1 dacă, deși pe baza sursa această cheie nu exista, a fost generată de algoritm.
Aceste patru DataTable-uri sunt generate cu ajutorul a patru proceduri stocate care interoghează tabelele sistem ale SQLServer-ului (care de la versiunea 2005 au fost trensformate în view-uri) sys.objects, sys.indexes, sys.keys.
După ce au fost executate cele patru proceduri și, astfel, cele patru DataTable-uri au fost umplute cu informații, se trece la executarea celor patru pași ai algoritmului R-R, toate prelucrările asupra tabelelor, coloanelor și cheilor fiind facute la nivelul DataTable-urilor.
De menționat că la pasul patru, unde se impune ca orice tabelă să conțină cel puțin o coloană care să nu accepte null, în cazul în care tabela curentă nu conține nici o coloană not null cu excepția cheii primare, algoritmul caută în coloanele tabelei dacă nu există o coloană care, deși admite nuluri, nu conține nicio înregistrare nulă și în cazul în care găsește o astfel de coloană setează automat condiția de not null pe coloana respectivă. Totuși, dacă nu există nicio coloană cu proprietățile mai sus menționate, se deschide o fereastră către utilizator în care acesta este întrebat care dintre coloane va deveni not null. După ce utilizatorul alege o coloană, în dreptul acesteia la nivelul tabelei interne “dtTables” bitul de pe coloana UserNotNull este setat cu 1.
După încheierea execuției celor patru pași ai algoritmului R-R se trece la implementarea fizică a modificărilor pe baza de date destinație astfel: Se creează întâi toate tabelele cu cheile primare pe baza destinație conform informațiilor din “dtTables”. Apoi, conform informațiilor din “dtAllIndexesPerColumn” se creează indecșii pe fiecare tabelă. După aceea, se copiază datele din tabela sursă în tabela destinație. Dacă există rânduri identice din punct de vedere al înregistrărilor care nu satisfac conditiile uneia din cheile unice create de algoritm, atunci tabelei respective i se va mai adăuga o coloană de tip întreg, ce va face și ea parte din cheia mai sus menționată, și care va genera valori distincte pentru înregistrările identice. Dacă există o coloană pe care utilizatorul a marcat-o ca fiind nenulă, deși aceasta nu avea inițial această constrângere și conținea înregistrâri nule, se caută dacă coloana nu avea setată o valoare implicită. În cazul în care se găsește această valoare, toate înregistrările nule capata valoarea implicită; dacă nu există o astfel de valoare, se deschide o nouă fereastră către utilizator, în care acesta este întrebat cu ce valoare dorește să înlocuiască înregistrările nule. În cele din urmă, după ce toate datele au fost copiate, se trece la creerea cheilor străine. Și aici trebuie menționat cazul în care există în tabelă înregistrări care nu satisfac conditiile cheii străine: pentru fiecare tabelă care conține astfel de înregistrări, se creează o nouă tabelă, cu structură identică cu cea originală, dar fără chei, și care poartă numele tabelei originale la care se adaugă denumirea “_Err_” și numele cheii care a generat eroarea, în care se țin minte înregistrările ce nu corespund cerințelor cheii străine, iar utilizatorului îi este afișat pe ecran un mesaj de avertizare. De exemplu, pentru tabela denumita “Products” care conține înregistrări ce nu satisfac cheia “FK_Orders_OrderDetails” se va genera tabela “Products_Err_ FK_Orders_OrderDetails”.
Dacă algoritmul R-R a fost executat cu succes, se trece la executarea algoritmului R-M, care, practic, nu face decât să înregistreze în tabelele sistem ale Meta-catalogului MatBase noile obiecte obținute în urma importului. De exemplu, tabelele sunt înregistrate ca entități în cadrul modelului matematic, coloanele devin atribute în cazul în care nu sunt chei străine, cheile străine devin funcții structurale, cheile compuse devin mimimal injectivități, etc…
În cele din urmă, dacă ambii algoritmi au fost executați cu succes, aplicația șterge procedurile stocate pe care le-a folosit pe parcursul importului atât de pe baza sursă cat si de pe cea destinație.
4. Exemple de import relațional MatBase
Implementarea sub-sistemului de import relațional al MatBase a fost testată cu mai multe bdr. Am ales pentru ilustrare trei dintre ele, datorită faptului că două se situează la poluri opuse (meta-catalogul Access 2003, care este extrem de simplu și sărac în detalii de proiectare și cel al MatBase însuși, care este nu doar complex, ci și aproape exhaustiv în ceea ce privește proiectarea matematică riguroasă), iar al treilea (bdr Northwind, furnizată de Microsoft drept exemplu) situat între primele două.
4.1 Meta-catalogul MS Access 2003
Orice bd Access (chiar și vidă) conține un meta-catalog format, până la versiunea 2003 inclusiv, din următoarele 5 tabele: MSysAccessObjects (conținând date despre memorarea proiectelor Access), MSysACEs (conținând date de securitate despre drepturile grupurilor și utilizatorilor asupra obiectelor Access), MSysObjects (conținând date despre schema meta-catalogului și a bd utilizator: tabele, coloane, chei, interogări etc.), MSysQueries (conținând detalii despre subexpresiile interogărilor) și MsysRelationships (conținând date despre legăturile între tabele via chei străine). Figura 4.1 le prezintă pe cele 4 accesibile (minus MSysACEs, pentru care utilizatorii nu au nici măcar drept de citire).
Fig. 4.1: Diagrama relațiilor între tabelele permanente ale meta-catalogului Access
Alte tabele se adaugă meta-catalogului pe măsură ce este nevoie de ele (precum, de exemplu, MSysAccessXML și MSysMacros).
Evident că singurele două tabele interesante din punct de vedere al temei acestei lucrări sunt MSysObjects și MSysRelationships. Inițial, prima conține 17 linii (corespunzând celor 5 tabele ale meta-catalogului, mulțimilor de tabele, relații între ele, forme, module, pagini web etc.), iar ce de-a doua e vidă (un prim semn că proiectarea meta-catalogului e deficitară: în mod surprinzător, nici o relație nu este definită între cele 5 tabele ale sale).
Fig. 4.2: Instanța inițială a tabelei MSysObjects
Fig. 4.3: Instanța inițială a tabelei MSysRelationships
Pentru primul test, am adăugat acestei bd două tabele, T1 (cu cheia T1) și T2 (cu cheia T1 T2 și cheia străină T1), conform figurii 4.4, plus o interogare Q1.
Fig. 4.4: Structura și relațiile tabelelor de test T1 și T2
Instanța tabelei MSysObjects s-a îmbogățit cu 6 linii (vezi figura 4.5), câte una pentru fiecare tabelă, interogare, relație între T1 și T2, utilizatorului Admin și tabelei sistem MsysAccessXML. Figura 7 prezintă noua instanță a tabelei MSysRelationships, care acum conține o linie corespunzătoare relației între T2 și T1 indusă de cheia străină T2.T1.
Aplicând algoritmul R-R, lui MSysObjects i-ar fi aduse doar două modificări: Name devine singura coloană semantică ce nu admite nuluri și i se adaugă cheia semantică Connect Database DateCreate DateUpdate Flags ForeignName Lv LvExtra LvModule LvProp Name Owner ParentID RmtInfoLong RmtInfoShort Type. Lui MsysRelationships, pe lângă interzicerea nulurilor pentru szRelationship (pentru că valorile sale constituie singurul mod de legare la MSysObjects, cu valorile din coloana Name!), i s-ar adăuga o cheie primară surogat auto-number #MSysRelationships și cheia semantică ccolumn grbit icolumn szColumn szObject szReferencedColumn syReferencedObject szRelationship.
Fig. 4.5: Instanța tabelei MSysObjects după adăugarea tabelor și interogării de test
Fig. 4.6: Instanța tabelei MSysRelationships după adăugarea tabelor de test și a legăturii între ele
Algoritmul R-M n-ar mai avea însă rost să fie aplicat, deoarece, pentru nici o tabelă, fie ea sistem ori utilizator, nu avem acces la meta-datele privind coloanele și cheile sale; acestea sunt memorate în tabelele MSysColumns și MSysIndexes, ambele complet ascunse. Se observă însă că, mai mult, chiar dacă am avea acces și la aceste tabele, informațiile pe care le poate furniza MMED asupra meta-catalogului ar fi, datorita precarității proiectării acestuia, foarte puține. Numai din instanța acestuia putem, din păcate, deduce că, de exemplu, szRelationship este o funcție structurală definită pe MSysRelationships și cu valori în MSysObjects sau că ParentID este tot o funcție structurală, definită pe și cu valori în MSysObjects.
Algoritmul R-ER ar avea, sintactic, rost să fie aplicat doar pentru bd utilizator de test, pentru care ar fi capabil să producă DE-A structurală (i.e. fără elipse) a T1, T2 și funcției structurale T2.T1 (fără putința însă de a ști dacă aceasta este sau nu injectivă); semantic însă, desigur, aceasta nu ar avea rost, deoarece nu ar putea oferi nici măcar toate informațiile oferite de utilitarul Access Relationships (vezi figura 5).
În concluzie, este evident faptul că, în general, dacă schema unei bd este săracă, R-R, R-M și R-ER vor putea produce doar o schemă matematică corespunzătoare la fel de săracă; în general, desigur, ele nu pot deduce nimic în plus, căci nu se ocupă nici de investigarea instanțelor de date (data mining), decât în măsura strict necesară „normalizării” lor conform standardelor MatBase și nici de investigarea codului aplicațiilor construite peste bd (care uneori implementează constrângeri suplimentare celor declarate în schema bd).
Pe scurt, R-R, R-M și R-ER sunt utile doar pentru bd a căror schemă e bogată (de preferință foarte complexă), chiar dacă ea este greșit proiectată; pentru schemele sărace, rezultatul aplicării lor trebuie investigat în adânc și completat manual de o manieră consistentă.
4.2 Baza de date MS Northwind SQL Server 2005
Microsoft furnizează drept exemplu, atât în Access, cât și în SQL Server și o bdr numită Northwind. Din păcate, de foarte multe ori, ea este de fapt mai degrabă un contra-exemplu de proiectare a bdr, deci o foarte bună alegere pentru ilustrarea puterii și testarea implementării algoritmilor de import relaționali ai MatBase.
4.3 Meta-catalogul MatBase (versiunile MS SQL Server 2008/2005/2000)
La celălalt capăt al spectrului de teste posibile, am ales, datorită complexității și bogăției sale, importul meta-catalogului MatBase (în versiunea sa .NET C#, XML, SQL Server), cu ajutorul căruia am și testat în profunzime și aproape exhaustiv implementarea algoritmilor sub-sistemului de import al MatBase.
Așa cum era de așteptat (deoarece și meta-catalogul a fost proiectat și implementat folosind chiar MatBase), algoritmul R-R a produs o bd identică cu meta-catalogul, fără a găsi nici o eroare de proiectare sau implementare și nici vreo posibilă optimizare: aceasta demonstrează că, la nivel relațional cel puțin, acesta se supune 100% standardelor MatBase în materie.
Mai mult, algoritmul R-M a produs la rândul său exact același model matematic pe care îl produce sub-sistemul de export MatBase: aceasta demonstrează desigur faptul că cele două sub-sisteme (de import și export) sunt exact inverse unul altuia.
Anexa 1 prezintă modelul MMED al meta-catalogului MatBase obținut prin exportarea rezultatului importării sale. Deoarece exportul grafic, al diagramelor entități-asociații, nu funcționează încă în MatBase, rezultatul aplicării algoritmului R-ER asupra meta-catalogului nu a putut fi comparat cu cel al exportului corespunzător.
Concluzii
MatBase este un SGBDC foarte puternic, unic în lume, oferind proiectanților și utilizatorilor de bd, bc și aplicații asupra acestora posibilitatea de a folosi concomitent patru modele ale datelor, dintre care MMED furnizează rigoarea matematică și putința încorporării în schemele bd a unor constrângeri ce apar extrem de uzual în practică, dar pe care nici un alt model, deci SGBD nu le oferă (în schimb MatBase generează automat cod pentru impunerea lor), MLD puterea expresivă formidabilă a Datalog (care, de exemplu, permite calculul închiderilor tranzitive cu câte un progrămel de două linii), MEA puterea sugestivă impresionantă a diagramelor, iar MRD eficiența memorării, actualizării și interogării instanțelor bd.
Importul bdr în MatBase permite atât recuperarea aproape instantanee a schemelor și instanțelor de bd proiectate și utilizate anterior cu ajutorul principalelor SGBDR existente pe piață, analiza schemei lor, corectarea eventualelor erori de proiectare, optimizarea atât a spațiului disc ocupat, cât și a vitezei de interogare și actualizare a instanțelor corespunzătoare (pe scurt: ridicarea lor la standardele MatBase în domeniu), precum și decriptarea, atât matematică, cât și vizuală (prin intermediul DE-A generate) a semanticii bdr importate; în plus, desigur, bdr importate pot fi ulterior modificate și/sau extinse, atât din punct de vedere al schemelor, cât și al instanțelor lor, folosind orice combinație a celor patru modele de date, precum și generatorul automat de cod pentru impunerea constrângerilor matematice non-relaționale oferite de MMED și MatBase.
Principalele limitări ale implementării prezentate în lucrare sunt tipul bdr ce pot fi importate (doar cele gestionate de MS SQL Server), precum și informațiile considerate (doar schema și instanțele tabelelor). Îmi propun ca la studiile Master să continui munca în ambele aceste două direcții: importul și din Oracle, IBM DB/2, MS Access etc., dar și, ortogonal, pe cel al view-urilor, procedurilor catalogate (ambele trebuind, evident, modificate și ele automat nu doar din punctul de vedere al diferențelor sintactice între SQL-urile respective, ci și din cel al modificărilor făcute automat în schemele importate pentru a le ridica la standardele MatBase), drepturilor de acces ale utilizatorilor etc.
Mulțumiri
Sunt îndatorat coordonatorului științific al proiectului de diplomă, Domnul Profesor universitar Doctor Mircea Petrescu, pentru a fi acceptat să mă ghideze, pentru răbdarea, efortul și energia cu care s-a implicat, pentru rigoarea și clarviziunea ce mi le-a insuflat drept standarde.
Mulțumesc Doamnei Simona Mancaș, matematician-informatician MSc, doctorand, care, pe lângă detalii privind teoria MMED, a MatBase și a SQL, mi-a furnizat și nenumărate detalii tehnologice despre MS SQL Server, T-SQL, C# și .NET Framework.
Mulțumesc Domnului conferențiar universitar doctor Christian Mancaș pentru viziunea de ansamblu oferită asupra MMED și MatBase, pentru bibliografia pusă la dispoziție, dar și pentru numeroase detalii asupra algoritmilor de import relațional în MatBase.
Bibliografie
Anexa: Schema MMED a meta-catalogului MatBase
MatBase Database EMDM Scheme by Categories
Generated automatically by MATBASE
at 06/10/2006 16:21:51.8906250
Copyright S.C DATASIS ProSoft S.R.L, 1985 – 2008
1.SETS
SETS (The set of set names in MatBase managed databases; some names are synonyms of others. Sets are either C-Computed Sets, or E-Entities,N-Void Set, R-Relationships, V-Values. Relationships can be viewed as such, or as entity sets depending on Relationship?.)
#S –> NAT total injective (SETS obid.)
SetName –> CHAR(255) total (The set name.)
SetType –> {‘E’,’R’,‘V’,’N’} total (The set type abbreviation.)
*card –> NAT total (The set cardinal.)
*card = COUNT(*)
Relationship? –> BOOL total (True if user wishes to display the relationship as a relationship, false if wishes it to be equivalently displayed as an entity set (with the canonical cartesian projections as explicit structural functions).)
SetSemantics –> CHAR(900) (The set description.)
SetCategOrdinal –> RAT total (Set ordinal number within its set category.)
ObjectId : SETS –> FUNCTIONS (The corresponding obid.)
FactPredicate : SETS <–> PREDICATES total injective (The corresponding factual predicate.)
Synonym : SETS <–> SETS injective (The set to wich the current set is a synonym.)
Database : SETS –> DATABASES total (The database to which the sets belongs.)
SetCategory : SETS –> SetsCategories total (Set category.)
key: SetName • Database (Set names should be unique within any database.)
key: SetCategory • SetCategOrdinal (For any set category the corresponding set ordinal should be unique.)
(for all x in SETS)(SetType(x) = 'C' v (SetType(x) = 'R' v (SetType(x) = 'E' v (SetType(x) = 'V' v SetType(x) = 'N')))) (Set types should be either C(Computed), E(Entitiy), N(Empty Set), R(Relationship), or V(Value).)
(for all x in SETS)(Codomain(ObjectId(x) included in Nat(256)) (Every object identifier has the naturals as its codomain.)
SETS = EMPTY + *VALUES + *OBJECTS (MatBase sets are either of values, or of objects, or the empty set.)
*SETS – {EMPTY} (The collection of not empty sets.)
Definition: *SETS – {EMPTY} = SETS – {EMPTY}
*VALUES (The collection of values sets.)
Definition: *VALUES = SETS|Im(SetType) = {'V'}
*ENTITIES (The collection of entities sets.)
Definition: *ENTITIES = SETS|Im(SetType) = {'E'}
RELATIONSHIPS (The set of binary non-functional relationships. Subset of SETS.)
#R –> SETS total injective (RELATIONSHIPS obid.)
Acyclic –> BOOL total surjective (True if relationship is acyclic, false otherwise.)
Symmetric –> BOOL total (True if relationship is symmetric, false otherwise.)
Antisymmetric –> BOOL total (True if relationship is antisymmetric, false otherwise.)
Transitive –> BOOL total (True if relationship is transitive, false otherwise.)
Reflexive –> BOOL total (True if relationship is reflexive, false otherwise.)
*OBJECTS (The collection of objects sets.)
Definition: *OBJECTS = ENTITIES + RELATIONSHIPS
*SETS (The set of computed sets and their definitions. Subset of SETS.)
#S <–> SETS total injective (*SETS obid.)
*SetDef <–> EXPRESSIONS total injective (The expression defining the computed set.)
key: *SetDef (No computed set definition should be stored more than once.)
2.MAPPINGS
FUNCTIONS (The set of MatBase managed functions (be them attributes, structural, or computed) names (renaming is needed for Datalog¬ programs and SQL queries).)
#F –> NAT total injective (FUNCTIONS obid.)
FunctionName –> CHAR(255) total (The function name.)
Attribute –> NAT total injective (True if function is an attribute, false if it is a structural one.)
Injective –> BOOL total (True if function is injective, false otherwise.)
Total –> BOOL total (True if function is total, false otherwise.)
Projection? –> BOOL total (True if the function is a canonical Cartesian projection; false otherwise.)
Acyclic –> BOOL total injective (True if function is acyclic, false otherwise.)
Idempotent –> BOOL total (True if function is idempotent, false otherwise.)
Surjective –> BOOL total (True if function is surjective, false otherwise.)
Reflexive –> BOOL total (True if function is reflexive, false otherwise.)
Transitive –> BOOL total (True if function is transitive, false otherwise.)
Symmetric –> BOOL total (True if function is symmetric, false otherwise.)
Antisymmetric –> BOOL total injective (True if function is antisymmetric, false otherwise.)
DomConstr –> NAT total injective (For string attributes, stores maximum allowed string length.)
Position –> NAT total injective (The position of the function within its object type.)
FunctionSemantics –> CHAR(900) (The function description.)
*Im : FUNCTIONS –> SETS (Image function.)
*Im = {y/exist x in D, f(x)=y}
Domain : FUNCTIONS –> SETS total (The domain set.)
Codomain : FUNCTIONS –> SETS total (The codomain set.)
DefaultValue : FUNCTIONS –> CONSTANTS (The constant which is the function default value.)
Renaming : FUNCTIONS –> FUNCTIONS (The renamed function.)
key: FunctionName • Domain (For any domain there may not be two or more functions having same name defined on it.)
key: Domain • Position (No two functions may occupy same position within their object type.)
(for all x in FUNCTIONS)(DomConstr(x) > 0) (Values of any functions need at least one bit of storage.)
*ATTRIBUTES (The set of attributes.)
Definition: *ATTRIBUTES = FUNCTIONS|Codomain(ATTRIBUTES) in VALUES
*STRUCT_FUNCTS (The set of structural functions.)
Definition: *STRUCT_FUNCTS = FUNCTIONS – ATTRIBUTES
*COMP_FUNCT (The set of pairs <f,g> where f is a composite function whose definition includes g.)
Definition: *COMP_FUNCT = COMP_FUNCT in FUNCTIONS
*COMP_FUNCT in FUNCTIONS (Composite functions are functions.)
*FUNCTIONS (The set of computed functions and their definitions. Subset of FUNCTIONS.)
#F <–> FUNCTIONS total injective (*FUNCTIONS obid.)
*FunctionDef <–> EXPRESSIONS total injective (The expression defining the computed function.)
key: *FunctionDef (No computed function definition should be stored more than once.)
3.CONSTRAINTS
ConstraintTypes (The set of MatBase constraint types.)
#CT –> NAT total injective (ConstraintTypes obid.)
CType <–> CHAR(4) total injective (Constraint type abbreviation.)
ConstraintType <–> CHAR(4) total injective (Constraint type description.)
ConstraintCategory : ConstraintTypes –> CONSTRAINT_CATEGS total (The constraint category.)
key: CType (No two constraint types may have same abbreviation.)
key: ConstraintType (No two constraint types may have same descriptions.)
CONSTRAINT_CATEGS (The set of constraint categories.)
#CC –> NAT total injective (CONSTRAINT_CATEGS obid.)
CCateg <–> CHAR(1) total injective (The constraint category abbreviation.)
CCategory <–> CHAR(64) total injective (The constraint category description.)
key: CCategory (Constraint category descriptions should be unique.)
key: CCateg (Constraint category abbreviations should be unique.)
CONSTRAINTS (The set of all constraints in MatBase managed databases.)
#C –> NAT total injective (CONSTRAINTS obid.)
ConstraintName –> CHAR(450) total (The constraint name.)
ConstraintText <–> CHAR(1800) total injective (The constraint formula description.)
ConstraintSemantics –> CHAR(900) (The constraint description.)
ConstraintRDNo –> CHAR(8) (The requirement number in the document.)
ConstraintReqDocPgNo –> CHAR(8) total (The number page of the document where the constraint appears.)
ConstraintType : CONSTRAINTS –> ConstraintTypes total (The constraint type.)
ConstraintFormula : CONSTRAINTS –> FORMULAS (The constraint formula.)
Database : CONSTRAINTS –> DATABASES total (The database to which the constraint belongs.)
ConstraintReqDoc : CONSTRAINTS –> REQ_DOCS total (The requierement document from which the constraint has been abstracted and formalized.)
key: ConstraintName • Database (There may be several constraints with same name in different databases, but no two constraints may have same name in a same database.)
key: ConstraintReqDoc • ConstraintRDNo • ConstraintReqDocPgNo (No constraint requierement should be abstracted more than once.)
CONSTRAINTS = INCLUSIONS + SET_EQUALITIES +*MIN_INJECTIVS + FUNCT_EQUALS + EXIST_CNSTRS + DISJUNCTIONS + DIRECT_SUMS + REPRES_SYSTS +* DOM_CNSTRS + *OBJ_CNSTRS + UNIONS + *SURJECTIVITIES + *INJECTIVITIES + *REFLEXIVITIES + *SYMMETRIES + *ANTISYMMETRIES + *TRANSITIVITIES + *ACYCLICITIES (Constraints are only and all of the 18 MatBase type ones.)
INCLUSIONS (The set of inclusions constraints. Subset of CONSTRAINTS.)
#I : INCLUSIONS –> CONSTRAINTS total (INCLUSIONS obid.)
*SetType ° Subset –> CHAR(1) (Set type of the included set (needed for C? constraint).)
*SetType ° Subset = *SetType ° Subset
*SetType ° Set –> CHAR(1) (Set type of the including set (needed for C? constraint).)
*SetType ° Set = *SetType ° Set
Subset : INCLUSIONS –> SETS total (The included set.)
Set : INCLUSIONS –> SETS total (The including set.)
structural key: Subset • Set (Rules out storing any inclusion more than once.)
*SetType ° Set = *SetType ° Subset (Inclusions are only alowed within a same set subclass.)
acyclic reflexive INCLUSIONS
Subset(x) ()
Definition: Subset(x) = Im ° Subset(x)
SET_EQUALITIES (The set of set equality constraints. Subset of CONSTRAINTS.)
#SE <–> CONSTRAINTS total injective (SET_EQUALITIES obid.)
*SetType ° RightSet –> CHAR(1) (Set type of the right side equality set (needed for C? constraint).)
*SetType ° RightSet = *SetType ° RightSet
*SetType ° LeftSet –> CHAR(1) (Set type of the left side equality set (needed for C? constraint).)
*SetType ° LeftSet = *SetType ° LeftSet
LeftSet : SET_EQUALITIES –> SETS total (The left set in the set equality.)
RightSet : SET_EQUALITIES –> SETS total (The right set in the set equality.)
structural key: LeftSet • RightSet (Any equality should not be stored more than once.)
*SetType ° LeftSet = *SetType ° RightSet (Set equalities are only alowed within a same set subclass.)
acyclic SET_EQUALITIES
Leftset(x) ()
Definition: Leftset(x) = Im ° Leftset(x)
Rightset(x) ()
Definition: Rightset(x) = Im ° Righttset(x)
*MIN_INJECTIVS (The set of minimal injectivities.)
Definition: *MIN_INJECTIVS = CONSTRAINTS|Im(ConstraintType) = {'MI'}
MIN_INJ_COMP (The set of triples <c,f,p> meaning that function f is member of minimal injectivity c in position p.)
#MIC –> NAT total injective (MIN_INJ_COMP obid.)
Position –> NAT total (The position of the function wihin the key constraint.)
MinInject : MIN_INJ_COMP –> CONSTRAINTS total (The key constraint to which the function belongs.)
MFunction : MIN_INJ_COMP –> FUNCTIONS total (The function included in the minimal injectivity.)
structural key: MinInject • MFunction (Rules out storing more than once same function in same minimal injectivity.)
key: MinInject • Position (Rules out storing in any position of a minimal injectivity more than one function.)
(for all x in MIN_INJ_COMP)(Position(x) > 0) (Position of any function within a minimal injectivity should be strictly positive.)
acyclic MIN_INJ_COMP
FUNCT_EQUALS (The set of function equality constraints. Subset of CONSTRAINTS.)
#FE <–> CONSTRAINTS total injective (FUNCT_EQUALS obid.)
LeftFunct : FUNCT_EQUALS –> FUNCTIONS total (The left function in the equality.)
RightFunct : FUNCT_EQUALS –> FUNCTIONS total (The right function in the equality.)
structural key: LeftFunct • RightFunct (Rules out storing twice same function equality.)
acyclic FUNCT_EQUALS
Domain(x) ()
Definition: Domain(x) = Im ° Domain(x)
Codomain(x) ()
Definition: Codomain(x) = Im ° Codomain(x)
EXIST_CNSTRS (The set of existence constraints. Subset of CONSTRAINTS.)
#C <–> CONSTRAINTS total injective (EXIST_CNSTRS obid.)
ECLeftSide : EXIST_CNSTRS –> FUNCTIONS total (The function to the left of the existence constraint operator.)
ECRightSide : EXIST_CNSTRS –> FUNCTIONS total (The function to the right of the existence constraint operator.)
structural key: ECLeftSide • ECRightSide (Rules out storing twice same existence constraint.)
acyclic EXIST_CNSTRS
Domain(ECLeftSide(x)) ()
Definition: Domain(ECLeftSide(x)) = Im ° Domain (Im ° ECLeftSide(x))
DISJUNCTIONS (The set of disjunctions constraints. Subset of CONSTRAINTS.)
#D <–> CONSTRAINTS total injective (DISJUNCTIONS obid.)
*SetType ° DRightSide –> CHAR(1) (Set type of the right side disjunction set (needed for C43 constraint).)
*SetType ° DRightSide = *SetType ° DRightSide
*SetType ° DLeftSide –> CHAR(1) (Set type of the left side disjunction set (needed for C43 constraint).)
*SetType ° DLeftSide = *SetType ° DLeftSide
DLeftSide • DRightSide : DISJUNCTIONS –> SETS ()
DLeftSide : DISJUNCTIONS –> SETS total (The set left to the intersection operator.)
DRightSide : DISJUNCTIONS –> SETS total (The set right to the intersection operator.)
structural key: DLeftSide • DRightSide (Any disjunction should not be stored more than once.)
*SetType ° DLeftSide = *SetType ° DRightSide (Disjunctions are only alowed within a same set subclass.)
acyclic DISJUNCTIONS
DLeftSide(x) ()
Definition: DLeftSide(x) = Im ° DLeftSide(x)
DRightSide(x) ()
Definition: DRightSide(x) = Im ° DRightSide(x)
DIRECT_SUMS (The set of direct sums constraints; if the same set has several direct sums constraints, then for each one of them except the first one synonyms should be used. Subset of CONSTRAINTS.)
#C <–> CONSTRAINTS total injective (DIRECT_SUMS obid.)
DSLeftSideIndex –> INT total (The index of the current direct sum set definition (there may be several distinct partitions of a same set).)
DSLeftSide <–> SETS total injective (The set defined as a direct sum.)
key: DSLeftSide • DSLeftSideIndex (No set partitioning should be stored more than once (but several different partitionings may be defined for a same set).)
DSLeftSide(x) ()
Definition: DSLeftSide(x) = Im ° DSLeftSide(x)
DIR_SUMS_COMP (The set of pairs <s,m> meaning that set m is included in the left hand set of direct sum constraint s.)
#DSC –> NAT total injective (DIR_SUMS_COMP obid.)
DirectSum : DIR_SUMS_COMP –> DIRECT_SUMS total (The direct sum constraint.)
DSMember : DIR_SUMS_COMP –> SETS total (The set that is a member of the direct sum.)
structural key: DirectSum • DSMember (Enforces unique appearences of each set in the right hand side of any direct sum.)
acyclic DIR_SUMS_COMP
DSMember(x) ()
Definition: DSMember(x) = Im ° DSMember(x)
DSMember(y) ()
Definition: DSMember(y) = Im ° DSMember(y)
REPRES_SYSTS (The set of representative systems constraints. Subset of CONSTRAINTS.)
#C <–> CONSTRAINTS total injective (REPRES_SYSTS obid.)
CanonicalSurjection : REPRES_SYSTS –> FUNCTIONS total (The function which is the canonical surjection of the representative system.)
key: CanonicalSurjection (Rules out storing same canonical surjection more than once (as this whould imply storing same representative system more than once).)
REPRES_SYSTS in FUNCTIONS (Any representative systems may be represented only by its associated canonical surjection.)
*DOM_CNSTRS (The set of domain constraints.)
Definition: *DOM_CNSTRS = CONSTRAINTS|Im(ConstraintType) = {'DC'}
*OBJ_CNSTRS (The set of objects constraints.)
Definition: *OBJ_CNSTRS = CONSTRAINTS|Im(ConstraintType) = {'OC'}
*DOM_OBJ_CNSTR (The union of the domain and object constraints.)
Definition: *DOM_OBJ_CNSTR = *DOM_CNSTRS U *OBJ_CNSTRS
UNIONS (The set of union type constraints.)
#U –> NAT total injective (UNIONS obid.)
UIndex –> NAT total (The index of a set union for distinguishing between several distinct decompositions over same set into set uinons.)
ULeftSide : UNIONS –> SETS total (The set decomposed as a set union.)
key: ULeftSide • UIndex (No union constraint should be stored more than once (but several different unions may be defined for a same set).)
UNIONS_COMP (The set of pairs <u,s>, meaning that set s is a member of union u.)
#UC –> NAT total injective (UNIONS_COMP obid.)
Union : UNIONS_COMP –> UNIONS total (The union constraint canonical projection.)
UMember : UNIONS_COMP –> SETS total (The union member canonical projection.)
key: Union • UMember (No set should be duplicated in a union.)
*INCLUSIONS (The set of inclusions constraints. Subset of CONSTRAINTS.)
Definition: *INCLUSIONS = CONSTRAINTS|Im(ConstraintType) = {'I'}
*SET_EQUALITIES (The set of set equality constraints. Subset of CONSTRAINTS.)
Definition: *SET_EQUALITIES = CONSTRAINTS|Im(ConstraintType) = {'SE'}
*FUNCT_EQUALS (The set of function equality constraints. Subset of CONSTRAINTS.)
Definition: *FUNCT_EQUALS = CONSTRAINTS|Im(ConstraintType) = {'FE'}
*EXIST_CNSTRS (The set of existence constraints. Subset of CONSTRAINTS.)
Definition: *EXIST_CNSTRS = CONSTRAINTS|Im(ConstraintType) = {'EC'}
*DISJUNCTIONS (The set of disjunctions constraints. Subset of CONSTRAINTS.)
Definition: *DISJUNCTIONS = CONSTRAINTS|Im(ConstraintType) = {'D'}
*DIRECT_SUMS (The set of direct sums constraints; if the same set has several direct sums constraints, then for each one of them except the first one synonyms should be used. Subset of CONSTRAINTS.)
Definition: *DIRECT_SUMS = CONSTRAINTS|Im(ConstraintType) = {'DS'}
*REPRES_SYSTS (The set of representative systems constraints. Subset of CONSTRAINTS.)
Definition: *REPRES_SYSTS = CONSTRAINTS|Im(ConstraintType) = {'RS'}
*UNIONS (The set of union type constraints.)
Definition: *UNIONS = CONSTRAINTS|Im(ConstraintType) = {'U'}
*INJECTIVITIES (The subset of one-to-one functions.)
Definition: *INJECTIVITIES = CONSTRAINTS|Im(ConstraintType) = {'FI'}
*SURJECTIVITIES (The subset of onto functions.)
Definition: *SURJECTIVITIES = CONSTRAINTS|Im(ConstraintType) = {'FS'}
*BIJECTIVITIES (The subset of one-to-one and onto functions.)
Definition: *BIJECTIVITIES = *INJEVTIVITIES in *SURJECTIVITIES
*ACYCLICITIES (The subset of acyclic binary relations.)
Definition: *ACYCLICITIES = CONSTRAINTS|Im(ConstraintType) = {'AC'}
*TRANSITIVITIES (The subset of transitive binary relations.)
Definition: *TRANSITIVITIES = CONSTRAINTS|Im(ConstraintType) = {'T'}
*ANTISYMMETRIES (The subset of antisymmetric binary relations.)
Definition: *ANTISYMMETRIES = CONSTRAINTS|Im(ConstraintType) = {'A'}
*SYMMETRIES (The subset of symmetric binary relations.)
Definition: *SYMMETRIES = CONSTRAINTS|Im(ConstraintType) = {'S'}
*REFLEXIVITIES (The subset of reflexive binary relations.)
Definition: *REFLEXIVITIES = CONSTRAINTS|Im(ConstraintType) = {'R'}
OPERATORS (The set of MatBase operators: A-Algebraic, L-Logic, M-Mappings,R-Relational Algebraic, S-Sets Algebraic.)
#AO –> NAT total injective (OPERATORS obid.)
OpSymb <–> CHAR(8) total injective (The operator symbol.)
OpName <–> CHAR(64) total injective (The operator name.)
OpType <–> CHAR(1) total injective (Operator type abbreviation.)
key: OpName (Operator names should be unique.)
key: OpSymb (Operator symbols should be unique.)
(for all x in OPERATORS)(OpType(x) = 'A' v (OpType(x) = 'L' v (OpType(x) = 'R' v (OpType(x) = 'S' v OpType(x) = 'M')))) (Operator types should be either A(Algebraic), L(Logic), M(Mappings), R(Relational algebraic), or S(Set).)
EXPRESSIONS (The (recursive) set of algebraic expressions (either on numbers, or on sets, or functions) used to define constraints, or computed sets and functions. Leaves only have LeftSides equals to their object id.)
#E –> NAT total injective (EXPRESSIONS obid.)
Expression <–> CHAR(900) total injective (Expression formula description.)
Parantheses? –> BOOL total (True if expression is enclosed in parantheses, false otherwise.)
LMinus? : EXPRESSIONS –> BOOL total (True if left subexpression is prefixed by a unary minus, false otherwise.)
LeftExpr : EXPRESSIONS –> EXPRESSIONS total (The expression`s left subexpression.)
AOp : EXPRESSIONS –> *Alg_Ops (The binary algebraic operator infixed between the left and right subexpressions.)
RightExpr : EXPRESSIONS –> EXPRESSIONS (The expression`s right subexpression.)
key: LeftExpr • AOp • RightExpr • LMinus? (Rules out storing a logical expression more than once.)
key: Expression (No expression shoud be stored more than once.)
AOp |- RightExpr (If an expression has a binary algebraic operator, then it should also have a right subexpression.)
RightExpr |- AOp (If an expression has a right subexpression, then it should also have a binary algebraic operator.)
*Alg_Ops (The subset of algebraic operators.)
Definition: *Alg_Ops = OPERATORS|Im(OpType) = {'A'}
TERMS (The set of terms in formulas of type C-Constant, F-Formula, or V-Variable.)
#T <–> EXPRESSIONS total injective (TERMS obid.)
Term <–> CHAR(64) total injective (The term formula description.)
TermType : TERMS –> CHAR total (The term type.)
key: Term (Terms description should be unique.)
(for all x in TERMS)(TermType(x) = 'C' v (TermType(x) = 'F' v TermType(x) = 'V')) (Term types should be either C(Constant), F(Formula), or V(Variable).)
TERMS = VARIABLES + CONSTANTS + FUNCT_CALLS (Terms either variables, constants, or function calls.)
TERMS in EXPRESSIONS (Terms are expressions.)
VARIABLES (The set of variables used in formulas and Datalog¬ programs. Subset of TERMS.)
#T –> TERMS total injective (VARIABLES obid.)
VariableName <–> CHAR(64) total injective (The variable name.)
key: VariableName (Variable names should be unique.)
VARIABLES in TERMS (Variables are terms.)
CONSTANTS (The set of constants of interest for Matbase managed databases. Subset of TERMS.)
#C <–> TERMS total injective (CONSTANTS obid.)
Constant <–> CHAR(64) total injective (Constant description.)
ConstantType –> SETS total (The set which includes the constant.)
key: Constant (No constant should be stored more than once.)
CONSTANTS in TERMS (Constants are terms.)
FUNCT_CALLS (The set of function calls included in logic formulas.)
#T –> TERMS total injective (FUNCT_CALLS obid.)
FunctionCall –> CHAR(255) total (Function call description.)
Function : FUNCT_CALLS –> FUNCTIONS total (The called function.)
structural key: Function • FunctionCall (Rules out storing more than once same function call of same function.)
FUNCT_CALLS in TERMS (Function calls are terms.)
acyclic FUNCT_CALLS
FUNCT_C_V (The set of triples <f,p,v> meaning that in function f variable v is in position p.)
#FCV –> NAT total (FUNCT_C_V obid.)
FCVFunctionCall –> FUNCT_CALLS total (The function call.)
FCVVarPosition –> NAT total (Position of the variable in the function call.)
FCVVariable –> VARIABLES total (The variable used in the function call on current position.)
key: FCVFunctionCall • FCVVarPosition (No two variables may occupy same position within a same function call.)
(for all x in FUNCT_C_V)(FCVVarPosition(x) > 0) (Position of any variable within a function call should be strictly positive.)
FORMULAS (The (recursive) set of logic formulas used to formalize domain and object constraints. Leaves only have LeftSides equals to their object id.)
#F –> NAT total injective (FORMULAS obid.)
FormulaText <–> CHAR(900) total injective (The formula description.)
Negation? –> BOOL total (True if formula is prefixed by a negation operator, false otherwise.)
LeftFormula : FORMULAS –> FORMULAS total (The left subformula.)
LOp : FORMULAS –> *LOps (The binary logical operator infixed between the left and right subexpressions.)
RightFormula : FORMULAS –> FORMULAS (The right subformula.)
key: FormulaText (No formula shoud be stored more than once.)
key: Negation? • LeftFormula • Lop • RightFormula (Rules out storing same logic formula more than once.)
RightFormula |- LOp (If a formula has a binary logic operator, then it should also have a right subformula.)
LOp |- RightFormula (If a formula has a right subformula, then it should also have a binary logic operator.)
*LOps (The subset of logical operators.)
Definition: *LOps = OPERATORS|Im(OpType) = {'L'}
ATOMS (The set of atoms with which make up logic formulas.)
#ATM <–> FORMULAS total injective (ATOMS obid.)
*Atom <–> CHAR(900) total injective (Atom description.)
LeftOp : ATOMS –> ATOMS total (Atom left operand.)
RelOp : ATOMS –> *Std_Ops total (Atom binary relational operator.)
RightOp : ATOMS –> ATOMS total (Atom right operand.)
key: *Atom (No atom should be stored more than once.)
key: LeftOp • RelOp • RightOp (Rules out storing standard algebraic predicates more than once.)
ATOMS in FORMULAS (Atoms are formulas.)
Quantifiers (The set of logic quantifiers (universal and existential).)
#Q –> NAT total injective (Quantifiers obid.)
QSymbol <–> CHAR(8) total injective (The logical quantifier symbol.)
Quantifier –> CHAR(16) total (The logical quantifier description.)
key: QSymbol (Quantifier symbols should be unique.)
key: Quantifier (Quantifier descriptions should be unique.)
ACT_PARAMS (The set of actual parameters for logic formulas in domain and object constraints.)
#AP –> NAT total injective (ACT_PARAMS obid.)
Quantifier : ACT_PARAMS –> Quantifiers total (The quantifier applied to the actual parameter.)
ParamVar : ACT_PARAMS –> VARIABLES total (The variable which is the actual parameter.)
ParamRange : ACT_PARAMS –> SETS total (The set which is the actual paramater range.)
key: ParamRange • ParamVar • Quantifier (Rules out storing any actual parameter more than once.)
FORM_PARAMS (The set of logic formulas formal parameters.)
#FP –> NAT total injective (FORM_PARAMS obid.)
ActualParam : FORM_PARAMS –> ACT_PARAMS total (The actual parameter corresponding to the formal one.)
Formula : FORM_PARAMS –> FORMULAS total (The formula corresponding to the formal parameter.)
structural key: ActualParam • Formula (Forbides using any parameter twice in a predicate instantiation.)
acyclic FORM_PARAMS
SUBSTITUTIONS (The set of variable substitutions in logic formulas.)
#S –> NAT total injective (SUBSTITUTIONS obid.)
OVSubst : SUBSTITUTIONS –> FORM_PARAMS total (The formal parameter which is substituted.)
SVSubst : SUBSTITUTIONS –> VARIABLES total (The variable which is substituting the formal parameter.)
Cnstrnt : SUBSTITUTIONS –> CONSTRAINTS total (The (domain or object) constraint for which the substitution is done.)
structural key: OVSubst • SVSubst (Any substitution is done for one and only one constraint.)
structural key: OVSubst • Cnstrnt (In any constraint, there may be only one substitution for any parameter.)
structural key: Cnstrnt • SVSubst (Rules out using a same variable more than once as an actual parameter in any constraint.)
*Std_Ops (The subset of standard mathematical operators.)
Definition: *Std_Ops = OPERATORS|Im(OpType) = {'S'}
4.DATALOG
PROGRAMS (The set of MatBase managed Datalog¬ programs.)
#P –> NAT total injective (PROGRAMS obid.)
ProgName <–> CHAR(255) total injective (The program name.)
ProgSemantics –> CHAR(900) (The program description.)
*ProgramRAES <–> RA_EQ_SYSTEMS total injective (The relational algebraic equation system corresponding to the Datalog program.)
key: ProgName (Program names should be unique.)
INF_RULES (The set of inference rules which make up Datalog¬ programs.)
#IR –> NAT total injective (INF_RULES obid.)
RuleBody –> CHAR(800) total (The inference rule body formula description.)
InfRuleSemantics –> CHAR(900) (The inference rule description.)
RuleHead : INF_RULES –> PREDICATE_CALLS total (The predicate call which is the rule head.)
*RuleRAEq <–> RA_EQUATIONS total injective (The relational algebraic equation corresponding to the inference rule.)
key: RuleHead • RuleBody (Rules out storing twice a same inference rule.)
PROG_COMP (Datalog¬ programs components: the set of all inference rules per program; note that any program may include any rule only once.)
#PGC –> NAT total injective (PROG_COMP obid.)
Program : PROG_COMP –> PROGRAMS total (The Datalog program including the inference rule.)
InferenceRule : PROG_COMP –> INF_RULES total (The inference rule included by the program.)
structural key: Program • InferenceRule (Rules out storing more than once same inference rule for same program.)
acyclic PROG_COMP
PREDICATES (The set of predicates (be them standard, extensional, or intensional) used in logic formulas and Datalog¬ programs.)
#P –> NAT total injective (PREDICATES obid.)
PredicateName –> CHAR(64) total (The predicate name.)
*Factual? –> BOOL total injective (True if the predicate is factual (extensional), false otherwise (intensional).)
stdPred <–> FORMULAS injective (The formula of the standard predicate (not explicitly defined for set predicates).)
Database : PREDICATES –> DATABASES total (The database to which the predicates belongs.)
key: PredicateName • Database (Predicate names should be unique within any database.)
*EXT_PREDS (The set of Datalog extensional predicates.)
Definition: *EXT_PREDS = Im(FactPredicate)
*EXT_PREDS in PREDICATES (Extensional predicates are predicates.)
*STD_PREDS (The set of standard mathematical Datalog predicates.)
Definition: *STD_PREDS = {x in PREDICATES|StdPred(x) not equal to NULL}
*INT_PREDS (The set of Datalog intensional predicates.)
Definition: *INT_PREDS = PREDICATES – *EXT_PREDS – *STD_PREDS
*INT_PREDS in PREDICATES (Intensional predicates are predicates.)
PREDICATE_CALLS (The set of predicate calls included in logic formulas and Datalog¬ programs.)
#PC –> NAT total injective (PREDICATE_CALLS obid.)
PredicateCall –> CHAR(4) total (The predicate call formula description.)
Predicate : PREDICATE_CALLS –> PREDICATES total (The called predicate.)
key: PredicateCall • Predicate (Rules out storing more than once same predicate call for same predicate.)
INF_R_COMP (Inference rules body components: the set of predicate calls per inference rules.)
#IRC –> NAT total injective (INF_R_COMP obid.)
Negation? –> BOOL total (True if the predicate call is negated, false otherwise.)
PredicateCallPosition –> NAT total (The position of the predicate call within the inference rule.)
InfRule : INF_R_COMP –> INF_RULES total (The inference rule.)
PredicateCall : INF_R_COMP –> PREDICATE_CALLS total (The predicate call included in the inference rule.)
key: InfRule • PredicateCallPosition (Each position in an inference rule may be occupied only by one predicate call.)
(for all x in INF_R_COMP)(PredCallPosition(x) > 0) (Position of any predicate call within an inference rule should be strictly positive.)
acyclic INF_R_COMP
PREDICATE_C_V (The set of triples <p,i,v> meaning that in predicate call p variable v is in position i.)
#PCV –> NAT total injective (PREDICATE_C_V obid.)
PredCVVarPosition –> NAT total (The position of the variable within the predicate call.)
PredCVPred : PREDICATE_C_V –> PREDICATE_CALLS total (The predicate call.)
PredCVVar : PREDICATE_C_V –> VARIABLES total (The variable used in the predicate call.)
key: PredCVPred • PredCVVarPosition (Each Datalog predicate call variable position may hold only one variable.)
(for all x in PREDICATE_C_V)(PredCVVarPosition(x) > 0) (Position of any variable within a predicare call should be strictly positive.)
RA_EQ_SYSTEMS (The set of RA equation systems obtained by syntax-directed translation from Datalog¬ programs.)
#RAES –> NAT total injective (RA_EQ_SYSTEMS obid.)
RAESystemName <–> CHAR(255) total injective (The name of the relation algebra equation system.)
key: RAESystemName (Relational algebraic equation system should be unique.)
RA_EQUATIONS (The set of equations which make up RA equation systems.)
#RAE –> NAT total injective (RA_EQUATIONS obid.)
RaEquation <–> CHAR(900) total injective (The relational algebraic equation (corresponding to some inference rules).)
RaEqLeftSide : RA_EQUATIONS –> PREDICATES total (The predicate in the left side of the relational algebra equation.)
RaEqRightSide : RA_EQUATIONS –> RA_EXPR total (The relational algebraic expression in the right side of the relational algebra equation.)
key: RaEquation (Relational algebraic equation shoud be unique.)
key: RaEqLeftSide • RaEqRightSide (Rules out storing same relational algebraic equation twice.)
RA_ES_COMP (For each equation system, stores the set of composing equations; note that no equation may be stored twice for a same system.)
#RAESC –> NAT total injective (RA_ES_COMP obid.)
RA_EQ_SYSTEMS : RA_ES_COMP –> RA_EQ_SYSTEMS total (The relational algebraic equation system which includes the relational algebraic equation.)
RA_EQUATIONS : RA_ES_COMP –> RA_EQUATIONS total (The relational algebraic equation included in the relational algebraic equation system.)
structural key: RA_EQ_SYSTEMS • RA_EQUATIONS (Rules out storing more than once same relational algebraic equation for same system.)
acyclic RA_ES_COMP
RA_EXPR (The (recursive) set of RA expressions which make up RA equations (corresponding to inference rules). Leaves only have LeftSides equals to their object id.)
#RAEx –> NAT total injective (RA_EXPR obid.)
RAExpresion <–> CHAR(900) total injective (The relational algebraic expression formula description.)
LeftRAExpr : RA_EXPR –> RA_EXPR total (The left relational algebraic subexpression.)
RaBinOp : RA_EXPR –> *RaOps (The binary relation algebraic operator infixed between the left and right subexpressions.)
RightRAExpr : RA_EXPR –> RA_EXPR (The right relational algebraic subexpression.)
sFormula : RA_EXPR –> FORMULAS (The selection formula of the relational algebraic expression (if any).)
Rename : RA_EXPR –> FUNCTIONS (The renaming of the relational algebraic expression (if any).)
Projection : RA_EXPR –> piRA_expr (The projection of the relational algebraic expression (if any).)
key: RAExpresion (Relational algebraic equation expression should be unique.)
key: LeftRAExpr • RaBinOp • RightRAExpr • sFormula • Rename • Projection (Rules out storing expressions more than once.)
RaBinOp |- RightRaExpr (If an expression has a binary relational algebraic operator, then it should also have a right subexpression.)
RightRaExpr |- RaBinOp (If an expression has a right subexpression, then it should also have a binary relational algebraic operator.)
*RaOps (The subset of relational algebraic operators.)
Definition: *RaOps = OPERATORS|Im(OpType) = {'R'}
piRA_expr (The set of projections included in RA expressions.)
piRA –> NAT total injective (piRA_expr obid.)
ProjectionTableIndex –> NAT total (The index of the current projection (there may be several distinct projections on a same table).)
ProjectionTable : piRA_expr –> SETS total (The set on which projection is applied.)
key: ProjectionTable • ProjectionTableIndex (No projection should be stored more than once (but several different projections may be defined for a same table).)
piRA_EXPR_COMP (The set of RA projection list components; note that in any projection, any mapping name may only occur once (that is renamings should be unique).)
piRAEC –> NAT total (piRA_EXPR_COMP obid.)
piRA_EXPR : piRA_EXPR_COMP –> piRA_expr total (The projection relational expression.)
FUNCTIONS : piRA_EXPR_COMP –> FUNCTIONS total (The function on which the projection is made.)
structural key: piRA_EXPR • FUNCTIONS (Rules out storing more than once same function in same projection expression.)
acyclic piRA_EXPR_COMP
5.ER_DIAGRAMS
DIAGRAMS (The set of MatBase E-RDs.)
#D –> NAT total injective (DIAGRAMS obid.)
DiagramName –> CHAR(128) total (The diagram name.)
JpegPath <–> CHAR(900) injective (The path of the jpeg file storing the diagram.)
DiagramSemantics –> CHAR(900) (The diagram description.)
DB : DIAGRAMS –> DATABASES total (The database to which the diagram belongs.)
key: DB • DiagramName (DBMSs don`t accept two or more diagrams having same name in a same database.)
DIAGRAM_O_COMP (The set of pairs <d,o>, meaning that object o is included in E-RD d.)
#DOC –> NAT total injective (DIAGRAM_O_COMP obid.)
Object –> SETS total (The object set included in the diagram as a rectangle or diamond.)
X –> FLOAT injective (The rectangle or diamond center abscissa.)
Y –> FLOAT injective (The rectangle or diamond center ordinate.)
Diagram : DIAGRAM_O_COMP –> DIAGRAMS total (The diagram.)
key: Diagram • Object (No object should be stored more than once in a same diagram.)
acyclic DIAGRAM_O_COMP
DIAGRAM_A_COMP (The set of pairs <d,a>, meaning that arrow a is included in E-RD d.)
#DAC –> NAT total injective (DIAGRAM_A_COMP obid.)
Diagram : DIAGRAM_A_COMP –> DIAGRAMS total (The diagram.)
Arrow : DIAGRAM_A_COMP –> FUNCTIONS total (The function displayed as an arrow in the diagram.)
structural key: Diagram • Arrow on DIAGRAMS_A_COMP (No arrow should be stored more than once in a same diagram.)
acyclic DIAGRAM_A_COMP
6.SYSTEM
EMPTY (The empty set.)
BOOL ({true,false})
NAT (The naturals set.)
INT (The integers set.)
RAT (The rationals set.)
CHAR (The freely generated monoid over the ASCII/UNICODE alphabet.)
DATE (The calendar dates set.)
FLOAT (The set of rationals.)
REQ_DOCS (The set of requirement documents from where constraints are abstracted and formalized.)
#RD –> NAT total injective (REQ_DOCS obid.)
RDCode <–> CHAR(2) total injective (The requierements document abbreviation.)
RDDescription <–> CHAR(900) total injective (The requierements document description.)
key: RDCode ()
key: RDDescription ()
SetsCategories (The collection of set categories.)
#SC –> NAT total injective (SetCategories obid.)
SetCategory <–> CHAR(16) total injective (Set category description.)
DBMSTypes (The set of DBMS manufacturers of interest.)
#M –> NAT total (DBMSTypes obid.)
DBMSType <–> CHAR(32) total injective (DBMS type description.)
key: DBMSType (No DBMS type should be stored more than once.)
DBMSVersions (The set of all DBMS versions of interest.)
#DV –> NAT total (DBMSVersions obid.)
Version –> CHAR(64) total (DBMS version.)
DBMSManufact : DBMSVersions –> DBMSTypes total (DBMS manufacturer name.)
key: DBMSManufact • Version (No DBMS version should be stored more than once.)
SERVERS (The set of DBMSs storing Matbase managed databases.)
#SRV –> NAT total injective (SERVERS obid.)
ServerName <–> CHAR(255) total injective (The server name.)
Active –> BOOL total injective (True if the server is up, false otherwise.)
DBMSVersion : SERVERS –> DBMSVersions total (The version of the server.)
key: ServerName (Server name should be unique.)
DATABASES (The set of all databases managed by MatBase.)
#DB –> NAT total injective (DATABASES obid.)
DatabaseName –> CHAR(255) total (The database name.)
DatabaseSemantics –> CHAR(900) (The database description.)
Server : DATABASES –> SERVERS total (The server hosting the database.)
key: DatabaseName • Server (DBMSs don`t accept two or more hosted databases having same name.)
APPLICATIONS (The set of programming applications build onto MatBase managed databases.)
#App –> NAT total injective (APPLICATIONS obid.)
AppName –> CHAR(100) total (Application name.)
Path –> CHAR(800) total (Application storage path.)
Database : APPLICATIONS –> DATABASES total (The database on which the application is built.)
key: AppName • Path (OSs don`t accept two or more files having same name in a same folder.)
DICTIONARY (The set of MatBase string constants and their equivelences in the languages of interest.)
Lg –> NAT total injective (DICTIONARY obid.)
System –> BOOL total injective (True if label/message is a system one, false if it is a user one.)
DictSemantics –> CHAR(900) total (The dictionary description.)
EN <–> CHAR(510) total injective (The English version for labels, messages,etc.)
FR <–> CHAR(510) total injective (The French version for labels, messages,etc.)
RO <–> CHAR(510) total injective (The Romanian version for labels, messages,etc.)
key: EN (No English label/message/etc. should be stored more than once.)
key: FR (No French label/message/etc. should be stored more than once.)
key: RO (No Romanian label/message/etc. should be stored more than once.)
LANGUAGES (The set of MatBase dictionary languages.)
Lg –> NAT total injective (LANGUAGES obid.)
LngCode <–> CHAR(4) total injective (Language abbreviation.)
LngName <–> CHAR(255) total injective (The language name.)
LngPos –> NAT total injective (Language position within the dictionary.)
LngActive –> BOOL total injective (True if current language is active, false if it is inactive (active = user selected or default MatBase current language).)
key: LngName (Language names should be unique.)
key: LngPos (In any column position of the dictionary there may be only one language stored.)
key: LngCode (Language abbreviations should be unique.)
PREFERENCES (The set of MatBase users preferences.)
#Pref –> NAT total injective (PREFERENCES obid.)
PreferenceName <–> CHAR(255) total injective (The preference name.)
Value –> BOOL total injective (The preference value: true if the preference is currently enabled, false otherwise.)
PreferenceSemantics –> CHAR(900) (The preference description.)
7. OBJECT CONSTRAINTS INVOLVING MORE THAN ONE SET
Constraint Name: Obj_Cnstr_MatBase_Obj_Cnstr_MatBase_RELATIONSHIPS
(for all x in RELATIONSHIPS)(¬(Symmetric(x) ^ Antisymmetric(x)) ^ ¬(Acyclic(x) ^ Reflexive(x))) (No relation may simultaneously be neither symmetric and antisymmetric, nor acyclic and reflexive (as acyclicity implies non-reflexivity).)
Constraint Name: Obj_Cnstr_MatBase_SETS_SetType
(for all x in SETS)(for all y in CONSTANTS)(Constant(y) not equal to SetName(x)) (Constant names should be distinct of set names.)
Constraint Name: Obj_Cnstr_MatBase_INCLUSIONS_DefInc
(for all x in INCLUSIONS)(for all y in Subset(x)) => (y in Set(x)) (Formalizes inclusions definition.)
Constraint Name: Obj_Cnstr_MatBase_SET_EQUALITIES_DefSE
(for all x in SET_EQUALITIES)(for all y in LeftSet(x))(for all z in RightSet(x))(y in RightSet(x) ^ z in LeftSet(x)) (Formalizes set equalities definition.)
Constraint Name: Obj_Cnstr_MatBase_SET_EQUALITIES_SE_Inc
(for all x in INLCUSIONS)(for all y in SET_EQUALITIES)((Subset(x) not equal to LeftSet(y) v Set(x) not equal to RightSet(y)) ^ (Set(x) not equal to LeftSet(y) v Subset(x) not equal to RightSet(y))) (Rule out set equalitites between any subset and its corresponding set.)
Constraint Name: Obj_Cnstr_MatBase_SET_EQUALITIES_SE_Inc_2
(for all x in SET_EQUALITIES)(for all y in INCLUSIONS)(for all z in INCLUSIONS)¬(Subset(y) = Subset(z) ^ (LeftSet(x) = Set(y) ^ RightSet(x) = Set(z) v RightSet(x) = Set(y) ^ LeftSet(x) = Set(z)) v Set(y) = Set(z) ^ (LeftSet(x) = Subset(y) ^ RightSet(x) = Subset(z) v RightSet(x) = Subset(y) ^ LeftSet(x) = Subset(z)) ^ z not equal to y) (Rule out set equalitites between any subset and its corresponding derivable inclusions.)
Constraint Name: Obj_Cnstr_MatBase_FUNCTIONS
(for all x in FUNCTIONS)¬(Symmetric(x) ^ AntiSymmetric(x)) ^¬(Acyclic(x) ^ Reflexive(x)) (No function may simoultaneously be neither symmetric and anitsymmetric, nor acyclic and reflexive (as acyclicity implies non-reflexivity).)
Constraint Name: Obj_Cnstr_MatBase_FUNCTIONS_DefFunct
(for all x in FUNCTIONS)(for all y in Domain(x))(Total(x) ^ x(y) in Codomain(x) v ¬Total(x) ^ x(y) in Codomain(x) U {NULL}) (Formalizes function definition.)
Constraint Name: Obj_Cnstr_MatBase_FUNCTIONS_DefImgFunct
(for all x in FUNCTIONS)(for all y in Codomain(x))(for all z in Domain(x))(x(z) = y => y in Im(x)) (Function image definition.)
Constraint Name: Obj_Cnstr_MatBase_FUNCTIONS_DefCanonicalInj
(for all x in INCLUSIONS)(for all y in Subset(x))(i(y) = y) (Formalizes canonical injection mapping definition.)
Constraint Name: Obj_Cnstr_MatBase_FUNCTIONS_Injectivity
(for all x in SETS)(Injective(ObjectId(x))) (Enforces injectivity.)
Constraint Name: Obj_Cnstr_MatBase_MIN_INJ_COMP_DefProductFunct
(for all x,y in MIN_INJ_COMP)(MinInject(x) = MinInject(y)) => Domain(MFunction(x) = Domain(MFunction(y))) (Any two functions f and g can be concatenated in function f • g only if f and g have a same domain.)
Constraint Name: Obj_Cnstr_MatBase_MIN_INJ_COMP_DefMinInj
(for all x in MIN_INJ_COMP)(¬Injective(MFunction(x)) (Formalizes minimal injectivity definition.)
Constraint Name: Obj_Cnstr_MatBase_MIN_INJ_COMP_DefMinInjComp
(for all x,y in MIN_INJ_COMP)(MinInject(x) not equal to MinInject(y) => Im(MFunction)|MinInject(x) ¬included Im(MFunction)|MinInject(y) ^ Im(MFunction)|MinInject(y) ¬included Im(MFunction)|MinInject(x)) (Formalizes minimal injectivity definition.)
Constraint Name: Obj_Cnstr_MatBase_FUNCT_EQUALS_DefFE
(for all x in FUNCT_EQUALS)(Domain(LeftFunct(x)) Domain(RightFunct(x)) ^ Im(LeftFunct(x) = Im(RightFunct(x)))) (Any tho functions f and g can be equal only if they have same domain and images.)
Constraint Name: Obj_Cnstr_MatBase_FUNCT_EQUALS_FunctAliases
(for all x in FUNCT_EQUALS)(LeftFunct(x) in COMP_FUNCT v RightFunct(x) in COMP_FUNCT) (Rules out interpreting function aliases as constraints.)
Constraint Name: Obj_Cnstr_MatBase_EXIST_CNSTRS_DefEC
(for all x in EXIST_CNSTRS)(Domain(ECLeftSide(x)) included in Domain(ECRightSide(x))) (Any two functions f and g can be related by f |- g, only if they have same domain.)
Constraint Name: Obj_Cnstr_MatBase_EXIST_CNSTRS_DefEC2
(for all x in EXIST_CNSTRS)(for all y in Domain(ECLeftSide(x)))(ECLeftSide(x)(y) not equal to NULL => ECRightSide(x)(y) not equal to NULL ) (Formalizes existence constraint definition.)
Constraint Name: Obj_Cnstr_MatBase_EXIST_CNSTRS_TrivialEC
(for all x in EXIST_CNSTRS)(ECLeftSide(x) not equal to ECRightSide(x)) (Rules out trivial existence constraint of type f |- f, for any function f(note that trivial ones of the form f |- empty set are ruled out by constraint "function, total").)
Constraint Name: Obj_Cnstr_MatBase_DISJUNCTIONS_DefDisj
(for all x in DISJUNCTIONS)((for all y in DLeftSide(x))(y not in DRightSide(x)) ^ (for all y in DRightSide(x))(y not in DLeftSide(x))) (Formalizes disjunctions definition.)
Constraint Name: Obj_Cnstr_MatBase_DISJUNCTIONS_Disj_Sets
(for all x in INCLUSIONS)(for all y in DISJUNCTIONS)((Subset(x) not equal to DLeftSide(y) v Set(x) not equal to DRightSide(y)) ^ (Set(x) not equal to DLeftSide(y) v Subset(x) not equal to DRightSide(y))) (Rule out disjunctions between subsets.)
Constraint Name: Obj_Cnstr_MatBase_DISJUNCTIONS_Disj_Sets2
(for all x in SET_EQUALITIES)(for all x in DISJUNCTIONS)((LeftSet(x) not equal to DLeftSet(y) v RightSet(x) not equal to DRightSide(y)) ^ RightSet(x) not equal to DLeftSide(y) v LeftSet(x) not equal to DRightSide(y)) (Rule out disjunctions between sets.)
Constraint Name: Obj_Cnstr_MatBase_DISJUNCTIONS_DerivedDisj
(for all x in SET_EQUALITIES)(for all y in DISJUNCTIONS)(for all z in DISJUNCTIONS)¬((z not equal to y ^ (LeftSet(x) = DLeftSide(y) v LeftSet(x) = DRightSide(y)) v (RightSet(x) = DLeftSide(z) ^ DRightSide(z) = DRightSide(y) v RightSet(x) = DRightSide(z) ^ DLeftSide(z) = DLeftSide(y))) (Rules put storing disjunctions derivable from other related disjunctions and set equalities.)
Constraint Name: Obj_Cnstr_MatBase_DIRECT_SUMS_DefDS
(for all x in DIR_SUMS_COMP)(for all y in DSMember(x))(y in DSLeftSide(DirectSum(x))) (Formalizes direct sums definition.)
Constraint Name: Obj_Cnstr_MatBase_DIRECT_SUMS_DefDS2
(for all x in DIRECT_SUMS)(for all y in DSLeftSide(x))(exists z in DIR_SUMS_COMP)(DirectSum(z) = x ^ y in DSMember(z)) (Formalizes direct sums definition.)
Constraint Name: Obj_Cnstr_MatBase_DIRECT_SUMS_DefDS3
(for all x,y in DIR_SUMS_COMP)(for all z in DSMember(x))(for all w in DSMember(y))(DirectSum(x) = DirectSum(y) ^ x not equal to y => z not in DSMember(y) ^ w not in DSMember(x)) (Formalizes direct sums definition.)
Constraint Name: Obj_Cnstr_MatBase_DIRECT_SUMS_ExistenceLRSet
(for all x in DIR_SUMS_COMP)(for all y in DIRECT_SUMS)(DirectSum(x) = y => DSMember(x) not equal to DSLeftSide(y)) (Rules out appearance of the left hand side set into the corresponding right hand side too.)
Constraint Name: Obj_Cnstr_MatBase_DIRECT_SUMS_Homogenity
(for all x in DIR_SUMS_COMP)(SetType ° DSLeftSide ° DirectSum(x) = SetType ° DSMember(x) v SetType ° DSMember(x) =`N`) (Enforces homogenity of the direct sums.)
Constraint Name: Obj_Cnstr_MatBase_DIRECT_SUMS_StoresMoreDS
(for all x,y in DIRECT_SUMS)(for all u,v in DIR_SUMS_COMP)(x not equal to y ^ DSLeftSide(x) = DSLeftSide(y) => Im(DSMember)|DirectSum(u)=x not included in Im(DSMember)|DirectSum(v)=y ^ Im(DSMember)|DirectSum(v)=y not included in Im(DSMember)|DirectSum(u)=x) (Rules out storing both A = B+C+D and A = B+C; note that it also tyles out storing any direct sum more than once.)
Constraint Name: Obj_Cnstr_MatBase_DIRECT_SUMS
(for all x in DIR_SUMS_COMP)(SetType ° DirectSum(x)° DSLeftSide = SetType ° DSMember(x)) (Direct sums are only allowed within a same set subclass.)
Constraint Name: Obj_Cnstr_MatBase_DIRECT_SUMS_DerivedDS_Set
(for all x in SET_EQUALITIES)(for all y in DIRECT_SUMS)(z not equal to y ^ (LeftSet(x) = DSLeftSide(y) ^ RightSet(x) = DSLeftSide(z) v RightSet(x) = DSLeftSide(y) ^ LeftSet(x) = DSLeftSide(z)) ^ Im(DSMember)|DirectSum(u)=y = Im(DSMember)|DirectSum(v)=z) (Rules out storing sums derivable from other related direct sums and set equalities.)
Constraint Name: Obj_Cnstr_MatBase_DIRECT_SUMS_Coresp_LR_DS
(for all x in DIR_SUMS_COMP)(for all y in DISJUNCTIONS)((DSLeftSide(DirectSum(x)) = DLeftSide(y) => DSMember(x) not equal to DRightSide(y)) ^ (DSLeftSide(DirectSum(x)) = DRightSide(y) => DSMember(x) not equal to DLeftSide(y))) (Rules out disjunctions between the left hand side set and any corresponding right hand side one.)
Constraint Name: Obj_Cnstr_MatBase_DIRECT_SUMS_Coresp_RR_DS
(for all x,y in DIR_SUMS_COMP)(for all z in DISJUNCTIONS) (x not equal to y ^ DirectSum(x) = DirectSum(y) => (DSMember(x) not equal to DLeftSide(z) v DSMember(y) not equal to DRightSide(z)) ^ (DSMember(y) not equal to DLeftSide(z) v DSMember(x) not equal to DRightSide(z))) (Rules out disjunctions between any two right hand side terms of a same direct sum.)
Constraint Name: Obj_Cnstr_MatBase_REPRES_SYSTS
(for all x in REPRES_SYSTS)(Codomain(x) included in Domain(x)) (For any representative system, its quotient set is a subset of its underlying set.)
Constraint Name: Obj_Cnstr_MatBase_REPRES_SYSTS_RSPropr
(for all x in REPRES_SYSTS)(Surjective(x) ^ Idempotent(x)) (Formalizes canonical surjections properties: they are both surjective and idempotent.)
Constraint Name: Obj_Cnstr_MatBase_INF_R_COMP_UKInfR
(for all x, y in INF_RULE)(for all u,v in INF_R_COMP)(x not equal to y ^ RuleHead(x) = RuleHead(y) => Im(Negation? • Predicate)|InfRule(u)=x not equal to Im(Negation? • Predicate)|InfRule(v)=y (Rules out storing twice a same inference rule.)
Constraint Name: Obj_Cnstr_MatBase_EXPRESSIONS_StoreExprTwice
(for all x,y in EXPRESSIONS)(AOp(y) = AOp(x) = 'NULL' ^ LMinus(x) not equal to 'NULL' ^ x = LeftExpr(y) => LMinus(y) = 'NULL') (Rules out duble applications of unary minus.)
Constraint Name: Obj_Cnstr_MatBase_EXPRESSIONS_AOpComutativities
(for all x in EXPRESSIONS)(for all y in EXPRESSIONS)¬((LMinus(x) = 'NULL' ^ AOp(x) = '+' or AOp(x) = '*') => AOp(y) = AOp(x) ^ LMinus(y) = 'NULL' ^ LeftExpr(x) = RightExpr(y) ^ RightExpr(x) = LeftExpr(y)) (Rules out storing dual commutative sum and product expressions not prefixed by a unary minus.)
Constraint Name: Obj_Cnstr_MatBase_EXPRESSIONS_AOpComutativities1
(for all x in EXPRESSIONS)(for all y in EXPRESSIONS)¬((LMinus(x) = '-' ^ LMinus(y) = '-' or AOp(x) = '*') => AOp(y) = AOp(x) ^ LMinus(y) = ''- ^ LeftExpr(x) = RightExpr(y) ^ RightExpr(x) = LeftExpr(y)) (Rules out storing dual commutative sum and product expressions prefixed by a unary minus.)
Constraint Name: Obj_Cnstr_MatBase_EXPRESSIONS_AOpComutativities2
(for all x in EXPRESSIONS)(for all y in EXPRESSIONS)¬((LMinus(x) = 'NULL' ^ AOp = '-' => AOp(y) = '+' ^ LMinus(y) = '-' ^LeftExpr(x) = RightExpr(y) ^ RightExpr(x) = LeftExpr(y))) (Rules out storing dual commutative algebraic sum and product expressions not prefixed by a unary minus.)
Constraint Name: Obj_Cnstr_MatBase_EXPRESSIONS_AOpComutativities3
(for all x in EXPRESSIONS)(for all y in EXPRESSIONS)¬((LMinus(x) = '-' ^ AOp(x) = '+' => AOp(y) = '-' ^ LMinus(y) = 'NULL' ^ LeftExpr(x) = RightExpr(y) ^ RightExpr(x) = LeftExpr(y)) (Rules out storing dual commutative algebraic sum and product expressions prefixed by a unary minus.)
Constraint Name: Obj_Cnstr_MatBase_EXPRESSIONS_AOpDistributivities
(for all a,b,c,d,e,f,x in EXPRESSIONS)(for all y in EXPRESSIONS)¬(mdistrib(a,b,c,d,e,f,x,y)) (Rules out storing product distributive expressions.)
Constraint Name: Obj_Cnstr_MatBase_EXPRESSIONS_AOpDistributivities1
(for all a,b,c,d,e,f,y in EXPRESSIONS)(for all x in EXPRESSIONS)¬(mdistrib(a,b,c,d,e,f,x,y)) (Rules out storing dual product distributive expressions.)
Constraint Name: Obj_Cnstr_MatBase_EXPRESSIONS_AOpDistributivities2
(for all a,b,c,d,e,f,x in EXPRESSIONS)(for all y in EXPRESSIONS)¬(distrib(a,b,c,d,e,f,x,y)) (Rules out storing division distributive expressions.)
Constraint Name: Obj_Cnstr_MatBase_EXPRESSIONS_AOpDistributivities3
(for all a,b,c,d,e,f,x in EXPRESSIONS)(for all y in EXPRESSIONS)¬(distrib(a,b,c,d,e,f,x,y)) (Rules out storing dual division distributive expressions.)
Constraint Name: Obj_Cnstr_MatBase_EXPRESSIONS_ForbidsDivisionBy0
(for all x in EXPRESSIONS)(AOp(x) = '/' ^ RightExpr(x) not equal to 0) (Rules out division by 0.)
Constraint Name: Obj_Cnstr_MatBase_FORMULAS
(for all x,y in FORMULAS)(LOp(y) = LOp(x) = `NULL` ^ Negation?(x) = x = LeftFormula(y) => ¬Negation?(y)) (Rules out duble negations.)
Constraint Name: Obj_Cnstr_MatBase_FORMULAS_TrivialTautologies
(for all x in FORMULAS)(LeftFormula(x) not equal to RightFormula(x)) (Rules out trivial tautologies.)
Constraint Name: Obj_Cnstr_MatBase_FORMULAS_TautologicalInconsistence
(for all x,y in FORMULAS)(for all z in FORMULAS)¬(((LeftFormula • LOp • RightFormula)(x) = (LeftFormula • LOp • RightFormula(y) ^ Negation?(x) not equal to Negation?(y) ^ LeftFormula(z) = x ^ RightFormula(z) = y)) (Rules out tautological inconsistences (including contradictions).)
Constraint Name: Obj_Cnstr_MatBase_FORMULAS_LOpComutativities
(for all x in FORMULAS )(for all y in FORMULAS)¬((LeftFormula(x) = RightFormula(y) ^ LOp(x) not equal to ' =>' ^ LOp(x) = LOp(y) ^ RightFormula(x) = LeftFormula(y))) (Rules out storing commutative formulas.)
Constraint Name: Obj_Cnstr_MatBase_FORMULAS_LOpDistrib
(for all a,b,c,d,e,f,x in FORMULAS)(for all y in FORMULAS)¬(adistrib(a,b,c,d,e,f,x,y)) (Rules out storing distributive formulas.)
Constraint Name: Obj_Cnstr_MatBase_FORMULAS_LOpDistributivity
(for all a,b,c,d,e,f,y in FORMULAS)(for all x in FORMULAS)¬(adistrib(a,b,c,d,e,f,x,y)) (Rules out storing dual distributive formulas.)
Constraint Name: Obj_Cnstr_MatBase_FORMULAS_DefImplication
(for all x,y,z in FORMULAS)(for all t in FORMULAS)¬(((LeftFormula • LOp • RightFormula)(x) = (LeftFormula • Lop • RightFormula)(y) ^¬Negation?(x) ^ Negation?(y) ^ LOp(t) = `v`^ (LeftFormula)(t) = y ^ RightFormula(t) = z v LeftFormula(t) = z ^ RightFormula(t) = y))) (Rules out storing logical implication equivalent expressions.)
Constraint Name: Obj_Cnstr_MatBase_FORMULAS_DefEquivalence
(for all x,y in FORMULAS)(for all z in FORMULAS)¬((LeftFormula(x) = RightFormula(y) ^ RightFormula(x) = LeftFormula(y) ^ ¬Negation? ^ ¬Negation?(y) ^ LOp(x) = LOp(y) = '=>' ^ (LeftFormula(z)=x ^ RightFormula (z) = y) or LeftFormula(z) = y ^ RightFormula(z) = x))) (Rules out storing logical equivalence equivalent expressions.)
Constraint Name: Obj_Cnstr_MatBase_FORMULAS_DeMorganFirstLaw
(for all x,y,z,u,v in FORMULAS)(for all t in FORMULAS)¬(((LeftFormula • Lop • RightFormula)(x) = (LeftFormula • LOp • RightFormula(y) ^ ¬Negation?(x) ^ Negation?(y) ^ (LeftFormula • Lop • RightFormula)(z) = (LeftFormula • LOp • RightFormula(u) ^ ¬Negation?(z) ^ Negation?(u) ^ Negation?(v) ^ (LeftFormula(v)=x ^ RightFormula(v) = z ^ LOp(v) = `^` ^ LOp(T)= `V`^ ¬Negation?(t) ^ (LeftFormula(t)=y ^ RightFormula(t) = u v LeftFormula(t) = u ^ RightFormula(t) = y))) (Rules out storing first DeMorgan Law equivalent expressions.)
Constraint Name: Obj_Cnstr_MatBase_FORMULAS_DeMorganSecondLaw
(for all x,y,z,u,v in FORMULAS)(for all t in FORMULAS)¬(((LeftFormula • Lop • RightFormula)(x) = (LeftFormula • LOp • RightFormula(y) ^ Negation?(x) ^ Negation?(y) ^ (LeftFormula • Lop • RightFormula)(z)=(LeftFormula • LOp • RightFormula(u) ^ Negation?(z) ^ Negation?(u) ^ Negation?(v) ^ (LeftFormula(v) = x ^ RightFormula(v) = z ^ LOp(t) = '^' ^ LOp(v) = 'v' ¬Negation?(t) ^ (LeftFormula(t) = y) ^ RightFormula(t) = u v LeftFormula(t) = u ^ RightFormula(t) = y))) (Rules out storing second DeMorgan Law equivalent expressions.)
Constraint Name: Obj_Cnstr_MatBase_FORMULAS_Transitivity
(for all x,y in FORMULAS)(for all z in FORMULAS)¬((LOp(x) = LOp(y) = LOp(z) not equal to 'v') ^ LeftFormula(y) = RightFromula(x) ^ LeftFormula(x) = LeftFormula(z) ^ RightFormula(y) = RightFormula(z))) (Rules out storing transitivity equivalent expressions.)
Constraint Name: Obj_Cnstr_MatBase_FORMULAS_Acyclicity
(for all x in FORMULAS)(LOp(x) not equal to 'v' => acyclic(LeftFormula • RightFormula)|LOp(x)) (Rules out storing cyclic formulas (except for disjunctions).)
Constraint Name: Obj_Cnstr_MatBase_ATOMS_StoreReflexivities
(for all x in ATOMS)(LeftOp(x) not equal to RightOp(x)) (Rule out storing reflexivities.)
Constraint Name: Obj_Cnstr_MatBase_ATOMS_StoreSymmetries
(for all x in ATOMS)(for all y in ATOMS)¬((RelOp(x) = '=' => LeftOp(x) = RightOp(y) ^ RightOp(x) = LeftOp(y) ^ RelOp(x) = RelOp(y))) (Rule out storing symmetries.)
Constraint Name: Obj_Cnstr_MatBase_ATOMS_Transitivity
(for all x,y in ATOMS)(for all z in ATOMS)¬((RelOp(x) = RelOp(y) = RelOp(z) ^ LeftOp(y) = RightOp(x) ^ LeftOp(x) = LeftOp(z) ^ RightOp(y) = RightOp(z))) (Rule out storing transitivities.)
Constraint Name: Obj_Cnstr_MatBase_ATOMS_Acyclicity
(for all x in ATOMS)(acyclic(LeftOp • RightOp)|RelOp(x)) (Rule out storing acyclicity.)
Constraint Name: Obj_Cnstr_MatBase_SUBSTITUTIONS_AllSRefSameFormula
(for all x,y in SUBSTITUTIONS)(Cnstrnt(x)=Cnstrnt(y) => FPFormula ° OVSubst(x) = FPFormula ° OvSubst(y) ) (All variable substitutions of any constraint should refer to the same formula.)
Constraint Name: Obj_Cnstr_MatBase_PROGRAMS_ProgSafety
(for all x in VARIABLES)(for all y,z in PREDICATE_CALLS)(for all s,t in PREDICATE_C_V)(for all u in INF_R_COMP)(exists v in INF_R_COMP)(u not equal to v ^ Negation?(u) ^ not Negation?(v) ^ InfRule(u) = InfRule(v) ^ y = Predicate(u) = PredCVPred(s) ^ z = Predicate(v) = PredCVPred(t) ^ x = PredCVVar(s) = PredCVVar(t)) (Program safety formalization.)
Constraint Name: Obj_Cnstr_RA_EXPR_DefRAExpr
(for all x in RA_EXPR)(LeftRAExpr(x) not equal to #RAEX(x)) (Rules out storing tautological relational algebraic expressions definitions.)
Constraint Name: Obj_Cnstr_RA_EXPR_DefRaExpr2
(for all x in RA_EXPR)(RightRAExpr(x) not equal to #RAEX(x)) (Rules out storing dual tautological relational algebraic expressions definitions.)
Constraint Name: Obj_Cnstrs_MatBase_FUNCTIONS_Codom
(for all x in FUNCTIONS)(ConstType(x) • DefalutValue(x) = Codomain(x)) (For any function, its default value should be in its codomain.)
Constraint Name: Obj_Cnstr_MatBase_FUNCTIONS_Ren
(for all f,g in FUNCTIONS)(g = Renaming(f) => Domain(f) = Domain(g) ^ Codomain(f) = Codomain(g)) (Any function renaming should have same domain and codomain as the renamed one.)
Constraint Name: Obj_Cnstr_MatBase_SETS
(for all s,t in SETS)(t = Synonym(s) => SetType(t) = SetType(s)) (Any set synonym should have same type as the renamed one.)
Constraint Name: Obj_Cnstr_MatBase_SETS_Syn
(for all x, y in SETS)(y = Synonym(x) => Synonym(y) = NULL) (No synonym may be on another synonym.)
Constraint Name: Obj_Cnstr_MatBase_FUNCTIONS_Proj
(for all x in FUNCTIONS)(Projection?(x) => SetType Domain(x) = 'R' ) ()
Constraint Name: Obj_Cnstr_MatBase_FUNCTIONS_Img
(for all f in FUNCTIONS)(Img(f) in Codom(f)) ()
LS)(for all s,t in PREDICATE_C_V)(for all u in INF_R_COMP)(exists v in INF_R_COMP)(u not equal to v ^ Negation?(u) ^ not Negation?(v) ^ InfRule(u) = InfRule(v) ^ y = Predicate(u) = PredCVPred(s) ^ z = Predicate(v) = PredCVPred(t) ^ x = PredCVVar(s) = PredCVVar(t)) (Program safety formalization.)
Constraint Name: Obj_Cnstr_RA_EXPR_DefRAExpr
(for all x in RA_EXPR)(LeftRAExpr(x) not equal to #RAEX(x)) (Rules out storing tautological relational algebraic expressions definitions.)
Constraint Name: Obj_Cnstr_RA_EXPR_DefRaExpr2
(for all x in RA_EXPR)(RightRAExpr(x) not equal to #RAEX(x)) (Rules out storing dual tautological relational algebraic expressions definitions.)
Constraint Name: Obj_Cnstrs_MatBase_FUNCTIONS_Codom
(for all x in FUNCTIONS)(ConstType(x) • DefalutValue(x) = Codomain(x)) (For any function, its default value should be in its codomain.)
Constraint Name: Obj_Cnstr_MatBase_FUNCTIONS_Ren
(for all f,g in FUNCTIONS)(g = Renaming(f) => Domain(f) = Domain(g) ^ Codomain(f) = Codomain(g)) (Any function renaming should have same domain and codomain as the renamed one.)
Constraint Name: Obj_Cnstr_MatBase_SETS
(for all s,t in SETS)(t = Synonym(s) => SetType(t) = SetType(s)) (Any set synonym should have same type as the renamed one.)
Constraint Name: Obj_Cnstr_MatBase_SETS_Syn
(for all x, y in SETS)(y = Synonym(x) => Synonym(y) = NULL) (No synonym may be on another synonym.)
Constraint Name: Obj_Cnstr_MatBase_FUNCTIONS_Proj
(for all x in FUNCTIONS)(Projection?(x) => SetType Domain(x) = 'R' ) ()
Constraint Name: Obj_Cnstr_MatBase_FUNCTIONS_Img
(for all f in FUNCTIONS)(Img(f) in Codom(f))
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Implementarea Sub Sistemului de Import Relational al Matbase (ID: 164203)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.