Título da Dissertação ou Trabalho - Ciência da Computação

Transcrição

UNIVERSIDADE FEDERAL DA FRONTEIRA SUL
CAMPUS CHAPECÓ
CURSO DE CIÊNCIA DA COMPUTAÇÃO
GEOMAR ANDRÉ SCHREINER
EXTRAÇÃO DE ESQUEMAS DE DOCUMENTOS XML:
UMA ABORDAGEM PROBABILÍSTICA
CHAPECÓ
2014
EXTRAÇÃO DE ESQUEMAS DE DOCUMENTOS XML:
UMA ABORDAGEM PROBABILÍSTICA
Trabalho de conclusão de curso de graduação
apresentado como requisito para obtenção do
grau de Bacharel em Ciência da Computação da
Universidade Federal da Fronteira Sul.
Orientador: Prof. Dr. Denio Duarte
CHAPECÓ
2014
Schreiner, Geomar André
Extração de Esquemas de Documentos XML: Uma Abordagem
Probabilística / por Geomar André Schreiner. – 2014.
80 f.: il.; 30 cm.
Orientador: Denio Duarte
Monografia (Graduação) - Curso de Ciência da Computação, Universidade Federal da Fronteira Sul, Chapecó, SC, 2014.
1. XML. 2. Extração de Esquema. 3. Probabilidade. 4. PExtract.
5. XSD. 6. Rede Bayesiana. I. Duarte, Denio. II. Título.
c 2014
Todos os direitos autorais reservados a Geomar André Schreiner. A reprodução de partes ou do
todo deste trabalho só poderá ser feita mediante a citação da fonte.
E-mail: [email protected]
EXTRAÇÃO DE ESQUEMAS DE DOCUMENTOS XML: UMA
ABORDAGEM PROBABILÍSTICA
Trabalho de conclusão de curso de graduação apresentado como requisito para obtenção do
grau de Bacharel em Ciência da Computação da Universidade Federal da Fronteira Sul.
Orientador: Prof. Dr. Denio Duarte
Aprovado em: ___\___\______
BANCA EXAMINADORA:
________________________________________
Dr. Denio Duarte - UFFS
________________________________________
Me. Marcelo Cezar Pinto - UFFS
________________________________________
Ma. Andressa Sebben - UFFS
AGRADECIMENTOS
Agradeço primeiramente a Deus por me proporcionar saúde, força e coragem nessa
caminhada.
Agradeço a minha esposa Mariane, que me apoiou e incentivou durante a elaboração
do trabalho. Que com amor e paciência soube compreender minhas dificuldades e dividir as
alegrias das horas boas. Agradeço também, aos meus pais, meu irmão e a minha irmã, por me
ajudarem e darem força nos momentos difíceis. De nada me serve o conhecimento se a minha
vida não tivesse sido abençoada com todos vocês. Obrigado!
Agradeço ao meu orientador, Prof. Dr. Denio Duarte, por sua grande ajuda no desenvolvimento desse trabalho. Obrigado por me mostrar que um orientador não deve ter só
conhecimento e competência, mas compreensão, paciência e bom senso. Obrigado, professor,
pelo conhecimento compartilhado, pela paciência, e pela orientação na realização deste trabalho. Agradeço também à Profa Andressa Sebben e ao Prof Marcelo Cezar Pinto por participarem
da banca de avaliação.
Obrigado a todos os meus colegas e amigos que, de uma forma ou de outra, me ajudaram
com o trabalho. Obrigado também a todos os meus professores que me deram o conhecimento
necessário para que esse trabalho fosse escrito. Finalmente, agradeço às demais pessoas que
me ajudaram direta e indiretamente na realização do trabalho e por falta de ajuda de minha
memória, não relato aqui.
RESUMO
Os dados que transitam pela Web são considerados dados semi estruturados. Estes
dados possuem uma estrutura heterogênea, muitas vezes extensa e incompleta. Neste contexto,
a XML (Extensible Markup Language) é uma linguagem de marcação que define a estrutura de
um documento. A XML possui uma organização hierárquica em árvore baseada em marcas o
que a torna muito flexível. Devida a flexibilidade da linguagem XML, manipular documentos
XML torna-se muito custoso quando não se possui informações sobre a sua estrutura (esquema). Este trabalho explora o uso da probabilidade como ferramenta de auxilio na extração
de esquemas. Assim, é proposto um método que realiza a extração de um esquema baseado
em uma coleção de documentos XML. O método consiste em três passos: (i) criar uma Rede
Bayesiana (redes que armazenam probabilidades), (ii) com base na rede gerar uma gramática
livre de contexto estendida e (iii) transformar a gramática em um esquema XML. A partir do
método é proposta a ferramenta pExtract , que implementa o funcionamento do método.
No decorrer do trabalho são apresentados também resultados de experimentos utilizando a ferramenta criada, demonstrando o funcionamento do método e sua eficácia. Desta forma, através
dos resultados comprava-se que o método proposto realiza a extração (em um tempo aceitável) de um esquema que contém a estrutura da coleção de documentos utilizado como entrada.
Palavras-chave: XML. Extração de Esquemas.
Bayesiana.
Probabilidade.
XML-Schema.
Rede
ABSTRACT
Data on the web are mainly semistructured. They have heteregeneous structures and they
are voluminous. XML (Extensible Markup Language) is a mark-up language that models
semistructured data. XML lets the user define his own customized markup language for
different document classes. Users can create XML documents freely. This flexibility has a
drawback: processing XML documents can be computational onerous. Schemas can be used to
create a class of XML documents and help applications to process them. In this context, XML
schema extraction allows application know XML document structure a priori allowing a better
perfomance when processing it. This work proposes an approach to schema extraction based on
probability. Our approach extracts XML schemas in three steps: (i) builds a bayesian network
from an input XML documento tree, (ii) builds a extended context free grammar from the
bayesian network built, and (iii) transform the grammar into an XML schema. We implement
a tool called pExtract based on the proposed approach. We show that pExtract extracts correct
schemas from XML documents collection in a reasonable time.
Keywords: XML. Schema extraction. Probability. XML-Schema. Bayesian Network.
LISTA DE FIGURAS
Figura 1.1 – Exemplo de documento XML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 1.2 – Exemplo de regras de um documento XML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 2.2 – Árvore hierárquica de um documento XML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 2.3 – Documento XML representado na forma de fluxo . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 2.4 – Exemplo de TG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 2.5 – Árvore criada a partir da gramática da Figura 2.4 . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 2.6 – Exemplo de declaração de uma XML Schema . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 2.7 – Segundo exemplo de declaração de uma XSD . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 2.8 – Exemplo de documento XML com referência há esquema . . . . . . . . . . . . . . . . . .
Figura 2.9 – Exemplo de declaração de um elemento complexo com conteúdo simples . . .
Figura 2.10 – Exemplo de elemento XML válido para a Figura 2.9 . . . . . . . . . . . . . . . . . . . . . . .
Figura 3.2 – DTD criada utilizando o Xtract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 3.3 – Árvore de derivação gerada a partir do documento X . . . . . . . . . . . . . . . . . . . . . . .
Figura 3.4 – Inferencia Inicial das regras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 3.5 – Figura 3.4 após a junção por contexto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 3.6 – Figura 3.5 após a junção por conteúdo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 3.7 – Figura 3.6 após a extração de tipos básicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 3.8 – XSD criada utilizando o método de Inferência Gramatical . . . . . . . . . . . . . . . . . .
Figura 3.9 – Gramática gerada pelo Algoritmo 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 3.10 – Estrutura dos módulos do XStruct (HEGEWALD; NAUMANN; WEIS, 2006)
Figura 3.11 – Gramática gerada pelo Algoritmo 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 3.12 – Resultado do módulo de extração de tipos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 3.13 – XSD criada utilizando o XSTRUCT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 3.14 – PTA gerada a partir do documento X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 3.15 – TLSM gerada a partir do documento X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 3.16 – Camadas internas TLSM Figura 3.15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 3.17 – XSD criada utilizando o XTLSM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 4.1 – Rede de Crença (COPPIN, 2010) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 4.2 – Exemplo Vida na Faculdade (COPPIN, 2010). . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 5.1 – Exemplos de árvores XML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 5.2 – Grafo Orientado Etiquetado gerado a partir da Figura 5.1 . . . . . . . . . . . . . . . . . . .
Figura 5.3 – Rede Baseada em Crença gerada a partir da Figura 5.1 . . . . . . . . . . . . . . . . . . . . .
Figura 6.1 – Estrutura dos módulos do pExtract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 6.2 – Diagrama de Classes - Modulo 1 pExtract . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 6.3 – Método startElement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 6.4 – Método endElement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 7.1 – Documento XML representando um BD de motos (Figura 2.1) . . . . . . . . . . . . .
Figura 7.2 – Rede Bayesiana gerada através de X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Figura 7.3 – eCFG gerada partir da Rede Bayesiana (Figura 7.2) . . . . . . . . . . . . . . . . . . . . . . . .
Figura 7.4 – XSD gerada pelo pExtract a partir de X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
12
15
15
16
18
18
20
21
21
23
23
25
29
31
32
32
33
33
34
36
37
39
40
41
43
44
45
46
49
50
52
53
54
61
63
64
64
68
69
71
72
LISTA DE TABELAS
Tabela 3.1 – Características métodos de extração de esquemas . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Tabela 7.1 – Resultados dos experimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
LISTA DE ABREVIATURAS E SIGLAS
DG
Directed Graph
DTD
Document Type Definition
eCFG
extended Context Free Grammar
ER
Expressão Regular
HTML
HyperText Markup Language
JSON
JavaScript Object Notation
MDL
Minimun Description Lenght
ML
Markup Language
OLT
Ordered Labeled Three
PTA
Prefix Tree Acceptor
RDF
Resource Description Framework
RTG
Regular Tree Grammar
SGML
Standard Generalized Markup Language
TG
Tree Grammars
TLSM
Two Layer State Machine
W3C
World Wide Web Consortiun
XML
Extensible Markup Language
XSD
XML-Schema
SUMÁRIO
1 INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 XML E ESQUEMAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1 ESQUEMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 Gramáticas de Árvore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.2 Linguagens de Esquema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.2.1 XML Schema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 EXTRAÇÃO DE ESQUEMAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1 XTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1 Estudo de Caso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 INFERÊNCIA GRAMATICAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1 Estudo de Caso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 MÉTODO DE MIN&CHUNG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1 Estudo de Caso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 XSTRUCT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.1 Estudo de Caso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5 XTLSM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5.1 Estudo de Caso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6 CONSIDERAÇÕES FINAIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4 PROBABILIDADE E REDES BAYESIANAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 MÉTODO PROPOSTO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6 IMPLEMENTAÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7 EXPERIMENTOS COM O PEXTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1 ESTUDO DE CASO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2 OUTROS EXPERIMENTOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8 CONCLUSÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.1 TRABALHOS FUTUROS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
REFERÊNCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
14
16
17
19
19
24
25
27
29
31
33
34
37
39
40
42
45
48
52
61
68
68
73
76
77
79
11
1 INTRODUÇÃO
Os dados que transitam na Web são considerados dados semiestruturados, ou seja, ao
contrário da forma usual de armazenamento de dados onde existe uma estrutura bem definida,
dados da Web possuem uma estrutura heterogênea, muitas vezes incompleta e extensa. Muitos
destes dados são armazenados no formato XML.
Extensible Markup Language (XML) é uma linguagem de marcação criada em 1990
pela World Wide Web Consortium (W3C). Possui uma organização hierárquica em árvore, baseada em marcas (tags) o que a torna muito flexível. Devido a esta flexibilidade, o processamento
de documentos XML dos quais não se possui conhecimento da estrutura pode ser custoso. Por
exemplo, suponha que é necessária a realização de uma consulta C em XQuery1 no documento
XML X (Figura 1.1). C é a consulta "for $y in doc (motos.xml)/motos where $moto/cor =
’azul’ return $y " que irá retornar os dados da moto que possui cor azul. Como não há informações preliminares sobre o documento, o processador de consulta irá por força bruta interpretar
o documento e encontrar a informação desejada. Após varrer completamente X, o processador
de consulta irá constatar que não existe um elemento cor, então irá retornar um conjunto vazio.
Tendo em vista a realização desta consulta, percebe-se que esta não é uma maneira eficiente de
realizá-la. Se X representasse um grande volume de dados, a consulta levaria muito tempo para
ser realizada, além do fato de a consulta não ser validada, somente executada. Assim, torna-se
essencial uma maneira eficiente de manipular estes dados.
1
<? xml v e r s i o n = " 1 . 0 " e n c o d i n g = "UTF−8" ? >
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<motos>
<moto>
<marca>Yamaha< / marca>
<modelo> F a z e r < / modelo>
< c i l i n d r a d a s >250< / c i l i n d r a d a s >
< / moto>
<moto>
<marca>Honda< / marca>
<modelo>CBX< / modelo>
< c i l i n d r a d a s >300< / c i l i n d r a d a s >
<opcional>Alerta < / opcional>
< / moto>
< / motos>
Figura 1.1 – Exemplo de documento XML
Uma maneira eficiente de manipular estes dados é utilizando um esquema. Esquema é
um conjunto de regras que são obedecidas durante a atualização dos dados de um documento
1
http://www.w3schools.com/xquery/
12
XML. Tendo conhecimento da estrutura do arquivo XML, podem ser realizadas otimizações
em consultas aos dados, bem como integrar de maneira simples documentos de diferentes bases
de dados (MELLO et al., 2000). Seguindo o exemplo, a Figura 1.2 apresenta um conjunto
de regras que define a estrutura de X, ou seja seu esquema. Assim, quando o processador de
consulta executar uma consulta validando-a inicialmente conforme um conjunto de regras (Figura 1.2), caso a consulta busque por elementos não existentes, ela será abortada. Desta forma,
o processador irá possuir informações estruturais de X, evitando que ele tenha de fazer um
reconhecimento inicial do documento e facilitando a consulta. Porém, a maioria dos documentos XML que transitam pela Web não possui um esquema associado (BARBOSA; MIGNET;
VELTRI, 2005).
motos ← moto+;
moto ← marca modelo cilindradas opcional?;
marca ← ;
modelo ← ;
cilindradas ← ;
opcional ← ;
Figura 1.2 – Exemplo de regras de um documento XML
Dados semi-estruturados são dados nos quais há sempre uma estrutura presente (implicitamente ou explicitamente), pois estes dados são auto-descritivos (MELLO et al., 2000).
Desta forma torna-se possível que dado uma coleção de documentos com algum tipo de semelhança estrutural, possa-se realizar a extração de um esquema. A área de pesquisa de extração
de esquemas trata deste problema. Existem varias técnicas propostas para realizar esta extração: por inferência gramatical (CHIDLOVSKII, 2002), máquinas de estado (AMIEL; HARRUSI; AVERBUCH, 2008), custo mínimo de descrição (XING; PARTHEPAN, ????), entre
outras (GAROFALAKIS et al., 2000; HEGEWALD; NAUMANN; WEIS, 2006). Das soluções
encontradas apenas a abordagem proposta em (PASQUALI; DUARTE, 2008) utiliza probabilidade para realizar a extração.
Assim, este trabalho tem como objetivo explorar a probabilidade como ferramenta de
auxílio na extração de esquemas. Propondo um aprimoramento para o método de extração proposto em (PASQUALI; DUARTE, 2008) que se apoia na teoria da probabilidade. O método
proposto por (PASQUALI; DUARTE, 2008) é um método teórico, ou seja, não foi implementado. O método proposto neste trabalho utiliza probabilidades através de Redes Bayesianas para
inferir uma gramática livre de contexto estendida (eCFG - extended Context Free Grammar)
13
que contém a estrutura da coleção de documentos utilizada como entrada. A partir do método
é proposta uma ferramenta denominada pExtract . O pExtract realiza a extração de um
esquema baseado em 3 módulos. O primeiro módulo lê uma coleção A de documentos XML
(possivelmente unitária) e com base nela cria uma Rede Bayesiana. O segundo módulo infere
eCFG com base nas informações contidas na rede Bayesiana. E o último módulo transforma a
eCFG em um esquema XML que possui a estrutura de A.
O restante deste trabalho está organizado da seguinte forma: O próximo capítulo apresenta a linguagem XML e sua aplicação, e apresenta também o conceito de esquema e de
linguagem de esquema. Já no Capítulo 3 são apresentadas as principais técnicas desenvolvidas
para a extração de esquemas. No Capítulo 4 será apresentada a probabilidade e o conceito de
uma rede Bayesiana baseada em crença. No Capítulo 5 é apresentado o método proposto, que
a partir de uma coleção de documentos XML extrai seu esquema. O Capítulo 6 apresenta a
forma com que o pExtract foi implementado e as peculiaridades de sua implementação. No
Capítulo 7 são apresentados alguns estudos de caso aplicados ao pExtract . Finalmente o
Capítulo 8 apresenta a conclusão deste trabalho, bem como as experiências de desenvolvimento,
resultados obtidos durante e após o desenvolvimento da ferramenta e alguns trabalhos futuros.
14
2 XML E ESQUEMAS
Uma linguagem de marcação (Markup Language - ML) é uma linguagem constituída
por um conjunto de descrições denominadas marcas (tags) que possuem uma definição gramatical e sintática. Estas marcas são utilizadas para especificar a estrutura de um conjunto de
dados, inserir comentários, ou a forma de apresentação destes dados.
Neste contexto, em 1969, foi criada a Standart Generalized Markup Language (SGML).
Na década de 80 foi adotada como padrão internacional de troca de dados eletrônicos (FAWCETT; AYERS; QUIN, 2012). O SGML tem um grande poder de representação, sendo flexível
para trabalhar com arquivos grandes e complexos. Esta flexibilidade traz uma alta complexidade
para o processamento de documentos SGML (FAWCETT; AYERS; QUIN, 2012).
O HTML (HyperText Markup Language), por exemplo, é uma aplicação do SGML, que
utiliza uma lista com marcas pré-definidas. Estas marcações são responsáveis pela forma como
serão exibidos os dados contidos no documento. O HTML é tido como uma linguagem de
simples compreensão tanto para humanos quanto para máquinas (FAWCETT; AYERS; QUIN,
2012). Possui uma formação simples constituída de dados, marcações e atributos. Contudo, o
HTML visa somente tratar da forma com que a informação é exibida, deixando de lado o que
esta representa.
Extensible Markup Language (XML) é uma linguagem de marcação publicada em 1998
pela World Wide Web Consortium (W3C), sendo um subconjunto do SGML. O XML foi criado
com intuito de simplificar o uso do SGML. Visa possuir a simplicidade do HTML e o poder de
representação contido no SGML. Ao contrário do HTML, o XML não fixa uma lista de marcações possíveis, porém especifica algumas regras, o que o faz reter grande parte da flexibilidade
do SGML ao mesmo tempo que reduz sua complexidade (FAWCETT; AYERS; QUIN, 2012).
Uma característica importante em um documento XML é que este deve possuir uma
boa formação. Para isso, todas as tags abertas devem ser fechadas. As marcações contidas
no documento são sensíveis ao contexto e o seu aninhamento deve ser respeitado. O exemplo
ilustrado na Figura 2.1 mostra um documento XML bem formado.
Outra característica importante para que um documento XML seja considerado bem
formado é a presença de uma marca mais externa, que englobe todas as demais marcas, chamada
de raiz. No exemplo da Figura 2.1 a raiz é representada pela tag "motos".
O XML propõe um modelo hierárquico onde os dados são representados na forma de
15
1
2
3
4
5
6
7
8
9
10
11
<motos>
<moto c i l i n d r a d a s = " 125 " >
<modelo>CG T i t a n < / modelo>
< / moto>
< / moto>
< / motos>
uma árvore com nós etiquetados (marcas) (DUARTE; LIMA, 2013). Sendo assim, o exemplo
da Figura 2.1 pode ser transcrito como uma árvore, onde os elementos (nomes das marcas)
representam o nó e a raiz do documento é a raiz da árvore. A Figura 2.2 mostra esta transcrição.
motos
moto
moto
marca
modelo
marca
modelo
Figura 2.2 – Árvore hierárquica de um documento XML
Além disso, um documento XML é constituído de duas partes: o prólogo e o corpo
(FAWCETT; AYERS; QUIN, 2012). O prólogo é considerado o cabeçalho do documento, possui a declaração do XML (versão, codificação, etc), comentários e algumas vezes informações
estruturais ou de processamento referentes ao documento. O corpo do documento é basicamente
composto pelos demais elementos (tags) do documento. Levando em consideração o exemplo
de documento (Figura 2.1), a primeira linha é o prólogo, e as demais o corpo do documento.
Documentos XML podem ser processados de duas formas, como árvore (Figura 2.2) ou
sequência de caracteres (Figura 2.3). A forma pela qual o documento será processado depende
da forma como o mesmo é tratado. Se houver a necessidade de navegar pelo documento diversas
vezes, a representação em árvore deve ser utilizada. No entanto, se apenas uma leitura dos dados
for suficiente, a representação em fluxo tem maior eficiência (DUARTE; LIMA, 2013).
Nesta seção foi apresentada de forma breve a linguagem XML e algumas de suas características. O XML é uma linguagem de marcação de dados, criada para simplificar o uso
do SGML. Documentos XML devem obrigatoriamente apresentar uma boa formação, ou seja,
16
1
<? xml v e r s i o n = " 1 . 0 " e n c o d i n g = "UTF−8" ? > <motos> <moto
c i l i n d r a d a s = " 125 " > <marca>Honda< / marca> <modelo>CG
T i t a n < / modelo> < / moto> <moto c i l i n d r a d a s = " 250 " > <marca>
Yamaha< / marca> <modelo> F a z e r < / modelo> < / moto> < / motos>
Figura 2.3 – Documento XML representado na forma de fluxo
deve existir uma tag mais externa denominada de raiz, o aninhamento entre as tags deve ser
respeitado e todas as tags abertas devem ser fechadas. Opcionalmente uma instância XML também pode passar por um processo de validação. A validação garante que os dados presentes no
documento seguem um conjunto de regras. As regras responsáveis pela validação devem definir
a estrutura do documento. O conjunto destas regras é chamado de esquema. Esquema é o tema
da próxima seção.
2.1
ESQUEMA
Como visto anteriormente, XML é um padrão de representação para dados semi-
estruturados. Sua organização segue um modelo hierárquico em forma de árvore com nós
etiquetados. Não possui uma estrutura fixa, de forma a deixar livre para os usuários a criação e alteração do documento.
Um esquema é um conjunto de regras que define a estrutura de um banco de dados
ou de um documento qualquer (FAWCETT; AYERS; QUIN, 2012). Segundo (DUARTE;
LIMA, 2013), se for fixada uma estrutura para elementos de uma instância XML este documento não poderá mais ser atualizado livremente, sendo dependente de uma validação. Essa
restrição imposta sobre o documento é um esquema que deve ser respeitado. Um documento
XML é considerado válido quando respeita as restrições impostas a ele. A validade não é uma
característica obrigatória de um documento XML (MELLO et al., 2000).
Um esquema restringe as operações que serão realizadas em um determinado documento. Essa restrição faz com que haja perda de parte da flexibilidade que a XML proporciona
aos seus usuários (FAWCETT; AYERS; QUIN, 2012). Porém, ganha-se em outros aspectos
como: descrição dos dados, auxílio a consulta sobre os dados, otimização de consultas, eficiência no armazenamento dos dados, criação de classes de documentos, facilidade na transformação dos documentos para documentos diferentes e facilita a integração de dados entre diferentes
sistemas (DUARTE; LIMA, 2013; MELLO et al., 2000).
Quando um esquema é gerado para um documento XML é criada uma classe e todos os
17
documentos que são válidos para o esquema pertencem a esta mesma classe (DUARTE; LIMA,
2013). Criando classes para documentos pode-se agrupá-los e os armazenar em conjunto de
forma a gerar ganhos no desempenho de consultas (VIJAYEANDRA, 2011).
A sintaxe da XML permite associar um esquema a um documento de duas formas: internamente ou externamente (FAWCETT; AYERS; QUIN, 2012). É declarado internamente,
quando as definições do esquema estão no prólogo do documento. Esta abordagem é usada
quando o esquema não é muito extenso. Também é usada quando não há necessidade de compartilhar o esquema com outros documentos. Já a definição externa consiste em informar no
prólogo do documento uma referência a um arquivo externo onde estão as definições do esquema.
Para a descrição dos esquemas é utilizada uma linguagem de esquemas (DUARTE;
LIMA, 2013). Ela permite que se possa criar regras para facilitar a compreensão das relações
entre os diversos elementos de uma instância XML. Assim, seu uso facilita a compreensão e o
uso do documento XML para usuários e aplicativos (DUARTE; LIMA, 2013).
Apesar de existir um padrão de representação computacional para documentos XML
(árvores ou fluxo), esquemas XML não possuem um padrão de representação. As mais utilizadas são gramática regular de árvore (RTG - Regular Tree Grammar), grafo dirigido etiquetado
(DG - Directed Graph) e representações mistas (DUARTE; LIMA, 2013). No entanto, árvores
XML são geradas com maior precisão utilizando gramáticas regulares de árvore (DUARTE;
LIMA, 2013).
A seguir, será apresentado de forma breve o que são gramáticas de árvore, para que se
possa entender de que forma estas gramáticas podem representar a estrutura de um documento
XML. Então serão apresentadas as linguagens de esquema, com foco na XML Schema que será
utilizada na implementação da ferramenta.
2.1.1
Gramáticas de Árvore
Gramáticas de árvore (TG -Tree Grammars) são mecanismos para gerar árvores (DU-
ARTE; LIMA, 2013). Como dito anteriormente, documentos XML podem ser vistos como
árvores, sendo assim, uma TG que descreve um documento XML pode ser considerada um esquema. Uma instância XML construída a partir de uma TG é considerada válida, pois respeita
as restrições impostas pela TG.
Uma gramática regular de árvore pode ser considerada uma quádrupla G = (N, Σ, P, I),
18
onde N é o conjunto de símbolos não terminais, Σ são os símbolos terminais, P são as regras de
formação ou produções (X ← a(Y ) , a ∈ Σ e Y é uma expressão regular sobre N) e I o conjunto
de símbolos iniciais.
N = {motos, moto1, moto2, marca, modelo, dado}
Σ = {motos, moto, marca, modelo, dado}
P ={
motos ←motos((moto1|moto2)+ );
moto1 ←moto (marca, modelo);
moto2 ← moto (modelo);
marca ← marca (dado);
modelo ← modelo (dado);
dado ← dado (dado);
}
I = {motos}
Figura 2.4 – Exemplo de TG
Figura 2.5 – Árvore criada a partir da gramática da Figura 2.4
A Figura 2.4 traz o exemplo de uma gramática de árvore. Na figura os símbolos terminais estão grifados em negrito e os não-terminais em itálico. Os símbolos terminais representam
as tags contidas no documento XML. O símbolo terminal dado, visa representar qualquer tipo
de dado, seja ele inteiro, string, data ou qualquer outro.
A árvore apresentada na Figura 2.5 é um exemplo de árvore gerada pela gramática apresentada na Figura 2.4. O símbolo inicial da gramática é o não terminal motos. Por ser o símbolo
inicial da gramática este deve gerar a raiz da árvore. Este símbolo possui uma regra de produção onde há o terminal motos (raiz da árvore) e um ou mais filhos gerados pela regra dos não
terminais moto1 ou moto2. A regra de moto1 produz o terminal moto e deve gerar dois filhos
marca e modelo. Percebe-se no exemplo que o filho da esquerda do nó raiz foi gerado pela regra
moto1. Já o filho mais a direita, foi gerado pela regra moto2. Esta regra, segundo o exemplo de
gramática, só possui um filho gerado pela produção do não terminal modelo.
A validação de um documento XML para determinado esquema é o processo de reconhecimento de uma árvore segundo sua gramática. Esta validação (reconhecimento) é feita
19
através de autômatos de árvore. Este trabalho não tem como foco a validação de documentos
XML, porém mais informações sobre o assunto podem ser encontradas em (DUARTE; LIMA,
2013; COMON et al., 2007; MILO; SUCIU; VIANU, 2000; PAPAKONSTANTINOU; VIANU,
2002).
2.1.2
Linguagens de Esquema
Informações armazenadas em documentos XML são estruturadas a partir de marcações
que envolvem texto, o que define a estrutura da instância. A interpretação destes dados, devido à
flexibilidade do XML, torna sua implementação complexa. Uma linguagem de esquema permite
estabelecer regras que facilitem a interpretação dos dados contidos no documento (DUARTE;
LIMA, 2013).
Um esquema define regras para a validação de informações presentes em um documento
XML. Sendo assim, tem-se a garantia que dados provenientes de fontes diferentes possuem a
mesma estrutura, se os documentos forem válidos para um mesmo esquema. Um esquema pode
ser compartilhado em um determinado grupo, o que facilita a troca de informações entre todas
as partes (DUARTE; LIMA, 2013).
Existem duas principais linguagens de esquema, a DTD (Document Type Definition) e
a XML Schema. A DTD foi muito utilizada até o ano de 2004 (BEX; NEVEN; BUSSCHE,
2004), porém hoje em dia está caindo em desuso (FAWCETT; AYERS; QUIN, 2012). Mais
informações sobre o DTD podem ser obtidas em (FAWCETT; AYERS; QUIN, 2012). A XML
Schema tem seu uso recomendado pela W3C. Neste trabalho, será utilizada a XML Schema,
que será descrita com mais detalhes na próxima seção.
2.1.2.1
XML Schema
A XML Schema (XSD - XML Schema Definition) foi proposta pela Microsoft e tem
seu uso recomendado pela W3C desde 2001. Sua especificação técnica foi dividida em dois
documentos, um contendo a estrutura do documento e o outro contendo os tipos de dados. Tem
como seu principal objetivo criar restrições e definir a estrutura de uma instância XML com
foco na validação (DUARTE; LIMA, 2013).
Os elementos presentes em uma XML Schema são classificados em dois tipos: simples
e complexos (DUARTE; LIMA, 2013; FAWCETT; AYERS; QUIN, 2012). Os simples são os
tipos de dados como strings, inteiros, datas e não possuem subelementos. Já os complexos são
20
aqueles que possuem subelementos ou atributos.
Para atrelar um documento XML a uma XSD, deve haver no prólogo do documento
uma linha referenciando o local onde se encontra o documento XSD. A Figura 2.6 representa
um esquema que está armazenado em um documento nomeado "motos.xsd". Na Figura 2.8 é
apresentada uma instância XML que respeita as validações impostas pelo esquema (Figura 2.6).
Percebe-se que na linha 2 da Figura 2.8 é feita a ligação com o esquema, onde são usados
dois parâmetros, o primeiro "xmlns:xsi" é a forma dos namespaces que serão utilizados, e o
segundo (xsi:noNamespaceSchemaLocation) é o local onde se encontra o arquivo do esquema
sem vínculo a namespaces. A Figura 2.7 e Figura 2.6 apresentam o mesmo esquema, apenas
declarado de forma diferente.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
<? xml v e r s i o n = " 1 . 0 " ? >
< x s : s c h e m a v e r s i o n = " 1 . 0 " x m l n s : x s = " h t t p : / / www . w3 . o r g / 2 0 0 1 /
XMLSchema " >
< x s : e l e m e n t name= " m o t o s " >
<xs:complexType>
< x s : e l e m e n t name= " moto " >
<xs:complexType>
<xs:sequence>
< x s : e l e m e n t name= " marca " t y p e = "
xs:string " />
< x s : e l e m e n t name= " modelo " t y p e = "
xs:string " />
< x s : e l e m e n t name= " o p c i o n a l " t y p e = "
x s : s t r i n g " minOccurs=" 0 "
maxOccurs = " unbounded " / >
</ xs:sequence>
< x s : a t t r i b u t e name= " c i l i n d r a d a s " u s e = "
r e q u i r e d " type =" x s : i n t e g e r " / >
< / xs:complexType>
</ xs:element>
< / xs:complexType>
</ xs:element>
< / xs:schema>
Figura 2.6 – Exemplo de declaração de uma XML Schema
Namespaces servem para delimitar um escopo aos elementos ou atributos, podendo ser
criado na definição de um esquema XML e mantido externamente. Um esquema é um vocabulário XML cujos nomes de atributos e de elementos pertencem a um namespace. O uso de
namespaces permite que elementos de vocabulários diferentes mas com mesmo nome possam
ser usados simultaneamente sem que ocorram conflitos (DUARTE; LIMA, 2013; FAWCETT;
AYERS; QUIN, 2012). Na Figura 2.6, não é feita nenhuma referência ao uso de namespaces
externos. Na linha 2 dessa figura, é feita a declaração do uso padrão dos namespaces contidos
em http://www.w3.org/2001/XMLSchema, sendo identificados por xs.
Na linha 3 da Figura 2.6, é declarado o elemento motos. Um elemento pode ser de-
21
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
<? xml v e r s i o n = " 1 . 0 " ? >
< x s : s c h e m a v e r s i o n = " 1 . 0 " x m l n s : x s = " h t t p : / / www . w3 . o r g / 2 0 0 1 /
XMLSchema " >
<xs:complexType>
< x s : e l m e n t r e f = " moto " / >
< / xs:complexType>
</ xs:element>
<xs:complexType>
<xs:sequence>
< x s : e l e m e n t r e f = " marca " / >
< x s : e l e m e n t r e f = " modelo " / >
< x s : e l e m e n t r e f =" o p c i o n a l " minOccurs=" 0 "
</ xs:sequence>
< x s : a t t r i b u t e name= " c i l i n d r a d a s " u s e = " r e q u i r e d "
type =" x s : i n t e g e r " / >
< / xs:complexType>
</ xs:element>
< x s : e l e m e n t name= " marca " t y p e = " x s : s t r i n g " / >
< x s : e l e m e n t name= " modelo " t y p e = " x s : s t r i n g " / >
< x s : e l e m e n t name= " o p c i o n a l " t y p e = " x s : s t r i n g " / >
21
22
< / xs:schema>
Figura 2.7 – Segundo exemplo de declaração de uma XSD
1
2
3
4
5
6
7
8
9
10
11
12
13
14
<motos x m l n s : x s i = " h t t p : / / www . w3 . o r g / 2 0 0 1 / XMLSchema−i n s t a n c e
" xsi:noNamespaceSchemaLocation =" motos . xsd " / >
<motos>
<modelo>CG T i t a n < / modelo>
< / moto>
< o p c i o n a l > F r e i o ABS< / o p c i o n a l >
<opcional>Carenagens< / opcional>
< / moto>
< / motos>
Figura 2.8 – Exemplo de documento XML com referência há esquema
clarado de duas formas: globalmente ou localmente. Um elemento é declarado globalmente
quando é definido diretamente no elemento raiz, estando assim no nível mais elevado do esquema. Este caso é apresentado na Figura 2.7 onde todos os elementos são declarados globalmente e apenas referenciados dentro dos outros. Assim, um elemento global pode ser referenciado em qualquer parte do esquema (i.g., elemento moto na linha 8 - Figura 2.7). Um elemento
local é definido como filho de qualquer outro elemento e só pode ser usado dentro do escopo de
seu pai. Na Figura 2.6 o elemento motos é definido globalmente e marca localmente.
Um elemento pertencente a uma XML Schema pode ser de dois tipos, simples ou complexo. Um elemento simples é aquele que não possui filhos nem atributos. Na Figura 2.6, os
elementos marca, modelo e opcional são elementos simples. Elementos complexos são os que
22
possuem filhos e/ou atributos como motos e moto.
Elementos simples são definidos através do atributo type (linha 8 da Figura 2.6). Elementos complexos são definidos através do elemento xs:complexType (linha 6 da Figura 2.6)
que, por sua vez, pode ser de dois tipos: com conteúdo simples ou conteúdo complexo. O
conteúdo complexo, possibilita especificar cardinalidade, delimitadores de grupo e conteúdos
mistos.
A cardinalidade permite limitar o número de aparições de um elemento. Essa restrição é
feita diretamente na declaração de um elemento através dos atributos maxOccurs e minOccurs.
O atributo maxOccurs limita o número máximo de repetições do elemento no decorrer do documento. Pode assumir valores inteiros positivos maiores que 0 ou o valor "unbounded"que deixa
livre o número de aparições. Já o atributo minOccurs limita o número mínimo de repetições de
um elemento. Pode assumir qualquer valor inteiro positivo, sendo o 0 utilizado para representar
um elemento opcional. O valor default para ambos os atributos é 1.
Sendo assim, no exemplo ilustrado pela Figura 2.6, o elemento moto deverá aparecer
pelo menos uma vez em um documento válido para o esquema. Já o elemento opcional pode
ou não aparecer como filho do elemento moto.
Os delimitadores de grupo delimitam a ordem e sequência que subelementos devem
aparecer no documento. Existem basicamente três elementos de grupo: sequence, choice, all.
O elemento sequence (linha 6 da Figura 2.6) faz com que todos os subelementos dele apareçam
na mesma ordem que foram declarados, respeitando sempre a cardinalidade imposta. O choice é
o operador "ou"e é escolhido apenas um dos subelementos presentes neste grupo. Já o elemento
all faz com que seus subelementos apareçam sem restrição de ordem.
Conteúdos complexos mistos permitem a "mistura" de elementos e texto. Um elemento
deste grupo permite que haja elementos de qualquer tipo entre o texto. Para que um elemento
seja considerado misto, ele deve apresentar o atributo mixed com o valor true. O valor default
deste atributo é false.
O elemento complexo com conteúdo simples permite que um elemento seja composto
de texto e de atributos. A declaração é feita através do elemento xs:simpleContent seguido da
definição se este representa uma extensão ou uma restrição. Quando o elemento é do tipo extensão, podem ser adicionados atributos, enquanto no tipo de restrição não permite adição de novos
atributos, mas permite que os atributos de base (elementos simples ou complexo com conteúdo
simples) sejam limitados. A Figura 2.9 é um exemplo da declaração de um elemento deste tipo.
23
Percebe-se através dela que o elemento modelo tem como filho apenas texto e possui também
um atributo tipo. Um elemento XML válido para esta restrição é apresentado na Figura 2.10.
1
2
3
4
5
6
7
8
9
< x s : e l e m e n t name= " modelo " >
<xs:complexType>
<xs:simpleContent>
< x s : e x t e n s i o n base =" x s : s t r i n g ">
< x s : a t t r i b u t e name= " t i p o " t y p e = " x s : s t r i n g " /
>
</ xs:extension>
</ xs:simpleContent>
< / xs:complexType>
</ xs:element>
Figura 2.9 – Exemplo de declaração de um elemento complexo com conteúdo simples
1
2
3
<modelo t i p o = " c u s t o m " >
Kansas
< / modelo>
Figura 2.10 – Exemplo de elemento XML válido para a Figura 2.9
Atributos são definidos utilizando o elemento xs:attribute. Para definição de um atributo é necessário somente indicar um nome e o seu tipo. Atributos podem ser declarados de
duas formas: globalmente ou localmente. Quando declarado globalmente (na raiz do documento) é compartilhado por todos os elementos contidos no esquema. É definido localmente
quando está dentro de um tipo complexo de elemento, ficando restrito ao escopo deste elemento.
Para que um elemento seja obrigatório é necessário que em sua definição conste o atributo
use="required". Na Figura 2.6 linha 12, é declarado o atributo cilindradas que é obrigatório, já
na Figura 2.9 o atributo tipo não é obrigatório.
Nesta seção foram apresentadas as principais características da linguagem XML
Schema. As características foram escolhidas conforme a relevância no uso neste trabalho. Mais
informações sobre XML Schema podem ser encontradas em (DUARTE; LIMA, 2013; FAWCETT; AYERS; QUIN, 2012; HAROLD, 2004). Foram apresentadas também algumas das
vantagens do seu uso, porém como já dito, muitos dos documentos disponíveis na internet não
possuem um esquema associado. Se os documentos não vem acompanhados de um esquema
é necessário que se realize a extração do mesmo. O próximo capítulo apresenta algumas das
técnicas propostas por outros autores para extração de esquemas.
24
3 EXTRAÇÃO DE ESQUEMAS
Como visto nas seções anteriores, um esquema é um conjunto de informações referentes
a estrutura de um documento. Seu uso é indicado pois permite a definição de um conjunto de
regras que deverão ser obedecidas durante a atualização dos dados presentes em uma instância
de um documento XML. Com base no esquema de uma coleção de documentos XML podem
ser realizadas otimizações na consulta de dados e facilitar a integração dos dados gerados por
aplicações distintas.
Muitas empresas utilizam documentos XML para realizar integrações entre os dados de
aplicações distintas. Se não existe um esquema que defina os dados presentes nos documentos o
seu processamento torna-se menos eficiente. Com o uso de um esquema tem-se a certeza que os
dados presentes em determinado documento respeitam a estrutura imposta pelo esquema. Desta
forma, o processamento dos dados torna-se mais simples e a integração dos dados torna-se mais
simples e coesa.
O esquema também possibilita que haja um ganho de desempenho na execução de consultas sobre dados armazenados em documentos XML. Se é executada uma consulta em um
documento XML, o processador de consulta deve fazer uma busca por chaves dentro do documento para ver se a consulta pode ou não ser executada. Se a consulta for realizada sobre
documentos dos quais o esquema é conhecido, a validação da consulta é feita sobre o esquema,
e se a estrutura da consulta for válida ela é aplicada sobre os dados (MELLO et al., 2000).
Não existe nenhuma regra que obrigue documentos XML a serem acompanhados de
um esquema (CHIDLOVSKII, 2001). Assim a maioria dos documentos encontrados na WEB
não possuem um esquema associado a eles ou o documento não respeita o esquema que o
acompanha (BARBOSA; MIGNET; VELTRI, 2005). O que torna muito pertinente que através
de uma determinada coleção de documentos XML (mesmo que unitária) seja possível a extração
de um esquema que descreva a estrutura da coleção.
Segundo (GAROFALAKIS et al., 2000), seres humanos fazem a melhor inferência possível de um esquema para determinada coleção de documentos XML. Evidentemente esta abordagem torna-se impraticável para documentos extensos ou coleções com muitos documentos.
Sendo assim, é necessária uma ferramenta que realize a extração de forma automática ou semiautomática.
Muitas pesquisas vem sendo desenvolvidas na área de extração de esquemas (GAROFA-
25
LAKIS et al., 2000; CHIDLOVSKII, 2001; MIN; AHN; CHUNG, 2003; HEGEWALD; NAUMANN; WEIS, 2006; AMIEL; HARRUSI; AVERBUCH, 2008). Diversas abordagens foram
propostas para solucionar este problema. Esta seção apresenta cinco métodos de extração de
esquemas encontrados na literatura: XTRACT (GAROFALAKIS et al., 2000), Inferência Gramatical (CHIDLOVSKII, 2001), Min&Chung (MIN; AHN; CHUNG, 2003), XStruct (HEGEWALD; NAUMANN; WEIS, 2006) e XTLSM (AMIEL; HARRUSI; AVERBUCH, 2008).
A metodologia de apresentação segue os seguintes passos: o método é brevemente descrito
com o seu pseudo-código e, em seguida, um exemplo do funcionamento é apresentado. Todos os métodos estudados utilizam uma coleção de documentos XML como entrada e, para
fins de simplificação, neste trabalho, a coleção de documentos é representada por apenas um
documento XML.
O documento XML X da Figura 3.1 é utilizado como entrada para apresentar todos os
métodos aqui discutidos.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
<motos>
<opcional > F r e i o Disco< / opcional >
<revisao>
<km>15000 < /km>< v a l o r > 3 5 0 , 0 0 < / v a l o r >
<km>35000 < /km>< v a l o r > 6 0 0 , 0 0 < / v a l o r >
</ revisao>
< / moto>
<moto>
< o p c i o n a l >Abs< / o p c i o n a l >
<revisao>
<km>1000 < /km>< v a l o r > 1 7 , 0 0 < / v a l o r >
<km>5000 < /km>< v a l o r > 3 5 , 0 0 < / v a l o r >
<km>10000 < /km>< v a l o r > 3 2 0 , 0 0 < / v a l o r >
</ revisao>
< / moto>
<modelo> B i z < / modelo>
<ano_modelo>2013 < / ano_modelo>
< / moto>
< / motos>
3.1
XTRACT
Esta seção apresenta o XTRACT (GAROFALAKIS et al., 2000), um método de extração
que constrói uma DTD que representa a estrutura do documentos XML dado como entrada. O
26
Algoritmo 1 apresenta o seu funcionamento.
O método pode ser resumido em três etapas principais: (i) o documento XML é transformado em um conjunto de sequências de símbolos, para cada elemento de X são geradas
sequências que representam a ocorrência de seus sub-elementos, a partir dessas sequências são
construídas expressões regulares (ER) denominadas de candidatas, (ii) as candidatas são otimizadas e simplificadas através do processo de fatoração, e (iii) do conjunto gerado é escolhida
uma das candidatas para compor a DTD final, essa escolha é feita baseada no princípio do Minimun Description Lenght (MDL) que seleciona a candidata que melhor descreve estruturalmente
a sequência no menor tamanho possível (em bytes).
A primeira etapa do método é chamada de Generalização (Generalization). Nesta etapa
são geradas diversas ERs candidatas, das quais uma será selecionada para fazer parte da DTD
final. Para cada uma das sequências presentes na entrada são executados alguns passos que
transformarão a sequência em uma ER. Inicialmente, a sequência é analisada de forma a encontrar candidatas que utilizem a concatenação de símbolos. Este processo é repetido algumas
vezes, sendo que em cada vez é gerada uma nova sequência S, onde é permitido um número r
de repetições de um símbolo na sequência. Então, passa-se a tentar construir S’ a partir de S
utilizando o operador "ou". Cada nova candidata que este método gerar é adicionada as candidatas para a DTD. Se o método não conseguir gerar S’, ele retorna S. Desta forma serão geradas
diversas pequenas ERs, que serão passadas como entrada para o módulo de fatoração.
A próxima etapa a ser executada é o da fatoração (Factoring). Nesta etapa são executados alguns métodos de simplificação sobre as candidatas afim de obter as menores possíveis.
Este processo pode ser muito custoso tendo em vista o número de candidatas e o tamanho de
cada uma delas. Sendo assim, o método de fatoração do XTRACT seleciona candidatas para a
fatoração com base em duas regras: (1) candidatas que possuem prefixos e sufixos comuns entre
as regras, (2) candidatas que tenham a mínima semelhança possível com ERs já selecionadas.
A última etapa a ser executada é a de Minimização que utiliza o principio do MDL para
escolher qual das candidatas melhor descreve as sequências apresentadas como entrada. Nesta
etapa é feita a escolha da candidata que representa totalmente o elemento do documento XML
utilizado como entrada e que possui o menor custo de MDL. O MDL usado pelo XTRACT é
baseado no tamanho em bytes que a ER candidata possui e o tamanho da sequência de bytes
utilizados para descrevê-la em termos de DTD (GAROFALAKIS et al., 2000). Sendo assim,
durante a execução desta etapa é feito o cálculo do MDL de todas as candidatas geradas, e é feita
27
a escolha da candidata que possuir o menor MDL. Caso o calculo do MDL cause um empate, a
candidata que estiver na primeira posição da lista será selecionada.
O Algoritmo 1 apresenta um pseudocódigo do método, a seguir é apresentado um estudo
de caso para ilustrar o seu funcionamento.
Algoritmo 1: XTRACT
Entrada: documento XML
Saída: DTD
1 elementos ← extraiElementos(Entrada);
2 foreach elemento in elementos do
3
sequenciaElementos ← extraiSeqElementos(elemento);
4
foreach sequencia in sequenciaElementos do
5
adiciona sequencia em candidatas;
6
for r in (2,3,4) do
7
geraCandidataE(sequencia, r, candidata);
8
geraCandidatasOu(candidata,candidatas);
9
end
10
end
11
fatora(candidatas);
12
menorMDL ← calculaMDL(candidatas[0]);
13
DTD ← candidatas[0];
14
i ← i + 1;
15
while i < tamanho(candidatas) do
16
if calculaMDL(candidatas[i]) < menorMDL then
17
menorMDL ← calculaMDL(candidatas[i]);
18
DTD ← candidatas[i];
19
end
20
i ← i + 1;
21
end
22
adiciona DTD em DTDFinal;
23 end
24 return DTDFinal
3.1.1
Estudo de Caso
Neste estudo de caso é utilizado o documento X (Figura 3.1) para demonstrar a execução
do Algoritmo 1.
Inicialmente, é feita a busca dos elementos de X (linha 1). Cada tag de X é considerada um elemento. Sendo assim, a variável elementos receberá todos os elementos de X ( i.e.
motos, moto, marca, modelo, opcional, revisao, km, valor, ano_modelo). Para cada um dos
elementos de elementos (linha 2) é executada a extração de sequências (linha 3). A extração
28
das sequências, basicamente, é o processo de retirada dos elementos contidos em um determinado elemento. Por exemplo, para o elemento motos a sequência correspondente é {moto moto
moto }, pois a tag motos contém apenas 3 elementos moto, e aparece uma vez. Sendo assim, a
variável sequenciaElementos recebe { moto moto moto}(linha 3).
Para cada sequência de elementos de sequenciaElementos serão construídas ERs candidatas a serem elementos da DTD (linhas 4 a 10). Essa etapa do método é chamada de generalização. Inicialmente, a sequência é adicionada ao vetor de candidatas (linha 5), então é invocado
3 vezes o método "geraCandidataE" variando o parâmetro r em 2,3 e 4 que representa o número de vezes que um símbolo pode se repetir. Este método irá varrer a sequência com o intuito
de criar expressões regulares que correspondam à estrutura do elemento candidato. Assim, a
primeira candidata c1 a ser gerada (r = 2) será moto*. c1 é passada para o método geraCandidatasOu que tentará gerar outras candidatas baseadas em c1 , utilizando o operador "ou". Todas
as candidatas geradas são adicionadas ao vetor de candidatas. Passando c1 como parâmetro
para o método, será obtida como resposta a candidata a própria c1 pois não é possível obter mais
candidatas utilizando o operador "ou". Outra candidata gerada pelo método "geraCandidataE"
(com r = 3) é moto moto*, que ao passar pelo método geraCandidataOu não sofreria alterações. r = 4 não gera nenhuma nova candidata. Sendo assim, ao final da etapa de generalização
para a sequência { moto moto moto} seriam geradas as candidatas: { moto moto*, moto*}. Para
a maior parte das candidatas geradas a partir dos elementos de X, não serão feitas alterações ao
passar pelo método geraCandidataOu exceto a candidata (km valor)*, onde o método retornará
as candidatas (km valor)*, (km | valor)*.
A próxima etapa a ser executada é a da fatoração onde as candidatas geradas são submetidas a processos de simplificação (linha 11). Basicamente, o sistema de fatoração irá varrer
todas as candidatas e simplificá-las, podendo até criar novas candidatas unindo ou construindo
novas candidatas. Passando para o módulo de fatoração as candidatas obtidas anteriormente, a
candidata moto moto* será eliminada, pois após fatorada esta irá ficar igual a candidata restante
moto*. Ao fim desta etapa a variável candidatas terá somente a candidata moto*. Para a maior
parte dos conjuntos de candidatas que serão geradas ao longo da execução do exemplo, a etapa
de fatoração não fará grande mudanças, exceto quando esta receber as candidatas { marca modelo, modelo ano_modelo }, quando o módulo deve devolver como resposta a candidata (marca
| modelo | ano_modelo).
A última etapa a ser executada é onde será feita a eleição da candidata que participará dos
29
elementos que constituem a DTD final. Esta eleição, como já dito, é feita utilizando o princípio
do MDL. Como a variável candidatas contém apenas uma candidata então será a eleita para
fazer aparte da DTD final. Sendo assim, será calculado o MDL para a primeira candidata que
estiver no vetor de candidatas (linha 12 - i.e. moto*, que é 32 (pois moto* ocupa 5 bytes para
ser armazenada mais 27 bytes dele convertido em elemento da DTD). Como não existem mais
candidatas, a candidata é descrita em termos de DTD e é adicionada a DTD final (linhas 13 e
22 respectivamente). O elemento resultante deste passo é apresentado na Figura 3.2 (linha 2).
Para a maior parte dos elementos de X apenas uma candidata será passada para o módulo do
MDL. Porém a execução do algoritmo gerará as candidatas (km valor)*, (km | valor)* para o
elemento revisao, a eleita entre estas será (km valor)* pois possui um custo de MDL menor que
sua concorrente.
O processo é repetido para todos os elementos que foram extraídos do documento de
entrada. Após a execução de todas as etapas para todos os elementos a DTD obtida será a apresentada pela Figura 3.2. Percebe-se que o método faz a extração de um esquema que descreve
a estrutura do documento XML utilizado como entrada, porém não se preocupa com a extração
de atributos e de tipos básicos dos elementos.
1
2
3
4
5
6
7
8
9
10
< !ELEMENT motos ( moto ∗ ) >
< !ELEMENT moto ( ( marca | modelo | o p c i o n a l | r e v i s a o |
ano_modelo ) ∗ ) >
< !ELEMENT marca ( #PCDATA) >
< !ELEMENT modelo ( #PCDATA) >
< !ELEMENT o p c i o n a l ( #PCDATA) >
< !ELEMENT r e v i s a o (km, v a l o r ) >
< !ELEMENT km( #PCDATA) >
< !ELEMENT v a l o r ( #PCDATA) >
< !ELEMENT ano_modelo ( #PCDATA) >
Figura 3.2 – DTD criada utilizando o Xtract
3.2
INFERÊNCIA GRAMATICAL
O método descrito em (CHIDLOVSKII, 2001) é baseada em inferência gramatical, ou
seja, dado um conjunto de entrada é inferida uma gramática que deve descrever todo o conjunto
de dados. Este método consiste na execução de 3 passos: (i) os documentos são representados
em forma de uma árvore, (ii) é feita a indução de uma gramática com base na árvore gerada no
primeiro passo e (iii) a gramática é transformada em uma XSD.
Inicialmente, é feita uma transformação do documento XML em uma árvore t, sendo
30
que, o início e o fim das tags delimitam as subárvores de t (CHIDLOVSKII, 2001).
A segunda etapa é dividida em quatro passos: (i) geração dos símbolos não terminais
para cada um dos elementos de t que possuírem filhos, e também são geradas produções de símbolos não terminais que irão representar os nodos de t, (ii) é feita uma junção entre as regras de
maneira a levar em conta seu contexto, o que irá eliminar ambiguidades existentes na gramática,
(iii) é realizada uma análise para verificar se terminais não estão sendo tratados em regras diferentes, tentando uní-los em uma única regra, realizando assim uma junção baseada no conteúdo
e (iv) é feita uma análise nos elementos considerados simples, afim de extrair os tipos de dados
de cada um. Sendo assim, ao cumprir a segunda etapa do método será gerada uma gramática livre de contexto estendida (eCFG - extended context-free grammar) (BRÜGGEMANN-KLEIN;
WOOD, 1998). A eCFG é uma gramática livre de contexto que aceita expressões regulares
a direita das produções (BRÜGGEMANN-KLEIN; WOOD, 1998). A gramática gerada irá
descrever a árvore do documento usado como entrada.
Na última etapa do método, é feita a conversão da eCFG para uma XSD. Esta conversão
é feita com base nas regras da eCFG, e com algumas informações armazenadas ao longo das
etapas anteriores, como o número de ocorrência de um determinado terminal.
O Algoritmo 2 apresenta o funcionamento do método, e a seguir é apresentado o estudo
de caso.
Algoritmo 2: Inferência Gramatical
Saída: XSD
1 arvoreDerivacao ← criarArvore(Entrada);
2 eCGF ← infereGramaticaInicial(arvoreDerivacao);
3 juncaoNaoTerminaisPorContexto(eCFG);
4 juncaoNaoTerminaisPorConteudo(eCFG);
5 foreach regra in eCFG do
6
foreach elemento in regra.producao do
7
if elemento.valor == "Any" then
8
extraiTipoPrimitivo(elemento, Entrada);
9
end
10
end
11 end
12 esquema = converteECFGParaXMLSchema(eCFG);
31
3.2.1
Estudo de Caso
Como no estudo de caso anterior, será utilizado o documento X (Figura 3.1) para ilustrar
o funcionamento do Algoritmo 2.
Inicialmente, é feita a conversão de X para uma representação em árvore (linha 1). A
árvore gerada será uma árvore de derivação de um gramática livre de contexto sem os seus não
terminais. A árvore t1 da Figura 3.3 representa a árvore gerada a partir de X. Para maior clareza
algumas subárvores de t1 foram omitidas sendo expressas pelo pontilhado presente na figura.
motos
motos
motos
motos
...
...
marca
modelo
revisao
opcional
km
...
valor
Figura 3.3 – Árvore de derivação gerada a partir do documento X
Após a conversão, a segunda etapa do método é dividida em quatro partes:
1. São gerados símbolos para cada um dos elementos de t1 (linha 2). É criada inicialmente
uma regra denominada Start que representa o elemento raiz da árvore. Para cada um
dos elementos presentes em t1 (Figura 3.3) são criadas regras. O nome da regra será
da forma An , sendo n um identificador do número da regra. A produções contidas na
regra representam os filhos que o elemento pode possuir na árvore. Assim, elementos
complexos (possuem filhos) tem seu valor representado pelo rótulo de uma nova regra e
elementos simples por Any. Após executado o método eCFG (linha 3) receberá o conjunto
das regras contidas na Figura 3.4. Por exemplo o elemento revisao de t1 que possui filhos
e gera a regra A5 .
2. É feita uma junção da regras que possue, a fim de eliminar ambiguidades (linha 3). O
método irá comparar as regras e a forma que estas estão sendo utilizadas e fará a junção.
Levando em consideração a gramática contida na variável eCFG (Figura 3.4) as regras
32
A1 , A2 e A3 estão sendo usadas no mesmo contexto (regra Start), sendo assim as regras
A2 e A3 receberam o rótulo da regra A1 . A Figura 3.5 apresenta o conteúdo de eCFG
após a execução deste passo.
3. É realizada a junção das regras baseando-se no conteúdo, ou seja, verifica as regras que
possuem produções semelhantes e tenta uni-las em uma única regra. Com análise das
regras da Figura 3.5, serão selecionadas as regras A4 e A5 . Essas regras possuem produções semelhantes, sendo assim, a produção da regra A5 será incorporada a produção
A4 concatenando-as utilizando o operador "ou". Ao final da parte desta etapa a variável
eCFG possui o conteúdo apresentado na Figura 3.6;
4. Realiza a extração de tipos básicos dos elementos simples (linhas 5 a 11). Para realizar
esta etapa as produções de todas as regras são varridas, sendo selecionados os elementos
que possuem como valor o terminal Any (elementos simples) e passados para a função
extraiTipoPrimitivo (linha 8) que irá analisar o documento de entrada e inferir através de
tentativa e erro um tipo para o elemento. Ao fim desta parte a variável eCFG possui o
conteúdo apresentado na Figura 3.7
A última etapa do método fará, através de uma série de regras, a conversão da eCFG em
uma XSD. A Figura 3.8 apresenta o esquema gerado a partir da eCFG apresentada na Figura 3.7
.
Start ← moto : A1 moto : A2 moto : A3
A1 ← marca : Any modelo : Any opcional : Any revisao : A4
A2 ← marca : Any modelo : Any opcional : Any opcional : Any revisao : A5
A3 ← modelo : Any ano_modelo : Any
A4 ← km : Any valor : Any km : Any valor : Any
A5 ← km : Any valor : Any km : Any valor : Any km : Any valor : Any
Figura 3.4 – Inferencia Inicial das regras
A1 ← marca : Any modelo : Any opcional : Any revisao : A4 |
marca : Any modelo : Any opcional : Any opcional : Any revisao : A5 |
modelo : Any ano_modelo : Any
A4 ← km : Any valor : Any km : Any valor : Any
A5 ← km : Any valor : Any km : Any valor : Any km : Any valor : Any
Figura 3.5 – Figura 3.4 após a junção por contexto
33
A1 ← marca : Any modelo : Any opcional : Any revisao : A4 |
marca : Any modelo : Any opcional : Any opcional : Any revisao : A5 |
modelo : Any ano_modelo : Any
A4 ← km : Any valor : Any km : Any valor : Any | km : Any valor :
Any km : Any valor : Any km : Any valor : Any
Figura 3.6 – Figura 3.5 após a junção por conteúdo
A1 ← marca : String modelo : String opcional : String revisao : A4 |
marca : String modelo : String opcional : String opcional : String revisao :
A4 | modelo : String ano_modelo : Int
A4 ← km : Int valor : F loat | km : Int valor : F loat km : Int valor : F loat
Figura 3.7 – Figura 3.6 após a extração de tipos básicos
3.3
MÉTODO DE MIN&CHUNG
O método proposto em (MIN; AHN; CHUNG, 2003) consiste em transformar os ele-
mentos pertencentes aos documentos em regras com uma notação própria. Após essa transformação, é feita uma verificação das regras comparando com os elementos dos documentos
utilizados como entrada. Esse processo é chamado de consolidação da gramática. Após a consolidação desta gramática, esta pode ser traduzida para uma DTD ou para uma XSD.
Inicialmente, todas as tags contidas no documento são convertidas para elementos. Para
cada um destes elementos, é feita a extração de conteúdo e a transformação em um termo. Um
termo é constituído de sequências de símbolos ou escolhas de símbolos, ou seja, um termo é
uma regra constituída de concatenação de símbolos ou de símbolos separados pelo operador
"ou". Um termo pode vir acompanhado de um número mínimo de aparições (min) e de um
número máximo de aparições (max). Por exemplo, um elemento E é constituído de um termo
T que é associado a um número de min e max, ou seja, E:= T(min,max) ). O termo também pode
(1,3)
ser considerado opcional, denotado com opt=true (i.e. E:= Topt=true
|T2
1
). Durante esta etapa,
é observada uma regra básica, cada elemento não deve aparecer mais de uma vez em um termo.
Essa propriedade ajuda a manter a consistência das regras.
Após a inferência desta gramática, é feito o processo de consolidação dos elementos
contidos na gramática. Para tal, é feito um particionamento dos conjuntos de entradas de forma
a ficarem em subsequências. Estas subsequências não podem possuir o mesmo símbolo duas
vezes. Por exemplo dada a entrada "aabcaa" as subsequências são (a)[1,2] , bc e (a)[1,2] pois
34
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
<? xml v e r s i o n = " 1 . 0 " ? >
< x s : s c h e m a x m l n s : x s = " h t t p : / / www . w3 . o r g / 2 0 0 1 / XMLSchema " >
<xs:complexType>
< x s : e l e m e n t name= " moto " m i n O c c u r s = " 1 " maxOccurs = " 3 " >
<xs:complexType>
< x s : e l e m e n t name= " marca " m i n O c c u r s = " 0 " t y p e = "
xs:string " />
< x s : e l e m e n t name= " o p c i o n a l " t y p e = " x s : s t r i n g "
maxOccurs = " 2 " / >
< x s : e l e m e n t name= " r e v i s a o " >
<xs:complexType>
<xs:sequence>
< x s : e l e m e n t name= " km " t y p e = " x s : i n t " / >
< x s : e l e m e n t name= " v a l o r " t y p e = " x s : f l o a t " /
>
</ xs:sequence>
< / xs:complexType>
</ xs:element>
< x s : e l e m e n t name= " ano_modelo " t y p e = " x s : i n t " / >
< / xs:complexType>
</ xs:element>
< / xs:complexType>
</ xs:element>
< / xs:schema>
Figura 3.8 – XSD criada utilizando o método de Inferência Gramatical
sequências como "aab"ou "caa"seriam impróprias já que repetem um símbolo duas vezes. Para
minimizar o grande número de regras geradas, são inferidas regras que agrupam subsequências
que possuem partes iguais. No exemplo anterior, as subsequências geradas são combinadas na
regra (a(1,2) | bc)(1,2) . Também são utilizadas regras de heurística que auxiliam na junção dessas
subsequências.
Ao fim dessas etapas, regras gramaticais serão formadas. Estas regras definem a estrutura contida no documento. Elas podem ser convertidas para uma DTD ou para XSD. Os autores
em (MIN; AHN; CHUNG, 2003) apresentam experimentos feitos para verificar a exatidão do
esquema gerado pela ferramenta. O método é comparado com o XTRACT, sendo aplicada em
documentos cujo esquema é conhecido. Possibilitando assim, que se verifique qual dos métodos é mais eficaz. Nos resultados apresentados o método proposto por (MIN; AHN; CHUNG,
2003) possui esquema mais semelhante ao original do que o esquema gerado pelo XTRACT e
possui tempo de execução menor (MIN; AHN; CHUNG, 2003).
O Algoritmo 3 apresenta o pseudocódigo gerado a partir da descrição do método.
3.3.1
Estudo de Caso
Para o estudo de caso será utilizado o documento X (Figura 3.1) para ilustrar o funcio-
namento do Algoritmo 3.
35
Algoritmo 3: Método de Min&Chung
Saída: gramática de notação própria
1 elementos ← extraiElementosEntrada(Entrada);
2 foreach elemento in elementos do
3
extraiSequencias(sequencia, Entrada, elemento);
4
if tamanho(sequencia) > 0 then
5
particionaSequencias(sequencias, sequencias);
6
agrupaSequenciasSemlhantes(sequencias);
7
criaRegra(regra, sequencias);
8
foreach seq in sequencias do
9
if regra não valida para seq then
10
corrige regra;
11
seq ← sequencias[0];
12
end
13
end
14
adiciona regra na gramatica;
15
end
16 end
O algoritmo recebe X como entrada, e inicialmente, realiza a extração dos elementos
presentes no documento (linha 1). Sendo assim, a variável elementos receberá a lista de elementos extraídos de X (motos, moto, marca, modelo, opcional, revisao, km, valor, ano_modelo).
Cada elemento de X é processado pelo Algoritmo 3 gerando um conjunto de regras que
representará as sequências de subelementos do documento X. Seguindo a execução do exemplo,
o primeiro elemento a ser processado é motos. Sendo assim, é feita a extração das sequências
para este elemento (linha 3). A variável sequencia irá conter o valor (moto moto moto).
Após extraída a sequência é realizado o particionamento (linha 5), caso a sequência
extraída possua tamanho maior que 0 (linha 4). Durante este processo, a sequência contida
na variável sequencia será dividida em ERs que descrevam a sequência. Cada ER é gerada de
forma a não conter repetições de símbolos, sendo assim, sempre que uma repetição é encontrada
na sequência original, a ER criada vira uma partição e o trecho que ela descreve é retirado da
sequencia. Cada uma destas partições é armazenada na variável sequencias. Quando executado
este passo com valor contido em sequencia (moto moto moto) será criada apenas uma partição
(moto[1,3] ). Ao final desta etapa a variável sequencias possuirá o valor { moto[1,3] }.
O processo de agrupamento das partições (linha 6), visa eliminar possíveis ambiguidades contidas nas partições das sequencias. Durante a execução deste método, é feita uma
varredura nas partições a fim de encontrar partições iguais ou muito semelhantes. Quando par-
36
tições iguais são encontradas uma destas é eliminada. Se partições semelhantes são encontradas,
estas são combinadas para contemplar ambas as ERs. Como na execução do exemplo a variável
sequencias contém apenas uma sequência esta etapa não realiza mudanças.
De posse das sequências, é feita a inferência de uma regra que contemple todas as
sequências (linha 7). Para tal, são utilizadas uma série de proposições baseadas em heurística.
Uma regra é formada por um conjunto de termos, cada termo representa uma ou um conjunto de
partições contidas na variável sequencias. No exemplo, a variável sequencias apresenta apenas
um elemento, então a regra criada será apenas a transcrição deste elemento como um termo.
Assim, a variável regra receberá como rótulo o nome do elemento e como valor T1 , ou seja,
T1 ← moto[1,3] .
O último passo a ser executado é o de consolidação da gramática (linhas 8 a 13). Para
realizar este processo, cada umas das sequências de elementos contidas na variável sequencias
é analisada visando validar a sequência utilizando a regra. Se a regra não é capaz de validar
a sequência, a regra é corrigida utilizando algumas propriedades e o processo de validação
recomeça (linha 11).
Após a validação, a regra é adicionada a gramática que contém a estrutura do documento
X (linha 14). A Figura 3.9 apresenta o valor que a variável gramática possui após a execução
do algoritmo para todos os elementos. Percebe-se através dela que elementos simples como
modelo, marca, ano_modelo, opcional, km e valor não possuem regras próprias. Quando for
realizada a conversão das regras para um DTD ou XSD estes elementos devem ser convertidos
para elementos simples.
motos ← T1 ;
T1 ← moto[1,3]] ;
moto ← T2 |T3 ;
T2 ← marca modelo T4 revisao;
T3 ← modelo ano_modelo;
T4 ← opcional[1,2] ;
moto ← T5 ;
T5 ← (km valor)[1,2] ;
Figura 3.9 – Gramática gerada pelo Algoritmo 3
37
3.4
XSTRUCT
O XStruct descrito em (HEGEWALD; NAUMANN; WEIS, 2006), é baseado nas abor-
dagens propostas em (MIN; AHN; CHUNG, 2003; GAROFALAKIS et al., 2000). É constituído
por cinco módulos (apresentados na Figura 3.10): Attribute Extration, Datatype Recognition,
Model Extraction, Factoring e Schema Printer. Cada um desempenhando um papel específico
no processo de extração do esquema.
Inicialmente, o Xstruct utiliza a API SAX para fazer a leitura dos documentos XML.
Após a leitura, a entrada é encaminhada para os módulos de Attribute Extration, Datatype
Recognition e Model Extraction. O módulo de extração de modelo (Model Extraction) fornece
as entradas para o módulo de fatoração (Factoring). Então o módulo de impressão (Schema
Printer) combina as saídas do módulo de extração de tipo (Datatype Recognition), com a do
módulo de extração de atributos (Attribute Extration) e com a do módulo de fatoração para gerar
a XSD que representa os documentos. A Figura 3.10 apresenta a interconexão dos componentes
do XStruct.
Figura 3.10 – Estrutura dos módulos do XStruct (HEGEWALD; NAUMANN; WEIS, 2006)
O XStruct utiliza uma variação do algoritmo proposto em (MIN; AHN; CHUNG, 2003)
no módulo de extração de modelos (Extraction Model). O Xstruct usa o método de Min&Chung
com o papel específico de realizar a extração de uma gramática regular para cada um dos ele-
38
mentos contidos na instância XML. Estas gramáticas são combinadas na fase de fatoração para
gerar uma única gramática que representa a estrutura de todos os elementos.
A etapa de fatoração é feita pelo módulo "Fatoring". É utilizado a ideia de fatoração
proposta em (GAROFALAKIS et al., 2000). São feitas alterações no algoritmo de fatoração
original, para que ele possa receber o formato das entradas enviadas pelo módulo anterior. Este
módulo é responsável por agrupar todas as gramáticas geradas pelo módulo de extração criando
uma única gramática que descreve os documentos utilizados como entrada.
Paralelamente aos módulos descritos acima, são executados os módulos de extração de
tipos e extração de atributos. O módulo que realiza a extração de tipos, reconhece apenas tipos
básicos (i.e. boolean, integer, decimal, float, date, time, string). A extração é feita com base no
conteúdo encontrado para o elemento. Para realizá-la é criada uma lista com os conteúdos de
cada elemento, então é verificado qual o tipo encaixa para todos os conteúdos encontrados para
o elemento, seguindo a ordem boolean, integer, decimal, float, date, time, string. Já o módulo
de extração de atributos é mais simples. Consiste em verificar as ocorrências de atributos nos
elementos do documento, e verificar seu tipo (utilizando métodos do módulo de extração de
tipos) e também se o atributo é obrigatório ou não. Se o atributo está presente em todas as
aparições de um determinado elemento então ele é considerado obrigatório, senão opcional.
O último módulo a ser executado é do "Schema Printer". Neste módulo é gerado o
documento XSD que representa a coleção de documentos utilizada como entrada. Com base
nas informações obtidas nas saídas dos módulos de extração de tipo, extração de atributos e
fatoração, o módulo de impressão do esquema cria uma combinação de todas as informações
que culmina na criação da XSD que descreva todos os dados. Sendo assim, o XStruct combina
os métodos propostos por (MIN; AHN; CHUNG, 2003; GAROFALAKIS et al., 2000) com
técnicas de extração de atributos e de tipos de dados.
Algoritmo 4: Xstruct
Entrada: coleção documentos XML
Saída: XSD
1 gramatica ← modelExtraction(Entrada);
2 gramatica ← factoring(gramatica);
3 tiposDados ← dataTypeRecognition(Entrada);
4 atributos ← attributeExtraction(Entrada);
5 schema ← schemaPrinter(gramatica, atributos, tiposDados);
39
3.4.1
Estudo de Caso
Como nos estudos de casos anteriores o documento X será utilizado para apresentar o
funcionamento do Algoritmo 4.
O algoritmo recebe como entrada um documento XML. Esse documento é passado como
parâmetro para a função modelExtraction (linha 1). Esta função representa uma chamada ao
método proposto por Min&Chung (MIN; AHN; CHUNG, 2003). Como apresentado anteriormente, o método de Min&Chung consiste na extração de uma gramática, com sintaxe própria,
que descreve a estrutura do documento utilizado como entrada. Sendo assim, o Xstruct utiliza
o método para realizar a extração de uma gramática. Após a execução da função a variável
gramatica possui o conteúdo apresentado pela Figura 3.11.
motos ← T1 ;
T1 ← moto[1,3]] ;
moto ← T2 |T3 ;
T2 ← marca modelo T4 revisao;
T3 ← modelo ano_modelo;
T4 ← opcional[1,2] ;
moto ← T5 ;
T5 ← (km valor)[1,2] ;
Figura 3.11 – Gramática gerada pelo Algoritmo 3
O próximo passo a ser executado é passar a gramática gerada para o módulo de fatoração. O modulo de fatoração é baseado no módulo de fatoração usado pelo XTRACT (GAROFALAKIS et al., 2000). São feitas algumas alterações no módulo para que este atenda as
necessidades do XStruct. Sendo assim, o método factoring irá receber a gramatica como parâmetro (linha 2) e irá fazer a junção de regras semelhantes. Esta junção é baseada no contexto
das regras (produção). As regras são simplificadas que possuem produções semelhantes, afim
de deixar o esquema mais enxuto e conciso. A gramática resultante dos outros passos não sofrerá mudanças nesta etapa, tendo em vista, que não possui regras semelhantes que possam ser
unidas.
O próximo módulo a ser executado é o de reconhecimento de tipos (Datatype Recognition - linha 3). O módulo irá extrair a lista de todos os elementos com seus respectivos valores.
Então, irá verificar para cada elemento encontrado qual dos tipos primitivos se encaixa. A ordem de tipos que é utilizada para o teste é boolean, integer, decimal, float, date, time, string.
Por exemplo, para o documento X serão extraídos os elementos marca, modelom opcional, km,
40
valor, ano_modelo, elementos como motos, moto, revisao não são adicionados a lista por não
possuírem valores associados. A Figura 3.12 apresenta os elementos extraídos e seus respectivos tipos.
marca : String;
modelo : String;
opcional : String;
km : integer;
valor : f loat;
ano_modelo : integer;
cilindradas : integer;
Figura 3.12 – Resultado do módulo de extração de tipos
Na linha 4 do Algoritmo 4 é feita a chamada do procedimento attributeExtraction que
representa o modulo de extração de atributos. Este procedimento irá analisar todos os elementos
presentes no documento de entrada e verificar quais deles possuem atributos. Cada elemento
que possuir atributo será adicionado em uma lista com seus respectivos atributos. Seguindo
a execução do exemplo, somente o elemento moto possui atributo no documento X. Assim, o
elemento moto e seu atributo cilindradas serão adicionados a um vetor que será armazenado na
variável atributos.
A última etapa do algoritmo a ser executada e a transformação das informações extraídas
para uma XSD. Esta tarefa é executada pelo procedimento schemaPrinter. Neste módulo são
utilizadas uma série de propriedades que irão transformar e combinar as informações extraídas
(gramática, tipos de dados e atributos) para criar uma XSD. A Figura 3.13 apresenta a XSD
criada pelo procedimento.
3.5
XTLSM
O método apresentado em (AMIEL; HARRUSI; AVERBUCH, 2008) é baseada em um
novo tipo de máquina de estado a TLSM (two layer state machine) usada para validar gramáticas
de árvore. Cada estado da TLSM contém uma máquina de estados regular que descreve os filhos
de um elemento da coleção de documentos XML.
O método propõe 4 etapas para a extração do esquema: (i) é feita a criação de um
reconhecedor de árvores de prefixos (PTA - prefix tree acceptor) a partir de um documento
XML, (ii) a PTA é convertida em uma máquina de estados combinando árvores semelhantes,
(iii) através da máquina de estados criada na etapa anterior é criada um TLSM, e (iv) a TLSM é
41
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
<? xml v e r s i o n = " 1 . 0 " ? >
<xs:complexType>
< x s : e l e m e n t name= " moto " m i n O c c u r s = " 1 " maxOccurs = " unbounded " >
<xs:complexType>
xs:string " />
<xs:complexType>
<xs:sequence>
>
</ xs:sequence>
< / xs:complexType>
</ xs:element>
< x s : a t t r i b u t e name= " c i l i n d r a d a s " t y p e = " x s : s t r i n g " / >
< / xs:complexType>
</ xs:element>
< / xs:complexType>
</ xs:element>
< / xs:schema>
Figura 3.13 – XSD criada utilizando o XSTRUCT
convertida para uma XSD.
Na primeira etapa de execução é criada uma PTA. Uma PTA é basicamente uma representação em árvore de uma máquina de estados finita (CARRASCO; ONCINA, 1994). Para
a criação da PTA, inicialmente o documento XML é representado através de uma árvore de
rótulos ordenada (OLT - ordered labeled tree). Uma OLT é uma árvore onde todos os filhos de
um nó são ordenados, e cada nó possui um nome não único. O elementos com mesmo nome
contidos na OLT juntamente com suas subárvores são combinados para criar a PTA.
Em seguida, a PTA é então convertida para uma máquina de estados. Para isso, é feita
uma análise da PTA, onde são marcadas as subárvores que possuem semelhanças. É feita então, a junção ou combinação destas subárvores, o que culmina na criação de uma máquina de
estados.
Na segunda etapa, cada um dos estados da máquina é transformado em uma outra máquina de estados. Desta forma é possível criar uma distinção entre os filhos de uma OLT. Esta
máquina de estados multinível é denominada de TLSM. A TLSM é apresentada como uma
máquina de estados finita que possui máquinas de estados internas. Cada uma das máquinas
internas está ligada a um estado de uma máquina da camada superior, sendo que todas as máquinas presentes nas camadas de TLSM são finitas e determinísticas.
A TLSM criada na terceira etapa descreve a estrutura presente no documento XML uti-
42
lizado como entrada. Porém apesar da TLSM possuir uma linguagem própria apresentada em
(CARRASCO; ONCINA, 1994) ela não é considerada um padrão. Então, na última etapa de
execução do algoritmo, a TLSM é convertida para uma XSD. Para cumprir esta etapa, são apresentados pelo autor alguns subalgoritmos utilizados para realizar esta conversão. Seu objetivo
é reduzir as máquinas de estado internas até que não seja mais possível, então as transformam
em elementos da XSD utilizando força bruta.
O Algoritmo 5 apresenta um pseudocódigo do método, este algoritmo será utilizado
posteriormente na aplicação do estudo de caso.
Algoritmo 5: XTLSM
Saída: XSD
1 PTA ← criaPTA(Entrada, root);
2 fsm ← generaliza(PTA, Entrada);
3 foreach estado in fsm do
4
estadoInterno ← novo estado inicial;
5
foreach nodo in Entrada do
6
filho ← filhoDireita(nodo);
7
while filho do
8
if (estadoInterno, filho) não foi mapeado then
9
if existe transição estado interno para filho na TLSM then
10
adiciona na TLSM transição (estadoInterno, filho);
11
else
12
cria novo estado interno e;
13
adiciona na TLSM transição (e, filho);
14
estadoInterno ← e;
15
end
16
adiciona (estadoInterno, filho) em mapeado;
17
end
18
filho ← irmaoEsquerda(filho);
19
end
20
end
21 end
22 xsd ← converteTLSMParaXSD(tlsm);
3.5.1
Estudo de Caso
Para o estudo de caso, novamente será utilizado o documento X (Figura 3.1) para ilustrar
funcionamento do Algoritmo 5.
Inicialmente, o algoritmo irá transformar X em uma PTA (Figura 3.14). Para tal, ele
irá interpretar o documento XML em forma de árvore, então através do método criaPTA (linha
43
1) criará a PTA. O método criaPTA recebe dois parâmetros, o primeiro é o documento XML
e o segundo o elemento raiz do documento. Como a raiz de X é o elemento motos esse será
o segundo parâmetro do método. Ao fim desse passo a variável PTA irá armazenar a PTA
gerada, representada na Figura 3.14. Onde as transições são rotuladas pelo nome do elemento,
os círculos representam estados e os círculos duplos representam estados de reconhecimento.
0
motos
1
marca
moto
3
modelo
2
revisao
4
opcional
6
valor
km
5
ano_modelo
9
8
7
Figura 3.14 – PTA gerada a partir do documento X
O algoritmo então, transforma a PTA em uma máquina de estados (linha 3). Essa transformação é feita realizando a junção de subárvores contidas na PTA levando em consideração
suas semelhanças e contexto. Como a PTA gerada pelo exemplo não possui subárvores semelhantes, ela não sofrerá mudanças sendo somente transportada da variável PTA para fsm
(linha 3). Sendo assim, ao fim do processo a máquina gerada será a mesma apresentada pela
Figura 3.14.
O próximo passo a ser executado cria a TLSM (linhas 3 a 21). Durante este passo, a
máquina de estados criada será transformada em uma TLSM. A TLSM se diferencia de uma
máquina de estados normal por possuir estados com máquinas de estados internas. O XTLSM
faz uso das máquinas de estado internas para realizar a validação dos filhos de um elemento
presente no documento.
Para criar a TLSM é feita uma análise de todos os estados presentes na máquina de
estados existente (fsm - linha 3) em conjunto com os nodos presentes no documento de entrada
(i.e. X). A Figura 3.15 apresenta a TLSM criada a partir da máquina de estados apresentada
na Figura 3.14. Sendo assim, em cada estado da máquina será verificado se o nodo da transição
44
possui filhos, caso existam, será criada uma nova camada, ou seja, uma máquina de estados
interna e serão adicionadas as transições que validam a ordem em que os filhos deverão aparecer.
Seguindo a execução do exemplo, o estado selecionado será o estado inicial com o primeiro
nodo (motos). Na linha 6, a variável filho receberá o filho mais a direita do elemento motos
(moto). Após verificado que o estadoInterno (agora um estado inicial) com o filho (moto) ainda
não foi mapeado (linha 8) e que não existe um estado para o filho na TLSM (linha 9), será
criado um novo estado que é alvo de uma transição do estado estadoInterno pelo elemento
filho, e o novo valor do estadoInterno será o estado criado (linhas 12, 13 e 14). Então, é
selecionado o irmão a esquerda do filho, que é novamente moto, será criada uma transição para
o estado estadoInterno por moto (linha 10). A camada da TLSM gerada por estes passos esta
representada na Figura 3.16 (a).
A Figura 3.15 representa a TLSM gerada na execução do algoritmo com X como entrada. Os estados representados por um quadrado são estados que possuem uma máquina de
estados interna. As máquinas internas são apresentadas na Figura 3.16. Os estados 1, 2 e 6 da
Figura 3.15 são as partes (a),(b) e (c) respectivamente da Figura 3.16.
0
moto
1
marca
3
motos
modelo
2
4
revisao
opcional
6
valor
8
km
5
ano_modelo
7
9
Figura 3.15 – TLSM gerada a partir do documento X
A última etapa do método consiste em transformar a TLSM em uma XSD (linha 22).
Para isso, são propostos alguns algoritmos de redução da TLSM que simplificam e reduzem a
TLSM gerada, então através de força bruta a TLSM é transformada em uma XSD. A Figura 3.17
apresenta a XSD gerada na execução do algoritmo.
45
(a)
(c)
km
moto
0
0
km
1
2
1
moto
valor
modelo
(b)
1
opcional
2
0
3
marca
opcional
modelo
revisao
4
1
1
ano_modelo
5
1
Figura 3.16 – Camadas internas TLSM Figura 3.15
3.6
CONSIDERAÇÕES FINAIS
Neste capítulo foram descritas abordagens que realizam a extração da estrutura de um
documento XML, ou seja, um esquema que descreve a estrutura de uma coleção de documentos XML. A maioria destas abordagens, cria uma gramática que representa a estrutura do documento e a converte para uma XSD ou para uma DTD. Além disso, a maioria delas, tem
em comum o uso de expressões regulares para representar regras que descrevem a estrutura
do documento. As abordagens apresentadas em (GAROFALAKIS et al., 2000; CHIDLOVSKII, 2001; MIN; AHN; CHUNG, 2003; HEGEWALD; NAUMANN; WEIS, 2006) possuem
semelhanças nos seus processos de extração. Já a abordagem apresentada em (CARRASCO;
ONCINA, 1994) segue uma linha diferente. As diferenças são rapidamente discutidas nesta
seção.
O XTRACT transforma o documento XML em uma série de sequências que são transformadas em ERs. Estas ERs passam por um processo de simplificação (fatoração), então por
uma eleição que seleciona as ERs que serão transformadas em elementos da DTD final. Em
contra partida, o método de Inferência Gramatical cria uma eCFG com base na instância XML
(interpretado-o em forma de árvore) sendo ela transformada em uma XSD. Já o método de
Min&Chung propõe a criação de uma gramática (com uma notação própria) que representa a
ordem dos elemento do documento XML utilizado como entrada. As regras geradas são submetidas á um processo de validação, que por força bruta verifica a validade de cada uma segundo
a ordem dos elementos no documento. As regras que forem válidas podem ser transformadas
46
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
<? xml v e r s i o n = " 1 . 0 " ? >
<xs:complexType>
< x s : e l e m e n t name= " moto " m i n O c c u r s = " 1 " maxOccurs = " unbounded " >
<xs:complexType>
xs:string " />
<xs:complexType>
<xs:sequence>
>
</ xs:sequence>
< / xs:complexType>
</ xs:element>
< / xs:complexType>
</ xs:element>
< / xs:complexType>
</ xs:element>
< / xs:schema>
Figura 3.17 – XSD criada utilizando o XTLSM
para XSD ou DTD. O XStruct possui um processo semelhante que reúne a extração da gramática proposta pelo método de Min&Chung e a fatoração proposta pelo XTRACT. Percebe-se
que esses métodos possuem uma forma parecida de trabalho, criando uma gramática ou ERs
para os elementos do documento XML, realizando algum tipo de validação/simplificação das
regras e transformando-as em um XSD ou DTD.
O XTLSM apresenta uma linha diferente de trabalho, sendo que este propõe o uso de
máquinas de estado para descrever a estrutura do documento. Inicialmente, o XTLSM cria uma
PTA que valida o documento XML utilizado como entrada. Após isso a PTA é transformada
em um máquina de estados. A máquina de estado é transformada em um TLSM que além de
validar a forma em que os filhos de um elemento aparecem, possui estados internos que validam
os irmão do elemento. Finalmente a TLSM é convertida para uma XSD.
Com base nas informações apresentadas nas seções deste capítulo foi gerada uma tabela
(Tabela 3.1) que apresenta algumas das características dos métodos apresentados.
Cada linha da Tabela 3.1 apresenta um método e suas colunas representam características dos métodos. Através dos dados contidos na tabela, percebe-se que a maior parte dos
métodos inicialmente cria uma gramática que representa o documento, no entanto, o método
XTLSM cria uma máquina de estados. A terceira coluna da tabela apresenta as linguagens de
esquema que cada método suporta. O método de Min&CHung não é convertido para nenhum
47
dos formatos, embora seu formato de descrição possa ser transformado para DTD ou XSD não
é apresentada uma forma de realizar esta conversão.
A quarta coluna da Tabela 3.1 apresenta os métodos que realizam a extração de atributos
contidos no documento XML. Apenas o método Xstruct realiza a extração de atributos. A
última coluna da tabela, apresenta os métodos que possuem a extração dos tipos dos elementos
do documento XML. Percebe-se que apenas os métodos Ming&Chung e XTRACT não realizam
a extração de tipos.
Método
Forma Representação
Formatos Suportados Ext. Atributos Ext. Tipos
XTRACT
ER
DTD
Inferência Gramatical
eCFG
XSD
X
Min&Chung
Gramática notação própria
Xstruct
CFG
XSD
X
X
XTLSM
Máquina de Estados
XSD
X
Tabela 3.1 – Características métodos de extração de esquemas
Durante este capítulo foram apresentadas as características e a forma de trabalho de algumas abordagens de extração de esquemas. Cada uma das técnicas possui uma forma distinta
de realizar o processo de extração (embora existam algumas semelhanças). Contudo, em nenhuma das abordagens encontradas foi utilizada a probabilidade como ferramenta de auxilio na
inferência do esquema. Este trabalho visa explorar essa abordagem, de forma a verificar se esta
técnica apresenta alguma vantagem sobre as demais. A probabilidade é o assunto do próximo
capítulo.
48
4 PROBABILIDADE E REDES BAYESIANAS
Em qualquer experimento aleatório, há sempre incerteza quanto à ocorrência ou não de
determinado evento (SPIEGEL; FARIAS, 1978). A probabilidade é o percentual de chance
de um determinado evento ocorrer, ou de uma certa hipótese ser verdadeira (RUSSELL et al.,
1995). É um valor dado para a chance que um evento ocorra, escalado entre 0 e 1. Se o
valor da probabilidade é igual a 1, o evento sempre ocorrerá. Em contrapartida, se o valor da
probabilidade for 0 então o evento nunca irá ocorrer.
Uma probabilidade P (A) é denominada de probabilidade a priore de A. Representa a
chance que o evento "A" possui de ocorrer. Por exemplo, se A representa a hipótese de "estar
quente" (i.e., ocorrer temperaturas elevadas, acima de 25o C), e a probabilidade a priori de A
supostamente é de 30%, então P (A) = 0,3. Agora se B representa a hipótese de "ser inverno",
a probabilidade a priori de B supõe-se ser de 25% , então P (B) = 0,25. Sendo assim, a
probabilidade de estar quente é de 30% e a probabilidade de estarmos no inverno é de 25%.
Existe também a probabilidade condicionada, que é a probabilidade de um evento ocorrer dado que outro está ocorrendo. Utilizando o exemplo, pode ser necessário saber a probabilidade de ser inverno e estar quente. Assim, é necessário que seja realizado o cálculo que indique
a probabilidade de A (estar quente) ocorrer dado B (ser inverno), esta probabilidade (condicionada) é denotada por P (A|B) . Para obter esta probabilidade é necessário o uso do cálculo
P (A ∧ B) = P (A ∧ B)/P (B). Porém este cálculo fica atrelado a necessidade de se conhecer a
probabilidade de que os dois eventos ocorram concomitantemente (P (A ∩ B)). Para este exemplo, é feita a suposição que a probabilidade de estar quente e ser inverno P (A) é de 20% ou
seja, P (A ∩ B) = 0,2. Então para verificarmos qual a probabilidade de estar quente dado que
estamos no inverno é P (A|B) = P (A ∩ B)/P (B), P (A|B) = 0,2/0,25, logo P (A|B) = 0.05,
ou seja 5%.
Este problema é minimizado com a aplicação do Teorema de Bayes. Este teorema
é usado para calcular a probabilidade de que um evento ocorra, tendo como base um fragmento relacionado de informação (COPPIN, 2010). O teorema é declarado na forma: P(B|A)
= P (A|B) · P (B)/P (A). Levando em consideração o exemplo anterior, agora será calculada a probabilidade de ser inverno dado que está quente, sendo que a probabilidade de A e
B ocorrerem ao mesmo tempo (P (A ∩ B)) é agora desconhecida, porém a probabilidade a
condicionada de A é de 5%. Com isso, põe-se a calcular a probabilidade condicionada de
49
B (P (B|A)) ocorrer aplicando o Teorema de Bayes. Assim, aplicando o teorema de Bayes
(P (B|A) = 0.05 · 0.25/0.3) que resulta em P (A|B) = 0,041, ou seja a probabilidade a posteriori de B é 4,1%.
Há também elementos que não possuem dependências entre si. Segundo (COPPIN,
2010), dois eventos A e B, serão independentes se a probabilidade a priori de A seja totalmente
desvinculada da probabilidade de B ocorrer. Um exemplo disso é o lançamento de duas moedas
M1 e M2 . A probabilidade de que a primeira moeda dê cara independente do resultado que a
segunda moeda obterá. Se A e B são independentes o cálculo da probabilidade de que tanto
A quanto B ocorram ao mesmo tempo (P(A ∩ B)) será a probabilidade da A multiplicado pela
probabilidade B, ou seja P(A ∩ B) = P (A) · P (B). Assim, para calcular qual a probabilidade
de duas moedas serem jogadas e ambas deem cara, é calculada levando em conta que tanto
a P (M1 ) e P(M2 ) possuem o valor 0,5 ja que há 50% de chance de lançar uma moeda (não
viciada) e esta dê cara. Desta forma a P (M1 /capM2 ) = 05, 0 · 0,5, resultando em P (M1 ∩
M2 )0,25.
Neste contexto, conceitua-se uma rede Bayesiana de crença, que pode ser denotada por
um grafo orientado acíclico. Neste grafo, os nodos representam as hipóteses e os arcos as ligações de dependência que existem entre as hipóteses. Cada nodo n da rede tem um conjunto
de probabilidades associada baseada nos valores dos nodos os quais n dependente, consequentemente as ligações das quais n participa. A Figura 4.1 é um exemplo genérico de uma rede
baseada em crença.
B
A
C
D
E
Figura 4.1 – Rede de Crença (COPPIN, 2010)
A Figura 4.1 é constituída por cinco nodos, sendo que dois, os nodos A e B, representam
probabilidades de dois eventos que independem um do outro. Tal afirmação pode ser feita devido ao fato de não existir um arco unindo diretamente os dois, já o nodos C, D e E representam
eventos que possuem dependências. Por exemplo, o nodo C possui uma relação dependência
com o nodo A, já que existe um arco partindo de A que chega em C. Da mesma forma, o nodo
E depende do nodo B, pois há um arco originado em B que tem como destino o nodo E. O nodo
50
D possui relação com ambos os eventos A e B, sendo assim ele depende de ambos para ocorrer.
Cada nodo na rede possui um conjunto de dados probabilísticos atrelado a si, baseados
nos nodos com os quais ele se conecta. Nodos como A e B somente possuem probabilidade a
priori, pois independem dos demais nodos. Já os nodos como C e E possuem os dados referentes
as suas conexões (A e B respectivamente). Desta forma o nodo D deve possuir informações
probabilísticas que levam em conta tanto a informações de A quanto as de B.
Segundo (COPPIN, 2010), na construção de uma rede Bayesiana deve-se tomar cuidado
com a ordem em que os nodos são adicionados. Deve ser ordenado de forma que as conexões
entre os nodos façam sentido. Começando por causas e depois adicionar os eventos que elas
causam, e depois, os eventos viram as causas e são adicionados a suas causas e assim sucessivamente.
As redes Bayesianas são comumente utilizadas para armazenar conjuntos de probabilidades combinadas. Já que somente as probabilidades pertinentes são armazenadas. No caso
do exemplo (Figura 4.1) probabilidades como P(A|B) e P(B|C) não são armazenadas, pois não
existem arcos que as liguem.
A Figura 4.2(a) apresenta uma rede de crença simples com 5 nodos que representam
hipóteses sobre a vida de um estudante: C que ingresse para a faculdade, S que estudará, P
que frequente festas, E seja bem-sucedido nas provas e F que haverá diversão. Os arcos do
grafo possuem informações probabilísticas aqui apresentadas pelas tabelas de probabilidade
condicionada da Figura 4.2 (b). O cabeçalho das tabelas apresenta a origem e o destino do arco,
as colunas que possuem apenas uma letra (e.g., S) representa a origem e a última coluna de
cada tabela o destino do arco (i.g., P(E)). Por exemplo a tabela T 3 (Figura 4.2 (b)) apresenta as
informações do arco com origem em P e destino F .
(a)
(b)
C
S
T3
T2
T1
P
T5
T4
E
F
Figura 4.2 – Exemplo Vida na Faculdade (COPPIN, 2010)
51
Os valores apresentados pelas tabelas são valores fictícios criados por (COPPIN, 2010).
Com base no grafo, pode-se afirmar inicialmente que a probabilidade de C ocorrer é de 20%
(tabela T 1). O nodo C é o único que possui probabilidade a priori, pois é o único que não
depende de nenhum outro. A tabela T 4 apresenta dois arcos, um de S para E e outro de P para
E, isso indica que o nodo E depende de dois outros nodos. As probabilidades armazenadas
nas tabelas são probabilidades condicionas (exceto T 1 ). Com base nas informações da rede
podemos calcular qual a probabilidade de durante a faculdade estar em uma festa (P ) e se
divertir (F ), assim temos P(F |P ) = 0.9, pois existe um arco entre P e F onde se P for verdadeira
a probabilidade de F será de 0,7 (linha 2, tabela T 3). As Redes Bayesianas podem ser utilizadas
para realizar cálculos complexos, porém este não é o intuito de deste trabalho, então tais cálculos
não serão apresentados.
As redes Bayesianas, são redes onde são armazenadas probabilidades. Neste trabalho, é
utilizada uma variação das Redes Bayesianas aqui apresentadas, para armazenar probabilidades
referentes aos nodos de uma árvore. Através de uma árvore será construída uma rede que
contenha todos os nodos da árvore. As ligações presentes na rede representarão relacionamentos
que ocorrem na árvore. Os relacionamentos que serão representados são de dois tipos: entre pai
e filho e irmão a direita. Para cada relacionamento são armazenadas informações como tipo do
relacionamento, o número de vezes que ele aparece na mesma árvore e em árvores diferentes e
a probabilidade de que ele ocorra. Com base nos dados contidos na rede será inferia a estrutura
do documento. Este será o assunto da próxima seção.
52
5 MÉTODO PROPOSTO
O referido trabalho é um aprimoramento da ideia proposta por (PASQUALI; DUARTE,
2008) e visa a criação de uma ferramenta que através de uma coleção de documentos XML S
(possivelmente unitária) seja inferido automaticamente um esquema que represente S. Para tal,
com base em S é criada uma rede Bayesiana de Crença. A partir da rede gerada, é inferida uma
eCFG que descreverá a estrutura de S, então, a eCFG será transformada em uma XSD.
Em (PASQUALI; DUARTE, 2008) é apresentada uma ferramenta que realiza a extração
de um esquema utilizando teoria da probabilidade. A ferramenta apresentada recebe um conjunto de árvores Ct (possivelmente unitária) e a processa em duas fases: (i) percorre Ct criando
um grafo orientado etiquetado Ge com informações sobre os nodos, e (ii) baseado em Ge cria
uma eCFG que descreve Ct .
O grafo proposto por (PASQUALI; DUARTE, 2008) é um grafo G = (V,E) orientado
onde V é um conjunto de nós etiquetado com a dupla (l, t), sendo l a etiqueta do nó na árvore Ct
e t o número de aparições em locais distintos de Ct . Já E é um conjunto de arcos identificados
pela tupla (v,w,(σ, ρ, ν)), onde v e w são a origem e destino do arco. E (σ, ρ, ν) é uma tripla
representando (i) o tipo de relacionamento σ: c (child) filho e s (sibling) irmão à direita, (ii) a
quantidade ρ de vezes que w tem um relacionamento σ com v e (iii) a quantidade de vezes que
o relacionamento σ entre v e w é encontrado em posições diferentes na árvore.
(a)
(b)
artigo
artigo
autor
autor
titulo
autor
titulo
Coautor
Coautor
Figura 5.1 – Exemplos de árvores XML
A Figura 5.2 apresenta o grafo Ge criado a partir do conjunto de árvores Ct apresentado
na Figura 5.1. Percebe-se através de Ge que nas árvores utilizadas como entrada (Ct ) o nodo
artigo aparece duas vezes. Percebe-se também que o nodo artigo possui três filhos distintos
autor, titulo, coautor já que possui três arcos do tipo filho (c) que partem dele e tem como
destino os nodos autor, titulo, coautor. O nodo autor aparece como irmão de titulo em Ct pois
existe um arco do tipo irmão à direita (s) entre autor e titulo.
Então, através das informações contidas em Ge e o uso da probabilidade, é criada uma
53
(s, 1, 1)
autor, 2
(c, 3, 2)
artigo, 2
(s, 2, 2)
(c, 2, 2)
titulo, 2
(c, 2, 1)
Coautor, 1
(s, 1, 1)
(s, 1, 1)
Figura 5.2 – Grafo Orientado Etiquetado gerado a partir da Figura 5.1
eCFG que descreve as árvores de Ct . Inicialmente, é realizado o cálculo da probabilidade de
um nodo r possuir um filho x. Este cálculo é realizado da forma P (Tx |Tr ) (probabilidade de
x aparecer dado r), onde Tr represente o valor de t armazenado para r e Tx o valor de ν do
relacionamento (arco) de r com x (i.e. P (autor|artigo) = 1,0, já que t para o nodo artigo é 2,
e ν de artigo para autor também é 2). Após o cálculo das probabilidades de um nodo ser filho
de outro, é feito o cálculo que verifica a probabilidade de um nodo ser irmão de outro, denotado
por P (a|b) (probabilidade de a ser irmão à direita de b) ou P (Ta |Tb ) onde Ta é o valor de t para
o nodo a e Tb o valor de ν para o relacionamento de a com b. Por exemplo, a probabilidade
de titulo ser irmão à direita de autor, P (titulo|autor) = 1,0, pois t para o nodo titulo é 2, e
ν para o relacionamento de autor e titulo também é 2. Com base nestas probabilidades e do
percurso feito no grafo, é criada a eCFG. A eCFG criada a partir da Figura 5.2 é {artigo ←
autor+ titulo autor*, autor ← , titulo ← , coautor ← }.
Com base neste método, propõe-se o pExtract , uma ferramenta que realiza a extração de um esquema com base em uma coleção de documentos XML (possivelmente unitária).
O pExtract realiza a extração do esquema em 3 etapas: (i) gera uma rede Bayesiana de
Crença, (ii) transforma a rede em uma eCFG e (iii) transforma a eCFG no esquema XML correspondente.
Inicialmente, a ferramenta proposta recebe uma coleção de documentos. A coleção
é lida e interpretada utilizando a API SAX, que trata o documento como uma sequência de
caracteres. Durante a leitura do documento, é construída então uma rede baseada em crença.
Para cada elemento lido, são feitas alterações na rede para que esta esteja de acordo com a
entrada. As alterações que um elemento pode realizar na rede ficam restritas a inclusão de um
54
novo nodo, alteração de ligações entre nodos (somente incluindo arcos, nunca excluindo), e
alteração dos dados probabilísticos presentes no nodo ou em um arco.
A rede de crença, como dito anteriormente, é um grafo acíclico onde os nodos possuem
informações probabilísticas. Assim, o grafo que representa a rede de crença é um grafo orientado G = (V,E) (que pode possuir ciclos triviais) onde V é o conjunto de nós etiquetados com
a tupla (l,t, p) (l representa a etiqueta do nó no documento XML utilizado como entrada, t a
quantidade de vezes em que o nó aparece no conjunto de entradas, p a quantidade de vezes
que o nodo aparece como pai de algum outro nodo) e E = (v,w,(s,n,<u>,pt)) é o conjunto de
arcos do grafo, onde v e w ∈ a V e são respectivamente o nodo de origem e de destino do
arco. Já (s,n,<u>,pt) é um conjunto de informações onde (i) s representa o tipo do relacionamento: filho c (child) ou irmão à direita s (sibling), (i) n representa o número de vezes que o
relacionamento ocorre em diferentes subárvores, (i) <u> é uma tupla utilizada apenas para o
relacionamento irmão à direita que identifica os pais dos nodos envolvidos no relacionamento,
e (iv) pt é a probabilidade de que ocorra w dado v (P(w|v)), em outras palavras, a probabilidade
que o relacionamento s ocorra. Esta probabilidade é calculada com base no número de vezes
que w aparece como filho de v e o número de vezes em que v aparece como pai de qualquer nó.
Cada nó do grafo deve possuir além da tupla (l,t, p) a lista dos atributos do elemento que ele
representa, e o número de vezes que cada atributo aparece no elemento.
(s, 1, <artigo>,0.5)
(c, 3, <>,1.0)
artigo,2,7
autor,2,0
(s, 2, <artigo>, 1.0)
(c, 2, <>,1.0)
titulo, 2,0
(c, 2,<>,0.5)
Coautor, 1,0
(s, 1, <artigo>,0.5)
(s, 1, <artigo>,1.0)
Figura 5.3 – Rede Baseada em Crença gerada a partir da Figura 5.1
A Figura 5.3 apresenta a rede Bayesiana criada a partir das instâncias XML apresentadas
pela Figura 5.1. Percebe-se pela rede que o nodo autor possui 100% de chances de aparecer
como filho do nodo artigo. O nodo autor também possui um autorelacionamento (relacionamento do tipo irmão à direita onde v é igual a w) que possui 50% de chance de ocorrer, dado
55
Algoritmo 6: Módulo 1 pExtract - Rede Baseada em Crença
1 criaGrafo(grafo, elemento)
2 Nodo nodo ← buscaNodo(elemento, grafo);
3 lista ← elemento.pegaFilhos();
4 foreach nElemento in lista do
5
atual ← novoNodo(nElemento, grafo);
6
adicionaArco(’c’, nodo, atual, grafo);
7
if anterior is not null then
8
adicionaAresta(’s’, atual, anterior, grafo);
9
end
10
anterior ← atual;
11
criaGrafo(grafo, nElemento);
12 end
que o elemento aparece 2 vezes nas árvores, porém em somente uma das vezes possui o autorelacionamento (Figura 5.1 (a)). Comparando o grafo da rede Bayesiana com o grafo gerado
anteriormente (Figura 5.2) percebe-se semelhanças, porém a rede Bayesiana possui uma gama
maior de informações armazenadas (i.g. a probabilidade de um relacionamento ocorrer (pt)).
O Algoritmo 6 apresenta um algoritmo recursivo que cria a rede baseada em crença.
Este algoritmo possui dois parâmetros: o primeiro é o grafo que está sendo criado e o segundo
é um elemento do documento XML da coleção. Inicialmente, o método será invocado com
um grafo vazio para o elemento que representa a raiz do documento. Então é feita a busca no
grafo pelo elemento e passado como parâmetro. Assim, a função buscaNodo irá buscar no grafo
um ponteiro para o nodo etiquetado com e (linha 2). Se não existir um nodo etiquetado com
e, a função criará um. Então são extraídos todos os elementos que no documento são filhos
de e (linha 3). Para cada filho de e é criado um novo nodo que é armazenado no grafo e na
variável atual (linha 5). Então é adicionada um arco entre o nodo e seu filho atual (linha 6), o
arco adicionado representa o relacionamento entre atual e nodo no documento XML. O método
adicionaAresta possui quatro parâmetros: (i) tipo do relacionamento (’c’ para filho e ’s’ irmão
à direita), (ii) o nodo origem do arco, (iii) o nodo destino do arco e (iv) o grafo onde o arco é
adicionado.
Se existir um elemento na variável anterior, significa que o elemento atual possui um
irmão à suà direita, sendo assim, é criado um arco do tipo irmão à direita entre atual e anterior
(linha 7 e 8). O procedimento adicionaAresta tenta criar um arco entre os nodos passados como
parâmetro. Inicialmente, o procedimento verifica se existe o arco com o tipo indicado entre os
nodos. Se existir um arco, o procedimento atualiza os valores de probabilidade dos nodos e do
56
arco. Caso o arco não exista, o procedimento irá criá-lo.
Na linha 11 do Algoritmo 6, o método é chamado recursivamente, recebendo o próximo
elemento a ser processado. Assim, criaGraf o é chamado para todos os elementos e seus subelementos. Quando um elemento não possuir subelementos, o método é chamado para o próximo
irmão, caso não exista, volta para o pai. A execução continua até que todos os elementos sejam
processados.
O segundo módulo do método cria a eCFG. Sendo assim, é feita uma análise dos dados
presentes no grafo e criada a gramática. Inicialmente, é feita a busca pelo nodo que representa
a raiz do documento XML. O Algoritmo 7 apresenta um pseudocódigo deste módulo.
Algoritmo 7: Módulo 2 pExtract - eCFG
1 criaRegra(eCFG, nodo, grafo)
2 regra ← nova Regra;
3 regra.rotulo ← nodo;
4 nodosEsquerda ← buscaNodoEsquerda(nodo, grafo);
5 foreach nodoE in nodosEsquerda do
6
adicionaNaRegra(regra, nodoE);
7
criaRegra(eCfg, nodoE, grafo);
8
if nodoE possui auto relacionamento then
9
if arco(nodo, nodoE).pt == 1 then
10
adicionaNaRegra(regra, +);
11
else
12
adicionaNaRegra(regra, *);
13
end
14
else
15
if arco(nodo, nodoE).pt < 1 then
16
adicionaNaRegra(regra, ?);
17
end
18
end
19
adicionaNaRegra(regra, montaRegra(eCfg, nodoE, nodo, grafo));
20
if nodoE not is Last(nodosEsquerda) then
21
adicionaNaRegra(regra, |);
22
end
23 end
24 adiciona regra na eCFG;
O procedimento criaRegra realiza de maneira recursiva a criação da eCFG. Ele recebe
3 parâmetros: a eCFG (que no primeiro passo está vazia), um nodo, e o grafo. Inicialmente,
o procedimento cria uma nova regra para o elemento passado como parâmetro. A regra só é
criada se não existir outra regra que possua a mesma cabeça (lado direito da regra). A regra
recebe o nome do nodo como cabeça (linha 3).
57
Então são extraídos do grafo os elementos que deverão aparecer primeiro na regra (elementos mais à esquerda). Tais elementos somente possuem arcos do tipo "c" com o nodo
recebido como parâmetro. Estes elementos também não devem possuir arcos do tipo "s" como
destino (salvo se o nodo for destino e origem do arco). Os nodos que respeitam essas duas
restrições são armazenados na variável nodosEsquerda (linha 4).
Cada um dos nodos contidos em nodosEsquerda deverá aparecer no inicio da regra.
Para isso, na linha 6 (Algoritmo 7) o nodoE é adicionado à produção da regra. Então é feita a
chamada recursiva para o procedimento criaRegra que irá criar uma regra cuja cabeça será o
nodoE. Se o nodoE possuir um auto relacionamento (um arco do tipo ’s’ cuja origem e destino é
nodoE) então é verificada a probabilidade de que na árvore do documento XML o nodo seja pai
do nodoE (a probabilidade do arco cuja origem é o nodo e o destino nodoE apareça na árvore).
Se for 0 então é adicionado o fecho "estrela" de Kleene (*) senão o fecho "positivo" (+) (linhas
10 e 12 respectivamente). Na linha 15 verifica-se se o relacionamento é obrigatório, se não for
é adicionado o símbolo "?" que demonstra que o elemento é opcional.
O restante do percurso irá montar o restante da regra (linha 19 - Algoritmo 7). Para isso,
é invocado o procedimento montaRegra que irá realizar um percurso no grafo. Este percurso
é feito com base em nodos que possuam relacionamento do tipo irmão à direita com nodoE
e relacionamento do tipo filho com nodo. Este procedimento retorna uma regra que contém
os elementos que foram visitados no grafo. O Algoritmo 8 apresenta um pseudocódigo do
procedimento montaRegra.
Inicialmente, o procedimento extrai do grafo os nodos que possuem ao mesmo tempo
relacionamento do tipo irmão à direita com nodoF e relacionamento do tipo filho com nodoP
(linha 2). Cada um dos nodos encontrados é adicionado a regra (linha 4) e para cada um deles é
chamado o método criaRegra (Algoritmo 7). É feita então a chamada recursiva para o método
montaRegra, que fará com que seja adicionada a regra o irmão à direita de nodoD (linha 13).
Desta forma, é feito o percurso pelos nodos, através de arcos do tipo irmão à direita, são processados todos os nodos que possuem relação do tipo filho com o nodoP. Quando existe mais
de um nodo com relacionamento irmão à direita com nodoF, estes serão concatenados unidos
com o operador "ou" (linhas 13 e 14). Quando não há mais irmão à direita a serem explorados o método retorna a regra criada. Este processo fará com que a chamada que originou (no
Algoritmo 7) receba a regra.
Voltando ao Algoritmo 7, após a chamada do procedimento montaRegra (linha 19) a
58
Algoritmo 8: Monta Regra
1 montaRegra(eCFG, nodoF, nodoP, grafo)
2 nodosDireita ← buscaNodoEsquerda(nodoF, nodoP, grafo);
3 foreach nodoD in nodosDireita do
4
adicionaNaRegra(regra, nodoE);
5
criaRegra(eCfg, nodoD, grafo);
6
if nodoD possui auto relacionamento then
7
if arco(nodoF, nodoD).pt == 1 then
8
adicionaNaRegra(regra, +);
9
else
10
adicionaNaRegra(regra, *);
11
end
12
else
13
if arco(nodo, nodoE).pt < 1 then
14
adicionaNaRegra(regra, ?);
15
end
16
end
17
adicionaNaRegra(regra, montaRegra(eCfg, nodoD, nodoP, grafo));
18
if nodoE not is Last(nodosEsquerda) then
19
adicionaNaRegra(regra, |);
20
end
21 end
22 retorna regra;
regra estará completa. Caso exista mais de um nodo no vetor nodosEsquerda, estes deverão ter
suas regras concatenada com o operador "ou" (linhas 20 e 21). Ao fim desses passos, a regra
deverá ser adicionada na eCFG (linha 24). Este processo será repetido no mínimo uma vez para
cada nodo presente no grafo, tendo em vista, que todos os nodos pertencem a pelo menos um
percurso no grafo.
Após a etapa de geração da eCFG, inicia-se o processo de transformação da eCFG em
um esquema XML. Através de um conjunto de regras, a ferramenta transforma todas as regras
contidas na eCFG em um esquema XML que corresponde à estrutura dos documentos XML
utilizados como entrada. Estas regras são baseadas no conteúdo da eCFG e de alguns dados
obtidos através da rede Bayesiana (i.e., atributos). As regras adotadas para realizar a transformação da eCFG em XSD são:
1. Rótulos cujo nome n tal que n ∈ V onde G = (V,E) são transformados em elementos;
2. Regras cuja produção é vazia (i.e. ) geram elementos simples do tipo string;
3. Regras cujas produções são compostas (i.e. A → (B C | D)) geram elementos de tipo
59
complexo;
4. Produções concatenadas (unidas pelo operado e) são declarados dentro de delimitadores
de grupo do tipo sequence;
5. Produções unidas pelo separador | (operador ou) são declaradas em delimitadores de
grupo do tipo choice;
6. Produções que possuem o fecho "positivo" de Kleene (+ ) devem possuir minOccurs = 1
e maxOccurs igual a "unbounded" não limitando o número de repetições aceitas;
7. Produções que possuem o fecho "estrela" de Kleene (*) devem possuir minOccurs = 0 e
maxOccurs igual a "unbounded" não limitando o número de repetições aceitas;
8. Produções que são seguidas do símbolo "?" devem possuir minOccurs = 0;
Neste trabalho não é abordado o problema da extração de tipos de dados. Os tipos de
dados básicos (i.e. inteiro, data, string e números com casas decimais) presentes nos elementos
do documento XML serão ignorados, afim de facilitar o processo de extração dos elementos,
sendo que todos os elementos que não possuem filhos ou os atributos presentes no documento
serão ’tipados’ como string. O problema de contexto dos elementos (elementos que possuem o
mesmo contexto porém nomes diferentes) também não será abordado neste trabalho, devida a
complexidade que representa.
A ferramenta aqui proposta é baseada no método apresentado por (PASQUALI; DUARTE, 2008). O método proposto por (PASQUALI; DUARTE, 2008) é apenas um método
teórico (não foi implementado). Ele cria um grafo etiquetado orientado através de um conjunto
de árvores, e então, infere uma eCFG baseada no grafo, utilizando cálculos de probabilidade
para estabelecer os filhos de um nodo e a ordem que estes devem aparecer. O método proposto
neste trabalho diferente do método proposto por (PASQUALI; DUARTE, 2008) não utiliza a
probabilidade para verificar as relações entre nodos, mas para verificar se um determinado elemento é obrigatório ou não. Neste trabalho, as relações entre os elementos são obtidas através
dos percursos feitos nas ligações estabelecidas na Rede Bayesiana.
O pExtract propõe três passos para realizar a extração do esquema de uma coleção
de documento C. Inicialmente, é gerada uma rede Bayesiana de Crença, onde os nodos representam os elementos de C e os arcos as inter-relações que estes elementos possuem. Então, é
60
inferida uma eCFG com base nos dados presentes na rede. E na última etapa a eCFG é transformada no esquema XML correspondente. Neste capítulo foram apresentadas as características
do método e alguns pseudocódigos que ilustram seu funcionamento, o próximo capítulo com
câncer trata da forma que o método foi implementado.
61
6 IMPLEMENTAÇÃO
Neste capítulo é apresentada a maneira pela qual o
pExtract foi implemen-
tado. Como dito anteriormente, o método proposto neste trabalho possui 3 passos, que no
pExtract foram implementados em 3 módulos. A Figura 6.1 apresenta a estrutura dos módulos do pExtract . Inicialmente, o pExtract irá receber como entrada uma coleção
de documentos XML C (possivelmente unitária). O primeiro módulo do pExtract receberá C, e com base nela será criada uma Rede Bayesiana. A saída do primeiro módulo (Rede
Bayesiana) é passada como entrada para o segundo módulo. O segundo módulo irá processar
a rede, realizando uma série de percursos no grafo. Utilizando as informações probabilísticas
armazenadas na rede irá gerar uma eCFG. A eCFG (saída do módulo 2) é passada para o último
módulo do pExtract . No último módulo é feita a transformação das regras da eCFG em
uma XSD. A XSD gerada contém a estrutura de C. Abaixo será apresentada de forma breve a
implementação dos módulos do pExtract .
pExtract
Modulo 1
Cria Rede
Modulo 2
Cria eCFG
Modulo 3
Cria XSD
Figura 6.1 – Estrutura dos módulos do pExtract
O módulo 1 do pExtract cria a Rede Bayesiana, sendo assim, ele deve interpretar
a coleção de documentos XML C e criar o grafo. Inicialmente, o módulo recebe C, que é
interpretada utilizando a API SAX. Para tal, foi desenvolvida uma classe denominada "SaxPar-
62
ser" que realiza o "parse" do documento XML. A API SAX2 faz o reconhecimento (parse) do
documento trabalhando com eventos. A API em Java obriga o usuário a implementar 5 eventos:
(i) startDocument chamado quando o documento é iniciado, (ii) startElement chamado quando
uma tag inicia, (iii) characters captura o conteúdo de um elemento, (iv) endElement chamado
quando é encontrado o fechamento da tag, e , (v) endDocument chamado quando o documento
acaba.
A Rede Bayesiana foi implementada com base em 4 classes. Estas classe são apresentadas pelo diagrama de classes da Figura 6.2. São elas:
1. Graph, que representa a base da rede Bayesiana. A classe possui dois atributos: nodes,
que armazena todos os nodos presentes no grafo/rede, e arcs, que armazena os arcos/relacionamentos presentes no grafo.
2. Node, que representa um nodo da rede que mapeia um elemento do documento XML.
A classe possui quatro atributos: (i) l que armazena o nome (label) do elemento XML,
(ii) value armazena os valores que o elemento possui no documento, (iii) t armazena o
número de ocorrências do elemento no decorrer do documento XML, e (iv) attributes que
armazena todos os atributos que o elemento possui no documento.
3. Arc, que representa os arcos/relações da rede. A classe possui 6 atributos: (i) v é a origem
do arco, (ii) w é o destino do arco, (iii) s apresenta o tipo da relação (’c’-filho, ’s’-irmão
a direita), (iv) n número de vezes que o relacionamento se repete, (v) u é uma lista dos
nodos que originam o relacionamento (i.e. , se a possui dois filhos b e c, então b e c
possuem um relacionamento de irmão à direita originado por a), e (vi) pt que apresenta
a probabilidade do relacionamento ocorrer.
4. Attribute, que armazena a rede Bayesiana. A classe possui dois atributos: name que
armazena o nome do atributo do elemento, value que armazena os valores dos atributos
do elemento, e n o número de vezes que o atributo aparece no elemento no decorrer do
documento XML.
O grafo é criado através dos eventos que ocorrem na classe SaxParser. Quando uma
tag é aberta no documento, o método startElement (Figura 6.3) é invocado, e quando a tag é
encerrada o método endElement (Figura 6.4) é chamado.
2
www.saxproject.org/
63
Figura 6.2 – Diagrama de Classes - Modulo 1 pExtract
A Figura 6.3 apresenta a forma como o método startElement foi implementado. Quando
esse método é chamado, ele inicialmente atribui o nome da tag que originou o evento à variável
tagAtual. Então verifica a existência de um nodo armazenado na variável atual (linha 110).
Caso exista, o nodo que está armazenado na variável é adicionado a pilha e a variável ant é
reinicializada com null. A variável pilha representa uma pilha onde são adicionados elementos
que possuem filhos. A variável ant sempre contém um elemento anterior ao atual. É feita uma
busca no grafo para verificar se exite um nodo que represente a tag atual, se existir, é retornado
o objeto que o representa, senão é criado um novo objeto nodo (que possuirá o nome da tag)
e este é adicionado ao grafo (linhas 114 a 118). Verifica-se então, se existe algum elemento
na pilha. Caso exista, o elemento que estiver no topo é o pai do elemento atual no documento
XML. Sendo assim, é criado um arco que represente o relacionamento entre o topo da pilha e o
nodo atual. Verifica-se então, se existe um elemento anterior (variável ant), caso afirmativo, o
elemento atual é irmão à direita do elemento ant no documento XML. Assim, é criado um arco
que representa este relacionamento.
A Figura 6.4 apresenta a implementação feita para o método endElement. Inicialmente,
64
Figura 6.3 – Método startElement
a variável tagAtual recebe o valor null. Esta variável armazena o nome da tag atual. Este método
é chamado quando um fechamento de tag é encontrado. Assim, quando ele é invocado a tag
atual chegou ao fim. Então, a variável ant recebe o nodo atual, ou seja se outra tag for aberta,
será irmã da atual. Caso a variável atual esteja nula, quer dizer que houve dois fechamentos
de tags consecutivos (i.e., encontrado o fechamento de um elemento e na sequência o de seu
pai). Se isso ocorrer, deve-se desempilhar um elemento da pilha e este deve ser considerado o
anterior (ant - linha 147 e 148). Caso a pilha esteja vazia, o método acusa um erro, pois foram
fechadas mais tags do que haviam sido abertas (isso pode mostrar que o documento de entrada
é mal formado).
Figura 6.4 – Método endElement
Através destes dois métodos toda a Rede Bayesiana é gerada. A cada tag aberta no
65
documento a variável atual o representa, quando é encontrado o fechamento da tag a variável
recebe um valor nulo. Caso uma tag seja aberta e a variável atual ainda possua um valor válido,
significa que o novo elemento é filho do elemento atual, ou seja, foi avançado um nível na
hierarquia da estrutura do documento. Sendo assim, a pilha implementada nos métodos visa
representar a hierarquia do documento. O elemento que estiver na base da pilha é o elemento
raiz do documento, e cada elemento subsequente um nível abaixo dele, portanto o elemento do
topo, representa o pai do elemento atual. Desta forma, a cada fechamento de tag é verificado se
um elemento atual existe, caso exista este é tido como nulo, porém se este já for nulo, significa
que deve-se voltar um nível na hierarquia. Assim, o elemento do topo da pilha é desempilhado
e vira o elemento anterior, pois até que seja encontrado outro fechamento de tag, os elementos
encontrado estarão no mesmo nível deste. Ao fim da leitura da coleção de documentos a Rede
Bayesiana estará completa, e será passada como entrada para o segundo módulo.
O segundo módulo irá percorrer a Rede Bayesiana e criará a eCFG. Para criar e armazenar a eCFG foram criadas duas classes: Gramatica e Regra. A classe Gramatica armazena
todas as regras que constituem a gramática. Esta classe possui os métodos responsáveis por gerar a eCFG. A classe Regra implementa o comportamento das regras da eCFG. Ela é constituída
de dois atributos: rotulo que contém o rótulo/nome (lado direito da regra) da regra e producao
que armazena a produção da regra.
Inicialmente, é criado um objeto do tipo Gramatica e para o construtor deste objeto, é
passado o objeto grafo (que contém a Rede Bayesiana). A partir do grafo, é feita a busca pelo
nodo N que representa o elemento raiz da coleção de documentos. Após identificado o nodo,
será criada uma regra na qual o nome de N será a cabeça e os nodos que forem sorvedores
(destino) de arcos que partam dele farão parte da produção. A ordem em que estes nodos serão
apresentados na produção da regra é importante, pois esta define a ordem em que os elementos
aparecem nos documentos XML. Sendo assim, deve-se identificar o nodo que aparecerá primeiro na produção. Este nodo, deverá possuir um arco do tipo filho com N e possuir apenas
arcos do tipo irmão à direita como origem. Após selecionado o nodo, este é adicionado a produção e realizado um percurso pelos nodos que possuem arco do tipo irmão a direita com ele
(desde que esta seja originada por N ). A cada nodo que é adicionado a produção de N , é feita
uma chamada recursiva do método criaRegra passando o nodo como parâmetro. Desta forma
este método cria todas as regras da gramática.
O método criaRegra deve criar uma regra para o nodo N que lhe for passado como
66
parâmetro. O método cria a regra com o nome do nodo N e seleciona o filho mais à esquerda
dele (nodo que possuir um arco do tipo filho com N e nenhum arco do tipo irmão à direita
originada por N ). Para cada elemento mais a esquerda filho de N encontrado, é chamado o
método montaRegra que irá realizar o percurso pelos irmãos a direita dos nodos e retornará
uma regra parcial. As regras parciais são concatenadas utilizando o operador "|" (ou). Nodos
que não possuem filhos (não deve possuir arcos do tipo filho como origem) geram regras cuja
produção é Epsilon.
O método montaRegra faz o percurso baseada em dois nodos recebidos como parâmetro
(Nf e Np ), sendo Nf o nodo o qual se busca o irmão a direita e Np o nodo que representa o
elemento pai do relacionamento. O método então seleciona todos o nodos que possuem um
relacionamento do tipo irmão à direita com Nf (originado por Np ), e a partir destes chama
recursivamente o método montaRegra. Quando existir um Nf que não possua mais irmãos à
direita o método retorna o nome do nodo. Assim, conforme o método retorna, o percurso feito
é armazenado e este gera a produção da regra.
Após gerada a eCGF, está é passada para o último módulo do pExtract . Este módulo
implementa uma série de regras que transformam uma regra da eCFG em um elemento da XSD.
Sendo assim, foi criada uma classe chamada XMLSchema. No construtor desta classe, são feitas
inicialmente as definições de cabeçalho da XSD. Então é invocado um método implementado da
classe Gramatica que transforma cada regra da gramática em um elemento da XSD. As regras
utilizadas para realizar esta transformação, foram apresentadas no capítulo anterior.
Neste capítulo foi apresentada de maneira breve a implementação do pExtract .
Foram implementados o 3 módulos do método. O primeiro módulo faz a leitura do documento
XML utilizando a API SAX e cria a Rede Bayesiana. A rede foi construída utilizando 4 classes:
(i) Graph que armazena os nodos da rede e seus arcos, (ii) Node que representa os elementos
contidos no documento XML com seu atributos, (iii) Arcs que representa um relacionamento
entre dois elementos e (iv) Attribute que representa um atributo do nodo. Já para implementação
do segundo módulo que transforma a rede em uma eCFG foram utilizadas 2 classes: Gramatica
que é constituída de um conjunto de regras e Regra que representa uma regra e é constituída de
um rótulo e de uma produção. Para implementação do último módulo apenas uma classe foi
utilizada. A classe XMLSchema contém as informações necessárias para criar a XSD baseada
nos elementos contidos na gramática.
No próximo capítulo serão apresentados alguns experimentos realizados utilizando o
67
pExtract . O primeiro é um estudo de caso que mostrará passo a passo o funcionamento
do pExtract . Na sequência são apresentados mais alguns experimentos, dos quais são
apresentados os resultados.
68
7 EXPERIMENTOS COM O PEXTRACT
Neste capítulo são apresentados alguns resultados obtidos com o pExtract . Inicialmente, é apresentado um estudo de caso utilizando o documento XML X da Figura 7.1, para
demonstrar passo a passo o funcionamento do método e em seguida são apresentados alguns
resultados de testes com coleções de documentos.
7.1
ESTUDO DE CASO
Neste seção é utilizado um estudo de caso para explicar o pExtract assim como foi
feito com outros métodos no Capítulo 3. O documento XML X apresentado pela Figura 7.1 é
utilizado como entrada para o método.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
<motos>
<opcional > F r e i o Disco< / opcional >
<revisao>
<km>15000 < /km>< v a l o r > 3 5 0 , 0 0 < / v a l o r >
<km>35000 < /km>< v a l o r > 6 0 0 , 0 0 < / v a l o r >
</ revisao>
< / moto>
<moto>
< o p c i o n a l >Abs< / o p c i o n a l >
<revisao>
<km>1000 < /km>< v a l o r > 1 7 , 0 0 < / v a l o r >
<km>5000 < /km>< v a l o r > 3 5 , 0 0 < / v a l o r >
<km>10000 < /km>< v a l o r > 3 2 0 , 0 0 < / v a l o r >
</ revisao>
< / moto>
<modelo> B i z < / modelo>
<ano_modelo>2013 < / ano_modelo>
< / moto>
< / motos>
Figura 7.1 – Documento XML representando um BD de motos (Figura 2.1)
O primeiro módulo (Figura 6.1) do pExtract faz a criação da Rede Bayesiana com
base no documento XML de entrada. A leitura do documento é feita utilizando a API SAX que
faz uso de eventos para realizar o parsing do documento. Quando o parser inicia a leitura do
documento, é lançado o evento de início do documento. Ao encontrar o elemento motos (linha
3 de X) a API irá lançar o evento de abertura de tag. Neste evento, o pExtract verifica
se o elemento motos já foi mapeado para algum nodo, como ele não foi, um nodo é criado e
69
adicionado ao grafo. Verifica-se então se o elemento possui algum atributo. O elemento motos
não possui atributos, mas caso existissem, estes seriam adicionados ao nodo criado. Então o
pExtract verifica se exite algum elemento na pilha. A pilha em questão armazena o níveis
hierárquicos do documento. Neste momento, a pilha está vazia então nada é feito. É verificada
a existência de um elemento anterior. Como motos é o primeiro elemento não existe nenhum
elemento anterior. Então o nodo criado para motos é mantido em uma variável que armazena o
nodo atual. É dada sequência à leitura do documento.
O próximo elemento lido é moto. Quando for encontrada a abertura de tag para o elemento é chamado novamente o evento de abertura de tag. É verificado se já existe um nodo que
mapeia moto, como não existe é criado um nodo e adicionado ao grafo. Então é verificado se
existe um nodo atual, como existe (motos) este é empilhado e se houver algum nodo anterior
a variável tem seu valor re-setado, pois está em um nível hierárquico diferente de moto. Então
é verificado se existem nodos na pilha. A pilha possui o nodo motos (topo da pilha) então é
criado um arco entre os nodos motos e moto do tipo ’c’. É verificado então se existe algum
nodo armazenado como nodo anterior. Como neste momento ainda não existe nodo anterior o
nodo moto não possui irmãos. E o nodo criado para moto será armazenado também como nodo
atual.
valor,5,0
(c,2,<>,1.0)
motos,1,3
(s,1,<motos>,1.0)
(c,1,<>,1.0)
(s,2,<revisao>,1.0)
(c,2,<>,0.66)
revisao,2,10
moto,3,11
(c,2,<>,1.0)
(c,2,<>,0.66)
km,5,0
(c,3,<>,1.0)
(c,3,<>,0.66)
(s,2,<moto>,0.66)
(c,1,<>,0.33)
opcional,3,0
(s,1,<moto>,0.33)
ano_modelo,1,0
marca,2,0
(s,2,<moto>,0.66)
(s,1,<moto>,0.33)
(s,2,<moto>,1.0)
modelo,3,0
Figura 7.2 – Rede Bayesiana gerada através de X
Seguindo na leitura de X, é lida a tag marca. Assim, é verificado se existe um nodo
atual, como este existe é adicionado à pilha e se houver um nodo anterior este receberá o valor
nulo. É criado então, um arco do tipo ’c’ entre marca e o topo da pilha (moto). Como não existe
70
nenhum nodo anterior (pois este foi anulado) o nodo lido é armazenado como atual e é dada
sequência na leitura do documento. Então é encontrado o fechamento da tag marca. Assim, é
verificado se existe um nodo atual. Caso exista o algoritmo irá atribuir a o nodo anterior o nodo
armazenado como nodo atual. E se não existir, o elemento do topo da pilha é desempilhado e
armazenado como nodo anterior. Em ambos os casos, o elemento atual recebe o valor nulo.
Seguindo a leitura do documento, é encontrada a abertura de tag para o elemento modelo.
Inicialmente, é verificado se existe um nodo que mapeia o elemento, como ainda não existe é
criado um novo nodo. É verificado então se existe um nodo atual. Como o nodo atual possui
um valor nulo, é criado um arco do tipo ’c’ entre o topo da pilha (que asseguradamente não
estará vazia) e o nodo recém criado. Então é verificado se existe um nodo anterior, como o
nodo marca está armazenado como anterior é criado um arco do tipo ’s’ entre marca e modelo
originada pelo nodo que estiver no topo da pilha, no caso o nodo moto. Assim, estes passos são
executados para todas as tags do documento X. Ao final do processo de leitura do documento
a Rede Bayesiana terá sido gerada. A Figura 7.2 apresenta a rede criada a partir de X.
O segundo módulo do pExtract (Figura 6.1) irá inferir um eCFG baseada nas informações da Rede Bayesiana. Inicialmente, o método irá identificar o nodo no grafo que
representa o elemento raiz de X. O nodo etiquetado motos ,1, 3 (Figura 7.2) é o elemento
raiz. Após identificado será criada uma regra na qual o nodo motos será a cabeça (lado direito
da regra) e os nodos que possuírem arcos do tipo filho com ele formarão sua produção (lado
esquerdo da regra). Para criar esta produção, inicialmente o método irá identificar o nodo que
deve aparecer mais à esquerda da regra. Este nodo deve possuir apenas arcos do tipo irmão à
esquerda como origem (salvo se ele for origem e destino do arco). Assim, verifica-se através
da rede (Figura 7.2) que o nodo a aparecer primeiro na regra é moto. Após identificado o nodo,
será feito a partir deste um percurso passando pelos arcos do tipo irmão à direita originadas
pelo nodo motos (nodo que dá nome a regra). O nodo moto é adicionado a regra, e então é feita
uma busca no grafo para identificar quais os nodos possuem arcos do tipo irmão à direita com
o nodo moto. A busca irá retornar apenas o próprio nodo, já que ele possui apenas um arco
do tipo irmão à direita e esta possui como destino o próprio nodo (autorelacionamento). Como
o nodo moto possui um autorelacionamento na regra é adicionado o fecho + ou * de Kleene.
Como a probabilidade do relacionamento ocorrer é de 100% é adicionado o fecho +. A regra
gerada é apresentada na primeira linha da Figura 7.3.
Após a construção da primeira regra, a eCFG tem suas regras construídas com base na
71
motos ← moto+;
moto ← marca? modelo (opcional ∗ revisao | ano_modelo);
marca ← ;
modelo ← ;
opcional ← ;
revisao ← km valor;
km ← ;
valor ← ;
ano_modelo ← ;
Figura 7.3 – eCFG gerada partir da Rede Bayesiana (Figura 7.2)
ordem em que o nodos aparecem na produção. Assim, a próxima regra criada será para o nodo
moto. Cria-se então uma regra cuja cabeça é moto e que tem sua produção definida pelos arcos
do tipo filho das quais ele é a origem. A ordem em que os nodos aparecem na produção é
definida com base nos arcos do tipo irmão à direita que seus filhos possuem, ou seja, dos arcos
do tipo irmão à direita que são originadas por moto (i.e., arcos que possem em sua tupla u o
nodo moto, sendo o arco definido pelo conjunto (v,w,(s,n, <u>, pt)). A produção inicia com
o filho mais à esquerda de moto, ou seja, marca. Como marca possui apenas 66% de chance
de ser filha de moto e não possui autorelacionamento deve aparecer como elemento opcional
na gramática, sendo seguido do ’?’ na produção (segunda linha Figura 7.3). Então é feito o
percurso passando pelos arcos do tipo irmão à direita originadas por moto partindo de marca, e
cada nodo do percurso é adicionado à regra. Então o próximo nodo a ser adicionado na regra
será modelo. Como o arco entre moto e modelo possui 100% de chance de ocorrer modelo é
adicionada na regra como elemento obrigatório. O próximo nodo a ser adicionado na regra
deve ser irmão à direita de modelo. Como na rede existem dois nodos com esta propriedade
(opcional e ano_modelo) devem ser gerados dois percurso concatenados com o operador ou (|).
Assim, é gerado um percurso a partir de opcional e outro a partir de ano_modelo (segunda linha
da Figura 7.3).
Este processo é repetido até que todos os nodos pertencentes à rede tenham originado
uma regra. Nodos que não possuem filhos (arco do tipo filho como origem) geram regras cuja
produção é vazia denotada pelo símbolo (e.g., terceira e quarta linhas da Figura 7.3). Já nodos
que possuem filhos possuem regras com produções mais elaboradas (i.g., primeira linha da
Figura 7.3). Na Figura 7.3 é apresentada a eCFG gerada pelo segundo módulo do pExtract .
O último módulo do pExtract converte a eCFG em uma XSD. Este módulo utiliza
uma série de propriedades propostas no Capítulo 5 para transformar uma regra da eCFG em
72
um elemento de XSD. Assim, cada uma das regras contidas na eCFG é transformada em um
elemento da XSD, seguindo a ordem em que estas aparecem na eCFG. A Figura 7.4 apresenta
a XSD gerada.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
<? xml v e r s i o n = " 1 . 0 " ? >
<xs:complexType>
<xs:sequence>
< x s : e l e m e n t r e f = " moto " maxOccurs = " unbounded " / >
</ xs:sequence>
< / xs:complexType>
</ xs:element>
<xs:complexType>
<xs:sequence>
< x s : e l e m e n t r e f = " marca " m i n O c c u r s = " 0 " / >
< x s : e l e m e n t r e f = " modelo " / >
<xs:choice>
<xs:sequence>
< x s : e l e m e n t r e f =" o p c i o n a l " minOccurs="
0 " maxOccurs = " unbounded " / >
< x s : e l e m e n t r e f =" r e v i s a o " / >
</ xs:sequence>
< x s : e l e m e n t r e f = " ano_modelo " / >
</ xs:choice>
</ xs:sequence>
< x s : a t t r i b u t e name= " c i l i n d r a d a s " t y p e = " x s : s t r i n g " /
>
< / xs:complexType>
</ xs:element>
< x s : e l e m e n t name= " marca " t y p e = " x s : s t r i n g " / >
< x s : e l e m e n t name= " o p c i o n a l " t y p e = " x s : s t r i n g " / >
< x s : e l e m e n t name= " r e v i s a o " / >
<xs:complexType>
<xs:sequence>
< x s : e l e m e n t r e f = " km " / >
< x s : e l e m e n t r e f =" v a l o r " / >
</ xs:sequence>
< / xs:complexType>
< / x s : e l e m e n t >< x s : e l e m e n t name= " km " t y p e = " x s : s t r i n g " / >
< x s : e l e m e n t name= " v a l o r " t y p e = " x s : s t r i n g " / >
< x s : e l e m e n t name= " ano_modelo " t y p e = " x s : s t r i n g " / >
< / xs:schema>
Figura 7.4 – XSD gerada pelo pExtract a partir de X
O esquema gerado pelo pExtract para o documento X é compatível com os esquemas gerados pelos outros métodos apresentados neste trabalho. Comparando a XSD gerada
pelo pExtract com a XSD criada pelo método de Inferência Gramatical (Figura 3.8), XStruct (Figura 3.13) e do XTLSM (Figura 3.17). Percebe-se inicialmente, que as abordagens de
Inferência Gramatical, XStruct e XTLSM realizam a extração de tipos primitivos do elemento
o que não é contemplado pelo pExtract . Além disso, percebe-se que a XSD gerada pelo
pExtract possui maior semelhança com as XSDs geradas pelo XStruct e XTLSM, pois, a
XSD gerada pelo método de Inferência Gramatical fixa o número máximo de repetições de um
elemento, o que não acontece nos demais métodos onde repetições são assinaladas com o valor
73
"unbonded" que permite repetições infinitas.
Nesta seção foi apresentado um estudo de caso aplicado ao pExtract . O estudo
de caso consistiu em utilizar como entrada para o pExtract o documento X e através dos
passos do algoritmo extrair seu esquema. Então é feita uma rápida comparação entre a XSD
gerada e as XSDs geradas para X por outros métodos apresentados anteriormente (Capítulo 3).
Através desta comparação percebe-se que a XSD gerada pelo pExtract é compatível com as
XSDs geradas pelos demais métodos. Na próxima seção são apresentados alguns resultados de
experimentos realizados com o pExtract .
7.2
OUTROS EXPERIMENTOS
As coleções de documentos utilizadas nos experimentos foram geradas a partir de dois
aplicativos. Inicialmente, foram geradas algumas coleções utilizando o XMLGen do XMark3 ,
um projeto que reúne uma série de soluções que auxiliam na criação de benchmarks utilizando
documentos XML. O XMLGen foi utilizado para gerar apenas dois experimentos devido à restrição que ele impõe. O XMLGen apenas gera documentos que respeitem uma DTD específica
imposta pelos desenvolvedores, podendo o usuário apenas alterar o tamanho do documento. Devido a este fato, foi selecionado o Oxygen XML Developer desenvolvido pela SyncroSoft SLR4 .
O Oxygen XML Developer permite gerar documentos XML baseados em uma XSD informada
pelo usuário. O usuário pode também controlar o número máximo de repetições dos elementos
e a profundidade máxima presente no documento XML.
A Tabela 7.1 apresenta resultados obtidos extraindo o esquema de coleções (unitárias) de
documentos XML. Cada linha da tabela representa uma coleção de documentos e seus respectivos resultados. As colunas da tabela apresentam informações sobre o documento ou resultados
dos experimentos. A primeira coluna da tabela apresenta um identificador do experimento. A
segunda coluna (Profundidade) apresenta o número máximo de camadas hierárquicas que existem para os elementos do documento, ou seja, dada a representação em árvore de um documento
XML D a profundidade será a diferença máxima em níveis que existe entre um elemento das
folhas e o elemento raiz de D (e.g., a coleção A apresenta profundidade 4). A terceira coluna
(Num. Elementos) representa o número de elementos (sem contar repetições) que compõe o
documento XML (e.g., as coleções A,B,C e D apresentam número de elementos 8). A quarta
3
4
xml-benchmark.org
www.oxygenxml.com
74
coluna (Num. Tot. Elementos) apresenta o número total de elementos presentes no documento
(e.g., a coleção D apresenta 144.295.969 ocorrências de elementos). A quarta coluna apresenta
o tamanho em bytes da coleção de documentos utilizada como entrada (e.g., a coleção G possui
um tamanho de 915,7 MB). A última coluna apresenta o tempo que o pExtract levou para
realizar a extração do esquema (e.g., a coleção A foi processada em 0,176s). Os dados da tabela foram gerados a partir da execução dos experimentos em um computador com o sistema
operacional Ubuntu Linux 13.04 (32 bits) com um processador Intel Core i5 - 480M (2,66GHz,
Cache 3MB) com 4GB de memória RAM. Para computar os tempos foi utilizado o comando
time do Linux.
Identificador Profundidade Num. Elementos Num. Tot. Elementos Tamanho Coleção (Bytes) Tempo Execução
A
4
8
115
4,3 KB
0m0,176s
B
4
8
482.959
21,1 MB
0m1,576s
C
4
8
17.777.919
806,3 MB
0m17,984s
D
4
8
144.295.969
6,7 GB
3m31,140s
E
10
19
146
2,4 KB
0m0,188s
F
10
19
508.488
22,2 MB
0m1,616s
G
10
19
20.156.021
915,7 MB
0m29,094s
H
10
19
452.806.093
21,2 GB
9m13,956s
Tabela 7.1 – Resultados dos experimentos
Com base nas informações presentes na tabela, pode-se afirmar que o tempo de extração do pExtract independe da profundidade do documento XML, e independe também do
número de elementos (sem contar repetições). O método é dependente apenas do número total
de elementos que o documento XML possui (contando repetições). Por exemplo, a coleção B
possui uma profundidade 4 e possui 8 tipos de elementos. Já a coleção F possui profundidade
10 e 19 elementos (sem contar as repetições). Apesar da diferença de profundidade entre B e F
ambos possuem tempo de processamento muito semelhante, 1,576 segundos e 1,616 segundos
respectivamente. Este padrão se repete nos demais casos de teste apresentados. Coleções com
número total de elementos semelhantes tendem a possuir tempos de processamento semelhante.
Percebe-se através da tabela que a maior parte dos experimentos possui um tempo de
extração abaixo de 30 segundos, sendo que, apenas dois dos experimentos excedem este tempo
(H e D). Os experimentos H e D possuem um número elevado de elementos 452.806.093 e
144.295.969 respectivamente. Devido a este fato apresentam um tempo de extração superior aos
demais experimento, sendo que, o experimento H teve seu esquema extraído em 9m13,956s e
D em 3m31,140s.
Durante o processamento dos experimentos, foi observado também que o primeiro módulo do pExtract consome cerca de 80% do tempo total de processamento da coleção de
75
documentos XML. Assim, a etapa de criação da Rede Bayesiana representa um gargalo no processamento do pExtract . Este fato ocorre devido à complexidade envolvida na criação da
rede. Ao ler um elemento pertencente ao documento, o pExtract deve verificar se o nodo já
foi mapeado. Se o nodo já estiver mapeado é retornado um ponteiro para o endereço deste nodo.
Isso evita que dois nodos representem o mesmo elemento, o que poderia causar ambiguidades
na eCFG. Paralelamente, o módulo também evita que sejam criados arcos repetidos. Quando é
feita a tentativa de criar um arco, o pExtract verifica se este arco já existe. Se existe as probabilidades atreladas a ela são atualizadas, senão é criado o arco. Ambos os processos citados
são de custo elevado e possuem uma complexidade O(n2 ).
Nesta seção foram apresentados alguns experimentos utilizando o pExtract . Para
cada experimento foi gerada uma coleção de documentos XML e esta foi utilizada como entrada para o pExtract . As coleções de documentos foram geradas através de um esquema
conhecido. Após cada execução do pExtract , o esquema gerado era comparado ao esquema que havia sido utilizado para criar a coleção de documentos. Para todos os experimentos
realizados, o esquema gerado pelo pExtract foi compatível com o esquema original da coleção. Comprova-se assim, que o pExtract realiza a extração de um esquema que contém
a estrutura do documento. Não foram realizados testes que comparem o desempenho entre o
pExtract e os métodos encontrados na literatura, pois não foram encontradas implementações destes métodos.
No decorrer do capítulo foram apresentados alguns experimentos realizados com
pExtract . Inicialmente, foi aplicado o estudo de caso do documento X que ilustrou passo
a passo o funcionamento do método. Posteriormente foi apresentada uma tabela que possui
informações sobre alguns experimentos. As coleções de documentos XML dos experimentos
foram gerados a partir das ferramentas XMLGen e Oxygen XML Developer utilizando esquemas
conhecidos. Através destes experimentos foi apresentada a eficiência da extração dos esquemas
gerados a partir do pExtract . O próximo capítulo apresenta a conclusão do trabalho e
algumas propostas de trabalhos futuros.
76
8 CONCLUSÃO
O XML é muito utilizado na Web para troca de dados entre aplicações, devido a sua
flexibilidade. Porém, essa flexibilidade faz com que o processamento dos documentos possa ser
custoso, pois sua estrutura é desconhecida a priori (esquema). A maior parte dos documentos
XML que circulam pela Web não possui um esquema associado. Para auxiliar as aplicações
no processamento destes documentos, faz-se necessária uma ferramenta que possa extrair o seu
esquema. Neste trabalho foram apresentadas algumas abordagens para a extração de esquema
(i.e., XSTRACT, Inferência Gramatical, Min&Chung, XStruct e XTLSM). Cada uma delas
utiliza uma técnica distinta para realizar a extração. Porém, apenas uma abordagem descrita em
(PASQUALI; DUARTE, 2008) utiliza a probabilidade para inferir o esquema.
Assim, este trabalho propõe um método que realiza a extração de esquemas utilizando
como base a probabilidade. O método é dividido em 3 passos. O primeiro cria uma Rede
Bayesiana a partir da coleção de documentos XML utilizada como entrada. O segundo módulo
irá gerar uma eCFG com base na Rede Bayesiana. E o último módulo transforma a eCFG em
uma XSD. A ferramenta pExtract é a implementação do método proposto neste trabalho.
O pExtract foi apresentado passo a passo utilizando um estudo de caso e foi utilizado em
alguns experimentos de extração de esquemas.
Através do estudo de caso percebeu-se que o esquema gerado é compatível com o esquema gerado pelos demais métodos encontrados na literatura. Percebeu-se também que o
esquema gerado pelo pExtract possui maiores semelhanças com as XSDs geradas pelos
método XStruct e XTLSM, já que o método de Inferência Gramatical fixa um número máximo
de repetições para alguns elementos.
Com os experimentos foi possível observar: (i) a ferramenta mostrou bons tempos de
execução mostrando-se escalável, (ii) que 80% do tempo de execução da ferramenta é utilizado pelo primeiro módulo, (iii) apesar do esquema gerado descrever a coleção de documentos
XML utilizada como entrada, nem sempre a XSD gerada é mínima, (iv) a ferramenta tem seu
tempo de resposta atrelado unicamente ao número total de elementos da coleção (contando as
repetições), e (v) o esquema gerado através da ferramenta foi compatível com os esquemas
utilizados para gerar as coleções de documentos utilizadas no experimento.
O primeiro módulo do pExtract realiza a criação da Rede Bayesiana. Este módulo
representa um gargalo no tempo de execução do pExtract consumindo cerca de 80% do
77
tempo total de execução da ferramenta. O algoritmo responsável pela criação da rede possui
complexidade O(n2 ), sendo n o número de elementos (distintos) que o documento XML possui.
O pExtract nem sempre cria uma XSD mínima para a coleção dos documentos
utilizada como entrada. Apesar da XSD gerada descrever a estrutura de toda coleção utilizada
como entrada, alguns elementos presentes na XSD podem ser reduzidos. Por exemplo, quando
na entrada existe um elemento a que em uma ocorrência possui como filhos os elementos b, c, d
e e, em outra os filhos g, c, d e e. A regra mínima para a eCFG, que apresenta a estrutura de a
seria a ← (b|g) c d e. Para gerar as regras da eCFG o pExtract realiza percursos pelo grafo
com base nos nodos considerados filhos mais à esquerda do elemento. Assim para o elemento
a são realizados dois percursos na rede, um partindo de b e o outro partindo de g. Os percursos
gerados são b c d e e g c d e respectivamente. Para gerar a regra da eCFG estes percursos são
concatenados utilizando o operador | (ou). Desta forma, a regra gerada pelo pExtract para
o elemento a será a ← (b c d e|g c d e). Percebe-se que se esta regra produz o mesmo resultado
que a regra a ← (b|g) c d e, porém não é simplificada.
O pExtract realiza a extração de um esquema que contém a estrutura de todos os
elementos do documento XML. Porém estes elementos são tipados como string sem levar em
consideração o real tipo de dado que o elemento armazena.
Os pontos negativos que a ferramenta pExtract apresenta (i.e., XSD gerada nem
sempre é minima e não realiza extração de tipos) não geram grandes implicações ao esquema
gerado. Estas carências da ferramenta fazem com que ela possua um tempo reduzido de execução, tendo em vista que não existe um processo de fatoração ou simplificação das regras da
eCFG e de extração de tipos. Assim, pode-se afirmar que apesar das carências que a ferramenta
possui ela apresenta um funcionamento satisfatório, realizando a extração de um esquema que
representa a coleção de documentos XML utilizada como entrada em um tempo relativamente
curto.
8.1
TRABALHOS FUTUROS
Baseado no que foi descrito na seção anterior, têm-se as seguintes perspectivas de con-
tinuação desse trabalho:
1. Otimizações no módulo de criação da Rede Bayesiana;
2. Simplificação das regras da eCFG;
78
3. Extração de tipos básicos dos elementos;
4. Elaboração de uma métrica que consiga quantificar a qualidade do esquema gerado;
5. Realizar um benchmark das ferramentas de extração de esquema e compará-las com o
pExtract , afim de descobrir qual abordagem produz o melhor esquema em menos
tempo.
6. Adaptar o pExtract para que este possa ser capaz de extrair esquemas JSON e/ou
RDF;
Existem algumas perspectivas que irão melhorar o pExtract adicionando a extração
de tipos básicos dos elementos e a simplificação de regras, o que implicará em uma melhora do
esquema gerado. Porém, é importante ressaltar que atualmente a ferramenta realiza a extração
de uma XSD compatível com a estrutura da coleção utilizada com entrada e em um curto tempo
de execução.
79
REFERÊNCIAS
AMIEL, S.; HARRUSI, S.; AVERBUCH, A. XML Schema Inference from Positive Example: the tlsm approach. 2008.
BARBOSA, D.; MIGNET, L.; VELTRI, P. Studying the XML Web: gathering statistics from
an xml sample. World Wide Web, Hingham, MA, USA, v.8, n.4, p.413–438, Dec. 2005.
BEX, G. J.; NEVEN, F.; BUSSCHE, J. Van den. DTDs versus XML schema: a practical study.
Proceedings of the 7th International Workshop on the Web and Databases: colocated with
ACM SIGMOD/PODS 2004, [S.l.], p.79–84, 2004.
BRÜGGEMANN-KLEIN, A.; WOOD, D. Regular tree languages over non-ranked alphabets. [S.l.]: Citeseer, 1998.
CARRASCO, R. C.; ONCINA, J. Learning stochastic regular grammars by means of a state
merging method. In: Grammatical Inference and Applications. [S.l.]: Springer, 1994. p.139–
152.
CHIDLOVSKII, B. Schema Extration from XML Data: a grammatical inference approach.
KRDB’01 Workshop (Knowledge Representation and Databases), [S.l.], p.10, 2001.
CHIDLOVSKII, B. Schema extraction from XML collections. In: ACM/IEEE-CS JOINT
CONFERENCE ON DIGITAL LIBRARIES, 2., New York, NY, USA. Proceedings. . . ACM,
2002. p.291–292. (JCDL ’02).
COMON, H. et al. Tree Automata Techniques and Applications. release October, 12th 2007,
Available on: http://www.grappa.univ-lille3.fr/tata.
COPPIN, B. Inteligência artificial. Rio de Janeiro: LTC, [S.l.], 2010.
DUARTE, D.; LIMA, A. Esquemas XML. In: MORO, M.; BRAGAGNOLO, V.; HEUSER,
C. (Ed.). Gestão de Dados na Web e XML. [S.l.]: No Prelo, 2013.
FAWCETT, J.; AYERS, D.; QUIN, L. R. E. Beginning XML. 5th.ed. Birmingham, UK: Wrox
Press Ltd., 2012.
GAROFALAKIS, M. et al. XTRACT: a system for extracting document type descriptors from
xml documents. SIGMOD Rec., New York, NY, USA, v.29, n.2, p.165–176, 2000.
80
HAROLD, E. R. XML 1.1 Bible. [S.l.]: Wiley. com, 2004. v.136.
HEGEWALD, J.; NAUMANN, F.; WEIS, M. XStruct: efficient schema extraction from
multiple and large xml documents. 22nd International Conference on Data Engineering
Workshops (ICDEW’06), [S.l.], p.81–81, 2006.
MELLO, R. d. S. et al. Dados Semi-Estruturados. SIMPÓSIO BRASILEIRO DE BANCO
DE DADOS, [S.l.], 2000.
MILO, T.; SUCIU, D.; VIANU, V. Typechecking for XML transformers. Proceedings of the
nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, New York, NY, USA, p.11–22, 2000.
MIN, J.-K.; AHN, J.-Y.; CHUNG, C.-W. Efficient extraction of schemas for XML documents.
Information Processing Letters, [S.l.], v.85, n.1, p.7–12, 2003.
PAPAKONSTANTINOU, Y.; VIANU, V. Incremental validation of XML documents. In: Database Theory—ICDT 2003. [S.l.]: Springer, 2002. p.47–63.
PASQUALI, F.; DUARTE, D. O Uso da Probabilidade para DescreverArvores (XML). XXIII
Simposio Brasileiro de Banco de Dados (Sessão de Posteres), [S.l.], 2008.
RUSSELL, S. J. et al. Artificial intelligence: a modern approach. [S.l.]: Prentice hall Englewood Cliffs, 1995. v.74.
SPIEGEL, M. R.; FARIAS, A. A. de. Probabilidade e estatística. [S.l.: s.n.], 1978.
VIJAYEANDRA, P. Efficient Schema Extraction from a Collection of XML Documents.
2011.
XING, G.; PARTHEPAN, V. Efficient schema extraction from a large collection of XML documents. Proceedings of the 49th Annual Southeast Regional Conference, [S.l.].

Título da Dissertação ou Trabalho - Ciência da Computação

Transcrição

Documentos relacionados

Sábios, Pensadores, Filósofos, Artistas, Investigadores

Integração de Informações em Saúde na WEB

(Microsoft Word Viewer - MANUAL_DIGPRPO_INSTALA\307\303O

Apresentação do PowerPoint

Tong Xuan Zhi Yao Fu - Medicina Chinesa Clássica

abbccddeeffggooiijjkk nnmmqqtt

clipping 01-12 - Sombras Moto Clube

O Projeto Millennium divulga a mais recente edição do relatório O

Trabalhando com XML

SCOOTER 2 TEMPS