Datalog
# 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.

