XSLT e recursividade
estrutural
Helena Galhardas
DEI IST
Agenda


Recursividade estrutural
XSLT
Recursividade estrutural: um
paradigma diferente
Dados são vistos como conjuntos e um
operador de união:
{a:3, a:{b:”one”, c:5}, b:4} =
{a:3} U {a:{b:”one”,c:5}} U {b:4}
Exemplo 1
Encontrar todos os inteiros nos dados
f($T1 U $T2) = f($T1) U f($T2)
f({$L: $T})
= f($T)
f({})
= {}
f($V)
= if isInt($V) then {result: $V} else {}
a
3
b
a
result
b
c
“one”
5
4
3
result
5
result
4
Exemplo 2
O que faz?
f($T1 U $T2)
f({$L: $T})
f({})
f($V)
=
=
=
=
f($T1) U f($T2)
if $L=a then {b:f($T)} else {$L:f($T)}
{}
$V
Exemplo 3
Aumentar os preços dos motores de 10%
f($T1 U $T2) = f($T1) U f($T2)
f({$L: $T}) = if $L= engine
then {$L: g($T)}
else {$L: f($T)}
f({})
= {}
f($V)
= $V
engine
part
price
100
body
price part
1000
g($T1 U $T2) = g($T1) U g($T2)
g({$L: $T}) = if $L= price
then {$L:1.1*$T}
else {$L: g($T)}
g({})
= {}
g($V)
= $V
engine
price
price 1000
100
part
price
110
body
price part
1100
price
price 1000
100
Exemplo 4
Encontrar todas as sub-árvores que se
conseguem chegar por (a.b)*.a
a
b
a
f($T1 U $T2) = f($T1) U f($T2)
f({$L: $T}) = if $L= a
then g($T} U $T
else { }
f({})
= {}
f($V)
= {}
g($T1 U $T2) = g($T1) U g($T2)
g({$L: $T}) = if $L= b
then f($T)
else { }
g({})
= {}
g($V)
= {}
Forma genérica de recursividade
estrutural
f1($T1 U $T2) =
f1({$L: $T}) =
f1({})
=
f1($V)
=
f1($T1) U f1($T2)
E1($L, f1($T),...,fk($T), $T)
{}
{}
. . . .
fk($T1 U $T2) =
fk({$L: $T}) =
fk({})
=
fk($V)
=
fk($T1) U fk($T2)
Ek($L, f1($T),...,fk($T), $T)
{}
{}
Cada E1, ..., Ek consiste só {_ : _}, U, if_then_else_
Execução da recursividade estrutural

Calcula as funções recursivas começando
com f1 na raíz
Terminação é garantida
Quão eficientemente se pode executar?

Não vamos detalhar
XSL

XSL composto por:


Linguagem para transformar documentos XML (XSLT)
Vocabulário XML para especificar semântica de formatação:
 XSL-FO (formatting objects)
XSLT transforma um doc XML numa árvore de
resultado:





Outro doc XML
Um doc HTML
Um doc que contenha FO
XSL-FO em geral:



Corresponde a uma ou mais áreas no écran ou página
Tem props para descrever o aspecto visual da área
Tem como conteúdo ou
 texto
 Objecto externo (image, applet, etc.), ou
 Mais objectos de formatação
Programa XSLT


XSL program = template-rule ... template-rule
template-rule = match pattern + template
Modelo de computação:
• diferente do das outras ligs de interrogação.
• XSL começa no elemento raiz e tenta aplicar um padrão
a esse nó.
• Se tiver sucesso, então executa o template correspondente
sobre esse nó.
• Normalmente, o template instroi o XSL para produzir
um resultado em XML ou para aplicar os templates
recursivamente nos nós filhos.
• Aí, o processo é repetido.
•o XSL é como uma função recursiva.
Regras XSLT




Regras são indicadas pelos elementos
xsl:template
O padrão é especificado usando uma expressão
XPath no valor do atributo match
template é o conteúdo do elemento xsl:template
<xsl:apply-templates/> é uma instrução que aplica
o programa XSLT completo a todos os filhos do
elemento que fez match no template
Exemplo documento XML
<bib> <book>
</book>
<paper>
</paper>
<book>
</book>
</bib>
<title> t1 </title>
<author> a1 </author>
<author> a2 </author>
<title> t2 </title>
<author> a3 </author>
<author> a4 </author>
<title> t3 </title>
<author> a5 </author>
<author> a6 </author>
<author> a7 </author>
Exemplo de programa XSLT
<xsl:template >
<xsl:apply-templates/>
</xsl:template>
<xsl:template match = “/bib/*/title”>
<result>
<xsl:value-of />
</result>
</xsl:template>
Significado: Devolve os títulos de todos os livros.
Resultado:
<result> t1 </result>
<result> t2 </result>
<result> t3 </result>
Como funciona?

Começa pela raiz <bib>... </bib>


Verifica se algum padrão é satisfeito pelo nó raiz
O padrão da primeira regra é.



Mais uma vez, só o padrão da primeira regra é
satisfeito


XSLT avalia o corpo da regra <xsl:apply-templates/>
Implica que o programa completo vai ser aplicado a
todos os filhos de <bib> ou seja aos 3 elementos
<book> … </book>
Implica aplicar o programa completo aos elementos
<title> e <author>
Finalmente, o padrão da segunda regra é satisfeito
pelo elemento <title>

O XSLT gera um elemento <result> ...</result> em que
o seu conteúdo é o valor do nó corrente ou seja a
cadeia de caracteres com o título
Padrões XSLT: expressões de caminho
bib
elemento bib
*
qualquer elemento
/
root
/bib
bib debaixo de root
bib/paper
paper debaixo de bib
bib//paper
paper bebaixo de bib, a qq
profundidade
//paper
paper a qualquer profundidade
paper|book
um paper ou um book
@price
atributo price
bib/book/@price atributo price em book, em bib
db/book[@price]
books que têm um atributo price
db/book[@price=’10’] books com price igual a 10
Instrução < xsl:element name= “...”>


Cria um novo elemento com nome “...”
Exemplos:
<xsl:template match=“A”>
<xsl:element name =“B”>
<xsl:value-of/>
<xsl:element/>
Equivalente a:
<xsl:template match=“A”>
<B><xsl:value-of/></B>
</xsl:template>
Outro exemplo
<xsl:template match=“*”>
<xsl:element name = “name()”>
<xsl:value-of/>
</xsl:element>
</xsl:template>


Copia todos os elementos top-level do ficheiro de
entrada.
“name()” retorna o nome do nó corrente, que
usamos como o nome do nó de saída.
Controlo de fluxo
<xsl:template match = “* | /”> <xsl:apply-templates/>
</xsl:template>
<xsl:template match=“a”> <A><xsl:apply-templates/></A>
</xsl:template>
<xsl:template match=“b”> <B><xsl:apply-templates/></B>
</xsl:template>
<xsl:template match=“c”> <C><xsl:value-of/></C>
</xsl:template>
<a> <e> <b> <c> 1 </c>
<c> 2 </c>
</b>
<a> <c> 3 </c>
</a>
</e>
<c> 4 </c>
</a>
<A> <B> <C> 1 </C>
<C> 2 </C>
</B>
<A> <C> 3 </C>
</A>
<C> 4 </C>
</A>
XSLT e recursividade estrutural
Equivalente a:
f(T1 U T2) = f(T1) U f(T2)
f({L: T}) = if L= c then {C: t}
else L= b then {B: f(t)}
else L= a then {A: f(t)}
else f(t)
f({})
= {}
f(V)
= V
 <xsl:template match=“c”>
 <xsl:template match=“b”>
 <xsl:template match=“a”>
 <xsl:template match = “* | /”>
XSLT vs recursividade estrutural
XSLT:
 Sobre árvores
 Pode entrar em ciclo
infinito
Recursividade estrutural:
 Grafos arbitrários
 Termina sempre
Exemplo: conversão XML em HTML
<xsl:template match=“/”>
<HTML>
<HEAD>
<TITLE> Bibliography
entries </TITLE>
</HEAD>
<BODY>
<xsl:apply-templates/>
</BODY>
</xsl:template>
<xsl:template match=“title”>
<TD>
<xsl:value-of>
>/TD>
</xsl:template>
<xsl:template match=“author”>
<TD>
<xsl:value-of>
>/TD>
<<xsl:template match = “book|paper”>
<TR>
<xsl:apply-templates
select=“title”/>
<xsl:apply-templates
select=“author”/>
</TR>
</xsl:template>
<xsl:template match=“bib”>
<TABLE>
<TBODY>
<xsl:apply-templates/>
</TBODY>
</TABLE>
</xsl:template>
Resultado: HTML
<HTML>
<HEAD>
<TITLE> Bibliography Entries </TITLE>
</HEAD>
<BODY>
<TABLE>
<TBODY>
<TR><TD> t1 </TD> <TD> a1 </TD> <TD> a2 </TD> </TR>
<TR><TD> t2 </TD> <TD> a3 </TD> <TD> a4 </TD> </TR>
<TR><TD> t3 </TD> <TD> a5 </TD> <TD> a6 </TD> <TD>
a7 </TD></TR>
</TBODY>
</TABLE>
</BODY>
</HTML>
Ainda outro programa XSLT simples
Copia a entrada:
<xsl:template match = “/”>
<xsl:apply-templates/>
</xsl:template>
<xsl:template match = “text()”>
<xsl:value-of select=“.”/>
</xsl:template>
<xsl:template match = “*”>
<xsl:element name=“name(.)”>
<xsl:apply-templates/>
</xsl:element>
</xsl:template>
Exercício
Escreva um programa XSLT que transforme o doc XML:
<teaches>
<teaches-tuple course="XML" lecturer="Peter Wood"/> <teaches-tuple
course="Algorithms" lecturer="Trevor Fenner"/>
</teaches>
Noutro com o formato:
<teaches>
<teaches-tuple>
<course>XML</course>
<lecturer>Peter Wood</lecturer>
</teaches-tuple>
<teaches-tuple>
<course>Algorithms</course>
<lecturer>Trevor Fenner</lecturer>
</teaches-tuple>
</teaches>
Assuma que teaches é o elemento raíz e que os atributos course e
lecturer são obrigatórios. O programa deve executar-se para qualquer
número de ocorrências do elemento teaches-tuple.
Referências








S. Abiteboul, P. Buneman, D. Suciu, “Data on the Web, From
Relations to Semistructured Data and XML”, Morgan Kaufmann,
2000, (caps 5 e 6)
Peter Wood, Slides on “Representing and Querying Data on the
Web”, http://www.dcs.bbk.ac.uk/~ptw/teaching/data-on-theweb.html.
Dan Suciu, Slides on “The semistructured data model”, CSE 590ds:
Management of XML and Semistructured Data,
http://www.cs.washington.edu/education/courses/cse590ds/01sp/
www.w3.org/Style/XSL/
W3C's XSL home page
hands-on-xsl.pdf
hands-on XSL: a simple exercise demonstrating the principles of
XSLT (previously available from IBM developerWorks)
nwalsh.com/docs/tutorials/xsl/
an XSL tutorial by Paul Grosso and Norman Walsh
www.zvon.org/xxl/XSLTreference/Output/
an XSLT reference using examples; links to other XML tutorials
metalab.unc.edu/xml/books/bible/updates/14.html
a chapter from the XML Bible on XSL Transformations (and XPath)
Próximo tópico

XQuery
Resolução de conflitos para regras
de template
Se várias regras de template fazem match, escolher a que
tem maior prioridade
 Prioridades podem ser:

Explicitas: <xsl:template match=“abc” priority=“1.41”>
implicitas: regras ad-hoc dadas pelo W3, baseadas no match

match=“abc”  prioridade

match=“[... some namespace name... ]”  prioridade

match=“node()”  prioridade

0.
-0.5.
-0.25.
Modos em XSLT



Modo = nome para um grupo de template
rules
Útil quando o mesmo nó tem que ser
percorrido várias vezes
Equivalente a ter múltiplas funções
recursivas
Exemplo
Calcular o caminho (a.b)* :
<xsl:template match = “/”>
<xsl:apply-templates mode=“f”/>
</xsl:template>
<xsl:template match=“*” mode=“f”/>
<xsl:template match=“a” mode=“f”>
<result> <xsl:copy-of match=“.”/> </result>
<xsl:apply-templates mode=“g”/>
</xsl:template>
<xsl:template match=“*” mode=“g”>
<xsl:template match=“b” mode=“g”>
<xsl:apply-templates mode=“f”/>
</xsl:template>
f(T1 U T2) = f(T1) U f(T2)
f({a: T}) = {result:T} U g(T)
f({})
= {}
f(V)
= V
g(T1 U T2) = g(T1) U g(T2)
g({b: T}) = f(T)
g({})
= {}
g(V)
= V