Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

Les deux révisions précédentes Révision précédente
ter [2015/01/28 08:40]
ecoquery [Extraction de règles d'inférence dans les bases de données RDF]
ter [2015/11/06 08:21] (Version actuelle)
ecoquery
Ligne 1: Ligne 1:
-====== Sujets de TER 2014-2015 ======+====== Sujets de TER 2015-2016 ======
  
-===== Application ​de la diversification ​de solutions SAT dans le cadre de la fouille de motifs ​=====+===== Bibilothèque d'​algorithmes d'​équivalence et de réécriture ​de requêtes ​=====
  
-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'​attributsdans une base de donnée relationnelle+Dans le cadre de l'​intégration différentes sources de donnéesune approche classique consiste à exprimer des requête sur un schéma global et à réécrire ces requêtes pour récupérer ​(une partiedes information sur chaque source
  
-Il arrive fréquemment que le nombre ​de motifs correspondant ​à une requête soit très élevé ​ce qui pose deux problèmes:  +Bien qu'il existe plusieurs algorithmes,​ notamment pour Datalog (e.g. [1], [2], [3]), 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, ​qui constituera une brique de base pour des développements à venir dans l'équipe BD du LIRIS autour du raisonnement sur les requêtes. De ce point de vue, une attention particulière devra être apportée sur la qualité du code produit par opposition à la quantité d'​algorithmes implémentés.
-  - l'​analyste risque d'​être perdu dans l'avalanche de résultats;  +
-  - 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 ​[[research:​satminer|SATMiner]], l'​approche proposée par A. Nalel [2] pour renvoyer des solutions diversifiéespuis d'​évaluer l'​intérêt de cette approche pour répondre à la problématique d'​avalanche de solutions dans SATQL.+[1] A.Y. Halevy: "​Answering queries using views: A survey"​The VLDB Journal, Vol10, Iss. 4, 2001
  
-[1http://​liris.cnrs.fr/​Documents/​Liris-5712.pdf+[2JWang, MMaher, RTopor: "​Rewriting Unions of General Conjunctive Queries Using Views",​ Advances in Database Technology (EDBT), 2002
  
-[2Alexander Nadel: "Generating Diverse Solutions in SAT", ​Theory and Applications of Satisfiability Testing - SAT 2011Lecture Notes in Computer Science Volume 6695, 2011pp 287-301 ​+[3D. Calvanese, G. De Giacomo, M. Lenzerini, and M. Y. Vardi: "Query processing under glav mappings for relational and graph databases", ​Proc. VLDB Endow.6(2):​61–72Dec. 2012.
  
-**mots-clés**:​ SAT, fouille de motifs 
  
-=====  Synthèse sur les mécanismes de contrôle d’accès dans les bases de données ​RDF =====+**mots-clés**:​ Intégration ​de données, Datalog
  
-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. +=====  Mises à jour et contrôle d'accès sur des bases de données ​RDF =====
  
-Le Web sémantique ​est basé sur le modèle de données RDF (Resource Description Framework) ​[9pour 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). +Le web sémantique [5est défini comme une extension du Web courant dans lequel ​l'​information ​un sens bien défini permettant à la machine ​de capturer ​la sémantique des donnéesIl fournit ​un cadre commun qui permet aux données ​d'​être ​partagées ​et réutilisées entre les applications Web
- +
-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 ... +
- +
-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. +
- +
-[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 tripletsL'​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 Web sémantique est basé sur le modèle de données RDF (Resource Description Framework) [6] 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).
  
-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'​équipe BD du LIRIS à proposé dans [7] un modèle ​de contrôle d'​accès évolué pour les bases de données RDF. Une première implémentation ​de ce modèle a été réalisée sur TDB, la base de donnée ​RDF native de Jena. Afin de limiter le surcoût du contrôle d'​accès lors de l'​exécution ​des requêtesun ensemble d'​informations sont précalculées ​et stockées dans la baseCe mode de fonctionnement limite actuellement cette implémentation à un fonctionnement en lecture seule (les mise à jour nécessite un recalcul complet de ces informations). L'​objectif de ce TER est dans un premier temps d'​implémenter ​une mise à jour incrémentale de ces informations,​ puis dans un deuxième temps de mener une réflexion sur l'​extension des politiques de contrôle d'​accès aux opérations de mise à jour.
  
-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.+[5] Berners-Lee,​ Tim, James Hendler, and Ora Lassila. "The semantic ​web." Scientific american 284.5 (2001): 28-37.
  
-**mots-clés**:​ fouille de règlesSQL+[6] ManolaFrank, Eric Miller, and Brian McBride. "RDF primer."​ W3C recommendation 10.1-107 (2004).
  
 +[7] Tarek Sayah, Emmanuel Coquery, Romuald Thion, Mohand-Saïd Hacid:
 +"​Inference Leakage Detection for Authorization Policies over RDF Data." DBSec 2015: 346-361