SOLUTIONS SOLUTIONS SOLUTIONS

Exercices ASWS : XML, RDF, OWL

1 XPath

Soit un arbre XML :

0
/

1
A

2 11
B E

3 5 6 7 8 10 12 13 15
C F C F C F D C C

4 9 14
D D D

Exercice 1.1 : Donnez les requtes XPath suivantes :

1. Tous les noeuds C.

Solution : //C 2
2. Les enfants de tous les noeuds A.

Solution : /A/* 2
3. Les descendants de tous les noeuds A.

Solution : A//* 2
4. Les petits-enfants D de tous les noeuds A.

Solution : //A/*/D 2
5. Tous les noeuds C qui nont pas de fils D.

Solution : //C[not(D)] 2
6. Les petits-enfants C de tous les noeuds A qui nont pas denfant D.

Solution : //A/*/C[not(D)] 2
7. Tous les frres gauche des noeuds C.

Solution : //C/preceding-sibling::* 2
8. Le premier frre droite de chaque noeud C.

Solution : //C/preceding-sibling::*[1] 2

2 Modle RDF

Soit donn le graphe RDF G1 :

Exercice page: 1
 SOLUTIONS SOLUTIONS SOLUTIONS

Marie
Ville Region
nom
rdf:type marie habite rdf:type rdf:type
Personne se_situe_en
paris idf
rdf:type pierre
habite nom nom
nom
"Pierre" Paris Ile de france

Exercice 2.1 : Traduisez le graphe G1 suivant en document RDF-XML et en expressions Turtle.

Solution : RDF-XML (plusieures solutions possibles) :

<rdf:Description rdf:ID=pierre>
<nom>Pierre</nom>
<rdf:type>
<rdf:Description rdf:about=#Personne/>
</rdf:type>
<habite>
<rdf:Description rdf:ID=paris>
<rdf:type>
<rdf:Description rdf:about=#Ville/>
</rdf:type>
<nom>paris</nom>
<se_situe_en>
<rdf:Description rdf:ID=idf>
<rdf:type>
<rdf:Description rdf:about=Region/>
</rdf:type>
<nom>Ile de France</nom>
</se_situe_en>
</rdf:Description>
</habite>
</rdf:Description>
<rdf:Description rdf:ID=marie>
<nom>Marie</nom>
<rdf:type>
<rdf:Description rdf:about=#Personne/>
</rdf:type>
<habite>
<rdf:Description rdf:about=paris>
</habite>
</rdf:Description>
ou (version plate) :
<rdf:Description rdf:ID=pierre>
<nom>Pierre</nom>
<rdf:type rdf:resource=#Personne/>
<habite rdf:resource=#paris
</rdf:Description>
<rdf:Description rdf:ID=marie>
<nom>Marie</nom>
<rdf:type rdf:resource=#Personne/>
<habite rdf:resource=#paris
</rdf:Description>
<rdf:Description rdf:ID=paris>

Exercice page: 2
 SOLUTIONS SOLUTIONS SOLUTIONS

<rdf:type rdf:resource=#Ville/>
<nom>paris</nom>
<se_situe_en rdf:resource==idf/>
</rdf:Description>
<rdf:Description rdf:ID=idf>
<rdf:type rdf:resource==Region/>
<nom>Ile de France</nom>
</rdf:Description>
ou (types sous forme de nomde balises, version compacte) :
<Personne rdf:ID=pierre>
<nom>Pierre</nom>
<habite>
<Ville rdf:ID=paris>
<se_situe_en>
<Region rdf:ID=idf>
<nom>Ile de France</nom>
</Region>
</se_situe_en>
</Ville>
</habite>
</Personne>
<Personne rdf:ID=marie>
<nom>Marie</nom>
<habite rdf:resource=paris/>
</Personne>
Expressions Turtle (plusieures solutions possibles) :
Triplets :
#pierre #habite #paris .
#pierre #nom Pierre .
#pierre rdf:type #Personne .
#marie #habite #paris .
#marie #nom Marie .
#marie rdf:type #Personne .
#paris rdf:type #Ville .
#paris #nom Paris .
#paris #se_situe_en #idf .
#idf rdf:type Region .
#idf #nom Ile de France .
Plus compacte :
#pierre #habite #paris; #nom Pierre; rdf:type #Personne .
#marie #habite #paris; #nom Marie; rdf:type #Personne .
#paris rdf:type #Ville; #nom Paris; #se_situe_en #idf .
#idf rdf:type Region; #nom Ile de France .
2
Exercice 2.2 : Est-ce que G1 est minimal ?

Solution : oui : il nexiste pas de mapping m dont lapplication G1 gnre un sous-graphe de G1 . 2

Exercice 2.3 : On peut dfinir un deuxime graphe G2 qui reprsente linformation Pierre habite Paris et Marie habite
dans une ville situe en rgion Ile de France. Donnez (1) la description RDF-XML et (2) les expressions Turtle qui
reprsentent cette information.

Solution : RDF-XML :

Exercice page: 3
 SOLUTIONS SOLUTIONS SOLUTIONS

<rdf:Description rdf:id="pierre">
<habite>
<rdf:Description rdf:id="paris"/>
</habite>
</rdf:Description>
<rdf:Description rdf:id="marie">
<habite>
<ville>
<se_situe_en>
<region rdf:id="idf" nom="Ile de France"/>
</se_situe_en>
</ville>
</habite>
</rdf:Description>
Encodage en Turtle (noeud blanc implicite) :
#pierre #habite #paris .
#marie #habite [rdf:type #Ville; #se_situe_en #idf ] .
#idf rdf:type Region ;
#nom Ile de France .
o (noeud blanc explicite, ensemble de triplets)
#pierre #habite #paris .
#marie #habite _a .
_a rdf:type #Ville .
_a #se_situe_en #idf .
#idf rdf:type Region ;
#nom Ile de France .
2
Exercice 2.4 : Montrez que G1 |= G2 .

Solution : Il existe un mapping m : G2 G02 tel que G02 est un sous-graphe de G1 :

m(n) est lidentit pour tous les noeuds non-blancs n
m(_a) = #paris pour le seul noeud blanc _a
On obtient G02 :
#pierre #habite #paris .
#marie #habite #paris .
#paris rdf:type #Ville .
#paris #se_situe_en #idf .
#idf rdf:type Region ;
#nom Ile de France .
qui est un sous-graphe de G1 . En consquence G1 |= G2 . 2
Exercice 2.5 : Est-ce que lunion des deux graphes G1 G2 est minimale ?

Solution : non : en ajoutant les deux arcs (marie, habite, _a) et (_a, rgion, idf) G1 (_a correspond
un noeud blanc), il existe un mapping de G1 G2 vers un sous-graphe de G1 G2 . 2
Exercice 2.6 : Est-ce quil est possible de reprsenter sous forme dun graphe RDF la proposition Marie habite la mme
ville que Pierre mais on ne sait pas laquelle (sans ajouter des nouveaux types de proprits) ?

Solution : Non : Dans le langage RDF-XML, un noeud blanc peut seulement tre le sujet de plusieurs proprits et il
nest pas possible dexprimer des jointures o un noeud blanc est lobjet de plusieurs proprits.
Exemple : {(marie, habite, V ), (pierre, habite, V )} o V est un noeud blanc ne peut pas tre exprim en RDF. Par
contre, il est possible de dfinir un motif de graphe (requte) SPARQL qui vrifie si Marie habite la mme ville que
Pierre : #marie #habite V . #pierre #habite V . 2

Exercice page: 4
 SOLUTIONS SOLUTIONS SOLUTIONS

3 SPARQL

Soit le schma RDFS suivant :

<rdfs:Class rdf:ID="Cours"/>
<rdfs:Class rdf:ID="Etudiant"/>
<rdfs:Class rdf:ID="Enseignant"/>
<rdf:Property rdf:ID="enseigne_par">
<rdfs:domain rdf:resource="#Cours"/>
<rdfs:range rdf:resource="#Enseignant"/>
</rdf:Property>
<rdf:Property rdf:ID="inscrit_dans">
<rdfs:range rdf:resource="#Cours"/>
<rdfs:domain rdf:resource="#Etudiant"/>
</rdf:Property>
<rdf:Property rdf:ID="nom">
<rdfs:domain rdf:resource="#Cours"/>
<rdfs:domain rdf:resource="#Etudiant"/>
<rdfs:domain rdf:resource="#Enseignant"/>
<rdfs:range rdf:resource="rdfs:Literal"/>
</rdf:Property>
<rdf:Property rdf:ID="prerequis">
<rdfs:domain rdf:resource="#Cours"/>
<rdfs:range rdf:resource="#Cours"/>
</rdf:Property>

Exercice 3.1 : Exprimez les requtes suivantes en SPARQL.

1. Les noms des enseignants du cours BDIA-M2.

Solution :
prefix : <http://www.owl-ontologies.com/bdia#>
select ?N
where { ?C :nom ?X ; :enseigne_par ?P .
?P :nom ?N
filter (?X = "BDIA-M2")}
ou
prefix : <http://www.owl-ontologies.com/bdia#>
select ?N
where { [ :nom ?X ; :enseigne_par [ :nom ?N] ]
filter (?X = "BDIA")}
2
2. Les prrequis (noms de cours) demands pour le cours BDIA-M2.

Solution :
prefix : <http://www.owl-ontologies.com/bdia#>
select ?N
where { [ :nom ?X ; :prerequis [ :nom ?N] ]
filter (?X = "BDIA-M2")}
2
3. Les classes avec la proprit nom.

Solution :

Exercice page: 5
 SOLUTIONS SOLUTIONS SOLUTIONS

prefix : <http://www.owl-ontologies.com/bdia#>
select ?C
where { :nom rdfs:domain ?C }
2
4. Les instances de classes avec la proprit nom.

Solution :
prefix : <http://www.owl-ontologies.com/bdia#>
select ?X
where { ?X :nom [] }
2
5. Les cours avec leurs prrequis (si prsents).

Solution :
prefix : <http://www.owl-ontologies.com/bdia#>
select ?N
where { ?A :nom ?X; rdf:type :Cours . OPTIONAL { ?A :prerequis [ :nom ?N] }}
2
6. Les noms des enseignants qui enseignent deux cours diffrents.

Solution :
prefix : <http://www.owl-ontologies.com/bdia#>
select distinct ?N
where {?B :enseigne_par ?A .
?C :enseigne_par ?A .
?A :nom ?N .
filter (?B != ?C) }
2
7. Les noms des tudiants qui suivent deux cours diffrents du mme enseignant.

Solution :
prefix : <http://www.owl-ontologies.com/bdia#>
select distinct ?N
where { ?B :enseigne_par ?A .
?C :enseigne_par ?A .
?E :inscrit_dans ?B ; :inscrit_dans ?C .
?E :nom ?N
filter (?B != ?C) }
2
8. Les noms des cours sans prerquis (ngation).

Solution :
prefix : <http://www.owl-ontologies.com/bdia#>
select distinct ?N
where { ?A :nom ?N ; rdf:type :Cours .
optional { ?A :prerequis ?B }
filter (!bound(?B))
2
Exercice 3.2 : On suppose que tous les triplets (schma RDFS et graphe RDF) sont stockes dans une table relationnelle
RDF (S, P, O). Traduisez les requtes prcdentes en SQL.

Solution :

Exercice page: 6
SOLUTIONS SOLUTIONS SOLUTIONS

1. Les noms des enseignants du cours BDIA-M2.

select C.O
from RDF A, RDF B, RDF C
where A.P= :nom and A.O = BDIA-M2
and A.S = B.S and B.P=:enseigne_par
and C.S = B.O and C.P=:nom ;
2. Les prrequis (noms de cours) demands pour le cours BDIA-M2.
select C.O
from RDF A, RDF B, RDF C
where A.P =:nom and A.O=BDIA-M2 and
B.S = A.S and B.P=:prerequis and C.S=B.O and
C.P = :nom;
3. Les classes avec la proprit nom.
prefix : <http://www.owl-ontologies.com/bdia#>
select ?C
where { :nom rdfs:domain ?C }
4. Les instances avec la proprit nom.
select S
from RDF
where P=:nom
5. Les noms des cours avec leurs prrequis (si prsents).
select A.S, A.O, D.S, D.O
from ((RDF A left outer join RDF B on (A.S = B.S and B.P=:prerequis))
left outer join RDF D on (B.O = D.S and D.P=:nom))
join RDF C on A.S = C.S
where A.P=:nom and C.O = :Cours ;
6. Les enseignants qui enseignent au moins deux cours diffrents.
select distinct A.O, C.O
from RDF A join RDF B on (A.P=:enseigne_par and B.P=:enseigne_par and A.O=B.O)
join RDF C on A.O=C.S and C.P=:nom
where A.S <> B.S;
7. Les tudiants qui suivent deux cours diffrents du mme enseignant.
select distinct A.O, C.S
from RDF A join RDF B on (A.P=:enseigne_par and B.P=:enseigne_par and A.O=B.O)
join RDF C on A.S=C.O and C.P=:inscrit_dans
join RDF D on B.S=D.O and D.P=:inscrit_dans
where A.S <> B.S;
8. Les noms des cours sans prerquis (ngation).
select A.S, A.O
from RDF A join RDF S on A.S = S.S
where A.P=:nom and S.P = rdf:type and S.O = :Cours
and A.S not in (select B.S from RDF B where B.P = :prerequis);
2

Smantique SPARQL
Soit donn le graphe RDF suivant :
D ={ (B1, name, paul), (B1, phone, 777 3426), (1)
(B2, name, john), (B2, email, [email protected]), (2)
(B3, name, george), (B3, webP age, www.george.edu), (3)
(B4, name, ringo), (B4, email, [email protected]), (4)
(B4, webP age, www.starr.edu), (B4, phone, 888 4537)} (5)

Exercice page: 7
 SOLUTIONS SOLUTIONS SOLUTIONS

Evaluez les motifs suivants en suivant la smantique compositionnelle vue en cours :

1. P 1 = ((?A, email, ?E)OP T (?A, webP age, ?W )).

Solution : JP 1KD = 1 (?A?E?W ) = (B2, [email protected], N U LL), 2 (?A?E?W ) = (B4, [email protected], www.starr.edu)
2
2. P 2 = (((?A, name, ?N )OP T (?A, email, ?E))OP T (?A, webP age, ?W )).

Solution : JP 2KD =?A?N ?E?W 1 : B1paul2 : [email protected] : B3georgewww.george.edu4 :

[email protected] 2
3. P 3 = ((?A, name, ?N )OP T ((?A, email, ?E)OP T (?A, webP age, ?W ))).

Solution : JP 3KD =?A?N ?E?W 1 : B1paul2 : [email protected] : B3george4 : [email protected]

Note the difference between JP 2KD and JP 3KD . These two examples show that J((AOP T B)OP T C)KD 6= J(AOP T (BOP T C))KD
in general. 2
4. P 4 = ((?A, name, ?N )AN D((?A, email, ?E)U N ION (?A, webP age, ?W ))).

Solution : JP 4KD =?A?N ?E?W 1 : [email protected] : B3georgewww.george.edu3 : [email protected] :

B4ringowww.starr.edu 2

4 OWL et Logiques de Description

Exercice 4.1 : On suppose lexistence de quatre concepts A, B, C et D o A est un sous-concept de B (A v B). Montrez
par lalgorithme de subsomption structurelle que
A u R.C u R.D v B u R.C

Solution : Algorithme de subsomption structurelle :

1. Normalisation : A u R.(C u D) v B u R.C
2. Pour chaque sous-expression X de lexpression de droite, il existe une sous-expression Y de lexpression de
gauche qui est subsume par X (Y v X) :
X = B, Y = A : A v B
X = R.C, Y = R.(C u D) : il faut montrer C u D v C (avec le mme algorithme) :
X = C, Y = C : C v C
2
C u R.(D u R0 .E) v C u R.D.

Solution : Algorithme de subsomption structurelle :

1. Normalisation : rien faire
2. Pour chaque sous-expression X de lexpression de droite, il existe une sous-expression Y de lexpression de
gauche qui est subsume par X :
X = C, Y = C
X = R.D, Y = R.(D u R0 .E) : il faut montrer D u R0 .E v D (avec le mme algorithme) :
X = D, Y = D
2
Exercice 4.2 : Il est possible de traduire un ensemble de concepts atomiques et de rles en un schma de base de donnes
relationnel : On suppose que chaque concept correspond une relation avec un attribut (un n-uplet par instance) et que
chaque rle correspond une relation avec deux attributs. On peut dfinir des requtes qui retournent toutes les instances
dun concept complexes. Par exemple, la requte

{x | C(x) y(R(x, y) D(y))}

retourne toutes les instances du concept C u R.D.
Traduisez les concepts suivants en requtes dans le calcul relationnel.

Exercice page: 8
 SOLUTIONS SOLUTIONS SOLUTIONS

C u R.D

Solution :
{x | C(x) y(R(x, y) D(y))}
ou
{x | C(x) y(R(x, y) D(y))}
2
C u R.D

Solution : quivalent C u R.D 2

C u R.E

Solution :
{x | C(x) y(R(x, y) E(y))}
ou
{x | C(x) y(R(x, y) E(y))}
2
C u R.E

Solution : quivalent C u R.E 2

Preuve par tableau

La mthode de preuve par tableau consiste essayer de prouver quil existe au moins un modle pour une formule logique
donne.
Exercice 4.3 : Prouvez que la formule suivante est cohrente (il existe un modle) :

x(C(x) y(R(x, y) D(y)) z(R(x, z) E(z)))

Solution :
1. Normalisation (pousser la ngation) :
(a) x(C(x) y(R(x, y) D(y)) z(R(x, z) E(z)))
(b) x(C(x) y(R(x, y) D(y)) z(R(x, z) E(z)))
2. Mthode par tableau :
1 x(C(x) y(R(x, y) D(y)) z(R(x, z) E(z)))
2 (exists) C(a) y(R(a, y) D(y)) z(R(a, z) E(z))
3 (conj) C(a)
y(R(a, y) D(y))
z(R(a, z) E(z))
4 (exists,conj) R(a, b)
D(b)
5 (forall) R(a, b) E(b)
R(a, b) E(b)
6 (disj)
CLASH TERMINAISON
Il existe un modle M avec I(C) = {a}, I(R) = {(a, b)}, I(D) = {b}, I(E) = . 2

Preuves de satisfiabilit de concepts

Voici un extrait dune ontologie touristique :

Exercice page: 9
 SOLUTIONS SOLUTIONS SOLUTIONS

<owl:Class rdf:ID="Activite"/>
<owl:Class rdf:ID="ActiviteSportive">
<rdfs:subClassOf rdf:resource="#Activite"/>
</owl:Class>
<owl:Class rdf:ID="SejourActif">
<owl:equivalentClass>
<owl:Restriction>
<owl:someValuesFrom rdf:resource="#Activite"/>
<owl:onProperty>
<owl:ObjectProperty rdf:ID="activites"/>
</owl:onProperty>
</owl:Restriction>
</owl:equivalentClass>
</owl:Class>
<owl:Class rdf:ID="SejourSportif">
<owl:equivalentClass>
<owl:Restriction>
<owl:onProperty rdf:resource="#activites"/>
<owl:allValuesFrom rdf:resource="#ActiviteSportive"/>
</owl:Restriction>
</owl:equivalentClass>
</owl:Class>
Exercice 4.4 : Reprsentez cette ontologie sous forme dexpressions dune logique de description (TBox).

Solution :
ActiviteSportive v Activite
SejourSportif activites.ActiviteSportive
SejourActif activites.Activite
2
Exercice 4.5 : Montrez formellement que SejourSportif nest pas un sous-concept de SejourActif .

Solution : Il suffit de montrer quil existe un modle pour SejourSportif u SejourActif dans la terminologie pr-
cdente (SejourSportif u SejourActif est une dfinition cohrente).
Preuve par tableau :
On remplace tous les concepts par leur dfinition (unfolding)
On transforme le concept en formule logique (introduire les variables)
Normalisation : On pousse les ngations vers les concepts et les rles en utilisant les quivalences logiques : par
exemple, x(F (x)) devient x(F (x)), ...
On applique les oprations de rcriture dfinies pour les tableaux : limination des quantificateurs et des connecteurs
logiques
A la fin : on cherche les conflits (CLASH) et des modles possibles

Exercice page: 10
 SOLUTIONS SOLUTIONS SOLUTIONS

Remplacer les concepts par leur dfinition (unfolding) :

SejourSportif SejourActif
z }| { z }| {
activites.ActiviteSportive u(activites.Activite)

Rprsentation avec variables :

x(y(activites(x, y) ActiviteSportive(y)) (z(activites(x, z) Activite(z))))
ou
x(y(activites(x, y) ActiviteSportive(y)) (z(activites(x, z) Activite(z))))

Pousser les ngations vers lintrieur :

x(y(activites(x, y) ActiviteSportive(y)) z(activites(x, z) Activite(z)))

Remplacer x par une instance t :

y(activites(t, y) ActiviteSportive(y)) z(activites(t, z) Activite(z))

Remplacer y et z par Y (Y est une variable qui peut tre remplace par toutes les instances du domaine
dinterprtation ) :
(activites(t, Y ) ActiviteSportive(Y )) (activites(t, Y ) Activite(Y ))

Rgle de conjonction :
activites(t, Y ) ActiviteSportive(Y )
activites(t, Y ) Activite(Y )

Rgles de disjonction (splits) :

activites(t, Y ) ActiviteSportive(Y )
activites(t, Y ) Activite(Y ) activites(t, Y ) Activite(Y )
I1 I2 I3 CLASH
Modles possibles : toutes les interprtations qui contiennent un sjour t sans activits associes (I1 et I3 ) ou relis
travers le rle activites qu des instances sui ne sont pas des activits (I2 ). 2
Exercice 4.6 : Voici une terminologie (TBox) :

V ache v Animal u V egetarien (6)

M outon v Animal (7)
Cochon v Animal (8)
V egetarien mange.Animal (9)
V acheF olle V ache u mange.M outon (10)
(11)

Montrez formellement que

1. V acheF olle est un concept inconsistent dans la terminologie prcdente.

Solution : On essaie de prouver V acheumange.M outon v (il nexiste pas de modle pour V acheumange.M outon
dans la terminologie prcdente) :
Unfolding : par la terminologie on sait que
V egetarien
z }| {
la vache est un animal vgtarien : Animal u mange.Animal
le mouton est un animal : Animal
On tend le concept initial : V ache u Animal u mange.Animal u mange.(M outon u Animal)
reprsentation avec des variables : x(V ache(x)Animal(x)y(mange(x, y) Animal(y))z(mange(x, z)
M outon(z) Animal(z)))
limination des quantificateurs (Y peut tre remplac par nimporte quelle instance du domaine dinterprtation) :
p1 p2 p3 p4
z }| { z }| { z }| { z }| {
V ache(v) Animal(v) (mange(v, Y ) Animal(Y )) mange(v, Y ) M outon(Y ) Animal(Y )

Exercice page: 11
SOLUTIONS SOLUTIONS SOLUTIONS

deux branches possibles :

(a) mange(v, Y ) (p1) contradiction avec mange(v, Y ) (p2)
(b) Animal(m) (p2) contradiction avec Animal(Y ) (p4)
2
2. Il existe des animaux non vgtariens (dans la terminologie prcdente).

Solution : On essaye de montrer quil existe un modle pour Animalu(mange.Animal) dans la terminologie :
Il nest pas possible dtendre le concepts avec des connaissances de la terminologie.
Pousser les ngations : Animal u mange.Animal
Introduction des variables : Animal(x) mange(x, y) Animal(y)
Modles : toutes les interprtations avec au moins deux animaux x et y ou x mange y : I(Animal) = {x, y}, I(mange) =
{(x, y)}.
Remarque : I(Animal) = {x}, I(mange) = {(x, x)} est aussi un modle.
2
3. Les cochons peuvent manger du Mouton.

Solution : On essaye de montrer quil existe un modle pour Cochon u mange.M outon :
Extension avec la terminoloie et introduction de variables : x(Cochon(x) Animal(x) y(mange(x, y)
M outon(y) Animal(y))
Elimination des variables : Cochon(c) Animal(c) mange(v, m) M outon(m) Animal(m)
Modle possible : AnimalI = {c, m}, CochonI = {c}; M outonI = {m}, mangeI = {(c, m)}
2

Exercice page: 12