RDF-3X
Un moteur de bases de données conçu pour RDF
03.19.204
Plan
- Présentation de RDF
- Représentation des données
- Résolution des requêtes
1.
Resource Description Framework
Données bien formattées
Données agrégées, d'origines différentes
Données sans tables, sous forme de graphe
(Sujet, Prédicat, Objet)
SPARQL
SPARQL Protocol and RDF Query LanguageLangage de requêtes standardisé par le W3C
Proche du SQL mais adapté au RDF
Exemple de requête
SELECT DISTINCT ?titre
WHERE {
?film <hasTitle> ?titre.
?film <hasCasting> ?acteur.
?acteur <hasName> "Johny Depp"
}
Recherche tous les titres de films où joue Johny Depp
2.
Représentation des données
Première idée
Seconde idée
Seconde idée
Identifiants
Toutes les valeurs sont remplacées par des identifiants
Indiçage
La table est représentée dans un arbre de recherche
Elle est triée dans l'ordre lexicographique
Les réponses aux requêtes du type {Sujet ?p ?o} sont des intervalles
Problème
SELECT ?x WHERE { ?x Predicat Objet }
L'ordre lexicographique n'optimise pas cette requête
Solution
On enregistre les données 6 fois : une part permutation de{
Sujet, Prédicat, Objet}
Ça prend de la place !
Compression des données
On enregistre la différence avec le triplet précédent
Un octet d'en-tête indique la taille de la représentation de cette différence
Tables supplémentaires
Pour optimiser d'autres requêtes simples
- SP, PO, SO, PS, OP, OS pour
SELECT ?x ?y WHERE { ?x ?a ?z } - S, P, O pour
SELECT ?x WHERE { ?x ?a ?b }
3.
Résolution des requêtes
Requêtes simples...
En utilisant précédemment
... et compliquées
Problème d'optimisation des requêtes avec jointures
Réalisation d'un graphe
Noeuds : triplets
Arrêtes : si une variable apparaît dans 2 requêtes
Comment ordonner ces jointures ?
Solution 1 : Seaux
| Seaux | V1 | V2 | # | ||
|---|---|---|---|---|---|
| A | 1 | 2 | 6 | ||
| E | D | 1 | 3 | 7 | |
| 4 | 2 | 4 | |||
| C | 4 | 6 | 2 | ||
| 4 | 7 | 3 | |||
| SEAUX | # | 2-disctint | 1-disctint | |
|---|---|---|---|---|
| Etape 1 | A | 6 | 1 | 1 |
| B | 2 | 1 | 1 | |
| Etape 2 | C | 5 | 2 | 1 |
| D | 11 | 2 | 2 | |
| Etape 3 | E | 16 | 4 | 2 |
Calculs supplémentaires
Pour chaque seau b, calcul de :
s=s ; s=p ; s=o
p=s ; p=p ; p=o
o=s ; o=p ; o=o
Exemple :
(s=p) = # { {t triplet de b} ×t.sujet = t'.prédicat {t' triplet} }
Comment les utiliser ?
| X = ?a P O | Y = S P ?a | Z = S P ?a |
| (Σ s=o) = 5000 |
(Σ o=s) = 3000 (Σ o=o) = 2000 |
(Σ o=s) = 8000 (Σ o=o) = 7000 |
| sup # X.Y = 3000 | sup # Y.Z = 2000 | sup # X.Z = 5000 |
Solution 2 : Motifs fréquents
Analyse des motifs fréquents dans le graphe
Ce fait selon les prédicats.
Non évident : cas des boucles par exemple.
Classement par le nombre de noeuds utilisés.
Un motif est conservé seulement si ses sous-motifs sont des motifs fréquents.
Calcul en quelques minutes des 1000 motifs les plus fréquents.