Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Datalog
Résumé
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.
Datalog a la syntaxe suivante. 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: où 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.
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 , 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 :où 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 par le fait que est un opérateur croissant, via une application élémentaire du théorème de Knaster-Tarski.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.