Datalog

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant l’informatique
Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Datalog
Date de première version 1977
Paradigme Langage de requête
Auteur Hervé Gallaire et Jack Minker

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[modifier | modifier le code]

Datalog a la syntaxe suivante. [1],[2] 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é [3]

Une règle Datalog est une expression de la forme: est un prédicat intensionnel, sont des prédicats intensionnels ou extensionnels, et et sont des n-uplets d'éléments de , dont l'arité est compatible avec celle des prédicats. est appelé la tête de la règle, son corps. On impose que chaque variable 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[modifier | modifier le code]

Fixons une instance 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 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 .

Pour définir cette sémantique, observons tout d'abord que chaque règle de la forme peut être vue comme une requête sur des instances du schéma relationnel :

est l'ensemble des variables de apparaissant dans le corps de la règle .

Introduisons l'opérateur de conséquence 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  : . Pour , posons . Le résultat de l'évaluation de sur , noté , est , où est le point fixe de la suite . L'existence de ce point fixe est garanti [1],[2] par le fait que est un opérateur croissant, via une application élémentaire du théorème de Knaster-Tarski.

Implémentations[modifier | modifier le code]

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

Notes[modifier | modifier le code]

  1. a, b et c (en) Serge Abiteboul, Richard Hull et Victor Vianu, Foundations of Databases, Addison Wesley, (ISBN 978-0-201-53771-0, lire en ligne)
  2. a, b et c Serge Abiteboul, Richard Hull et Victor Vianu, Fondements des bases de données, Vuibert, (ISBN 978-2-711-78678-7)
  3. (en) Stefano Ceri, Georg Gottlob et Letizia Tanca, « What You Always Wanted to Know About Datalog (And Never Dared to Ask) », IEEE Transactions on Knowledge and Data Engineering, vol. 1, no 1,‎ (ISSN 1041-4347, lire en ligne)

Articles connexes[modifier | modifier le code]