Relationell algebra

Den stabila versionen checkades ut den 29 juli 2022 . Det finns overifierade ändringar i mallar eller .

Relationell algebra är ett slutet system av operationer på relationer i en relationsdatamodell . Relationella algebraoperationer kallas också för relationella operationer .

Den ursprungliga uppsättningen av 8 operationer föreslogs av E. Codd på 1970-talet och inkluderade både operationer som fortfarande är i bruk ( projektion , sammanfogning , etc.) och operationer som inte har kommit i bruk (till exempel uppdelning av relationer).

I utvecklingen av relationsteori och praktik har flera nya relationsoperationer föreslagits, såsom semi-join ( SEMI-JOIN ) och semi-difference, eller anti-semi-join ( ANTI-SEMI-JOIN ) [1] [2 ] , CROSS APPLY och OUTER APPLY , transitiv stängning ( TCLOSE ) etc.

Eftersom många operationer är uttryckbara genom varandra, som en del av relationalgebra, kan flera varianter av basen (en uppsättning operationer genom vilka alla andra är uttryckbara) urskiljas. Den mest kända och strikt definierade grunden ( algebra A ) föreslogs av Christopher Date och Hugh Darwen [3] .

Relationsalgebra och relationskalkyl är ekvivalenta i sin uttryckskraft [4] . Det finns regler för att konvertera förfrågningar mellan dem.

Huvudapplikationen för relationalgebra är att tillhandahålla en teoretisk ram för relationsdatabaser , särskilt frågespråk för sådana databaser, främst SQL .

Sluten relationalgebra

Relationell algebra är en uppsättning operationer på relationer så att resultatet av var och en av operationerna också är en relation. Denna egenskap hos en algebra kallas slutenhet .

Operationer på en relation kallas unär , på två relationer - binära , på tre - ternära (dessa är praktiskt taget okända).

Ett exempel på en unär operation är en projektion, ett exempel på en binär operation är en union.

En N -är relationsoperation f kan representeras av en funktion som returnerar en relation och tar n relationer som argument:

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

Eftersom relationalgebra är stängd kan andra relationella algebrauttryck (lämpliga för typ) ersättas som operander i relationsoperationer:

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

I relationsuttryck kan du använda kapslade uttryck av en godtyckligt komplex struktur.

Begränsningar för operationer

Vissa relationsoperationer, särskilt union , intersection och subtraktion , kräver att relationen har matchande (samma) rubriker (scheman). Det betyder att antalet attribut, namnen på attributen och typen ( domän ) av attributen med samma namn är desamma.

Vissa relationer är inte formellt kompatibla på grund av skillnader i attributnamn, men blir det efter att ha tillämpat funktionen för att byta namn.

Den kartesiska produktoperationen kräver att operandrelationerna inte har attribut med samma namn. Relationer sägs vara kompatibla genom att ta den utökade kartesiska produkten om skärningspunkten mellan uppsättningarna av attributnamn hämtade från deras relationsscheman är tom.

Relationell algebraoperationer

Följande är några operationer av relationalgebra som är av antingen historiskt eller praktiskt intresse. Det är omöjligt att lista alla operationer, eftersom alla operationer som uppfyller definitionen av relationell är en del av den relationella algebra.

Byter namn på

Resultatet av att tillämpa operationen för att byta namn på attribut är en relation med de ändrade attributnamnen.

Syntax :

R BYT DAMN Atr 1 , Atr 2 , … SOM NewAtr 1 , NewAtr 2 , …

var

R - förhållande Atr 1 , Atr 2 , … — initiala attributnamn NewAtr 1 , NewAtr 2 , … är nya attributnamn.

Konsolidering

En relation med samma rubrik som typkompatibla relationer A och B , och en kropp bestående av tupler som tillhör antingen A , B eller båda.
Syntax:

A UNION B

Korsning

En relation med samma titel som relationerna A och B , och en kropp bestående av tupler som tillhör både relationerna A och B samtidigt .
Syntax:

A KORSNING B

Subtraktion

En relation med samma rubrik som typkompatibla relationer A och B , och en kropp bestående av tupler som tillhör relation A och inte tillhör relation B.
Syntax:

A MINUS B

Tilldelningsoperation

Tilldelningsoperatorn (:=) låter dig lagra resultatet av att utvärdera ett relationsuttryck i en befintlig relation.

Kartesisk produkt

En relation vars rubrik ( A 1 , A 2 , …, A n , B 1 , B 2 , …, B m ) är sammanlänkningen av rubrikerna för relationerna A ( A 1 , A 2 , …, A n ) och B ( B 1 , B 2 , …, B m ), och kroppen består av tupler som alla är kombinationer av tupler av relationerna A och B : ( a 1 , a 2 , …, a n , b 1 , b 2 , … , b m ),

Så att

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

Syntax:

A GÅNGER B

Sampling (begränsning)

En relation med samma titel som relation A och en kropp bestående av tupler vars attributvärden utvärderas till TRUE när de ersätts i villkor c . c är ett booleskt uttryck som kan inkludera attribut för relation A och/eller skalära uttryck.
Syntax:

EN VAR c

Provet skrivs som eller där: $\sigma _{a\theta b}(R)$ $\sigma _{a\theta v}(R)$

a och b är attributnamn
θ är en av de binära operationerna ${\displaystyle \{\;<,\leq ,=,\neq ,\geq ,\;>\))$
v är en konstant
R -förhållande

Projektion

Projektion är en unär operation som låter dig få en "vertikal" delmängd av en given relation , eller tabell, det vill säga en sådan delmängd som erhålls genom att välja de specificerade attributen , följt av eliminering, om nödvändigt, av redundanta dubbletter av tupler . Låt en tabell med attributnamn ges , det vill säga någon delmängd av uppsättningen attributnamn . Resultatet av en tabellprojektion på de valda attributnamnen är en ny tabell som erhålls från den ursprungliga tabellen genom att ta bort attribut som inte ingår i den valda uppsättningen, följt av eventuellt borttagande av redundanta dubbletter. $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}}})$

När du implementerar en projektion är det nödvändigt att specificera den projicerade relationen och en viss uppsättning av dess attribut, som kommer att bli titeln på den resulterande.

När projektionen utförs allokeras ett "vertikalt" snitt av operandrelationen med den naturliga förstörelsen av potentiellt uppkomna dubbletter av tupler.

Syntax:

A[X, Y, …, Z]

eller

PROJEKT A {x, y, …, z}

Anslutning

Operationen att sammanfoga relationerna A och B med predikatet P är logiskt ekvivalent med den sekventiella tillämpningen av den kartesiska produkten av A och B och urval av predikatet P . Om det finns attribut med samma namn i relationerna måste dessa attribut bytas om innan kopplingen utförs.

Syntax:

( A GÅNGER B ) DÄR P

Division

En relation med en rubrik (X 1 , X 2 , …, X n ) och en kropp som innehåller en uppsättning tuppel (x 1 , x 2 , …, x n ) så att för alla tupler (y 1 , y 2 , … , y m ) ∈ B med avseende på A(X 1 , X 2 , …, X n , Y 1 , Y 2 , …, Y m ) det finns en tuppel (x 1 , x 2 , …, x n , y 1 , y 2 , …, y m ) .

Syntax:

A DIVIDEBY B

Uttryckbarhet för vissa operationer i termer av andra

Vissa av relationsoperatorerna kan uttryckas i termer av andra relationsoperatorer.

Gå med i operatören

Join-operatören definieras i termer av den kartesiska produkten och välj operatörer enligt följande:

(A GÅNGER B) DÄR X=Y där X och Y är attribut för relationerna A respektive B med initialt lika namn. Korsningsoperatör

Korsningsoperatorn uttrycks via subtraktion enligt följande:

A SKÄRSNING B = A MINUS (A MINUS B) divisionsoperatör

Divisionsoperatorn uttrycks i termer av subtraktion, kartesisk produkt och projektionsoperatorer enligt följande:

A DIVIDEBY B = A[X] MINUS ((A[X] GÅNGER B) MINUS A)[X]

Implementeringar

Det första frågespråket baserat på Codds algebra var Alpha, utvecklat av Codd själv. Därefter skapades ISBL, och detta banbrytande arbete har hyllats av många myndigheter [5] för att visa ett sätt att förvandla Codds idé till ett användbart språk. Affärssystem 12 var ett kortlivat relations-DBMS som följde ISBLs ledning.

1998 föreslog Christopher Date och Hugh Darwen ett språk som heter Tutorial D för användning i undervisning i relationsdatabasteori, detta frågespråk var också baserat på idéer från ISBL. Rel är en implementering av Tutorial D.

Även SQL -frågespråket är löst baserat på relationalgebra, även om operander i SQL ( tabeller ) inte exakt är relationer och flera användbara relationalgebrasatser håller inte i SQL (kanske till nackdel för optimerare och/eller användare). SQL-tabellmodellen är en multiset , inte en uppsättning . Till exempel är ett uttryck en sats för relationalgebra på mängder, men inte relationalgebra på multimängder; för studiet av relationalgebra på multiset, se kapitel 5 i den "fullständiga" läroboken av Garcia-Molina , Ullman och Widom [6] . $(R\cup S)\setminus T=(R\setminus T)\cup (S\setminus T)$

Anteckningar

↑ Introduktion till Joins . Hämtad 14 november 2011. Arkiverad från originalet 26 november 2011. (obestämd)
↑ Datum, Christopher. SQL och relationsteori. Hur man skriver kod i SQL korrekt. - Symbol-Plus, 2010
↑ C. Date, Hugh Darwen. Grunderna i framtida databassystem. Tredje manifestet. M: Janus-K, 2004.
↑ Gray, 1989 , sid. 188.
↑ CJ-datum. Edgar F. Codd-AM Turing-pristagare . amturing.acm.org . Hämtad 27 december 2020. Arkiverad från originalet 23 december 2017. (obestämd)
↑ Hector Garcia-Molina . Databassystem: hela boken / Hector Garcia-Molina , Jeffrey D. Ullman , Jennifer Widom. — 2:a. - Pearson Prentice Hall, 2009. - ISBN 978-0-13-187325-4 .

Litteratur

Grey P. Logik, algebra och databaser. - M . : Mashinostroenie, 1989. - S. 188-213. — 368 sid.
Datum CJ Introduktion till databassystem = Introduktion till databassystem. - 8:e uppl. - M. : Williams , 2005. - 1328 sid. - ISBN 5-8459-0788-8 (ryska) 0-321-19784-4 (engelska).

Länkar

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

Databas
Begrepp	Datamodell relationella modell algebra normal form Referensintegritet DB DBMS Hierarkisk modell nätverksmodell Objektorienterad DB DBMS Objektrelationell DBMS transaktion Journalföring ( proaktiv ) Sektionering Segmentering Kolumnlagring
Objekt	Attityd Kolumn ( virtuell ) Linje Tabell Prestanda Lagrad procedur Utlösare Markör Index bordsutrymme
Nycklar	Primär ( surrogat ) Extern Potential supernyckel
SQL	VÄLJ FÖRA IN UPPDATERING RADERA STYMPA SAMMANFOGA ANSLUTA SIG UNION KORSAS BORTSETT FRÅN SKAPA ÄNDRA SLIPPA GRANT BEGÅ RULLA TILLBAKA
Komponenter	Frågespråk Frågeoptimerare Frågeplanerare Utförandeplan för frågor Fråga cache ODBC VÄSEN ADO.NET JDBC