Subsumption for XML Types DEA SIR Signe Carlsen Le 27 Mars 2001

Subsumption for XML Types

DEA SIRSigne Carlsen

Le 27 Mars 2001

2Présentation Subsumption27/03/01

Sommaire

I - Introduction

II - Assignation de types à des données XML

III - Mécanisme de « subsumption »

IV - Utilisation du « Greatest Lower Bound »

V - Exemple d’application du mécanisme de « subsumption »

VI - Conclusion


I - Introduction

• De plus en plus d’applications intranet/internet intégrant des données hétérogènes venant de sources diverses

• Nécessité d’établir des liens entre les différents types de données XML pour pouvoir accéder à des informations du même genre venant de sources différentes – Exemple : site présentant les catalogues de téléphones portables de diverses entreprises

• La « subsumption » répond au problème :– Relation entre les types XML– Stockage d’informations optimisé– Requêtes facilitées


Exemple : documents XML du site


II - Assignation de types à des données XML (1/4)

• Modèle de données XML– Structure d’arbre où les nœuds possèdent des identifiants, des labels et éventuellement des

nœuds fils (voir figure1)

• Systèmes de types (ou schémas)– Possèdent également une structure d’arbre où les nœuds ont des noms de types, des labels et

éventuellement des nœuds fils (voir figure1)

• Assignation des types d ’un schéma aux données d ’un modèle de données XML– Se fait avec une fonction qui à chaque nœud de l’arbre du modèle de données fait

correspondre un nom de type du schéma



Figure 1





• Exemple d ’assignation en prenant les données du premier arbre et les types du deuxième arbre de la figure1 :

(o1) = HpJammer

(o11) = J11

(o13) = J13

(o132) = J132

(o14) = J14

(o141) = J141

etc.


III - Mécanisme de « subsumption » (1/2)

• Établit une relation entre les types de deux schémas– A l’aide d’une fonction ’ - comme l’assignation de types - qui à chaque nom de type d’un

schéma S1 fait correspondre un nom de type d ’un autre schéma S2– Cette fonction obéit à certaines règles– Si ces règles sont respectées alors on dit que S1 subsume S2 à travers la « subsumption » ’

et on note S1 S2

• Une propriété de la « subsumption » : – Si il existe une assignation de type entre une base de données D et le schéma S1 et si S1

S2 à travers la « subsumption » ’ alors il existe une assignation de type o’ entre D et le schéma S2


III - Mécanisme de « subsumption » (2/2)

• Exemple de « subsumption » en prenant les types du deuxième arbre et les types du troisième arbre de la figure1 :

’(HpJammer) = Jammer

’(J11) = J ’11

’(J13) = J ’13

’(J111) = J ’111

’(J14) = Option

’(J141) = Any

etc.


IV - Utilisation du « Greatest Lower Bound » (1/2)

• Schéma décrivant le type d’information commune à deux schémas

• Ce schéma est obtenu en faisant l ’intersection entre deux schémas.

• Grâce au Greatest Lower Bound une optimisation de l ’exécution des requêtes est possible.

• Dans le typage des données XML il met en avant les attributs intervenant dans une requête, par exemple une requête portant sur la garantie du téléphone portable.

• A partir d’un schéma incluant le champ de la garantie warranty du téléphone portable on peut obtenir un nouveau schéma respectant le typage suivant :


IV - Utilisation du « Greatest Lower Bound » (2/2)

• Typage faisant apparaître l ’attribut lié à la garantie WarrantyOption ’ :

Warranty-Jammer := jammer [ ?Company ’, Name ’, Price ’,

*( WarrantyOption ’ | (OtherOption ’, ?Supplement ’) ) ] ;

Company ’ := company [ String ] ;

Name ’ := name [ String ] ;

Price ’ := price [ Int | onrequest ] ;

WarrantyOption ’ := warranty * Any ;

OtherOption ’ := ! warranty * Any ;

Supplement ’ := supplement [ Int ] ;


V - Exemple d’application du mécanisme de subsumption (1/3)

• On applique ce mécanisme à partir d’une requête et d’un schéma obtenu avec le « Greatest Lower Bound »

• Typage d ’une requête YATL :– Exemple : on cherche les portables dont la garantie dure un certain nombre d’années– Le typage de la requête serait :

p[$n, $w] := products * Jammer ;

Jammer := jammer [ *(Name | Warranty | Other) ] ;

Name := name * ($n : Any1) ;

Warranty := warranty * ($w : Any2) ;

Other := ! name ! warranty * Any ;

Any1 := true [Any *] ; Any2 := true [Any *] ;



• La « subsumption » ’ réalise une correspondance entre les types contenus dans le schéma de la requête et les types inclus dans le nouveau schéma obtenu avec le « Greatest Lower Bound » (voir 8) :

’(Warranty-Jammer) = Jammer

’(Name ’) = Name

’(WarrantyOption ’) = Warranty

’(Company ’) = Other

’(Price ’) = Other

’(OtherOption ’) = Other

etc.



• Ainsi on sait que les valeurs de $n sont celles des éléments de type Name ’ stockés dans le schéma du « Greatest Lower Bound »

• La « subsumption » ’ garde les relations avec les schémas d’origine

• Elle facilite l’exécution des requêtes par un stockage plus adapté (voir 8)

• Par conséquent, l’accès à l’information visée par la requête (ici la garantie) est plus rapide


VI - Conclusion

• Afin de mesurer l ’impact de la « subsumption » lors d ’évaluations de requêtes : application dans le contexte du système de conversion de données YAT

• Le typage dans XML suscite beaucoup d’intérêt auprès des chercheurs pour plusieurs raisons :– La formulation des requêtes (DataGuides)

– L’optimisation des requêtes (An algebra for XML)

– Le stockage de l’information (STORED)


Bibliographie

• Gabriel M. Kuper et Jerome Siméon, Subsumption for XML Types, Janvier 2001.

• S. Cluet, C. Delobel, J. Siméon et K. Smaga, Your mediators need data conversion!, Juin 1998.

• A. Deutsch, M. F. Fernandez et D. Suciu, Storing semistructured data with STORED, Juin 1999.

• V. Christophides, S. Cluet et J. Siméon, On wrapping query languages and efficient XML integration, Mai 2000.

• R. Goldman et J. Widom, DataGuides : Enabling Query Formulation and Optimization in Semistructured Databases, Aout 1997.

• Lien internet : http://www-db.research.bell-labs.com

Documents

Subsumption for XML Types DEA SIR Signe Carlsen Le 27 Mars 2001