Les couches du Web sémantique
Nous avons plusieurs couches dans la pile du web sémantique. URI/IRI : URI (Universal Resource Identifier) permet d’identifier n’important quelle ressource,même abstraite ou anonyme. URI a deux déclinaisons:
URN(universal Resource Name) URI d’identification d’une ressource par son nom unique dans un espace de noms.
URL(Uniform Resource Locator) URI spécifiant l’adresse physique de localisation d’une ressource sur Internet et la méthode permettant d’y accéder.
IRI(International Resource Identifier) est une version internationalisée de URI. XML(Extensible Markup Language) fournit une syntaxe pour décrire la structure du document, créer et manipuler des instances des documents. Il utilise l’espace de nommage (name-space) afin d’identifier les noms des balises (Tags) utilisés dans le document XML. Le schéma XML permet de définir les vocabulaires pour des documents XML valides. Cependant, XML n’impose aucune contrainte sémantique à la signification de ces documents. L’interopérabilité syntaxique n’est pas suffisante pour qu’un logiciel puisse comprendre le contenu des données et les manipuler d’une manière significative.
RDF et RDF Schema. Les couches RDF et RDF – Schema sont considérées comme les premières fondations de l’interopérabilité sémantique. Elles permettent de décrire les taxonomies des concepts et des propriétés (avec leur signature). RDF fournit un moyen d’insérer la sémantique dans un document. L’information est conservée principalement sous forme de déclarations RDF. Le schéma RDF (RDFS) décrit les hiérarchies des concepts et leurs relations, les propriétés et les restrictions domaine/co – domaine pour les propriétés. RDF, acronyme de Resource Description Framework, est un modèle de données. Par abus de langage, il est commun de dire que c’est un «langage» d’assertion et d’annotation. R DF est un outil fondamental du web sémantique : il permet de définir des métadonnées afin de préciser les caractéristiques d’une information. Il établit des relations entre ressources. Il est donc particulièrement adapté aux annotations associées aux ressources du Web. RDFS (RDF Schéma) définit un vocabulaire utilisé dans les modèles de données RDF. Un document RDFS précise également les propriétés des différents objets modélisés, les domaines de valeurs possibles et décrit les relations entre ces différents objets. Les mécanismes de raisonnement mis en œuvre dans RDFS trouvent leurs fondements dans les premiers langages à base de logique pour données orientées objet, tels que F- logique et la logique de description . Une formalisation du modèle théorique de RDFS sémantique a été fournie dans.Les fondations et les aspects avancés de bases de données RDFS ont été étudiés dans. Ce dernier travail couvre des problèmes tels que le raisonnement sur RDFS et présente un ensemble de règles d’inférence qui mettent en œuvre le cœur de la sémantique du modèle théorique RDF. En outre, il étudie les problèmes tels que la complexité de l’implication (si un graphe RDFS implique logiquement un autre graphe), les formes normales de RDFS, et les requêtes réalisées sur les bases de données RDFS.
SPARQL permet d’interroger des données RDF. OWL Elle décrit des sources d’information hétérogènes, distribuées et semi-structurées en définissant les consensus du domaine commun et partagées par plusieurs personnes et communautés(la signification de la connaissance). OWL, acronyme de Web Ontology Language, permet d’étendre le vocabulaire et les propriétés de RDF. Il offre une grande souplesse dans la définition des relations. Par exemple, OWL permet de préciser qu’une propriété est l’inverse de l’autre, ce qui permet d’inférer des relations non explicites. « A est le père de B» nous dit également que B est fils de A. Ceci paraît trivial, mais en informatique, il faut établir ce genre de raisonnement de base afin d’avoir des informations traitées «intelligemment». OWL permet de construire des relations de disjonctions ou de faire des unions. Les ontologies aident la machine et l’humain à communiquer avec concision en utilisant l’échange sémantique plutôt que syntaxique.
la couche régle a pour objectif de normaliser la représentation des règles RDF. Elle comporte deux langages de règles: SWRL (Semantic Web Rule Langage) et RIF (Rule Interchange Format). SWRL est une extension d’OWL. RIF ne repose pas directement sur RDF, mais sur XML et il permet de faciliter l’utilisation et l’échange de règles entre les formats déjà existants.
Logique et Preuve . Il faut faire des inférences mais il faut aussi pouvoir les expliquer. La logique est un langage permettant d’expliquer des «règles» de raisonnements. Ces règles permettent de déduire de nouveaux faits à partir de faits existants. Une preuve est une suite de règles permettant de déduire un nouveau fait.
Ontology Web Language: OWL
Owl est un langage de description d’ontologies (ensemble structuré de savoir dans un domaine de connaissance particulier) conçu au départ pour la publication et le partage d’ontologies sur le web sémantique. Il définit un vocabulaire riche pour la description d’ontologies complexes. Issu des logiques de descriptions, OWL est basé sur une sémantique formelle définie par une syntaxe rigoureuse. Il dispose de fonctions facilitant la réutilisation d’autres ontologies et permet de définir des rapports complexes entre les ressources. Il intègre par exemple des outils de comparaison des propriétés et de classes comme l’identité, l’équivalence, le contraire, la cardinalité, la symétrie, la transitivité, la disjonction … OWL (Web Ontology Language) a été recommandé par le W3C en 2004, et est à sa version 2 en 2009. Il définit plusieurs profils offrant des compromis différents en termes d’expressivité et de complexité .
Plus un outil est complet, plus il est, en général, complexe. C’est cet écueil qu’a voulu éviter le groupe de travail WebOnt du W3C en dotant OWL de trois sous-langages offrant des capacités d’expression croissantes et, naturellement, destinés à des communautés différentes d’utilisateurs: OWL Lite est le sous langage de OWL le plus simple. Il est destiné aux utilisateurs qui ont besoin d’une hiérarchie de concepts simple. OWL Lite est adapté, par exemple, aux migrations rapides depuis d’anciens thésaurus.
OWL DL est plus complexe que OWL Lite, permettant une expressivité bien plus importante. OWL DL est fondé sur la logique descriptive (d’où son nom, OWL Description Logics), un domaine de recherche étudiant la logique, et conférant donc à OWL DL son adaptation au raisonnement automatisé. Malgré sa complexité relative face à OWL Lite, OWL-DL garantit la complétude des raisonnements (toutes les inférences sont calculables) et leur décidabilité (leur calcul se fait en une durée finie).
OWL Full est la version la plus complexe d’OWL, mais également celle qui permet le plus haut niveau d’expressivité. OWL Full est destiné aux situations où il est plus important d’avoir un haut niveau de capacité de description, quitte à ne pas pouvoir garantir la complétude et la décidabilité des calculs liés à l’ontologie. OWL Full offre cependant des mécanismes intéressants, comme par exemple la possibilité d’étende le vocabulaire par défaut de OWL.
SPARQL: SPARQL Protocol and RDF Query Langage
Sparql est le standard préconisé par le W3C pour interroger des modèles de triplets RDF. Sparql est à la fois un langage et protocole de requête. Le protocole va permettre à un client web de consulter, en exécutant une requête Sparql, un service ou point d’accès Sparql(Endpoint) qui traitera la requête pour retourner la réponse sous différents formats (RDF/XML, N3, JSON, etc.). Le langage permet d’interroger, de modifier, d’insérer et de supprimer des descriptions RDF en utilisant des clauses (similaires dans certains cas à celles du langage SQL).
BGPs : basicgraphpatterns : Une requête SPARQL est composée généralement de trois parties: la partie des préfixes qui permet de créer des alias pour ne pas répéter les Namespaces ou URI dans la requête, la partie centrale qui peut être une clause SELECT, CONSTRUCT, ASK ou DESCRIBE et la troisième partie constitue un BGPs(basic graph patterns) ou motif de triplets. Ce dernière est précédée par un WHERE avec plusieurs motifs de triplets séparés par des «.» . Un motif de triplet est un triplet dans les valeurs peuvent être des atomes ou des variables. Un atome peut être un URI ou un littéral ou bien une ressource anonyme . Le BGP peut avoir plusieurs formes et cette forme dépend de la manière les variables sont jointes. On parle de jointure quand une variable est partagée par plusieurs motifs de triplets. Cette forme influe beaucoup sur le traitement de la requête. Parmi les formes de motifs de requêtes nous pouvons citer:
Requête en Etoile (Star query) : se compose uniquement de jointures sujet-sujet où chaque variable de jointure est le sujet de tous les motifs de triplets impliqués dans la requête. Requête Chainée (chain query) : consiste en des jointures sujet-objet où les motifs de triplets sont connectés consécutivement comme une chaîne.
Requête en Arbre(tree query) : les jointures se font entre sujet-sujet et sujet-objet. Requête en cycle contient des jointures du type sujet-sujet, sujet-objet et objet-objet. Requête complexe(complex query) : est une combinaison de types de requêtes cités en haut.
Les méthodes de hachage
Les méthodes de hachage sont très utilisées dans les tripleStores actuels. Ces méthodes partitionnent les données en utilisant le sujet ou l’objet comme clé. A la fin les triplets ayant les mêmes sujets sont dans la même partition. Cela permet d’éviter les communications entre les machines pour l’évaluation de requêtes. Le partitionnement par hachage est une méthode, largement utilisée dans de nombreux moteurs RDF distribués . La plupart des systèmes implémente le hachage en utilisant le sujet comme clé du triplet. Il existe également des améliorations, qui consiste à hacher en tenant compte de la sémantique et cette approche est appelée le hachage sémantique .
Le hachage sémantique consiste à partitionner les données en trois étapes principales: Construction d’un ensemble de groupes de triplets qui sont des éléments de base pour le hachage sémantique. Regroupement des blocs de construction de base pour générer les partitions de hachage de base . Générer des partitions de hachage sémantique k-hop, qui étendent chaque partition de hachage de base via une réplication de triplets contrôlée . Pour équilibrer davantage la quantité de triplets répliquée et l’efficacité du traitement des requêtes, un filtre est posé sur le triplet ayant comme prédicat rdf: type lors de la réplication de k-hop.
Table des matières
1 Introduction
2 Le Web Sémantique
2.1 Introduction
2.2 Les couches du Web sémantique
2.3 Resource Description Framework: RDF
2.4 Ontology Web Language : OWL
2.5 SPARQL: SPARQL Protocol and RDF Query Langage
2.5.1 BGPs: basicgraphpatterns
2.5.2 Opérateur OPTIONAL
3 Approche de partitionnement classique de graphes
3.1 Définitions
3.1.1 Définitions sur les graphes
3.1.2 Définitions du partitionnement de graphes
3.2 Algorithmes utilisés pour le partitionnement de graphes
3.2.1 L’approche spectrale
3.2.2 L’approche combinatoire
3.2.2.1 Les algorithmes itératifs d’optimisation
3.2.2.2 Les algorithmes génériques d’optimisation
3.2.3 L’approche multi-niveaux
3.2.3.1 L’étape de contraction
3.2.3.2 L’étape de partitionnement initial
3.2.3.3 L’étape d’expansion
3.2.4 Conclusion
4 partitionnement de graphes RDF statiques
4.1 Introduction
4.2 Les méthodes de hachage
4.3 PARTOUT
4.3.1 Partitionnement et allocation de données
4.3.2 Traitement de requêtes
4.4 Sedge : Self Evolving Distributed Graph Management Environment
4.4.1 Partitionnement de graphe
4.4.2 Gestion de partition à deux niveaux
4.4.3 Gestion des métadonnées
4.4.4 Optimiseur de performance
4.5 DREAM: Distributed RDF Engine with Adaptive Query Planner and Minimal Communication
4.5.1 Architecture de DREAM
4.6 H2RDF+
4.7 HadoopRDF
4.7.1 Approche de HadoopRDF
4.7.1.1 Architecture
4.7.1.2 Partition de données et décomposition de requête SPARQL
4.8 CliqueSquare
4.8.1 Partitionnement de données
4.8.2 Processus de partitionnement MapReduce
4.9 NHOPDB
4.10 WARP: Workload-aware replication and partitioning for RDF
4.11 D-SPARQ
4.12 S2RDF (SPARQL on SPARK for RDF)
5 Bilan
6 Conclusion et perspectives
