View
111
Download
2
Category
Preview:
Citation preview
Relation de subsumptionentre
schémas de types
Données semi-structuréeset
typage de données
Au sommaire…
Introduction 1. Données semi-structurées 2. Modéliser des données semi-structurées 3. Subsumption entre schémas Conclusion Bibliographie
Introduction
Le Web : une base de données géante non structuréeComment concevoir un SGBD adapté au Web ?
Plus généralement : comment mutualiser des informations homogènes à partir de sources de données hétérogènes ?
Les SGBD standards ne supportent pas l’hétérogénéité…Il faut faire appel à des modèles plus flexibles qui s’adaptent à la forme des données plutôt que de l’imposer.
1. Données semi-structurées
Quelques définitions Quelques propriétés Quelques enjeux Et quelques problèmes !
Quelques définitions
Première définition : toute forme de données n’étant ni une base de données ni de la donnée brute…=> champ de définition large
Deuxième définition : toute forme de données possédant une structure implicite, non rattachée à un schéma=> données auto-descriptives
Exemples :=> page Web=> texte=> document XML
Quelques propriétés
Propriétés des données : => données auto-descriptives=> données hétérogènes
Propriétés de la structure :=> structure implicite=> structure irrégulière=> peu de contraintes
Confusion entre données et structure Pas de connaissances a priori de la structure
Quelques enjeux
Flexibilité de l’échange de données Intégration de données Gestion de l’hétérogénéité Système qui s’adapte aux données et non pas le contraire Augmentation des possibilités de requêtage
Définir des schémas de données Correspondance entre schémas
=> subsumption
Quelques problèmes
Les SGBD standard ne sont pas adaptés=> ne supportent pas l’hétérogénéité=> niveau de contrainte trop élevé=> structure explicite et régulière=> connaissance du schéma obligatoire
Comment modéliser les données semi-structurées ?
2. Modéliser des données semi-structurées
Modèle de données Modèle OEM Schéma de types Assignation de schémas
Modèle de données
Graphe étiqueté, orienté, avec un nœud racine=> arcs orientés et étiquetés=> un nœud racine unique=> presque un arbre
Exemple : description des personnages de la bande dessinée Astérix
personnage personnage personnage
nom
originedescription nom
origine
description nom
origine
description
cheveux taillecheveux
taillepoids
ami
ami
&1231 &1232 &1233
&11
&1
&12 &13
&111 &112 &113 &121 &122 &123 &131 &132 &133
&1131 &1132
BDAsterix
jaunes
Obelix CesarGaule Gaule Rome mince
petit bas de poitrine
roux à tresses
grand
Asterix
Figure 2 : graphe OEM
Modèle OEM
OEM : Object Exchange Model=> Tsimmis Project de Stanford
Modèle minimaliste permettant de représenter un grand nombre de formes de données, dont les BD standard
Nœuds = objets avec oid=> objets atomiques vs objets complexes=> o. atomiques : int, string, … = nœuds-feuilles=> o. complexes : {(étiquette,oid)} = nœuds-intermédiaires
Schéma de données (1/2)
Modèle simplifié=> nœud racine unique=> arcs orientés=> nœuds identifiés (oid) et étiquetés (sauf la racine)=> nœuds-références étiquetés avec « & »
O1 := personnage
O11 := nom O12 := origine O13 := description
O111 := «Astérix» O121 := «Gaule» O131 := cheveux O132 := taille
O1311 := «jaunes» O1312 := «petit»
Figure 2 : Schéma de données
O14 := &
O2 := «ami»
Schéma de données (2/2)
O ensemble infini d’oid et L ensemble d’étiquettes Une b.d. est une structure D=<OD, labelD, childrenD>
1. OD O2. labelD est un mapping de OD dans L3. childrenD est un mapping de OD{} dans i0OD
i; si labelD(o)=&, alors childrenD(o)OD
1
La structure obtenue en ne considérant pas les nœuds-références est un arbre
Retour à l’exemple
Schéma de types (1/2)
Exploiter la structure avec un système de typage des données=> notion d’objets typés
Utilisation d’un schéma de types pour décrire ce système=> prédicats sur les étiquettes=> expressions régulières sur les descendants
T1 := personnage
T11 := nom T12 := origine T13 := description
T111 := String O121 := «Gaule» T131 := cheveux T132 := taille
T1311 := String T1312 := String
Figure 3 : Schéma de types
T14 := &
T2 := «ami»
* ?
Schéma de types (2/2)
T ensemble infini de noms de types, P ensemble de prédicats sur les étiquettes fermé pour la disjonction (ou), la conjonction (et) et le complémentaire (not()).
L(R) langage défini par les expressions régulières sur T=>t, &t, (t1,t2), (t1|t2), t1*, t1?, etc.
Un schéma de types est une structure S=<TS,predicateS, regexpS> :1. TS sous-ensemble fini de T2. predicateS mapping de TS dans P, avec soit predicateS(t)={&} soit &predicateS(t)3. regexpS mapping de TS{} sur L(R)S, avec si predicateS(t)={&}, regexpS(t) est de la forme t1|t2|…|tn
Retour à l’exemple
Assignation de schéma (1/2)
Soient D une base de données et S un schéma de types D est de type S ssi il existe une fonction d’assignation
f : OD{} TS {} tq :1. f()= 2. Pour oOD, predicateS(f(o))=labelD(o)3. Pour oOD {}, avec childrenD(o)=[o1,..,on], f(o1),..,f(on)L(regexpS(f(o)))
Retour aux exemples
O23 := description
O231 := cheveux O232 := taille O233 := poids
O2331 := «bas de poitrine»O2321 := «grand»O2321 := «roux»
T23 := description
T231 := cheveuxT232 := taille
T233 := poids
T2321 := StringT2321 := String
T2331 := String
?
label(O23) = description
children(023) = [O231,O232,O233]
predicate(T23) = description
regexp(T23) = T231,T232,T233?
predicate(f(O23))=label(O23)=description
f(O231), f(O232), f(O233)L(regexp(T23))
Figure 4 : Assignation de schéma
Assignation de schéma (2/2)
Première remarque : Il existe un schéma minimal Any assignable à toute base de données.
Seconde remarque : Pour chaque base de données S, il existe un schéma S ne typant que cette base, noté S[D].
3. Subsumption entre schémas
Le problème Subsumption de schémas Propriétés Utilisation de la subsumption
Le problème
Comment intégrer des données traitant des informations homogènes provenant de sources hétérogènes ?
Quelle correspondance entre 2 schémas de types ? Exemple
PhysicalDescr := description
hair := cheveux height := taille
heightDesc := StringhairDescr := String
T23 := description
T231 := cheveuxT232 := taille
T233 := poids
T2321 := StringT2321 := String
T2331 := String
?
Figure 5 : Relation entre schémas
Schema S
Schema S’
Subsumption de schémas
Définition intuitive: relation de correspondance entre les types de deux schémas, mapping entre deux schémas.=> assignation de types entre schémas
Soient S et S’ deux schémas de types, S subsume S’ s’il existe une fonction de mapping g:TS{} TS’{} tq :1. g(t)= ssi t=2. tTS, predicateS(t) predicateS’(g(t))3. tTS{},g(L(regexpS(t))) L(regexpS’(g(t)))
Si S subsume S’ et S’ subsume S alors on a une relation d’équivalence entre S et S’
Exemple
PhysicalDescr := description
hair := cheveux height := taille
heightDesc := StringhairDescr := String
T23 := description
T231 := cheveuxT232 := taille
T233 := poids
T2321 := StringT2321 := String
T2331 := String
?
Figure 6 : Subsumption entre schémas
Schema S
Schema S’
S subsume S’ avec la fonction g tq :
g(PhysicalDescr)=descriptiong(hair)=T231g(hairDescr)=T2321g(height)=T232g(heightDescr)=T2321
Par ex, on a :
predicateS(PhysicalDescr)=predicateS’(T23) =description
L=regexpS(PhysicalDescr)=cheveux,tailleL’=regexpS’(description)=cheveux,taille,poids?et LL’
Propriétés de la subsumption
S[D] subsume tout schéma assignable à D La relation de subsumption est transitive Si S est assignable à D et S subsume S’ alors S’ est
assignable a D=> utile pour la validation de schémas
Avantages :=> travail sur des schémas (tailles < taille des données)=> pas d’accès direct aux données
Utilisation de la subsumption
Idée forte : accéder aux données par le schéma le plus adéquat Système de requêtes : pour une requête donnée, indépendante
d’un schéma, trouver le schéma permettant d’obtenir le résultat
borne inférieure pour le relation de susbsumption : pour deux schémas, il existe un schéma maximal subsumant les deux autres.=> optimiser les informations de typage communes=> détermination du bon schéma
Systèmes de requêtes, systèmes de stockage, intégration…
Conclusion
Notion théorique que l’on retrouve dans de nombreux travaux sur les données semi-structurées : XML Schema, YATL, etc.
Le typage de données est d’une grande complexité=> la subsumption permet de travailler sur des schémas plutôt que sur les bases de données directement
Améliorer les systèmes de requêtes est l’une des principales motivations
Bibliographie
Subsumption for XML types - Gabriel M Kuper & Jérôme Siméon (2001) Semi-structured data - Peter Buneman (1997) Querying semi-structured data - Serge Abiteboul (1997) Adding structure to unstructured data - Peter Buneman, Susan Davidson,
Duan Fernandez, Dan suciu (1997)
Recommended