Calcul relațional

Calculul Relational face parte, împreună cu algebra relațională și Datalog , dintre limbile oficiale care permit să -și exprime interogări pentru gestionarea bazelor de date organizate în conformitate cu modelul relațional . Este împărțit în calcul relațional pe tupluri și calcul relațional pe domenii (TRC și respectiv DRC). Concepută de Edgar F. Codd în anii 1970, a fost istoric baza pentru dezvoltarea și evoluția SQL .

fundal

TRC a fost introdus pentru prima dată de Edgar F. („Ted”) Codd , ca parte a modelului relațional, pentru a oferi un sistem de declarații de baze de date care a fost mai degrabă declarativ decât procedural. Edgar F. Codd în anii 1970 a lucrat la teoria relațională a datelor sale, în urma căreia IBM a început să-și folosească modelul în cadrul unui proiect (System R) destinat să dea un mare impuls sistemelor relaționale, care au evoluat apoi în sistem comercial DB2 ^[1] . Apoi a publicat calculul relațional într-un articol ulterior din 1972, care conține, de asemenea, dovada echivalenței puterii expresive între calculul relațional și algebra relațională ^[2] .

Descriere și definiție formală

TRC (Tuple Relational Calculus) se bazează pe modelul relațional , adică un model logic pentru a descrie datele într-un mod foarte simplu, definind relațiile pornind de la domenii; din punct de vedere practic, o relație poate fi asimilată unui tabel cu rânduri și coloane. TRC este unul dintre instrumentele utilizate pentru interogarea bazelor de date , adică pentru extragerea informațiilor considerate utile. TRC este un limbaj declarativ și neprocedural: aceasta înseamnă că în interogări (un termen care indică interogarea unei baze de date printr-un limbaj formal) nu este explicit modul în care informațiile sunt extrase, ci mai degrabă rezultatul dorit. Obțineți din interogare, adică datele pe care doriți să le izolați de ceilalți, astfel încât să fie ușor de consultat și consumat. Deoarece TRC este pur declarativ, nu are sens să optimizăm o interogare de calcul relațional, deoarece operațiunile efectuate pentru a ajunge la rezultat nu sunt explicite de limbaj.

Formular standard TRC

Forma standard a limbajului TRC este următoarea: {t | p (t)} , unde p (t) este o formulă formată din părți mai simple și care nu se pot minimiza în continuare numite atomi . Pentru a indica anumite valori și a face formulele mai explicative, este permisă utilizarea comparatoarelor clasice precum: =, <>,>,> =, <, <=. Este posibil să se facă restricții precum t [A]: această sintaxă indică faptul că luăm în considerare pentru un tuplu valoarea unui atribut A.

Reguli de construcție pentru formule

Există reguli precise de urmat pentru a obține formule TRC corecte:

Un atom este o formulă;
Dacă p este o formulă, la fel este ~ p .
Dacă p1 și p2 sunt formule, așa sunt și p1 ∧ p2, p1 ∨ p2, p1 => p2
Dacă p este o formulă în care s este o variabilă, la fel sunt ∃ s $\in$ ${\ displaystyle \ in}$ ${\ displaystyle \ in}$ R (p (s)) , ∀ s $\in$ ${\ displaystyle \ in}$ ${\ displaystyle \ in}$ R (p (s))

TRC are, de asemenea, trei proprietăți fundamentale:

Legea lui De Morgan: p1 ∧ p2 = ~ (~ p1 ∨ ~ p2)
Corespondența dintre cuantificatori: ∀t $\in$ ${\ displaystyle \ in}$ ${\ displaystyle \ in}$ R (p (t)) = ~ ∃t $\in$ ${\ displaystyle \ in}$ ${\ displaystyle \ in}$ R (~ p (t))
Definiția implicației: p1 => p2 = ~ p1 ∨ p2

Din aceste ultime trei legi este evident că este posibil să scrieți toate expresiile posibile fără utilizarea simbolului de implicație și fără cuantificatorul universal, ci numai cu utilizarea unui operator binar și a cuantificatorului existențial. Această metodă de scriere se numește Formă normală existențială . Urmează un exemplu de interogare.

 Extrageți bobocii studenților care au luat „matematică”, dar nu „baze de date”. Exemplul prezintă schema bazei de date considerate și atributele relative între paranteze drepte.

EXAMEN [Matr, Cod curs, Data]; CURS [Cod curs, titlu, profesor]

  {t | ∃t1 $\in$  $\in$   ${\ displaystyle \ in}$   ${\ displaystyle \ in}$  EXAMEN, ∃t2 $\in$  $\in$   ${\ displaystyle \ in}$   ${\ displaystyle \ in}$  CURS:
       ((t [Matr] = t1 [Matr]) ∧
       (t1 [CodCorso] = t2 [CodCorso]) ∧
       (t2 [Titlu] = 'matematică')) ∧ 
           ~ (∃ t3 $\in$  $\in$   ${\ displaystyle \ in}$   ${\ displaystyle \ in}$  EXAMEN, ∃ t4 $\in$  $\in$   ${\ displaystyle \ in}$   ${\ displaystyle \ in}$  CURS:
                (t [Matr] = t3 [Matr]) ∧ 
                (t3 [CodCorso] = t4 [CodCorso]) ∧ 
                (t4 [Title] = 'baze de date'))))}

Operații algebrice exprimate în TRC

Deși TRC este, așa cum sa menționat, un limbaj declarativ și neprocedural, este posibil să se exprime toate operațiile (și, prin urmare, interogările) care pot fi exprimate cu algebră relațională.

Selecție : este posibil să o definiți ca o extracție orizontală, adică selectează toate și numai tuplurile care satisfac predicatul indicat în operator.

 Exemplu: extrageți toate tuplurile în care atributul A are o valoare mai mare de 1:
{t | ∃t1 $\in$  $\in$   ${\ displaystyle \ in}$   ${\ displaystyle \ in}$  R: (t [A]> 1)}.
Mai întâi indicați ce relație (schemă) aparține tuplului și apoi rescrieți simbolul folosit pentru a indica tuplul urmat de o paranteză pătrată care conține numele atributului pe care doriți să faceți selecția urmată de comparator util pentru realizarea doritei selecție.

Proiecție : este opusul selecției, adică este o extracție verticală care se realizează alegând unul sau mai multe atribute dintre cele de interes în schemă și aruncându-le pe celelalte, arătând apoi toate valorile pe care tuplele au pentru acele atribute.

 Exemplu: extrageți toate valorile atributelor A și B ale relației R:
 {t | ∃ t1 $\in$  $\in$   ${\ displaystyle \ in}$   ${\ displaystyle \ in}$  R: (t [A, B] = t1 [A, B])} 
Atributele pe care dorim să le proiectăm sunt indicate între paranteze pătrate și la egalitate cu tuplul t dorit
au ca rezultat.

Produs cartezian : este ansamblul tuturor combinațiilor posibile de tupluri aparținând două relații diferite.

 Exemplu: extrageți produsul cartezian al tuplurilor relațiilor R, ale căror atribute sunt A, B și C și T cu atributele D, E și F.
{t | ∃t1 $\in$  $\in$   ${\ displaystyle \ in}$   ${\ displaystyle \ in}$  R, ∃t2 $\in$  $\in$   ${\ displaystyle \ in}$   ${\ displaystyle \ in}$  T:
((t [A, B, C] = t1 [A, B, C]) ∧
  (t [D, E, F] = t2 [D, E, F]))}
Ca de obicei, mai întâi definim apartenența tuplurilor la relația de referință și apoi echivalăm toate atributele fiecărui tuplu, în cazul t1 și t2, cu tuplul care trebuie să proiecteze rezultatul nostru, adică t. Cele două operații de egalitate sunt unite de AND-ul logic.

Join : este un operator care asociază tupluri de relații diferite care au totuși aceeași valoare pe unul sau mai multe atribute compatibile, adică pe același domeniu.

 Exemplu: uniți relația R (A, B) și S (C, D) pe atributele omogene B și C.
{t | ∃t1 $\in$  $\in$   ${\ displaystyle \ in}$   ${\ displaystyle \ in}$  R, ∃t2 $\in$  $\in$   ${\ displaystyle \ in}$   ${\ displaystyle \ in}$  T:
 ((t [A, B] = t1 [C, D]) ∧
  (t [C, D] = t2 [C, D]) ∧
  (t [B] = t [C]))}}
Unirea funcționează comparând atributele tuplurilor a două relații diferite, creând o nouă relație.

Diferență : se folosește pentru a exclude dintr-o relație tuplurile care au una sau mai multe anumite caracteristici.

 Exemplu: extrageți tuplele de R care nu sunt conținute în relația S.
{t | ∃ t $\in$  $\in$   ${\ displaystyle \ in}$   ${\ displaystyle \ in}$  A: (t $\notin$  $\notin$   ${\ displaystyle \ notin}$   ${\ displaystyle \ notin}$  S)}

Unire : unește tuplurile a două sau mai multe relații.

 Exemplu: extrageți tuplurile care derivă din unirea relațiilor R și T.
{t | ∃t1 $\in$  $\in$   ${\ displaystyle \ in}$   ${\ displaystyle \ in}$  R, ∃t2 $\in$  $\in$   ${\ displaystyle \ in}$   ${\ displaystyle \ in}$  T:
  (t = t1) ∨ (t = t2)}
Sintaxa indică pur și simplu că tuplurile rezultate aparțin fie relației R, fie relației S și, prin urmare, rezultatul conține toate tuplurile relațiilor R și S.

Operații în TRC exprimate în algebră

Arătăm doar un exemplu al modului în care propozițiile TRC pot fi exprimate în algebră relațională; conține selecție, proiecție, unire și diferență.

 Exemplu: extrageți toate tuplele lui R (A, B, C) având A mai mare decât unu și valorile lui B nu sunt în S (A, B, C):
TRC: {t | ∃t1 $\in$  $\in$   ${\ displaystyle \ in}$   ${\ displaystyle \ in}$  R:
       ((t [A, B, C] = t1 [A, B, C]) ∧ (t1 [A]> 1) ∧
             ~ (∃t2 $\in$  $\in$   ${\ displaystyle \ in}$   ${\ displaystyle \ in}$  S:
               (t1 [B] = t2 [B])}

Algebră relațională:  $\sigma _{A>1}$  $σ$   $LA$   $>$   $1$   ${\ displaystyle \ sigma _ {A> 1}}$   ${\ displaystyle \ sigma _ {A> 1}}$  (R - (R $\ltimes _{B=B}$  $⋉$   $B.$   $=$   $B.$   ${\ displaystyle \ ltimes _ {B = B}}$   ${\ displaystyle \ ltimes _ {B = B}}$  S))

Puterea expresivă a Calculului relațional

Calculul relațional pe tupluri și algebră are aceeași putere expresivă , adică setul de interogări exprimabile este același în ciuda diferențelor dintre cele două limbi. Reamintim că calculul relațional este un limbaj declarativ, adică identifică în mod explicit scopurile și obiectivele interogărilor fără a acorda atenție procedurii care trebuie realizată pentru a le atinge, o caracteristică în locul limbajelor procedurale, cum ar fi algebra relațională. Datalog are o mai mare putere expresivă, deoarece este posibil să se exprime interogări recursive.

Legături cu SQL

Calculul relației tuplurilor apare ca cel mai apropiat formalism de logica SQL . Ambele formalisme sunt declarative, deși SQL a fost îmbogățit cu structuri procedurale. Mai mult, TRC pare să aibă suficientă putere expresivă pentru a exprima interogări conjunctive, adică interogări care conțin selecție, proiecție, îmbinări; aceste interogări sunt cele mai populare din SQL.

Notă

^ Un model relațional de date pentru băncile mari de date partajate ( PDF ), pe seas.upenn.edu , iunie 1970.
^ Codd EF, Continuarea normalizării modelului relațional al bazei de date în sistemul de baze de date , editat de R. Rustin, Englewood Cliffs, Prentice Hall, 1972, pp. 33-64.

Bibliografie

Henry F. Korth și Abraham Silberschatz,Conceptele sistemului de baze de date , New York, McGraw-Hill Book Company, 1986, ISBN 0-07-044752-7 .
Paolo Atzeni, Stefano Ceri, Piero Fraternali, Stefano Paraboschi și Riccardo Torlone, Baze de date. Modele și limbi de interogare , ediția a IV-a, Milano, McGraw-Hill, 2013, ISBN 978-88-386-6800-5 .

Elemente conexe

[1] Un model relațional de date pentru băncile mari de date partajate ( PDF ), pe seas.upenn.edu , iunie 1970.

[2] Codd EF, Continuarea normalizării modelului relațional al bazei de date în sistemul de baze de date , editat de R. Rustin, Englewood Cliffs, Prentice Hall, 1972, pp. 33-64.

[1]

[2]