theory.anubis
8.69 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
Une petite théorie des bases de données relationnelles.
*** Définitions générales.
Considérons un certain nombre d'ensembles (en fait de types de données) donnés à
l'avance. En général, dans les systèmes de bases de données courants, ces types sont
les entiers (INT) les chaînes de caractères (STRING), les booléens (BOOL), et
éventuellement quelques autres.
On peut considérer des types plus complexes en faisant des produits cartésiens de
types. Pour representer les clients d'une entreprise, on utilisera par exemple le
produit cartésien: STRING x STRING x INT, où chacun des trois facteurs représente
respectivement, le nom, l'addresse et le solde du client. En fait, faire un tel
produit cartésien revient à définir les champs pour l'enregistrement d'un client. Les
éléments d'un tel produit cartésien seront d'ailleurs appelés des 'enregistrements'.
Une 'relation' (au sens des bases de données relationnelles) est une partie d'un tel
produit cartésien, qui est non seulement finie, mais explicitement énumérée. En fait,
une relation peut être tout simplement considérée comme une liste (bien entendu finie)
d'enregistrements. On peut bien sûr voir aussi cette relation sous la forme d'une
table, où chaque champ correspond à une colonne et chaque ligne à un enregistrement. On
dira d'une telle relation qu'elle est 'incluse' dans le produit cartésien considéré.
Une 'base de données' est un ensemble fini de relations. Dans une bases de données,
chaque relation a un nom qui l'identifie sans ambigüité dans la base de données, de
même que dans une relation (table), chaque champ (colonne) a un nom qui l'identifie
sans ambigüité dans la relation. Si le système est sensé pouvoir manipuler plusieurs
bases de données, chaque base de données a elle-même un nom qui l'identifie sans
ambigüité dans le système. Si on suppose par exemple, qu'on a un champ de nom 'C', dans
une relation de nom 'R', dans une base de donnéees de nom 'B', on pourra désigner ce
champ par la notation: B.R.C, ou: R.C si la base de données est connue, ou simplement C
si la relation est connue.
Le role du système de gestion de bases de données est de stocker les bases de données
(donc les relations) sur un média persistant (disque dur en général), mais aussi d'être
capable de manipuler ces données pour satisfaire les interrogations des utilisateurs du
système. En fait les utilisateurs peuvent soit interroger le système sans modifier les
données, soit imposer (s'ils en ont le droit) des modifications des bases de données
et/ou des relations (ajout/modification/suppression d'enregistrement, de relation, de
bases de données).
*** Interrogation.
Elle est fondée sur trois opérations fondamentales portant sur les relations:
- le produit,
- la projection,
- la sélection.
Ces opérations peuvent être combinées pour produire des opérations plus complexes.
Le 'produit' de deux relations est simplement le produit cartésien au sens
mathématique. Si R1 et R2 sont des relations, disons:
R1 est une partie finie de X x Y x Z
R2 est une partie finie de U x V
Alors le produit R1 x R2 sera une partie finie de X x Y x Z x U x V. Précisément, il
s'agira de tous les quintuplets (x,y,z,u,v) qu'on peut former en prenant un triplet
(x,y,z) dans R1 et un couple (u,v) dans R2, de toutes les façons possibles. Il est
clair qu'on peut calculer R1 x R2 sous forme de liste à partir des listes décrivant R1
et R2. Bien entendu si le nombre d'enregistrement de R1 est n et si le nombre
d'enregistrements de R2 est m, le nombre d'enregistrements de R1 x R2 sera égal au
produit nm. On peut bien entendu faire aussi le produit de plus de deux relations.
Pour 'projeter' une relation R1, disons une partie finie de X x Y x Z, il faut d'abord
choisir sur quoi on projette. Pour cela il faut sélectionner des facteurs dans le
produit X x Y x Z. Par exemple, on peut sélectionner X et Z. On projette alors le
produit X x Y x Z sur le produit X x Z. Mathématiquement, cette projection est la
fonction:
(x,y,z) |-> (x,z)
La projection de R1 est alors par définition l'image de R1 par cette fonction. Par
exemple, si la relation R1 est la suivante (sous forme de table):
X Y Z
-------------
a b c
a d e
f g h
a g c
La projection sur le produit X x Z sera:
X Z
---------
a c
a e
f h
Noter que cette projection de R1 n'a que trois éléments, alors que R1 en a 4. Ceci est
du au fait qu'une projection n'est en général pas injective. Dans le cas de l'exemple,
les triplets (a,b,c) et (a,g,c) ont la même projection.
Enfin, si R1 est une relation incluse dans X x Y x Z, on peut imposer une condition aux
éléments de R1, ce qui sélectionne une partie de R1, qui est a fortiori finie. Par
exemple, en prenant la même relation R1 que ci dessus, et en imposant la condition que
le champ correspondant à Y ait pour valeur g, on obtient la sous-relation suivante:
X Y Z
-------------
f g h
a g c
Cette opération de sélection revient donc tout simplement à supprimer des
enregistrements, c'est à dire des lignes dans la table (alors que la projection
supprime des colonnes).
Bien entendu, les conditions pouvant être imposées peuvent être conçues de manière plus
ou moins sophistiquées. Elles peuvent se présenter sous forme d'égalités (comme dans
l'exemple ci-dessus), ou d'inégalité, etc..., de plus on doit pouvoir faire des
opérations booléennes sur ces conditions (et, ou, implique, non).
*** Un exemple réaliste.
Considérons trois relations tout à fait standard pour une entreprise. Dans ces
relations nous ne représentons qu'une seule ligne:
Clients
----------------------
Id Name Address
----------------------
.
.
.
23 Bush White House
.
.
.
Products
------------------------
Id Name Color
------------------------
.
.
.
45 rocket black
.
.
.
Sales
---------------------------
Id ClientId ProductId
---------------------------
.
.
.
67 23 45
.
.
.
Supposons maintenant que nous voulions connaitre les noms de toutes les personnes qui
ont acheté une 'rocket'. Il suffit de faire le produit cartésien des trois relations,
puis d'imposer sur ce produit la condition suivante:
Clients.Id = Sales.ClientId
et Sales.ProductId = Product.Id
et Product.Name = rocket
puis de projeter sur le facteur Clients.Name. On obtiendra:
Result
---------------
Name
---------------
.
.
.
Bush
.
.
.
En SQL, la requête ci-dessus pourrait être écrite:
SELECT Clients.Name
FROM Clients, Sales, Products
WHERE Clients.Id = Sales.ClientId
AND Sales.ProductId = Product.Id
AND Product.Name = "rocket";
On voit que:
- ce qui suit SELECT détermine la projection,
- ce qui suit FROM détermine le produit,
- ce qui suit WHERE détermine la sélection.
Si vous avez compris cet exemple, vous avez compris l'essentiel des bases de donnéess
relationnelles et l'essentiel de SQL (Structured Query Language).
En fait, il est bien clair que dans la réalité on ne calcule pas le produit cartésien
des trois relations, car on risquerait de produire une très grande liste dont on
utilisera seulement une toute petite partie. Les systèmes de bases de données sont
équipés non seulement d'algorithmes plus malins pour faire ces calculs, mais même
d'optimiseurs de requêtes qui modifient la requête en une requête équivalente, mais
dont l'exécution est sensée aller plus vite. Toute ceci n'est pas trivial, et démontre
qu'on a intérêt à utiliser les systèmes existants pour faire des calculs, qui comme le
montre l'exemple, ne sont pas nécessairement évidents.
*** Modification.
L'opération la plus courante est d'ajouter/modifier/supprimer un enregistrement. On
peut aussi modifier une série d'enregistrements en se basant sur des conditions, qui
peuvent faire intervenir des produits.