Dans la création de la table Restaurant, remplacer

rID integer,

par

rID integer PRIMARY KEY,

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

pseudonyme varchar(30),
dateInscription date

par

UNIQUE (pseudonyme varchar(30),
dateInscription date)

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

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

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.

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

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

SELECT pseudonyme FROM Evaluateur JOIN Evaluation WHERE COUNT>=3

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

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 :

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 :

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

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

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 :

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.

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.

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

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 t₁ et t₂ ayant la même projection sur X, a fortiori leurs projections sur Y sont égales : σ_Re est correcte.
• On suppose que les tuplets t₁ et t₂ 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 t₁ et t₂ 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.

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 :

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

S = {'A':'D', 'AB':'E', 'BF':'E', 'CD':'F', 'E':'C'}

def fermeture(X):
    Cl = {x for x in X}
    done = False
    while not done:
        done = True
        for rule in S:
            Z = set(S[rule])
            if set(rule).issubset(Cl) and not Z.issubset(Cl):
                Cl |= Z
                done = False
    return Cl

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.

• 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⁺.

Le dictionnaire devient

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.

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)

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

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

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

• Le système est correct : si on pouvait produire dans le système (σ_Re,σ_P) 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 (σ_Re,σ_P) cqfd.