Informatique

L’objectif de ce cours est de présenter les fondements des bases de données et des bases de connaissance. Il introduira les concepts communs à ces types de données (relationnel, graphe, document), les langages de requêtes fondés par la logique, l’algèbre, et les expressions régulières. Il présentera les algorithmes fondamentaux qui sous-tendent l’interrogation des bases de données et de connaissances ainsi que la complexité algorithmique des problèmes liés à ces requêtes. Les étudiants étudieront également les éléments de syntaxe et la sémantique des requêtes logique, la relation proche entre logique et langage de programmation.

Le cours abordera les notions suivantes:

• les structures relationnelles, les graphes, les arbres
• les termes, les formules, les programmes, les requêtes
• la logique du premier ordre et l’algèbre relationelle
• les requêtes conjonctives acycliques, l’algorithme de Yannakakis
• les circuits logiques comme agrégats d’ensembles de réponses de requêtes
• les requêtes de chemins, les requêtes récursives
• datalog, l’évaluation de requêtes datalog

Grâce à cette connaissance profonde des mécanismes d’interrogation de bases de données, l’étudiant aura la capacité de

• mieux comprendre et mieux écrire des requêtes
• réécrire et optimiser des requêtes et des bases de données
• choisir de bons plans d’exécution