Livre_silo 30 août 2013 16:32 Page 296
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
296
Informatique pour tous
Cet arbre enrichi de ces deux nouvelles informations est représenté dans la relation suivante :
R
id
Nom Parent bas haut
1
A
0
1
20
2
B
1
2
13
3
C
1
14
19
4
D
2
3
8
5
E
2
9
12
6
F
3
15
16
7
G
3
17
18
8
H
4
4
5
9
I
4
6
7
10
J
5
10
11
1 Montrer que dans une telle représentation, il est possible d’obtenir les descendants d’une valeur avec
une seule sélection.
2 Même question pour les ancêtres.
3 Parmi les ancêtres obtenus, comment peut-on distinguer le père ? En déduire que l’attribut Parent est
redondant.
4 Indiquer comment on peut modifier la relation pour ajouter un fils à la valeur E tout en préservant les
valeurs bas et haut afin qu’elles correspondent toujours à un parcours de l’arbre.
5 Même question pour la suppression d’une des valeurs sans enfant.
Exercice 11.16 ** On démontre que la division cartésienne de deux relations R et R ′ est bien définie. Si
Q est une relation, on appelle P la propriété « il existe une relation R ′′ vérifiant (Q × R ′ ) ∪ R ′′ = R et
(Q × R ′ ) ∩ R ′′ = ∅ ».
Démontrer que :
1 Il existe une relation Q vérifiant la propriété P .
2 Si deux relations Q 1 et Q 2 vérifient la propriété P , alors Q 1 ∪ Q 2 vérifie également P .
Conclure.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
296
Informatique pour tous
Cet arbre enrichi de ces deux nouvelles informations est représenté dans la relation suivante :
R
id
Nom Parent bas haut
1
A
0
1
20
2
B
1
2
13
3
C
1
14
19
4
D
2
3
8
5
E
2
9
12
6
F
3
15
16
7
G
3
17
18
8
H
4
4
5
9
I
4
6
7
10
J
5
10
11
1 Montrer que dans une telle représentation, il est possible d’obtenir les descendants d’une valeur avec
une seule sélection.
2 Même question pour les ancêtres.
3 Parmi les ancêtres obtenus, comment peut-on distinguer le père ? En déduire que l’attribut Parent est
redondant.
4 Indiquer comment on peut modifier la relation pour ajouter un fils à la valeur E tout en préservant les
valeurs bas et haut afin qu’elles correspondent toujours à un parcours de l’arbre.
5 Même question pour la suppression d’une des valeurs sans enfant.
Exercice 11.16 ** On démontre que la division cartésienne de deux relations R et R ′ est bien définie. Si
Q est une relation, on appelle P la propriété « il existe une relation R ′′ vérifiant (Q × R ′ ) ∪ R ′′ = R et
(Q × R ′ ) ∩ R ′′ = ∅ ».
Démontrer que :
1 Il existe une relation Q vérifiant la propriété P .
2 Si deux relations Q 1 et Q 2 vérifient la propriété P , alors Q 1 ∪ Q 2 vérifie également P .
Conclure.