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

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

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