Groupe Eyrolles 2003, ISBN 2-212-11281-5 · quence, le modèle relationnel peut apparaître comme un modèle mathématique simple des données. De plus, grâce à la représentation

© Groupe Eyrolles 2003,ISBN 2-212-11281-5

Partie 2

LE RELATIONNEL

VI – Le modèle relationnel (The relational model)

VII – Le langage SQL2 (The SQL2 language)

VIII – Intégrité et BD actives (Integrity and Triggers)

IX – La gestion des vues (View management)

X – L’optimisation de questions (Query optimization)

Chapitre VI

LE MODÈLE RELATIONNEL

1. INTRODUCTION : LES OBJECTIFS DU MODÈLE

Le modèle relationnel a été introduit par E. F. Codd [Codd70], qui travaillait aufameux centre de recherche d’IBM San-José et s’opposait au développement dumodèle DIAM, un modèle utilisant des entités liées par de multiples pointeurs. Lapremière volonté du modèle relationnel fut d’être un modèle ensembliste simple, sup-portant des ensembles d’enregistrements aussi bien au niveau de la description que dela manipulation. Les premières idées d’un modèle ensembliste avaient été proposéesun peu avant, notamment dans [Childs68]. Le modèle relationnel est aujourd’hui labase de nombreux systèmes, et les architectures permettant d’accéder depuis une sta-tion de travail à des serveurs de données s’appuient en général sur lui. Le relationnel adonc atteint ses objectifs au-delà de toute espérance.

Les premiers objectifs du modèle ont été formulés par E. F. Codd [Codd70] comme suit :

1. Permettre un haut degré d’indépendance des programmes d’applications et des acti-vités interactives à la représentation interne des données, en particulier aux choixdes ordres d’implantation des données dans les fichiers, des index et plus générale-ment des chemins d’accès.

2. Fournir une base solide pour traiter les problèmes de cohérence et de redondancedes données.

Ces deux objectifs, qui n’étaient pas atteints par les modèles réseau et hiérarchique,ont été pleinement satisfaits par le modèle relationnel, d’une part grâce à la simplicitédes vues relationnelles qui permettent de percevoir les données sous forme de tables àdeux dimensions, et d’autre part grâce aux règles d’intégrité supportées par le modèleet ses fondements logiques.

En addition aux objectifs fixés par E. F. Codd, le modèle relationnel a atteint un troi-sième objectif :

3. Permettre le développement de langages de manipulation de données non procédu-raux basés sur des théories solides.

Ce troisième objectif est atteint d’une part à l’aide de l’algèbre relationnelle qui per-met de manipuler des données de manière très simple et formelle – comme les opéra-teurs arithmétiques permettent de manipuler des entiers –, et d’autre part à l’aide deslangages assertionnels basés sur la logique qui permettent de spécifier les données quel’on souhaite obtenir sans dire comment les obtenir.

Finalement, le modèle relationnel a atteint deux autres objectifs non prévus initiale-ment :

4. Être un modèle extensible permettant de modéliser et de manipuler simplement desdonnées tabulaires, mais pouvant être étendu pour modéliser et manipuler des don-nées complexes.

5. Devenir un standard pour la description et la manipulation des bases de données.

L’objectif 4 est très important, car il a permis d’intégrer de nouveaux concepts aumodèle relationnel, notamment la plupart des concepts de l’orienté objets que nousétudierons dans la troisième partie de cet ouvrage. Les premiers travaux de recherchedans ce sens ont été effectués par Codd lui-même [Codd79], puis poursuivis à BellLaboratories [Zaniolo83], à Berkeley [Stonebraker87] et, en France, à l’INRIA[Gardarin89].

L’objectif 5 a été réalisé en particulier grâce à IBM : le modèle relationnel et son lan-gage SQL ont été normalisés au niveau international en 1986 [ISO89]. Nous ferons unpoint sur le langage SQL et sa standardisation dans le chapitre suivant.

Dans ce chapitre, nous allons tout d’abord présenter les concepts structuraux de basedu modèle relationnel qui permettent de modéliser les données sous forme de tables àdeux dimensions. Nous exposerons ensuite les règles de cohérence des relations quisont considérés comme partie intégrante du modèle. Puis nous introduirons l’algèbrerelationnelle, qui est l’outil formel indispensable pour manipuler des relations. Lesnombreuses extensions de cette algèbre seront également présentées. En conclusion,nous démontrerons les vastes possibilités d’enrichissement offertes par le modèle rela-tionnel, possibilités qui seront étudiées plus en détail au niveau des modèles objets etlogiques, sujets d’autres parties de ce livre.

180 • BASES DE DONNÉES : OBJET ET RELATIONNEL

2. LES STRUCTURES DE DONNÉES DE BASE

2.1. DOMAINE, ATTRIBUT ET RELATION

Le modèle relationnel est fondé sur la théorie mathématique bien connue des rela-tions. Cette théorie se construit à partir de la théorie des ensembles. Trois notions sontimportantes pour introduire les bases de données relationnelles. La première permetde définir les ensembles de départ. Ces ensembles sont les domaines de valeurs.

Les domaines sont donc les ensembles dans lesquels les données prennent valeur.Comme un ensemble, un domaine peut être défini en extension, en donnant la liste desvaleurs composantes, ou en intention, en définissant une propriété caractéristique desvaleurs du domaine. Au départ, les domaines ENTIER, REEL, BOOLEEN,CARACTERES (une chaîne de caractères de longueur fixe ou variable) sont définis enintention. À partir de ces domaines, il est possible de définir en intention desdomaines plus spécifiques tels que MONNAIE (réel avec 2 chiffres derrière la virgule),DATE (entier de 6 chiffres jour, mois et an), TEMPS (heure en secondes), etc. Undomaine peut toujours être défini en extension, par exemple le domaine des couleursde vins : COULEUR-VINS = {Rosé, Blanc, Rouge}.

Rappelons que le produit cartésien d’un ensemble de domaines D1, D2..., Dn estl’ensemble des vecteurs <v1, v2..., vn> où, pour i variant de 1 à n, vi est unevaleur de Di. Par exemple, le produit cartésien des domaines COULEUR-VINS = {ROSE, BLANC, ROUGE} et CRUS = {VOLNAY, SANCERRE,CHABLIS} est composé des neuf vecteurs représentés figure VI.1.

Figure VI.1 : Exemple de produit cartésien

COULEUR-VINS = {ROSE, BLANC, ROUGE}

CRUS = {VOLNAY, SANCERRE, CHABLIS}

ROSEROSEROSEBLANCBLANCBLANCROUGEROUGEROUGE

VOLNAYSANCERRECHABLISVOLNAYSANCERRECHABLISVOLNAYSANCERRECHABLIS

Notion VI.1 : Domaine (Domain)

Ensemble de valeurs caractérisé par un nom.

Le modèle relationnel • 181

Nous pouvons maintenant introduire la notion de relation, à la base du modèle.

Sous-ensemble d’un produit cartésien, une relation est composée de vecteurs. Unereprésentation commode d’une relation sous forme de table à deux dimensions a étéretenue par Codd. Elle est généralement utilisée. Chaque ligne correspond à un vec-teur alors que chaque colonne correspond à un domaine du produit cartésienconsidéré ; un même domaine peut bien sûr apparaître plusieurs fois. Par exemple, àpartir des domaines COULEURS_VINS et CRUS, il est possible de composer la rela-tion COULEURS_CRUS représentée sous forme tabulaire figure VI.2.

Figure VI.2 : Un premier exemple de relation

Pour pouvoir distinguer les colonnes d’une relation sans utiliser un index, et ainsirendre leur ordre indifférent tout en permettant plusieurs colonnes de même domaine,il est nécessaire d’associer un nom à chaque colonne. Une colonne se distingue d’undomaine en ce qu’elle prend valeur dans un domaine et peut à un instant donné com-porter seulement certaines valeurs du domaine. Par exemple, si le domaine estl’ensemble des entiers, seules quelques valeurs seront prises à un instant donné, parexemple {10, 20, 30}. L’ensemble des valeurs d’une colonne de relation est en géné-ral fini. Afin de bien distinguer domaine et colonne, on introduit la notion d’attributcomme suit :

Le nom associé à un attribut est souvent porteur de sens. Il est donc en général diffé-rent de celui du domaine qui supporte l’attribut. Ainsi, la première colonne de la rela-tion COULEUR-CRUS pourra être appelée simplement COULEUR et la deuxièmeCRU. COULEUR et CRU seront donc deux attributs de la relation COULEUR-CRUS.

Notion VI.3 : Attribut (attribute)

Colonne d’une relation caractérisée par un nom.

ROSEROSE

BLANC ROUGE ROUGEROUGE

SANCERRECHABLIS

SANCERREVOLNAY

SANCERRECHABLIS

COULEURS_CRUS Couleur Cru

Notion VI.2 : Relation (Relation)

Sous-ensemble du produit cartésien d’une liste de domaines caractérisé par un nom.


Les lignes d’une relation correspondent à des n-uplets de valeurs. Une ligne est aussiappelée tuple (du mot anglais tuple) : un tuple correspond en fait à un enregistrementdans une relation (encore appelée table).

La notion de relation est bien connue en mathématiques : une relation n-aire est unensemble de n-uplets. Un cas particulier souvent employé est la relation binaire, quiest un ensemble de paires ordonnées. Une relation n-aire est souvent représentée parun graphe entre les ensembles composants. Ainsi, la relation LOCALISATION, don-nant la région de chaque cru et certains prix moyens des vins associés, est représentéepar un graphe figure VI.3.

Figure VI.3 : Graphe de la relation LOCALISATION

Une relation peut aussi être représentée sur un diagramme à n dimensions dont lescoordonnées correspondent aux domaines participants. Ainsi, la relation STATIS-TIQUE, d’attributs AGE et SALAIRE, donnant la moyenne des salaires par âge, estreprésentée figure VI.4.

Figure VI.4 : Diagramme représentant une relation binaire

Salaire

Âge

100

80

60

40

20

10

0

CRUS RÉGION PRIX

Sancerre

Chablis

Volnay

45

42

38

Loire

Bourgogne

Notion VI.4 : Tuple (tuple)

Ligne d’une relation correspondant à un enregistrement.


Une autre perception mathématique d’une relation consiste à voir chaque tuple tcomme une fonction t : Ai –> Di pour i = 1, 2... n qui applique donc lesattributs sur les domaines. Ainsi, une relation peut être vue comme un ensemble finide fonctions. Bien sûr, cet ensemble varie en fonction du temps. Tout ceci montre ladiversité des outils mathématiques qui peuvent être appliqués aux relations. En consé-quence, le modèle relationnel peut apparaître comme un modèle mathématique simpledes données. De plus, grâce à la représentation tabulaire, il est simple à appréhenderpour les non mathématiciens.

2.2. EXTENSIONS ET INTENTIONS

Comme tous les modèles de données, le modèle relationnel permet de décrire des don-nées dont les valeurs varient en fonction du temps. Les relations varient en fonctiondu temps en ce sens que des tuples sont ajoutés, supprimés et modifiés dans une rela-tion au cours de sa vie. Cependant, la structure d’une relation caractérisée par les troisconcepts de domaine, relation et attribut est un invariant pour la relation (elle nechange pas en fonction du temps). Cette structure est capturée dans le schéma de larelation.

Un schéma de relation est noté sous la forme :

R (A1 : D1, A2 : D2..., Ai : Di... An : Dn)

R est le nom de la relation, Ai les attributs et Di les domaines associés. À titred’exemple, la figure VI.5 propose deux schémas de relations : celui de la relationLOCALISATION introduite ci-dessus et celui de la relation VINS qui représente desvins caractérisés par un numéro, un cru, un millésime et un degré. Les domaines utiliséssont ceux des entiers, des réels et des chaînes de caractères de longueur variable (CHAR-VAR). La plupart du temps, lorsqu’on définit le schéma d’une relation, les domaines sontimplicites et découlent du nom de l’attribut ; aussi omet-on de les préciser.

Figure VI.5 : Schémas des relations LOCALISATION et VINS

Soulignons que le schéma d’une relation représente son intention, c’est-à-dire lespropriétés (au moins certaines) communes et invariantes des tuples qu’elle va contenir

LOCALISATION (CRU : CHARVAR, REGION : CHARVAR, PRIX : FLOAT)VINS (NV :INTEGER, CRU : CHARVAR, MILL :INTEGER, DEGRE : FLOAT)

Notion VI.5 : Schéma de relation (Relation Schema)

Nom de la relation suivi de la liste des attributs et de la définition de leurs domaines.


au cours du temps. Au contraire, une table représente une extension d’une relation(voir figure VI.2 par exemple), c’est-à-dire une vue des tuples qu’elle contient à uninstant donné. Une extension d’une relation R est aussi appelée instance de R.L’intention est le résultat de la description des données, alors qu’une extension (ouinstance) fait suite à des manipulations et représente un état de la base.

3. LES RÈGLES D’INTÉGRITÉSTRUCTURELLE

Les règles d’intégrité sont les assertions qui doivent être vérifiées par les donnéescontenues dans une base. Il est possible de distinguer les règles structurelles qui sontinhérentes au modèle de données, c’est-à-dire nécessaires à sa mise en œuvre, et lesrègles de comportement propres au schéma particulier d’une application. Le modèlerelationnel impose a priori une règle minimale qui est l’unicité des clés, comme nousallons le voir ci-dessous. Il est commode et courant [Date81] d’ajouter trois types derègles d’intégrité supplémentaires afin d’obtenir les règles d’intégrité structurelle sup-portées par le modèle relationnel : les contraintes de références, les contraintesd’entité et les contraintes de domaine.

3.1. UNICITÉ DE CLÉ

Par définition, une relation est un ensemble de tuples. Un ensemble n’ayant pas d’élé-ment en double, il ne peut exister deux fois le même tuple dans une relation. Afind’identifier les tuples d’une relation sans donner toutes les valeurs et d’assurer simple-ment l’unicité des tuples, la notion de clé est utilisée.

De manière plus formelle, une clé d’une relation R est un ensemble d’attributs K telque, quels que soient les tuples t1 et t2 d’une instance de R, t1(K) ≠ t2(K),c’est-à-dire que t1 et t2 ont des valeurs de K différentes. Un ensemble d’attributscontenant une clé est appelée super-clé [Ullman88].

Toute relation possède au moins une clé car la connaissance de tous les attributs per-met d’identifier un tuple unique. S’il existe plusieurs clés, on en choisit en général une

Notion VI.6 : Clé (Key)

Ensemble minimal d’attributs dont la connaissance des valeurs permet d’identifier un tuple uniquede la relation considérée.


arbitrairement qui est appelée clé primaire. Par exemple, NV peut constituer une cléprimaire pour la relation VINS. Le couple <CRU,MILLESIME> est une clé alterna-tive.

Soulignons que la notion de clé caractérise l’intention d’une relation : dans touteextension possible d’une relation, il ne peut exister deux tuples ayant même valeurpour les attributs clés. La détermination d’une clé pour une relation nécessite doncune réflexion sur la sémantique de la relation, c’est-à-dire sur toutes les extensionspossibles et non pas sur une extension particulière.

3.2. CONTRAINTES DE RÉFÉRENCES

Le modèle relationnel est souvent utilisé pour représenter des entités du monde réel quisont les objets ayant une existence propre, et des associations entre ces objets [Chen76].Une entité correspond alors à un tuple dans une relation qui comporte à la fois la clé del’entité et ses caractéristiques sous forme d’attributs. Une entité est identifiée par lavaleur de sa clé. Un type d’association est modélisé par une relation comportant les clésdes entités participantes ainsi que les caractéristiques propres à l’association.

À titre d’exemple, nous considérons les entités BUVEURS et VINS du monde réel : laclé de l’entité BUVEURS est le numéro de buveur NB et celles de l’entité VINS lenuméro de vin NV. Ces entités peuvent être associées par une consommation d’un vinpar un buveur : une consommation sera par exemple modélisée par une associationABUS entre le buveur et le vin. Cette base typique et simple, qui servira souventd’exemple, est appelée DEGUSTATION. Le diagramme entité-association de cettebase est représenté figure VI.6.

Figure VI.6 : Diagramme entité-association de la base DEGUSTATION

BUVEURS VINS

Nom

Prénom

Type

Adresse

Cru

Millésime Qualité

Degré

Quantité Date

NBNV

ABUS


En relationnel, chaque entité est représentée par une table. Une association est aussireprésentée par une table, dont les attributs seront les clés des entités participantes,c’est-à-dire NB et NV, ainsi que les attributs caractérisant l’association, par exemplela date et la quantité bue. On aboutit ainsi au schéma relationnel représentéfigure VI.7.

Figure VI.7 : Schéma relationnel de la base DEGUSTATION

L’utilisation du modèle relationnel pour représenter des entités et des associations nepermet pas jusque-là de représenter le fait que l’association entre une consommationet un vin est obligatoire, c’est-à-dire que tout abus doit correspondre à un vin existantdans la base. De même, le fait que le lien entre une consommation et un buveur soitobligatoire est perdu. Le maintient de liens obligatoires a justifié l’introduction de lanotion de contrainte référentielle [Date81].

Une telle contrainte d’intégrité s’applique en général aux associations obligatoires :une telle association ne peut exister que si les entités participant à l’association exis-tent déjà. Notez que dans la définition, R1 et R2 ne sont pas forcément distinctes :l’association peut en effet porter sur deux entités de même type, par exemple entreune personne et ses parents.

La représentation de contraintes de référence peut s’effectuer par la définition de clésétrangères dans une relation : une clé étrangère est un groupe d’attributs qui doitapparaître comme clé dans une (autre) relation. Par exemple, la relation ABUS (NB,NV, DATE, QUANTITE) a pour clé <NB, NV, DATE> et a deux clés étrangères,NB dans BUVEURS et NV dans VINS.

Les contraintes référentielles définissent des liens obligatoires entre relations. Ce sontdes contraintes très fortes qui conditionnent le succès des opérations de mises à jour.Lors de l’insertion d’un tuple dans une relation référençante, il faut vérifier que lesvaleurs de clés étrangères existent dans les relations référencées. Par exemple, lors del’insertion d’un abus, il faut que le vins et le buveurs associés existent, sinon l’inser-tion est refusée pour cause de violation d’intégrité. Lors de la suppression d’un tupledans une relation référencée, il faut vérifier qu’aucun tuple n’existe dans chaque rela-tion référençante ; s’il en existe, le système peut soit refuser la suppression, soit la

Notion VI.7 : Contrainte référentielle (Referential constraint)

Contrainte d’intégrité portant sur une relation R1, consistant à imposer que la valeur d’un grouped’attributs apparaisse comme valeur de clé dans une autre relation R2.

BUVEURS (NB, NOM, PRENOM, ADRESSE, TYPE)VINS (NV, CRU, MILL QUALITE, DEGRE)ABUS (NB, NV, DATE, QUANTITE)


répercuter en cascade (c’est-à-dire, supprimer les tuples référençants). Par exemple, lasuppression d’un vin entraînera la vérification qu’aucun abus ne référence ce vin. Lescontraintes d’intégrité référentielles sont donc des liens forts qui rendent les relationsdépendantes ; en quelque sorte, elles introduisent des liens hiérarchiques depuis lesrelation référencées vers les relations référençantes.

3.3. VALEURS NULLES ET CLÉS

Lors de l’insertion de tuples dans une relation, il arrive fréquemment qu’un attributsoit inconnu ou non applicable ; par exemple, la quantité de vin bu par un buveur àune certaine date peut être inconnue ; si un vin ne possède pas de millésime, l’attributmillésime est inapplicable à ce vin. On est alors amené à introduire dans la relationune valeur conventionnelle, appelée valeur nulle.

La signification précise d’une valeur nulle est souvent ambiguë ; le groupeANSI/X3/SPARC a recensé quatorze significations possibles, parmi lesquelles valeurinconnue et valeur inapplicable sont les plus caractéristiques.

Tout attribut dans une relation ne peut prendre une valeur nulle ; en effet, l’existenced’une clé unique impose la connaissance de la clé afin de pouvoir vérifier que cettevaleur de clé n’existe pas déjà. Ainsi, une contrainte structurelle du modèle relationnelest la contrainte d’entité définie ci-dessous [Date81].

À moins qu’il n’en soit spécifié autrement par une contrainte sémantique, le modèlerelationnel n’impose pas que les clés étrangères qui n’appartiennent pas à une clé pri-maire soient non nulles. Cela peut permettre une certaine souplesse, par exempled’enregistrer des employés qui ne sont attachés à aucun service.

3.4. CONTRAINTES DE DOMAINES

En théorie, une relation est construite à partir d’un ensemble de domaines. En pra-tique, les domaines gérés par les systèmes sont souvent limités aux types de base

Notion VI.9 : Contrainte d’entité (Entity constraint)

Contrainte d’intégrité imposant que toute relation possède une clé primaire et que tout attribut parti-cipant à cette clé primaire soit non nul.

Notion VI.8 : Valeur nulle (Null value)

Valeur conventionnelle introduite dans une relation pour représenter une information inconnue ouinapplicable.


entier, réel, chaîne de caractères, parfois monnaie et date. Afin de spécialiser un typede données pour composer un domaine plus fin (par exemple, le domaine des salairesmensuels qui sont des réels compris entre 6 000 et 1 000 000 de francs), la notion decontrainte de domaine est souvent ajoutée aux règles d’intégrité structurelle du rela-tionnel. Cette notion peut être introduite comme suit :

L’assertion logique est l’appartenance à une plage de valeurs ou à une liste de valeurs.Par exemple, SALAIRE ≥ 5 000 et ≤ 1 000 000, COULEUR ∈ {BLEU,BLANC, ROUGE}, etc. Les contraintes permettent de contrôler la validité des valeursintroduites lors des insertions ou mises à jour. La non-nullité d’une colonne peut aussiêtre considérée comme une contrainte de domaine, par exemple DEGRE IS NULL.

4. L’ALGÈBRE RELATIONNELLE :OPÉRATIONS DE BASE

L’algèbre relationnelle a été inventée par E. Codd comme une collection d’opérationsformelles qui agissent sur des relations et produisent les relations en résultats[Codd70]. On peut considérer que l’algèbre relationnelle est aux relations ce qu’estl’arithmétique aux entiers. Cette algèbre, qui constitue un ensemble d’opérations élé-mentaires associées au modèle relationnel, est sans doute une des forces essentiellesdu modèle. Codd a initialement introduit huit opérations, dont certaines peuvent êtrecomposées à partir d’autres. Dans cette section, nous allons introduire six opérationsqui permettent de déduire les autres et qui sont appelées ici opérations de base. Nousintroduirons ensuite quelques opérations additionnelles qui sont parfois utilisées. Desauteurs ont proposé d’autres opérations qui peuvent toujours se déduire des opérationsde base [Delobel83, Maier83].

Les opérations de base peuvent être classées en deux types : les opérations ensem-blistes traditionnelles (une relation étant un ensemble de tuples, elle peut être traitéecomme telle) et les opérations spécifiques. Les opérations ensemblistes sont des opé-rations binaires, c’est-à-dire qu’à partir de deux relations elles en construisent unetroisième. Ce sont l’union, la différence et le produit cartésien. Les opérations spéci-fiques sont les opérations unaires de projection et restriction qui, à partir d’une rela-tion, en construisent une autre, et l’opération binaire de jointure. Nous allons définirtoutes ces opérations plus précisément.

Notion VI.10 : Contrainte de domaine (Domain constraint)

Contrainte d’intégrité imposant qu’une colonne d’une relation doit comporter des valeurs vérifiantune assertion logique.


4.1. LES OPÉRATIONS ENSEMBLISTES

4.1.1. UnionL’union est l’opération classique de la théorie des ensembles adaptée aux relations demême schéma.

Plusieurs notations ont été introduites pour cette opération, selon les auteurs :– RELATION1 ∪ RELATION2– UNION (RELATION1, RELATION2)– APPEND (RELATION1, RELATION2)

La notation graphique représentée figure VI.8 est aussi utilisée. À titre d’exemple,l’union des relations VINS1 et VINS2 est représentée figure VI.9.

Figure VI.8 : Représentation graphique de l’union

Figure VI.9 : Exemple d’union

Vins1 CruCHENASTOKAYTAVEL

Mill198319801986

RégionBEAUJOLAIS

ALSACERHONE

CouleurROUGEBLANCROSE∪

Vins2 CruTOKAY

CHABLIS

Mill19801985

RégionALSACE

BOURGOGNE

CouleurBLANCROUGE

Vins CruCHENASTOKAYTAVEL

CHABLIS

Mill1983198019861985

RégionBEAUJOLAIS

ALSACERHONE

BOURGOGNE

CouleurROUGEBLANCROSE

ROUGE

∪

RELATION1 RELATION2

RÉSULTAT

Notion VI.11 : Union (Union)

Opération portant sur deux relations de même schéma RELATION1 et RELATION2 consistant àconstruire une relation de même schéma RELATION3 ayant pour tuples ceux appartenant à RELA-TION1 ou RELATION2 ou aux deux relations.


4.1.2. DifférenceLa différence est également l’opération classique de la théorie des ensembles adaptéeaux relations de même schéma.

La différence est un opérateur non commutatif : l’ordre des relations opérandes est doncimportant. Plusieurs notations ont été introduites pour cette opération, selon les auteurs :– RELATION1 – RELATION2– DIFFERENCE (RELATION1, RELATION2)– REMOVE (RELATION1, RELATION2– MINUS (RELATION1, RELATION2)

La notation graphique représentée figure VI.10 est aussi utilisée. À titre d’exemple, ladifférence des relations VINS1 – VINS2 est représentée figure VI.11.

Figure VI.10 : Représentation graphique de la différence

Figure VI.11 : Exemple de différence


Mill198319801986

RégionBEAUJOLAIS

ALSACERHONE

CouleurROUGEBLANCROSE−

Vins2 CruTOKAY

CHABLIS

Mill19801985

RégionALSACE

BOURGOGNE

CouleurBLANCROUGE

Vins CruCHENAS

TAVEL

Mill19831986

RégionBEAUJOLAIS

RHONE

CouleurROUGEROSE

–

RELATION1 RELATION2

RÉSULTAT

Notion VI.12 : Différence (Difference)

Opération portant sur deux relations de même schéma RELATION1 et RELATION2, consistant àconstruire une relation de même schéma RELATION3 ayant pour tuples ceux appartenant à RELA-TION1 et n’appartenant pas à RELATION2.


4.1.3. Produit cartésienLe produit cartésien est l’opération ensembliste que nous avons rappelée ci-dessuspour définir le concept de relations. Elle est adaptée aux relations. Cette fois, les deuxrelations n’ont pas nécessité d’avoir même schéma.

Des notations possibles pour cette opération sont :– RELATION1 X RELATION2– PRODUCT (RELATION1, RELATION2)– TIMES (RELATION1, RELATION2)

La notation graphique représentée figure VI.12 est aussi utilisée. À titre d’exemple, larelation VINS représentée figure VI.13 est le produit cartésien des deux relationsCRUS et ANNEES de la même figure.

Figure VI.12 : Représentation graphique du produit cartésien

Figure VI.13 : Exemple de produit cartésien


RégionBEAUJOLAIS

ALSACERHONE

CouleurROUGEBLANCROSEX

Années Mill19801985

Vins CruCHENASTOKAYTAVEL

CHENASTOKAYTAVEL

Mill198019801980198519851985

RégionBEAUJOLAIS

ALSACERHONE

BEAUJOLAISALSACERHONE

CouleurROUGEBLANCROSE

ROUGEBLANCROSE

X

RELATION1 RELATION2

RÉSULTAT

Notion VI.13 : Produit cartésien (Cartesian product)Opération portant sur deux relation RELATION1 et RELATION2, consistant à construire une rela-tion RELATION3 ayant pour schéma la concaténation de ceux des relations opérandes et pourtuples toutes les combinaisons des tuples des relations opérandes.


4.2. LES OPÉRATIONS SPÉCIFIQUES

4.2.1. ProjectionLa projection est une opération spécifique aux relations qui permet de supprimer desattributs d’une relation. Son nom provient du fait qu’elle permet de passer d’une rela-tion n-aire à une relation p-aire avec p<n, donc d’un espace à n dimensions à unespace à moins de dimensions.

Les notations suivantes sont utilisées pour cette opération, en désignant parAttributi, Attributj... Attributm les attributs de projection :– ΠAttributi, Attributj... Attributm (RELATION1)

– RELATION1 [Attributi, Attributj... Attributm]

– PROJECT (RELATION1, Attributi, Attributj... Attributm)

La notation graphique représentée figure VI.14 est aussi utilisée. Le trapèze horizontalsignifie que l’on réduit le nombre de colonnes de la relation : partant du nombrereprésenté par la base, on passe au nombre représenté par l’anti-base. La figure VI.15donne un exemple de projection d’une relation VINS comportant aussi l’attributQUALITE sur les attributs MILLESIME et QUALITE.

Figure VI.14 : Représentation graphique de la projection

RELATION

RÉSULTAT

A1, A2… An

Notion VI.14 : Projection (Projection)

Opération sur une relation RELATION1 consistant à composer une relation RELATION2 en enlevant à la relation initiale tous les attributs non mentionnés en opérandes (aussi bien au niveau du schéma que des tuples) et en éliminant les tuples en double qui sont conservés une seulefois.


Figure VI.15 : Exemple de projection

4.2.2. RestrictionLa restriction est aussi une opération spécifique unaire, qui produit une nouvelle rela-tion en enlevant des tuples à la relation opérande selon un critère.

Les conditions possibles sont du type :<Attribut> <Opérateur> <Valeur>

où l’opérateur est un opérateur de comparaison choisi parmi {=,<, ≤, ≥, >, ≠}.L’attribut doit appartenir à la relation sur laquelle s’applique le critère. Par exemple,pour la relation VINS, CRU = “Chablis” est une condition de restriction pos-sible. DEGRE > 12 est une autre condition possible. Il est aussi possible d’utiliserdes compositions logiques de critères simples, c’est-à-dire des « et » et « ou » deconditions élémentaires. On pourra par exemple utilisé le critère CRU = “Chablis” etDEGRE > 12, ou encore le critère CRU = “Chablis” ou DEGRE = 12. Toutecomposition de critères valides par conjonction et disjonction (des parenthèses peu-vent être utilisées pour préciser les priorités) est valide. Notons que les compositionslogiques peuvent aussi être obtenues par union et intersection de relations restreintes(voir ci-dessous).

Les notations suivantes sont utilisées pour la restriction :– σcondition (RELATION1)– RELATION1 [Condition]– RESTRICT (RELATION1, Condition)

Notion VI.15 : Restriction (Restriction)

Opération sur une relation RELATION1 produisant une relation RELATION2 de même schéma,mais comportant les seuls tuples qui vérifient la condition précisée en argument.

VINS CruVOLNAYVOLNAYCHENASJULIENAS

Mill1983197919831986

RégionBOURGOGNEBOURGOGNEBEAUJOLAISBEAUJOLAIS

QualitéABAC

Π(VINS) CruVOLNAYCHENASJULIENAS

RégionBOURGOGNEBEAUJOLAISBEAUJOLAIS

Πcru, Région


ainsi que la notation graphique représentée figure VI.16. Le trapèze vertical signifieque l’on réduit le nombre de tuples de la relation : partant du nombre représenté par lecôté gauche, on passe au nombre représenté par le côté droit. La figure VI.17 repré-sente la restriction d’une relation VINS enrichie d’un attribut QUALITE par la condi-tion QUALITE = “BONNE”.

Figure VI.16 : Représentation graphique de la restriction

Figure VI.17 : Exemple de restriction

4.2.3. JointureLa jointure est une des opérations essentielles de l’algèbre relationnelle, sans doute laplus difficile à réaliser dans les systèmes. La jointure permet de composer deux rela-tions à l’aide d’un critère de jointure. Elle peut être vue comme une extension du pro-duit cartésien avec une condition permettant de comparer des attributs. Nous la défini-rons comme suit :

Notion VI.16 : Jointure (Join)

Opération consistant à rapprocher selon une condition les tuples de deux relations RELATION1 etRELATION2 afin de former une troisième relation RELATION3 qui contient l’ensemble de tous lestuples obtenus en concaténant un tuple de RELATION1 et un tuple de RELATION2 vérifiant lacondition de rapprochement.

VINS CruVOLNAYVOLNAYCHENASJULIENAS

Mill1983197919831986

RégionBOURGOGNEBOURGOGNEBEAUJOLAISBEAUJOLAIS

QualitéABAC

σcru > 1983

VINS CruJULIENAS

Mill1986

RégionBEAUJOLAIS

QualitéC

RELATION

RÉSULTAT

Ai θ Valeur


La jointure de deux relations produit donc une troisième relation qui contient toutesles combinaisons de tuples des deux relations initiales satisfaisant la condition spéci-fiée. La condition doit bien sûr permettre le rapprochement des deux relations, et doncêtre du type :

<Attribut1> <opérateur> <Attribut2>

où Attribut1 appartient à RELATION1 et Attribut2 à RELATION2. Selon le typed’opérateur, on distingue :– l’équi-jointure dans le cas où l’opérateur est =, qui est une véritable composition

de relations au sens mathématique du terme ;– l’inéqui-jointure dans les autres cas, c’est-à-dire avec un des opérateurs <, ≤,>, ≥, ≠.

Dans le cas d’équi-jointure, les deux attributs égaux apparaissent chacun dans lerésultat : il y a donc duplication d’une même valeur dans chaque tuple. Afin d’élimi-ner cette redondance, on définit la jointure naturelle comme suit :

L’opération de jointure est représentée par l’une des notations suivantes, la conditionétant simplement omise dans le cas de jointure naturelle (c’est alors l’égalité des attri-buts de même nom) :– RELATION1 RELATION2

Condition– JOIN (RELATION1, RELATION2, Condition)

La figure VI.18 donne la représentation graphique de l’opération de jointure ; lafigure VI.19 illustre cette opération en effectuant la jointure naturelle des deux rela-tions VINS et LOCALISATION. L’inéqui-jointure de ces deux relations selon lacondition QUALITE > QUALITE MOYENNE est représentée figure VI.20. On sup-pose que les qualités sont codées par ordre décroissant A, B, C, D, E.

Figure VI.18 : Représentation graphique de la jointure

RÉSULTAT

Ai θBj

RELATION1 RELATION2

Notion VI.17 : Jointure naturelle (Natural join)

Opération consistant à rapprocher les tuples de deux relations RELATION1 et RELATION2 afin deformer une troisième relation RELATION3 dont les attributs sont l’union des attributs de RELATION1et RELATION2, et dont les tuples sont obtenus en composant un tuple de RELATION1 et un tuple deRELATION2 ayant mêmes valeurs pour les attributs de même nom.


Figure VI.19 : Jointure naturelle des relations VINS et LOCALISATION

Figure VI.20 : Inéqui-jointure des relations VINS et LOCALISATION

VINS CruVOLNAYVOLNAYCHABLISJULIENAS

Mill1983197919831986

RégionBOURGOGNEBOURGOGNECALIFORNIE

QualitéABAC

LOCALISATION CruVOLNAYCHABLISCHABLIS

QualMoyAAB

VINSNLOC Cru Mill QualitéABBACCC

Région QualMoyBAABAAB

Qualité ≠ QualMoy

CruVOLNAYVOLNAYVOLNAYCHABLISJULIENASJULIENASJULIENAS

1983197919791983198619861986

CHABLISVOLNAYCHABLISCHABLISVOLNAYCHABLISCHABLIS

CALIFORNIEBOURGOGNEBOURGOGNECALIFORNIEBOURGOGNEBOURGOGNECALIFORNIE


Mill1983197919831986


QualitéABAC


QualMoyAAB

VINSREG CruVOLNAYVOLNAYCHABLISCHABLIS

Mill1983197919831983

QualitéABAA

RégionBOURGOGNEBOURGOGNEBOURGOGNECALIFORNIE

QualMoyAAAB


La jointure n’est pas toujours considérée comme une opération de base de l’algèbrerelationnelle. En effet, si l’on étend la définition de la restriction de manière à consi-dérer des conditions multi-attributs du type <Attribut1> <Opérateur><Attribut2>, alors la jointure peut être obtenue par un produit cartésien suivid’une restriction du résultat comme suit :

JOIN (RELATION1, RELATION2, Condition) =RESTRICT ((RELATION1 X RELATION2), Condition)

Compte tenu de son jointure, nous avons préféré ici définir la jointure comme uneopération de base.

5. L’ALGÈBRE RELATIONNELLE :OPÉRATIONS DÉRIVÉES

Les opérations présentées ci-dessous sont parfois utilisées pour manipuler des rela-tions. Elles peuvent en général être obtenues par combinaison des opérations précé-dentes. Dans certains cas (complément, jointure externe), leur expression à partir desopérations de base nécessite la manipulation de relations constantes à tuples prédéfi-nis, telles que la relation obtenue par le produit cartésien des domaines, ou encorecelle composée d’un seul tuple à valeurs toutes nulles.

5.1. INTERSECTION

L’intersection est l’opération classique de la théorie des ensembles adaptée aux rela-tions de même schéma.

Plusieurs notations ont été introduites pour cette opération selon les auteurs :

– RELATION1 ∩ RELATION2

– INTERSECT (RELATION1, RELATION2)

– AND (RELATION1, RELATION2)

La notation graphique représentée figure VI.21 est aussi utilisée.

Notion VI.18 : Intersection (Intersection)

Opération portant sur deux relations de même schéma RELATION1 et RELATION2 consistant àconstruire une relation de même schéma RELATION3 ayant pour tuples ceux appartenant à la foisà RELATION1 et RELATION2.


Figure VI.21 : Représentation graphique de l’intersection

L’intersection est une opération redondante avec les opérations de base, puisqu’il estpossible de l’obtenir à partir de la différence à l’aide d’une des formules suivantes :

RELATION1 ∩ RELATION2 = RELATION1 – (RELATION1 – RELA-TION2)

RELATION1 ∩ RELATION2 = RELATION2 – (RELATION2 – RELA-TION1)

5.2. DIVISION

La division permet de rechercher dans une relation les sous-tuples qui sont complétéspar tous ceux d’une autre relation. Elle permet ainsi d’élaborer la réponse à des ques-tions de la forme « quel que soit x, trouver y » de manière simple.

De manière plus formelle, désignons par ai une valeur quelconque de l’attribut Ai. Untuple est alors une suite de valeurs <a1, a2, a3...>. Utilisant ces notations, le quotientde D par D est défini par :

Q = {<a1, a2... ap> tel-que quel-que-soit <ap+1... an> de d, <a1, a2... ap, ap+1..., an> appartient à D}

Les notations possibles pour la division sont :

– D ÷ d

– DIVISION (D, d)

ainsi que la représentation graphique de la figure VI.22. Un exemple de division estreprésenté figure VI.23.

Notion VI.19 : Division (Division)

Opération consistant à construire le quotient de la relation D (A1, A2... Ap, Ap+1... An)par la relation d(Ap+1... An) comme la relation Q(A1, A2... Ap) dont les tuples sont ceuxqui concaténés à tout tuple de d donnent un tuple de D.

∩

RELATION1 RELATION2

RÉSULTAT


Figure VI.22 : Représentation graphique de la division

Figure VI.23 : Exemple de division

La division peut être obtenue à partir de la différence, du produit cartésien et de laprojection comme suit :

– D – d = R1 – R2 avec

– R1 = ΠA1, A2... Ap(D)– R2 = ΠA1, A2... Ap ((R1 X d) – D)

5.3. COMPLÉMENT

Le complément permet de trouver les tuples qui n’appartiennent pas à une relation. Ilsuppose a priori que les domaines sont finis (sinon on obtient des relations infinies).

VINS CruVOLNAYVOLNAYCHABLISCHABLISJULIENAS

Mill19831979198319791986

QualitéABAAA

QUALITE QualitéAA

÷ Mill19831979

CRU CruCHABLIS

÷

RELATION1 RELATION2

RÉSULTAT


Le complément d’une relation RELATION1 est noté au choix :

– RELATION1

– NOT(RELATION1)

– COMP(RELATION1)

La figure VI.24 illustre cette opération dans un cas simple. C’est une opération peu utili-sée du fait qu’elle permet de générer des tuples qui ne sont pas dans la base, en généraltrès nombreux. Si l’on note par X Di le produit cartésien des domaines, le complémentd’une relation RELATION1 est obtenu à partir de la différence comme suit :

– NOT (RELATION1) = X Di – RELATION1

Figure VI.24 : Exemple de complément

5.4. ÉCLATEMENT

L’éclatement [Fagin80] est une opération qui n’appartient pas vraiment à l’algèbrerationnelle puisqu’elle donne deux relations en résultats, à partir d’une. Elle est cepen-

COUL_CRU Cru Couleur

NOT(COUL_CRU) Cru Couleur

CHABLISCHABLISVOLNAYMÉDOCMÉDOC

ROUGEROSÉ

ROUGEROSÉ

BLANC

CHABLISVOLNAYVOLNAYMÉDOC

BLANCROSÉ

BLANCROUGE

Domaines : CRU = { Chablis, Volnay, Médoc}COULEUR = {Rouge, Rosé, Blanc}

Notion VI.20 : Complément (Complement)

Ensemble des tuples du produit cartésien des domaines des attributs d’une relation n’appartenantpas à cette relation.


dant utile pour partitionner une relation horizontalement en deux sous-relations. À cetitre, elle est considérée comme une extension de l’algèbre.

Cet opérateur appliqué à la relation RELATION1 génère donc deux relations R1 et R2qui seraient obtenues par restriction comme suit :

– R1 = RESTRICT (RELATION1, Condition)

– R2 = RESTRICT (RELATION1, ¬ Condition)

5.5. JOINTURE EXTERNE

Les jointures définies ci-dessus perdent des tuples d’au moins une relation quand lesrelations jointes n’ont pas de projections identiques sur l’attribut de jointure. Pour pré-server toutes les informations dans tous les cas, il est nécessaire de définir des join-tures qui conservent les tuples sans correspondant avec des valeurs nulles associéesquand nécessaire. C’est dans ce but que Codd [Codd79] a introduit les jointuresexternes.

Cette opération est très utile, en particulier pour composer des vues sans perte d’infor-mations. Elle se note en général comme suit :

– RELATION1 RELATION2

– EXT-JOIN (RELATION1, RELATION2)

La jointure externe permet par exemple de joindre des tables CLIENTS et COM-MANDES sur un numéro de client commun, en gardant les clients sans commande etles commandes sans client associé. Elle est donc très utile en pratique. On peut aussidistinguer la jointure externe droite qui garde seulement les tuples sans correspondantde la relation de droite. On notera celle-ci ou REXT-JOIN. De même, on peutdistinguer la jointure externe gauche ( ou LEXT-JOIN). Un exemple de jointureexterne complète apparaît figure VI.25.

Notion VI.22 : Jointure externe (External Join)

Opération générant une relation RELATION3 à partir de deux relations RELATION1 et RELA-TION2, par jointure de ces deux relations et ajout des tuples de RELATION1 et RELATION2 neparticipant pas la jointure, avec des valeurs nulles pour les attributs de l’autre relation.

Notion VI.21 : Éclatement (Split)

Opération consistant à créer deux relations à partir d’une relation RELATION1 et d’une condition,la première contenant les tuples de RELATION1 et la deuxième ceux ne la vérifiant pas.


Figure VI.25 : Exemple de jointure externe

5.6. SEMI-JOINTURE

Dans certains cas, lors de l’exécution d’une jointure, il n’est pas nécessaire de conser-ver tous les attributs des deux relations en résultat : seuls les attributs d’une des deuxrelations sont conservés. Une opération spécifique de semi-jointure, très utile pouroptimiser l’évaluation des questions, a été définie [Berstein81].

La semi-jointure de la relation RELATION1 par la relation RELATION2 est notée :

– RELATION1 RELATION2

– SEMI-JOIN (RELATION1, RELATION2)

Elle est équivalente à la jointure des relations RELATION1 et RELATION2 suivie parune projection du résultat sur les attributs de la relation RELATION1. Notez quel’opération n’est pas symétrique puisque seuls des tuples de la première relation sontconservés. Elle peut être vue comme une restriction de la relation RELATION1 parles valeurs des attributs de jointure figurant dans la relation RELATION2. Lafigure VI.26 illustre cette opération de semi-jointure.

Notion VI.23 : Semi-jointure (Semi-join)

Opération portant sur deux relations RELATION1 et RELATION2, donnant en résultat les tuples deRELATION1 qui participent à la jointure des deux relations.

VINS CruVOLNAYVOLNAYJULIENAS

Mill198319791986


QualitéABC


QualMoyAAB

VINSREG CruVOLNAYVOLNAYCHABLISCHABLISJULIENAS

Mill19831979

——

1986

QualitéAB——C

RégionBOURGOGNEBOURGOGNEBOURGOGNECALIFORNIE

—

QualMoyAAAB—

•


Figure VI.26 : Exemple de semi-jointure

5.7. FERMETURE TRANSITIVE

La fermeture transitive est une opération très particulière qui permet d’ajouter destuples à une relation. Elle n’appartient pas à l’algèbre rationnelle, mais peut être vuecomme une de ses extensions. Il n’est pas possible de constituer cette opération avecun nombre fixe d’opérations de l’algèbre rationnelle : elle peut être effectuée par unesérie de jointure/projection/union, mais le nombre d’opérations à effectuer dépend ducontenu de la relation. Certains auteurs considèrent que c’est une faiblesse del’algèbre relationnelle que de ne pas pouvoir exprimer une fermeture transitive parune expression constante d’opérations élémentaires.

Cette opération se note suivant les auteurs :

– τ(R)– R+

– CLOSE(R)

Notion VI.24 : Fermeture transitive (Transitive closure)

Opération sur une relation R à deux attributs (A1, A2) de même domaine consistant à ajouter à Rtous les tuples qui se déduisent successivement par transitivité, c’est-à-dire que si l’on a des tuples<a, b> et <b, c>, on ajoute <a, c>.


Mill1983197919831986


QualitéABAC


QualMoyAAB

VINSLOG CruVOLNAYVOLNAYCHABLIS

Mill198319791983

QualitéABA


Pour effectuer une fermeture transitive, il est nécessaire d’effectuer une boucle d’opé-rations jusqu’à obtention de la fermeture complète. On doit donc utiliser un langagede programmation avec une boucle while, comme suit :

τ(R) = while τ(R) change do τ(R)= τ(R)∪ ΠA1,A4 (R τ(R)).

Cette opération permet par exemple de calculer à partir d’une relation PARENTS(Parent, Enfant) la relation ANCETRES (Ascendant, Descendant),qui donne toute la filiation connue d’une personne. La figure VI.27 illustre cette opé-ration. La fermeture transitive de PARENTS est calculée parjointures/projections/unions successives de la relation PARENTS avec elle-mêmejusqu’à saturation, c’est-à-dire jusqu’à obtention d’une relation stable à laquelle unenouvelle jointure/projection/union n’apporte plus de tuples. On voit que la relationANCETRES représente le graphe correspondant à la fermeture transitive du graphe dela relation PARENTS.

Figure VI.27 : Exemple de fermeture transitive

PARENTS Parent EnfantPierre PaulJeanne PaulPaul YvesYves Jean

• Pierre• Jeanne

• Paul

• Yves

• Jean

Pierre PaulJeanne PaulPaul YvesYves JeanPierre YvesJeanne YvesPierre JeanJeanne JeanPaul Jean

ANCÊTRES Ascendant Descendant

Graphede la relation PARENTS


6. LES EXPRESSIONS DE L’ALGÈBRERELATIONNELLE

À partir des opérations de l’algèbre relationnelle, il est possible de composer un lan-gage d’interrogation de bases de données. Une question peut alors être représentée parun arbre d’opérateurs relationnels. Le paraphrasage en anglais de telles expressionsest à la base du langage SQL que nous étudierons dans le chapitre suivant.

6.1. LANGAGE ALGÉBRIQUE

En utilisant des expressions d’opérations de l’algèbre relationnelle, il est possibled’élaborer les réponses à la plupart des questions que l’on peut poser à une base dedonnées relationnelle. Plus précisément, les opérations de base de l’algèbre relation-nelle constituent un langage complet, c’est-à-dire ayant la puissance de la logique dupremier ordre.

Nous avons étudié plus précisément la logique du premier ordre et les langagesd’interrogation qui en découlent au chapitre V. Disons simplement que l’algèbre rela-tionnelle permet d’exprimer toute question exprimable avec la logique du premierordre sans fonction, par exemple avec le calcul de tuple ou de domaine. L’algèbrerelationnelle peut d’ailleurs être étendue avec des fonctions [Zaniolo85].

Voici quelques questions sur la base DEGUSTATION dont le schéma a été représentéfigure VI.7. Elles peuvent être exprimées comme des expressions d’opérations, oucomme des opérations successives appliquées sur des relations intermédiaires ou debase, générant des relations intermédiaires. Pour des raisons de clarté, nous avonschoisi cette deuxième représentation. L’expression peut être obtenue simplement ensupprimant les relations intermédiaires notées Ri.

(Q1) Donner les degrés des vins de crus Morgon et de millésime1978 :R1 = RESTRICT (VINS, CRUS = “MORGON”)R2 = RESTRICT (VINS, MILLESIME = 1978)R3 = INTERSECT (R1, R2)RESULTAT = PROJECT (R3, DEGRE)

(Q2) Donner les noms et prénoms des buveurs de Morgon ou Chenas :R1 = RESTRICT (VINS, CRU = “MORGON”)R2 = RESTRICT(VINS, CRUS = “CHENAS”)R3 = UNION (R1, R2)

Notion VI.25 : Langage complet (Complete language)

Langage équivalent à la logique du premier ordre.


R4 = JOIN (R3, ABUS)R5 = JOIN (R4, BUVEURS)RESULTAT = PROJECT (R5, NOM, PRENOM)

(Q3) Donner les noms et adresses des buveurs ayant bu plus de 10 bouteilles deChablis 1976 avec le degré de ce vin :

R1 = RESTRICT (ABUS, QUANTITE > 10)R2 = RESTRICT (VINS, CRU = “CHABLIS”)R3 = RESTRICT (VINS, MILLESIME = 1976)R4 = INTERSECT (R2, R3)R5 = JOIN (R1, R4)R6 = PROJECT (R5, NB, DEGRE)R7 = JOIN (R6, BUVEURS)RESULTAT = PROJECT (R7, NOM, ADRESSE, DEGRE)

(Q4) Donner les noms des buveurs n’ayant bu que du Morgon :

R1 = JOIN(BUVEURS,ABUS,VINS)R2 = RESTRICT(R1, CRU = “Morgon”)R3 = PROJECT(R2, NOM)R4 = RESTRICT(R1, CRU ≠ “Morgon”)R5 = PROJECT(R1, NOM)RESULTAT = MINUS(R3 – R5)

Si l’on accepte les relations constantes, l’algèbre relationnelle permet aussi d’exécuterles mises à jour. Par exemple, l’intersection du vin [100, TOKAY, 1978, 13] s’effec-tuera comme suit :

R1 = CONSTANTE (VINS, [100, TOKAY, 1978, 13])VINS = UNION (VINS, R1)

où CONSTANTE permet de définir une relation de même schéma que la relation VINScontenant le seul tuple indiqué en argument.

6.2. ARBRE ALGÉBRIQUE

Une question exprimée sous forme d’un programme d’opérations de l’algèbre rela-tionnelle peut être représentée par un arbre relationnel. Les nœuds correspondentaux représentations graphiques des opérations indiquées ci-dessus et les arcs aux flotsde données entre opérations.

Ainsi, la question « Noms et Prénoms des buveurs habitant Paris ayant bu du Chablisdepuis le 1er janvier 1992 » peut être exprimée à l’aide de l’arbre représenté

Notion VI.26 : Arbre relationnel (Relational tree)

Arbre dont les nœuds correspondent à des opérations de l’algèbre relationnelle et les arcs à desrelations de base ou temporaires représentant des flots de données entre opérations.


figure VI.28. Plusieurs arbres équivalents peuvent être déduits d’un arbre donné àl’aide de règles de transformation simples, telles que la permutation des jointures etrestrictions, la permutation des projections et des jointures, le regroupement des inter-sections sur une même relation, etc. Ces transformations sont à la base des techniquesd’optimisation de questions qui dépassent le sujet de ce chapitre. La figure VI.29 pro-pose un arbre équivalent à celui de la figure VI.28, obtenu par descente de projectionset regroupement d’intersections.

Figure VI.28 : Exemple d’arbre représentant une question

La composition d’opérations de l’algèbre relationnelle ne nécessite pas toujoursd’attendre le résultat de l’opération précédente pour exécuter l’opération suivante.Restriction, projection et jointure peuvent ainsi être exécutées par des algorithmes à flotsde données. Des opérateurs se succédant sur un arbre peuvent donc être exécutés enparallèle par des algorithmes « pipe-line ». Des opérateurs figurant sur des branches dis-tinctes d’un arbre peuvent aussi être exécutés en parallèle de manière indépendante. Lareprésentation par arbre algébrique met ainsi en évidence les possibilités de parallélismeet les enchaînements nécessaires. Ces propriétés des arbres relationnels sont importantespour optimiser les questions dans des contextes parallèles.

RÉSULTAT

B.NOM, B. PRÉNOM

≥A. DATE 01.01.92

=V. CRU “CHABLIS”

A.NV V.NV

B.ADRESSE “PARIS”LIKE

B.NB A.NB

ABUS A

VINS V

BUVEURS B

=


Figure VI.29 : Arbre équivalent à l’arbre précédent

7. FONCTIONS ET AGRÉGATSL’algèbre relationnelle est insuffisante pour traiter de véritables applications des bases dedonnées, telles la suivie de production, la gestion de budget, etc. Il est en effet nécessaired’effectuer des calculs sur la base pour supporter de telles applications. C’est l’objet del’introduction des fonctions de calcul au sein de l’algèbre et du support des agrégats.

7.1. FONCTIONS DE CALCUL

La possibilité d’effectuer des calculs sur les attributs est simplement introduite en généra-lisant projection, restriction et jointure par introduction de fonctions. Ainsi, tout attributapparaissant en argument d’une opération est remplacé par une expression d’attributs.

VINS V

RÉSULTAT

B.NOM, B. PRÉNOM

A.NV V.NV=

B.NOMB. PRÉNOM

A.NVV.NV

B.NB

B.NBB.NOM

B. PRÉNOM

A.NBA.NV

=V. CRU “CHABLIS”

LIKEB.ADRESSE “PARIS” ≥A. DATE 01.01.92

BUVEURS B ABUS A

=


Voici des exemples d’expressions d’attributs :10 + 50 – 23 ;QUANTITE * 50 ;QUANTITE * DEGRE / 100 ;QUANTITE – QUANTITE * DEGRE / 100.

De telles expressions peuvent donc être utilisées comme arguments de projections, derestrictions voire de jointures. Le programme d’algèbre relationnelle suivant illustreces possibilités :

R1 = JOIN (VINS, ABUS, DEGRE*QUANTITE/100 > QUANTITE/10)R2 = RESTRICT(R1, DEGRE*QUANTITE/100 > 10)RESULTAT = PROJECT(R2, CRU, QUANTITE – QUANTITE*DEGRE/100)

La notion d’expression d’attributs peut être généralisée avec des fonctions autres que lesfonctions arithmétiques, par exemple des fonctions écrites dans un langage externe. Onaboutit ainsi à une généralisation de l’algèbre relationnelle aux fonctions [Zaniolo85].

7.2. SUPPORT DES AGRÉGATS

Les expressions d’attributs permettent d’effectuer des opérations de calcul en ligne,sur des attributs de relations. En pratique, il est nécessaire d’effectuer des opérationsde calcul en colonnes, sur des tuples de relations, cela par exemple afin de sommerdes dépenses, etc. Le concept d’agrégat permet de telles opérations.

Les fonctions de calcul sur ensemble les plus souvent proposées sont :– SOMME (SUM) permettant de calculer la somme des éléments d’un ensemble ;– MOYENNE (AVG) permettant de calculer la moyenne des éléments d’un ensemble ;– MINIMUM (MIN) permettant de sélectionner l’élément minimum d’un ensemble ;– MAXIMUM (MAX) permettant de sélectionner l’élément maximum d’un ensemble ;– COMPTE (COUNT) permettant de compter les éléments d’un ensemble.

La figure VI.30 illustre le concept d’agrégat. La table VINS est enrichie d’un attributQUANTITE. L’agrégat représenté calcule la somme des quantités par CRU. L’opéra-tion générique s’écrit :

R = AGREGAT(<RELATION> ; <ATTRIBUT1> ; <FONCTION>{<ATTRIBUT2>})

Notion VI.28 : Agrégat (Aggregat)

Partitionnement horizontal d’une relation en fonction des valeurs d’un groupe d’attributs, suivi d’unregroupement par application d’une fonction de calcul sur ensemble.

Notion VI.27 : Expression d’attributs (Attribut expression)

Expression arithmétique construite à partir d’attributs d’une relation et de constantes, par applica-tion de fonctions arithmétiques successives.


<Attribut1> représente un ou plusieurs attributs utilisés pour le partitionnement.Fonction est la fonction d’ensemble appliquée à l’attribut <Attribut2>. Parexemple, on écrit :

RESULTAT = AGREGAT(VINS ; CRU ; SUM{QUANTITE})

pour l’agrégat illustré figure VI.30. Notez qu’un agrégat peut s’effectuer sans parti-tionnement ; on peut par exemple calculer simplement la moyenne de tous les degréscomme indiqué figure VI.30 par la commande :

RESULTAT = AGREGAT(VINS ; ; AVG{DEGRE}).

Figure VI.30 : Exemples de calcul d’agrégats

8. CONCLUSIONDans ce chapitre, nous avons introduits les concepts essentiels aujourd’hui supportéspar le modèle relationnel dans les grands systèmes industriels tels que ORACLE,INGRES, DB2, SYBASE, etc. Ces concepts constituent la base du langage SQL, lelangage des systèmes relationnels. Nous allons étudier ce langage et ses extensionsdans les chapitres qui suivent.

Le modèle relationnel fait aujourd’hui autorité dans l’industrie. Issu de la théorie des rela-tions, il est à l’origine une remarquable construction de la recherche. Il a su progressive-

VINS CruVOLNAYVOLNAYCHABLISCHABLISJULIENAS

Mill19831979198319921986

Degré11,711,311,411,812,0

Quantité100200250300400

MOY Degré11,64

SUM CruVOLNAYCHABLISJULIENAS

Quantité300550400

AGREGAT(VINS; CRU; SUM{QUANTITE})

AGREGAT(VINS;; AVG{DEGRE})


ment intégrer des concepts de plus en plus riches, tels que l’intégrité référentielle, lesrègles actives, etc. Le modèle a aujourd’hui intégré les concepts de l’objet pour fonderl’objet-relationnel, comme nous le verrons dans la troisième partie de cet ouvrage. Il aencore un bel avenir devant lui, bien qu’il soit parfois contesté par les tenants de l’objet.

9. BIBLIOGRAPHIE[Berstein81] Bernstein P., Goodman N., « The Power of Natural Semijoins », Siam

Journal of Computing, vol. 10, n° 4, décembre 1981, p. 751-771.

Une discussion de la puissance de l’opérateur de semi-jointure. Après une défi-nition de la semi-jointure, Phil Bernstein et Nathan Goodman montrent que cetopérateur permet d’exprimer un grand nombre de questions avec jointures,plus spécifiquement toutes celles dont le graphe des jointures est un arbre.

[Chen76] Chen P.P., « The Entity-Relationship Model – Towards a Unified View ofData », ACM Transactions on Database Systems, vol. 1, n° 1, mars 1976.

L’article de base sur le modèle entité-association. Il introduit ce modèle pourdécrire la vue des données d’une entreprise. En particulier, les diagrammes deChen sont présentés. Il est montré que le modèle permet d’unifier les différentspoints de vue et de passer simplement à une implémentation relationnelle. Cedernier point explique le fait que beaucoup d’outils d’aide à la conception debases de données relationnelles utilisent une variante du modèle de Chen.

[Childs68] Childs D.L., « Feasibility of a Set-Theoretic Data Structure – A GeneralStructure Based on a Reconstituted Definition of a Relation », Congrès IFIP,Genève, 1968, p. 162-172.

Un des premiers articles proposant un modèle basé sur le concept de relation etdes opérateurs ensemblistes. La proposition de Codd s’est inspirée des travauxde Childs.

[Codd70] Codd E.F., « A Relational Model for Large Shared Data Banks »,Communications de l’ACM, vol. 13, n° 6, juin 1970, p. 377-387.

L’article de base proposant le modèle relationnel. Il introduit les conceptsessentiels de relation, domaine, attribut et clé. L’algèbre relationnelle est pro-posée comme langage de manipulation des relations.

[Codd79] Codd E.F., « Extending the Relational Model to Capture More Meaning »,ACM TODS, vol. 4, n° 4, décembre 1979, p. 397-433.

Une proposition d’extension du modèle relationnel pour mieux décrire lasémantique des applications. L’idée de base est de distinguer différents types de


relations (entité, association, généralisation, etc.) et d’étendre les opérateursrelationnels en conséquence. Un traitement des valeurs nulles avec une logiquetrivaluée est aussi proposé. L’ensemble du modèle étendu, appelé RM/T, estdécrit par un métamodèle relationnel.

[Date81] Date C.J., « Referential Integrity », 7e Very Large Data Bases, Cannes,France, 1981, IEEE Ed.

L’article proposant le support de l’intégrité référentiel au sein du modèle rela-tionnel. Chris Date introduit les contraintes référentielles et les contraintesd’entité comme contraintes de base à intégrer au modèle relationnel pour unmeilleur support de la sémantique des données. Un langage de déclaration decontraintes est aussi esquissé.

[Delobel83] Delobel C., Adiba M., Bases de Données et Systèmes Relationnels, livre,Dunod Informatique, 1983.

Un des premiers livres français sur les bases de données relationnelles. Alorsque le livre Bases de Données – Les Systèmes et Leurs Langages de GeorgesGardarin paru à la même époque propose une vue simplifiée des différentsconcepts, ce livre offre une vision plus formelle, souvent fondée sur les travauxde l’université de Grenoble. Des opérateurs relationnels spécifiques et uneapproche originale à la normalisation des relations sont notamment développés.

[Fagin80] Fagin R., « A Normal Form for Relational Databases that is Based onDomains and Keys », ACM TODS, vol. 6, n° 3, septembre 1981, p. 387-415.

Un des articles prosant une forme ultime de normalisation des relations. Unerelation est en 5e forme normale si elle ne peut plus être décomposée par pro-jection sur différents sous-schémas, de sorte à obtenir la relation de départ parjointures naturelles des sous-relations. Fagin introduit une méthode de norma-lisation fondée sur les domaines et les clés. Il montre qu’il s’agit là de la formeultime de normalisation par projection et jointure. Il introduit aussi un opéra-teur d’éclatement qui permet d’envisager d’autres formes de normalisationhorizontale.

[Gardarin89] Gardarin G., Cheiney J.P., Kiernan J., Pastre D., « Managing ComplexObjects in an Extensible DBMS », 15th Very Large Data Bases InternationalConference, Morgan Kaufman Pub., Amsterdam, Pays-Bas, août 1989.

Une présentation détaillée du support d’objets complexes dans le SGBD exten-sible Sabrina. Ce système est dérivé du SGBD relationnel SABRE et supportedes types abstraits comme domaines d’attributs. Il a aujourd’hui évolué vers unSGBD géographique (GéoSabrina) et est commercialisé par INFOSYS.

[ISO89] International Organization for Standardization, « Information ProcessingSystems – Database Language SQL with Integrity Enhancement »,International Standard ISO/IEC JTC1 9075 : 1989(E), 2e édition, avril 1989.


La norme SQL aujourd’hui en vigueur. Ce document de 120 pages présente lanorme SQL1 : concepts de base, éléments communs, langage de définition deschémas, définition de modules de requêtes, langage de manipulation. Toutes lagrammaire de SQL1 est décrite en BNF. Ce document résulte de la fusion dustandard de 1986 et des extensions pour l’intégrité de 1989.

[Maier83] Maier D., The Theory of Relational Databases, livre, Computer SciencePress, 1983.Le livre synthétisant tous les développements théoriques sur les bases de don-nées relationnelles. En 600 pages assez formelles, Maier fait le tour de la théo-rie des opérateurs relationnels, des dépendances fonctionnelles, multivaluées etalgébriques, et de la théorie de la normalisation.

[Stonebraker87] Stonebraker M., « The Design of the POSTGRES Storage System »,13th Very Large Databases International Conference, Morgan & Kauffman Ed.,Brighton, Angleterre, 1987.Une description assez complète du système POSTGRES, successeur d’INGRESdéveloppé à Berkeley. M. Stonebraker présente la conception du noyau de stoc-kage du système POSTGRES. Outre un contrôle de concurrence original per-mettant le support de déclencheurs (ou réflexes), ce sytème intégre les typesabstraits au modèle relationnel. Un type abstrait permet de définir un typed’attribut ou de tuple. Le système POSTGRES a ainsi permis de prototyper lesfonctionnalités orientées objets intégrées à la version 7 d’INGRES.

[Ullman88] Ullman J.D., Principles of Database and Knowledge-base Systems, livres,volumes I et II, Computer Science Press, 1988.Deux volumes très complets sur les bases de données, avec une approche plutôtfondamentale. Jeffrey Ullman détaille tous les aspects des bases de données,des méthodes d’accès aux modèles objets en passant par le modèle logique. Leslivres sont finalement centrés sur une approche par la logique aux bases dedonnées. Les principaux algorithmes d’accès, d’optimisation de requêtes, deconcurrence, de normalisation, etc. sont détaillés.

[Zaniolo83] Zaniolo C., « The Database Language GEM », ACM SIGMODConférence, San José, Ca., ACM Ed., 1983.Une extension du modèle relationnel vers le modèle entité-association et du lan-gage QUEL pour supporter un tel modèle. Carlo Zaniolo propose d’utiliser lesentité pour spécifier les domaines lors de la définition des associations. Il proposealors une extension de QUEL avec une notation pointée pour naviguer depuis lesassociations vers les attributs des entités. L’ensemble constitue le langage GEM,qui a été implémenté à Bell Labs au-dessus de la machine bases de données IDM.

[Zaniolo85] Zaniolo C., « The Representation and Deductive Retrieval of ComplexObjects », 11th Very Large Data Bases International Conference, MorganKaufman Pub., Stockholm, Suède, août 1985.


Une extension de l’algèbre relationnelle au support de fonctions. Cet articleprésente une extension de l’algèbre relationnelle permettant de référencer desfonctions symboliques dans les critères de projection et de sélection, afin demanipuler des objets complexes. Des opérateurs déductifs de type fermeturetransitive étendue sont aussi intégrés.


Documents

Groupe Eyrolles 2003, ISBN 2-212-11281-5 · quence, le modèle relationnel peut apparaître comme un modèle mathématique simple des données. De plus, grâce à la représentation