Limbaje formale pentru baze de date

Limbajele formale ale bazelor de date sunt limbi pentru descrierea operațiunilor de acces la date ale unei baze de date ;
Principalele, cu care pot fi exprimate interogări , sunt:

Algebra relațională , care este un limbaj procedural (adică procedura de construire a informațiilor solicitate este explicită). Se bazează pe cinci operații fundamentale (selecție, proiecție, unire, diferență și produs cartezian) și trei derivate (intersecție, îmbinare și semi-îmbinare) care dau puterea expresivă deplină a limbajului.

Calculul relațional , care este în schimb declarativ (adică ce informații trebuie extrase, dar nu cum). Acest limbaj se bazează pe logica primului ordin și, în afară de formulele nesigure, are o putere expresivă echivalentă cu cea a algebrei relaționale. Este împărțit în două tipuri principale: calculul tuplurilor (TRC, Tuple Relational Calculus ) și calculul domeniilor (DRC, Domain Relational Calculus ).

Datalog , care posedă o putere expresivă mai mare decât algebra relațională și trc, deoarece poate exprima interogări recursive. De asemenea, se bazează pe programarea logică, ca derivat al Prolog .

 Exemplu de algebră relațională și interogare TRC:
Arată numele studenților
 care au luat 28 la examinarea bazelor de date.
 Bază de date:
 STUDENT (număr de serie, nume, data nașterii, adresă);
 EXAMEN (numărul de serie, codul cursului, data, nota);
 CURS (Cod curs, titlu, profesor);

 Algebră relațională:
 Π Nume σ Rating = 28 ∧ Titlu = 'BasidiDati'
 (STUDENT ▷ ◁ EXAMEN ▷ ◁ CURS)

 TRC:
 {t | ∃ t1 ∈ STUDENT,
 ∃ t2 ∈ EXAMEN,
 ∃ t3 ∈ CURS
 (t [Nume] = t1 [Nume] ∧
 t1 [Număr de serie] = t2 [Număr de serie] ∧
 t2 [CourseCode] = t3 [CourseCode] ∧
 t2 [Scor] = 28 ∧ t3 [Titlu] = 'BasidiDati')}

 Jurnal de date:
 VOTĂ (Nume): -Estudiant (M, Nume, _ _),
 Examen (M, CCorso, _, V),
 Curs (CCorso, T, _),
 V = 28, T = „Baze de date”

Expresii algebrice în TRC

Deoarece interogările de algebră relațională pot fi exprimate prin cinci funcții fundamentale, pentru a demonstra că puterea sa expresivă este inclusă în cea de calcul (adică nu există interogări exprimabile în algebră relațională, dar nu și în trc) este suficient să arătăm cum aceste cinci primitivele sunt exprimabile în trc.

Selecţie: $\sigma _{condizione}R\leftrightarrow \{t|\exists t_{1}\in R(condizione\land t=t_{1})\}$ ${\ displaystyle \ sigma _ {condition} R \ leftrightarrow \ {t | \ există t_ {1} \ în R (condition \ land t = t_ {1}) \}}$ ${\ displaystyle \ sigma _ {condition} R \ leftrightarrow \ {t | \ există t_ {1} \ în R (condition \ land t = t_ {1}) \}}$
Proiecție: $\Pi _{attributo_{1},attributo_{2},...attributo_{n}}R\leftrightarrow \{t|\exists t_{1}\in Rt[attributo_{1}]=t_{1}[attributo_{1}]\land t[attributo_{2}]=t_{1}[attributo_{2}]\land ...t[attributo_{n}]=t_{1}[attributo_{n}])\}$ ${\ displaystyle \ Pi _ {atribut_ {1}, atribut_ {2}, ... atribut_ {n}} R \ leftrightarrow \ {t | \ există t_ {1} \ în Rt [atribut_ {1}] = t_ { 1} [atribut_ {1}] \ land t [atribut_ {2}] = t_ {1} [atribut_ {2}] \ land ... t [atribut_ {n}] = t_ {1} [atribut_ {n} ]) \}}$ ${\ displaystyle \ Pi _ {atribut_ {1}, atribut_ {2}, ... atribut_ {n}} R \ leftrightarrow \ {t | \ există t_ {1} \ în Rt [atribut_ {1}] = t_ { 1} [atribut_ {1}] \ land t [atribut_ {2}] = t_ {1} [atribut_ {2}] \ land ... t [atribut_ {n}] = t_ {1} [atribut_ {n} ]) \}}$
produs cartezian: Dacă TABELUL ₁ este compus din atributele a, b, c și TABEL este compus din d, e; $TABELLA_{1}\times TABELLA_{2}\leftrightarrow \{q|\exists t\in TABELLA_{1},s\in TABELLA_{2}(q[a]=t[a]\land q[b]=t[b]\land q[c]=t[c]\land q[d]=s[d]\land q[e]=s[e])\}$ ${\ displaystyle TABLE_ {1} \ times TABLE_ {2} \ leftrightarrow \ {q | \ există t \ în TABLE_ {1}, s \ în TABLE_ {2} (q [a] = t [a] \ land q [ b] = t [b] \ land q [c] = t [c] \ land q [d] = s [d] \ land q [e] = s [e]) \}}$ ${\ displaystyle TABLE_ {1} \ times TABLE_ {2} \ leftrightarrow \ {q | \ există t \ în TABLE_ {1}, s \ în TABLE_ {2} (q [a] = t [a] \ land q [ b] = t [b] \ land q [c] = t [c] \ land q [d] = s [d] \ land q [e] = s [e]) \}}$
Diferență: $TABELLA_{1}-TABELLA_{2}\leftrightarrow \{q|\exists t\in TABELLA_{1}(q=t\land (\not \exists s\in TABELLA_{2}(s=q)))\}$ ${\ displaystyle TABLE_ {1} -TABELLA_ {2} \ leftrightarrow \ {q | \ există t \ în TABLE_ {1} (q = t \ land (\ not \ există s \ în TABLE_ {2} (s = q) )) \}}$ ${\ displaystyle TABLE_ {1} -TABELLA_ {2} \ leftrightarrow \ {q | \ există t \ în TABLE_ {1} (q = t \ land (\ not \ există s \ în TABLE_ {2} (s = q) )) \}}$
Uniune: $TABELLA_{1}\cup TABELLA_{2}\leftrightarrow \{q|\exists t\in TABELLA_{1},s\in TABELLA_{2}(q=t\lor q=s)\}$ ${\ displaystyle TABLE_ {1} \ cup TABLE_ {2} \ leftrightarrow \ {q | \ există t \ în TABLE_ {1}, s \ în TABLE_ {2} (q = t \ lor q = s) \}}$ ${\ displaystyle TABLE_ {1} \ cup TABLE_ {2} \ leftrightarrow \ {q | \ există t \ în TABLE_ {1}, s \ în TABLE_ {2} (q = t \ lor q = s) \}}$

Expresii TRC în algebră relațională

Dacă, așa cum am văzut anterior, toate operațiile algebrei relaționale pot fi traduse cu expresii mai mult sau mai puțin complexe în TRC, nu este sigur că acest lucru se poate întâmpla și invers. De fapt, este important să subliniem că puterea expresivă a algebrei relaționale și a TRC poate fi considerată echivalentă numai atunci când limbajul din urmă este limitat la expresiile definite ca sigure .

O formulă sigură în Calcul, este o formulă independentă de domeniu, adică nu trebuie să depindă de posibilitatea de a-l varia.

Interogare nesigură

O formulă nesigură este o formulă dependentă de domeniu.

Exemplu de interogare nesigură :

 {t | t ∉ R}

Această expresie are ca rezultat tupluri infinite (sau mai bine zis toate tuplurile construibile pornind de la domeniul pe care este definit t) și, prin urmare, nu este „independentă de domeniu”. Prin urmare, această interogare nu poate fi evaluată în algebră.

Superioritatea registrului de date

Interogările recursive nu pot fi exprimate în algebră relațională sau trc (o interogare este recursivă dacă este exprimată în termeni în sine). Mai jos oferim un exemplu de interogare care nu poate fi exprimată în algebră fără a furniza o dovadă a acestui fapt.

Tabelul Ierarhia reprezintă o organigramă corporativă în care fiecare angajat are cel mult un supervizor.

Grefier de anul întâi	bobocSuperior

În acest context, întrebarea „pentru a extrage numărul de înregistrare a tuturor angajaților direcți sau indirecți ai unui superior” nu poate fi exprimată în algebră. De fapt, ar trebui realizat printr-un număr de îmbinări în funcție de instanța tabelului și, prin urmare, ar fi imposibil să se garanteze întotdeauna corectitudinea acestuia (dată fiind o interogare constând din n îmbinări, este suficient ca un angajat să aibă n + 1 superiori indirecți pentru a face ca rezultatul interogării să nu fie costum de afaceri). Exprimarea corectă a interogării necesită utilizarea recursivității.

Recursivitate în Datalog

Întrebările recursive, pe de altă parte, pot fi exprimate în Datalog: capul unei reguli poate apărea în corpul său. Regula de mai sus ar putea fi, de exemplu, rezolvată astfel:

 Supervizor (IMP, MAN): -Ierarhie (IMP, MAN)
 Supervizor (IMP, MAN): -Ierarhie (IMP, MED), Supervizor (MED, MAN)
 ? -Supervizor („Antonio”, _)

Notă

Diapozitive ale cursului bazelor de date 1 POLIMI ( PDF ), pe home.deib.polimi.it . Adus pe 29 noiembrie 2016 .
Concepte de sistem de baze de date - ediția 6 , pe codex.cs.yale.edu . Adus de 12 decembrie 2016.