XML et les BD
1. Introduction
2. Modèle de données
3. Langage de requêtes
4. Produits
5. Conclusion
Indexation et Optimisation
1. Introduction
Générations de BD
– Réseau et hiérarchique 70 - 80
– Relationnel 80 - 90
– Objet-Relationnel 90 - …
Web et BD
– un rendez-vous manqué
– couplage faible par serveur d'applications
– le Web est une vaste BD distribuée
– la structuration est faible
– plutôt orienté documentaire ...
Introduction
©GG
2
XML s'impose
Intégration des données et méta-données
Standard d’échange de données universel
Les BD ne peuvent rester indifférentes :
– nécessité de stocker les documents XML
– nécessité de pouvoir interroger ces documents
– évolution ou révolution ?
Quel modèle de données ?
Quel langage d'interrogation ?
Quelle intégration avec l'existant ?
Introduction
©GG
3
Limites de SQL
Mauvais support de l'imbrication
– GROUP BY limités
– Généralement dans les éditeurs de rapports
SQL3 trop complexe
– Requêtes imbriquées difficiles
– Méthodes en qualification coûteuse
– Références pas très claires
Peu adapté à XML
– Vision tabulaire
– Manipulation par des fonctions (SQL/XML)
SQL à 30 ans !
– Inventé en 1970 pour la gestion
– XQuery le successeur ?
Introduction
©GG
4
Exemple de documents
<?xml version="1.0"?>
<Restaurants region="Normandie"
version="2.0">
<Restaurant type="francais"
categorie="***">
<Nom>Le Grand Hôtel</
Nom>
<Adresse>
<Rue>Promenade M. Proust
</Rue>
<Ville>Cabourg</Ville>
</Adresse>
<Manager>Dupont</Manager>
<Menu>Plat du jour</Menu>
</Restaurant>
Introduction
<Restaurant type="francais"
categorie="**">
<Nom>L'Absinthe</Nom>
<Adresse>
<No>10</No>
<Rue>quai Quarantaine
</Rue>
<Ville>Honfleur</Ville>
</Adresse>
<Téléphone>0231893900
</Téléphone>
<Manager>Dupont</Manager>
<Manager>Durand</Manager>
<Menu Prix="12"> Fruits de Mer
</Menu>
</Restaurant>
</Restaurants>
©GG
5
2. Modèle de données
Schémas flexibles et irréguliers
– Optionnels, avec ou sans DTD
Données auto-descriptives
– Balises et attributs
Modèle de type hypertexte
– Support des références
Éléments atomiques ou complexes
– Composition par agrégation
Types de données variés et extensibles
– Textes, numériques, …, types utilisateur
Modèle semi-structuré
©GG
6
Le modèle de données
XQuery Data Model
Modèle des schémas et de XPath 2
Un document est un arbre à nœud étiqueté
Chaque nœud possède une identité
Exprimé en XML, souvent représenté graphiquement
Une forêt est une collection de documents de même
schéma
Une source de données est soit un document, soit une
forêt
Modèle semi-structuré
©GG
7
Diagramme XML Spy
Modèle semi-structuré
©GG
8
Et les documents sans schéma ?
Possibilité de stocker des
documents sans schéma
Solution
– Forêt fermée versus forêt ouverte
– Construction et gestion
dynamique des schémas
– Notion de "document guide" ou
DTD généralisée
– Schéma faible avec typage string
– Possibilité d’inférer des types à
partir des valeurs
– Le SGBD génère un schéma
(arbre couvrant sans feuilles)
– Maintenu lors des mises à jour
(compteur d'utilité)
– Schéma de base pour
l'interrogation
Facilite la conception
– Dégager des collections de
documents apparentés
– Le SGBD conçoit pour vous !
Modèle semi-structuré
©GG
9
Bilan Modèle de données
Un standard riche
– schémas standardisés depuis 3 mai 2001
– Représentation graphique ad-hoc
– Génération automatique en cas d'absence
Faut-il un autre modèle que les schémas ?
– Doit couvrir les schémas
– Doit couvrir les DTD
– Doit couvrir l'absence de schéma et DTD
– Syntaxe plus simple
Modèle semi-structuré
©GG
10
3. Langage de requêtes
MODELE
LANGAGE REQUETES
Hiérarchique
DML DL1
Réseau
DML CODASYL
Relationnel
SQL: SELECT …
Objet
OQL
XML
???
Langages de requêtes
©GG
11
Qu’est ce que XQuery ?
XQuery est le langage de requêtes pour XML défini et
standardisé par le W3C
XQuery s’impose comme le langage de requêtes:
– Pour les bases de données XML natives
– Pour les documents XML textuels (XQuery Text)
– Pour l’intégration de données (bases de données virtuelles)
Le besoin d’interroger les bases relationnelles en XQuery
existe
– Pour l’intégration et la publication de données
– Compétition avec les extensions de SQL (SQL/XML)
Langages de requêtes
©GG
12
Objectifs
Puissance
de SQL
Recherche
d'information
Types XML Schema
XPath 2
Structure
d'arbres
Langages de requêtes
Langage
fonctionnel
©GG
13
La base
Proposé par IBM , MS, AT&T, Data Direct, ...
Langage fonctionnel type CAML
Forme de requête élémentaire
–
–
–
–
FOR $<var> in <forest> [, $<var> in <forest>]+ //itération
LET $<var> := <subtree> // assignation
WHERE <condition> // élagage
RETURN <result> // construction
Les forêts sont sélectionnées par des Xpath
(document ou collection)
Le résultat est une forêt (un ou plusieurs arbres)
Langages de requêtes
©GG
14
Exemple 1 : XPath
(Q1) Noms de tous les restaurants :
collection(“Restaurants”)/Restaurant/Nom/text()
collection(“Restaurants”)/Restaurant/Nom
Langages de requêtes
©GG
15
Exemple 2 et 3 : XPath +
Expression régulière
– Menu de tous les restaurants
collection(“Restaurants”)//Menu
Accès via indice à attribut
– Donnez le nom des menus du premier restaurant
collection(“Restaurants”)/Restaurant[1][email protected]
Langages de requêtes
©GG
16
Exemple 4 : Sélection
Lister le nom des restaurants de Cabourg:
collection(“Restaurants”)/Restaurant
[Adresse/Ville= “Cabourg"] /Nom
<resultat>
{for $R in collection("Restaurants")/Restaurant
where $R/Adresse/Ville = “Cabourg”
return {$R/Nom}}
</resultat>
Langages de requêtes
©GG
17
Exemple 5 : Jointure
Lister le nom des Restaurants avec téléphone
dans la rue de l'Hôtel Lutecia:
for
$R in collection("Restaurants")/Restaurant,
$H in collection("Hotels")/Hotel
where $H//Rue = $R//Rue
and $H//Nom = "Le
Lutecia"
return
<Result>
{$R/Nom}
{$R/Téléphone}
</Result>
Langages de requêtes
©GG
18
Exemple 6 : Restructuration d'arbre
Construire une liste de restaurants par Ville
for $c in
distinct(collection(“Restaurants”)/Restaurant//Ville)
return
<Ville>{$c}</Ville>
<Restaurants>
{for $r in collection(“Restaurants”)/Restaurant
where $r//Ville = $c
return {$r}}
<Restaurants>
Langages de requêtes
©GG
19
Exemple 7 : Imbrication en Where
Adresses des hotels dans des villes ayant des
restaurants trois étoiles
for $h in collection(“Hotels”)/Hotel
where $h/Adresse/Ville in
for $r in collection(“Restaurants”)/Restaurant
where [email protected] = "***"
return {$r/Adresse/Ville/text()}
return {$h/Adresse}
Langages de requêtes
©GG
20
Syntaxe Simplifiée (XLive)
// Réduite à FWR
XQuery
ForClause
VarDef
WhereClause
CplexCond
CondCond
Op
Expr
ReturnClause
XMLElement
VarName
nameTag
QuotedText
Constant
XPath
::=
::=
::=
::=
::=
::=
::=
::=
::=
::=
::=
::=
ForClause [WhereClause] ReturnClause
“for” VarDef [,VarDef] …
“$”VarName “in” “collection” “(” QuotedText “)”/XPath
“where” CplexCond
Cond | Cond AND CplexCond | Cond OR Cplex
Expr Op Constant | Expr Op Expr | “contains(” Expr , Text “)”
“=” | “!=” | “<” | “<=” | “>” | “>=”
“$”VarName/XPath
“return” XMLElement*
“<”tag“>”XMLElement“</”tag“>”| “{” XPath“}”*| “{” XQuery“}”*
::=
Any variable
::=
XML label
Any text between quotes " …“
::=
Quoted text or number
XPath expression restricted to child and descendant directions
©GG
21
Exemple 8 : Agrégat simple
Combien de restaurants y-a-t-il en collection ?
let $R := collection(“Restaurants”)/Restaurant
return
<NombreRestaurant > {count ($R)}
</NombreRestaurant>
Langages de requêtes
©GG
22
Exemple 9 : Agrégat partitionné
Lister le nom de chaque restaurant avec le prix
moyens des menus proposés
– for $r in collection(“Restaurants”)//Restaurant
let $a := collection(“Restaurants”)//
[Restaurant = $r][email protected]
return
<resultat>
{$r/Nom}
<avgPrix>{AVG($a)}</avgPrix>
</resultat>
Langages de requêtes
©GG
23
Exemple 10 : recherche textuelle
Lister les bons restaurants de Paris
– for $r in collection(“Restaurants”)//Restaurant
where (contains ($r/Comments, “Bon”)
or contains ($r/Comments, “Excellent”))
and $r/Adresse/Ville = “Paris”
return {$r/Nom}
Langages de requêtes
©GG
24
Exemple 11 : Ordre et désordre
Lister les bons restaurants de Paris par ordre
alphabétique
for $r in
unordered(collection(“Restaurants”)//Restaurant)
where (contains($r/Comments, "Excellent”)
or contains($r/Comments, "Good”))
and $r/Adresse/Ville = “Paris”
return {$r/Nom}
orderby ($r/Nom descending)
Langages de requêtes
©GG
25
Exemple 12 : Multi-requêtes
Construire un document avec en-tête, titre, liste
restaurants peu chers, titre, liste restaurants chers
<XML_document>
<Very_Expensive_Restaurants>
<Title>List of very expensive restaurants</Title>
{for $r in collection("Restaurants”)//Restaurant
where every $p in [email protected] satisfies ($p>100)
return {$r}}
</Very_Expensive_Restaurants>
<Very_Inexpensive_Restaurants>
<Title>List of very inexpensive restaurants</Title>
{for $r in collection(“Restaurants”)//Restaurant
where some $p in [email protected] satisfies ($p<10)
return {$r}}
<Date>{date()}</Date>
</Very_Inexpensive_Restaurants>
</XML_document>
Langages de requêtes
©GG
26
Exemple 13 : String
Trouver les livres dans lequel le nom d'un élément
se termine par "or" et le même élément contient la
chaîne "Suciu" quelque part. Pour chaque tel livre,
retourner le titre et l'élément qualifiant.
for $b in document("document")//book
let
$e := $b/*[contains(string(.), "Suciu")
and ends-with(local-name(.), "or")]
where exists($e)
return <book> { $b/title } { $e } </book>
Langages de requêtes
©GG
27
Fonctionnalités XQuery Text
Recherche sur mot-clés
Recherche de phrase
Support des mots de
laiaison
Recherche sur préfix,
suffix, infix
Normalisation des mots,
accents, capitales, …
Langages de requêtes
Recherche par proximité
(unité = mots)
Spécification de l'ordre
des mots
Combinaison logic avec
AND, OR , NOT
Recherche par similarité
Tri des résultats par
pertinence
©GG
28
Bilan XQuery
Véritable langage de
programmation
Très puissant
–
–
–
–
–
–
–
–
Sur des forêts dont les
arbres sont des
documents
Questions ?
Sélection
Jointure
Imbrication
Restructuration
Agrégation
Tri
Plein texte
…
Langages de requêtes
©GG
29
4. Aperçu des produits
Systèmes natifs
– Technique spécialisée de stockage et recherche
– Extension des techniques documentaires à l'élément
SGBD relationnels étendus
– Séparation des éléments et du graphe
– Mapping en tables
SGBD objet adapté
– Utilisation d'une structuration objet (DOM)
– Un produit : Excelon (Object Store)
Racheter par Progress Software
SGBDX
©GG
30
4.1 SGBD Natif XML
SGBD
XML
– conçu pour XML,
– stockant les documents en
entiers sans les
décomposer en éléments,
– utilisant de techniques
d'indexation d'arbres
spécifiques.
Stockage
XML
XML
Recherche
XML
Noyau SGBD
Concurrence, Fiabilité
Forêts
d'arbres
SGBDX
Requête
©GG
Index
31
Indexation Plein Texte
Utilisation d'un thésaurus au chargement
– ensemble de termes reliés
– liste des mots importants
– synonymes et préférés
– spécialisations, traductions
– Standards ISO 2788 et ANSI Z39.19
Stémisation (racine) ou lémisation (préféré)
Listes inverses
– fichiers de mots significatifs
– pour chaque mot, adresse document (élément+offset)
SGBDX
©GG
32
Principaux produits
De multiples start-up
–
–
–
–
–
–
–
–
Software A.G. Tamino
http://www.softwareag.com/
X-Hive/Db
http://www.x-hive.com/
Coherity
http://www.coherity.com/
IXIA soft
http://www.ixiasoft.com/
XML Global
http://www.xmlglobal.com/
NeoCore
http://www.neocore.com/
Xyleme
http://www.xyleme.com/
Exist
http://exist.sourceforge.net/
Intégration comme type spécialisé à SGBD OR
– DB2 XML Extender, Oracle XML DB, SQL Server 2005
SGBDX
©GG
33
Xyleme
Entrepôt XML efficace
Architecture distribuée
– Cluster de PCs
– Communication avec Corba
Développé sur Linux en C++
Support du langage de requêtes XyQL
– OQL étendu avec des expressions de chemins
– Recherche plein texte en éléments efficace
SGBDX
©GG
34
Xyleme Functionnalities
SGBDX
©GG
35
Xyleme: Natix Repository
Objectifs
– Minimiser les I/O pour accès directe et balayage
– Accès direct efficace via index et identifiant
– Compression des données sans pénaliser les accès
Stockage efficace d’arbre
– Pages de taille fixe classique
– Enregistrements de taille variable à l’intérieur
Equilibrage des arbres par éclatement de pages
SGBDX
©GG
36
Xyleme: Architecture Physique
XyQuery
Global Query
Manager
Local Query Manager
Loader/Indexer
Repository
Context
Local Query Manager
Loader/Indexer
XyIndex
Repository
Context
xyIndex
SGBDX
©GG
XyIndex
xyIndex
37
Xyleme: Exemple de Requêtes
– Extension de OQL avec XPath
– Orientation recherche textuelle
Select
From
boss/Name, boss/Phone
comp in BusinessDomain,
boss in comp//Manager
Where comp/Product contains “Xyleme”
SGBDX
©GG
38
Xyleme Indexation
Liste inversée standard
– mot  documents contenant ce mot
Index Xyleme
– mot  éléments contenant ce mot
(document + élément identifier)
La plupart des requêtes sur mots-clés sont
traitées en index, sans accès aux documents
Possibilité d’enrichir la requête via un thésaurus
avant la recherche en index
SGBDX
©GG
39
4.2 Mapping SGBDR
XML
Composant logiciel audessus d'un SGBDR
assurant:
XQuery
Recherche
XML
Stockage
XML
– le stockage et l'interrogation
de documents XML
– en transformant le XML en
tables
– et les tables en XML
SQL
SGBD
Tables
de lignes
SGBDX
XML
©GG
Index
40
Exemple de Mapping
Restaurant(#R, Nom, Tel)
SGBDX
Adresse(#R,N°, Rue, Ville) Manager(#R, Nom)
©GG
41
SQL/XML
Intégration de fonctionnalités XQuery à SQL
Support à la SQL3
–
–
–
–
Type de donnée natif XML Type (colonnes XML)
Fonctions d’extraction XPath
Fonctions de construction de XML (pont relationnel)
Insertion et Maj de XML en colonne(s)
Exemple de requête
SELECT XMLElement("Emp",
XMLForest ( e.hire, e.dept AS "department") )AS "result“
FROM EMPLOYEE e
WHERE ExtractValue(e.XMLemp, [email protected]) > 200;
Intégré à Oracle et DB2
SGBDX
©GG
42
Fonctions SQL/XML
SGBDX
Fonction
Rôle
XMLAgg
prend en argument une collection de fragments et retourne un document XML agrégé ;
XMLConcat
reçoit en argument une série d’instances XMLType correspondant aux valeurs d’une colonne pour les lignes
d’une table et retourne les instances concaténées ;
XMLElement
prend en argument un nom d’élément, une collection d’attributs optionnels, un contenu d’élément et retourne
une instance XMLType ;
XMLForest
convertit la suite de ses argument en XML et retourne un fragment XML concaténation des arguments
convertis ;
XMLColAttVal
converti une valeur de colonne en XML ;
XMLSequence
transforme une suite de lignes référencées par un curseur en séquence XML ;
XMLTransform
applique une feuille de style XSL à une instance XMLType et retourne une instance XMLType ;
ExtractValue.
reçoit en argument une instance XMLType et une expression XPath et retourne la valeur scalaire des nœuds
sélectionnés
ExtractXML
reçoit en argument une instance XMLType et une expression XPath et retourne une instance XML
représentant les nœuds sélectionnés.
©GG
43
Oracle XML/DB
Stockage et publication
– Mapping de XML plat sur une table
– Mapping de XML imbriqué en tables imbriquées
– Stockage de XML en colonne (XML Type)
– Commandes PutXml et GetXml
Interrogation
– Support de SQL/XML
– Servlet XSQL
document XML avec requêtes SQL/XML
transformation du résultat des requêtes en XML
SGBDX
©GG
44
Microsoft: SQL Server 2005
Stockage de XML
– Stockage natif comme "XMLtype"
– Mapping de XML en tables
XPath
XQuery
SQL
défini par assistants
exécuté par procédures stockées
– Stockage en Large OBject
varchar et varbinary
Interrogation en XML
– XQuery et XML DML
SQL
Server
Proposé pour interroger et mettre à
jour les données XML
Possibilité de définir des vues XML et
de les interroger
XML
View
XML
Files
– SELECT … FOR XML
Retourne du XML à partir de
requêtes SQL et permet de définir le
format du XML retourné
RowSet
– OpenXML
XML
Manipulation de documents XML
comme des tables avec des
procédures stockées
SGBDX
©GG
45
XQuare Bridge (Open Source)
Extraction XML
– via XQuery traduite en SQL
Scripts XQuery
API XML/DBC
Extractor Mapper
Stockage XML en base
JDBC
– Mapping via schema
– Accélérateur XTree (Repository)
SGBDR
Portable
– Oracle, SQLServer, PostGres, …
SGBD
Version industrielle
BD
relationnelle
– www.datadirect.com
SGBDX
Règles de Mapping
API SAX2
©GG
46
Natif versus XORDBMS
Points forts XOR
Points forts Natif
– pas de nouveau SGBD
– possibilité de normaliser les
données
– possibilité de stocker
comme valeur d’attribut
– une certaine portabilité
multi-SGBD
– performance pour accès
grain fin
SGBDX
– un nouveau SGBD fait pour
XML
– jamais de mapping à définir
et maintenir
– intégrité du document
– recherche plein texte
– performance pour accès
gros grain
©GG
47
5. Conclusion
XML peut-il changer les bases de données ?
– Recherche en BD semi-structurées
– Besoin de schémas faibles (XML Schéma)
– Langage de requêtes standardisé (XQuery)
– L'effet du Web ...
Intégration douce à l'Objet/relationnel
– Transformation en tables
– Gestion du graphe
– Support des textes libres niveau élément
©GG
48
Résumé
XML fournit un cadre uniforme pour :
– échanger des données structurées (DTD, schéma)
– échanger des données semi-structurées (graphes)
– interroger des documents (XQuery)
– intégrer des sources de données hétérogènes (table,
multimédia)
Beaucoup de travaux sont en cours
– Gestion efficace au sein d'Oracle, de DB2, etc.
– Construction de middlewares pull/push fondés sur
XQuery
– Construction de SGBD pur
©GG XML (Xylème, etc.)
49
Techniques d’Indexation XML
1. Objectifs
2. Dataguide et Variation
3. Index Fabric
4. Adaptative Path Index
5. Node Numbering scheme
6. Compact Structural Summary
7. Conclusion
Requirements
XML Queries involve navigating data using regular
path expressions.(e.g., XPath)
– /Livre//Auteur[@specialite="informatique"])
– Accessing all elements with same name string.
– Ancestor-descendant relationship between elements.
– Content based access on values included in text.
©GG
51
Index Types
Structural index
– Accessing all elements of given name
– Ancestor-descendant and parent-child relationship
between elements
Content index
– Accessing elements containing given keywords
– Supporting most text search functionalities
©GG
52
Classical Content Index
Classically based on inverted
lists
Words
Localization
- t1 : doc1-100, doc1-300, doc3-200, …
– For each term, gives the doc.ID +
localization
- t2 : doc2-30, doc4-70, …
- t3 : doc4-87, doc5-754, …
Several variations allows
different search types
– Offset, Relative, Proximity
(word, localization)
Generally stored in a B+-Tree
to optimize search for a given
word
Size is an important issue
– Fixed entry (word repeated)
(word, Frequency,
(localization)*)
– Variable length entry
– Memory and Disk
©GG
53
Problem with XML
Support of element addressing
Query processing
– Doc.ID should include NodeId
(Xpath) + Offset
– Structural joins
– Text search
– Exact search
Index size becomes very large
– XPath are long
Support of typed data
Support of updates
– Integer, float, simple types of
XML schema
– Requires classical indexes for
certain elements
– Incremental updates would
be a plus
©GG
54
Evaluation Criteria
Identifiers
Keyword Search
– Per node or per document
– By element scan
– By B-tree traversal
Descendant/Ancestor
Search
Update
– By join algo.
– By graph traversal
– By OID comparison
– Incremental
Index size
– Entry number
– Entry size
©GG
55
2-Dataguide and Variation
A legal label path:
Goldman & Widom VLDB97
Dynamic schemas
– Restaurant/Name
Target set
– helps in query formulation
– for e=Restaurant/Entree is Ts(e) =
{6,10,11}.
– DocId can be added to identifiers
Concise and accurate
structural summaries
– Every path in the database has
one and only one corresponding
path in the DataGuide with the
same sequence of labels
©GG
56
Dataguide Principle
To achieve conciseness
– a DataGuide describes every
unique label path of a source
exactly once.
To ensure accuracy
– a DataGuide encodes no label
path that does not appear in the
source.
2,3
4
And for convenience
– a DataGuide itself be an object
(OEM or XML).
5,9
6,10,11
7
8
8
Targeted dataguide
©GG
57
Dataguide Evaluation
Identifier
– One per node
Descendant/Ancestor Search
– By graph traversal
Keyword Search
– By element scan
Update
– Insertion is incremental
– Deletion is complex
Index size
– Entry number : Linear for tree; can be exponential in number of DB nodes
– Entry size : number of elements for a path
©GG
58
T-Index
[Milo & Suciu, LNCS 1997]
T-index stands for Template-index
A path template t has the form
– T1 x1 T2 x2 … Tn xn
– where each Ti is either a regular path expression or one of the
following two place holders P (any Path) and F (any Formula)
– //restaurant/ x P y /Address/City z F u
A query path q is obtained from t by instantiating:
– P by any path ; F by any formula
©GG
59
Principle
T-index indexes all sequences of objects connected by a
sequence of path expressions defined by a template.
Particular cases :
– 1-index indexes = template any path P
Indexes all objects reachable through an arbitrary path expression P from
a root:
two nodes are equivalent (same entry) if the set of paths into them from
the root is the same.
1-index is a non-deterministic version of the strong data guide
– 2-index indexes = template P x P
all pairs of objects connected by an arbitrary path expression P
©GG
60
Building a T-index
Group objects into equivalence classes containing objects that are
indistinguishable w.r.t to a class of paths defined by a path
template
Finer equivallence classes are more efficient to construct using bisimulation
Construct a non deterministic automaton
– states represent the equivalence classes
– transitions correspond to edges between objects in those classes.
T-index can be used to answer queries of more general forms than
the template
©GG
61
3-Adaptative Path Index (APEX)
Adaptative Path Index for XML [Chung et.al.
SIGMOD 2002]
Summarize paths that appear frequently in query
workload
Maintain all paths of length 1
Efficient for partial match paths
Incremental update of index
©GG
62
APEX details
Each node has an identifier (nid)
Required paths for indexing ({label}+some composed
paths)
APEX = Graph (structural summary) + hash tree
(incoming required paths to nodes of Graph)
Hash tree is used to find nodes of graph for given label
path, also for incremental update
Determine frequently used path from query workload
using sequential pattern mining
©GG
63
APEX Example
XML data structure
APEX Hash tree and Graph
©GG
64
APEX Evaluation
Identifiers
– One per node
Descendant/Ancestor Search
– Hash tree access if required or graph traversal or join
Keyword Search
– Not supported
Update
– Insertion is incremental
Index size (two structures)
– Entry number : Linear in number of nodes
– Entry size : number of elements for a path
©GG
65
4-Index Fabric
[Cooper et al. .A Fast Index for Semistructured
Data.. VLDB, 2001]
Extension of dataguide for text search
– Keeps all label paths starting from the root
– Encode each label path with data value as a string
– Use efficient index for strings to store it (Patricia trie)
Perform queries on keywords for elements as
string search
Does not keep information on non-terminal nodes
©GG
66
Patricia Trié
Trié : Key  Value
A Patricia trie is a simple
form of compressed trie
which merges single child
nodes with their parents
More efficient for long keys
(non-common postfix in one
node)
Trie = A tree for storing strings in which there is one
node for every common prefix. The strings are stored
in extra leaf nodes.
©GG
67
Exemple
Doc 1:<invoice>
<buyer>
<name>ABC Corp</name>
<address>1 Industrial Way</address>
</buyer>
<seller>
<name>Acme Inc</name>
<address>2 Acme Rd.</address>
</seller>
<item count=3>saw</item>
<item count=2>drill</item>
</invoice>
Doc 2: <invoice>
<buyer>
<name>Oracle Inc</name>
<phone>555-1212</phone>
</buyer>
<seller>
<name>IBM Corp</name>
</seller>
<item>
<count>4</count>
<name>nail</name>
</item>
</invoice>
©GG
68
Patricia Trie
©GG
69
Search on Paths
Example of queries:
– /invoice/buyer/name/[ABC Corp]
– /invoice/buyer//[ABC Corp]
A key lookup operator search for the path key
corresponding to the path expression.
If path expands to infinite number of tags
– start by using a prefix key lookup operator,
– then navigate through children to check the rest
©GG
70
Fabric Evaluation
Identifiers
– One per document
Descendant/Ancestor Search
– As string search; do not keep order of elements
Keyword Search
– By Patricia trie leaves if expanded; value index otherwise
Update
– Insertion is incremental
– Deletion is complex
Index size (index stored with document)
– Entry number : Linear for tree
– Entry size : number of elements for a path
©GG
71
5-Node Numbering Scheme
Used for indexing elements
Node Identifier (NID)  element
The NID aims at replacing structural joins by
simple function computation:
– check parent & ancestor relationships
is_parent(NID1,NID2), is_ancestor(NID1,NID2)
– determine parent & children
get_parent(NID1), get_children(NID1)
©GG
72
Virtual nodes (1)
[Lee & Yoo Digital Libraries 99]
– Document structure mapped on a k-ary tree
– Node identifier assigned according to the level-order
tree traversal
parent(i) = (i-2)/k + 1
child(i,j) = k(i-1) + j + 1
©GG
73
Virtual nodes (2)
NID can be used to address elements in index of
elements
Only certain nodes (e.g., leaves) have to be indexed as
parent nodes can be determined by computation
Problems:
– arity of tree – may be variable and large
– determination of real existence of parent/child
– update when arity increases ?
©GG
74
XML trees node pre/post numbering
[Dietz82]
Identification of nodes
– Identifier = preorder
rank||postorder rank
(1,7)
X ancestor of Y <=>
– pre(X) < pre(Y) and
post(X) > post(Y)
(6,6)
(2,4)
Example
– 1<5 and 7>3 => (1,7) ancestor
(5,3)
(3,1)
©GG
(4,2)
(5,3)
(7,5)
75
Interval encoding
[Li&Moon VLDB 2001]
Identify each node by a pair of
numbers <order, size> as follows:
For a tree node y of parent x:
– order(x) < order(y)
– order(y)+size(y) =< order(x) + size(x)
(1,100)
(41,10)
(10,30)
For two sibling nodes x and y, if x is
the predecessor of y in preorder
traversal then
– order(x) + size(x) < order(y)
(11,5)
(25,5)
(45,5)
(17,5)
Size keeps space for updates
©GG
76
Relative Region Coordinates (1)
[Kha & Yoshikawa IEEE Data Engin. 2001]
– A RRC of a node n of an XML tree is a pair [sp-sn,sp-en] of
addresses in the region of parent, i.e., relative to parent start
Parent
Child
s
e
©GG
77
Relative Region Coordinates (2)
Absolute region coordinate (ARC)
– Relative to root begin (from byte Nth to Mth)
– Allow to extract the XML data
– Can be derived from RRCs of parents and self:
Begin = (parentsself)s –(k-1)
End = (parents)s +e(self)–(k-1)
Advantages
– Updates are kept local to a region
To access parent-child efficiently
– A B-tree like structure is maintained (à la Natix).
©GG
78
Xyleme
Generate a form of dataguide per cluster
– Generalized DTD
Manage a label and value index (full index)
– Keep document ID and element ID
– Two forms of element ID:
Bit structured scheme: structure position
Prefix-postfix scheme: left-deep traversal
Stores XML DOM trees in pages
– NATIX (Mannheim Univ.) technology
©GG
79
Xyleme
©GG
80
6-Compact Structural Summary
[Bremer & Gertz Tech Report 2003]
Compact addressing of words in XML doc.
Encode XPath as reference to a path in a
document guide (path set, DTD or schema)
©GG
81
Managing a Compact Index
Naïve XML Indexing
Problem:
– (Word,docId,(XPath)*)
– How to memorize the
location of a word inside an
element ?
Example
– book/chapter[2]/resume/sec
tion[3]
– article/author/name
Solution [Bremer & Gertz
02]
Difficulties:
– Encode the XPath as a
reference to a path in a
document guide (path
sequence or schema)
– Index size !
– Processing time !
Intersection of lists
©GG
82
XPath Encoding
XPath encoded as a path ID (PID) of structure (N,(p1,p2, ...)
– N being a node identifier in the guide
– (p1, p2, ...) being indices for repetitive ancestors from root to N
db
db
I
Article*
II
techreport
article
article
title
III
title
text
techreport
VI
text
IV
Sect*
V
Document Guide
sect sect sect
/db/article[1]/text/sect[3]
PID : (V, (1, 3))
©GG
83
PID Ordering and Encoding
Compact PID Encoding : (V, (1, 3))
PID order :
/db/article[1]/text/sect[3]
– IV,(1))<(V,(1,2)) <(V,(1,3)).
Pre-order relationship
db
– X Parent Y
–  PID(X) < PID(Y)
Compact PID encoding
techreport
article
article
– Path number
Integer (short)
2 children : 1 bit
title
text
– Repetitive node
1 child : 0 bit
3 children : 2 bits
log2(n) bits
sect sect sect
Total :
©GG
3 bits
84
Index Implementation
Entry
– Word (stem) || Address
– Address is :
PID || (offset in element)*
<livre>
<titre>Les Misérables, Tome 1 : Fantine</titre>
<auteur>Victor Hugo</auteur>
<histoire>
1815. Alors que tous les aubergistes de la ville l'ont chassé, le
bagnard Jean Valjean est hébergé par Mgr Myriel ( que les
pauvres ont baptisé, d'après l'un de ses prénoms, Mgr
Bienvenu). L'évêque de la ville de Digne, l'accueille avec
bienveillance, le fait manger à sa table et lui offre un bon lit.
….
</histoire>
</livre>
– Example
City (V(1,3); (9, 36))
Word
PID – offset*
Valjean
(PID; 15)
Ville
(PID; 9, 36)
…
©GG
85
XQuery Text Evaluator
Normalize the query through thesaurus
– Translation
– Synonyms
– Conceptualization
Access to the text index
– Intersection, union, difference of PIDs
Access to the relevant elements from PIDs
Verification of relevance
©GG
86
7-Conclusion
Various indexing techniques for XML
Main dimensions of variations
– Structural summary
Dataguide, Schema guide, Generalized DTD
– Identification of nodes (NID)
Should keep parent-child relationship
Should be stable to updates
– Index of keywords
Should be compact
Should give NID and offset of instances
©GG
87
Classification
XML
Indexing Methods
Hierarchy
T-Index
Fabric
Dataguide
Numbering
Scheme
Text
Search
Graph
Traversal
APEX
Pre/Post
Order
RRC
Interval
Encoding
©GG
88
Index for XQuery Text
Facilitate the retrieval of:
– Non stop words
– Suffixes, prefixes
– Location of words in elements
– Relevant nodes for a search
Entries should focus on elements
– Word [(docId, NID)*]
©GG
89
Implémentation XQuery
Introduction
Algèbre XML
Génération des plans
1. Introduction
Des techniques en évolution
– Beaucoup de recherche sur XML DB
Extension des techniques relationnelles
– Algèbre XML
– Réécriture de requêtes en arbre algébrique
– Transformation et optimisation des arbres
– Prise en compte des index de structure et contenu
©GG
91
Techniques de base
XQuery
Parser
Analyse de la requête
Cannonisation
Mise en forme normale
Transformation
Transformation et simplification
Génération
Génération d'un plan d'exécution
Optimizer
Optimisation
Query
Plan
Run Time
Machine
Machine d'exécution de l'algèbre
©GG
92
2. Algèbres pour XML
De multiples algèbres
– Jagadish H.V., Lakshmanan L.V.S., Srivastava D., Thompson K.
TAX: A Tree Algebra for XML, Proc. DBPL Conf., Roma Italy,
2001.
– Fernandez M., Simeon J., Wadler P.. An Algebra for XML Query,
In Foundations of Software Technology and Theoretical
Computer Science, New Delhi, 2000.
– Zaniolo C. The Representation and Deductive Retrieval of
Complex Objects, Proc 11th VLDB, Stockholm, 1985.
– Galanis L., Viglas E., DeWitt D.J., Naughton J.F., Maier D.
Following the Paths of XML: an Algebraic Framework for XML
Query Evaluation, 2001
– Tuyet-Tram Dang-Ngoc and Georges Gardarin Federating
heterogeneous data sources with xml, IKS 2003
©GG
93
XAlgèbre
Proposée et implémentée pour un médiateur
– XMLMedia, XQuark
– XLive
Besoin d’une algèbre adaptée à XQuery
– XTuples, représentation de données semi-structurées
– XOpérateurs, une extension des opérateurs
relationnels, manipulant les XTuples.
©GG
94
XTuples
Pourquoi ce besoin de
nouvelle représentation?
– Valeurs nulles
– Attributs multivalués
– Extensions
Nécessité d’une
représentation adaptée aux
données semi-structurées.
©GG
Nom
Prénom
Club
Palmarès
Mutu
Adrian
NULL
Coupe
d’Italie
Palermo
Martin
Villareal
NULL
Del Piero
Allessandro
FC Juventus
Ligue des
champions,
Championn
at d’Italie
95
XTuples : représentation
Un XTuple est composé de
– un ensemble d’arbre A
– un ensemble de références R sur
les nœuds des arbres A.
– Ces références sont appelées
XAttributs.
R
A
a/b a/c f/h/i f
a
Les opérations relationnelles se
font sur R.
Les parcours et recomposition
se font sur A.
Un ensemble de XTuples du
même type forment une
XRelation
©GG
f
c
b
A
eD
d
B
C
j
E
a
F
f
c
b
G
h
i
g
d
H
g
eJ
I
h
i
j
K
L
96
Les XOpérateurs
Opérateurs étendus du relationnel adapté aux données
semi-structurées.
Ils opèrent sur les XRelations (composées de XTuples)
Semi-pipeline
Full-pipeline
• XJoinHash
Non-bloquant • XConstruct
Bloquant
• XMin
•
•
• XJoinMultiHash
• XIntersection
Xsource
Xsource
Xsource (‘PLAYERS’)
(‘STADIUM’)
(« STADIUM »)
Xsource
Xsource
(‘STADIUM’)
(« STADIUM
»)
Relation Étudiée
Dans son intégralité
XMax
Puis jointure XTuple
Hashage
1°
relation,
de retourner un XTuplepar
XTuple
XOrderBydeavant
la relation 1
Puis 2°
XOrderBy
U
XJoinHash
©GG
XUnion
• XRestrict
• XProject
• Xunion
• XProduct
• XJoinSimple
• XSource
97
Construction et Projection
XSource
–
–
–
–
construction XAttribut
construction forêt
ordre de la source
non-bloquant
a bc
<SAX/>
XSource
XProjection
– destruction de colonnes
– destruction de (sous-)
arbres
– ordre préservé
– non-bloquant
a bc
bc
XProjection
©GG
98
Filtrage
XRestriction
– destruction de lignes complètes
– ordre préservé
– non bloquant
a bc
a bc
XRestriction
©GG
99
Union
XUnion
– ordre préservé en mode bloquant, non préservé sinon
– bloquant ou non suivant paramétrage
a bc
XUnion
a bc
a bc
©GG
100
Jointure
XJointure
– Jointure des tables et juxtaposition d'arbres
– ordre préservé en mode bloquant, non préservé sinon
– bloquant ou non suivant paramétrage
a bc
XFusion
XJointure
– Concaténation d'arbres
a bc d e
d ef
©GG
101
Algèbre XML : Imbrication
Opérations d’imbrication nécessaire pour calculer les
éléments multi-valués
– Exemple :
–
for $r in //restaurant
–
Let $m := $r//menu
–
Return ($r/name, $r/region, count($m))
Solution: introduire les opérateurs Nest/Unest
–
–
$r.Project(/name, /region, //menu) $r1
$r1.Nest(/name,/region, //menu*)
En plus court et plus puissant:
–
$r.Project((/name), /region, //menus*)
Aussi utile pour les quantifiers (quel que soit = every)
©GG
102
Algèbre XML: Valeurs nulles
Nul en XML à deux aspects
– Élément vide <region />
– Elément absent
XQuery recherche les prédicats vrai (non nuls)
– Elément en condition obligatoire
XQuery permet les éléments vides en résultat
– Correspond à une valeur optionnelle
Doit être pris en compte par l’algèbre
– Les restrictions peuvent éliminer les nuls
– Les jointures sont des (left/right) outer join si le résultat n’est pas
soumis à condition
©GG
103
Annotation des attributs
Les attributs des XRelations sont associés à un XPath
– $r/nom, $r/region, $r/offer/menus/menu
Chaque attribut peut être annoté style DTD
– A0 = optional, A1 = mandatory
– A* = nested optional, A+ = nested mandatory
Les attributes peuvent être la base d’un groupe
d’imbrication
– (A, B)
Exemple
– ($r/nom1),$r/region0, $r/offer/menus/menu*
©GG
104
XAlgebra: Vue d’ensemble
Datasource.XSource (Path seq, atomic XQuery)  XRelation
– Transform a source in an XRelation of attributes Path sequence
XRelation.XRestrict (unary Constraint) XRelation
– select Xtuples satisfying conditions on attribute values
XRelation.XProject (Path seq) XRelation
– Remove attributes that are not in path sequence
XRelation.XJoin (XRelation, binary Constraint)  XRelation
– join of two XRelations on attribute values
XRelation.XFusion (Path seq)  XRelation
– Remove attributes and merge each XTuple trees in one of given schema
XRelation.XReconstruct (Path seq)  XML
– Extract XML documents of given schema from the XRelation
©GG
105
Implémentation des algorithmes
XSélection
XJointure
– Par accès à index
– Intérêt d'indexer tous
les mots
– Intersection et union
des adresses selon
critères
– Filtrage final pour
vérifier
– Par accès aux index
– Par produit cartésien
– Par tri-fusion
– Par hachage
Intérêt du pipline
©GG
106
3. Techniques de Transformation
Notion de modèle d’arbre (Tree Pattern)
Jagadish VLDB 2002
Principe des modèles d’arbres généralisés (GTP)
Utilisation des GTP pour XQuery
Optimisation & performances
©GG
107
TPQ (Tree Pattern Query)
TPQ = arbre modélisant une requête.
– Il est destiné à être « mappé » sur l’arborescence du
document XML cible
$a
Arbre T
$b
$c
Arbre T2
$e
ancêtre
$f
parent
$d
$g
: relation ancêtre-descendant
: relation père-fils
©GG
108
GTP (Generalized Tree Pattern)
Le GTP ajoute au TPQ des arcs en pointillés symbolisant
des relations optionnelles
GTP: G = (T,F) T: arbre F:formule
Chaque nœud de l’arbre T est labellisé par une variable
et possède un numéro de groupe.
F est une formule booléenne exprimant les prédicats
applicables aux nœuds.
Un ensemble de nœuds forment un groupe s’ils sont
reliés entre eux par des liens non optionnels.
©GG
109
GTP - Exemple
FOR $p IN document(“auction.xml”)//person, $l IN $p/profile
WHERE $l/age > 25 AND $p//state != ‘MI’
RETURN <result> {$p//watches/watch} {$l/interest} </result>
$p (0)
$s $w
(0) (1)
$l (0)
$t $g
(1)
(0)
$p.tag = person & $s.tag = state &
$l.tag = profile & $i.tag = interest &
$w.tag = watches & $t.tag = watch &
$g.tag = age & $g.content > 25 &
$s.content != ‘MI’
$i
(2)
Relation optionnelle
Numéro de groupe (par convention
le groupe 0 inclut l’élément root)
©GG
110
Pattern Match
Un « Pattern Match » de l’arbre G dans une
collection d’arbres C est un sous-arbre h partiel
h: G  C tel que:
– h contient au moins le groupe 0 de G.
– h préserve la structure relationnel de G.
– h vérifie la formule booléenne F de G.
©GG
111
Pattern match : Exemple
On mappe le GTP sur
l’arborescence XML
$p (0)
$s $w
(0) (1)
(1)
GTP
XML
1
people
$l (0)
$t $g
$i (2)
(0)
person 2
3
6
9
address watches profile
11
person
12
address
15
profile
4
5
7
8
10
13
14 16
17
city age
interest
state city watch watch age state
“30” “s2”
“28”
“s1”
Résultat = H1: $p->2, $s->4, $l->9, $g->10, $w->6, $t->7
©GG
112
GTP Universel
Il permet de modéliser les requêtes contenant le
quantificateur « EVERY » dans la clause
« WHERE »
Un GTP universel est un GTP G=(T, F) tel que
plusieurs arcs soient étiquetés ‘EVERY’
Un arc peut être étiqueté ‘EVERY’ seulement s’il
pointe sur un nœud atteignable par des arcs non
optionnels depuis le nœud racine
©GG
113
GTP Universel : Exemple
FOR $o IN document(“auction.xml“)
WHERE EVERY $b in $o/bidder SATISFIES $b/increase>100
RETURN <result> {$o} </result>
(0) $o

F_L :
F_R:
(1) $b

pc($o, $b) & $b.tag = bidder
pc($b, $i) & $i.tag = increase &
$i.content >100
$b: [F_L →
$i: (F_R)
(2) $i
©GG
114
GTP Requête imbriquée
FOR $p IN document(“auction.xml”)//person
LET $a := FOR $t IN document(“auction.xml”)//closed_auction
WHERE [email protected] = [email protected]
RETURN <item>
{FOR $t2 IN document(“auction.xml”)//europe/item
WHERE [email protected] = [email protected]
RETURN {$t2/name}}
</item>
WHERE $p//age > 25
RETURN <person name = {$p/name/text()}> {$a} </person>
→ Récupère le nom et les items achetés en europe, par
toutes les personnes agées de plus de 25 ans.
©GG
115
GTP Requête imbriquée (2)
(0)
$p
$g
(0)
(1.0)
$t
(1.1.0)
$e
$n1 $b
$i
$t2 (1.1.0)
(2) (1.0) (1.1.0)
$n2(1.1.1)
©GG
$p.tag = person &
$g.tag = age &
$n1.tag = $n2.tag=name &
$b.tag = buyer &
$t.tag = closed_auction&
$i.tag = itemref &
$t2.tag = item &
$g.content > 25
Join Condition:
$p.id=$b.person &
$i.item=$t2.id
116
Transformation
XQuery en GTP
XQuery : “FLWR”
Une expression FLWR :
ForClause ::=
(LetClause ::=
WhereClause ::=
ReturnClause ::=
FOR $fv1 IN E1, … , $fvn IN En.
LET $lv1 := E1, … , $lvn := En.)
WHERE
(E1, … , En).
RETURN {E1} … {En}.
Ei ::= FLWR (Requêtes imbriquées) | XPATH.
©GG
117
Algorithme de transformation
Il prend en entrée une expression FLWR et
renvoie un GTP
Il parse au fur et à mesure la requête XQuery en
utilisant la récursivité afin de gérer les expressions
FLWR imbriquées dans une clause ‘FOR’ par
exemple
Le parsing d’une expression Xpath entraîne la
création d’un nouveau nœud dans le GTP résultat
©GG
118
4. Plan d’évaluation
La principale motivation derrière les GTP est de
fournir une base pour une exécution efficace.
Pour cela:
– Supprimer les correspondances répétées pour des
TPQ similaires.
– Retarder la matérialisation des nœuds autant que
possible.
©GG
119
Algèbre physique
Index Scan ISp(S) :
– Sort chaque nœud satisfaisant le prédicat p en utilisant un index pour les
arbres S d’entrée.
Filter Fp(S) :
– Sort seulement les arbres satisfaisant le prédicat p des arbres S. L’ordre est
préservé.
Sort Sb(S) :
– Trie la séquence d’entrée des arbres S sur la base de tri b.
Value Join Jp(S1,S2) :
– une comparaison des deux séquences d'arbres d'entrées, par le prédicat de
jointure p. L'ordre de la séquence de sortie est basé sur l'ordre de séquence
d'entrée gauche de S1.
©GG
120
Algèbre physique (2)
Structural Join SJr(S1, S2):
– Les séquences d'arbres S1 et S2 doivent être triées en fonction
du noeud id. L’opérateur joins S1 et S2 basés sur la relation r
entre eux (pc ou ad)pour chaque paire. La sortie est triée sur S1
ou S2 si besoin.
Group By Gb(S) :
– l'entrée S est triée sur le group by basé sur le prédicat b.
Merge M(S1,…,Sn) :
– Les Sj doivent avoir la même cardinalité k. Pour chaque 1≤i≤k,
joindre l'arbre i avec chaque entrée sous une racine artificielle,
et produire l'arbre. L'ordre est préservé.
©GG
121
Traduire le GTP en plan physique
Utilisation d'un algorithme spécifique pour générer
le plan physique à partir du GTP
Obtention d'un plan du type :
M
G
person, profile
S
person, profile
SJ
watches/watch
G
person, profile
S
person, profile
OSJ
profile/interest
©GG
S
F : filter
IS : tag index scan
SSJ : structural semi-join
SJ : strcutural join
OSJ : outer structural join
S : sort
M : merge
122
Optimisation grâce aux schémas
Principe :
– les informations contenues dans le schéma XML (.xsd)
vont permettrent d’optimiser les GTP et les plans
d’exécution physique en résultant
©GG
123
Élimination des nœuds « internes »
a//b//c  a//c
$a
$a
$b
$c
$c
Seulement si le schéma spécifie que tout chemin de a à c
passe par un élément b
©GG
124
Deux nœud pour le même élément
XML
FOR $b IN …//book
$b
$b
WHERE $b/title = ‘Germinal’
RETURN <x> {$b/title} {$b/year} </x>
$t
$t2 $y
$t
$y
Seulement si le schéma spécifie que tout livre ne
possède qu’un titre !
©GG
125
Éliminer les nœuds inutiles
FOR $a IN …./a[b]
RETURN {$a/c}
$a
$b
$a
$c
$c
Seulement si le schéma spécifie que tout élément a
possède au moins un sous-élément b !
©GG
126
Eliminer un ‘GROUP BY’ du plan
physique
RETURN {$a/sous-element}
Une clause ‘FOR’ nécessite un ‘GROUP BY’ du
résultat
Mais si le schéma spécifie que le sous-élément
est unique alors ce ‘GROUP BY’ devient inutile
©GG
127
Performances des GTP
La méthode d’exécution faisant appel aux GTP
surpasse en rapidité les méthodes de parcours
classique de l’arborescence pour l’exécution de
tous les types de requêtes
Les auteurs ont effectués ces tests dans
l’environement suivant : TIMBER native XML
database, PIII 866MHz, Ms Windows 2000, index
sur les principaux éléments
©GG
128
5. Conclusion
Les GTP semblent être actuellement la méthode
la plus efficace pour XQuery
Mode opératoire en 3 étapes :
Requête
XQuery
GTP
Optimisation
par schéma
©GG
Plan
physique
Résultat
129
Descargar

X5-BD_XML - Georges Gardarin