Stockage de données XML & RDF

Emmanuel Coquery

emmanuel.coquery@univ-lyon1.fr

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

Nom Chemin
Martin 1
Julius 11
Jones 111
Brown 112
Lambert 12
Bellot 121
LambertJr 1211
Soule 13
Dupuis 131
Fildou 132

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

Nom d f
Martin 1 20
Julius 2 7
Jones 3 4
Brown 5 6
Lambert 8 13
Bellot 9 12
LambertJr 10 11
Soule 14 19
Dupuis 15 16
Fildou 17 18

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:
    • 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

 

Manolescu, I. : XML query processing: storage and query model interplay tutorial at the EDBT 2004 summer school

 

Haslhofer B. , Momeni E., Schandl B., Zander S. : Europeana RDF Store Report

 

D2R server