Variables libres, variables liées et requêtes dans le cadre du calcul relationnel

Rappel

Les notions d'occurrence de variables libres et liées dans une formule sont définies de la manière usuelle. Une occurrence d'une

variable \(x\) est libre dans une formule \(\varphi\) si :

  • \(\varphi\) est un atome ;

  • ou \(\varphi = (\psi \wedge \xi)\) et l'occurence de \(x\) dqns \(\psi\) ou \(\xi\) est libre ;

  • ou \(\varphi = \exists y \ \psi, x\) et \(y\) sont des variables distinctes, et l'occurrence de \(x\) est libre dans \(\psi\).

L'ensemble \(libre(\varphi)\) est l'ensemble des variables qui ont au moins une occurrence libre dans \(\varphi\). Une variable est liée si elle n'est pas libre.

Définition

Nous étendons les notions d'occurrence de variables libres et liées déjà introduites. Une occurrence d'une variable \(x\) est libre dans une formule \(\varphi\) si :

  • \(\varphi\) est un atome;

  • ou \(\varphi = (\psi \wedge \xi)\) et l'occurrence de \(x\) dans \(\psi\) ou \(\xi\) est libre (et idem pour \(\vee\));

  • \(\varphi = \exists y \ \psi\), \(x\) et \(y\) sont des variables distinctes, et l'occurrence de \(x\) est libre dans \(\psi\) (et idem pour \(\forall\)).

Rappel

Une requête est définie comme une expression de la forme:

\(\{t_1,\dots,t_m \mid \varphi\}\)

où \(t_1,\dots,t_m\) sont des termes et où l'ensemble des variables apparaissant dans \(t_1,\dots,t_m\) est exactement \(libre(\varphi)\).