Fédération de données semi-structurées avec XML Tuyêt Trâm DANG NGOC Laboratoire PRiSM Université de Versailles-Saint-Quentin Présentation du Mardi 10

Fédération de données semi-structurées avec XML

Tuyêt Trâm DANG NGOC

Laboratoire PRiSMUniversité de Versailles-Saint-Quentin

<[email protected]>

Présentation du Mardi 10 juin 2003

Tuyêt Trâm DANG NGOC - Université de Versailles 2mardi 11 avril 2023

ContexteIntégration de donnéesÉvaluation de requêtesValidationOptimisationConclusion et perspectives

Plan


Contexte

Intégration de donnéesÉvaluation de requêtesValidationOptimisationConclusion et perspectives

Plan

Contexte : Représentation du monde réel

• Données non-régulières (données semi-structurées)

• Représentation (XML) et langage de requêtes (XQuery)


Inconvénients des modèles de données classiques

bar nom adresse rue ville telephone boissonL'Envol NULL LaCépède Paris NULL Maple Kiss,

Gin Tonic

Le Frog's

25, Cour Saint Emilion, Paris

NULL NULL 0143407071 NULL

L'apparement Café

NULL NULL Paris 0148871222,

0148874942Café, Thé, Chocolat, Margarita, Gin Tonic

Valeurs nulles Attributs multi-valués

Typages différents Difficultés

d'extensions


Données semi-structurées

Structure implicitedéfinie dans les données

elles-mêmes Structure irrégulière

données manquantesdonnées multi-valuéesdonnées de types différents

Structure arborescente Schéma éventuel Représentation

SGML, OEM, XML

bar

nom

adresse

rue

ville

boisson

telephone

boisson

bar

nom

adresse

L'Envol

Lacépède

Paris

Maple Kiss

Gin Tonic

Le Frog's

01 43 40 70 71

25, cour Saint-Emilion Paris

Manipulation et traitement complexe

<bar> <nom> L’Envol </nom> <adresse> <rue> Lacépegrave;de </rue> <ville> Paris </ville> </adresse> <boisson> Maple Kiss </boisson> <boisson> Gin Tonic </boisson></bar>

<bar> <nom> Le Frog’s </nom> <telephone> 01 43 40 70 71</telephone> <adresse> 25, cour Saint-Emilion Paris</adresse></bar>

<bar> <nom> L’Envol </nom> <adresse> <rue> Lacépegrave;de </rue> <ville> Paris </ville> </adresse> <boisson> Maple Kiss </boisson> <boisson> Gin Tonic </boisson></bar>

<bar> <nom> Le Frog’s </nom> <telephone> 01 43 40 70 71</telephone> <adresse> 25, cour Saint-Emilion Paris</adresse></bar>


Langage de requête sur XML : XQuery

for $var in expr

let $var := expr

where exprorder-by $varreturn expr

for $var in expr

let $var := expr

where exprorder-by $varreturn expr

•Ordonnancement•Equivalent de ORDER-BY de SQL

•Ordonnancement•Equivalent de ORDER-BY de SQL

OO

•Sous-arbres sélectionnés•Présentation des sous-arbres•Equivalent du SELECT de SQL avec une reconstruction

•Sous-arbres sélectionnés•Présentation des sous-arbres•Equivalent du SELECT de SQL avec une reconstruction

RR

FF•Collection d’arbres utilisés•Equivalent du FROM de SQL

•Collection d’arbres utilisés•Equivalent du FROM de SQL

LL•Mémorisation d’arbres•Affectation de variables locales

•Mémorisation d’arbres•Affectation de variables locales

WW

•Condition (élagage)•Equivalent du WHERE de SQL

•Condition (élagage)•Equivalent du WHERE de SQL


Exemple XQueryfor $v in Collection ("*")/volsfor $g in Collection ("*")/guide where $v/temps < 4and $v/trajet/arrivee = $g/villereturn<voyage> <vol> <num> {$v/numero} </num> <trajet> {$v/trajet} </trajet> </vol> <temperature> {$g/tpmoy} </temperature> <hotels> { for $h in Collection ("*")/hotels where $h/categorie = "5" and $v/trajet/arrivee = $h/adresse/ville return <hotel> <nom> {$h/nom} </nom> <adresse> {$h/adresse} </adresse> </hotel> } </hotels></voyage>

for $v in Collection ("*")/volsfor $g in Collection ("*")/guide where $v/temps < 4and $v/trajet/arrivee = $g/villereturn<voyage> <vol> <num> {$v/numero} </num> <trajet> {$v/trajet} </trajet> </vol> <temperature> {$g/tpmoy} </temperature> <hotels> { for $h in Collection ("*")/hotels where $h/categorie = "5" and $v/trajet/arrivee = $h/adresse/ville return <hotel> <nom> {$h/nom} </nom> <adresse> {$h/adresse} </adresse> </hotel> } </hotels></voyage>

vols

temps

trajet

arriveedepart

numero

guide

villetpmoy

restaurant

nomadresse

hotels

nom

adresserueville

categorie

gerant

nom

prenom

note

<voyage><vol> <num> 19660128 </num> <trajet> <depart> Paris </depart> <arrivee> Berlin </depart> </trajet></vol><temperature> 18 </temperature><hotels>

<hotel> <nom> schönes Murmeltier </nom> <adresse> <rue> Mauerstrasse </rue> <ville> Berlin </ville> </adresse> </hotel> <hotel> <nom> grosser Pinguin </nom> <adresse> <rue> Lindestrasse </rue> <ville> Berlin </ville> </adresse> </hotel>

</hotels></voyage><voyage><vol> <num> 19760103 </num> ...

<voyage><vol> <num> 19660128 </num> <trajet> <depart> Paris </depart> <arrivee> Berlin </depart> </trajet></vol><temperature> 18 </temperature><hotels>

<hotel> <nom> schönes Murmeltier </nom> <adresse> <rue> Mauerstrasse </rue> <ville> Berlin </ville> </adresse> </hotel> <hotel> <nom> grosser Pinguin </nom> <adresse> <rue> Lindestrasse </rue> <ville> Berlin </ville> </adresse> </hotel>

</hotels></voyage><voyage><vol> <num> 19760103 </num> ...


ContexteIntégration de données

Evaluation de requêtesValidationOptimisationConclusion et perspectives

Plan

Intégration de données : Architecture de médiation

• Sources hétérogènes (adaptateurs)

• Sources distribuées (médiateurs)


Architecture de médiation

SGBDrelationnel

ApplicationSGBDobjet

SGBDSemi-Structuré

Agencede voyage

Chaînehôtelière

Horairedes vols

FichierstexteFichiers

texteFichiersHTML

InformationsPays

Météo

SQL

tuples OQLobjets

XQueryXML

Moteur derecherches textes API instances

?Médiateur

Adaptateur Adaptateur Adaptateur Adaptateur Adaptateur

SQLOQL

tuples objets APIinstancesMoteur

de recherche

textesXQuery

XML

langage commun de requêteformat de résultat commun


Architectures de médiation de données semi-structurées

Médiation avec modèle relationnelHermesAGORA/LeSelect, XPeranto, SilkRoute

Médiation avec modèle objetDIOM, MOMISIRO-DB, DISCO

Médiation avec modèle semi-structuréGARLIC, TSIMMIS, STRUDEL, YAT,MIX, Nimble, LiquidData


Architecture « Tout-XML »

Langage de requête : XQuery

Format du résultat : XML

Communication avec les adaptateurs : XML/DBC

Méta-données : XML-Schema

Formules et statistiques de coût : XML + MathML

Capacités : XML

Exécution de requêtes : XQuery + XML

Evaluation de requêtes : XAlgèbre

Structures internes : SAX, DOM, XTuple

Intégration de données hétérogènes : XML, Relationnel, Web


Architecture de médiation

SGBD-R

Adaptateur Adaptateur

Médiateur

Applicationutilisateur

Adaptateur

SGBD-SS

Pilote SGBD-R Pilote SGBD-SS Pilote Médiateur

Gestionnaire de pilotes XML/DBC

Analyseur

Métadonnées

Recomposeur

Générateur deplans d’exécution

Gestionnairede coûts

Métadonnées

Gestionnairede coûts

XQuery

StructureXQuery

XAlgèbre XAlgèbre XAlgèbre

executeQuery(XQuery)executeQuery(XQuery)executeQuery(XQuery)

SQL XPath XQueryTuples XML XML

XML XML XML

XTuple

XTuple XTupleXTuple

XML

Gestionnairede capacités


ContexteIntégration de donnéesEvaluation de requêtes

ValidationOptimisationConclusion et perspectives

Plan

Evaluation de requêtes• Construction d'un plan d'exécution (XAlgèbre)

• Evaluation


Évaluation de requêtes distribuées semi-structurées

Intégration de données Analyse de la requête Création du plan d’exécution

identification des opérations à réaliser localisation des sources optimisation

Évaluation et recomposition des résultatsCas des données semi-structurées Restructuration Objets multi-valués Composition de graphes

Construction de l’arbre algébrique


for $v in Collection ("*")/volsfor $g in Collection ("*")/guide where $v/temps < 4and $v/trajet/arrivee = $g/villereturn<voyage> <vol> <num> {$v/numero} </num> <trajet> {$v/trajet} </trajet> </vol> <temperature> {$g/tpmoy} </temperature> <hotels> { for $h in Collection ("*")/hotels where $h/categorie = "5" and $v/trajet/arrivee = $h/adresse/ville return <hotel> <nom> {$h/nom} </nom> <adresse> {$h/adresse} </adresse> </hotel> } </hotels></voyage>

let t1 := for $v in Collection ("*")/volsfor $g in Collection ("*")/guide where $v/temps < 4and $v/trajet/arrivee = $g/villereturn ($v/numero, $v/trajet, $v/trajet/arrivee, $g/tpmoy)

let t2 := for $v in $t1 for $h in Collection ("*")/hotels where $h/categorie = "5« and $t1/trajet/arrivee = $h/adresse/villereturn ($h/nom, $h/adresse, $h/adresse/ville)

<voyage> <vol> <num> {$v/numero} </num> <trajet> {$v/trajet} </trajet> </vol> <temperature> {$g/tpmoy} </temperature> <hotels> <hotel> <nom> {$h/nom} </nom> <adresse> {$h/adresse} </adresse> </hotel> </hotels></voyage>

Req

. élé

men

t. 2

Rec

onst

ruct

ion

Req

. élé

men

t. 1

Construction du plan d’exécution

for $v in Collection ("*")/volswhere $v/temps < 4return ($v/numero, $v/trajet, $v/trajet/arrivee)

for $g in Collection ("*")/guidereturn ($g/tpmoy)

for $h in Collection ("*")/hotelswhere $h/categorie = "5 " return ($h/nom, $h/adresse, $h/adresse/ville)

$v/trajet/arrivee = $g/ville

for $v in $t1return ($t1/trajet/arrivee )

$t1/trajet/arrivee = $h/adresse/ville

Atom. 1.1

Atom. 1.2

Atom. 2.1

Atom. 2.2

Recomp. 1

Recomp. 2 <voyage> <vol> <num> {$v/numero} </num> <trajet> {$v/trajet} </trajet> </vol> <temperature> {$g/tpmoy} </temperature> <hotels> <hotel> <nom> {$h/nom} </nom> <adresse> {$h/adresse} </adresse> </hotel> </hotels></voyage>

Reconstruction

S1

S2

S1, S3

for $v in volswhere $v/temps < 4return ($v/numero, $v/trajet, $v/trajet/arrivee)

for $g in guidereturn ($g/tpmoy)



for $h in hotelswhere $h/categorie = "5 " return ($h/nom, $h/adresse, $h/adresse/ville)


U

Résultat


S1 S2

S3 S1

for $v in volswhere $v/temps < 4return ($v/numero, $v/trajet, $v/trajet/arrivee)

for $g in guidereturn ($g/tpmoy)





U

Résultat


S1S2

S1S3

Normalisation Suppression des affectations

(clauses « LET ») Canonisation

Désimbrication des requêtes imbriquées

Atomisation Séparation des collections

Identification des sources Identification des sources gérant

chaque collection Création du plan d’exécution

Transformation en un arbre algébrique

Optimisation du plan d’exécution Optimisation de l’arbre algébrique

Normalisation Suppression des affectations

(clauses « LET ») Canonisation

Désimbrication des requêtes imbriquées

Atomisation Séparation des collections

Identification des sources Identification des sources gérant

chaque collection Création du plan d’exécution

Transformation en un arbre algébrique

Optimisation du plan d’exécution Optimisation de l’arbre algébrique


Algèbre

BesoinsRecherche de cheminFiltrageConstruction XMLPuissance d’interrogationSupport pour un typage flexibleSupport pour l’optimisation

Type d’algèbreExtension de l’algèbre classique : IBM, NIAGARA, TAX,

YATTransformation en algèbre relationnelle : AGORAEvaluation sémantique par boucles : AT&T

Répond aux mêmescritères que le langage de requête


bar

nom

adresse

rue

ville

boisson

boisson

L'Envol

Lacépède

Paris

Maple Kiss

Gin Tonic

telephone

bar

nom

adresse

Le Frog's

0143407071


bar

nom

adresse

rue

ville

boisson

boisson

L'Envol

Lacépède

Paris

Maple Kiss

Gin Tonic

telephone

bar

nom

adresse

Le Frog's

0143407071


bar

nom

adresse

rue

ville

L'Envol

Lacépède

Paris

bar

nom

adresse

Le Frog's


bar

nom

adresse

rue

ville

boisson

boisson

L'Envol

Lacépède

Paris

Maple Kiss

Gin Tonic

telephone

bar

nom

adresse

Le Frog's

0143407071


bar/

adre

sse/

rue

bar/

adre

sse/

ville

L’Envol Lacépède Paris Maple Kiss

Gin TonicLe Frog’s 0143407071 25, cour Saint-Emilion Paris

bar/

nom

bar/

adre

sse

bar/

bois

son

bar/

tele

phon

e

bar

nom

adresse

rue

ville

L'Envol

Lacépède

Paris

bar

nom

adresse

Le Frog's


bar

nom

adresse

rue

ville

boisson

boisson

L'Envol

Lacépède

Paris

Maple Kiss

Gin Tonic

telephone

bar

nom

adresse

Le Frog's

0143407071


bar/

nom

bar/

adre

sse

bar/

adre

sse/

rue

bar/

bois

son

bar/

adre

sse/

ville

bar/

tele

phon

e

bar

bar

nom

adresse

rue

ville

boisson

boisson

L'Envol

Lacépède

Paris

Maple Kiss

Gin Tonic

telephone

bar

nom

adresse

Le Frog's

0143407071


bar

nom

adresse

rue

ville

L'Envol

Lacépède

Paris

bar

nom

adresse

Le Frog's


bar/

nom

bar/

adre

sse

bar

« Projection sur le nom et l’adresse de chaque bar. »

•Opération directe sur arbres

•Transformation en tableau et opération relationnelle sur table

•Pb : coût de navigation

•Pb: coût de construction du tableau et la reconstruction de l’arbre

•Conservation de l’arbre et peu de navigation

Xtuples : motivations

•Référencement dans un tableau et opération relationnelle surtable ET évaluation en flux


XTuples : définition

Un XTuple est composé de 1. un ensemble d’arbre A2. un ensemble de références R

sur A.Ces références sont appelées

XAttributs. 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

bA

C

ac

edB

f

E

g h

iD

F

j

a/b a/c f/h/i f/g

bG

I

ac

edH

f

K

g h

iJ

L

j

AR


Evaluation en flux

Les documents XML sont remontés sous forme de flux d’évènements (SAX).

Les XTuples sont construits au vol sur les flux.

Les XOpérateurs (s’ils ne sont pas bloquants) traitent les XTuples au fur et à mesure.

Les XOpérateurs N-aire parallélisent les différents flux de XTuples d’entrées.


T1a/ba

Projection sur a et a/b

Evaluation en flux

T1a/ba

<a> x1 <c> <d>y1</d> <e>z1</e> <f>t1</f> <c> <d>u1</d> <a>

<a> x <c> <d>y</d> <e>z</e> <f>t</f> <c> <d>u</d> <a>


Requête X sur source S1

références a, a/b et a/c <a>

x <c> <d>y</d> <e>z</e> <f>t</f> <c> <d>u</d> <a>


<a> x <c> <d>y</d> <e>z</e> <f>t</f> <c> <d>u</d> <a>



<a> x2 <c> <d>y2</d> <e>z2</e> <f>t2</f> <c> <d>u</d> <a>

XSource XProject

a/c


Arbre algébrique

for $v in Collection ("*")/volswhere $v/temps < 4return<voyage> <vol> <num>$v/num</num> <trajet>$v/trajet</trajet> </vol> <hotels> for $h in Collection ("*")/hotels where $h/categorie="5" and $v/trajet/arrivee=$h/adresse/ville return <hotel> <nom>$h/nom</nom> <adresse>$h/adresse</adresse> </hotel> </hotels></voyage>

for $v in Collection ("*")/volswhere $v/temps < 4return<voyage> <vol> <num>$v/num</num> <trajet>$v/trajet</trajet> </vol> <hotels> for $h in Collection ("*")/hotels where $h/categorie="5" and $v/trajet/arrivee=$h/adresse/ville return <hotel> <nom>$h/nom</nom> <adresse>$h/adresse</adresse> </hotel> </hotels></voyage>

($v/temps, $v/num,$v/trajet, $v/trajet/arrivee)

($v/temps, $v/num,$v/trajet, $v/trajet/arrivee)

($h/categorie, $h/adresse/ville,$h/nom, $h/adresse)

($h/categorie, $h/adresse/ville,$h/nom, $h/adresse)

($h/adresse/ville,$h/nom, $h/adresse)

($v/temps, $v/num,$v/trajet, $v/trajet/arrivee ,($h/adresse/ville,$h/nom, $h/adresse))

($v/num,$v/trajet, ($h/nom, $h/adresse))

XSource

XSource

vols

hotels

$v/temps<4 $h/categorie="5"

$v/trajet/arrivee=$h/adresse/ville


XMin

a b cg

XOpérateurs

XSource Opérateurs relationnels

XProjection XRestriction XJointure

Opérateurs ensemblistes XUnion XIntersection XDifférence

Tris XOrder-By

Agrégats XMin XMax XCount

XReconstruction

XRestriction

a b ca b c

XProjection

b ca b c

a b c

XSource<SAX/>

XJointurea b c

d e f a b c d eTri

a b c a b c

XReconstruct

a b c

<SAX/>

a b c

XUnion

a b c a b c


ContexteIntégration de donnéesÉvaluation de requêtesValidation

OptimisationConclusion et perspectives

Plan

Validation• Prototypes (projets MIROWEB, XML-KM et MUSE)

• Cas d'utilisation (use-case du XQuery Working Group)

• Performance (benchmark TPC-R adapté)


Evaluation (1/2)

Temps d’exécution en millisecondes en fonction du nombre de documents résultat sur différentes étapes

Rapport des temps médiateur et adaptateur

Coût de communication

1400

1200

1000

nombre de documents résultats

tem

ps (

en m

s)

800

600

400

200

0

0 500 1000 1500 2000 2500 3000

TotalEval_Med

InitWrapper

rapp

ort d

es te

mps

0 500 1000 1500 2000 2500 3000


0

1

2

3

4

5

6

7

8

9Rapport

M1

A1

col1col1S1


Evaluation (2/2)

Jointure inter-sites

Algorithmes de jointures à optimiserTemps de communication dominant


tem

ps (

en m

s)

60000

50000

40000

30000

20000

10000

00 1000 2000 3000 4000 5000 6000 7000

Médiateur M2Médiateur M2

S1 S2

col1col1 col2col2

M2

A1 A2

S3

col2col2col1col1

M3

A3


ContexteIntégration de donnéesEvaluation de requêtesValidationOptimisation

Conclusion et perspectives

Plan

Optimisation• Evaluation des performances (modèle de coût)

• Réutilisation des résultats (cache sémantique)

• Prise en compte des limitations des sources


Modèle de coût

Coût d’une architecture de médiation Calibration [PEGASUS] pour données objet [IRO-DB]

requêtes types pour calibrer paramètres de la source Historique [HERMES]

s’appuie sur les statistiques des requêtes précédentes Défini par les adaptateurs [GARLIC]

défini séparément pour chaque adaptateur + coût par défaut Générique [DISCO]

intégrer coût des adaptateurs + coût par défaut + hiérarchie de coût

Coût sur données semi-structurées Coût sur modèle semi-structuré dans un entrepôt [LORE]

Modèle de coût générique + adaptation au semi-structuré coût des XOpérateurs langage de coût en XML


Langage de communication de coût

Communication du coût entre l'adaptateur et le médiateur

Basé sur XML Utilise le format

mathématique MathML

ma_var2 := MA_VAR1 + ma_fonction (ES, 36)ma_var2 := MA_VAR1 + ma_fonction (ES, 36)

<cost-model>

...<math xmlns="http://www.w3.org/1998/Math/MathML">

<declare type="real"> <ci> ma_var2 </ci> <apply> <plus> <ci> MA_VAR1 </ci> <apply> <ci> ma_fonction </ci> <ci> ES </ci> <cn> 36 </cn> </apply> </plus> </apply></declare></math>

...

<cost-model>

...<math xmlns="http://www.w3.org/1998/Math/MathML">

<declare type="real"> <ci> ma_var2 </ci> <apply> <plus> <ci> MA_VAR1 </ci> <apply> <ci> ma_fonction </ci> <ci> ES </ci> <cn> 36 </cn> </apply> </plus> </apply></declare></math>

...

Adapté au semi-structuréProfondeur des arbresTemps de référencement

d’un noeud filsNombre de fils moyen

par noeuds


Cache sémantique

Garder un historique des prédicats de requêtes déjà posées.requête dans le cache localrequête complémentaireactualiser le cache

Utiliser un SGBD semi-structuré natif comme cachePDOM, NatiX, Tamino, ReposiXidentifiants uniques d’éléments

a/b a/b/c

ab

c de

ab

c de

Contenance des chemins

date > 1976date > 1966

Contenance des prédicats


Langage de description des capacités d’interrogation <ruleset>

<rule num="10"> <permission> allow </permission> <relationalop> scan </relationalop> </rule> <rule num="100"> <permission> allow </permission> <relationalop> select </relationalop> <collection1>

<hotel><categorie></categorie></hotel></collection1>

<operator> less </operator> </rule> <rule num="200"> <permission> deny </permission> <relationalop> select </relationalop> </rule> <rule num= "300"> <permission> allow </permission> <relationalop> project </relationalop> <collection1> voiture </collection1> </rule> <rule num="65535"> <permission> deny </permission> </rule></ruleset>

<ruleset> <rule num="10"> <permission> allow </permission> <relationalop> scan </relationalop> </rule> <rule num="100"> <permission> allow </permission> <relationalop> select </relationalop> <collection1>



num perm operat coll att comp coll att

10 allow scan

100 allow select hotel categorie less

200 deny select

300 allow project hotel

65535 deny

Sources de capacités d’interrogation différentes

Adaptateur peut pallier certaines déficiences de la source

Le médiateur pallie les déficiences de l’adaptateur+source


ContexteIntégration de donnéesÉvaluation de requêtesValidationOptimisationConclusion et perspectives

Plan

Conclusion et perspectives• Synthèse & Contributions

• Perspectives


Synthèse & contributions

Architecture « Tout-XML » respecte les standards XML au maximum évolutivité et modularité

XAlgèbre : définition et évaluationExtension de l’algèbre relationnelle : simplePhase de compilation + Évaluation en flux

Module d’optimisationmodèle de coût + langage d’exportation cache sémantique en utilisant un SGBD natif XML

Extensions langage d’exportation de capacité adaptation de TPC-R à un contexte distribué hétérogène


Perspectives

Optimisation des plans d’exécution trouver des règles d’équivalence sur l’algèbre générateur de plans d’exécution implémentation de meilleurs algorithmes pour les XOpérateurs requête paramétrée indicateurs (hints) intégrer la gestion des capacités dans la construction des plans

d’exécution Modules d’optimisation

compression des données échangées modèle de coût cache sémantique indexation des données

Extensions intégration de fonctions externes : pour intégrer des sources multimédia utilisation du web sémantique

Questions ?

Annexes

BibliographieXLive

Use-cases

PublicationsFlux SAX et arbre DOM

PrototypesEvolution technique

Métadonnées

Formules de coût

XQuery

XOpérateurs

Cache

Banc d’essai

XTuple

Exportation plan d’exécution


Publications (1/3)

Projet MIROWEB G. Gardarin, F. Sha, T.-T. Dang-Ngoc, « XML-based Components for

Federating Multiple Heterogeneous Data Sources. » ER 1999: 506-519 L. Bouganim, T. Chan-Sine-Ying, T.-T. Dang-Ngoc, J.-L. Darroux, G.

Gardarin, F. Sha, « Miro Web: Integrating Multiple Data Sources through Semistructured Data Types. » VLDB 1999: 750-753

T.-T. Dang-Ngoc (Osis/PRiSM), D. Artal (Osis), C. Campanaro (Osis), P. Kirkham (Osis), H. Laude (Osis), A. Vuillier (Osis), « Integration Plan (ESPRIT-25208 Deliverable D3-1-2) », 1998

T.T. Dang-Ngoc (Osis/PRiSM), T. Chan-Sine-Ying (PRiSM), F. Chéron (Osis), G. Gardarin (PRiSM), P. Kirkham (Osis), H. Laude (Osis), « Browser Interface Specification (ESPRIT-25208 Deliverable D6-2-1) », 1998

T. Chan-Sine-Ying (PRiSM), T.T. Dang-Ngoc (Osis/PRiSM), D. Florescu (Inria), C. Campanaro (Osis), P. Kirkham (Osis), « Message Manager Specification (ESPRIT-25208 Deliverable D5-1-1) », 1998


Publications (2/3)

Projet XML-KM T.-T. Dang-Ngoc, G. Gardarin, « The XML Mediator. »

Document technique interne à e-XMLMedia, 26p.

Projet MUSE T.-S. Yeh, T.T. Dang-Ngoc, « Repository de méta-données

(RNTL Specification SP-3) », 2001 G. Gardarin, A. Mensch, T.-T. Dang-Ngoc, L. Smit,

« Integrating Heterogeneous Data Sources with XML and XQuery. » DEXA Workshops 2002: 839-846


Publications (3/3)

En cours de soumission T.T. Dang-Ngoc, G. Gardarin « Evaluating XQuery in a full-

XML Mediation architecture » Soumis à BDA’2003 T.T. Dang-Ngoc, G. Gardarin « Integrating Heterogeneous

Data Sources » En cours de soumission à IASTED 2003 T.T. Dang-Ngoc, G. Gardarin « Architecture de médiation

"Tout-XML". » En cours de soumission à la revue ISI (Integration de systèmes d'information)

T.T. Dans-Ngoc, H. Kouh, G. Gardarin « Semantic Integration and XML Mediation For Web Information Search » En cours d'écriture pour WIDM’2003


Mise en oeuvre (1/3)

MIROWEB (médiateur v0) Lab. PRiSM + SSII OsisEcriture d’un analyseur XML-QL Implémentation d’un médiateur simple basé sur une mise à

plat des documents OEMFormation de document XML résultat Implémentation d’un adaptateur SQLX sur repository

OEM et d’un adaptateur SQL sur oracle avec pour langage commun OEM

Création d’un mini-dataguideProtocole d’envoi de message entre médiateur et interface

client par socket et RMIConception d’une interface graphique cliente



XML-KM (médiateur v1) lab. PRiSM puis éditeur e-XMLMédia

Conception et implémentation d’un médiateur basé sur des documents OEM utilisant un mécanisme d’association (« binding ») sur variable.

Reprise de l’analyseur XML-QL de MIROWEBPrise en charge simple de déficience de capacité de traitement des

adaptateursCréation d’une base de méta-donnéesFormation de document XML résultat Implémentation d’un adaptateur SQLX sur repository OEM et

d’un adaptateur SQL sur oracle avec pour langage commun XMLConception d’une première version d’interface graphique

d’administration simple.



MUSE (médiateur v2) Lab. PRiSM + éditeur e-XMLMédiaConception et implémentation d’un médiateur basé sur des

documents XML utilisant la XAlgèbra.Conception et implémentation de la XAlgèbraConception et implémentation d’un gestionnaire de

métadonnées utilisant des XML-Schéma et différents index

Création d’un adaptateur XML/DBC pour le médiateur.Participation aux spécifications d’un repository natif XML

: ReposiX et implémentation d’un module d’indexation.


XTuplesReference Part ( R )

Tree Part ( T )

XAttributes

Tree

person

addressstreet town

nameBruce Wayne

lastname

Gotham17

nameBatman

person

addressstreet town

nameLois Lane

lastname

Metropolis28

person

addressstreet town

nameParker

New York121

nameSpiderman

person

addressstreet town

nameClark Kent

lastname

Metropolis42

nameSuperman

pers

on/n

ame

pers

on/a

ddr

ess

pers

on/l

astn

ame

car/

colo

r

car

bluecolor

657age

car

bluecolor

1age

car

bluecolor

4age

car

bluecolor

13age


XOpérateurs (1/3)

XSource construction XAttribut construction forêt ordre de la source non-bloquant

a b c

XSource

XProjection destruction de colonnes destruction de (sous-)arbres ordre préservé non-bloquant

XRestrictiondestruction de lignes

complète ordre préservé

non bloquant

XProjection

b ca b c

XRestriction

a b ca b c

<SAX/>


XOpérateurs (2/3)

XUnion ordre préservé en mode

bloquant, non préservé sinon bloquant ou non suivant

paramétrage

XJointure ajout de colonnes ajout/concaténation

d’arbresordre préservé en

mode bloquant, non préservé sinon

bloquant ou non suivant paramétrage

XJointurea b c

a b c

XUnion

d e f a b c d e

a b c a b c


XOpérateurs (3/3)

Tri (XSORT-BY)

déplacement de lignes complètes

bloquant Fonction d’agrégat

(Xmin, Xmax, Xcount)

nouvelle colonne (1 ligne)

nouveau arbre d’un noeud

bloquant

Tri

a b c a b c

Agrégat

a b cg

XReconstruct génération d’un flux

SAX résultat A partir d’une requête de

reconstruction

XReconstruct

a b c

<SAX/>


XProjection


XJointure


XProduit


XNest


XLive (XML Light Integration Virtual Engine)

WEBOracle 9i

SOAP

Oracle 9i wrapper

XPlan generator

Flow evaluation

XQuery

XQuery internal structure

XQuery

XML

SAX event flow

SAX event flow

oracle XDB

Presentation

XML

XPlan optimizer

GUI HTML

XSL

Cache

XAlgebraMetadata manager

Connection manager

Cost manager

Capability manager

XQuery parser

Indexation

XM

L N

ativ

e D

atab

ase

XQuery

SOAP

Web wrapper

XMLXQueryXMLXQuery

SOAP

Web wrapper

XML-Schema

HTML HTMLGET, POST GET, POSTSO

UR

CE

ME

DIA

TO

RU

SE

R


Evolution technique XML

parse XML -> DOM -> SAXSQLX -> XML-QL -> XQuerydataguide, DTD -> XML-SchemaOEM -> XMLsocket -> RMI -> SOAP


Use-cases

domaine description numéro de requêtes1 XMP exemples généraux 1 2 3 4 5 6 7 8 9 10 11

122 TREE préservant la hiérarchie 1 2 3 4 5 63 SEQ basées sur les séquences 1 2 3 4 54 R accès aux données relationnelles 1 2 3 4 5 6 7 8 9 10 11

12 13 14 15 16 17 185 SGML basé sur tests SGML 1 2 3 4 5 6 7 8 9 106 STRING recherche de chaîne de caractères 1 2 3 4 5 67 NS utilisant les espaces de noms 1 2 3 4 5 6 7 88 PARTS récursivité et références externes 19 STRONG utilisant des données fortement

typées1 2 3 4 5 6 7 8 9 10 11 12

traiténon-traité


Métadonnées (1/2)


Métadonnées (2/2)


Bancs d’essai (1/2)

M4

A7

M2 M3

M1

A1 A3 A4 A5 A6A2

(a)

M0

A1 A3 A4 A5 A6A2

(b)

(c)


Banc d’essai (2/2)


Exportation du plan d’exécution

en XML...pour garder des

requêtes « compilées »

pour interroger un adaptateur avec un autre (ex. pour jointure inter-site)

<pl:plan> <pl:xrecompose> <pl:param> <hotel> <name>$h/nom</name> <adresse>$h/adresse</> </hotel> </pl:param> <pl:xrestrict> <pl:constraint> <pl:left>$h/category</>[...]

<pl:plan> <pl:xrecompose> <pl:param> <hotel> <name>$h/nom</name> <adresse>$h/adresse</> </hotel> </pl:param> <pl:xrestrict> <pl:constraint> <pl:left>$h/category</>[...]

W W

M


LAV/GAV

Schéma fédéré

Base de données« vue universelle »

vue complexe, multi-relation qui transforme les sources et combine les informations processeur de requêtes LAV

Profil de la source

Profil de la source


Compression

Pour gagner en temps de communication Compression par blocs Compression par chemins [...]

<a> b1 <c> <d>d1</d> </c></a><a> b2 <c> <d>d2</d> </c></a><a> b3 [...]

<a> b5 <c> <d> d5 </d> </c></a><a> b6 <c> <d> d6 </d> </c></a>






[...]a/b : 1a/c/d : 2

a/b : 1a/c/d : 2

1 : b12 : d1/1 : b22 : d2/1 : b32 : d3

1 : b12 : d1/1 : b22 : d2/1 : b32 : d3


Réplication

Utilisation de deux sources identiques ou partielles pour aller plus viteMises à jour Information au générateur de

plan d’exécutionPeer-to-peer (information sur

les voisins, répartition, sources tombant en panne)

Pour gérer des sources tombant en panne

Médiateur

Adaptateur Adaptateur

S1 S1


Langages d’interrogation

Besoins : Opérateurs standards de requêtes sur bases de données Navigation dans les données Recherche par motifs Interrogation du schéma et des données Construction du résultat

Type de langages Extension de langages classiques : SGMLQL, HyOQL, LOREL/OEM-QL Conçus pour le semi-structuré : XML-QL, XQL, QUILT Normalisation : XPath, XQuery

XQuery FLWRExpr ::= (ForClause | LetClause)+ WhereClause? "return" Expr ForClause ::= "for" Variable "in" Expr ("," Variable "in" Expr)* LetClause ::= "let" Variable ":=" Expr ("," Variable ":=" Expr)* WhereClause ::= "where" Expr


Gestion de vues et trigger

Gestion de vues matérialisée.

Mise à jour par déclencheurs (trigger) actifs /passifs

Utilisation de cache pour vues matérialisées sous la forme d’un SGBD XML natif

WebSite

WebLoader

WebWarehouse

SEWISE

ViewManager

XQuery Processor

XML Warehouse

Coordinator

WebClient

XQuery XML

Web

Logger

OK OK


Document XML – Flux SAX – Arbre DOM

<personne> <nom> Cover </nom> <prenom> Harry </prenom> <adresse> <rue> Stendhal </rue> <ville> Paris </ville> </adresse></personne>

personnenom

prenom

adresserue

ville

#text: Cover

#text: Paris

#text: Stendhal

#text: Harry

startDocument ()startElement (personne)startElement (nom)characters (Cover)endElement (nom)startElement (prenom)characters (Harry)endElement (prenom)startElement (adresse)startElement (rue)characters (Stendhal)endElement (rue)startElement (ville)characters (Paris)endElement (ville)endElement (adresse)endElement (personne)endDocument ()


Intégration du cache

id3 id4 id8

id2 id9

id2 id10

Base d’histo-rique

Entrepôtnatif de donnéessemi-struc-turées

Mémoire secondaire

…

…

id3id4

Source

Adaptateur

Evaluateur du médiateur

CA

CH

E

a/b a/b/c

ab

c de

ab

c de

Contenance des chemins

date > 1976date > 1966

Contenance des prédicats


Modèle de coût pour médiation de données semi-structurées (1/2)

Modèle de coût générique + adaptation au semi-structuré Intégration du modèle de coût communiqué par les

adaptateursModèle de coûts suivant des formules et statistiques

communiquéesmodèle de coût par défauthiérarchie des coûts

Modèle de coût au niveau du médiateurFormule de coût des XOpérateurs

coût d’un opérateur XSourcecoût = coût_source + communication + construction_XTuple


Coût des Xopérateurs (2/2)

coût d’un opérateur autre que XSourcecoût= coûts_fils + coût_opoù coûts_fils [max (coût_filsi), (coût_filsi)suivant le degré de parallélisme

Due à la structure des XTuples, le coût d’un XOpérateur est celui de l’opérateur relationnel plus un éventuel coût de manipulation sur les arbres

Exécution d'un XOpérateurphase de pré-compilation (effectuée une seule fois)phase d'exécution (effectuée pour chaque XTuple)

XOpérateur

fils1 …filsn


Bibliographie (1/2)

Données semi-structurées [Abiteboul1997] S. Abiteboul. Querying Semistructured Data. In proc of

the 6th Intl. Conf. on Database Theory, 1997

Architecture de médiation [Wierderhold1992] G. Wiederhold. Mediator in the Architecture of Future

Information System. Computer, 25 (3), 1992

Algèbre XML [Beech et al.1999] D. Beech, A. Malhotra, et M. Rys. A Formal Data Model

and Algebra for XML. 1999. [McHugh et Widom1999] J. McHugh, S. Abiteboul, R. Goldman, D. Quass,

et J. Widom. LORE: A Database Management System for Semistructured Data. SIGMOD Record, 26(3):54-66, 1997.

[Fernandez et al.2001] M. Fernandez, J. Simeon, et P. Walder. A Semi-Monad for Semi-structured Data. In International Conference on Database Theory, Janvier 2001.


Bibliographie (2/2)

Modèles de coût calibration [Du1992] W. Du, R. Krishnamurthy, et M.-C. Shan. Query

optimization in a heterogeneous DBMS. In proc. VLDB, 1992. historique [Adali1996] S. Adali, K. Candan, et Y. Papakonstantinou. Query

Caching and Optimization in Distributed Mediator Systems. In ACM SIGMOD, 1996.

par adaptateur [Haas1997] L.M. Haas, D. Kossmann, E.L. Wimmers, et J. Yang. Optimizing Queries Across Diverse DataSources. In VLDB, 1997.

générique [Naacke1998] H. Naacke, G. Gardarin, et A. Tomasic. Leveraging Mediator Cost Models with Heterogeneous Data Sources. In ICDE, 1998.

semi-structuré [Widom1999] J. McHugh et J. Widom. Query Optimization for XML. In proc. VLDB, 1999.

Caches sémantique [Adali1996] S. Adali, K. Candan, et Y. Papakonstantinou. Query Caching

and Optimization in Distributed Mediator Systems. In ACM SIGMOD, 1996.

Transparents supprimés


Cas d’utilisation et bancs d’essai

Prototype projet ESPRIT MIROWEB projet ESPRIT XML-KM projet RNTL MUSE

Tous ont inclus le médiateur sous différentes versions. Cas d’utilisation

Parmi les cas d’utilisation proposés par le W3C, tout ceux spécifiques à l’orientation actuelle du médiateur sont évalués correctement (requêtes sur SGBD relationnels, médiation de différentes sources)

Bancs d’essaiAdaptation de TPC-R à un modèle distribué et hétérogène

dont semi-structuréPremières mesures de performances encourageantes

version 0 : XML-QLversion 0 : XML-QL

version 1 : XML-QLversion 1 : XML-QL

version 2 : XQueryversion 2 : XQuery


Modèle de coût

Coût d’une architecture de médiation Calibration [PEGASUS]

requêtes types pour calibrer paramètres de la source affinée avec échantillonnage pour données objets [IRO-DB]

Historique [HERMES] s’appuie sur les statistiques des requêtes précédentes

Défini par les adaptateurs [GARLIC] modèle de coût défini séparément pour chaque adaptateur et coût par

défaut pour coût manquant d’un adaptateur Générique [DISCO]

intégrer modèle de coût des adaptateurs + hiérarchie de coût et coût par défaut pour coût manquant d’un adaptateur

Coût sur données semi-structurées Coût sur modèle semi-structuré dans un entrepôt [LORE]


Cache sémantique

Garder un historique des prédicats de requêtes déjà posées.requête dans le cache localrequête complémentaireactualiser le cache

Utiliser un SGBD semi-structuré natif comme cachePDOM, NatiX, Tamino, ReposiXidentifiants unique d’élément

cache = Rsource = Ø

cache = Rsource = R – Rc

cache = Øsource = R

date > 1976 and date < 1980


date > 2002



Prise en compte des capacités d’interrogation des sources

Source de capacité d’interrogation différentesEx. SGBD-R: requête complexes, mises à jours, etc.Ex. Page web ou moteur de recherche : possibilité

d’interrogation limitée (formulaire) Adaptateur peut pallier certaines déficiences de la

source complexe pour les développeurs d’adaptateurs

Le médiateur pallie les déficiences de l’adaptateur+source prise en compte dans la création du plan d’exécution prise en compte dans le calcul du modèle de coût et le choix

du plan optimal


Langage de description des capacités d’interrogation

Basé sur XML Règles ordonnées Permissions par défaut :

autorisation ou interdiction







num perm operat coll att comp coll att

10 allow scan

100 allow select hotel categorie less

200 deny select

300 allow project hotel

65535 deny


tenancier

« Wild Geese »

nom établissementenseigne

« Joe »

Xtuples : motivations

tenanciernom etablissement

enseigne« Le Falstaff »

« John »

$t/nom $t/etablissement/enseigne

« Joe » « Wild Geese »

« John » « Le Falstaff »

tenancier

« Wild Geese »


« Joe »

tenancieretablissement


« John »

tenancier

« Wild Geese »


« Joe »



« John »

tenancier

« Wild Geese »


« Joe »



« John »

$t/nom $t/etablissement/enseigne

« Projection sur les enseignes desétablissements gérés par chaquetenancier. »

•Opération directe sur arbres

•Transformation en tableau etopération relationnelle surtable

•Référencement dans un tableauet opération relationnelle surtable ET évaluation en flux

•Pb : coût de navigation

•Pb: coût de construction du tableau et la reconstruction de l’arbre

tenancier

« Wild Geese »


« Joe »



« John »

•Conservation de l’arbre et peu de navigation

Documents

Fédération de données semi-structurées avec XML Tuyêt Trâm DANG NGOC Laboratoire PRiSM Université de Versailles-Saint-Quentin Présentation du Mardi 10