|
Prochaine révision
|
Révision précédente
Dernière révision
Les deux révisions suivantes
|
ter [2012/06/18 16:54]
ecoquery créée |
ter [2015/01/28 08:40]
ecoquery [Extraction de règles d'inférence dans les bases de données RDF] |
| ====== Sujets de TER ====== | ====== Sujets de TER 2014-2015 ====== |
| |
| ===== Éditeur de protocoles métier pour services Web ===== | ===== Application de la diversification de solutions SAT dans le cadre de la fouille de motifs ===== |
| |
| Un service Web est un application offrant des fonctionnalités accessibles à distance par d'autres programmes. | Le langage SATQL (cf [1] pour une version formelle), implémenté au sein de la plateforme [[research:satminer|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. |
| Un protocole métier est une machine à état dont les transitions correspondent à un message envoyé ou reçu par un service. Il permet de représenter les suites possibles d'échanges de messages avec le service. | |
| Ces protocoles peuvent être annotés pour enrichir la description qu'ils apportent avec des contraintes temporelles, des politiques de contrôle d'accès, etc ... | |
| |
| L'objectif de ce TER est de créer un éditeur graphique de protocole métier sous la forme d'une bibliothèque JavaScript permettant son intégration dans un navigateur Web. Cet éditeur devra être paramétrable pour permettre tout type d'annotation. Il devra être capable interagir avec le serveur de la page afin de pouvoir charger/sauver le protocole annoté. Il devra également être capable de faire remonter graphiquement des erreurs qui auraient été trouvées par un analyseur fonctionnant côté serveur. | Il arrive fréquemment que le nombre de motifs correspondant à une requête soit très élevé ce qui pose deux problèmes: |
| | - l'analyste risque d'être perdu dans l'avalanche de résultats; |
| | - le temps de calcul qui peut être très important. |
| |
| ===== Ajout de spécifications de méta-données dans un prototype de vérification de compatibilité de services Web ===== | L'objectif de ce TER est d'implémenter au sein des différents solveurs utilisés dans la plateforme [[research:satminer|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. |
| |
| Un service Web est un application offrant des fonctionnalités accessibles à distance par d'autres programmes. | [1] http://liris.cnrs.fr/Documents/Liris-5712.pdf |
| Un protocole métier est une machine à état dont les transitions correspondent à un message envoyé ou reçu par un service. Il permet de représenter les suites possibles d'échanges de messages avec le service. | |
| Ces protocoles peuvent être annotés pour enrichir la description qu'ils apportent avec des contraintes temporelles, des politiques de contrôle d'accès, etc ... | |
| |
| L'objectif de ce TER est d'enrichir l'implémentation d'un vérificateur de compatibilité entre protocoles annotés: | [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 |
| * en prenant en compte des méta-données supplémentaires comme les schémas XML, le sens (sémantique) des messages ou le sens des données; | |
| * en implémentant une version du vérificateur fonctionnant sur plus de deux protocoles | |
| | |
| ===== Prototype de moteur de fouille de données basé sur SAT Modulo Theory (2 sujets) ===== | |
| |
| La fouille de données consiste à extraire des informations pertinentes à partir d'un gros volume de données. Un exemple consiste à extraire de données sur les prescriptions des patients les combinaisons de médicaments ayant eu des effets indésirables. Un autre exemple consiste à extraire les combinaisons d'articles achetés souvent ensemble, afin de découvrir les habitudes des clients. De telles combinaisons intéressantes sont appelées motifs. | **mots-clés**: SAT, fouille de motifs |
| |
| Depuis quelques années, l'utilisation de la programmation par contraintes afin de découvrir des motifs intéressants à suscité un intérêt dans la communauté scientifique (voir par exemple http://dtai.cs.kuleuven.be/CP4IM/). | ===== Synthèse sur les mécanismes de contrôle d’accès dans les bases de données RDF ===== |
| |
| ==== Sujet 1: implémentation d'un prototype basé sur OpenSMT ==== | Le web sémantique [8] est défini comme une extension du Web courant dans lequel l'information a un sens bien défini permettant à la machine de capturer la sémantique des données. Il fournit un cadre commun qui permet aux données d'être partagées et réutilisées entre les applications Web. |
| |
| L'objectif de ce TER est de mesurer l'apport que peut apporter l'utilisation de solveurs SAT Modulo Theory (SMT) par rapport aux solveurs de contraintes utilisés aujourd'hui dans ce cadre. On débutera par une mise à niveau sur la fouille de données et sur les solveurs SAT et SMT, puis on adaptera à la fouille le solveur [[http://verify.inf.usi.ch/opensmt|OpenSMT]]. | Le Web sémantique est basé sur le modèle de données RDF (Resource Description Framework) [9] pour représenter les données et les relations entre elles. RDF permet de décomposer l'information en portions appelées "triplets" qui sont stockées dans des entrepôts de données (triple store). |
| |
| ==== Sujet 2: adaptation du cadre CP4IM au problème de fouille de séquences ==== | Il existe une vaste gamme de bases de données de données RDF tels que : OpenLink Virtuoso, Oracle Database Semantic Technologies, Allegro Graph, Sesame ... |
| |
| L'objectif de ce TER est de modifier le moteur de fouille d'ensemble d'objets fréquents((//frequent itemset//)) [[http://dtai.cs.kuleuven.be/CP4IM/|CP4IM]] pour l'adapter à la fouille de séquences. On mettra ensuite en place un benchmark pour comparer les résultats optenus par ce moteur avec ceux obtenu par une implémentation état de l'art et, si possible, par rapport aux résultats obtenus dans le cadre du sujet 1. | Les données RDF stockées dans ces bases de données peuvent être sensibles, et requièrent donc d'être protégées contre les accès non autorisés. Les bases de données RDF possèdent des mécanismes de contrôle d'accès qui permettent de définir la façon par laquelle les triplets RDF sont divulgués à l’utilisateur. |
| |
| | Ce TER vise à faire un tour d’horizon et un comparatif des différents mécanismes de contrôle d’accès disponibles dans les SGBD RDF du marché. Ce comparatif se fera aussi bien au niveau théorique (e.g. expressivité) que de la mise en œuvre en pratique, ce qui sous entend une expérimentation sur les différents systèmes. |
| |
| Ces TER se dérouleront dans le cadre du projet [[http://liris.cnrs.fr/dag/|DAG]]. | [8] Berners-Lee, Tim, James Hendler, and Ora Lassila. "The semantic web." Scientific american 284.5 (2001): 28-37. |
| | |
| | [9] Manola, Frank, Eric Miller, and Brian McBride. "RDF primer." W3C recommendation 10.1-107 (2004). |
| | |
| | |
| | ===== 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 |
| | |
| | **mots-clés**: RDF, règles d'association, volumétrie |
| | |
| | ===== 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/ |
| | |
| | **mots-clés**: Intégration de données, Datalog |
| | |
| | ===== 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. |
| | |
| | **mots-clés**: fouille de règles, SQL |
| |
Sauf mention contraire, le contenu de ce wiki est placé sous les termes de la licence suivante : CC Attribution-Noncommercial-Share Alike 3.0 Unported