Algèbre relationnelle - Relational algebra

Dans la théorie des bases de données , l' algèbre relationnelle est une théorie qui utilise des structures algébriques avec une sémantique bien fondée pour modéliser des données et définir des requêtes dessus. La théorie a été introduite par Edgar F. Codd .

La principale application de l'algèbre relationnelle est de fournir une base théorique pour les bases de données relationnelles , en particulier les langages de requête pour ces bases de données, dont le principal est SQL . Les bases de données relationnelles stockent des données tabulaires représentées sous forme de relations . Les requêtes sur les bases de données relationnelles renvoient souvent également des données tabulaires représentées sous forme de relations. La prémisse principale de l'algèbre relationnelle est de définir des opérateurs qui transforment une ou plusieurs relations d'entrée en une relation de sortie. Étant donné que ces opérateurs acceptent des relations en entrée et produisent des relations en sortie, ils peuvent être combinés et utilisés pour exprimer des requêtes potentiellement complexes qui transforment potentiellement de nombreuses relations d'entrée (dont les données sont stockées dans la base de données) en une seule relation de sortie (les résultats de la requête) . Les opérateurs unaires acceptent en entrée une seule relation ; les exemples incluent des opérateurs pour filtrer certains attributs (colonnes) ou tuples (lignes) à partir d'une relation d'entrée. Les opérateurs binaires acceptent en entrée deux relations ; de tels opérateurs combinent les deux relations d'entrée en une seule relation de sortie, par exemple en prenant tous les tuples trouvés dans l'une ou l'autre relation, en supprimant les tuples de la première relation trouvée dans la seconde relation, en étendant les tuples de la première relation avec les tuples dans la seconde relation répondant à certaines conditions, et ainsi de suite. D'autres opérateurs plus avancés peuvent également être inclus, où l'inclusion ou l'exclusion de certains opérateurs donne lieu à une famille d'algèbres.

introduction

Algèbre relationnelle a reçu peu d' attention en dehors des mathématiques pures jusqu'à la publication des EF Codd du modèle relationnel de données en 1970. Codd a proposé une telle algèbre comme base pour les langages de requête de base de données. (Voir la section Implémentations .)

Les cinq opérateurs primitifs de l'algèbre de Codd sont la sélection , la projection , le produit cartésien (également appelé produit croisé ou jointure croisée ), l' ensemble union et l' ensemble différence .

Définir les opérateurs

L'algèbre relationnelle utilise l' union des ensembles , la différence des ensembles et le produit cartésien de la théorie des ensembles , mais ajoute des contraintes supplémentaires à ces opérateurs.

Pour l'union d'ensembles et la différence d'ensembles, les deux relations impliquées doivent être compatibles avec l'union, c'est-à- dire que les deux relations doivent avoir le même ensemble d'attributs. Parce que l' intersection d'ensembles est définie en termes d'union d'ensembles et de différence d'ensembles, les deux relations impliquées dans l'intersection d'ensembles doivent également être compatibles avec l'union.

Pour que le produit cartésien soit défini, les deux relations impliquées doivent avoir des en-têtes disjoints, c'est-à-dire qu'elles ne doivent pas avoir un nom d'attribut commun.

De plus, le produit cartésien est défini différemment de celui de la théorie des ensembles dans le sens où les tuples sont considérés comme « superficiels » aux fins de l'opération. C'est-à-dire que le produit cartésien d'un ensemble de n -uplets avec un ensemble de m -uplets donne un ensemble de -uplets « aplatis » ( n  +  m ) (alors que la théorie des ensembles de base aurait prescrit un ensemble de 2-uplets, chacun contenant un n -uplet et un m -uplet). Plus formellement, R × S est défini comme suit :

${\displaystyle R\times S:=\{(r_{1},r_{2},\dots ,r_{n},s_{1},s_{2},\dots ,s_{m})|( r_{1},r_{2},\dots ,r_{n})\in R,(s_{1},s_{2},\dots ,s_{m})\in S\}}$

La cardinalité du produit cartésien est le produit des cardinalités de ses facteurs, c'est-à-dire | R × S | = | R | × | S |.

Projection ( Π )

Une projection est une opération unaire écrite sous la forme où est un ensemble de noms d'attributs. Le résultat d'une telle projection est défini comme l' ensemble obtenu lorsque tous les tuples de R sont restreints à l'ensemble . ${\displaystyle \Pi _{a_{1},\ldots ,a_{n}}(R)}$${\displaystyle a_{1},\ldots ,a_{n}}$${\displaystyle \{a_{1},\ldots ,a_{n}\}}$

Remarque : lorsqu'elle est implémentée dans le standard SQL , la "projection par défaut" renvoie un multi-ensemble au lieu d'un ensemble, et la projection Π pour éliminer les données en double est obtenue par l'ajout du DISTINCTmot - clé .

Sélection ( σ )

Une sélection généralisée est une opération unaire écrite, où φ est une formule propositionnelle qui se compose d' atomes comme admis dans la sélection normale et les opérateurs logiques ( et ), ( ou ) et ( négation ). Cette sélection sélectionne tous les tuples dans R pour lesquels est vérifié . ${\displaystyle \sigma _{\varphi }(R)}$${\displaystyle \wedge }$${\style d'affichage \lor }$${\style d'affichage \neg }$

Pour obtenir une liste de tous les amis ou associés dans un carnet d'adresses, la sélection peut être écrite sous la forme . Le résultat serait une relation contenant chaque attribut de chaque enregistrement unique où isFriend est vrai ou où isBusinessContact est vrai. ${\displaystyle \sigma _{{\text{isFriend = true}}\,\lor \,{\text{isBusinessContact = true}}}({\text{addressBook}})}$

Renommer ( ρ )

Un changement de nom est une opération unaire écrit où le résultat est identique à R , sauf que le b attribut dans tous les tuples est renommé à un un attribut. Ceci est simplement utilisé pour renommer l'attribut d'une relation ou la relation elle-même. ${\style d'affichage \rho _{a/b}(R)}$

Pour renommer l'attribut 'isFriend' en 'isBusinessContact' dans une relation, peut être utilisé. ${\displaystyle \rho _{\text{isBusinessContact / isFriend}}({\text{addressBook}})}$

Il y a aussi la notation, où R est renommé en x et les attributs sont renommés en . ${\displaystyle \rho _{x(A_{1},\ldots ,A_{n})}(R)}$${\displaystyle \{a_{1},\ldots ,a_{n}\}}$${\displaystyle \{A_{1},\ldots ,A_{n}\}}$

Jointures et opérateurs de type jointure

Jointure naturelle (⋈ )

La jointure naturelle (⋈) est un opérateur binaire qui s'écrit ( R ⋈ S ) où R et S sont des relations . Le résultat de la jointure naturelle est l'ensemble de toutes les combinaisons de tuples dans R et S qui sont égales sur leurs noms d'attributs communs. Par exemple, considérons les tables Employee et Dept et leur jointure naturelle :

Notez que ni l'employée nommée Mary ni le service des ressources humaines n'apparaissent dans le résultat.

Cela peut également être utilisé pour définir la composition des relations . Par exemple, la composition de Employee et Dept est leur jointure comme indiqué ci-dessus, projetée sur tout sauf l'attribut commun DeptName . Dans la théorie des catégories , la jointure est précisément le produit de la fibre .

La jointure naturelle est sans doute l'un des opérateurs les plus importants car c'est la contrepartie relationnelle de l'opérateur logique AND. Notez que si la même variable apparaît dans chacun des deux prédicats qui sont connectés par AND, alors cette variable représente la même chose et les deux apparences doivent toujours être remplacées par la même valeur (c'est une conséquence de l' idempotence du AND logique) . En particulier, la jointure naturelle permet la combinaison de relations associées par une clé étrangère . Par exemple, dans l'exemple ci-dessus, une clé étrangère contient probablement de Employee . DeptName à Dept . DeptName , puis la jointure naturelle de Employee et Dept combine tous les employés avec leurs départements. Cela fonctionne car la clé étrangère est conservée entre des attributs portant le même nom. Si ce n'est pas le cas comme dans la clé étrangère de Dept . Gestionnaire à employé . Name puis ces colonnes doivent être renommées avant de prendre la jointure naturelle. Une telle jointure est parfois aussi appelée équijointure (voir θ -join).

Plus formellement, la sémantique de la jointure naturelle est définie comme suit :

${\displaystyle R\bowtie S=\left\{r\cup s\ \vert \ r\in R\ \land \ s\in S\ \land \ {\mathit {Fun}}(r\cup s)\ droit\}}$

( 1 )

où Fun(t) est un prédicat qui est vrai pour une relation t (au sens mathématique) ssi t est une fonction. Il est généralement exigé que R et S aient au moins un attribut commun, mais si cette contrainte est omise et que R et S n'ont pas d'attributs communs, alors la jointure naturelle devient exactement le produit cartésien.

La jointure naturelle peut être simulée avec les primitives de Codd comme suit. Supposons que c ₁ , ..., c _m sont les noms d'attributs communs à R et S , r ₁ , ..., r _n sont les noms d'attributs propres à R et s ₁ , ..., de _k sont l'attribut noms propres à S . De plus, supposons que les noms d'attributs x ₁ ,..., x _m ne sont ni dans R ni dans S . Dans une première étape, les noms d'attributs communs dans S peuvent être modifiés :

${\displaystyle T=\rho _{x_{1}/c_{1},\ldots ,x_{m}/c_{m}}(S)=\rho _{x_{1}/c_{1}} (\rho _{x_{2}/c_{2}}(\ldots \rho _{x_{m}/c_{m}}(S)\ldots ))}$

( 2 )

Ensuite, nous prenons le produit cartésien et sélectionnons les tuples à joindre :

${\displaystyle P=\sigma _{c_{1}=x_{1},\ldots ,c_{m}=x_{m}}(R\times T)=\sigma _{c_{1}=x_{ 1}}(\sigma _{c_{2}=x_{2}}(\ldots \sigma _{c_{m}=x_{m}}(R\times T)\ldots ))}$

( 3 )

Enfin on fait une projection pour se débarrasser des attributs renommés :

${\displaystyle U=\Pi _{r_{1},\ldots ,r_{n},c_{1},\ldots ,c_{m},s_{1},\ldots ,s_{k}}(P )}$

( 4 )

θ -join et équijointure

Considérez les tableaux Car et Boat qui répertorient les modèles de voitures et de bateaux et leurs prix respectifs. Supposons qu'un client veuille acheter une voiture et un bateau, mais qu'il ne veuille pas dépenser plus d'argent pour le bateau que pour la voiture. Le θ -join (⋈ _θ ) sur le prédicat CarPrice ≥ BoatPrice produit le aplaties paires de lignes qui satisfont le prédicat. Lors de l'utilisation d'une condition où les attributs sont égaux, par exemple Price, la condition peut être spécifiée comme Price = Price ou alternativement ( Price ) elle-même.

Afin de combiner tuples de deux relations où la condition de combinaison est non seulement l'égalité des attributs communs , il est pratique d'avoir une forme plus générale de se joindre à l' opérateur, qui est le θ -join (ou theta-jointure). La θ- jointure est un opérateur binaire qui s'écrit comme ou où a et b sont des noms d'attributs, θ est un opérateur relationnel binaire dans l'ensemble {<, ≤, =, ≠, >, } , υ est une valeur constante, et R et S sont des relations. Le résultat de cette opération consiste à toutes les combinaisons de tuples en R et S qui répondent thetav . Le résultat de l' θ -join est défini que si les en- têtes de S et R sont disjoints, qui est, ne contiennent pas un attribut commun. ${\displaystyle {R\ \bowtie \ S \atop a\ \theta \ b}}$${\displaystyle {R\ \bowtie \ S \atop a\ \theta \ v}}$

La simulation de cette opération dans les opérations fondamentales est donc la suivante :

R ⋈ _{& thetav} S = σ _{& thetav} ( R × S )

Dans le cas où l'opérateur θ est l'opérateur d'égalité (=) alors cette jointure est également appelée équijointure .

Notez cependant qu'un langage informatique qui prend en charge les NATURAL JOIN et les opérateurs de sélection n'a pas besoin thetav -join aussi bien, car cela peut être réalisé par la sélection du résultat d'une jointure naturelle (qui dégénérés au produit cartésien lorsqu'il n'y a pas partagés les attributs).

Dans les implémentations SQL, la jointure sur un prédicat est généralement appelée une jointure interne , et le mot-clé on permet de spécifier le prédicat utilisé pour filtrer les lignes. Il est important de noter : former le produit cartésien aplati puis filtrer les lignes est conceptuellement correct, mais une implémentation utiliserait des structures de données plus sophistiquées pour accélérer la requête de jointure.

Semi-jointure (⋉)(⋊)

La gauche est une semi - jointure similaire à se joindre à la jointure naturelle et écrite comme R ⋉ S où R et S sont des relations . Le résultat est l'ensemble de tous les tuples dans R pour lesquels il existe un tuple dans S qui est égal sur leurs noms d'attributs communs. La différence avec une jointure naturelle est que les autres colonnes de S n'apparaissent pas. Par exemple, considérons les tables Employee et Dept et leur semi-jointure :

Plus formellement, la sémantique de la semi-jointure peut être définie comme suit :

R ⋉ S = { t  : t ∈ R ∧ ∃ s ∈ S ( Fun ( t ∪ s )) }

où Fun ( r ) est comme dans la définition de la jointure naturelle.

La semi-jointure peut être simulée en utilisant la jointure naturelle comme suit. Si a ₁ , ..., a _n sont les noms d'attributs de R , alors

R ⋉ S = _{a 1 , .., a n} ( R ⋈ S ).${\style d'affichage \Pi }$

Puisque nous pouvons simuler la jointure naturelle avec les opérateurs de base, il s'ensuit que cela vaut également pour la semi-jointure.

Dans l'article de Codd de 1970, la semi-jointure est appelée restriction.

Anti-jointure (▷)

Le antijoin, écrit R ▷ S où R et S sont des relations , est similaire à la semi - jointure, mais le résultat d'un antijoin est que les tuples dans R pour lesquels il n'y a pas tuple en S qui est égale à leurs noms d'attributs communs.

Par exemple, considérons les tables Employee et Dept et leur antijointure :

L'antijointure est formellement définie comme suit :

R ▷ S = { t  : t ∈ R ∧ ¬∃ s ∈ S ( Fun ( t ∪ s )) }

ou

R ▷ S = { t  : t ∈ R , il n'y a pas tuple s de S qui satisfait Fun ( t ∪ s )}

où Fun ( t ∪ s ) comme dans la définition de jointure naturelle.

L'antijointure peut également être définie comme le complément de la semi-jointure, comme suit :

R ▷ S = R  -  R ⋉ S

( 5 )

Compte tenu de cela, l'anti-jointure est parfois appelée anti-semi-jointure, et l'opérateur d'anti-jointure est parfois écrit sous forme de symbole de semi-jointure avec une barre au-dessus, au lieu de ▷.

Division (÷)

La division est une opération binaire qui est écrit en tant que R ÷ S . La division n'est pas implémentée directement dans SQL. Le résultat consiste en les restrictions des tuples dans R aux noms d'attributs uniques à R , c'est-à-dire dans l'en-tête de R mais pas dans l'en-tête de S , pour lesquels il considère que toutes leurs combinaisons avec les tuples dans S sont présentes dans R . Pour un exemple voir les tables Completed , DBProject et leur division :

Si DBProject contient toutes les tâches du projet de base de données, le résultat de la division ci-dessus contient exactement les étudiants qui ont terminé les deux tâches du projet de base de données. Plus formellement, la sémantique de la division est définie comme suit :

R ÷ S = { t [ a 1 , ..., a n ]: t ∈ R ∧ ∀ s ∈ S (( t [ a 1 , ..., a n ] ∪ s ) ∈ R )}

( 6 )

où { a ₁ ,..., a _n } est l'ensemble des noms d'attributs uniques à R et t [ a ₁ ,..., a _n ] est la restriction de t à cet ensemble. Il est généralement nécessaire que les noms d'attribut dans l'en-tête de S soient un sous-ensemble de ceux de R car sinon le résultat de l'opération sera toujours vide.

La simulation de la division avec les opérations de base est la suivante. On suppose que a ₁ ,..., a _n sont les noms d'attributs propres à R et b ₁ ,..., b _m sont les noms d'attributs de S . Dans la première étape, nous projetons R sur ses noms d'attributs uniques et construisons toutes les combinaisons avec des tuples dans S :

T  := _{a 1 ,..., a n} ( R ) × S

Dans l'exemple précédent, T représenterait une table telle que chaque étudiant (car l'étudiant est la clé/l'attribut unique de la table terminée) est combiné avec chaque tâche donnée. Ainsi, Eugene, par exemple, aurait deux lignes, Eugene → Database1 et Eugene → Database2 dans T.

EG : Tout d'abord, supposons que « Terminé » a un troisième attribut appelé « note ». C'est un bagage indésirable ici, donc nous devons toujours le projeter. En fait, dans cette étape, nous pouvons également supprimer « Tâche » de R ; le multiplicateur le remet.

T  := π _Student ( R ) × S // Cela nous donne toutes les combinaisons souhaitées possibles, y compris celles qui n'existent pas réellement dans R, et en excluant les autres (par exemple Fred | compilateur1, qui n'est pas une combinaison souhaitée)

Dans l'étape suivante, nous soustrayons R de T

rapport :

U  := T − R

Dans U, nous avons les combinaisons possibles qui « auraient pu » être dans R , mais ne l'étaient pas.

EG : Encore une fois avec les projections — T et R doivent avoir des noms d'attributs/en-têtes identiques.

U  := T − π _Student,Task ( R ) // Cela nous donne une liste de "ce qui manque".

Donc si nous prenons maintenant la projection sur les noms d'attributs uniques à R

alors on a les restrictions des tuples dans R pour lesquelles toutes les combinaisons avec des tuples dans S n'étaient pas présentes dans R :

V  := _{a 1 ,..., a n} ( U )

EX : Projet U jusqu'au(x) seul(s) attribut(s) en question (Étudiant)

V  := π _Étudiant ( U )

Il reste donc à faire la projection de R sur ses noms d'attributs uniques et à soustraire ceux de V :

W  := _{a 1 ,..., a n} ( R ) − V

EG : W  := π _Étudiant ( R ) − V .

Extensions communes

En pratique, l'algèbre relationnelle classique décrite ci-dessus est étendue avec diverses opérations telles que les jointures externes, les fonctions d'agrégat et même la fermeture transitive.

Jointures externes

Alors que le résultat d'une jointure (ou jointure interne) consiste en des tuples formés en combinant des tuples correspondants dans les deux opérandes, une jointure externe contient ces tuples et en plus des tuples formés en étendant un tuple sans correspondance dans l'un des opérandes par des valeurs de "remplissage". pour chacun des attributs de l'autre opérande. Les jointures externes ne sont pas considérées comme faisant partie de l'algèbre relationnelle classique discutée jusqu'à présent.

Les opérateurs définis dans la présente section supposent l'existence d'une nulle valeur, ω , que nous ne définissons pas, à utiliser pour les valeurs de remplissage; en pratique cela correspond au NULL en SQL. Afin de rendre les opérations de sélection ultérieures sur la table résultante significatives, une signification sémantique doit être attribuée aux valeurs NULL ; dans l'approche de Codd, la logique propositionnelle utilisée par la sélection est étendue à une logique à trois valeurs , bien que nous éliminions ces détails dans cet article.

Trois opérateurs de jointure externe sont définis : jointure externe gauche, jointure externe droite et jointure externe complète. (Le mot « extérieur » est parfois omis.)

Jointure externe gauche (⟕)

La jointure externe gauche est écrit sous la forme R ⟕ S où R et S sont des relations . Le résultat de la jointure externe gauche est l'ensemble de toutes les combinaisons de tuples dans R et S qui sont égaux sur leurs noms d'attributs communs, en plus (en gros) de tuples dans R qui n'ont pas de tuples correspondants dans S .

Par exemple, considérons les tables Employee et Dept et leur jointure externe gauche :

Dans la relation obtenue, tuples en S qui ne présentent pas de valeurs communes dans les noms d'attributs communs avec tuples dans R prennent une nulle valeur, ω .

Comme il n'y a pas tuples en département avec un DEPTNAME des finances ou de la direction , co s se produisent dans la relation résultant où tuples employés ont un DEPTNAME des finances ou de la direction .

Soient r ₁ , r ₂ , ..., r _n les attributs de la relation R et soit {( ω , ..., ω )} la relation singleton sur les attributs propres à la relation S (ceux qui ne sont pas des attributs de R ). Ensuite, la jointure externe gauche peut être décrite en termes de jointure naturelle (et donc en utilisant des opérateurs de base) comme suit :

${\displaystyle (R\bowtie S)\cup ((R-\pi _{r_{1},r_{2},\dots ,r_{n}}(R\bowtie S))\times \{(\ oméga ,\points \omega )\})}$

Jointure externe droite (⟖)

La jointure externe droite se comporte presque de manière identique à la jointure externe gauche, mais les rôles des tables sont inversés.

La jointure externe droite des relations R et S est écrit sous la forme R ⟖ S . Le résultat de la jointure externe droite est l'ensemble de toutes les combinaisons de tuples dans R et S qui sont égaux sur leurs noms d'attributs communs, en plus des tuples dans S qui n'ont pas de tuples correspondants dans R .

Par exemple, considérons les tables Employee et Dept et leur jointure externe droite :

Dans la relation résultante, tuples dans R qui ne présentent pas de valeurs communes dans les noms d'attributs communs avec tuples en S prennent une nulle valeur, ω .

Comme il n'y a pas tuples employé avec un DEPTNAME de production , co s se produisent dans le nom et EMPID attributs de la relation résultant où tuples en département avaient DEPTNAME de production .

Soient s ₁ , s ₂ , ..., s _n les attributs de la relation S et soit {( ω , ..., ω )} la relation singleton sur les attributs propres à la relation R (ceux qui ne sont pas des attributs de S ). Ensuite, comme pour la jointure externe gauche, la jointure externe droite peut être simulée à l'aide de la jointure naturelle comme suit :

${\displaystyle (R\bowtie S)\cup (\{(\omega ,\dots ,\omega )\}\times (S-\pi _{s_{1},s_{2},\dots ,s_{ n}}(R\nœud papillon S)))}$

Jointure externe complète (⟗)

La jointure externe ou la jointure externe complète combine en effet les résultats des jointures externes gauche et droite.

La jointure externe est écrit sous la forme R ⟗ S où R et S sont des relations . Le résultat de la jointure externe complète est l'ensemble de toutes les combinaisons de tuples dans R et S qui sont égaux sur leurs noms d'attributs communs, en plus des tuples dans S qui n'ont pas de tuples correspondants dans R et des tuples dans R qui n'ont pas de tuples correspondants dans S dans leurs noms d'attributs communs.

Par exemple, considérons les tables Employee et Dept et leur jointure externe complète :

Dans la relation résultante, tuples dans R qui ne présentent pas de valeurs communes dans les noms d'attributs communs avec tuples en S prennent une nulle valeur, ω . Les tuples de S qui ne présentent pas de valeurs communes dans les noms d'attributs communs avec tuples dans R prennent également une nulle valeur, ω .

La jointure externe complète peut être simulée à l'aide des jointures externes gauche et droite (et donc de la jointure naturelle et de l'union définie) comme suit :

R ⟗ S = ( R ⟕ S ) ∪ ( R ⟖ S )

Opérations pour les calculs de domaine

Il n'y a rien dans l'algèbre relationnelle introduit jusqu'à présent qui permettrait des calculs sur les domaines de données (autre que l'évaluation des expressions propositionnelles impliquant l'égalité). Par exemple, il n'est pas possible d'utiliser uniquement l'algèbre introduite jusqu'ici pour écrire une expression qui multiplierait les nombres de deux colonnes, par exemple un prix unitaire avec une quantité pour obtenir un prix total. Les langages de requêtes pratiques ont de telles facilités, par exemple le SQL SELECT permet aux opérations arithmétiques de définir de nouvelles colonnes dans le résultat , et une facilité similaire est fournie plus explicitement par le mot-clé du didacticiel D. Dans la théorie des bases de données, cela s'appelle la projection étendue . SELECT unit_price * quantity AS total_price FROM tEXTEND

Agrégation

De plus, le calcul de diverses fonctions sur une colonne, comme la sommation de ses éléments, n'est pas non plus possible en utilisant l'algèbre relationnelle introduite jusqu'ici. Cinq fonctions d'agrégation sont incluses dans la plupart des systèmes de bases de données relationnelles. Ces opérations sont Sum, Count, Average, Maximum et Minimum. En algèbre relationnelle l'opération d'agrégation sur un schéma ( A ₁ , A ₂ , ... A _n ) s'écrit comme suit :

${\displaystyle G_{1},G_{2},\ldots ,G_{m}\ g_{f_{1}({A_{1}}'),f_{2}({A_{2}}') ,\ldots ,f_{k}({A_{k}}')}\ (r)}$

où chaque A _j ', 1 ≤ j ≤ k , est l'un des attributs originaux A _i , 1 ≤ i ≤ n .

Les attributs précédant le g sont des attributs de regroupement, qui fonctionnent comme une clause "group by" en SQL. Ensuite, il existe un nombre arbitraire de fonctions d'agrégation appliquées à des attributs individuels. L'opération est appliquée à une relation arbitraire r . Les attributs de regroupement sont facultatifs, et s'ils ne sont pas fournis, les fonctions d'agrégation sont appliquées sur l'ensemble de la relation à laquelle l'opération est appliquée.

Supposons que nous ayons une table nommée Account avec trois colonnes, à savoir Account_Number, Branch_Name et Balance . Nous souhaitons trouver le solde maximum de chaque branche. Ceci est accompli par _{Branch_Name} G _{Max( Balance )} ( Account ). Pour trouver le solde le plus élevé de tous les comptes quelle que soit la branche, nous pourrions simplement écrire G _{Max( Balance )} ( Account ).

Le regroupement est souvent écrit sous la forme _{Branch_Name} ɣ _{Max( Balance )} ( Account ) à la place.

Fermeture transitive

Bien que l'algèbre relationnelle semble assez puissante pour la plupart des objectifs pratiques, il existe des opérateurs simples et naturels sur les relations qui ne peuvent pas être exprimés par l'algèbre relationnelle. L'un d'eux est la fermeture transitive d'une relation binaire. Étant donné un domaine D , soit la relation binaire R un sous-ensemble de D × D . La clôture transitive R ⁺ de R est le plus petit sous-ensemble de D × D qui contient R et satisfait la condition suivante :

${\displaystyle \forall x\forall y\forall z\left((x,y)\in R^{+}\wedge (y,z)\in R^{+}\Rightarrow (x,z)\in R^{+}\droit)}$

Il n'y a pas d'expression d'algèbre relationnelle E ( R ) prenant R comme argument variable qui produit R ⁺ . Cela peut être prouvé en utilisant le fait que, étant donné une expression relationnelle E pour laquelle on prétend que E ( R ) = R ⁺ , où R est une variable, nous pouvons toujours trouver une instance r de R (et un domaine correspondant d ) tel que E ( r ) r ⁺ .

SQL prend cependant officiellement en charge de telles requêtes de point fixe depuis 1999, et il avait des extensions spécifiques aux fournisseurs dans cette direction bien avant cela.

Utilisation de propriétés algébriques pour l'optimisation des requêtes

Les requêtes peuvent être représentées sous la forme d'un arbre , où

• les nœuds internes sont des opérateurs,
• les feuilles sont des relations ,
• les sous-arbres sont des sous-expressions.

L'objectif principal est de transformer les arbres d'expression en équivalent arbres d'expression , où la taille moyenne des rapports produits par des sous - expressions dans l'arbre est plus petit qu'il ne l' était avant l' optimisation . L'objectif secondaire est d'essayer de former des sous-expressions communes au sein d'une seule requête, ou s'il y a plusieurs requêtes en cours d'évaluation en même temps, dans toutes ces requêtes. La raison d'être du deuxième objectif est qu'il suffit de calculer une seule fois les sous-expressions communes et que les résultats peuvent être utilisés dans toutes les requêtes contenant cette sous-expression.

Voici un ensemble de règles qui peuvent être utilisées dans de telles transformations.

Sélection

Les règles concernant les opérateurs de sélection jouent le rôle le plus important dans l'optimisation des requêtes. La sélection est un opérateur qui diminue très efficacement le nombre de lignes dans son opérande, donc si les sélections dans un arbre d'expression sont déplacées vers les feuilles, les relations internes (générées par les sous-expressions) vont probablement diminuer.

Propriétés de sélection de base

La sélection est idempotente (plusieurs applications de la même sélection n'ont pas d'effet supplémentaire au-delà de la première) et commutative (l'ordre dans lequel les sélections sont appliquées n'a aucun effet sur le résultat final).

1. ${\displaystyle \sigma _{A}(R)=\sigma _{A}\sigma _{A}(R)\,\!}$
2. ${\displaystyle \sigma _{A}\sigma _{B}(R)=\sigma _{B}\sigma _{A}(R)\,\!}$

Briser les sélections avec des conditions complexes

Une sélection dont la condition est une conjonction de conditions plus simples est équivalente à une séquence de sélections avec ces mêmes conditions individuelles, et une sélection dont la condition est une disjonction est équivalente à une union de sélections. Ces identités peuvent être utilisées pour fusionner des sélections afin que moins de sélections doivent être évaluées, ou pour les diviser afin que les sélections de composants puissent être déplacées ou optimisées séparément.

1. ${\displaystyle \sigma _{A\land B}(R)=\sigma _{A}(\sigma _{B}(R))=\sigma _{B}(\sigma _{A}(R) )}$
2. ${\displaystyle \sigma _{A\lor B}(R)=\sigma _{A}(R)\cup \sigma _{B}(R)}$

Sélection et produit croisé

Le produit croisé est l'opérateur le plus coûteux à évaluer. Si les relations d' entrée ont N et M lignes, le résultat contiendra des lignes. Par conséquent, il est important de réduire la taille des deux opérandes avant d'appliquer l'opérateur de produit croisé. ${\style d'affichage NM}$

Cela peut être fait efficacement si le produit vectoriel est suivi d'un opérateur de sélection, par exemple . Compte tenu de la définition de jointure, c'est le cas le plus probable. Si le produit croisé n'est pas suivi d'un opérateur de sélection, nous pouvons essayer d'abaisser une sélection à partir des niveaux supérieurs de l'arbre d'expression en utilisant les autres règles de sélection. ${\displaystyle \sigma _{A}(R\fois P)}$

Dans le cas ci-dessus, la condition A est décomposée en conditions B , C et D en utilisant les règles de division concernant les conditions de sélection complexes, de sorte que et B contient uniquement les attributs de R , C contient les attributs uniquement de P , et D contient la partie de A qui contient les attributs de R et P . Notez que B , C ou D sont éventuellement vides. Ensuite, ce qui suit est valable : ${\displaystyle A=B\coin C\coin D}$

${\displaystyle \sigma _{A}(R\times P)=\sigma _{B\wedge C\wedge D}(R\times P)=\sigma _{D}(\sigma _{B}(R )\fois \sigma _{C}(P))}$

Opérateurs de sélection et d'ensemble

La sélection est distributive sur les opérateurs de différence, d'intersection et d'union définis. Les trois règles suivantes sont utilisées pour pousser la sélection sous les opérations définies dans l'arbre d'expression. Pour l'ensemble différence et les opérateurs d'intersection, il est possible d'appliquer l'opérateur de sélection à un seul des opérandes suite à la transformation. Cela peut être avantageux lorsque l'un des opérandes est petit et que la surcharge de l'évaluation de l'opérateur de sélection l'emporte sur les avantages de l'utilisation d'une relation plus petite comme opérande.

1. ${\displaystyle \sigma _{A}(R\setminus P)=\sigma _{A}(R)\setminus \sigma _{A}(P)=\sigma _{A}(R)\setminus P}$
2. ${\displaystyle \sigma _{A}(R\cup P)=\sigma _{A}(R)\cup \sigma _{A}(P)}$
3. ${\displaystyle \sigma _{A}(R\cap P)=\sigma _{A}(R)\cap \sigma _{A}(P)=\sigma _{A}(R)\cap P= R\cap \sigma _{A}(P)}$

Sélection et projection

La sélection commute avec la projection si et seulement si les champs référencés dans la condition de sélection sont un sous-ensemble des champs de la projection. Effectuer une sélection avant la projection peut être utile si l'opérande est un produit croisé ou une jointure. Dans d'autres cas, si la condition de sélection est relativement coûteuse à calculer, déplacer la sélection en dehors de la projection peut réduire le nombre de tuples qui doivent être testés (puisque la projection peut produire moins de tuples en raison de l'élimination des doublons résultant de champs omis).

${\displaystyle \pi _{a_{1},\ldots ,a_{n}}(\sigma _{A}(R))=\sigma _{A}(\pi _{a_{1},\ldots ,a_{n}}(R)){\text{ où les champs dans }}A\subseteq \{a_{1},\ldots ,a_{n}\}}$

Projection

Propriétés de projection de base

La projection est idempotente, de sorte qu'une série de projections (valides) est équivalente à la projection la plus externe.

${\displaystyle \pi _{a_{1},\ldots ,a_{n}}(\pi _{b_{1},\ldots ,b_{m}}(R))=\pi _{a_{1 },\ldots ,a_{n}}(R){\text{ où }}\{a_{1},\ldots ,a_{n}\}\subseteq \{b_{1},\ldots ,b_{ m}\}}$

Opérateurs de projection et de décor

La projection est distributive sur l'union des ensembles.

${\displaystyle \pi _{a_{1},\ldots ,a_{n}}(R\cup P)=\pi _{a_{1},\ldots ,a_{n}}(R)\cup \ pi _{a_{1},\ldots ,a_{n}}(P).\,}$

La projection ne se répartit pas sur l'intersection et la différence définie. Des contre-exemples sont donnés par :

${\displaystyle \pi _{A}(\{\langle A=a,B=b\rangle \}\cap \{\langle A=a,B=b'\rangle \})=\emptyset }$

${\displaystyle \pi _{A}(\{\langle A=a,B=b\rangle \})\cap \pi _{A}(\{\langle A=a,B=b'\rangle \ })=\{\langle A=a\rangle \}}$

et

${\displaystyle \pi _{A}(\{\langle A=a,B=b\rangle \}\setminus \{\langle A=a,B=b'\rangle \})=\{\langle A =un\rangle \}}$

${\displaystyle \pi _{A}(\{\langle A=a,B=b\rangle \})\setminus \pi _{A}(\{\langle A=a,B=b'\rangle \ })=\emptyset \,,}$

où b est supposé distinct de b' .

Renommer

Propriétés de renommage de base

Les renommages successifs d'une variable peuvent être regroupés en un seul renommage. Les opérations de renommage qui n'ont pas de variables en commun peuvent être arbitrairement réordonnées les unes par rapport aux autres, ce qui peut être exploité pour rendre les renommages successifs adjacents afin qu'ils puissent être regroupés.

1. ${\displaystyle \rho _{a/b}(\rho _{b/c}(R))=\rho _{a/c}(R)\,\!}$
2. ${\displaystyle \rho _{a/b}(\rho _{c/d}(R))=\rho _{c/d}(\rho _{a/b}(R))\,\! }$

Renommer et définir des opérateurs

Renommer est distributif sur la différence, l'union et l'intersection de l'ensemble.

1. ${\displaystyle \rho _{a/b}(R\setminus P)=\rho _{a/b}(R)\setminus \rho _{a/b}(P)}$
2. ${\displaystyle \rho _{a/b}(R\cup P)=\rho _{a/b}(R)\cup \rho _{a/b}(P)}$
3. ${\displaystyle \rho _{a/b}(R\cap P)=\rho _{a/b}(R)\cap \rho _{a/b}(P)}$

Produit et union

Le produit cartésien est distributif sur l'union.

1. ${\displaystyle (A\fois B)\cup (A\fois C)=A\fois (B\coupe C)}$

Implémentations

Le premier langage de requête basé sur l'algèbre de Codd était Alpha, développé par le Dr Codd lui-même. Par la suite, l' ISBL a été créé, et ce travail pionnier a été salué par de nombreuses autorités comme ayant montré la voie pour faire de l'idée de Codd un langage utile. Business System 12 était un SGBD relationnel de courte durée, puissant dans l'industrie, qui suivait l'exemple de l'ISBL.

En 1998, Chris Date et Hugh Darwen ont proposé un langage appelé Tutorial D destiné à être utilisé dans l'enseignement de la théorie des bases de données relationnelles, et son langage de requête s'inspire également des idées de l'ISBL. Rel est une implémentation du Tutoriel D .

Même le langage de requête de SQL est vaguement basé sur une algèbre relationnelle, bien que les opérandes en SQL ( tables ) ne soient pas exactement des relations et plusieurs théorèmes utiles sur l'algèbre relationnelle ne tiennent pas dans la contrepartie SQL (sans doute au détriment des optimiseurs et/ ou utilisateurs). Le modèle de table SQL est un sac ( multiset ), plutôt qu'un ensemble. Par exemple, l'expression est un théorème pour l'algèbre relationnelle sur les ensembles, mais pas pour l'algèbre relationnelle sur les sacs ; pour un traitement de l'algèbre relationnelle sur les sacs, voir le chapitre 5 du manuel "Complete" de Garcia-Molina , Ullman et Widom . ${\displaystyle (R\cup S)\setminus T=(R\setminus T)\cup (S\setminus T)}$

Voir également

Les références

Lectures complémentaires

Pratiquement n'importe quel manuel académique sur les bases de données a un traitement détaillé de l'algèbre relationnelle classique.

• Imieliński, T. ; Lipski, W. (1984). "Le modèle relationnel des données et les algèbres cylindriques" . Journal des sciences de l'informatique et des systèmes . 28 : 80-102. doi : 10.1016/0022-0000(84)90077-1 .(Pour la relation avec les algèbres cylindriques ).

Liens externes

• RAT. Traducteur logiciel d'algèbre relationnelle vers SQL
• Vidéos de cours : Traitement de l'algèbre relationnelle - Une introduction à la façon dont les systèmes de base de données traitent l'algèbre relationnelle
• Notes de cours : Algèbre relationnelle – Un tutoriel rapide pour adapter les requêtes SQL à l'algèbre relationnelle
• Relationnel – Une implémentation graphique de l'algèbre relationnelle
• Query Optimization (Page supprimée ; Alternatives les plus proches : Standford Query Optimization 2 , Microsoft research Query Optimization in relational systems , article de Stanford : Query Optimization ) Cet article est une introduction à l'utilisation de l'algèbre relationnelle dans l'optimisation des requêtes et comprend de nombreuses citations pour plus étude approfondie.
• Système d'algèbre relationnelle pour Oracle et Microsoft SQL Server
• Pireal – Un outil pédagogique expérimental pour travailler avec l'algèbre relationnelle
• DES – Un outil pédagogique pour travailler avec l'algèbre relationnelle et d'autres langages formels
• RelaX - Relational Algebra Calculator (logiciel open source disponible en tant que service en ligne sans inscription)
• RA : un interprète d'algèbre relationnelle
• Traduire SQL en algèbre relationnelle