Algebra relațională

Versiunea stabilă a fost verificată pe 29 iulie 2022 . Există modificări neverificate în șabloane sau .

Algebra relațională este un sistem închis de operații asupra relațiilor într-un model de date relaționale . Operațiile de algebră relațională se mai numesc și operații relaționale .

Setul inițial de 8 operații a fost propus de E. Codd în anii 1970 și a inclus atât operațiuni care sunt încă în uz ( proiecție , îmbinare etc.), cât și operațiuni care nu au intrat în uz (de exemplu, diviziunea relațiilor).

În dezvoltarea teoriei și practicii relaționale, au fost propuse mai multe operații relaționale noi, cum ar fi semi-join ( SEMI-JOIN ) și semi-diferență sau anti-semi-join ( ANTI-SEMI-JOIN ) [1] [2 ] , CROSS APPLY și OUTER APPLY , închidere tranzitivă ( TCLOSE ) etc.

Deoarece multe operații sunt exprimabile unele prin altele, ca parte a algebrei relaționale, se pot distinge mai multe variante ale bazei (un set de operații prin care toate celelalte sunt exprimabile). Cea mai faimoasă și strict definită bază ( algebra A ) a fost propusă de Christopher Date și Hugh Darwen [3] .

Algebra relațională și calculul relațional sunt echivalente în puterea lor expresivă [4] . Există reguli pentru conversia cererilor între ele.

Principala aplicație a algebrei relaționale este de a oferi un cadru teoretic pentru bazele de date relaționale , în special limbaje de interogare pentru astfel de baze de date, printre care principalul este SQL .

Algebră relațională închisă

Algebra relațională este un set de operații pe relații astfel încât rezultatul fiecăreia dintre operații este și o relație. Această proprietate a unei algebre se numește închidere .

Operațiile pe o relație se numesc unare , pe două relații - binare , pe trei - ternare (acestea sunt practic necunoscute).

Un exemplu de operație unară este o proiecție, un exemplu de operație binară este o unire.

O operație relațională N -ar f poate fi reprezentată printr-o funcție care returnează o relație și ia n relații ca argumente:

R=f(R_{1},R_{2},\dots, R_{n})

Deoarece algebra relațională este închisă, alte expresii de algebră relațională (adecvate pentru tip) pot fi înlocuite ca operanzi în operațiile relaționale:

R=f(f_{1}(R_{11},R_{12},\dots ),f_{2}(R_{21},R_{22},\dots ),\dots )

În expresiile relaționale, puteți utiliza expresii imbricate ale unei structuri arbitrar complexe.

Restricții privind operațiunile

Unele operații relaționale, în special uniunea , intersecția și scăderea , necesită ca relația să aibă anteturi (scheme) care se potrivesc (aceleași). Aceasta înseamnă că numărul de atribute, numele atributelor și tipul ( domeniul ) atributelor cu același nume sunt aceleași.

Unele relații nu sunt compatibile formal din cauza diferențelor în numele atributelor, dar devin astfel după aplicarea operației de redenumire a atributelor.

Operația de produs cartezian necesită ca relațiile de operanzi să nu aibă atribute cu același nume. Se spune că relațiile sunt compatibile prin luarea produsului cartezian extins dacă intersecția mulțimilor de nume de atribute luate din schemele lor de relații este goală.

Operații de algebră relațională

Următoarele sunt câteva operații de algebră relațională care sunt de interes istoric sau practic. Este imposibil să enumerați toate operațiile, deoarece orice operație care satisface definiția relațională face parte din algebra relațională.

Redenumire

Rezultatul aplicării operației de redenumire a atributelor este o relație cu numele atributelor schimbate.

Sintaxa :

R RENUMIRE Atr 1 , Atr 2 , … AS NewAtr 1 , NewAtr 2 , …

Unde

R - raport Atr 1 , Atr 2 , … — numele atributelor inițiale NewAtr 1 , NewAtr 2 , ... sunt nume de atribute noi.

Consolidare

O relație cu același titlu ca relațiile compatibile cu tipul A și B și un corp format din tupluri aparținând fie lui A , B , fie ambelor.
Sintaxă:

A UNIRE B

Traversare

O relație cu același titlu ca relațiile A și B și un corp format din tupluri aparținând ambelor relații A și B în același timp .
Sintaxă:

A INTERSECT B

Scădere

O relație cu același titlu ca relațiile compatibile cu tipul A și B și un corp format din tupluri care aparțin relației A și nu aparțin relației B.
Sintaxă:

A MINUS B

Operațiune de atribuire

Operatorul de atribuire (:=) vă permite să stocați rezultatul evaluării unei expresii relaționale într-o relație existentă.

produs cartezian

O relație al cărei titlu ( A 1 , A 2 , …, A n , B 1 , B 2 , …, B m ) este concatenarea titlurilor relațiilor A ( A 1 , A 2 , …, A n ) și B ( B 1 , B 2 , …, B m ), iar corpul este format din tupluri care sunt toate combinații de tupluri ale relațiilor A și B : ( a 1 , a 2 , …, a n , b 1 , b 2 , … , b m ),

astfel încât

( a 1 , a 2 , …, a n ) ∈ A , ( b 1 , b 2 , …, b m ) ∈ B .

Sintaxă:

A ORI B

Eșantionare (limitare)

O relație cu același titlu ca și relația A și un corp format din tupluri ale căror valori de atribut se evaluează la TRUE atunci când sunt substituite în condiția c . c este o expresie booleană care poate include atribute ale relației A și/sau expresii scalare.
Sintaxă:

A UNDE c

Eșantionul este scris ca sau unde: $\sigma _{a\theta b}(R)$ $\sigma _{a\theta v}(R)$

a și b sunt nume de atribute
θ este una dintre operațiile binare ${\displaystyle \{\;<,\leq,=,\neq,\geq,\;>\))$
v este o constantă
Raportul R

Proiecție

Proiecția este o operație unară care vă permite să obțineți un subset „vertical” al unei anumite relații , sau tabel, adică un astfel de subset care se obține prin selectarea atributelor specificate , urmată de eliminarea, dacă este necesar, a tuplurilor duplicate redundante. . Să fie dat un tabel cu nume de atribute , adică un subset al setului de nume de atribute . Rezultatul unei proiecții de tabel pe numele atributelor selectate este un nou tabel obținut din tabelul original prin ștergerea atributelor care nu sunt incluse în setul selectat, urmată de posibila eliminare a tuplurilor duplicate redundante. $T$ $A_{1},\;A_{2},\;\ldots ,\;A_{n}$ $T(A_{1},\;A_{2},\;\ldots ,\;A_{n})$ $\{A_{{i_{1}}},\;A_{{i_{2}}},\;\ldots ,\;A_{{i_{k}}}\}$ $T(A_{{i_{1}}},\;A_{{i_{2}}},\;\ldots ,\;A_{{i_{k}}})$

La implementarea unei proiecții, este necesar să se precizeze relația proiectată și un anumit set de atribute ale acesteia, care va deveni titlul celei rezultate.

Când proiecția este efectuată, o tăietură „verticală” a relației operandului este alocată cu distrugerea naturală a tuplurilor duplicate potențiale.

Sintaxă:

A[X, Y, …, Z]

PROIECT A {x, y, …, z}

Conexiune

Operația de unire a relațiilor A și B prin predicatul P este echivalentă logic cu aplicarea secvențială a produsului cartezian al lui A și B și selecția prin predicat P . Dacă în relații există atribute cu aceleași nume, atunci înainte de a efectua unirea, aceste atribute trebuie redenumite.

Sintaxă:

( A ORI B ) UNDE P

Divizia

O relație cu un antet (X 1 , X 2 , …, X n ) și un corp care conține un set de tupluri (x 1 , x 2 , …, x n ) astfel încât pentru toate tuplurile (y 1 , y 2 , … , y m ) ∈ B în raport cu A(X 1 , X 2 , …, X n , Y 1 , Y 2 , …, Y m ) există un tuplu (x 1 , x 2 , …, x n , y 1 , y 2 , …, y m ) .

Sintaxă:

A DIVIDEDE B

Expresibilitatea unor operații în raport cu altele

Unii dintre operatori relaționali pot fi exprimați în termenii altor operatori relaționali.

Alăturați-vă operatorului

Operatorul de unire este definit în termeni de produs cartezian și selectează operatori după cum urmează:

(A ORI B) UNDE X=Y unde X și Y sunt atribute respectiv ale relațiilor A și B cu nume inițial egale. Operator de intersecție

Operatorul de intersecție este exprimat prin scădere după cum urmează:

A INTERSECT B = A MINUS (A MINUS B) operator de divizie

Operatorul de împărțire este exprimat în termeni de scădere, produs cartezian și operatori de proiecție, după cum urmează:

A DIVIDEBY B = A[X] MINUS ((A[X] ORI B) MINUS A)[X]

Implementări

Primul limbaj de interogare bazat pe algebra lui Codd a fost Alpha, dezvoltat de Codd însuși. Ulterior, a fost creat ISBL, iar această lucrare de pionierat a fost lăudată de multe autorități [5] ca arătând o modalitate de a transforma ideea lui Codd într-un limbaj util. Business System 12 a fost un SGBD relațional de scurtă durată care a urmat exemplul ISBL.

În 1998 , Christopher Date și Hugh Darwen au propus un limbaj numit Tutorial D pentru a fi utilizat în predarea teoriei bazelor de date relaționale, acest limbaj de interogare a fost, de asemenea, bazat pe idei din ISBL. Rel este o implementare a Tutorialului D.

Chiar și limbajul de interogare SQL se bazează vag pe algebră relațională, deși operanzii din SQL ( tabele ) nu sunt exact relații și câteva teoreme utile de algebră relațională nu sunt valabile în SQL (poate în detrimentul optimizatorilor și/sau utilizatorilor). Modelul tabelului SQL este un multiset , nu un set . De exemplu, o expresie este o teoremă a algebrei relaționale pe mulțimi, dar nu algebrei relaționale pe mulțimi; pentru studiul algebrei relaționale pe multiseturi, vezi capitolul 5 al manualului „Complete” de Garcia-Molina , Ullman și Widom [6] . $(R\cup S)\setminus T=(R\setminus T)\cup (S\setminus T)$

Note

↑ Introducere în Joinuri . Consultat la 14 noiembrie 2011. Arhivat din original pe 26 noiembrie 2011. (nedefinit)
↑ Data, Christopher. SQL și teoria relațională. Cum să scrieți corect codul în SQL. - Symbol-Plus, 2010
↑ C. Date, Hugh Darwen. Fundamentele viitoarelor sisteme de baze de date. Al treilea Manifest. M: Janus-K, 2004.
↑ Gray, 1989 , p. 188.
↑ CJ Data. Edgar F. Codd - Laureat al Premiului AM Turing . amturing.acm.org . Preluat la 27 decembrie 2020. Arhivat din original la 23 decembrie 2017. (nedefinit)
↑ Hector Garcia-Molina . Sisteme de baze de date: cartea completă / Hector Garcia-Molina , Jeffrey D. Ullman , Jennifer Widom. — al 2-lea. - Pearson Prentice Hall, 2009. - ISBN 978-0-13-187325-4 .

Literatură

Gray P. Logica, algebra si baze de date. - M . : Mashinostroenie, 1989. - S. 188-213. — 368 p.
Data CJ Introducere în sistemele de baze de date = Introducere în sistemele de baze de date. - Ed. a 8-a. - M. : Williams , 2005. - 1328 p. - ISBN 5-8459-0788-8 (rusă) 0-321-19784-4 (engleză).

Link -uri

http://www.citforum.ru/database/dblearn/

Bază de date
Concepte	Model de date relaționale model algebră forma normala Integritate referenţială DB SGBD Model ierarhic model de rețea Orientat pe obiecte DB SGBD SGBD obiect-relațional tranzacţie Jurnal ( proactiv ) Secționarea Segmentarea Depozitare pe coloană
Obiecte	Atitudine Coloană ( virtuală ) Linia Masa Performanţă Procedură stocată Trigger Cursor Index tablespace
Chei	Primar ( surogat ) Extern Potenţial super cheie
SQL	SELECTAȚI INTRODUCE ACTUALIZAȚI ȘTERGE TRUNCHIA COMBINA A TE ALATURA UNIUNE INTERSECT CU EXCEPTIA CREA MODIFICA DROP GRANT COMMIT ROLLBACK
Componente	Limbajul de interogare Optimizator de interogări Planificator de interogări Planul de execuție al interogării Interogați cache-ul ODBC ZGOMOT ADO.NET JDBC