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 suivanteModèle:,. On fixe:

• Un ensemble $𝒳$, dont les éléments sont appelés variables
• Un ensemble $𝒟$, dont les éléments sont appelés constantes
• Un schéma relationnel $𝑆𝑐ℎ$, 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é $𝐵𝑢𝑡$

Une règle Datalog est une expression de la forme: $S(𝐲)\leftarrow R_1({𝐱}_1),\dots ,R_n({𝐱}_n)$ où $S$ est un prédicat intensionnel, $R_1\dots R_n$ sont des prédicats intensionnels ou extensionnels, et ${𝐱}_1\dots {𝐱}_n$ et $𝐲$ sont des n-uplets d'éléments de $𝒳\cup 𝒟$, dont l'arité est compatible avec celle des prédicats. $S(𝐲)$ est appelé la tête de la règle, $R_1({𝐱}_1),\dots ,R_n({𝐱}_n)$ son corps. On impose que chaque variable $y\in 𝒴$ 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 Modèle:,, l'arité de cette requête étant l'arité du prédicat $𝐵𝑢𝑡$.

Pour définir cette sémantique, observons tout d'abord que chaque règle $r\in P$ de la forme $S(𝐲)\leftarrow R_1({𝐱}_1),\dots ,R_n({𝐱}_n)$peut être vue comme une requête sur des instances du schéma relationnel :$$r(I):=\{S(𝐲)\mid \mathrm{\exists }{z}_1\dots z_k{R}_1({𝐱}_{\mathrm{𝟏}})\in I\wedge \dots \wedge R_n({𝐱}_{𝐧})\in I\}$$où $\{z_1\dots z_k\}$est l'ensemble des variables de $𝒳$ apparaissant dans le corps de la règle $r$.

Introduisons l'opérateur de conséquence ${\mathrm{\Gamma }}_P$ qui transforme une instance du schéma relationnel $𝑆𝑐ℎ$ 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$ : ${\mathrm{\Gamma }}_P(I):=I\cup \bigcup _{r\in P}\{r(I)\}$. Pour $n\in \mathbb{N}$, posons $I_{n+1}:={\mathrm{\Gamma }}_P(I_n)$. Le résultat de l'évaluation de $P$ sur $I_0$, noté $P(I_0)$, est $𝐵𝑢𝑡(I_{\mathrm{\infty }})$, où $I_{\mathrm{\infty }}$est le point fixe de la suite $(I_n{)}_{n\in \mathbb{N}}$. L'existence de ce point fixe est garanti Modèle:, par le fait que ${\mathrm{\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.

Articles connexes

• Structured Query Language