Datalog

Datalog a la syntaxe suivante[1] - [2]. On fixe:

• Un ensemble ${\displaystyle {\mathcal {X}}}$, dont les éléments sont appelés variables
• Un ensemble ${\displaystyle {\mathcal {D}}}$, dont les éléments sont appelés constantes
• Un schéma relationnel ${\displaystyle {\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é [3] ${\displaystyle {\mathit {But}}}$

Une règle Datalog est une expression de la forme: ${\displaystyle S(\mathbf {y} )\leftarrow R_{1}(\mathbf {x} _{1}),\dots ,R_{n}(\mathbf {x} _{n})}$ où ${\displaystyle S}$ est un prédicat intensionnel, ${\displaystyle R_{1}\dots R_{n}}$ sont des prédicats intensionnels ou extensionnels, et ${\displaystyle \mathbf {x} _{1}\dots \mathbf {x} _{n}}$ et ${\displaystyle \mathbf {y} }$ sont des n-uplets d'éléments de ${\displaystyle {\mathcal {X}}\cup {\mathcal {D}}}$, dont l'arité est compatible avec celle des prédicats. ${\displaystyle S(\mathbf {y} )}$ est appelé la tête de la règle, ${\displaystyle R_{1}(\mathbf {x} _{1}),\dots ,R_{n}(\mathbf {x} _{n})}$ son corps. On impose que chaque variable ${\displaystyle 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.

Fixons une instance ${\displaystyle 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 ${\displaystyle P}$ définit une requête sur cette base de données [1] - [2], l'arité de cette requête étant l'arité du prédicat ${\displaystyle {\mathit {But}}}$.

Pour définir cette sémantique, observons tout d'abord que chaque règle ${\displaystyle r\in P}$ de la forme ${\displaystyle 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 :

$${\displaystyle 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ù ${\displaystyle \{z_{1}\dots z_{k}\}}$est l'ensemble des variables de ${\displaystyle {\mathcal {X}}}$ apparaissant dans le corps de la règle ${\displaystyle r}$.

Introduisons l'opérateur de conséquence ${\displaystyle \Gamma _{P}}$ qui transforme une instance du schéma relationnel ${\displaystyle {\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 ${\displaystyle P}$ : ${\displaystyle \Gamma _{P}(I):=I\cup \bigcup _{r\in P}\{r(I)\}}$. Pour ${\displaystyle n\in \mathbb {N} }$, posons ${\displaystyle I_{n+1}:=\Gamma _{P}(I_{n})}$. Le résultat de l'évaluation de ${\displaystyle P}$ sur ${\displaystyle I_{0}}$, noté ${\displaystyle P(I_{0})}$, est ${\displaystyle {\mathit {But}}(I_{\infty })}$, où ${\displaystyle I_{\infty }}$est le point fixe de la suite ${\displaystyle (I_{n})_{n\in \mathbb {N} }}$. L'existence de ce point fixe est garanti [1] - [2] par le fait que ${\displaystyle \Gamma _{P}}$ est un opérateur croissant, via une application élémentaire du théorème de Knaster-Tarski.

pyDatalog est un module qui ajoute Datalog à la bibliothèque de Python.

De même Datalog est un module pour OCaml.

• Structured Query Language