title: Datalog
text: # Datalog
  
  Datalog est un langage de requête et de règles pour les bases de données déductives. Il correspond à un sous ensemble de Prolog. Ses origines remontent aux débuts de la programmation logique.
  
  ## Syntaxe
  
  Datalog a la syntaxe $suivante^,.$ On fixe:
  
  * Un ensemble ${\mathcal {X}}$, dont les éléments sont appelés variables
  * Un ensemble ${\mathcal {D}}$, dont les éléments sont appelés constantes
  * Un schéma relationnel ${\mathit {Sch}}$, c'est-à-dire un ensemble fini de prédicats, à chaque prédicat étant associé un entier positif ou nul appelé arité
  * Une partition de ce schéma relationnel en deux sous-schémas, le schéma intensionnel et le schéma extensionnel (les prédicats sont donc soit intensionnels, soit extensionnels)
  * Un prédicat intensionnel distingué ${\mathit {But}}$
  
  Une règle Datalog est une expression de la forme: $S(\mathbf {y} )\leftarrow R_{1}(\mathbf {x} _{1}),\dots ,R_{n}(\mathbf {x} _{n})$ où $S$ est un prédicat intensionnel, $R_{1}\dots R_{n}$ sont des prédicats intensionnels ou extensionnels, et $\mathbf {x} _{1}\dots \mathbf {x} _{n}$ et $\mathbf {y}$ sont des n-uplets d'éléments de ${\mathcal {X}}\cup {\mathcal {D}}$, dont l'arité est compatible avec celle des prédicats. $S(\mathbf {y} )$ est appelé la tête de la règle, $R_{1}(\mathbf {x} _{1}),\dots ,R_{n}(\mathbf {x} _{n})$ son corps. On impose que chaque variable $y\in {\mathcal {Y}}$ apparaissant dans la tête de la règle apparaisse également dans son corps.
  
  Un programme Datalog est un ensemble fini de règles Datalog.
  
  ## Sémantique
  
  Fixons une instance $I_{0}$ du schéma extensionnel, c'est-à-dire une base de données relationnelle dont les tables sont des instances des prédicats extensionnels. Un programme Datalog $P$ définit une requête sur cette base de $données^,,$ l'arité de cette requête étant l'arité du prédicat ${\mathit {But}}$.
  
  Pour définir cette sémantique, observons tout d'abord que chaque règle $r\in P$ de la forme $S(\mathbf {y} )\leftarrow R_{1}(\mathbf {x} _{1}),\dots ,R_{n}(\mathbf {x} _{n})$peut être vue comme une requête sur des instances du schéma relationnel :
  
  $r(I):=\{S(\mathbf {y} )\mid \exists z_{1}\dots z_{k}~R_{1}(\mathbf {x_{1}} )\in I\land \dots \land R_{n}(\mathbf {x_{n}} )\in I\}$
  
  où $\{z_{1}\dots z_{k}\}$est l'ensemble des variables de ${\mathcal {X}}$ apparaissant dans le corps de la règle $r$.
  
  Introduisons l'opérateur de conséquence $\Gamma _{P}$ qui transforme une instance du schéma relationnel ${\mathit {Sch}}$ en une autre instance de ce même schéma, formée de l'instance initiale et de toutes ses conséquences par chaque règle de $P$ : $\Gamma _{P}(I):=I\cup \bigcup _{r\in P}\{r(I)\}$. Pour $n\in \mathbb {N}$, posons $I_{n+1}:=\Gamma _{P}(I_{n})$. Le résultat de l'évaluation de $P$ sur $I_{0}$, noté $P(I_{0})$, est ${\mathit {But}}(I_{\infty })$, où $I_{\infty }$est le point fixe de la suite $(I_{n})_{n\in \mathbb {N} }$. L'existence de ce point fixe est $garanti^,$ par le fait que $\Gamma _{P}$ est un opérateur croissant, via une application élémentaire du théorème de Knaster-Tarski.
  
  ## Implémentations
  
  pyDatalog est un module qui ajoute Datalog à la bibliothèque de Python.
  
  De même Datalog est un module pour OCaml.
  
  