CAPES NSI 2020 Épreuve 1, Problème 2

mardi 28 juillet 2020
par  Alain BUSSER , Sébastien HOARAU

Le second problème du sujet de CAPES (épreuve 1, sujet ici) portait sur le système de déduction d’Armstrong. Celui-ci est basé sur la logique naturelle de Gentzen que nous allons découvrir à cette occasion.

%3 r1 Y⊆X r2 X→Y r1->r2 a1 Y→X a2 W∪X→W∪Y a1->a2 t0 X→Y t2 X→Z t0->t2 t1 Y→Z t1->t2

1 Interrogation et manipulation de bases de données

1. Contraintes et requêtes en SQL

Corrigé effectué grâce à l’aide de Rafaël Lopez (IUT Orsay)

(a) rID est la clé primaire de la relation Restaurant

Dans la création de la table Restaurant, remplacer

rID INTEGER,

par

rID INTEGER PRIMARY KEY,

(b) clés de la relation Evaluateur

eID est la clé primaire de la relation Evaluateur.

Dans la création de la table Evaluateur, remplacer

eID INTEGER,

par

eID INTEGER PRIMARY KEY,

Le couple (pseudonyme,dateInscription) est également clé.

Dans la création de la table Evaluateur, remplacer

  1. pseudonyme VARCHAR(30),
  2. dateInscription DATE

Télécharger

par

  1. UNIQUE (pseudonyme VARCHAR(30),
  2. dateInscription DATE)

Télécharger

(c) eID=135

Déterminer tous les restaurants qui ont été évalués par l’évaluateur dont l’eID est 135 :

  1. SELECT DISTINCT R.rID, nom
  2.         FROM Restaurant R
  3.         JOIN Evaluation E ON R.rID = E.rID
  4.                 WHERE eID = 135;

Télécharger

(d) paires d’évaluateurs ayant évalué le même restaurant

  1. SELECT DISTINCT EV1.eID, EV1.pseudonyme, EV2.eID, EV2.pseudonyme
  2.     FROM Evaluation E1
  3.             JOIN Evaluateur EV1 ON E1.eID = EV1.eID
  4.             JOIN Evaluateur EV2 ON EV1.RID = EV2.RID
  5.             JOIN Evaluation E2 ON E2.eID = EV2.eID
  6.                     WHERE EV1.eID < EV2.eID;

Télécharger

(e) note plus élevée la seconde fois

Pour tous les cas où la même personne note deux fois le même restaurant et donne une note plus élevée la seconde fois, retourner le pseudonyme de l’évaluateur et le nom du restaurant.

  1. SELECT R.rID, nom, E.eID, pseudonyme
  2.         FROM Restaurant R
  3.                 INNER JOIN Evaluation EV ON R.rID = EV.rID
  4.                 INNER JOIN Evaluateur E ON EV.eID = E.eID
  5.                 GROUP BY R.rID, nom, E.eID, pseudonyme
  6.                         HAVING COUNT(*) = 2
  7.                         HAVING COUNT(DISTINCT note) = 2

Télécharger

(f) Au moins 3 évaluations

Trouver le pseudonyme de tous les évaluateurs qui ont fait au moins 3 évaluations

SELECT pseudonyme FROM Evaluateur JOIN Evaluation WHERE COUNT>=3

(g) inclusions entre relations

Les restaurants de la relation Evaluations doivent être contenus dans la relation Restaurants :

FOREIGN KEY (rID) REFERENCES Restaurants

Les évaluateurs de la relation Evaluations doivent être contenus dans la relation Evaluateur :

FOREIGN KEY (eID) REFERENCES Evaluateur

2. Définition de propriétés

D’après les propriétés ACID,

  • l’atomicité (informatique) est la propriété d’une transaction de la base de données qui se fait sans interruption (ou alors pas du tout) ;
  • la cohérence (informatique) est la propriété d’une transaction qui aboutit à un état valide, du moins si la base de données était déjà valide avant la transaction ;
  • la persistence ou durabilité (informatique) est la garantie qu’une fois effectuée, la transaction ne sera plus annulée par la suite.

2 Inférence de dépendances fonctionnelles

Repères historiques

Gerhard Gentzen fit la remarque que pour David Hilbert une démonstration est une liste de résultats intermédiaires. Par exemple une preuve typique (selon Hilbert vu par Gentzen) partirait d’un axiome dont on déduirait un lemme dont on déduirait une proposition dont on déduirait un théorème :

axiome ⇒ lemme ⇒ proposition ⇒ théorème

Bref, si on dessine la démonstration sous forme d’un graphe orienté (les arêtes représentées par les flèches ⇒ de l’implication), ce graphe est linéaire : c’est une liste.

Mais Gentzen a surtout fait la remarque qu’en général une démonstration n’est pas linéaire, il arrive souvent qu’une conclusion soit déduite de plusieurs prémisses (le graphe est en réalité un arbre. Ce qui a posé un problème typographique à Gentzen : comment dessiner un arbre (racine en bas puisque c’est le théorème, feuilles en haut, les axiomes ou plutôt les hypothèses, Gentzen n’utilisant pas d’axiomes) ?

Gentzen a adopté une notation avec des traits horizontaux (celle que l’on voit dans l’énoncé). C’est la notation utilisée dans CoqIde. Mais surtout, Gentzen a fondé sa logique naturelle sur des règles de déduction et aucun axiome : tout en règles de déduction ! Dans cet article on va dessiner les déductions comme des arbres orientés, comme ceci :

%3 f1 Formule1 co Conclusion f1->co a . a->co b . b->co c . c->co fn Formule n fn->co

La déduction se lit du haut (les feuilles soit les hypothèses) vers le bas (la racine est la conclusion). Ou alors par chaînage arrière, auquel cas on se fixe des buts (les lemmes) et on y greffe leurs preuves au moment adéquat.

En 1970, E.F. Codd, qui travaillait pour IBM, a publié cette théorie algébrique des bases de données :

article de Codd (1970)
La fondation des bases de données relationnelles

Il base sa théorie sur la notion de relation (mathématiques), dûe à Gottlob Frege au XIXe siècle.

4 ans plus tard, W.W. Armstrong publie cette théorie :

article d’Armstrong (1974)
la fondation de la théorie des dépendances fonctionnelles

Il y insiste surtout sur la notion de dépendance fonctionnelle (existence d’une fonction entre certains attributs). Il formalise la notion de dépendance fonctionnelle par les axiomes notés F1, F2, F3 et F4 dans la partie 4 de l’article ci-dessus.

Mais, influencés par Gentzen, les auteurs du sujet ont préféré remplacer les axiomes d’Armstrong, par trois règles de déduction (réflexivité pour F1, augmentation pour F4 et transitivité pour F2).

Voici les trois règles de déduction du système d’Armstrong :

%3 r1 Y⊆X r2 X→Y r1->r2 a1 Y→X a2 W∪X→W∪Y a1->a2 t0 X→Y t2 X→Z t0->t2 t1 Y→Z t1->t2

La première (réflexivité, à gauche) dit que si Y est dans X, on peut construire (par projection) une dépendance fonctionnelle entre X et Y (l’identité).

La seconde (augmentation, au milieu) généralise la première : par restriction on peut étendre une dépendance au cas où on a rajouté W.

La troisième (transitivité, à droite) dit que la composition des fonctions permet de construire une dépendance fonctionnelle entre X et Z.

3. Une anomalie de mise à jour est ce qui se passe si un enregistrement est actualisé (après une requête de type UPDATE) mais qu’un autre enregistrement qui en dépend fonctionnellement, n’est pas actualisé.

Un exemple

Par exemple, si un critique a donné une note au Resto astronomique et qu’ensuite le webmestre constate, grâce à l’adresse du restaurant, qu’il s’agit en réalité du Resto gastronomique (le critique s’est trompé en entrant le nom du restaurant), il s’avère nécessaire de remplacer astronomique par gastronomique dans chacun des champs où apparaît ce mot. Si le remplacement n’est pas systématique, les notes données au Resto astronomique ne seront pas comptabilisées pour le Resto gastronomique.

4. Une clé est ensemble d’attributs dont dépendent fonctionnellement tous les autres ensembles d’attributs.

5. La règle d’inférence suivante est fausse :

%3 t0 X→Y t2 Z→X t0->t2 t1 Y→Z t1->t2

Un contre-exemple

En effet, ses deux prémisses sont vérifiées par la relation suivante :

clé X Y Z
1 a A x
2 b A x
3 c B y

X est une clé donc la dépendance fonctionnelle de Y par rapport à X est assurée, et chaque fois que Y==A on a Z==x donc Z dépend fonctionnellement de Y. Mais les enregistrements de clé primaire 1 et 2 vérifient Z==x sans avoir la même valeur de X : X ne dépend pas fonctionnellement de Z.

6. L’exemple de la question 5 produit une dépendance fonctionnelle (entre Z et X) non valide : l’ajout de la règle d’inférence de la question 5 est incorrect.

7. Le système d’inférence d’Armstrong est correct parce que chacune de ses règles est correcte :

  • Si Y⊆X, alors pour les tuplets t1 et t2 ayant la même projection sur X, a fortiori leurs projections sur Y sont égales : σRe est correcte.
  • On suppose que les tuplets t1 et t2 ont même projection sur W∪X. Alors
    • ils ont même projection sur W,
    • ils ont même projection sur X, d’où par hypothèse (la prémisse de σA) ils ont également même projection sur Y.
      Ils ont donc même projection sur W∪Y : σA est correcte.
  • On suppose que les tuplets t1 et t2 ont la même projection sur X. Alors d’après la première prémisse de σT ils ont également la même projection sur Y, et d’après la seconde prémisse de σT ils ont donc également la même projection sur Z : σT est donc correcte également.

8. En notant A, B, C, D, E et F les attributs d’une relation R,

(a) Comme E⊆C∪E, la règle σRe (réflexivité) permet de conclure que C∪E→E.

(b) On suppose que A∪B→B∪C et que D→A (hypothèses). En utilisant le schéma d’axiomes C⊆B∪C on en déduit que B∪D→C

La preuve

%3 s1 A∪B→B∪C s4 B∪D→B∪C s1->s4 transitivité s2 D→A s3 B∪D→B∪A s2->s3 augmentation s3->s4 s7 B∪D→C s4->s7 transitivité s5 C⊆B∪C s6 B∪C→C s5->s6 réflexivité s6->s7

On note ceci sous la forme {A∪B→B∪C,D→A}⊨B∪D→C

(c) {A∪B→C,A→D,C∪D→E∪F}⊨A∪B→F

La preuve

On utilise le fait que A∪A∪B=A∪B (réécriture) et le fait que F⊆E∪F. Les autres feuilles de cet arbre sont les hypothèses :

%3 s1 A∪B→C s3 A∪B→A∪C s1->s3 augmentation s2 A→D s4 A∪C→C∪D s2->s4 augmentation s5 A∪B→C∪D s3->s5 transitivité s4->s5 s8 A∪B→E∪F s5->s8 transitivité s6 C∪D→E∪F s6->s8 s7 F⊆E∪F s9 E∪F→F s7->s9 réflexivité co A∪B→F s8->co transitivité s9->co

3 Fermeture transitive

La relation X→Y peut être représentée par un graphe orienté (potentiellement infini) et l’algorithme de l’énoncé construit sa fermeture transitive par un parcours du graphe en largeur.

En Python

On utilise un ensemble d’ensembles (A,B,C,D,E,F) :

  1. S = {'A':'D', 'AB':'E', 'BF':'E', 'CD':'F', 'E':'C'}
  2.  
  3. def fermeture(X):
  4.     Cl = {x for x in X}
  5.     done = False
  6.     while not done:
  7.         done = True
  8.         for rule in S:
  9.             Z = set(S[rule])
  10.             if set(rule).issubset(Cl) and not Z.issubset(Cl):
  11.                 Cl |= Z
  12.                 done = False
  13.     return Cl

Télécharger

Les dépendances fonctionnelles sont dans un dictionnaire S (pour Σ) et l’algorithme renvoie l’ensemble des attributs qui sont dans la fermeture de X. Les réponses à la question 9 sont obtenues en appelant la fonction ci-dessus sur les chaînes F, BF et ABF.

9. Dans cette question on considère l’ensemble Σ={A→D,A∪B→E,B∪F→E,C∪D→F,E→C}

(a) La fermeture de F est F.

(b) La fermeture de B∪F est B∪C∪E∪F.

(c) La fermeture de A∪B∪F est A∪B∪C∪D∪E∪F.

Toute dépendance fonctionnelle peut être obtenue uniquement à partir de A∪B∪F : A∪B∪F est une clé de la relation R.

10. Soit le lemme : Σ⊨X→Y si et seulement si Y⊆X+

Démonstration du lemme

  • Si Y⊆X+ alors par définition de la fermeture transitive, on a Σ⊨X→Y.
  • Réciproquement, si Σ⊨X→Y alors à un moment donné, l’algorithme précédent va ajouter Y à la variable Cl et donc Y⊆X+.

On considère Σ={A→B∪C∪D,A∪B∪E→G,C∪D→E,E∪G→A∪B∪D,B∪E→F,F∪G→A}

En Python

Le dictionnaire devient

  1. S = {'A':'BCD', 'ABE':'G', 'CD':'E', 'EG':'ABD', 'BE':'F','FG':'A'}

Avec ce nouveau dictionnaire on obtient les réponses aux prochaines questions en appelant la même fonction fermeture avec les variables A puis BEF.

(a) La fermeture de A est A∪B∪C∪D∪E∪F∪G (calculée avec l’algorithme 1), et F⊆A∪B∪C∪D∪E∪F∪G. En appliquant le lemme on en déduit que Σ⊨A→F.

(b) La fermeture de B∪E∪Fest B∪E∪F. A⊈B∪E∪F donc d’après le lemme,Σ ⊭B∪E∪F→A donc B∪E∪F n’est pas une clé de R.

11. La fermeture est une fermeture (au sens de la morphologie mathématique)

Preuve

La fermeture φ est

  • extensive : par réflexivité, X→X donc X⊆φ(X)
  • croissante : si X⊆Y alors par augmentation φ(X)⊆φ(Y)
  • idempotente : par transitivité φ(φ(X))=φ(X)

4 Équivalence de systèmes d’inférence

On considère la nouvelle règle d’inférence suivante (pseudo-transitivité σP) :

%3 s1 X→Y s4 W∪X→Z s1->s4 s2 W∪Y→Z s2->s4

12. Toute preuve de Σ⊨X→Y utilisant la règle σP peut être transformée en une preuve n’utilisant que σA et σT.

Comment ?

Il suffit de remplacer dans la preuve (qui est un arbre comme on l’a vu) chaque occurence de σP par cet arbre :

%3 s1 X→Y s3 W∪X→W∪Y s1->s3 augmentation s2 W∪Y→Z s4 W∪X→Z s2->s4 s3->s4 transitivité

13. Toute preuve de Σ⊨X→Y utilisant les règles σRe, σA et σT peut être transformée en une preuve n’utilisant que σRe et σP.

Comment ?

  • Pour obtenir σA dans le nouveau système :

%3 s1 X→Y s4 W∪X→W∪Y s1->s4 pseudo-transitivité s2 W∪Y⊆W∪Y s3 W∪Y→W∪Y s2->s3 réflexivité s3->s4

  • Pour obtenir σT dans le nouveau système :

%3 s1 X→Y s3 X∪Y→Z s1->s3 pseudo-transitivité s4 X∪X→Z s1->s4 s2 Y∪Y→Z s2->s3 s3->s4 pseudo-transitivité

14. Le système (σReP) est correct et complet.

Preuve

  • Le système est correct : si on pouvait produire dans le système (σReP) une dépendance fonctionnelle non valide, la question 12 permettrait de construire une dépendance non valide dans le système d’Armstrong, or ce n’est pas possible d’après la question 7.
  • Le système est complet : Toute dépendance valide possède une preuve dans le système d’Armstrong, et la question 13 permet de transformer cette preuve en une preuve dans le système (σReP) cqfd.

Commentaires