Modelo de dados semiestruturado e tipificação em
XML
Helena Galhardas
DEI IST
Agenda



Resumo da aula passada
Modelo de dados semi-estruturado
Tipificação em dados semi-estruturados e
XML
Resumo da aula passada
Resumo: o que interessa lembrar


Semi-estruturado: casamento entre sistemas
documentais e SGBDs
XML



Árvores ordenadas, etiquetadas e com ligações
Semântica e tipos estão nas tags
Formato de transferência de dados
Resumo: tecnologia

SGBDs:


Documentos:


B-tree, hash table, optimização de interrogações
Indíce texto, classificação
XML:

Autómato de árvores
Resumo: problemas antigos ressurgem




Optimização de interrogações distribuídas
Integração de dados
Procura de dados e serviços
Gestão de actualizações de dados
Exercício
Considere uma BD relacional que contém uma
relação “ensina” com atributos “disciplina” e
“docente”. Esta relação representa uma
associação entre as disciplinas ensinadas no
Mestrado de Bolonha em Informática e os
professores que nele ensinam.
Escreva um documento XML que representa
uma instância dessa relação contendo dois
tuplos (arbitre a disciplina e o nome dos
professores)
Modelo de dados semi-estruturado e
XML
Modelo de dados semi-estruturado


Dados semi-estruturados são muitas vezes
conotados como “sem-esquema”
(schemaless) ou “explicáveis por si próprios”
(self-describing)
Dados são descritos através de uma sintaxe
simples:
{nome: {primeiro: “Bruno”, ultimo: “Martins”},
tel: 21 4233290,
email: “[email protected]”}
Representação gráfica
nome
tel
email
“[email protected]”
214233290
primeiro
“Bruno”
ultimo
“Martins”
Variações na estrutura
{pessoa:
{nome: {primeiro: “Bruno”, ultimo: “Martins”},
tel: 21 4233290,
email: “[email protected]”},
pessoa:
{nome: “Pável”, tel: 21 4233267, email:
[email protected]},
pessoa:
{nome: “Helena”, tel: 21 4233246, altura: 1,60}
}
Representação de dados relacionais
{
r1: {linha: {a: a1, b: b1, c: c1},
linha: {a: a2, b: b2, c: c2}
},
r2: {linha: {c: c2, d: d2},
linha: {c: c3, d: d3},
linha: {c: c4, d: d4}
}
}
Representação de BDs de objectos
{
pessoa: &o1 {nome: “Ana”,
idade: 35,
filho: &o2,
filho: &o3
},
pessoa: &o2 {nome: “João”,
idade: 7,
parentes: {mae: &o1,
irma: &o3}
},
pessoa: &o3 {nome: “Joana”,
país: “Portugal”,
mae: &o1
}
}
Modelo de dados semi-estruturado
Bib
&o1
complex object
paper
paper
book
references
&o12
&o24
references
author
title
year
&o29
references
author
http
page
author
title publisher
title
author
author
author
&o43
&25
&96
1997
last
firstname
lastname
atomic object
firstname
lastname
&243
“Serge”
“Abiteboul”
“Victor”
Object Exchange Model (OEM)
first
&206
“Vianu”
122
133
Sintaxe para expressões semiestruturadas
<ssd-expr> ::= <value> | oid<value> |oid
<value> ::= atomicvalue | <complexvalue>
<complexvalue> ::= {label: <ssd-expr>,...,
label:<ssd-expr>}



Um oid o é definido numa ssd-expression s se s tem a forma
ov para algum valor v ou s tem a forma {l1:e1, ..., ln:en} e o
está definido numa das e1,..., en
Qualquer oid é definido no máximo uma vez em s
Se um oid o é usado em s, então tem que ter sido definido em
s
Terminologia de grafos para descrever
dados semi-estruturados



Grafo (N, E) consiste num conjunto N de nós e um
conjunto E de arcos (edges)
Associado a cada e  E, existe um par ordenado de
nós, o nó fonte s(e) e o nó destino t(e).
Um caminho (path) é uma sequência e1, e2, ..., ek
de arcos tal que:




t(ei) = s(ei+1), 1<=i<=k-1,
K: tamanho do caminho
Um nó r é a raíz do grafo se existir um caminho de r
para n, para qualquer n  N
Um ciclo num grafo é um caminho entre um nó e ele
mesmo. Um grafo sem ciclos é aciclico.
Terminologia de grafos para descrever
dados semi-estruturados (2)




Um grafo com raíz é uma árvore se existir
um caminho único de r para n, para qualquer
nN
Um nó é terminal ou folha se não é a fonte
de nenhum arco em E.
DAG: Directed Acyclic graph
Modelo de dados semi-estruturados: grafo
com arcos etiquetados (edge-labeled graph)

Tb pode incluir etiquetas nos nós
XML e dados semi-estruturados
<person>
<name> Alan </name>
<age> 42 </age>
<email> ab@com </email>
</person>
Ssd-expression:
{person: {name: “Alan”, age: 43, email: [email protected]}}
Função de tradução T:
T(valoratomico) = valoratomico
T({l1:v1, ..., ln:vn} = <l1> T[v1] </l1> ... <ln> T[vn] </ln>
Referências XML

XML permite associar identificadores únicos a elementos, como
sendo o valor de um determinado atributo.
<state id = “s2”>
<scode> NE </scode>
<sname> Nevada </sname>
</state>
<city id = “c2”>
<ccode> CCN </ccode>
<cname> Carson City </cname>
<state-of idref =“s2”/>
</city>
Semelhanças e diferenças
<person id=“o123”>
<name> Alan </name>
<age> 42 </age>
<email> ab@com </email>
</person>
<person father=“o123”> …
</person>
father
person
{ person: &o123
{ name: “Alan”,
age: 42,
email: “ab@com” }
}
{ person: { father: &o123 …}
}
person
father
name age email
name
Alan
age
42
email
ab@com
Alan
42 ab@com
Semelhante em árvores, diferente em grafos
Ordem em XML

Em XML, existe a noção de ordem, em ssd não.
Person:{fn:”John”, ln:”Smith”} igual a
Person:{ln:”Smith”, fn:“John”}
Mas
<person><fn>John</fn>
<ln>Smith</ln></person>
Diferente de:
<person><ln>Smith</ln>
<fn>John</fn></person>

Atributos em XML não têm noção de ordem
Mistura de elementos e texto

XML pode misturar texto e elementos
<talk> Making Java easier to type and easier to type
<speaker> Phil Wadler </speaker>
</talk>

Além disto, XML tem uma panóplia de outras
construções como entidades, instruções de
processamento, comentários, etc.
Todas estas diferenças fazem com que a gestão de
dados XML seja mais complexa
Tipificação em XML
Tipificação em XML


Não é imposta
Mas
 Melhora o armazenamento
 Facilita a navegação nos dados (data guide)
 Facilita a interrogação
 Facilita a descrição e explicação dos dados
 Ajuda à optimização
 Permite a interoperabilidade entre programas
 Permite proteger os dados
Melhora o armazenamento
Company
person
Root
company
works-for
managed-by
Company
nam e
…
…
a d d re ss
…
…
c .e .o .
…
…
name
address
name
Employee
c.e.o.
o id
…
…
string
Employee
o id
…
…
nam e
…
…
m a n a g e d -b y
…
…
w o rk s-fo r
…
…
Store rest in overflow graph
Ajuda na optimização de interrogações
Bib
paper
year
int
journal
select X.title
from Bib._ X
where X.*.zip = “12345”
book
address
title
string
string
title
author
string
string
last first
zip city streetname name
string
string
string
string
select X.title
from Bib.book X
where X.address.zip = “12345”
Dados relacionais vs dados semiestruturados
Esquemas em dados relacionais



Definidos antes dos dados
Os dados têm que obedecer ao esquema
Cada instância de dados obedece exactamente a
um esquema
Esquemas em dados semi-estruturados



Definidos depois dos dados
Alguns dados podem não ter esquema associado
Uma instância de dados pode ter vários
esquemas
Quando é que o esquema é criado nos
dados semi-estruturados?

Criado pelo utilizador



Extraído dos dados


Antes ou depois dos dados
Não tem que ser único
Isto não existe em BDs relacionais
Extraído das interrogações

Como inferência de tipos em linguagens de
programação
Grafos de esquema (schema graphs)

Dado um conjunto de dados semiestruturados, podemos querer extrair o seu
esquema

O grafo de esquema especifica que arcos
são permitidos num grafo de dados

Todos os caminhos (paths) que ocorrem no grafo
de dados ocorrem no grafo de esquema
Exemplo (OEM)
Dados:
&r1
person
person
company person
manages
company
works-for
employee
&p1
&c1
&p2
&c2 c.e.o.&p3
c.e.o.
works-for
position
phone name address
namepositionworks-for
name
name
nameaddress
&s0 &s1
&s2
&s3
&s4
&s5
&s6 url &s7 &s8
&s9 description
“Smith” “Manager”
“Widget”
“Trenton”
“Jones”
description
“Sales”
&s10
eval &a5 1998
&a4
1997
&a7
&a3 task
&a6 “below target”
“www.gp.fr”
&a1
salesrep
procurement
“Paris” “Dupont”
“5552121” “Gadget”
&a2
contact
“on target”
Grafo de esquema
person
Root
company
works-for
Company
managed-by
Person
c.e.o. | employee
name | address | url name | phone | position
description
string
*
Any
Duas questões
Conformance: os dados são conforme o
esquema?
Classificação: se sim, então que objectos
pertencem a que classes?
Simulação de grafos
Definição Dois grafos edge-labeled G1, G2
Uma simulação é uma relação R entre nós:
se (x1, x2) pertencem a R, e (x1,a,y1) está em G1,
Então existe (x2,a,y2) em G2 (mesma etiqueta)
tal que (y1,y2) está em R
x1
G1
R
x2
a
a
y1
R
y2
G2
Simulação entre uma instância de
dados SS (OEM) e um grafo de
esquema
1.
Permite-se que um arco x1[l]y1 nos dados seja
2.
3.
simulado por algum arco x2[l’]y2 quando l’ é um
wild card ou uma alternância contendo l
AS raízes têm que estar na simulação rRr’ onde r
e r’ são as raízes dos dados e do grafo de
esquema, respectvamente. Diz-se que a
simulação é “rooted”
Sempre que xRy, se y é um tipo atómico então x
também tem que ser um nó atómico e ter um valor
desse tipo. Diz-se então que a simulação é
tipificada.
Exemplo
&r1
person
company person
manages
employee
&c1
&p2
c.e.o.
&p1
person
company
works-for
name position works-for
name phone
name address
&s0
“Smith”
&s1
“Manager”
&s2
&s3
&s4
“Widget”
“Trenton”
“Jones”
&s5
works-for
managed-by
&s9 description
&s6 url &s7 &s8
“Paris” “Dupont”
“5552121” “Gadget”
“Sales”
“www.gp.fr”
salesrep
&a2
contact
&a4
task
&a3
eval
&a5 1998
1997
&a6
Company
&a7
Person
c.e.o. | employee
name | address | url
&s10
&a1
person
company
position
address name
name
description
procurement
Root
works-for
&c2 c.e.o. &p3
name | phone | position
description
string
*
Any
“below target”
“on target”
Dados
Grafo de esquema
Usando Simulação
Grafo de dados D, esquema S
 conformance: encontrar a simulação máxima
R de D para S:


Notação: D  S
classificação: verificar se (x,c) estão em R

Notação: x  c
Extracção de esquema (data
guides)

Data guide é um sumário preciso e conciso do grafo
de dados




Preciso: todos os caminhos (paths) nos dados ocorrem no
data guide e vice-versa
Conciso: todos os caminhos no data guide ocorrem
exactamente uma vez
Data Guide é o grafo de esquema mais específico
para um dado grafo de dados, ou seja, existe uma
simulação do data guide para qualquer outro grafo
de esquema que o grafo de dados satisfaça
Um grafo de dados é análogo a um NFA
(nondeterministic finite state automaton)

Dado um NFA N, o data guide é análogo a um DFA
(deterministic finite state automaton) equivalente ao NFA N
Exemplo: Grafo de Dados
D=
&r
employee
employee employee
employee employee
manages
employee
employee
manages
manages
manages
manages
&p1
&p2
managedby
&p3
company worksfor worksfor
&p4
&p5
&p6
&p7
managedby
managedby
managedby
worksfor
employee
managedby
worksfor worksfor
worksfor
worksfor
worksfor
&c
&p8
Exemplo: Data Guide
Result
Sd =
Root
&r
company
managedby
employee
Employees
&p1,&p1,&p3,P4
&p5,&p6,&p7,&p8
manages
worksfor
Bosses
&p1,&p4,&p6
worksfor
Company
&c
manages
managedby
worksfor
Regulars
&p2,&p3,&p5,&p7,&p8
Referências



Serge Abiteboul, Slides of the course: “Données
Semistructurées”, Master Recherche Informatique
Paris Sud, http://www-rocq.inria.fr/~abitebou/MasterSSD/index.html
Dan Suciu, Slides on “The semistructured data
model”, CSE 590ds: Management of XML and
Semistructured Data,
http://www.cs.washington.edu/education/courses/cs
e590ds/01sp/
S. Abiteboul, P. Buneman, D. Suciu, “Data on the
Web, From Relations to Semistructured Data and
XML”, Morgan Kaufmann, 2000, (caps 2, 3 e 7)
Tópicos próximas aulas




DTD, XML Schema, XSDL
XSLT
XPath
XQuery