Stockage de données XML & RDF

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

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

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

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