Calcul relationnel

Introduction

Le calcul relationnel est une notation logique, où l’on exprimera les requêtes par la formulation de restrictions logiques que les éléments (tuples) retenus dans la réponse à la requête devront satisfaire.

Le calcul relationnel est basé sur la logique de premier ordre et le calcul des prédicats. Cette théorie mathématique étudie les formules logiques construites avec :

• un ensemble de prédicats (c’est-à-dire de propositions qui peuvent être vraies ou fausses dans un certain contexte)
• des opérateurs de comparaison (\(=,!=,<,\leq,>,\geq\))
• de négation (\(\neg\)),
• des connecteurs logiques (\(\lor,\land\))
• l’implication (\(\Rightarrow\))
• les quantificateurs universel et existentiel (\(\forall,\exists\))

A chaque formule logique correspond l’ensemble des données qui vérifient cette formule.

L’interrogation de la base de données consiste donc à énoncer une formule qui correspond aux données que l’on souhaite extraire de la base.

Le lecteur intéressé trouvera plus d’informations au lien suivant Heurtebise

On distingue :

• calcul relationnel de domaine (DRC)
• calcul relationnel de tuples (TRC)

Dans le premier cas (DRC), les variables sont associées à des domaines d’attributs. Cette représentation de requêtes est issue des travaux sur le langage QBE (IBM).

Dans le deuxième cas (TRC), les variables sont associées à des n-uplets (tuples). Cette représentation de requêtes est issue des travaux sur le langage QUEL (INGRES).

Exemple : pour récupérer les nom et prix de tous les produits sur l’ensemble des produits (la table produits(id,nom,prix)) :

• calcul relationnel de domaine : \(E = \{ (nom,prix) | produits(-,nom,prix) \}\)
• calcul relationnel de tuples : \(E = \{ (p.nom,p.prix) | produits(p) \}\)

Ces deux modes de calcul relationnel constituent deux sous-ensembles de la logique du premier ordre.

Remarque : dans le cas du TRC on peut utiliser indifféremment les notations suivantes :

• \(produits(p)\)
• \(p \in produits\)

pour signifier le fait que l’élément (le tuple) \(p\) est un produit de l’ensemble des \(produits\)

Calcul de domaines (DRC)

Le DRC est un langage d’interrogation de données formel permettant d’exprimer des questions à partir de formules bien formées dont chaque variable est interprétée comme variant sur le domaine d’un attribut de table.

Une requête en calcul relationnel de domaine s’écrit sous la forme :

• \(\{(x_1,x_2,...,x_n) \; \mid \; F(x_1,x_2,...,x_n)\}\)

où :

• \(F\) : est une formule logique
• \((x_1,x_2,...,x_n)\) : variables libres dans \(F\)

Une formule est construite à partir de prédicats atomiques (atomes) qui sont d’une des formes suivantes :

• Un atome de la forme \(R(x_1,x_2,....,x_n)\) où \(R\) est un nom de relation d’arité \(n\) et \(x_i\) une variable.
• Un atome de la forme \(x_i \; op \; x_j\) où \(op\) est un opérateur de comparaison classique, (\(x_i, x_j\)) des variables de domaines qui représentent les \(i^{eme}\) et \(j^{eme}\) valeurs du n-uplet.
• Un atome de la forme (\(x_i \; op \; c\)) ou (\(c \; op \; x_j\)) où \(c\) est une constante.

Une formule est constituée d’atomes connectés par les opérateurs logiques et (\(\land\)), ou (\(\lor\)), négation (\(\neg\)), les quantificateurs universel (\(\forall\)), existentiel (\(\exists\)) et se définit de la manière suivante :

• Tout atome est une formule.
• Si \(F_1\) et \(F_2\) sont des formules, alors (\(F_1 \land F_2\) ), (\(F_1 \lor F_2\) ), (\(\neg F_1\)) et (\(\neg F_2\)) sont des formules.
• Si \(F\) est une formule, alors (\(\exists x,F(x)\)) est une formule avec \(x\) variable nuplet.
• Si \(F\) est une formule, alors (\(\forall x,F(x)\)) est une formule avec \(x\) variable nuplet.

produits(id_prod, nom, quantite, couleur)

invitations (jour,personne)

Calcul de tuples (TRC)

Le TRC est un langage d’interrogation de données formel permettant d’exprimer des questions à partir de formules bien formées dont les variables sont interprétées comme variant sur les éléments (n-uplets) d’un ensemble (table).

Une requête en calcul relationnel de tuples s’écrit sous la forme :

• \(\{(t_1.x,t_1.y,t_2.u,t_2.v,...) \; \mid \; F(t_1,t_2 ...) \}\)

ou bien :

• \(\{(t_1.x,t_1.y,t_2.u,t_2.v,...) \; \mid \; F(t_1,t_2 ...) \land \; t_1 \in T_1 \land t_2 \in T_2 \; ... \}\)
• \(\{(t_1.x,t_1.y,t_2.u,t_2.v,...) \; \mid \; F(t_1,t_2 ...) \land \; T_1(t_1) \land T_2(t_2) \; ... \}\)

où :

• \(F\) : est une formule logique sur des éléments (tuples) \(t_1,t_2,...\) des ensembles \(T_1,T_2,...\)
• \((t_1.x,t_1.y,t_2.u,t_2.v...)\) : attributs des n-uplets (tuples) des ensembles \(T_1,T_2,...\)

Une formule est construite à partir de prédicats atomiques (atomes) qui sont d’une des formes suivantes :

• Un atome de la forme \(R(t_i)\) où \(R\) est un nom de relation et \(t_i\) une variable n-uplet.

  Cet atome identifie le domaine de la variable \(t_i\) comme celui de la relation de nom \(R\) (\(t_i\) est un n-uplet) .

• Un atome de la forme (\(t_i.x \; op \; t_j.u\)) (autre notation : \(t_i[x] \; op \; t_j[u]\)) où \(op\) est un opérateur de comparaison classique, (\(t_i, t_j\)) des variables n-uplets, et (\(x,u\)) des attributs des relations associées.

• Un atome de la forme (\(t_i.x \; op \; c\)) ou (\(c \; op \; t_j.u\)) où \(c\) est une constante.

Une formule est constituée d’atomes connectés par les opérateurs logiques et (\(\land\)), ou (\(\lor\)), négation (\(\neg\)), les quantificateurs universel (\(\forall\)), existentiel (\(\exists\)) et se définit de la manière suivante :

• Tout atome est une formule.
• Si \(F_1\) et \(F_2\) sont des formules, alors (\(F_1 \land F_2\) ), (\(F_1 \lor F_2\) ), (\(\neg F_1\)) et (\(\neg F_2\)) sont des formules.
• Si \(F\) est une formule, alors (\(\exists x,F(x)\)) est une formule avec \(x\) variable nuplet.
• Si \(F\) est une formule, alors (\(\forall x,F(x)\)) est une formule avec \(x\) variable nuplet.

produits(id_prod, nom, quantite, couleur)

invitations (jour,personne)