Stockage de données XML & RDF

Modèle de stockage

• Pour accélérer les requêtes:
  • index primaire / secondaire
  • taille de tuple fixe

• Pour faciliter les mise à jour:
  • Blocs non pleins
  • Algorithmique sur les arbres
  • Insertions

XML: XPath

Quels types de requêtes ?

Selections

[ @email = 'emmanuel.coquery@univ-lyon1.fr' ]

Jointures classiques

personne[ @id = //rendez-vous/invite/@id ]

Twig joins

rendez-vous[ @debut > '2013-11-12T14:00' ] // invite[ nom = 'Coquery' ]

Index XPath

Selections et jointures (sauf twig)

• Expression XPath + Document
      \(\mapsto\) Ensemble de noeuds + valeurs
• Index: valeur \(\mapsto\) noeuds
• Nécessite de savoir où est stocké chaque noeud

Exemple

index

//personne/nom

requête pouvant l'utiliser

//personne[ nom = 'Coquery' ]/age

\(\equiv\)

//personne/nom[ . = 'Coquery' ]/../age

Représentation des hierarchies

Optimisation du twig join
nœud 1 ancêtre de nœud 2 ?

• Eviter trop d'accès disque
  • Ne pas visiter trop de noeuds

• Complexité raisonnable
  • Idéal O(1)
  • Pas plus de O(h)
    (h = hauteur de l'arbre XML)

Pointeurs parent-enfants

Le noeud de l'enfant contient l'adresse du noeud du parent

Le noeud parent contient la liste des adresses des noeuds enfants

• Test ancêtre:
  • Boucle du descendant vers l'ancêtre

• Complexité du test au pire: O(h)
• Nombre d'accès disque au pire: O(h)

Par préfixe

noeud \(\leftrightarrow\) chemin depuis la racine

1 pas du chemin \(\leftrightarrow\) numéro de l'enfant

\(n_1\) ancêtre de \(n_2\)
\(\equiv\)
chemin(\(n_1\)) prefixe de chemin(\(n_2\))

• Complexité du test au pire: O(h)
• Nombre d'accès disque: O(1)

Exemple: organigramme

Exemple: document XML

<agenda>
  <rendez-vous
     debut="2013-11-12T14:00"
     fin="2013-11-12T15:30">
    <invite id="3">
     <nom>Coquery</nom>
    </invite>
    <salle>Ampere</salle>
  </rendez-vous>
  <personne id="3">
    <nom>Coquery</nom>
  </personne>
</agenda>

Par intervalle

noeud ↔ intervalle unique

\(n_1\) ancêtre de \(n_2\)
\(\equiv\)
\(intervalle(n_1) \supseteq intervalle(n_2)\)

• Complexité du test: O(1)
• Nombre d'accès disque: O(1)

Exemple: organigramme

Exemple: document XML

XML: Insertions

• Pointeur parent-enfant: O(w)
  • insertion du pointeur vers fils à sa place
• Préfixes: O(h)
  • sauf cas dégénérés: O(s)
• Intervalles: O(s)
  • faire de la place

w: nb fils du parent

h: hauteur de l'arbre

s: taille de l'arbre

Préfixes

• Insérer à la fin des fils
  • prendre le préfixe du dernier fils
  • incrémenter le dernier pas
• Autres insertions:
  • Décaler les fils :-(
  • Prévoir de la place

Préfixes: prévoir de la place

Idée: numéroter les fils
avec des nombres impairs uniquement

Utiliser les nombres pairs comme
des noeuds virtuels
 
Maintient les propriétés ancêtre ↔ descendant

Préfixes: exemple

Intervalles

• Dégager de la place
  • décaler les indices de début et de fin
    pour faire de la place
  • O(s)
• Ajouter les noeuds
  • O(ln(s)) si on compte l'index

Prévoir de la place au départ:
 
Grands intervalles
Ajout au [ 1/3, 2/3 ] de la place libre
Plus de place → rééquilibrage des intervalles

Intervalle: exemple dense

Intervalle: exemple grand intervalle de départ

Stockage de triplets RDF

Relations entre noeuds

URIs & Littéraux

Peu/pas de contraintes de schéma

Évaluation de SPARQL:
Pas si différent de l'algèbre relationnelle

Types de magasins (stores ) RDF

• Natifs
  Stockage dédié → on refait le SGBD
• Basés sur des SGBDR
  • Table triplets
  • S'appuyant sur une ontologie
  • RDF wrappers

Stores  natifs

• Le plus souvent 3 indexes:
  • sujet, prédicat, objet
  • les feuilles contienent les triplets complets
• Recodage des URI dans les entiers
  • id incrémental
  • hash
• Différences entre stores:
  • types d'index:
    • B-Tree (e.g. Jena-TDB)
    • Prefix Tree / Trie (e.g. 4store)
  • clustering (c.f. MIF37)

RDF dans un SGBDR: approche générique

Une table triple(suj,pred,obj)

ou 3 tables:
triple(suj,pred,type,obj)
uris(id,uri)
literals(id,lit)
 
IDs entiers plutôt que chaines

Exemple

...
SELECT ?r WHERE {
  ?r agenda:invite ?p.
  ?p agenda:nom ?n.
  FILTER(?n = "Coquery").
}

Requête SPARQL -> Requête SQL

SELECT u.uri
FROM triple invite, triple nom,
     literals l, uris u
WHERE invite.obj = nom.suj
  AND nom.obj = l.id
  AND l.lit = 'Coquery'
  AND invite.suj = u.id

1 attribut / prédicats

Une grande table

Ligne = Subject

Attribut = prédicat

Valeur = sujet
Mapping: ID ↔ URI/Littéral

Attention aux cardinalités
→ plusieurs tables

Utilisation du partitionnement vertical (MIF37)
→ SGBD colonnes

+ Ontologie

• Peut aider au partitionnement vertical
  • Impose des contraintes de cardinalité
  • Impose certains prédicats

Classe RDFS → Table

Prédicat → attribut
si card max = 1

Prédicat → table
sinon

Exemple

uri   litéral

RendezVous (uri, agenda:debut, agenda:fin, agenda:salle)
Personne(uri, agenda:nom)
agenda:invite(uris,urio)

SELECT rdv.uri
FROM RendezVous rdv, "agenda:invite" inv, Personne p
WHERE rdv.uri = inv.uris
  AND inv.urio = p.uri
  AND p.nom = 'Coquery'

SGBD RDF hybrides:

Certains prédicats sont stockés
en relationnel avec ontologie

Les autres:

• en relationnel générique
• ou en natif

Wrapper relationnel → RDF

Lecture seule

Mapping: schéma relationnel → RDFS / Ontologies

• pour chaque table
  • clé primaire → URI sujet
  • colonne → URI prédicat
    • conversion de type
    • gestion de clé étrangère
       
• associations n-n
  • spécifications tables intermédiaires
• requêtes plus complexes
  • exposer une vue comme une table

Références