Ceci est une ancienne révision du document !


Sujets de TER 2014-2015

Application de la diversification de solutions SAT dans le cadre de la fouille de motifs

Le langage SATQL (cf [1] pour une version formelle), implémenté au sein de la plateforme SATMiner, est un langage de requête permettant de chercher des motifs (sous forme d'ensemble d'attributs) dans une base de donnée relationnelle.

Il arrive fréquemment que le nombre de motifs correspondant à une requête soit très élevé ce qui pose deux problèmes:

  1. l'analyste risque d'être perdu dans l'avalanche de résultats;
  2. le temps de calcul qui peut être très important.

L'objectif de ce TER est d'implémenter au sein des différents solveurs utilisés dans la plateforme SATMiner, l'approche proposée par A. Nalel [2] pour renvoyer des solutions diversifiées, puis d'évaluer l'intérêt de cette approche pour répondre à la problématique d'avalanche de solutions dans SATQL.

[1] http://liris.cnrs.fr/Documents/Liris-5712.pdf

[2] Alexander Nadel: “Generating Diverse Solutions in SAT”, Theory and Applications of Satisfiability Testing - SAT 2011, Lecture Notes in Computer Science Volume 6695, 2011, pp 287-301

Extraction de règles d'inférence dans les bases de données RDF

La sémantique RDF [3], en particulier la partie concernant RDFS propose un système de règles d'inférences permettant de déduire des nouveaux triplets. L'opération de saturation d'un graphe RDF consiste à appliquer ces règles d'inférence afin de matérialiser tous les triplets pouvant être déduits. On obtient ainsi un graphe saturé.

On peut se poser une question duale: étant donné un graphe saturé, quelles sont les règles d'inférences qui sont vérifiées dans ce graphe. On peut pour se faire se ramener à un problème classique de découverte de règles d'associations [4]. L'objectif de ce TER est d'implémenter l'extraction des règles d'inférence RDF et de comprendre les éventuelles limites rencontrées par les implémentation “état de l'art” dans ce contexte.

[3] http://www.w3.org/TR/2014/REC-rdf11-mt-20140225/ [4] http://fr.wikipedia.org/wiki/R%C3%A8gle_d%27association

Bibilothèque d'algorithmes de réécriture dans le cadre de l'intégration de données

Dans le cadre de l'intégration différentes sources de données, une approche classique consiste à exprimer des requête sur un schéma global et à réécrire ces requêtes pour récupérer (une partie) des information sur chaque source.

Bien qu'il existe plusieurs algorithmes, notamment pour Datalog (e.g. [5], [6]), permettant de réaliser cette réécriture, il n'existe pas à notre connaissance de bibliothèque implémentant tous ces algorithmes. L'objectif de ce TER est donc de réaliser cette bibliothèque, en la rendant dans la mesure du possible compatible avec le moteur Datalog IRIS [7].

[5] A.Y. Halevy: “Answering queries using views: A survey”, The VLDB Journal, Vol. 10, Iss. 4, 2001

[6] J. Wang, M. Maher, R. Topor: “Rewriting Unions of General Conjunctive Queries Using Views”, Advances in Database Technology (EDBT), 2002

[7] http://iris-reasoner.org/

Refonte d'un démonstrateur pour un langage de fouille de règles

Le langage RQL est un langage de requêtes permettant de chercher des règles entre attributs de la forme suivante: étant donnée une certaine condition sur des attributs, A,B → C signifie si la condition est vraie sur A et B, alors elle est vraie C. Un moteur pour ce langage a été développé avec une interface web accessible ici: http://rql.insa-lyon.fr .

L'objectif de ce TER est de refondre le code du moteur de requête et de l'interface web de façon à faciliter les futures évolutions du démonstrateur.