Synthèse : XPath, XSLT, Datalog et Algorithmes GYO

Recto : XPath, XSLT et CQ / UCQ

XPath

• /a/b : fils directs
• //a : partout
• @x : attribut ; . : courant
• text() : texte ; A[B] : filtre
• not(), and, or
• [A] : il existe A
• [not(A)] : aucun A
• A=B : il existe a et b tels que a = b
• A!=B : il existe a et b tels que a != b
• Attention : A!=B est différent de not(A=B)

Exemples de sélection et d'unicité

• Au moins 2 valeurs différentes : f/@c != f/@c
• Au moins 3 valeurs différentes dont le rouge : f/@c="rouge" and f[@c!="rouge"]/@c != f[@c!="rouge"]/@c
• Doublon : f[@x=following-sibling::f/@x]
• Garder le premier (Garder 1) : f[not(@x=following-sibling::f/@x)]
• Unique local : x[not(@a=following-sibling::x/@a)]
• Unique global : x[not(@a=following::x/@a)]
• Absent avant : not(f/@x=preceding-sibling::p/f/@x)
• Absent après : not(f/@x=following-sibling::p/f/@x)
• Maximum sans la fonction max : A[not(v(A) < //A/v(A))]
• Minimum sans la fonction min : A[not(v(A) > //A/v(A))]
• Sauf le minimum : A[v(A) > //A/v(A)]
• Sauf le maximum : A[v(A) < //A/v(A)]
• Maximum de la somme : //bouquet[not(sum(fleur/@nombre) < //bouquet/sum(fleur/@nombre))]/@bnom
• Pas de multi-couleurs : //bouquet[not(fleur[@fnom=following-sibling::fleur/@fnom])]/@bnom

XSLT

<xsl:template match="/">
  <out>
    <xsl:apply-templates select="..."/>
  </out>
</xsl:template>

<xsl:template match="x">
  ...
</xsl:template>

<xsl:value-of select="..."/>
<x a="{@a}"/>

<xsl:attribute name="a">
  <xsl:value-of select="..."/>
</xsl:attribute>

<xsl:element name="{@x}">
  ...
</xsl:element>

Note : current() désigne le nœud du template.

Éléments souvent interdits en XSLT

• xsl:for-each
• xsl:if
• distinct-values()
• xsl:with-param

CQ / UCQ (Conjunctive Queries)

Requête : q: Ans(x) <- R(...), S(...)

Homomorphisme h : q1 -> q2

• Tête respectée
• Constantes fixées
• h(atomes q1) existent dans q2

Théorème d'inclusion

q1 ⊆ q2 si et seulement si il existe un homomorphisme h: q2 -> q1 (Attention : sens inverse).

Équivalence

q1 == q2 si et seulement si h: q1 -> q2 et h: q2 -> q1.

UCQ (Union de CQ)

Si qi ⊆ qj, alors qi est redondante.

Méthode UCQ :

1. Minimiser chaque CQ.
2. Tester les inclusions.
3. Supprimer les redondantes.

Minimiser q

Trouver une sous-requête q' avec q -> q' et q' -> q. En tête, les variables libres gardent leurs positions.

XQuery

let $x := ...
return ...

for $x in ...
let $y := ...
where ...
order by ...
return ...

distinct-values(...)
sum(...)

Construction et éléments dynamiques

<out>{
  for $x in ...
  return <item a="{$x/@a}">{$x}</item>
}</out>

element {$x} { ... }

Verso : GYO, Datalog et Chase

GYO / Semijoin

• Hyperarête = schéma
• Oreille O de T : Les attributs de O qui apparaissent ailleurs sont contenus dans T (O ∩ (Σ \ O) ⊆ T).
• Algorithme GYO : Tant qu'il y a une oreille, la supprimer. Si tout est supprimé, le schéma est alpha-acyclique. Si l'algorithme bloque, il ne l'est pas.
• Join Tree (Arbre de jointure) : Un nœud par hyperarête. Pour chaque attribut A, tous les nœuds contenant A forment un sous-arbre connexe.
• Semijoin : R semijoin S consiste à garder les tuples de R ayant au moins un tuple compatible dans S. R := R ⋉ S (R peut diminuer, S ne change pas).
• Dangling : Tuple ne participant à aucun tuple de la jointure totale.
• Full Reducer : Supprime tous les dangling tuples pour toute instance.
• Join-Tree Reducer : Des feuilles vers la racine, puis de la racine vers les feuilles.

Datalog

• EDB = entrée (données) ; IDB = calculé (règles).
• Variables en majuscules ; prédicats/constantes en minuscules.
• Les variables en tête doivent apparaître positivement dans le corps (body).
• Chemin : reach(X,Y) :- r(X,Y,C).
reach(X,Z) :- reach(X,Y), r(Y,Z,C).
• Cycle : cycle(X) :- reach(X,X).
• Négation stratifiée : p -> q (dépendance positive), p -/> q (dépendance négative). Stratifié si aucun cycle du PDG ne contient de dépendance négative.

Chase / Négation

• FD (Functional Dependency) : X -> Y.
• Tester F |= JD :
  1. Tableau canonique de la JD.
  2. Appliquer les FD jusqu'au point fixe.
  3. Si une ligne est entièrement "distinguished", alors vrai, sinon faux.
• Appliquer X -> Y : Si deux lignes sont égales sur X, identifier leurs valeurs sur Y.
• JD (Join Dependency) : *[R1, ..., Rn]. r = join(proj_R1(r), ..., proj_Rn(r)).

Rappels Flash

• XPath A!=B : Il existe des valeurs différentes.
• UCQ Inclusion : Homomorphisme en sens inverse.
• GYO : Oreilles jusqu'à vide.
• Join Tree : Occurrences d'un attribut restent connexes.
• Semijoin : Modifie le côté gauche seulement.
• XSLT current() : Nœud du template courant.
• Unique XPath : not(@x=following-sibling::.../@x).
• Point Fixe : Appliquer les règles jusqu'à ce qu'aucun nouveau fait ne soit produit.