ads:
Filipe de S´a Mesquita
Atualiza¸c˜oes Livres de Esquema em
Bancos de Dados XML
Manaus, Amazonas
05 de Maio de 2008
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
Filipe de S´a Mesquita
Atualiza¸c˜oes Livres de Esquema em
Bancos de Dados XML
Disserta¸c˜ao de mestrado apresentada ao
Curso de Mestrado em Inform´atica da Uni-
versidade Federal do Amazonas, como requi-
sito para obten¸c˜ao do t´ıtulo de Mestre em
Inform´atica
Orientador:
Professor Dr. Altigran Soares da Silva
Universidade Federal do Amazonas
Manaus, Amazonas
05 de Maio de 2008
ads:
Disserta¸c˜ao de Mestrado sob o t´ıtulo “Atualiza¸c˜oes Livres de Esquema em Bancos de
Dados XML”, defendida por Filipe de S´a Mesquita e aprovada em 05 de Maio de 2008,
em Manaus, Estado do Amazonas, pela banca examinadora constitu´ıda pelos d outores:
Prof. Dr. Altigran Soares da Silva
Orientador
Prof. Dr. Denilson Barbosa
University of Calgary
Prof. Dr. Edleno Silva Moura
Universidade Federal do Amazonas
Prof. Dr. Jo˜ao Marcos Bastos Cavalcanti
Universidade Federal do Amazonas
Dedicat´oria
Aos meus pais, a quem tenho profunda gratid˜ao e admira¸c˜ao.
Agradecimentos
Agrade¸co a Deus por me dar vida e prop´osito. Aos meus pais, Jos´e Jo˜ao e Luc´ılia,
e `as minhas irm˜as, Priscila e D´ebora, por me suportarem todos esses anos.
`
A minha
namorada e futura esposa, Camila Pican¸co, por me amar do jeito que sou.
Resumo
Este trabalho considera o problema de atualizar dados em XML no contexto de
usu´arios casuais e n˜ao especialistas trocando dados (por exemplo, usando servi¸cos de com-
partilhamentos de dados na Web) com limitado ou nenhum conhecimento sobre esquemas.
Um novo paradigma ´e introduzido para atualizar dados XML baseado em opera¸c˜oes de
atualiza¸c˜ao simples por´em poderosas. Em particular, propomos m´etodos efetivos para
traduzir dados de uma representa¸c˜ao para outra e tamb´em determinar os locais apropria-
dos para efetuar as atualiza¸c˜oes sem violar o esquema do banco de dados. Para aplicar
nossos m´etodos de forma concreta, discute-se uma linguagem de atualiza¸c˜ao intuitiva que
libera o usu´ario de conhecimentos espec´ıficos sobre esquemas e que pode ser implemen-
tada com o nosso arcabou¸co. Ainda mais, nossa proposta ´e mais simples que as linguagens
atuais para atualiza¸c˜ao de XML, e, como tal, ´e apropriada para usu´arios inexperientes.
Uma semˆantica para as opera¸c˜oes de atualiza¸c˜ao ´e discutida, assim como algoritmos efi-
cientes para implement´a-la. Para avaliar nossa abordagem, apresentamos uma an´alise
experimental com dados XML reais de v´arios dom´ınios, mostrando que nosso m´etodo ´e
eficiente, altamente efetivo e acurado.
Palavras-Chave: Atualiza¸c˜ao Livre de Esquema; XML; Gerˆencia de Dados na Web.
Abstract
We consider the problem of updating XML data in the context of casual, non-expert
users exchanging data (e.g., using Web data sharing services) with limited or no schema
knowledge. We introduce a novel paradigm for updating XML data based on simple yet
powerful update operations. In particular, we propose effective methods for translating
data from one representation into another and also for determining the appropriate lo-
cations for performing the updates without violating the schemas of the data sour ces.
In order to show a concrete application of our methods, we discuss an intuitive update
language that frees the user from specific schema knowledge and can be implemented
with our framework. Moreover, our proposal is much simpler than current XML update
languages, and, as such, it is appropriate for non-experts users. We discuss semantics for
the update operations as well as efficient algorithms for their implementation. To eva-
luate our approach, we present an exp erimental analysis with real XML data from several
domains, showing that our method is efficient, highly effective and accurate.
Keywords: Schema-Free Updates; XML; Web Data Management.
Sum´ario
Lista de Figuras
Lista de Tabelas
1 Introdu¸c˜ao p. 13
Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 13
Um Exemplo Motivador . . . . . . . . . . . . . . . . . . p. 14
Aplica¸c˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . p. 16
1.1 Desafios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 17
1.2 Contribui¸c˜oes e Organiza¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . p. 18
2 Fundamentos, Terminologia e Trabalhos Relacionados p. 20
2.1 Conceitos B´asicos de XML . . . . . . . . . . . . . . . . . . . . . . . . . p. 20
Express˜oes regulares 1-unambiguous . . . . . . . . . . . . p. 21
Autˆomato de Glushkov . . . . . . . . . . . . . . . . . . . p. 21
Validando documentos . . . . . . . . . . . . . . . . . . . p. 22
2.2 Consultas livre de esquema . . . . . . . . . . . . . . . . . . . . . . . . . p. 22
2.3 M´etricas de Similaridade . . . . . . . . . . . . . . . . . . . . . . . . . . p. 23
Distˆancia de edi¸c˜ao . . . . . . . . . . . . . . . . . . . . . p. 23
Distˆancia de edi¸c˜ao em ´arvores . . . . . . . . . . . . . . . p. 24
Similaridade de Cosseno . . . . . . . . . . . . . . . . . . p. 24
softTF-IDF . . . . . . . . . . . . . . . . . . . . . . . . . p. 24
2.4 Troca de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 24
2.5 Linguagens de Atualiza¸c˜ao de XML . . . . . . . . . . . . . . . . . . . . p. 25
3 Atualiza¸c˜ao Livre de Esquema p. 27
3.1 Considera¸c˜oes Iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 27
Atualiza¸c˜oes Livres de Esquema . . . . . . . . . . . . . . p. 29
3.2 Vis˜ao Geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 29
3.3 Ancoramento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 31
Determinando a Equivalˆencia d e N´os . . . . . . . . . . . p. 32
3.4 Linguagem de Atualiza¸c˜ao Livre de Esquema . . . . . . . . . . . . . . . p. 33
3.4.1 A Sintaxe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 33
Nota¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 34
3.4.2 Uma Semˆantica Conservadora . . . . . . . . . . . . . . . . . . . p. 34
INSERT P
1
INTO P
2
. . . . . . . . . . . . . . . . . . . . p. 34
UPDATE P
2
WITH P
1
. . . . . . . . . . . . . . . . . . . . p. 35
Uma Nota sobre semˆantica . . . . . . . . . . . . . . . . . p. 36
MERGE P
1
INTO P
2
. . . . . . . . . . . . . . . . . . . . . p. 37
DELETE P
1
FROM P
2
. . . . . . . . . . . . . . . . . . . . p. 37
3.5 Atualiza¸c˜oes Resultando em Documentos V´alidos . . . . . . . . . . . . p. 37
Determinando o Local da Atualiza¸c˜ao . . . . . . . . . . . p. 39
DTDs livres de conflito . . . . . . . . . . . . . . . . . . . p. 39
4 Adapta¸c˜ao de Dados p. 41
4.1 Mapeamentos na Adapta¸c˜ao de Dados . . . . . . . . . . . . . . . . . . p. 41
4.2 Casamento de Tip os . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 42
Similaridade de conte´udo . . . . . . . . . . . . . . . . . . p. 43
Similaridade baseada em palavras-chave . . . . . . . . . . p. 44
Similaridade baseada em valor . . . . . . . . . . . . . . . p. 45
Similaridade de r´otulo . . . . . . . . . . . . . . . . . . . p. 45
4.3 Encontrando mapeamentos . . . . . . . . . . . . . . . . . . . . . . . . . p. 47
Pares conflitantes . . . . . . . . . . . . . . . . . . . . . . p. 47
4.4 Traduzindo Instˆancias . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 49
Valores ausentes . . . . . . . . . . . . . . . . . . . . . . . p. 50
´
Arvore geradora m´ınima . . . . . . . . . . . . . . . . . . p. 50
5 Descoberta de
ˆ
Ancora p. 52
5.1 Algoritmo de Descoberta de
ˆ
Ancora . . . . . . . . . . . . . . . . . . . . p. 52
5.2 Similaridade de N´os Internos . . . . . . . . . . . . . . . . . . . . . . . . p. 54
6 Avalia¸c˜ao Experimental p. 56
6.1 Adapta¸c˜ao de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 57
Efetividade do escore combinado da adapta¸c˜ao de dados . p. 58
Impacto do tamanho do documento de entrada . . . . . . p. 59
Impacto no tamanho do banco de dados . . . . . . . . . . p. 59
Tolerˆancia a ru´ıdo . . . . . . . . . . . . . . . . . . . . . . p. 60
Avalia¸c˜ao do arcabou¸co de atualiza¸c˜ao . . . . . . . . . . p. 61
6.2 Descoberta de
ˆ
Ancora . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 62
6.3 Qualidade das Opera¸c˜oes Livre de Esquema . . . . . . . . . . . . . . . p. 63
Acuidade da Atualiza¸c˜ao . . . . . . . . . . . . . . . . . . p. 64
Qualidade das opera¸c˜oes livres de esquema . . . . . . . . p. 64
7 Conclus˜ao e Trabalhos Futuros p. 67
Referˆencias p. 69
Lista de Figuras
1 Instˆancias do banco de dados alvo antes (a) e depois (b) das opera¸c˜oes
de atualiza¸c˜ao. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 14
2 DTD para o banco de dados db.xml. . . . . . . . . . . . . . . . . . . . p. 15
3 Documentos fontes rss.xml (a) e ifilm.xml (b). . . . . . . . . . . . . p. 15
4 Inserindo dados de rss.xml (Figure 3(a)) em db.xml (Figure 1(a)) usando
XQuery. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 17
5 Exemplo de um grafo de DTD. . . . . . . . . . . . . . . . . . . . . . . p. 21
6 Autˆomato de Glushkov correspondente a regra de DTD l
i
← a, (b∗ |
(c, a+)). q
I
´e o estado inicial; q
b
, q
c
correspondem aos s´ımbolos b e c,
respectivamente; q
a
1
, q
a
2
correspondem a primeira e segunda ocorrˆencia
do s´ımbolo a. Estados finais s˜ao denotados por n´os com linhas duplas. . p. 22
7 Resultado da adapta¸c˜ao de dados sobre o documento rss.xml. . . . . . p. 28
8 Ancoramentos n˜ao amb´ıguos e completos s → t. As linhas pontilhadas
indicam o ancoramento. . . . . . . . . . . . . . . . . . . . . . . . . . . p. 29
9 Vis˜ao geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 30
10 Ancoramento amb´ıguo s → t
∗
. (Para maior clareza, omitimos o t´ıtulo
e o est´udio dos filmes). Observe que um ´unico filme em s ´e mapeado a
dois filmes em t por causa dos atores ancorados. . . . . . . . . . . . . . p. 31
11 Autˆomato de Glushkov correspondente a regra de DTD l
i
← a, (b∗ |
(c, a+)). q
I
´e o estado inicial; q
b
, q
c
correspondem aos s´ımbolos b e c,
respectivamente; q
a
1
, q
a
2
correspondem a primeira e segunda ocorrˆencia
do s´ımbolo a. Estados finais s˜ao denotados por n´os com linhas duplas. . p. 38
12 Mapeamento entre os grafos DTD de D
s
e D
t
. . . . . . . . . . . . . . . p. 42
13 Rede bayesiana para combina¸c˜ao dos componentes de similaridade . . . p. 42
14 Mapeamento entre os grafos DTD de D
s
e D
t
, com pares conflitantes a
e b. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 47
15 Procedimento para descoberta de ˆancora. . . . . . . . . . . . . . . . . . p. 53
16 Bancos de dados e documentos usados nos experimentos. . . . . . . . . p. 57
17 Acuidade de medidas de similaridades individuais entre os dom´ınios. . . p. 58
18 Impacto do tamanho do documento de entrada. . . . . . . . . . . . . . p. 59
19 Impacto do tamanho do banco de dados. . . . . . . . . . . . . . . . . . p. 60
20 Tolerˆancia a ru´ıdo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 60
21 Medida-f m´edia da descoberta de ˆancora para v´arios valores como limiar
de ancoramento λ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 63
Lista de Tabelas
1 Qualidade da adapta¸c˜ao de dados. . . . . . . . . . . . . . . . . . . . . . p. 62
2 Qualidade do ancoramento para elementos simples e complexos. . . . . p. 63
3 Acuidade das opera¸c˜oes de atualiza¸c˜ao. . . . . . . . . . . . . . . . . . . p. 65
4 Corre¸c˜ao da opera¸c˜ao de atualiza¸c˜ao quando o banco de dados deveria
permanecer inalterado. . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 65
13
1 Introdu¸c˜ao
Tecnologias presentes na World Wide Web, particularmente XML com seu crescente
repert´orio de ferramentas e aplica¸c˜oes, tˆem facilitado tremendamente a recupera¸c˜ao e o
compartilhamento de dados por usu´arios leigos ou casuais. Atualmente, h´a uma ampla
variedade de ferramentas e servi¸cos f´aceis de usar para publicar dados online , tal como
Freebase e Google Base. Outros servi¸cos bastante difundidos para publica¸c˜ao de dados
na Web s˜ao os RSS feeds, que oferecem informa¸c˜oes em formato XML. Est as facilidades
tˆem incentivado o desenvolvimento de solu¸c˜oes para facilitar a obten¸c˜ao de respostas
para consultas de usu´arios n˜ao especialistas. Uma linha de pesquisa proeminente ´e o
uso de abordagens livres de esquema, tais como consultas baseadas em palavras-chave ou
estrat´egias de relaxamento de consultas. Entretanto, ainda n˜ao foram propostas solu¸c˜oes
equivalentes para o problema de atualiza¸c˜ao de bancos de dados XML por usu´arios leigos.
Este trabalho considera atualiza¸c˜oes t´ıpicas r ealizadas por usu´arios casuais trocando
dados XML. Em uma aplica¸c˜ao onde colecionadores de filmes trocam dados, tais opera¸c˜oes
seriam: inserir filmes de um documento font e em um banco de dados alvo, atualizar o
banco de dados com dados novos e mais precisos provenientes de um documento fonte,
etc. O estado-da-arte em linguagens de atualiza¸c˜ao de XML requer conhecimento preciso
dos esquemas dos documentos envolvidos na atualiza¸c˜ao, assim como do conte ´udo dos
documentos. Por exemplo, no caso de uma inser¸c˜ao de filmes no banco de dados, ´e
necess´ario evitar inserir filmes duplicados. Al´em disso, cuidados devem ser tomados para
que o banco de dados resultante seja ainda v´alido com respeito ao seu esquema. Se
adicionarmos a isso o fato de que ´e necess´ario conhecer XQuery, que ´e a base de todas
as linguagens pr´aticas para consultas e atualiza¸c˜oes em XML, chegamos a um n´ıvel de
complexidade elevad´ıssimo para a maioria dos usu´arios, n˜ao somente os leigos.
Objetivo
Este trabalho visa permitir que usu´arios atualizem bancos de dados XML de uma forma
1 Introdu¸c˜ao 14
Thriller
@name
unknown
studio
Deja Vu
title
1996
year
genre
movie
movies
(a) Original
2006
year
Deja Vu
title
Thriller
@name
Warner
studio
Sublime
title
Horror
@name
The Departed
title
Warner
studio
genre genre
movie
studio
Touchstone Pictures
movie
movie
movies
(b) Atualizado.
Figura 1: Instˆancias do banco de dados alvo antes (a) e depois (b) das opera¸c˜oes de
atualiza¸c˜ao.
mais intuitiva e descomplicada que as solu¸c˜oes baseadas em XQuery. Em particular,
propomos um novo paradigma para atualizar documentos XML baseado em primitivas
simples que n˜ao requerem conhecimento expl´ıcito de esquemas. Nossas primitivas “livres
de esquema” exigem apenas que o usu´ario indique os dados envolvidos nas opera¸c˜oes. Por
exemplo, em uma inser¸c˜ao, o usu´ario pode simplesmente indicar um documento inteiro
para ser inserido em outro. A ´unica hip´otese adotada ´e que ambos documentos apre-
sentam dados do mesmo dom´ınio (por exemplo, filmes). Como mostramos ao logo do
trabalho, mesmo com documentos bastante pequenos, nossa abordagem ´e apta a encon-
trar as correspondˆencias entre os tipos de elementos (ex., t´ıtulo, ator) nos esquemas fonte
e alvo, permitindo portanto a reformata¸c˜ao dos dados fonte. Nossa abordagem tamb´em
´e capaz de identificar itens de dados duplicados nos documentos fonte e alvo, permitindo
assim determinar os locais apropriados para atualiza¸c˜oes.
Um Exemplo Motivador
Para ilustrar o problema de atualiza¸c˜ao livre de esquema, usaremos um banco de da-
dos XML (db.xml) como mostrado na Figura 1(a), que armazena uma cole¸c˜ao de dados
pessoais sobre cinema. Observe que os atributos s˜ao iniciados com ‘@’ e os valores textuais
s˜ao descritos abaixo dos r´otulos d os elementos ou atributos correspondentes. A Figura 2
mostra o DTD para este banco de dados. Suponha que o usu´ario queira inserir nesse
banco de dados novos lan¸camentos de filmes vindos de u m RSS feed, no qual o usu ´ario
se inscreveu (rss.xml, como mostrado na Figura 3(a)). Duas observa¸c˜oes d evem ser fei-
1 Introdu¸c˜ao 15
<!ELEMENT movies (genre*)>
<!ELEMENT genre (movie*)>
<!ATTLIST genre name ID #REQUIRED>
<!ELEMENT movie (title, studio, year?, description?,
actor*,rating*, review*)>
<!ELEMENT title (#PCDATA)>
<!ELEMENT studio (#PCDATA)>
<!ELEMENT year (#PCDATA)>
<!ELEMENT description (#PCDATA)>
<!ELEMENT rating (#PCDATA)>
<!ATTLIST rating country CDATA #REQUIRED>
<!ELEMENT review (title, paragraph*)>
<!ELEMENT paragraph (#PCDATA)>
Figura 2: DTD para o banco de dados db.xml.
The Departed
title
Thriller
genre
Horror
genre
Sublime
title
Warner
name item item
channel
(a)
PG−13
rated
Deja Vu
title
2006
released
Touchstone Pictures
company
film
(b)
Figura 3: Documentos fontes rss.xml (a) e ifilm.xml (b).
tas aqui. Primeiro, ambos os documentos XML contˆem informa¸c˜ao sobre cinema, mas
utilizam esquemas distintos; portanto, os dados de rss.xml devem ser re-estruturados de
acordo com o DTD de d b. xml. Segundo, o DTD do banco de dados requer elementos
genre ´unicos (note que o atributo @name de genre ´e um atributo ID); portanto, precisamos
inserir o primeiro filme como filho de um genre existente, enquanto precisamos criar um
novo elemento genre para o segundo filme em rss.xml, uma vez que ele pertence a um
gˆenero ainda n˜ao presente no banco de dados.
A ´unica maneira de executar esta tarefa com a infra-estrutura atual de atualiza¸c˜ao
de XML seria escrever comandos de atualiza¸c˜ao sobre db.xml que inclu´ıssem tamb´em
comandos de consulta sobre o documento fonte rss.xml. Usando a linguagem XQuery
estendida com recursos de atualiza¸c˜ao (ROBI E; FLORESCU; CHAMBERLIN, 2006), os co-
mandos apresentadas na Figura 4 podem ser usados para esta opera¸c˜ao de atualiza¸c˜ao.
A instˆancia resultante da execu¸c˜ao desses comandos ´e apresentada na Figura 1(b), na
qual as arestas dos elementos inseridos est˜ao destacadas por setas pontilhadas para maior
clareza.
Neste trabalho, p ropomos um novo paradigma no qual tais inser¸c˜oes podem ser indi-
cadas por constru¸c˜oes mais simples e de mais alto n´ıvel. Para aplicar nossos m´etodos de
1 Introdu¸c˜ao 16
forma concreta (em uma aplica¸c˜ao da Web, por exemplo), propomos uma linguagem de
atualiza¸c˜ao minimalista (Se¸c˜ao 3.4); entretanto, a essˆencia da nossa abordagem ´e que o
usu´ario deve apenas ser obrigado a indicar os n´os envolvidos na atualiza¸c˜ao. Por exemplo,
a atualiza¸c˜ao descrita na Figura 4 poderia ser expressa na nossa linguagem como segue:
INSERT doc(’rss.xml’) INTO doc(’db.xml’)
Onde, o sistema deve ser respons´avel por inserir os dados de rss.xml apropriadamente
em db.xml.
Considere agora a atualiza¸c˜ao do banco de dados com informa¸c˜oes mais precisas vindo
de uma fonte online. Por exemplo, o documento ifilm.xml (Figure 3(b)) cont´em o ano
correto de lan¸camento e nome do est´udio de um filme no banco de dados. Uma vez mais,
com a infra-estrutura atual d e atualiza¸c˜ao de XML ´e necess´ario localizar manualmente
os elementos a serem atualizados, e consultar as por¸c˜oes apropriadas do documento de
entrada para efetuar esta altera¸c˜ao. Propomos ent˜ao uma abordagem mais intuitiva na
qual o usu´ario submeteria um comando tal como:
UPDATE doc(’db.xml’) WITH doc(’ifilm.xml’)
Neste caso, nosso arcabou¸co seria respons´avel por fazer as corre¸c˜oes que resultariam no
banco de dados final, como mostrado na Figura 1(b).
Aplica¸c˜oes
Nossa principal motiva¸c˜ao para este trabalho ´e a troca de dados XML por usu´arios ca-
suais ou leigos, proveniente do uso crescente de XML em ferramentas de computa¸c˜ao
pessoal (BRAUER et al., 2005; MICROSOFT CORPORATION, 2006) e a prolifera¸c˜ao de sites
e comu nidades de compartilhamento de dados baseados na Web. Exemplos desse tipo
de site s˜ao Freebase
1
e GoogleBase
2
, os quais oferecem um ambiente colaborativo, onde
os usu´arios podem inserir novos dados ou editar os dados existentes, al´em de realizar
consultas sobre a base de dados. Usu´arios t´ıpicos desses sistemas n˜ao s˜ao especialistas
em tecnologias de bancos de dados, e, como tal, n˜ao s˜ao aptos a usar ferramentas e lin-
guagens sofisticadas como XQuery e seus recursos de atualiza¸c˜ao. Nosso trabalho tem
aplica¸c˜ao tamb´em em gerˆencia de dados pessoais, um desafio permanente em gerˆencia
1
http://www.freebase.com/ .
2
http://base.google.com .
1.1 Desafios 17
for $film in doc(‘rss.xml’)//film
let $genre := doc(‘db.xml’)//genre[@name=$film/genre]
let $movie := $genre/movie[title=$film/title]
return
if(exists($genre)) then
if(exists($movie)) then ()
else do insert
<movie>
<title>{string($item/title)}</title>
<studio>{string($item/../name)}</studio>
</movie>
into $genre
else do insert
<genre name={$film/genre}>
<movie>
<title>{string($item/title)}</title>
<studio>{string($item/../name)}</studio>
</movie>
</genre>
into doc(‘db.xml’)/movies
Figura 4: Inserindo dados de rss.xml (Figure 3(a)) em db.xml (Figure 1(a)) usando
XQuery.
de d ados devido a complexidade e diversidade dos dados envolvidos (ABITEBOUL et al.,
2005). Abordagens recentes advogam o uso de XML como formato unificador neste tipo
de aplica¸c˜ao (DITTRICH; SALLES, 2006), fazendo os m´etodos que desenvolvemos aqui di-
retamente aplic´aveis. Finalmente, nosso trabalho ´e aplic´avel no contexto tradicional de
troca e integra¸c˜ao de dados. Isto deve-se ao uso de t´ecnicas de casamento de esquema, jun-
tamente com restri¸c˜oes semˆanticas, para produzir automaticamente mapeamentos entre
esquemas, os quais podem ser usados diretamente, ou como ponto de partida para os
usu´arios definirem os mapeamentos. Por outro lado, ´e p oss´ıvel acoplar o nosso meca-
nismo de atualiza¸c˜ao dentro de uma ferramenta de troca de dados que use outros tipos
de processos para descoberta de mapeamentos. Em todos os casos, nossos m´etodos de-
mandam baixo investimento de configura¸c˜ao e esfor¸co m´ınimo dos usu´arios, tornando-se
uma op¸c˜ao bastante atrativa.
1.1 Desafios
Mesmo considerando que um paradigma de atualiza¸c˜ao livre de esquema, no qual o
usu´ario indica qual opera¸c˜ao efetuar e indica os n´os envolvidos na opera¸c˜ao, ´e claramente
prefer´ıvel `aquele baseado em atualiza¸c˜ao atrav´es de comandos em XQuery (Figura 4), h´a
1.2 Contribui¸c˜oes e Organiza¸c˜ao 18
muitos desafios para prover tal capacidade. Primeiro, como discutido acima, ´e necess´ario
identificar os elementos do documento fonte que ser˜ao realmente usados na atualiza¸c˜ao.
No exemplo acima, tivemos que tratar os dois filmes vindos de rss.xml diferentemente,
para evitar que a opera¸c˜ao resultasse num banco de dados inv´alido. Ainda mais, mesmo
que o DTD permitisse gˆeneros (elementos genre) duplicados, ´e necess´ario tomar cuidado
para n˜ao intro duzir redund ˆancia de dados desnecess´aria, que po de gerar confus˜ao.
Al´em disso, precisamos formatar os dados de entrada de acordo com o DTD do banco
de dados.
´
E necess´ario ainda tomar cuidado para n˜ao produzir atualiza¸c˜oes que resul-
tam em bancos de dados XML inv´alidos. Al´em de reformatar corretamente os dados
de entrada, isto requer determinar um local para atualiza¸c˜ao que n˜ao viole o DTD do
banco de dados. Em geral, isto requer revalidar o banco de dados depois da atualiza¸c˜ao,
e o problema pode se tornar ainda mais complicado quando v´arios locais de inser¸c˜ao s˜ao
permitidos.
Tradicionalmente, todos esses asp ectos s˜ao tratados manualmente por um p rograma-
dor de XQuery, o qual precisa tamb´em conhecer os detalhes de ambos esquemas envol-
vidos. O desafio que enfrentamos neste trabalho ´e lidar com essas dificuldades de forma
autom´atica, e no final das contas permitir que usu´arios inexperientes realizem atualiza¸c˜oes
sofisticadas como a do nosso exemplo usando um comando simples e de alto n´ıvel, sem
que eles precisem conhecer uma sintaxe de linguagem ou detalhes de esquema. Este pa-
radigma de alto n´ıvel poderia tamb´em ser materializado via interfaces gr´aficas nas quais
uma interface mais intuitiva po deria ser usada (por exemplo, “arrastando” o documento
rss.xml e o “soltando” em db.xml para indicar a opera¸c˜ao de inser¸c˜ao).
1.2 Contribui¸c˜oes e Organiza¸c˜ao
At´e onde sabemos, nenhum outro trabalho anterior tratou o problema de produzir
automaticamente atualiza¸c˜oes em documentos XML. Nossas contribui¸c˜oes s˜ao:
• Um novo paradigma para atualiza¸c˜ao de XML o qual ´e baseado em opera¸c˜oes in-
tuitivas e na habilidade do usu´ario de indicar os n´os envolvidos na atualiza¸c˜ao.
• Propomos uma linguagem simples de atualiza¸c˜ao e uma semˆantica para esta lingua-
gem que evita a introd u¸c˜ao de redund ˆancia no banco de dados.
• Nosso arcabou¸co ´e composto pelo processo de adapta¸c˜ao de dados e pelo algoritmo
de descoberta de ˆancora. O processo d e adapta¸c˜ao de dados traduz dados XML de
1.2 Contribui¸c˜oes e Organiza¸c˜ao 19
uma representa¸c˜ao para outra, reestruturando e renomeando os elementos, de forma
que sempre ´e gerado conte´u do v´alido mesmo quando lidamos com valores ausentes.
• Nosso algoritmo de descoberta de ˆancora determina o local preciso das atualiza¸c˜oes,
identificando n´os equivalentes nos documentos XML fonte e alvo.
Os fundamentos te´oricos, a terminologia utilizada neste trabalho e alguns trabalhos
relacionados s˜ao discutidos no pr´oximo cap´ıtulo. Nosso arcabou¸co para atualiza¸c˜ao livre
de esquema ´e apresentado no Cap´ıtulo 3. Uma linguagem simples de atualiza¸c˜ao ´e apre-
sentada para aplicar nossos m´etodos de forma concreta na Se¸c˜ao 3.4. O processo de
adapta¸c˜ao de dados ´e apresentado no cap´ıtulo Cap´ıtulo 4, e o algoritmo de descoberta
de ˆancora no Cap´ıtulo 5. A valida¸c˜ao experimental dos nossos m´etodos ´e discutida no
Cap´ıtulo 6, e a conclus˜ao do trabalho ´e apresentada no Cap´ıtulo 7.
20
2 Fundamentos, Terminologia e
Trabalhos Relacionados
Este cap´ıtulo introduz alguns conceitos b´asicos sobre XML e m´etricas de similari-
dade, necess´arios para entendimento do nosso trabalho. S˜ao apresentados tamb´em v´arios
trabalhos relacionados com a pesquisa realizada.
2.1 Conceitos B´asicos de XML
A linguagem de marca¸c˜ao extens´ıvel (ou eXtended Markup Language – XML) (BRAY et
al., 2006) tem se estabelecido como o principal formato para compartilhamento de dados na
Web. Os documentos XML s˜ao auto-descritivos e u sam marca¸c˜oes textuais para descrever
dados, sendo ele mentos e atributos as principais marca¸c˜oes. Por exemplo, em <rati ng
country=‘‘US’’> PG-13 </rating> temos um elemento com r´otulo rating e cont´eudo
“PG-13”, assim como um atributo com r´otulo country e valor “US”. Um atributo pode
ser um identificador (ID) do elemento, e outros elementos podem ser apontadores ou
referˆencias a outros elementos (IDREF, IDREFS). Documentos XML s˜ao modelados como
´arvores (ou grafos, se considerarmos atributos IDREF), onde os n´os s˜ao elementos e
atributos, e as arestas indicam como os elementos/atributos s˜ao aninhados. As rela¸c˜oes
pai-filho e ancestral-descente entre os n´os se aplicam aos documentos XML, assim como
em ´arvores. Um exemplo de ´arvore XML ´e apresentado na Figura 1(a).
A corre¸c˜ao de um documento XML ´e medida de duas formas diferentes. Um do-
cumento ´e bem-formado se ele est´a em conformidade com todas as regras de sintaxe de
XML (BRAY et al., 2006). Por exemplo, se ele apresenta apenas um elemento raiz. Um
documento mal-formado n˜ao ´e considerado um documento XML. Por outro lado, um
documento XML bem-formado ´e tamb´em v´alido se ele est´a em conformidade com sua
defini¸c˜ao de esquema, expressa por um DTD (Document Type Definition ), por exemplo.
DTD ´e uma gram´atica que define cada tipo de elemento permitido (e seu conte´udo) num
2.1 Conceitos B´asicos de XML 21
Figura 5: Exemplo de um grafo de DTD.
documento atrav´es de express˜oes regulares. Elementos s˜ao declarados num DTD por
regras da forma <!ELEMENT l c>, conhecidas como modelos de conte´udo, as quais espe-
cificam que: elementos v´alidos do tipo l tˆem conte´udo de acordo com c, onde c ´e uma
express˜ao regular que gera conte´udo v´alido. O DTD do banco de dados da Figura 1(a)
´e mostrado na Figura 2. Um DTD pode ser representado tamb´em como um grafo, onde
os n´os s˜ao elementos, atributos e operadores (ex., ?, +, *). Na Figura 5 ´e mostrado um
exemplo de grafo de DTD.
Express˜oes regulares 1-unambiguous
A especifica¸c˜ao de DTDs se restringem a express˜oes regulares 1-ambiguous para definir
modelos de conte´udo. Informalmente, uma express˜ao regular ´e 1-ambiguous se ´e poss´ıvel
casar unicamente a ocorrˆencia de um s´ımbolo na express˜ao regular a um elemento XML
na seq¨uˆencia de entrada sem verificar qualquer outro elemento. Em outras palavras,
express˜oes regulares 1-unambiguous requerem a verifica¸c˜ao de apenas um s´ımbolo por
elemento XML de entrada.
Autˆomato de Glushkov
Uma forma de representar as express˜oes regulares de um DTD ´e atrav´es do autˆomato
finito proposto por Glushkov (GLUSHKOV, 1961). O conte´udo de um elemento ´e v´alido
se ele ´e aceito por um autˆomato de Glushkov correspondente ao modelo de conte´udo do
elemento. Em um autˆomato de Glushkov de uma express˜ao regular E, os estados corres-
pondem `as posi¸c˜oes (s´ımbolos) de E e transi¸c˜oes conectam aquelas posi¸c˜oes que podem ser
consecutivas numa seq¨uˆencia de elementos v´alida. Um exemplo de autˆomato de Glushkov
´e ilustrado na Figura 6.
2.2 Consultas livre de esquema 22
q
I
q
a
1
q
b
q
c
q
a
2
a
b
c
a
b
a
Figura 6: Autˆomato de Glushkov correspondente a regra de DTD l
i
← a, (b∗ | (c, a+)).
q
I
´e o estado inicial; q
b
, q
c
correspondem aos s´ımbolos b e c, respectivamente; q
a
1
, q
a
2
correspondem a primeira e segunda ocorrˆencia do s´ımbolo a. Estados finais s˜ao denotados
por n´os com linhas duplas.
Validando documentos
Um problema relacionado ao nosso trabalho ´e verificar se um documento ´e v´alido com
rela¸c˜ao a um DTD. Em termos gerais, ´e preciso validar o conte´udo de cada elemento
no documento atrav´es do autˆomato de Glushkov correspondente. Entretanto, como exigi-
mos que um documento XML continue v´alido mesmo ap´os uma atualiza¸c˜ao, podemos usar
t´ecnicas de atualiza¸c˜ao incrementais (BARBOSA et al., 2004), que verificam se as altera¸c˜oes
num do cumento v´alido comprometem sua validade ou n˜ao.
2.2 Consultas livre de es quema
Numerosos m´etodos tˆem sido desenvolvidos para permitir mecanismos flex´ıveis de
consulta sobre dados XML (COHEN et al., 2003; GUO et al., 2003; LI; YU; JAGADISH, 2004),
como tamb´em bancos de dados relacionais, por exemplo, (AGRAWAL; CHAUDHURI; DAS,
2002; MESQUITA et al., 2007). Entretanto, at´e onde sabemos, nosso m´etodo ´e o primeiro
a tratar o problema mais desafiador de atualiza¸c˜oes livres de esquema.
A motiva¸c˜ao para alternativas “livres de esquema” para consultas em XML ´e aliviar
a carga de conhecer o esquema dos documentos em detalhe. Existem dois paradigmas
principais: (1) prover m´etodos de pesquisa semˆantica baseados em Recupera¸c˜ao de In-
forma¸c˜ao, no qual fragmentos de XML s˜ao retornados para responder uma consulta livre
de esquema (COHEN et al., 2003; GUO et al., 2003); e (2) estender linguagens de consulta
estruturadas com predicados para pesquisa de n´os na ´arvore XML (LI; YU; JAGADISH,
2004).
No primeiro caso, o problema geral ´e, dado um conjunto de palavras-chave como
consulta, deseja-se recuperar do banco de dados XML as sub-´arvores que contenham
essas palavras-chaves em seu conte´udo textual. Muitos trabalhos vˆem propondo dife-
2.3 M´etricas de Similaridade 23
rentes maneiras de retornar sub-´arvores significantes (meaningful) como resposta. Uma
das propostas mais difundidas ´e retornar o ancestral comum mais baixo (Lower Common
Ancestor or LCA) dos n´os que contenham as palavras-chave da consulta (por exemplo,
Meet (SCHMIDT; KERSTEN; W INDHOUWER, 2001)). No segundo caso, as t´ecn icas para en-
contrar sub-´arvores significantes s˜ao incorporados para flexibilizar a defini¸c˜ao da estrutura
a ser consultada.
Mais pr´oximas ao nosso trabalho s˜ao as t´ecnicas de estrutura¸c˜ao de consulta para
bancos de dados relacionais (MESQUITA et al., 2007; AGRAWAL; CHAUDHURI; DAS, 2002),
onde, dado uma consulta baseada em palavras-chave, o sistema gera consultas estrutura-
das em SQL (de acordo com uma semˆantica) que equivalem `as consultas originais como
intencionadas pelo usu´ario. Este processo envolve identificar para cada palavra-chave o
atributo alvo pretendido pelo usu´ario. Da mesma forma, nossos m´etodos precisam iden-
tificar qual tipo de elemento onde cada valor de entrada melhor “se adapta” no banco
de dados. Al´em disso, tamb´em definimos uma semˆantica para poss´ıveis opera¸c˜oes livres
de esquema, gerando ao final primitivas de atualiza¸c˜ao estruturadas, que podem ser fa-
cilmente traduzidas para linguagens de atualiza¸c˜ao, como XQuery.
2.3 M´etricas de Similaridade
Muitas abordagens livres de esquema para consultas s˜ao, na verdade, buscas por
similaridade, onde dado u ma consulta fornecida pelo usu´ario, queremos retornar os objetos
mais parecidos com a consulta num banco de dados. O cerne desse processo s˜ao as m´etricas
de similaridade utilizadas. Nesta se¸c˜ao discutiremos algumas delas, em particular as que
usamos neste trabalho. H´a tamb´em outras aplica¸c˜oes para as m´etricas de similaridade,
como em limpeza de dados (GALHARDAS et al., 2001; GRAVANO et al., 2001) e detec¸c˜ao de
duplicatas (WEIS; NAUMANN, 2005).
Distˆancia de edi¸c˜ao
A distˆancia de edi¸c˜ao ou distˆancia Levenshtein de duas seq¨uˆencias de caracteres ´e dada
pelo n´umero de edi¸c˜oes necess´arias para converter uma seq¨uˆencia em outra. As opera¸c˜oes
de edi¸c˜ao utilizadas s˜ao, geralmente: inser¸c˜ao, remo¸c˜ao ou substitui¸c˜ao de um caracter.
Em algumas aplica¸c˜oes o n´umero de edi¸c˜oes ´e normalizado pelo tamanho da seq¨uˆencia
maior, resultando num valor em [0, 1]. A distˆancia de edi¸c˜ao normalizada serve comumente
como suporte de outras m´etricas para o casamento aproximado de valores.
2.4 Troca de dados 24
Distˆancia de edi¸c˜ao em ´arvores
A id´eia de distˆancia de edi¸c˜ao tamb´em pode ser adaptada para ´arvores, onde quere-
mos o n´umero de edi¸c˜oes para converter uma ´arvore em outra. As opera¸c˜oes de edi¸c˜ao
geralmente s˜ao inserir, remover ou substituir n´os de uma ´arvore. Um problema relacio-
nado ´e o de determinar quando duas ´arvores XML s˜ao equivalentes, embora elas possam
ter estruturas diferentes e usar diferentes r´otulos de elementos (GUHA et al., 2002; WEIS;
NAUMANN, 2005).
Similaridade de Cosseno
A similaridade de cosseno entre dois textos (ou documentos) baseia-se no modelo espa¸co-
vetorial (BAEZA-YATES; RIBEIRO-NETO, 1999) utilizado freq¨uentemente em Recupera¸c˜ao
de Informa¸c˜ao, onde os documentos s˜ao modelados como vetores. Cada dimens˜ao corres-
ponde a um termo em separado. Se um termo ocorre num documento, o valor da dimens˜ao
correspondente no vetor ser´a maior que zero. Estes valores podem ser calculados por di-
versos esquemas de pondera¸c˜ao, sendo TF-IDF um dos mais difundidos (BAEZA-YATES;
RIBEIRO-NETO, 1999).
softTF-IDF
Uma limita¸c˜ao da similaridade de cosseno ´e que ela considera apenas o casamento exato de
palavras. Para contornar este problema, a varia¸c˜ao denominada softTF-IDF (COHEN; RA-
VIKUMAR; FIENBERG, 2003) permite que palavras similares sejam tamb´em consideradas.
Para isto, uma segunda m´et rica ´e usada entre as palavras dos documentos analisados. Se
duas palavras s˜ao suficientemente similares, considera-se que suas respectivas dimens˜oes
s˜ao as mesmas, ou seja, formam uma ´unica dimens˜ao.
2.4 Troca de dados
Outro problema que deve ser abordado em nosso contexto ´e traduzir dados forma-
tados de acordo com o DTD fonte em dados formatados de acordo com o DTD alvo.
Este problema ´e comumente chamado de Troca de Dados, que em sua defini¸c˜ao mais
geral, consiste em, receber dados estruturados conforme um esquema fonte, restrutur´a-
los e traduzi-los para um esquema alvo. Fagin et al. (FAGIN et al., 2003) estabeleceram
2.5 Linguagens de Atualiza¸c˜ao de XML 25
as funda¸c˜oes deste problema; em particular, eles estudaram d iferentes semˆanticas para
troca de dados e suas complexidades. Fuxman et al. (FUXMAN et al., 2006) estudaram o
problema no contexto de dois pares compartilhando dados; eles consideram o caso onde
os pares especificam quais dados eles est˜ao desejando receber de outros pares. Arenas e
Libkin (ARENAS; LIBKIN, 2005) consideram o problema de troca de dados XML onde os
esquemas fontes e alvo s˜ao DTDs. Estes trabalhos estabeleceram as bases do problema
de troca de dados, focando essencialmente em resultados de complexidade.
Nossa problema ´e encontrar casamentos entre os tipos de dois DTDs, a partir do
qual n´os podemos definir um mapeamento completo (ou seja, uma maneira de traduzir
as instˆancias de dados reais). Casamento de esquema tem sido extensivamente estudado
recentemente; Rahm e Bernstein apresentam um levantamento de v´arias t´ecnicas para
este problema (RAHM; BERNSTEIN, 2001). V´arios m´etodos (por exemplo, Similarity Floo-
ding (MELNIK; GARCIA-MOLINA; RAHM, 2002)) exploram informa¸c˜ao de esquema, tal como
r´otulos elementos de esquema, para derivar mapeamentos. O utros m´etodos exploram os
valores de dados para derivar associa¸c˜oes entre os elementos de esquema (COHEN; HIRSH,
1998). Nosso m´etodo de casamento autom´atico combina tanto similaridade de esquemas
como de valores para derivar tais mapeamentos. Como discutido ao longo do texto, nosso
m´etodo atinge alta acuidade em dados reais de diferentes Web sites.
H´a tamb´em trabalhos que tratam o problema de traduzir dados uma vez que os
esquemas est˜ao casados (veja, por exemplo, (POPA et al., 2002) e as referˆencias nele). O
estado-da-arte ´e definir mapeamentos com a ajuda de sistemas que necessitam tipicamente
de consider´avel investimento de configura¸c˜ao e interven¸c˜ao do usu´ario. Nossa solu¸c˜ao, por
outro lado, ´e completamente n˜ao supervisionada, e portanto adequada para usu´arios n˜ao
experientes e casuais trocadas dados na Web. Nosso algoritmo de tradu¸c˜ao de dados ´e
baseado nas t´ecnicas path outer union e hash-based tagging de (SHANMUGASUNDARAM et
al., 2001).
2.5 Linguagens de Atualiza¸c˜ao de XML
O estado-da-arte em linguagens de atualiza¸c˜ao de XML s˜ao linguagens estruturadas,
como XQuery (ROBIE; FLORESCU; CHAMBERLIN, 2006) e XUpdate(LAUX; MARTIN, 2000),
cuja semˆantica ´e precisa e bem-definida. Tais linguagens s˜ao eficientes e extremamente
adequadas para o desenvolvimento de aplica¸c˜oes cr´ıticas, que exigem 100% de corre¸c˜ao nas
opera¸c˜oes de atualiza¸c˜ao. Entretanto, como discutido anteriormente, os usu´arios precisam
2.5 Linguagens de Atualiza¸c˜ao de XML 26
conhecer os esquemas envolvidos na opera¸c˜ao e a sintaxe dessas linguagens para poderem
utiliz´a-las.
A linguagem proposta neste trabalho n˜ao visa substituir o paradigma atual de lingua-
gens estruturadas, mas permitir que usu´arios consigam produ zir, de uma forma simples e
intuitiva, opera¸c˜oes complexas em um cen´ario onde poucos erros s˜ao aceit´aveis. At´e onde
sabemos, este ´e o primeiro trabalho a tratar o o problema de produzir automaticamente
atualiza¸c˜oes em documentos XML.
27
3 Atualiza¸c˜ao Livre de Esquema
Como ilustrado no Cap´ıtulo 1, escrever programas de atualiza¸c˜ao em linguagens como
XQuery ´e uma tarefa suscet´ıvel a erros que requer conhecimento preciso da estrutura tanto
do documento fonte quanto do banco de dados alvo. Em um contexto livre de esquema, os
usu´arios devem poder especificar atualiza¸c˜oes de uma forma mais intuitiva. Para este fim,
propomos uma linguagem de atualiza¸c˜ao mu ito mais simples na qual os usu´arios especifi-
cam a opera¸c˜ao e o conte´udo que est´a envolvido na opera¸c˜ao de atualiza¸c˜ao. O problema
da atualiza¸c˜ao livre de esquema consiste em traduzir tais express˜oes em programas de
atualiza¸c˜ao que capturam tanto quanto poss´ıvel a “inten¸c˜ao” da atualiza¸c˜ao dada pelo
usu´ario.
3.1 Considera¸c˜oes Iniciais
Documentos XML s˜ao modelados como ´arvores ordenadas e rotuladas, onde elementos
e atributos s˜ao n´os e tags s˜ao r´otulos. Por simplicidade, n˜ao h´a distin¸c˜ao entre atributos
e elementos textuais em nossa discuss˜ao. O tipo de um elemento ´e dado pelo seu r´otulo
na nota¸c˜ao de DTD. Dessa forma, dois elementos s˜ao do mesmo tipo se apresentam o
mesmo r´otulo. Observe que, diferente do conceito apresentado aqui, o tipo de elemento
no contexto de XML Schema ´e mais pr´oximo ao tipo de dado: inteiro, real, textual.
Antes de definir o problema de atualiza¸c˜ao livre de esquema, discutimos atualiza¸c˜oes de
documentos XML em geral. Quatro primitivas de atualiza¸c˜ao s˜ao consideradas: anexar
um n´o (ou seja, um elemento XML ou atributo) como ´ultimo filho de um outro elemento
no banco de dados (APP), inserir um novo n´o antes de outro no banco de dados (INSB),
substituir um n´o no banco de dados por um novo (REP), e remover um n´o do banco de
dados (DEL). A partir destas primitivas, define-se:
Defini¸c˜ao 1 Uma opera¸c˜ao individual de atualiza¸c˜ao estruturada, denotada por uma tri-
pla u = (op, l, c), onde op ´e a prim iti va de atualiza¸c˜ao, l ´e a express˜ao de caminho
3.1 Considera¸c˜oes Iniciais 28
Thriller
@name
Warner
studio
The Departed
title
genre
movie
(a)
Horror
@name
Warner
studio
Sublime
title
movie
genre
(b)
Figura 7: Resultado da adapta¸c˜ao de dados sobre o documento rss.xml.
indicando o local da atualiza¸c˜ao, e c ´e o conte´udo a ser inserido ou modificado (c ´e vazio
para remo¸c˜oes).
Observe que o local da atualiza¸c˜ao pode ser expresso de muitas formas diferentes.
Em nossos exemplos s˜ao usadas express˜oes de caminho que retornam um n´o apenas;
entretanto, poderiam ser diretamente usados identificadores internos em implementa¸c˜oes
pr´aticas.
Tipicamente, programas de atualiza¸c˜ao s˜ao definidos pelo que chamamos de atua-
liza¸c˜oes estruturadas compostas: seq¨uˆen cias de atualiza¸c˜oes individuais u
1
, . . . , u
k
, agru-
padas em uma ´unica transa¸c˜ao atˆomica. Assumimos que um programa de atualiza¸c˜ao
u
1
, . . . , u
k
´e completado integralmente (ou seja, cada op era¸c˜ao ´e realizada) ou ´e abor-
tado (ou seja, o documento ´e deixado inalterado). Al´em disso, assumimos que cada u
i
´e
aplicado ao documento original (ou seja, os resultados d e opera¸c˜oes individuais n˜ao s˜ao
vis´ıveis a outras opera¸c˜oes na mesma transa¸c˜ao).
Exemplo 1 A seguinte opera¸c˜ao de atualiza¸c˜ao composta produz o mesmo efeito que as
express˜oes de atualiza¸c˜ao na Figura 4:
u
1
= (APP,
doc(‘db.xml’)//genre[@name=“Thriller”],
<movie><title>The Departed</ti tle >
<studio>Warner</studio></movie>)
u
2
= (APP,
doc(‘db.xml’)//movies,
<genre @name=“Horror”>
<movie><title>The Departed</ti tle >
<studio>Warner</studio></movie>
</genre>)
3.2 Vis˜ao Geral 29
(a) Ancoramento do filme na Figura 7(a). (b) Ancoramento do filme da Figura 3(b).
Figura 8: Ancorament os n˜ao amb´ıguos e completos s → t. As linhas pontilhadas indicam
o ancoramento.
Atualiza¸c˜oes Livres de Esquema
Uma atualiza¸c˜ao livre de esquema ´e denotada pela tripla sf = (op, s, t), onde op ´e uma
opera¸c˜ao, s ´e um documento fonte e t ´e o banco de dados alvo. Para maior clareza, o
documento fonte ´e simplesmente referenciado como documento, e o banco de dados alvo
como banco de dados. Assumindo que s e t s˜ao v´alidos com respeito aos DTDs D
s
e D
t
,
que podem ou n˜ao ser os mesmos, esperamos que o banco de dados resultante da opera¸c˜ao
tamb´em seja v´alido com respeito a D
t
.
Este trabalho considera o problema de rescrever uma atualiza¸c˜ao livre de esquema
sf = (op, s, t) em uma atualiza¸c˜ao estruturada composta equivalente (de acordo com uma
dada semˆantica).
3.2 Vis˜ao Geral
Nossa abordagem funciona como ilustrado na Figura 9. Primeiro, os dados no do-
cumento fonte s˜ao reorganizados para ficar de acordo o DTD do banco de dados alvo
(caso j´a n˜ao estejam). Este processo, chamado de adapta¸c˜ao de dados(Data Fitting),
´e descrito no Cap´ıtulo 4. Em resumo, a adapta¸c˜ao de dados extrai do documento um
conjunto de elementos XML reorganizados de acordo com o DTD do banco de dados.
Como veremos, cada um desses elementos define uma opera¸c˜ao de atualiza¸c˜ao separada.
Por exemplo, aplicando a opera¸c˜ao de adapta¸c˜ao de dados no documento da Figura 3(a),
os dois fragmentos mostrados na Figura 7 seriam obtidos como resultado.
3.2 Vis˜ao Geral 30
Figura 9: Vis˜ao geral
O segundo passo ´e determinar os locais das atualiza¸c˜oes. Isto ´e realizado tentando-se
ancorar cada sub-´arvore resultante do primeiro passo ao banco de dados. Para ilustrar
essa id´eia, a Figura 8(a) mostra o ancoramento do filme da Figura 7(a) no banco de dados
do nosso exemplo. Observe que o n´o do elemento genre e seu atributo @name tem n´os
correspondentes ´unicos no banco de dados. Portanto, dizemos que a ´arvore formada por
eles ancora de forma n˜ao amb´ıgua no banco de dados.
A descoberta de ˆancora ´e crucial em nosso m´etodo e uma das principais contribui¸c˜oes
deste trabalho. De fato, a semˆantica das atualiza¸c˜oes em nosso arcabou¸co ´e definida
baseando-se nas sub-´arvores ancoradas (mais detalhes seguem). Para inser¸c˜oes, cada n´o
n˜ao ancorado i que ´e filho de um n´o ancorado j ´e inserido como filho do n´o ao qual j
ancora no banco de dados. No exemplo acima (Figura 8(a)) isto corresponde a inserir
o novo filme (movie) como filho do n´o genre. No caso das atualiza¸c˜oes, cada n´o n˜ao
ancorado no banco de dados ´e substitu´ıdo p or um n´o equivalente no documento. Por
exemplo, no caso da Figura 8(b), isto corresponderia a substituir os n´os studio e year no
banco de dados. Finalmente, para remo¸c˜oes, os n´os ancorados (e seus descendentes) s˜ao
simplesmente removidos.
´
E poss´ıvel que mais de uma sub-´arvore no documento de entrada ancore no banco de
dados. Por exemplo, se o banco de dados tivesse algum outro filme do est´udio “Warner”,
seria poss´ıvel que o n´o studio no documento fonte na Figura 8(a) ancorasse no banco de
3.3 Ancoramento 31
Figura 10: Ancoramento amb´ıguo s → t
∗
. (Para maior clareza, omitimos o t´ıtulo e o
est´udio dos filmes). Observe que um ´unico filme em s ´e mapeado a dois filmes em t por
causa dos atores ancorados.
dados. Isto poderia resultar em diferentes interpreta¸c˜oes para o que deveria ser atua-
lizado. A semˆantica que propomos mais `a frente considera apenas o ancoramento que
envolve a raiz dos elementos XML produzidos pela adapta¸c˜ao de dados. Ou seja, n´os
“desancoramos” qualquer par de n´os cujos pais n˜ao est˜ao ancorados um ao outro.
O pr´oximo passo ´e verificar se a opera¸c˜ao de atualiza¸c˜ao resulta numa instˆancia v´alida
do banco de dados, como discutido na Se¸c˜ao 3.5. O ´ultimo passo ´e produzir as atualiza¸c˜oes
reais que ser˜ao efetuadas no banco de dados. Tais atualiza¸c˜oes s˜ao representadas usando
a nota¸c˜ao simples de atualiza¸c˜oes estruturadas descrita acima, de tal forma que ´e poss´ıvel
execut´a-las num sistema de armazenamento de XML ou traduzi-las para a nota¸c˜ao de
uma linguagem de atualiza¸c˜ao, como XQuery.
3.3 Ancoramento
Conforme descrito acima, o local da atualiza¸c˜ao ´e determinado encontrando-se um
conjunto de correspondˆencias entre os elementos no documento fonte e os elementos no
banco de dados, o qual n´os chamamos de ancoramento. Mais precisamente, um ancora-
mento entre duas ´arvores XML s e t ´e uma rela¸c˜ao s → t
∗
que associa para cada n´o s
i
∈ s
todos os n´os t
j
∈ t tal que s
i
e t
j
s˜ao equivalentes. O conceito de equivalˆencia depende do
tipo de n´o (folha ou interno), como discutido abaixo. Duas defini¸c˜oes importantes s˜ao,
como segue:
3.3 Ancoramento 32
Defini¸c˜ao 2 Um ancoramento A : s → t
∗
´e n˜ao amb´ıguo se ele ´e na verdade uma fun¸c˜ao
s → t e se, para cada s
i
, s
j
em s, se s
i
e s
j
s˜ao irm˜aos ent˜ao A(s
i
) e A(s
j
) s˜ao tamb´em
irm˜aos.
Defini¸c˜ao 3 Um ancoramento A : s → t
∗
´e completo se para cada s
i
∈ s, quando A(s
i
)
´e definido ent˜ao A(s
j
) tamb´em ´e definido, para cada s
j
que ´e um ancestral de s
i
.
A Figura 8 mostra dois exemplos de ancoramentos n˜ao amb´ıguos e completos. Para
melhor ilustrar estes conceitos, considere o ancoramento da Figura 10. Tal ancoramento
´e amb´ıguo, pois os atores “Joe” e “Bob” pertencem ao mesmo filme em s mas s˜ao mapea-
dos a filmes diferentes em t (alternativamente, pode-se interpretar o ancoramento como
um mapeamento de um ´unico filme no documento a dois no banco de dados, portanto
amb´ıguo). O ancoramento seria incompleto se houvesse dois n´os ancorados i e j tal que
um ´e ancestral de outro e h´a um n´o n˜ao ancorado no caminho entre eles.
A semˆantica conservadora que p ropomos requer que cada ancoramento seja n˜ao amb´ıguo
e completo por duas raz˜oes. Primeiro, ancoramentos amb´ıguos resultam em opera¸c˜oes
de atualiza¸c˜ao com poss´ıveis efeitos colaterais indesejados, como redundˆancia de dados.
Segundo, as lacunas apresentadas em ancoramentos incompletos permitem que o docu-
mento seja ancorada em diversas ´arvores do banco de dados (uma para cada lacuna), o que
pode ser visto como um tipo de ambig¨uidade.
´
E importante notar que um ancoramento
completo n˜ao requer que s e t (ou seja, o documento e o banco de dados) tenham todos
os seus n´os ancorados; na verdade, tudo o que ´e necess´ario ´e que exista uma sub-´arvore
s
′
de s, enraizada em s, e que s
′
ancore a uma sub-´arvore ´unica em t. Ainda mais, um
ancoramento incompleto pode ser sempre completado “desancorando-se” os pares de n´os
cujos pais n˜ao est˜ao ancorados um ao outro.
Determinando a Equivalˆencia de N´os
Consideramos que dois n´os XML s
i
e t
i
s˜ao equivalentes se: (1) eles apresentam o mesmo
tipo de elemento conforme a nota¸c˜ao de DTD, e (2) se h´a um consider´avel grau de simila-
ridade entre as sub-´arvores enraizadas neles. Este grau de similaridade pode ser avaliado
por alguma forma de similaridade de ´arvores tal como distˆancia de edi¸c˜ao em ´arvores.
Neste trabalho, como detalhado no Cap´ıtulo 5, usamos um processo de casamento de
baixo pra cima. Iniciamos casando os n´os folhas que apresentam os mesmos r´otulos e cujo
conte´udo ´e suficientemente similar. Usamos casamento aproximado, em vez de igualdade,
3.4 Linguagem de Atualiza¸c˜ao Livre de Esquema 33
para permitir erros de escrita e varia¸c˜oes de soletra¸c˜ao no documento e no banco de dados.
Uma vez que os n´os folhas que casam est˜ao ancorados, n´os prosseguimos de baixo pra
cima ancorando os ancestrais correspondentes. Em todos os casos, n´os ancoramos apenas
os n´os que tem tipos idˆenticos (r´otulos de elementos na nota¸c˜ao de DTD).
3.4 Linguagem de Atualiza¸c˜ao Livre de Esquema
Esta se¸c˜ao descreve a sintaxe da nossa linguagem de atualiza¸c˜ao livre de esquema, e
uma semˆantica conservadora para ela. Por conservadora entende-se que o resultado das
opera¸c˜oes usam todos os dados do documento fonte que podem ser “encaixados” no banco
de dados, contanto que: (i) o banco de dados resultante seja v´alido com respeito ao seu
DTD e (ii) nenhuma redundˆancia que poderia ser evitada seja introduzida no banco de
dados resultante.
3.4.1 A Sintaxe
Propomos a seguinte linguagem m´ınima para atualiza¸c˜ao de XML, parcialmente des-
crita como segue:
Path := doc(‘fname ’) Step*
Step := Axis Test Predicate?
Axis := ‘/’ | ‘//’
Test := name | ’@’name | ‘*’
Predicate := ‘[’ PredExpr ‘]’
PredExpr := number | OrExpr
Update := ‘INSERT’ Path ‘INTO’ Path |
‘UPDATE’ Path ‘WITH’ Path |
‘MERGE’ Path ‘INTO’ Path |
‘DELETE’ Path ‘FROM’ Path
Essencialmente, definimos quatro opera¸c˜oes, onde cada uma utiliza du as express˜oes de
caminho que definem o escopo da opera¸c˜ao. Por simplicidade, nossa linguagem ´e restrin-
gida a um fragmento de XPath muito pequeno, que ´e capaz de apontar os n´os apenas. No
fragmento acima d a especifica¸c˜ao segundo forma normal de Backus-Naur(EBNF), name,
fname and number s˜ao terminais que representam nomes de n´os, nomes de documen-
tos, e n´umeros naturais, respectivamente. Estes terminais s˜ao completamente definidos
3.4 Linguagem de Atualiza¸c˜ao Livre de Esquema 34
em (CLARK; DEROSE, 1999), assim como o n˜ao terminal OrExpr, que especifica os predi-
cados de compara¸c˜ao em XPath 1.0.
Exemplo 2 A seguinte atualiza¸c˜ao livre de esquema ex pressa a mesma atualiza¸c˜ao em
XQuery da Figura 4:
INSERT doc(’input.xml’) INTO doc(’db.xml’)
A seguinte atualiza¸c˜ao livre de esquema expressa a inser¸c˜ao de um filme espec´ıfico no
banco de dados:
INSERT doc(’input.xml’)//item[title=‘The Departed’]
INTO doc(’db.xml’)
Nota¸c˜ao
Por simplicidade, [P ] denota a lista de n´os que s˜ao retornados avaliando-se P como se faz
comumente em XPath. (Observe que cada express˜ao de caminho pode come¸car apenas
com um nome de documento, portanto [P ] ´e sempre bem definida.)
3.4.2 Uma Semˆantica Conservadora
Uma semˆantica conservadora para a linguagem que propomos ´e definida a seguir.
Como mencionado acima, esta semˆantica permite apenas ancoramentos n˜ao amb´ıguos e
completos; isto significa que a opera¸c˜ao ´e indefinida caso contr´ario.
Considere novamente A(e) como o conjunto (possivelmente vazio) dos n´os no banco
de dados em quais o n´o e no documento foi ancorado. Pelo fato de insistirmos em um
ancoramento n˜ao amb´ıguo, abusaremos um pouco da nota¸c˜ao e escreveremos A(e) = t
se t ´e o n´o no b anco de dados em qual e foi ancorado. Al´em disso, por quest˜ao de
simplicidade, n˜ao faremos distin¸c˜ao expl´ıcita entre um n´o ou a sub´arvore enraizada em
tal n´o. Entretanto, em todos os casos pode-se discernir se e denota apenas um n´o ou uma
sub-´arvore a partir do contexto.
3.4 Linguagem de Atualiza¸c˜ao Livre de Esquema 35
INSERT P
1
INTO P
2
Esta opera¸c˜ao insere o conte´udo de cada n´o retorn ado por P
1
em cada elemento retornado
por P
2
(um erro deve ser rep ortado se P
2
retorna atributos).
Seja s um n´o de [P
1
] e t um elemento de [P
2
]. A inser¸c˜ao de s em t ´e realizada como
segue. Primeiro, o processo de adapta¸c˜ao de dados ´e aplicado em s; como mencionado
anteriormente, isto resulta numa lista de elementos XML s
1
, . . . , s
n
em conformidade
com o DTD alvo. Cada n´o s
i
´e inserido em t separadamente. A inser¸c˜ao funciona
diferentemente dependendo se o n´o s
i
ancora ou n˜ao.
Se A(s
i
) = t
i
(ou seja, s
i
ancora), ent˜ao sejam e
1
, . . . , e
k
os descendentes de s
i
que
n˜ao ancoram (caso eles existam). Cada e
j
´e inserido na posi¸c˜ao mais `a direita (relativa a
ordem do documento) em t que n˜ao resulta em uma viola¸c˜ao de D
T
. Mais precisamente,
seja p
j
o pai de e
j
em s, e
j
´e inserido como filho de A(p
j
), no local mais `a direita tal que
o conte ´udo resultante ´e v´alido com respeito a D
T
, se poss´ıvel (veja Se¸c˜ao 3.5 abaixo).
Se s
i
n˜ao ancora (ou seja, A(s
i
) = ∅), tenta-se inserir s
i
como uma nova sub-´arvore
no banco de dados. Seja t
i
um descendente de t que cont´em todos os elementos do mesmo
tipo, isto ´e, mesmo r´otulo na nota¸c˜ao do DTD, de s
i
. Se t existe e ´e ´unico, s
i
´e inserido em
t da mesma maneira como acima, ou seja, no local mais `a direita que n˜ao causa viola¸c˜ao
do DTD.
O resultado de um opera¸c˜ao de inser¸c˜ao ´e uma seq¨uˆencia de atualiza¸c˜oes estruturadas
u
i
= (op
i
, l
i
, e
i
), um para cada filho n˜ao ancorado e
i
. A opera¸c˜ao real op
i
ser´a um APP
(anexar um n´o como filho) ou um INSB (inserir antes de um n´o), dependendo do DTD
(veja Se¸c˜ao 3.5); similarmente para o local preciso da atualiza¸c˜ao l
i
.
Exemplo 3 Considere novamente a inser¸c˜ao de filmes na Figura 3(a) no banco de dados
da Figura 1(a). O resultado da adapta¸c˜ao de dados ´e apresentado na Figura 7. A inser¸c˜ao
do filme da Figura 7(a) ´e detalhada na Se¸c˜ao 3.2; neste caso, o elemento genre ancorou,
levando `a in ser¸c˜ao do elemento movie apenas. A inser¸c˜ao do filme da Figura 7(b) ´e
realizada diferentemente pois o elemento genre n˜ao ancora no banco de dados. Uma vez
que o DTD para o banco de dados permite apenas um lugar para elementos genre, a sub-
´arvore inteira da Figura 7(b) ´e inserida no banco de dados. O resultado dessa opera¸c˜ao
livre de esquema s˜ao as primitvas estruturadas descritas no Exemplo 1.
3.4 Linguagem de Atualiza¸c˜ao Livre de Esquema 36
UPDATE P
2
WITH P
1
Enquanto o objetivo da opera¸c˜ao de inser¸c˜ao ´e adicionar conte´udo novo no banco de
dados, que s˜ao os n´os n˜ao ancorados, o objetivo da opera¸c˜ao de atualiza¸c˜ao ´e substituir
o conte´udo existente. Intuitivamente, esta opera¸c˜ao substitui todos os elementos n˜ao an-
corados no banco de dados por aqueles no documento que tˆem o mesmo r´otulo e podem
ser casados inequivocamente a outro. Como nas inser¸c˜oes, a opera¸c˜ao de atualiza¸c˜ao ´e
aplicada a cada n´o de [P
1
] e cada n´o elemento de [P
2
] separadamente, como segue.
Sejam s, t n´os de [P
1
] e [P
2
], respectivamente. Como antes, primeiro s ´e adaptado a
D
T
, resultando numa lista de elementos XML s
1
, . . . , s
n
. Cada s
i
´e tratado separadamente,
como segue. Se s
i
n˜ao ancora em t, nada ´e feito e prossegue-se para o pr´oximo elemento
da lista. Caso contr´ario, seja A(s
i
) = t
i
. Cada descendente de s
i
´e substitu´ıdo por um
n´o equivalente t
i
com o mesmo r´otulo mas conte´udo diferente (caso contr´ario tais n´os
deveriam estar ancorados).
Sejam e
1
, . . . , e
k
os descendentes de s
i
que n˜ao ancoram, e seja p
1
, . . . , p
j
seus pais
respectivos. Para cada e
j
, se a regra do DTD para o tipo de p
j
permite no m´aximo uma
ocorrˆencia de um elemento do tipo de e
j
e A(p
j
) tem um filho e
′
j
com o mesmo r´otulo de
e
j
, n´os os substitu´ımos com a primitiva: u = (REP, e
′
j
, e
j
).
Exemplo 4 Usando os documentos de nosso exemplo (Figura 1(a) e Figure 3(b)), consi-
dere a seguinte atualiza¸c˜ao:
UPDATE doc(’db.xml’) WITH doc(’ifilm.xml’)
Figura 8(b) mostra o ancoramento (depois da adapta¸c˜ao de dados) do documento da Fi-
gura 3(b). studio e year s˜ao substitu´ıdos no banco de dados pelos n´os correspondentes no
documento.
Uma Nota sobre semˆantica
Deve-se observar que, de acordo com a maneira que os filmes s˜ao organizados no banco de
dados do nosso exemplo, filmes que pertencem a mais de um gˆenero ir˜ao aparecer diversas
vezes no banco de dados, uma para cada gˆenero. Portanto, na semˆantica conservativa,
a atualiza¸c˜ao do Exemplo 4 falharia se o filme “Deja Vu” aparecesse m ais de uma vez
no banco de dados. Isto significaria que s na Figura 8(b) n˜ao poderia ancorar de forma
3.5 Atualiza¸c˜oes Resultando em Documentos V´alidos 37
n˜ao amb´ıgua. Para realizar essa opera¸c˜ao de atualiza¸c˜ao, teria-se que utilizar o seguinte
comando: UPDATE doc(’db.xml’) WITH do c(’film.xml’)//genre
MERGE P
1
INTO P
2
A opera¸c˜ao de fus˜ao ou merge ´e uma combina¸c˜ao de uma inser¸c˜ao e uma atualiza¸c˜ao.
Isto ´e equivalente a realizar em seq¨uˆencia as opera¸c˜oes INSERT P
1
INTO P
2
e UPDATE
P
2
WITH P
1
. Intuitivamente, elementos n˜ao ancorados de um documento de entrada s˜ao
inseridos no banco de dados, e elementos ancorados no banco de dados s˜ao substitu´ıdos
por seus elementos correspondentes no documento.
Exemplo 5 Considere a fus˜ao do banco de dados da Figura 1(a) com o documento da
Figura 3(b). Al´em das atualiza¸c˜oes discutidas no Exemplo 4, a opera¸c˜ao de fus˜ao teria
tamb´em inserido a classifica¸c˜ao (rating) do filme, contanto que a opera¸c˜ao de adapta¸c˜ao
de dados possa encontrar um tipo equivalente no banco de dados e o DTD do banco de
dados permita a inser¸c˜ao.
DELETE P
1
FROM P
2
Intuitivamente esta opera¸c˜ao remove do banco de dados aqueles n´os que ancoram aos
n´os especificados por P
1
. Para minimizar os potenciais efeitos colaterais indesejados, esta
opera¸c˜ao deve ser realizada apenas quando P
2
retorna um ´unico elemento.
Como antes, a opera¸c˜ao ´e realizada separadamente para cada n´o s que casa com P
1
;
para cada n´o desses, seja s
1
, . . . , s
n
o resultado de adaptar s ao DTD D
T
. Para cada s
i
,
se A(s
i
) ´e simplesmente removido, se estiver definido, usando a primitiva: u = (DELETE,
A(s
i
), null).
Enfatizamos que remo¸c˜oes livre de esquema s˜ao potencialmente perigosas, uma vez
que podem surgir efeitos colaterais inesperados pelos usu´arios. Talvez a maneira mais
natural para usu´arios inexperientes especificarem remo¸c˜oes ´e atrav´es da abordagem de
apontar-e-clicar, com ajuda de um interface de usu´ario apropriada, por exemplo.
3.5 Atualiza¸c˜oes Resultando em Documentos V´alidos
Em todas as opera¸c˜oes de atualiza¸c˜ao, ´e necess´ario detectar e prevenir mudan¸cas que
resultem em viola¸c˜ao do DTD do banco de dados. Durante a inser¸c˜ao de novos dados,
3.5 Atualiza¸c˜oes Resultando em Documentos V´alidos 38
q
I
q
a
1
q
b
q
c
q
a
2
a
b
c
a
b
a
Figura 11: Autˆomato de Glushkov correspondente a regra de DTD l
i
← a, (b∗ | (c, a+)).
q
I
´e o estado inicial; q
b
, q
c
correspondem aos s´ımbolos b e c, respectivamente; q
a
1
, q
a
2
correspondem a primeira e segunda ocorrˆencia do s´ımbolo a. Estados finais s˜ao denotados
por n´os com linhas duplas.
dois passos devem ser realizados: formatar os dados de entrada de acordo com o DTD
do banco de dados, o que ´e feito pelo passo de adapta¸c˜ao de dados, e certificar-se que o
conte´udo do banco de dados resultante de cada opera¸c˜ao ´e v´alido. Isto inclui validar os
novos elementos a serem inseridos assim como os elementos onde a inser¸c˜ao ser´a realizada.
Para remo¸c˜oes, ´e preciso garantir que o conte´udo do elemento afetado pela atualiza¸c˜ao
continue v´alido. Finalmente, para atualiza¸c˜oes, ou seja, substitui¸c˜ao de n´os, deve-se tomar
cuidado com as restri¸c˜oes globais nos DTDs, tais como regras ID e IDREF, que aplicam-se
ao documento como um todo. Deixamos a discuss˜ao sobre formata¸c˜ao para o Cap´ıtulo 4,
onde processo de adapta¸c˜ao de dados ´e discutido em detalhes.
Determinar que uma atualiza¸c˜ao a um documento v´alido resulta tamb´em num docu-
mento v´alido ´e um problema por si s´o. Entretanto, algumas das solu¸c˜oes propostas na
literatura (BALMIN; PAPAKONSTANTINOU; VIANU, 2004; BARBOSA; LEIGHTON; SMITH,
2006; BARBOSA et al., 2004) e seu impacto no nosso arcabou¸co s˜ao discutidas brevemente
aqui. Em particular, a discuss˜ao considera quest˜oes de implementa¸c˜ao e o tamanho dos
dados auxiliares requeridos por tais solu¸c˜oes.
H´a uma solu¸c˜ao geral para este problema que garante tempos de revalida¸c˜ao na ordem
de O(k log
2
n), onde n ´e o tamanho do banco de dados e k ´e o tamanho da atualiza¸c˜ao,
ou seja, o n´umero de n´os sendo inseridos ou removidos. Esta solu¸c˜ao necessita que sejam
criadas estruturas de dados auxiliares n˜ao triviais (e proporcionalmente muito grandes).
Uma solu¸c˜ao mais pr´atica ´e usar os m´etodos propostos em (BARBOSA et al., 2004), que
necessita apenas de t empo O(k log n), e que usam uma estrutura de dados auxiliar mais
simples e muito menor, e s˜ao aplic´aveis `a grande maioria (acima de 98%) dos DTDs
usados na pr´atica (BARBOSA; LEIGHTON; SMITH, 2006). A solu¸c˜ao mais simples, que
´e revalidar o banco de dados inteiro ou apenas os elementos que foram afetados pela
atualiza¸c˜ao, n˜ao requerem nenhum armazenamento auxiliar mas s˜ao p ontecialmente muito
caros (BARBOSA et al., 2004).
3.5 Atualiza¸c˜oes Resultando em Documentos V´alidos 39
Determinando o Local da Atualiza¸c˜ao
Um passo extra ´e necess´ario para inser¸c˜oes: antes de aplicar os algoritmos de revalida¸c˜ao
acima, ´e necess´ario determinar o lugar no qual a atualiza¸c˜ao deve ser aplicada.
´
E ´obvio que
dependendo do DTD, podem haver v´arios lugares onde a inser¸c˜ao poderia ser permitida.
Sabe-se que um DTD ´e uma associa¸c˜ao de express˜oes regulares 1-unambiguous, ou mode-
los de conte´udo, para r´otulos de elementos (BR
¨
UGGEMANN-KLEIN; WOOD, 1998). Sejam
l
i
← r
i
uma regra do DTD e G
r
i
o autˆomato de Glushkov (BR
¨
UGGEMANN-KLEIN; WOOD,
1998) correspondente a r
i
, ond e h´a um estado separado em G
r
i
para cada ocorrˆencia de
um s´ımbolo em r
i
.
´
E poss´ıvel construir um ´ındice que indica, para cada r´otulo de ele-
mento l, quais ocorrˆencias de um s´ımbolo podem preceder um elemento com r´otulo l de
um elemento v´alido.
Por exemplo, considere o autˆomato de Glushkov da Figura 11, que corresponde a
express˜ao regular da regra de DTD l
i
← a, (b∗ | (c, a+)). A partir deste autˆomato, e
pelo fato de exigirmos que as inser¸c˜oes sejam apenas na posi¸c˜ao mais `a direita poss´ıvel,
podemos inferir as seguintes regras:
- elementos c podem ser inseridos apenas depois de uma ocorrˆencia de a
1
;
- elementos b podem ser inseridos apenas depois de outros elementos b;
- um elemento a pode ser inserido apenas depois de uma ocorrˆencia de a
2
.
Infelizmente, se l
i
´e o r´otulo de um elemento e cujo pai ´e p, e o modelo de conte´udo
associado com p cont´em m´ultiplas ocorrˆencias de l
i
, determinar qual ocorrˆencia de l cor-
responde a e requer validar p. Isto pode ser evitado se forem usados os m´etodos de
revalida¸c˜ao incremental discutidos em (BARBOSA et al., 2004), que mantˆem precisamente
o mapeamento entre os n´os no documento XML e os estados nos autˆomatos finitos deter-
min´ısticos usados para valid´a-los.
DTDs livres de conflito
Para uma classe bastante comum de DTDs a situa¸c˜ao ´e bem mais simples. Express˜oes re-
gulares livres de conflito, chamados de modelos de conte´udo de elementos, s˜ao aqueles em
que nenhum s´ımbolo aparece mais que uma vez (BARBOSA et al., 2004), e correspondem a
mais de 98% daqueles usando na pr´atica de acordo com um levantamento recente (BAR-
BOSA; LEIGHTON; SMITH, 2006). Em tais casos, h´a uma correspondete de 1-para-1 entre
3.5 Atualiza¸c˜oes Resultando em Documentos V´alidos 40
r´otulos de elementos e estados no autˆomato correspondente ao modelo de conte´u do. Por-
tanto, com o m´etodo descrito acima seria p oss´ıvel encontrar a localiza¸c˜ao precisa de uma
atualiza¸c˜ao sem validar o documento e sem armazenar nenhuma informa¸c˜ao auxiliar.
41
4 Adapta¸c˜ao de Dados
O processo de adapta¸c˜ao de dados ´e respons´avel por formatar os dados do documento
fonte de acordo com o DTD do banco de dados alvo. Isto ´e feito por duas r az˜oes principais:
(1) assegurar que o banco de dados resultante da atualiza¸c˜ao seja v´alido (deve-se notar
que em geral ´e necess´ario tamb´em revalidar o banco de dados depois da atualiza¸c˜ao), e
(2) facilitar o processo de descoberta de ˆancora, que ´e bastante dependente dos tipos de
n´os nas ´arvores sendo casadas, conforme a nota¸c˜ao de DTD.
Essencialmente, nosso processo de adapta¸c˜ao d e dados encontra um mapeamento entre
os tipos, ou r´otulos de elementos no DTD, do documento de entrada e os tipos do banco
de dados alvo. Em outras palavras, o processo produz um conjunto de correspondˆencias
entre tais tipos, o qual ´e usado para traduzir os dados de entrada de acordo com o DTD
alvo. Para isto, nosso m´etodo explora a similaridade de conte´udo entre instˆancias de
diferentes tip os, assim como restri¸c˜oes semˆanticas e estruturais, como discutido a seguir.
4.1 Mapeamentos na Adapta¸c˜ao de Dados
O mapeamento utilizado na adapta¸c˜ao de dados ´e uma fun¸c˜ao que mapeia os tipos
do documento fonte s com DTD D
s
no banco de dados t com DTD D
t
. Na Figura 12 um
exemplo de mapeamento ´e mostrado. Observe, entretanto, que um n´o folha pode ocorrer
como filho de v´arios elementos distintos. Por exemplo, no DTD D
t
da Figura 12, o ele-
mento title pode conter valores de t´ıtulos de filmes (movie) ou t´ıtulo de cr´ıticas (review)
sobre o filme. Isto gera confus˜ao no mapeamento, e conseq¨uentemente, na tradu¸c˜ao dos
elementos. Para diferenciar os valores de cada tipo de elemento em casos como esse, os ti-
pos s˜ao defi nidos n˜ao apenas pelo r´otulo no DTD (ex., title), mas tamb´em pelo seu contexto
no documento correspondente (ex., movies/genre/movie ou movies/genre/movie/review),
como segue.
O contexto de um elemento e num documento XML com raiz r ´e defi nido pela
4.2 Casamento de Tipos 42
Figura 12: Mapeamento entre os grafos DTD de D
s
e D
t
.
Figura 13: Rede bayesiana para combina¸c˜ao dos componentes de similaridade
seq¨uˆencia de r´otulos de elementos no caminho de r at´e e. Por exemplo, o contexto de t itle
no DTD D
t
da Figura 12 pode ser movie ou movie/review. De agora em diante, os tipos
considerados no mapeamento s˜ao definidos pelo r´otulo e pelo contexto do elemento, como
mostrado na Figura 12.
4.2 Casamento de Tipos
O primeiros passo para mapear dois esquemas ´e casar seus tipos. Neste processo
s˜ao considerados apenas os tipos de n´os folhas (elementos simples e atributos), os quais
apresentam conte´udo textual. Sejam A e B tipos do documento fonte s com DTD D
s
e do banco de dados t com DTD D
t
, respectivamente. A similaridade entre A e B ´e
medida usando dois component es principais: a similaridade de conte´udo (C (A, B)) e a
similaridade de r´otulos (L(A, B)) entre eles. A similaridade de conte´udo estima a extens˜ao
da sobreposi¸c˜ao de valores nos elementos do tipo A com os valores nos elementos do
tipo B, baseados em seus valores reais presentes do documento e no banco de dados. A
similaridade de r´otulo estima qu˜ao pr´oximos s˜ao os r´otulos de A e B (e de seus ancestrais).
Os escores de similaridade s˜ao modelados como probabilidades e combinados no mo-
delo formal de redes bayesianas (PEARL, 1988) como segue (veja a Figura 13). A similari-
dade final entre A e B, denotada por F (A, B), depende da similaridade de conte´udo e de
4.2 Casamento de Tipos 43
r´otulo entre eles. Al´em disso, a similaridade de conte´udo C considera a similaridade entre
as palavras-chave K e os valores V dos tipos de elementos, como ilustrado na Figura 13.
Assume-se que C e L influenciam F atrav´es de um operador disjuntivo or(·, ·), tamb´em
conhecido como Noisy-OR-Gate (PEARL, 1988):
F (A, B) = or(C (A, B), L(A, B))
Informalmente, usando este operador disjuntivo assume-se que qualquer n´o pai (C e
L) pode ativar F , ou seja, aumentar significantemente seu escore final. Este operador ´e
particularmente ´util quando qualquer fator pode ativar F sozinho, independente de outros
fatores (PEARL, 1988). Fazendo isto, evita-se a necessidade de fazer ajustes finos nos
pesos relativos de fatores individuais, como mostrado em nossos resultados experimentais
(Cap´ıtulo 6). Formalmente, o operador d isjuntivo ´e definido como segue:
or(x, y) = 1 − ((1 − x) · (1 − y))
onde x e y s˜ao probabilidades.
Similaridade de conte´udo
N´os textuais e num´ericos s˜ao tratados diferentemente para calcular o escore C. Para
elementos e atributos num´ericos, uma abordagem simples por´em efetiva ´e utilizada: assu-
mindo que os valores num´ericos do tipo B seguem uma distribui¸c˜ao gaussiana, a similari-
dade entre A e B ´e definida como o valor m´edio da fun¸c˜ao densidade de probabilidade para
cada valor em n´os do tipo A. A fun¸c˜ao densidade foi adaptada para retornar 1 quand o
um valor ´e igual a m´edia ou u ma fra¸c˜ao, caso contr´ario. Isto foi feito normalizando-se
a fun¸c˜ao pela densidade m´axima, que ´e justamente atingida quando um valor ´e igual a
m´edia. Portanto, o escore de conte´udo para elementos e atributos num´ericos ´e definido
como segue:
C (A, B) =
1
|A|
v∈A
e
−
(v−µ)
2
2σ
2
onde σ e µ s˜ao o desvio padr˜ao e a m´ed ia, respectivamente, dos valores de elementos do
tipo B.
Elementos e atributos textuais, por outro lado, necessitam de mais trabalho. Como
ilustrado na Figura 13, a similaridade de conte´udo dos n´os textuais ´e calculada combinando-
4.2 Casamento de Tipos 44
se os escores das similaridades baseadas em palavras-chave (K) e valores (V ), ou seja:
C (A, B) = or(K(A, B), V (A, B))
onde K(A, B) e V (A, B) correspondem as similaridades b aseadas em palavras-chave e
valores entre A e B, respectivamente.
Similaridade baseada em palavras-chave
A similaridade entre os tipos textuais A e B ´e estimada atrav´es da por¸c˜ao de palavras em
comum compartilhadas por eles. Assume-se que o conte´udo de B ´e representativo com
rela¸c˜ao ao dom´ınio de seu tipo; ou seja, a maioria dos termos em valores de A podem
ser encontrada em B tamb´em, se eles s˜ao correspondentes. Note que o inverso n˜ao ´e
necessariamente verdade; ou seja, a similaridade de conte´udo pode ser assim´etrica. Intui-
tivamente, a similaridade de termos entre A e B deve ser alta se a sobreposi¸c˜ao de termos
entre o conte´udo de A e B ´e alta, e os termos em A que ocorrem em B s˜ao t´ıpicos nos
valores dos n´os do tipo B (veja abaixo). Mais precisamente, define-se:
K(A, B) =
1
2
k∈A∩B
w
k
(A)
w
total
(A)
+ 1 −
k∈A∩B
1 − w
k
(B)
(4.1)
onde w
k
(A) e w
k
(B) s˜ao os pesos do termo k relativa aos tipos A e B, respectivamente;
e w
total
(A) =
w
k
(A)∀k ∈ A.
O primeiro componente da Equa¸c˜ao 4.1 ´e uma soma normalizada de pesos das palavras
em A ∩ B. A similaridade m´axima ´e dada quand o A ∩ B = A, e a m´ınima quando
A ∩ B = ∅. O termo d e pondera¸c˜ao w
k
(A) ´e calculado pelo esquema de p ondera¸c˜ao
bastante conhecido, TF-IDF (BAEZA-YATES; RIBEIRO-NETO, 1999), privilegiando a alta
sobreposi¸c˜ao com palavras que s˜ao raras no documento de entrada mas comuns nos valores
dos n´os do tipo A:
w
k
(A) = tf
k
(A) · log
1 +
N
s
att(s, k)
onde tf
k
(A) ´e a freq¨uˆencia do termo k entre os valores de A, N
s
´e o n´umero total de tipos
no DTD de entrada D
s
e att(s, k) ´e o n´umero de n´os no documento fonte contendo k. Em
outras palavras, w
k
(A) ser´a mais alto se k ´e freq¨uente em valores de A e n˜ao aparece em
muitos elementos do documento s.
O segundo componente da Equa¸c˜ao 4.1 combina a chance de cada termo em n´os do
tipo A ser um termo t´ıpico no conte´udo de B, usando o operador disjuntivo. Este operador
4.2 Casamento de Tipos 45
permite que um ´unico termo t´ıpico aumente significamente a similaridade final entre A e
B. Consideramos que um termo ´e t´ıpico de B se ele ocorre em grande parte dos n´os do
tipo B e em nenhum outro tipo do banco de dados. Este conceito ´e similar ao esquema
TF-IDF. Entretanto, ao contr´ario do TF-IDF tradicional, o termo de pondera¸c˜ao w
k
(B)
retorna um valor no intervalo [0, 1], o qual ´e modelado como uma probabilidade:
w
k
(B) =
log(val(B, k))
log(V
B
)
·
1 −
log(att(t, k))
log(N
t
)
onde val(B, k) retorna o n´umero de n´os do tipo B onde k ocorre em seu conte´udo textual,
V
B
´e o n´umero total de n´os do tipo B, att(t, k) ´e o n´umero de n´os em t contendo k em
seu valor textual e N
t
´e o n ´umero total de tipos diferentes de n´os em t.
Similaridade baseada em valor
Enquanto a similaridade baseada em palavras-chave funciona bem quando h´a pouca ou
nenhuma sobreposi¸c˜ao de valores exatos entre o conte´udo de A e B, a similaridade baseada
em valor tira vantagem desta sobreposi¸c˜ao. Intuitivamente, a similaridade baseada em
valor entre A e B ´e alta se muitos valores do conte´udo de A s˜ao encontrados no conte´udo
de B. A contribui¸c˜ao de cada valor em A ∩ B para similaridade final ´e proporcional ao
n´umero de n´os de A, ou seja, 1/log(|A|), que ´e combinada por um operador de disjun¸c˜ao.
Assim define-se:
V (A, B) = 1 −
v∈A
1 −
o
v
(B)
l og(|A|)
onde o
v
(B) ´e 1 se o valor v ocorre em pelo menos um n´o do tipo B, ou 0 caso contr´ario;
e |A| ´e o n´umero de elementos do tipo A.
Dois valores s˜ao considerados iguais se eles cont´em exatamente as mesmas palavras-
chave. Para acelerar a computa¸c˜ao, representamos cada valor por uma assinatura MD5
do conjunto de suas palavras-chave.
´
E necess´ario notar que palavras muito comuns (stop-
wrods) n˜ao s˜ao consideradas palavras-chave, portanto n˜ao s˜ao in clu´ıdas nas assinaturas
dos valores.
Similaridade de r´otulo
A similaridade de r´otu lo L(A, B) entre A e B ´e computada levando em considera¸c˜ao
seus ancestrais. Os r´otulos n˜ao s˜ao comparados diretamente; em vez disso s˜ao usados
os radicais das palavras e algumas heur´ısticas simples para extrair palavras-chave rele-
4.2 Casamento de Tipos 46
vantes dos r´otulos. Por exemplo, “running
time” ´e representado por {“run”, “time”}. O
conjunto de palavras-chave de um tipo ´e chamado de descritor de r´otulo.
A similaridade entre um par de descritores de r´otulo ´e estimada usando a vers˜ao
“soft” da medida do cosseno no modelo espa¸co-vetorial, denominado soft TF-IDF (CO-
HEN; RAVIKUMAR; FIENBERG, 2003). Diferentemente da medida do cosseno tradicional,
o softTF-IDF relaxa necessidade de casamento exato entre as palavras-chave e alcan¸ca
melhores resultados em nosso contexto. O modelo softTF-IDF considera tamb´em palavras
similares usando uma segunda medida de similaridade para palavras-chave. Desta forma,
dadas duas palavras-chave de r´otulo a e b, tal que |a| ≤ |b|, a similaridade das palavras ´e
definida como s(a, b) = |a|/|b| se a ´e prefixo ou sufixo de b, ou 0 caso contr´ario.
Para calcular a similaridade de r´otulo, seja close(θ, A, B) o conjunto de pares de
palavras-chave (a, b), onde a ∈ A e b ∈ B, e tal que s(a, b ) > θ e b = arg max
b
′
∈B
s(a, b
′
); ou
seja, b ´e uma palavra-chave de B com a mais alta similaridade para a. Mais precisamente,
define-se:
L(A, B) =
(a,b)∈close(θ,A,B)
w(a, A) · w(b, B) · s(a, b)
a∈A
w(a, A)
2
·
b∈B
w(b, B)
2
onde w(a, A) e w(b, B) ´e o p eso de palavras-chave de r´otulo a e b com rela¸c˜ao ao tipos A
e B, respectivamente.
Dois fatores s˜ao levados em considera¸c˜ao para calcular o peso de uma p alavra: (1) o
n´ıvel do elemento cujo r´otulo cont´em a palavra-chave, ou seja, o n´umero de elementos no
caminho do n´o raiz at´e ele, e (2) qu˜ao raro ´e a palavra-chave entre os tipos de elementos
no esquema corresp ond ente. Intuitivamente, uma palavra-chave de mais baixo n´ıvel, que
ocorre no r´otulo de um n´o folha, melhor descreve um tipo que uma palavra-chave de n´ıvel
mais alto, que ocorre no r´otulo do n´o raiz, por exemplo. Al´em disso, um r´otulo que ocorre
em apenas um ´unico tipo de elemento ´e mais espec´ıfico que outro que ocorre em diversos
tipos. Mais formalmente, define-se:
w(a, A) = level(a, A) · log(IDF
a
)
onde IDF
a
´e o inverso da fra¸c˜ao dos descritores de r´otulo que cont´em a no esquema
correspondente.
4.3 Encontrando mapeamentos 47
Figura 14: Mapeamento entre os grafos DTD de D
s
e D
t
, com pares conflitantes a e b.
4.3 Encontrando mapeamentos
Uma vez que a medida de similaridade para os pares de tipos foi definida, o pr´oximo
passo ´e encontrar quais pares de tipos de fato casam. Tipos A e B casam quando a sua
similaridade F (A, B) ´e maior que um dado limiar. Baseados em uma s´erie de experi-
mentos preliminares, onde testamos a qualidade dos mapeamentos com alguns valores d e
limiar, definimos em nosso trabalho o valor 0,5. A partir de uma computa¸c˜ao par a par, ´e
constru´ıdo um multi-mapeamento de tipos (MELNIK; GARCIA-MOLINA; RAHM, 2002) M,
que ´e a rela¸c˜ao que associa cada tipo em s a todos aqueles que casam com ele em t.
Para isto, apenas pares de tipos que tem tipos de dados compat´ıveis s˜ao considerados.
Al´em disso, para atributos textuais, exige-se que seu tamanho seja compat´ıvel. Intuitiva-
mente, isto evita casar, por exemplo, um tipo contendo cr´ıticas de filmes com outro que
cont´em t´ıtulos de filmes, embora seus tipos de dados sejam os mesmos e eles apresentem
palavras-chave em comum, uma vez que os t´ıtulos de filmes comumente aparecem nos co-
ment´arios. Portanto, considerand o um tip o de elemento textual X, seja
ˆ
X a distribui¸c˜ao
dos tamanhos dos valores em n´os do tipo X, seja E(
ˆ
X) a m´edia de
ˆ
X e std(
ˆ
X) o desvio
padr˜ao de
ˆ
X. B ´e somente considerado como um candidato plaus´ıvel para A somente
se a diferen¸ca entre a m´edia dos valores de
ˆ
A e
ˆ
B esteja dentro do desvio padr˜ao de
ˆ
B.
Mais precisamente, exige-se que |E(
ˆ
A) − E(
ˆ
B)| ≤ max(std(
ˆ
B), ε), onde ε ´e um limiar de
tolerˆancia. Em nossos testes percebemos que ε = 1.5 funciona bem na pr´atica.
Pares conflitantes
Outra restri¸c˜ao imposta ´e que M n˜ao contenha pares conflitantes, como segue. Sejam
X e Y tipos de D
s
, X
′
e Y
′
tipos de D
t
e lca(X, Y ) o ancestral comum mais baixo no
contexto (ver Se¸c˜ao 4.1) de X e Y . Dois pares de mapeamento (X, X
′
) e (Y, Y
′
) s˜ao
conflitantes se D
s
permite mais de uma ocorrˆencia de elementos dos tipos X e Y como
4.3 Encontrando mapeamentos 48
descendentes de lca(X, Y ), por´em D
t
n˜ao permite o mesmo para os elementos dos tipos
X
′
e Y
′
descendentes de lca(X
′
, Y
′
). Por exemplo, a Figura 14 mostra um mapeamento
em conflito, onde a e b s˜ao pares conflitantes. Neste exemplo, X e Y corresponderiam a
keyword e comments, e X
′
e Y
′
corresponderiam a description e paragraph. Intuitivamente,
esses pares conflitantes induzem a gera¸c˜ao de elementos redundantes, em particular os
elementos do tip o movies (lca(X
′
, Y
′
)). Isto acontece pois o tipo film(lca(X, Y )) pode
ter como descendentes v´arios elementos dos tipos keyword e comments provenientes do
documento de entrada; entretanto, como D
t
n˜ao permite mais de um elemento do tipo
description por filme, para “acomodar” os m´ultiplos elementos traduzidos como description
precisamos duplicar os elementos movie e todos os seus d escendentes, inclusive os v´arios
elementos paragraph. Isto resulta numa grande redundˆancia de dados, que poderia ser
ainda maior se houvessem mais pares conflitantes.
Portanto, ´e necess´ario remover do multi-mapeamento os pares conflitantes que contri-
buem com escore m´ınimo de similaridade agregada entre D
s
e D
t
. Na realidade, este
´e um problema de otimiza¸c˜ao NP-completo. Considere do problema de encontrar a co-
bertura de v´ertices de peso m´ınimo (GAREY; JOHNSON, 1979) em um grafo G = (V, E),
onde v´ertices s˜ao associados com pesos positivos. O problema consiste em encontrar a
cobertura de V , ou seja, V
C
⊆ V tal que todas as arestas em E incidem num v´ertice de
V
C
, cujo peso total ´e m´ınimo. Este problema pode ser reduzido em tempo polinomial ao
problema de encontrar o conjunto de pares conflitantes com escore agregado m´ınimo numa
configura¸c˜ao onde pares em M correspondem a v´ertices em V e conflitos correspondem
a arestas em E. Em virtude da complexidade do problema, utilizamos uma heur´ıstica
gulosa simples e eficiente, a qual ´e descrita a seguir.
Em cada rodada, todos os pares em M s˜ao ordenados comparando-se seus escores
individuais contra a soma dos escores dos pares que est˜ao em conflito com eles, remo-
vendo o par com menor valor. Este processo ´e repetido at´e que n˜ao existam mais pares
conflitantes.
A partir do multi-mapeamento, nosso objetivo ´e extrair um mapeamento final µ que
associa tipos de D
s
em tipos de D
t
. Note que, diferente de M, µ ´e uma fun¸c˜ao. Al´em
disso, como de costume (RAHM; BERNSTEIN, 2001), exige-se que µ seja injetiva; ou
seja, cada tipo de s ´e mapeado no m´aximo a um tipo de t, e vice-versa. O algoritmo
best filter (MELNIK; GARCIA-MOLINA; RAHM, 2002) ´e usado para produzir µ. O processo
consiste basicamente em escolher os melhores pares candidatos dispon´ıveis em M at´e que
todos os tipos poss´ıveis sejam mapeados.
4.4 Traduzindo Instˆancias 49
4.4 Traduzindo Instˆancias
Uma vez que o mapeamento ´e definido, traduzir a instˆancia de D
s
em uma instˆancia
de D
t
se faz necess´ario. Os dados de entrada s˜ao achatados, ignorando tipos de elementos
que n˜ao est˜ao no mapeamento, e publicados de acordo com o DTD alvo. Nosso algoritmo
de pu blica¸c˜ao ´e baseado nas t´ecnicas path outer union e hash-based tagging de Shanmu-
gasundaram et al. (2001).
Mais precisamente, a ´arvore de entrada s ´e achatada numa rela¸c˜ao R(A
1
, . . . , A
n
),
onde cada A
i
corresponde a um tipo de D
s
mapeado a um tipo de D
t
. Caminha-se em
s numa busca em profundidade; cada vez que ´e encontrado um n´o folha l cujo tipo ´e
mapeado (ou seja, pertence a R), todos os n´os internos e
1
, . . . , e
m
situados no caminho
da raiz de s at´e l s˜ao identificados. Neste ponto uma tupla ´e adicionada a R contendo os
valores de todos os n´os folhas mapeados que s˜ao descendentes de algum e
i
, contanto que
cada n´o destes seja a ´unica ocorrˆencia descendente de e
i
permitida por D
s
. Elementos e/ou
n´os folhas ausentes s˜ao representados como valores null para as colunas correspondentes
de R. Observe que fazendo isto todos os dados da instˆancia fonte que pode ser mapeada
s˜ao armazenados em R.
A produ¸c˜ao da ´arvore XML traduzida ´e feita da seguinte forma. Primeiro, um ele-
mento XML n˜ao ordenado t
i
´e gerado para cada r
i
∈ R, certificando-se de evitar a gera¸c˜ao
de sub-´arvores duplicadas, o que ´e feito mantendo-se uma tabela hash com os valores que
j´a foram mapeados. As ´arvores XML ordenadas finais devem ser v´alidas de acordo com o
modelo de conte´udo associado com o tipo de t
i
em D
t
. Em outras palavras, a ´arvore deve
produzir uma palavra que ´e gerada pela express˜ao regular em D
t
. Portanto, dado um n´o
interno e
i
em t
i
, e o autˆomato de Glushkov G para o modelo de conte´udo associado com
e
i
em D
t
, ´e necess´ario produzir uma palavra w
i
que ´e: (1) aceita por G, e (2) contem
tantos filhos de e
i
quanto p oss´ıvel.
Isto ´e feito como segue. Vendo G como um grafo direcionado, obt´em-se uma ´arvore
geradora m´ınima MCA
G
, a partir do qual o menor caminho p em G ´e encontrado, tal
que: (1) p come¸ca no estado inicial de G e leva a um estado final; (2) p cont´em tantos n´os
correspondentes ao tipos mapeados (ou seja, tipos em R) quanto poss´ıvel. Isto pode ser
feito caminhando em MCA
G
de tr´as pra frente a partir dos estados finais. Cada caminho
´e verificado(h´a um n´umero linear deles), mantendo-se o caminho com o maior n´umero de
tipos mapeados n ele. Se dois caminhos tem o mesmo n´umero de tipos mapeados, o mais
longo ´e descartado. Isto resulta em uma palavra v´alida w
i
de acordo com G. O passo
4.4 Traduzindo Instˆancias 50
final ´e substituir os elementos em w
i
com aqueles que foram map eados pela adapta¸c˜ao de
dados, de acordo com seus tipos. Se mais de um elemento mapeado existe para o mesmo
elemento em w
i
, um deles ´e escolhido arbitrariamente.
Exemplo 6 Considere o autˆomato de Glushkov da Figura 11; a ´arvore geradora teria os
la¸cos dos n´os q
b
e q
a
2
removidos. Observe que h´a trˆes poss´ıveis caminhos que poderiam
ser usados para produzir conte´udo v´alido: I → q
a
1
, I → q
a
1
→ q
b
, e I → q
a
1
→ q
c
→ q
a
2
.
Esses correspondem a seguinte seq¨uˆencia de elementos XML: a, a b, e a c a, respectiva-
mente.
Valores ausentes
O processo acima resulta numa seq¨uˆencia de elementos XML formando conte´udo XML
v´alido para os n´os internos correspondentes (e
i
). Entretanto, ´e poss´ıvel que ele contenha
elementos que n˜ao correspondem a nenhum tipo mapeado pela adapta¸c˜ao de dados. Se-
melhantemente, ´e poss´ıvel que alguns elementos apresentem atributos obrigat´orios que
n˜ao s˜ao mapeados pelo nosso algoritmo de adapta¸c˜ao de dados. Em tais casos, precisa-se
adicionar valores padr˜oes apropriados como conte´udo de tais elementos e atributos. Para
elementos textuais e atributos ausentes seus valores s˜ao definidos como “unknown”. Para
atributos ID, um n´umero ´unico ´e inserido (por exemplo, mantido por um contador) para
evitar a p rodu¸c˜ao de conte´udo inv´alido. Para n´os complexos, o processo discutido acima ´e
repetido; ou seja, encontra-se uma seq¨uˆencia m´ınima de elementos que leva a um elemento
v´alido, e itera-se sobre os elementos dessa seq¨uˆencia.
Exemplo 7 A Figura 8(b) mostra o ancoramento do filme da Figura 3(b). Observe que
o atri buto @country foi adicionado ao elemento rat ing; porque nenhum pa´ıs est´a definido
no documento, o valor padr˜ao f oi usado no conte´udo mapeado.
´
Arvore geradora m´ınima
Historicamente, o problema de encontrar a ´arvore geradora m´ınima em grafos direciona-
dos ´e chamado de problema de minimum-cost arborescence (KLEINBERG; TARDOS, 2005).
No nosso contexto, o grafo ´e o AFD do modelo de conte´udo de um dado tipo de elemento
no DTD do banco de dados. Este problema ´e resolvido usando-se o algoritmo cl´assico de
Chu and Liu (tamb´em proposto independentemente por Edmonds), descrito em (KLEIN-
BERG; TARDOS, 2005). Uma quest˜ao ´e associar os pesos `as arestas do grafo; isto pode ser
4.4 Traduzindo Instˆancias 51
feito como segue: (1) arestas que n˜ao foram rotuladas com um tipo pelo mapeamento d a
adapta¸c˜ao de dados recebem um custo arbitrariamente alto; (2) arestas que foram rotu-
ladas com tipos pelo mapeamento da adapta¸c˜ao de dados recebem um custo proporcional
ao n´umero de tuplas em R para os quais foram associados o valor null. Fazendo isso,
garante-se que todos os n´os correspondentes aos tipos mapeados foram mantidos na ´arvore
geradora; ainda mais, ´e poss´ıvel garantir que os tipos de aparecem mais frequentemente
no documento fonte tem uma chance maior de serem mapeados ao banco de dados.
Uma implementa¸c˜ao direta do algoritmo acima ´e poss´ıvel em tempo de processamento
O(|E||V |), onde E e V s˜ao o conjunto de arestas e v´er tices no grafo. Pelo fato do tamanho
dos autˆomatos de Glush kov serem limitados polinomialmente ao tamanho das express˜oes
regulares, este algoritmo ´e eficiente na pr´atica.
52
5 Descoberta de
ˆ
Ancora
Neste cap´ıtulo o procedimento para computar o ancoramento da ´arvore XML s `a
´arvore XML t ´e apresentado (como brevemente descrito em Se¸c˜ao 3.3). Observe que, por
s ser uma ´arvore XML resultante do p rocesso de adapta¸c˜ao de dados, ambos s e t s˜ao
formatados de acordo com o DTD alvo D
T
.
Nossa semˆantica conservadora (Se¸c˜ao 3.4.2) imp˜oe que os ancoramentos produzidos
sejam completos e n˜ao amb´ıguos. Ou seja, ´e necess´ario encontrar um ancoramento que ´e
na verdade uma fun¸c˜ao A : s → t tal que se A(e) = e
′
, ent˜ao todas as seguintes condi¸c˜oes
s˜ao mantidas. Primeiro, e e e
′
devem ter tipos (r´otulos) idˆenticos. Segundo, e e e
′
devem
ser suficiente ment e similares. Diferentes no¸c˜oes d e similaridade s˜ao definidas para n´os
folhas e para n´os internos, como discutido abaixo. Terceiro, deve valer a propriedade de
que e ´e a raiz de s, ou os pais de e e e
′
ancoram um ao outro. Finalmente, n˜ao h´a e
′′
= e
′
em t que satisfa¸ca todos estes requisitos acima.
5.1 Algoritmo de Descoberta de
ˆ
Ancora
Nosso algoritmo funciona em dois passos. Primeiro, o algoritmo opera ancorando
de cima pra baixo todos os pares de n´os (e, e
′
) com o mesmo tipo. Quando os n´os
folhas s˜ao alcan¸cados, o sentido ´e invertido, onde os n´os ancorados inicialmente que n˜ao
exibem suficiente similaridade com nenhum n´o, ou s˜ao similares a mais d e um n´o, s˜ao
desancorados. A similaridade de dois n´os folhas depende somente de seus conte´udos,
enquanto a similaridade de dois n´os internos leva em considera¸c˜ao todos seus descendentes.
Al´em disso, se um n´o ´e similar a dois ou mais n´os, ele n˜ao ´e ancorado, para evitar
ambig ¨uidade.
´
E digno de notar que, enquanto a maioria do trabalho ´e feito durante a
fase de baixo pra cima, o primeiro passo reduz dramaticamente o n´umero de elementos
que precisam ser comparados, portanto melhorando grandemente o desempenho do nosso
m´etodo. De fato, um algoritmo puramente de cima para baixo come¸caria comparando
todos os n´os folhas em s com todos os n´os folhas em t, o que ´e desnecess´ario e caro.
5.1 Algoritmo de Descoberta de
ˆ
Ancora 53
Procedure: ancorar (e, C )
Input: n´o XML e, e o conjunto de n´os XML C
Output: anchoring A
A ← ∅; A
′
← ∅;
(⋆) Seja E o conjunto de elementos em C com tipo τ (e);
foreach a ∈ E do
if e ´e uma folha then
if distˆancia(e, a) < θ then
(≀) A ← {(e, a)}; break;
end
else
foreach c ∈ filhos(e) do
(†) A
′
← A
′
∪ ancorar(c,filhos(a));
end
(‡) if sim(e, a) > λ then
if A = ∅ then A ← A
′
∪ {(e, a)};
else return ∅
end
end
end
return A
Figura 15: Procedimento para descoberta de ˆancora.
De agora em diante, o tipo de um n´o e ´e denotado por τ(e). Para uma discuss˜ao mais
concreta, o algoritmo ser´a ilustrado utilizando o exemplo da Figura 8(a).
O algoritmo, mostrado na Figura 15, recebe como entrada e, o elemento XML que
queremos ancorar, e C , uma lista de elementos na ´arvore alvo t os quais s˜ao candidatos
para serem ancorados a e. Na pr´atica, C ´e usado para “focar” o processo de ancoramento,
tal que n´os evitamos tentar casar cada n´o em s com cada n´o em t. Na primeira chamada
ao algoritmo, e ´e a ´arvore de entrada s , e C o conjunto de todos os n´os na ´arvore alvo t,
permitindo portanto que s ancore a qualquer n´o em t.
O primeiro passo ao ancorar e ´e identificar aqueles elementos em C cujos tipos
(r´otulos) s˜ao iguais ao de e (⋆). Em nosso exemplo, inicialmente e seria o elemento
genre da Figura 8(a); portanto, n´os iteramos atrav´es de todos os elementos genre em t.
Dada a ´arvore de entrada e e uma ´arvore em t do mesmo tipo, denotada a no algoritmo,
o algoritmo progride de cima para baixo considerando apenas os descendentes de a (†).
Em nosso exemplo, isto se traduz no algoritmo tentando ancorar o elemento genre em s
a cada elemento genre em t, um de cada vez.
Note que durante a fase de cima pra baixo, leva-se em considera¸c˜ao apenas os tipos
(r´otulos) dos n´os a serem ancorados. Entretanto, quando um n´o folha ´e encontrado, o
5.2 Similaridade de N´os Internos 54
algoritmo ´e revertido para determinar a similaridade entre os n´os de baixo para cima.
Inicialmente, o algoritmo compara a similaridade de dois n´os folhas; se o seus conte´udos
s˜ao considerados suficientemente similares, eles s˜ao ancorados (≀). Dois n´os folhas e e a
s˜ao ditos similares se a distˆancia de edi¸c˜ao normalizada entre eles ´e abaixo de um limiar
θ. Em nossos experimentos foi usado θ = 0.3.
Na fase de baixo pra cima a similaridade entre os n´os internos ´e utilizada para decidir
se eles devem ser ancorados ou n˜ao. Neste est´agio, o algoritmo determina se o n´o corrente
e em s n˜ao ´e similar ao outro n´o em t ou se ´e similar a mais de um n´o em t, o que resultaria
num ancoramento amb´ıguo. Em ambos os casos, o n´o n˜ao ´e ancorado e o processo inteiro
de ancoramento de e ´e abortado (‡). Neste ponto, o algoritmo recua e tenta ancorar o pai
de e; observe que, porque o algoritmo est´a na fase de baixo pra cima, n˜ao haver´a outra
tentativa para ancorar e. Isto pode ser ilustrado pelo nosso exemplo na Figura 8(a): pelo
fato do elemento movie em s n˜ao ser similar ao movie em t, ele ´e mantido n˜ao ancorado,
tentando-se em seguida ancorar o elemento genre atrav´es de seus outros n´os descendentes,
em particular o atributo @name.
5.2 Similaridade de N´os Internos
O cerne do processo de descoberta de ˆancora ´e a fun¸c˜ao sim (e, a), que mede a si-
milaridade entre dois n´os internos e e a, considerando tamb´em a similaridade de seus
descendentes. Nossa medida de similaridade ´e baseada no DogmatiX (WEIS; NAUMANN,
2005), um arcabou¸co independente de dom´ınio para detec¸c˜ao de duplicatas. Intuitiva-
mente, a similaridade de duas sub-´arvores e e a depende do numero de folhas em e e a
que concordam uma com a outra, e o n´umero de de folhas em e e a que descordam uma
da outra.
Seja E
≈
o conjunto de todos os pares (l, l
′
) de n´os que concordam um com outro; ou
seja, l ´e um n´o folha em e, l
′
´e um n´o folha em a e A(l) = l
′
. (Note que quando dois n´os
internos est˜ao sendo ancorados, todos os n´os folhas descendentes deles que eram realmente
similares j´a foram ancorados.) Al´em disso, seja E
=
o conjunto de pares (l, l
′
) de n´os folhas
que descordam um do outro. E
=
´e constru´ıdo pareando cada n´o folha n˜ao ancorado em
e com um n´o escolhido n˜ao ancorado arbitrariamente escolhido de a, contanto que eles
sejam do mesmo tipo e nenhum n´o de e ou a pertence a mais de um par em E
=
.
5.2 Similaridade de N´os Internos 55
A similaridade entre e e a ´e definido como segue:
sim (e, a) =
w(E
≈
)
w(E
≈
) + w(E
=
)
,
onde w(E) mede qu˜ao seletivos s˜ao os valores dos pares em E. Intuitivamente, uma
concordˆancia (resp., discordˆancia) com n´os folhas contendo valores muito seletivos (ex., os
t´ıtulos de filmes) s˜ao melhores indicadores de similaridade que uma concordˆancia (resp.,
discordˆancia) de folhas que envolvem valores mais comuns (ex., nomes de est´udio). A
freq¨uˆencia inversa do documento ´e usada como medida de seletividade:
w(E) =
(e,e
′
)∈E
log
|T (e)|
cnt(e) + cnt(e
′
)
,
onde T (e) ´e o conjunto de elementos do tipo τ(e) no banco de dados alvo, e cnt(e) ´e o
n´umero de elementos de T (e), cujo valor textual ´e o mesmo de e.
56
6 Avalia¸c˜ao Experimental
Para avaliar nosso arcabou¸co de atualiza¸c˜ao livre de esquema, as opera¸c˜oes de atua-
liza¸c˜ao foram implementadas em um prot´otipo usando Java. Experimentos foram condu-
zidos sobre bancos de dados XML constru´ıdos usando dados publicamente dispon´ıveis na
Web de quatro dom´ınios: cinema, m´usica, livros e artigos cient´ıficos. A Figura 16(a) mos-
tra o tamanho e a URL de cada u m dos nossos bancos de dados de teste. Os tamanhos s˜ao
medidos em termos de “objetos de dados” representados nos bancos de dados, como filmes
e ´albuns, e os diferentes tipos (r´otulos) de elementos de acordo com o DTD. Os banco de
dados de livros e artigos s˜ao amostras aleat´orias do arquivo XML da DBLP, preservando-
se a estrutura original. O banco de dados de m´usica foi constru´ıdo convertendo-se para
XML o banco de dados relacional publicado pelo site MusicBrainz. O banco de dados
de filmes foi extra´ıdo do site do IMDB por um extrator e o resultado foi armazenado em
XML.
Os bancos de dados foram classificados em complexos e simples, de acordo com o
n´umero de tipos de elementos similares que eles apresentam. Intuitivamente, dois tipos
s˜ao considerados similares se os seus conte´udos se intercalam. Por exemplo, no banco
de dados de cinema, valores de elementos ator, diretor e escritor s˜ao dificilmente
discriminados at´e mesmo por humanos. Por isso, este banco de dados foi considerado
complexo. Outros exemplos de elementos similares s˜ao d esc ri¸c~ao e s ino pse. Outro
banco de dados complexo ´e o de m´usica, por causa dos elementos similares artista,
´album e trilha. Os bancos de dados restantes foram considerados simples porque n˜ao
apresentam elementos similares.
Em termos gerais, os experimentos simulam a atualiza¸c˜ao dos banco de dados de
teste usando dados provenientes de um RSS Feed ou de dados extra´ıdos de p´aginas Web
usando um extrator autom´atico. Trˆes conjuntos de objetos foram gerados para cada
dom´ınio. O conjunto Existente cont´em 10 objetos que j´a existiam no banco de dados
correspondente. O conjunto Novo ´e formado por 10 objetos que n˜ao existem no banco de
dados correspondente. Finalmente, o conjunto Uni˜ao, como o nome sugere, ´e a uni˜ao dos
6.1 Adapta¸c˜ao de Dados 57
Banco de dados Objetos Tipos Site Complexidade
Cinema 8,914 19 http://imdb.com Complexo
M´usica
14,966 4 http://musicbrainz.org/doc/Database Complexo
Livros
1,211 19 http://dblp.uni-trier.de/xml/ Simples
Artigos
8,000 13 http://dblp.uni-trier.de/xml/ Simples
(a) Bancos de dados alvos.
Documentos Tipos Usados/Total Site Formato Original
Cinema 10/77 http://movies.yahoo.com HTML
M´usica
4/40 http://www.pandora.com RSS
Livros
4/5 http://books.google.com HTML
Artigos
4/6 http://www.sigmod.org/record/xml/ XML
(b) Documentos fontes.
Figura 16: Bancos de dados e documentos usados nos experimentos.
outros dois conjuntos. A Figura 16(b) apresenta algumas caracter´ısticas dos documentos
fontes usados. Dentre elas, destacamos que a coluna “Tipos Usados/Total” corresponde
a fra¸c˜ao dos tipos usados nas atualiza¸c˜oes pelo total de tipos presentes nos documentos
fontes.
6.1 Adapta¸c˜ao de Dados
Antes de apresentarmos os resultados experimentais sobre os conjuntos de dados usa-
dos para avalia¸c˜ao do nosso arcabou¸co de atualiza¸c˜ao (Novo, Existente e Uni˜ao), ava-
liaremos nosso processo de adapta¸c˜ao de dados de forma independente. O objetivo dos
experimentos a seguir ´e avaliar a qualidade do mapeamento produzido pelo m´etodo. Neste
contexto, precis˜ao e revoca¸c˜ao s˜ao calculados como segue. Seja M
R
e M
F
o conjunto de
pares de mapeamento obtidos respectivamente por um especialista e pelo nosso m´etodo
de adapta¸c˜ao de dados. Os valores de precis˜ao (P ), revoca¸c˜ao (R) e medida-f (F ) s˜ao
calculados respectivamente como: P =
||M
R
∩M
F
||
||M
F
||
, R =
||M
R
∩M
F
||
||M
R
||
e F =
2×P ×R
P +R
.
Nos experimentos a seguir a acuidade dos mapeamentos ´e medida usando a medida-f,
que combina precis˜ao e revoca¸c˜ao e ´e comumente usada nos experimentos de Recupera¸c˜ao
de Informa¸c˜ao (BAEZA-YATES; RIBEIRO-NETO, 1999). Por exemplo, considere a plotagem
para cinema na Figura 6.1, cuja medida-f ´e 0,94 (0,97 de p recis˜ao e 0,92 de revoca¸c˜ao).
Isto significa que, na m´edia, nosso m´etodo escolheu menos de um p ar equivocadamente
(falso positivo) e falhou em escolher menos de um par correto (falso negativo) para compor
o mapeamento final, considerando 50 rodadas executadas neste experimento.
A efetividade da nossa abordagem de adapta¸c˜ao de dados foi estudada com as di-
6.1 Adapta¸c˜ao de Dados 58
Figura 17: Acuidade de medidas de similaridades individuais entre os dom´ınios.
ferentes medidas de similaridades discutidas no Cap´ıtulo 4. Para facilitar a leitura, os
escores F , C, K, V e L da Figura 13 s˜ao chamados de combinado, conte´udo, palavras-
chave, valores e r´otulos nesta se¸c˜ao. Observe que o escore K (palavras-chave) tamb´em ´e
considerado para similaridade num´erica, ao contr´ario de V (valores).
Efetividade do escore combinado da adapta¸c˜ao de dados
A Figura 6.1 mostra a acuidade m´edia do mapeamento de esquemas para diferentes me-
didas de similaridade. Para cada dom´ınio, foram usad os 50 documentos fontes com 10
objetos de dados diferentes em cada um, e nosso m´etodo de adapta¸c˜ao de dados foi usado
com diferentes medidas de similaridade. Como o gr´afico mostra, o m´etodo combinado
que propomos (Se¸c˜ao 4.2) supera todos as medidas de similaridade individuais (p alavras-
chave, valores e r´otulos); isto ´e particularmente evidente para os dom´ınios mais complexos
em nossos testes: cinema e m´usica.
´
E importante notar que a similaridade de conte´udo,
que ´e uma combina¸c˜ao os escores de palavras-chave e valores, obteve resultados muito
pr´oximos ao escore combinado. Isto mostra que nosso m´etodo ´e efetivo mesmo quando
os esquemas a serem mapeados s˜ao completamente dissimilares (em termos de r´otulos de
elementos).
6.1 Adapta¸c˜ao de Dados 59
0
0.2
0.4
0.6
0.8
1
302520151051
Medida−f
Tamanho do documento de entrada
combinano
conteúdo
palavras−chave
valores
rótulos
Figura 18: Impacto do tamanho do documento de entrada.
Impacto do tamanho do documento de entrada
Apenas o banco de dados de cinema foi usado neste experimento, devido o n´umero elevado
de objetos necess´ario para realizar os testes. Entretanto, espera-se que os resultados rela-
tivos sejam mantidos para os outros bancos de dados. A Figura 18 compara a efetividade
no m´etodo de adapta¸c˜ao d e dados com tamanhos variados do documento de entrada; cada
plotagem mostra a acuidade m´edia de 20 rodadas, cada uma com uma amostra diferente
de objetos nos documentos fontes. Observe que novamente o m´etodo combinado supera os
outros, particularmente para os documentos menores, ou seja, quando atualizando poucos
dados. A queda na qualidade da ab ord agem baseada em r´otulos ´e devido ao fato que mais
elementos op cionais est˜ao presentes em amostras maiores.
Impacto no tamanho do banco de dados
A Figura 19 mostra como os escores do m´etodo de similaridade combinado variam em
fun¸c˜ao do n´umero de objetos de dados no banco de dados. Cada plotagem mostra a acui-
dade m´edia de 5 rodadas, cada uma com um subconjunto diferente do bancos de dados da
Tabela 16(a). Em cada rodada foram usados 20 documentos de entrada com 10 objetos
cada. Observe que o m´etodo de adapta¸c˜ao de dados se comporta muito bem independente
do tamanho do banco de dados para os d om´ınios mais simples (artigos e livros) dos nossos
testes, que s˜ao predominantes na Web. Para os bancos de dados mais complexos, como
esperado, a acuidade do m´etodo melhora quando mais objetos de dados s˜ao mantidos no
6.1 Adapta¸c˜ao de Dados 60
0.6
0.65
0.7
0.75
0.8
0.85
0.9
0.95
1
100075050025050
Medida−f
Tamanho do banco de dados
Artigos
Livros
Cinema
Música
Figura 19: Impacto do tamanho do banco de dados.
banco de dados.
0
0.2
0.4
0.6
0.8
1
20151050
Medida−f
Número de atributos indesejados
combinado
conteúdo
palavras−chave
valores
rótulos
Figura 20: Tolerˆancia a ru´ıdo.
Tolerˆancia a ru´ıdo
A Figura 20 mostra o impacto que elementos indesejados (ou seja, que n˜ao tem cor-
respondentes no banco de dados) nos documentos tˆem sobre a acuidade do nosso m´etodo,
usando o banco de dados de cinema. Cada plotagem ´e a m´ed ia de 20 rodadas, cada uma
com 10 filmes. Inicialmente apenas elementos cujos tipos (r´otulos na nota¸c˜ao do DTD)
tem um tipo correspondente no banco de dados, depois outros tipos de elementos que
n˜ao tem um tipo corresp ondente no banco de dados s˜ao progressivamente adicionados ao
6.1 Adapta¸c˜ao de Dados 61
documento de entrada com dados reais da fonte Web. Como se pode ver, a similaridade
combinada sofre a menor queda relativa de acuidade em todas as medidas, remanescendo
quase perfeita mesmo quando apenas 1/3 dos tipos de elementos no documento de en-
trada tem um tipo correspondente no banco de dados, como mostra a Tabela 16(b),
onde apenas 10 tipos s˜ao realmente usados para atualizar o banco de dados de filmes.
´
E
bastante prov´avel que este comportamento se repita para o banco de dados de m´usica,
onde alcan¸camos bons resultados mesmo com apenas quatro tipos u sados na atualiza¸c˜ao
contra 40 no total. N˜ao ´e poss´ıvel repetir este experimentos para os dom´ınios de livros e
artigos, uma vez que os documentos fonte n˜ao apresentam quantidade suficiente de tipos
indesejados.
Avalia¸c˜ao do arcabou¸co de atualiza¸c˜ao
A seguir s˜ao apresentados os resultados do processo de adapta¸c˜ao de dados sobre os
12 conjuntos de dados usados para avalia¸c˜ao do nosso arcabou¸co de atu aliza¸c˜ao, a saber,
Novo, Existente e Uni˜ao, de quatro dom´ınios. A Tabela 1 apresenta os resultados do
processo sobre os conjuntos em an´alise. Nosso m´etodo funcionou quase perfeitamente no
conjunto Existente, o que era esperando uma vez que h´a uma grande sobreposi¸c˜ao entre os
dados dos objetos deste conjunto com o banco de dados. O m´etodo tamb´em atingiu bons
resultados para o conjunto Novo, a despeito da pequena sobreposi¸c˜ao de dados esperada
neste caso, que teve um imp acto nos valores de revoca¸c˜ao para os dom´ınios de m´usica e
artigos. Os resultados do conjunto Uni˜ao s˜ao t˜ao bons quanto os resultados obtidos para
o conjunto Existente. Na verdade, o ´unico resultado n˜ao perfeito foi o valor de precis˜ao
para o banco de dados de filmes (0, 91), no qual apenas um, entre 11 mapeamentos, foram
incorretamente gerados. Isto significa que ocorrˆencia de novos objetos n˜ao compromete a
qualidade geral do nosso m´eto do de adapta¸c˜ao de dados, como esperamos que aconte¸ca
em situa¸c˜oes pr´aticas.
Para o conjunto Uni˜ao, a adapta¸c˜ao de dados resulta em 80 ´arvores XML reformatadas
(20 para cada dom´ınio), cada um contendo objetos de dados. Isto corresponde de fato a
mais de 1.900 elementos. Observamos que neste experimento, apenas dois elementos (ou
0, 11% do total) foram incorretamente gerados. Em ambos os casos, o erro foi devido ao
´unico par mapeado incorretamente como citado acima. N´os usamos estas 80 ´arvores nos
experimentos que seguem, os quais lidam com a acuidade da descobertade ˆancora.
6.2 Descoberta de
ˆ
Ancora 62
Existente Novo Uni˜ao
Bancos de dados
P R P R P R
Cinema 0,9 1 1 1 0,91 1
M´usica
1 1 1 0,75 1 1
Livros
1 1 1 1 1 1
Artigos
1 1 1 0,80 1 1
Tabela 1: Qualidade da adapta¸c˜ao de dados.
6.2 Descoberta de
ˆ
Ancora
Avaliamos a qualidade do nosso algoritmo de descoberta de ˆancora atrav´es da com-
para¸c˜ao de seus resultados com ancoramentos manualmente gerados, os quais s˜ao consi-
derados como corretos. Os resultados dos experimentos s˜ao dados em termos de precis˜ao,
revo ca¸c˜ao e medida-f, definidos como segue. Seja A
R
um ancoramento perfeito e A
F
o ancoramento obtido pelo nosso m´etodo. Os valores de precis˜ao (P ), revoca¸c˜ao (R),
e medida-f (F ) s˜ao respectivamente calculados como: P =
||A
R
∩A
F
||
||A
F
||
, R =
||A
R
∩A
F
||
||A
R
||
e
F =
2×P ×F
P +F
.
Observe que para estas m´etricas serem ´uteis, A
R
e A
F
devem conter todos os elementos
da ´arvore de entrada, mesmo que alguns deles n˜ao sejam ancorados. Para lidar com essa
situa¸c˜ao, os elementos n˜ao ancorados em um ancoramento s˜ao representados como pares
(e, null), onde e ´e um elemento n˜ao ancorado.
A Figura 21 mostra a qualidade da descob erta de ˆancora expressada usando a m´edia
da medida-f para o limiar de ancoramento λ variando de 0, 3 a 1. Note que a maior
acuidade ´e atingida para λ entre 0, 55 e 0, 6 para todos os dom´ınios, mostrando que nosso
m´etodo de descoberta de ˆancora ´e geral e est´avel o suficiente para usar o mesmo limiar
para dom´ınios distintos. De agora em diante, usa-se λ = 0, 6 para todos os experimentos.
A Tabela 2 apresenta os resultados da avalia¸c˜ao de qualidade da descoberta de ˆancora,
tamb´em usando medida-f. A coluna “Todos” considera todos os elementos, enquanto
as colunas “Simples” e “Complexos” consideram apenas elementos simples e complexos,
respectivamente. O m´etodo de descob erta de ˆancora apresentou um desempenho excelente
em todos os quatro dom´ınios. Observe que eventuais erros em ancorar elementos simples
n˜ao comprometem o ancoramento de n´os complexos, que s˜ao usualmente mais dif´ıceis de
se lidar.
6.3 Qualidade das Opera¸c˜oes Livre de Esquema 63
0.6
0.65
0.7
0.75
0.8
0.85
0.9
0.95
1
0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Medida−f
Limiar de ancoramento
Cinema
Música
Livros
Artigos
Figura 21: Medida-f m´edia da d escoberta de ˆancora para v´arios valores como limiar de
ancoramento λ.
Todos Simples Complexos
Cinema 0,96 0,97 0,96
M´usica
0,98 0,98 0,98
Livros
0,95 0,94 0,95
Artigos
0,95 0,92 0,95
Tabela 2: Qualidade do ancoramento para elementos simples e complexos.
6.3 Qualidade das Opera¸c˜oes Livre de Esquema
Apresentamos agora os resultados da avalia¸c˜ao de qualidade do nosso arcabou¸co em
produzir atualiza¸c˜oes corretas em um banco de dados alvo D, conforme a inten¸c˜ao do
usu´ario que formulou a opera¸c˜ao de atualiza¸c˜ao livre de esquema.
Para isto, considere uma instˆancia I de D que reflete corretamente todas as edi¸c˜oes
intencionadas envolvidas em alguma opera¸c˜ao de atualiza¸c˜ao. Agora, considere outra
instˆancia P que ´e resultado de aplicar as atualiza¸c˜ao sugeridas pelo nosso arcabou¸co. A
qualidade do nosso arcabou¸co ´e medida comparando-se qu˜ao distinto P ´e de I. Nossa
m´etrica ´e o esfor¸co de reparar o banco de dados, definido como o n´umero de edi¸c˜oes
(inser¸c˜oes e remo¸c˜oes) necess´arios para converter P em I. Para este prop´osito, adaptamos
uma m´etrica `as vezes utilizada para avaliar m´etodos de casamento de esquema (MELNIK;
GARCIA-MOLINA; RAHM, 2002). Esta m´etrica, chamada aqui de acuidade da atualiza¸c˜ao,
´e detalhada abaixo.
6.3 Qualidade das Opera¸c˜oes Livre de Esquema 64
Acuidade da Atualiza¸c˜ao
Sejam U
P
e U
I
conjuntos de edi¸c˜oes necess´arias para converter D em P e D em I, respec-
tivamente. Portanto, o n´umero de edi¸c˜oes corretas ´e c = ||U
P
∩ U
I
||. A diferen¸ca (n − c),
onde n = ||U
P
||, denota o n´umero de edi¸c˜oes aplicados a P que precisam ser desfeitos. De
forma similar, (m − c), onde m = ||U
I
||, ´e o n´umero de falso negativos, ou seja, edi¸c˜oes
corretas que n˜ao foram aplicadas pelo nosso m´etodos. Por simplicidade, assume-se que
fazer ou desfazer uma edi¸c˜ao requer o mesmo esfor¸co, e que a verifica¸c˜ao de um elemento
correto n˜ao tem custo. Se um usu´ario realiza cada edi¸c˜ao em U
I
manualmente, ent˜ao m
edi¸c˜oes s˜ao necess´arias. Portanto, o esfor¸co do usu´ario ´e medido como a por¸c˜ao da “lim-
peza” manual necess´aria depois de aplicar a opera¸c˜ao de atualiza¸c˜ao livre de esquema em
compara¸c˜ao a atualiza¸c˜ao completamente manual, como segue:
l =
(n − c) + (m − c)
m
A economia de esfor¸co obtida usando-se uma opera¸c˜ao de atualiza¸c˜ao livre de esquema
´e estimada atrav´es da acuidade da atualiza¸c˜ao, definida como 1 − l. Numa atualiza¸c˜ao
perfeita, n = m = c, resultando em acuidade igual 1. Note que c/n e c/m correspondem
a precis˜ao e revoca¸c˜ao. Portanto, a acuidade da atualiza¸c˜ao pode ser expressa em fun¸c˜ao
da precis˜ao e revoca¸c˜ao como segue:
Acuidade = 1 −
(n − c) + (m − c)
m
=
c
m
2 −
n
c
= Revoca¸c˜ao
2 −
1
Precis˜ao
Na defini¸c˜ao acima, a no¸c˜ao de acuidade faz sentido apenas se a precis˜ao n ˜ao ´e menor
que 0, 5, isto ´e, pelo menos metade das edi¸c˜oes sugeridas pelo nosso m´etodo s˜ao corre-
tas. Caso contr´ario, a acuidade ´e negativa. De fato, se mais da metade das edi¸c˜oes s˜ao
incorretas, levaria mais esfor¸co para o usu´ario desfazˆe-las e inserir os elementos ausentes
que fazer as edi¸c˜oes manualmente desde o come¸co. Como esperado, a melhor acuidade 1
´e obtida quando tanto a precis˜ao e a revoca¸c˜ao s˜ao iguais a 1.
Qualidade das opera¸c˜oes livres de esquema
A qualidade das opera¸c˜oes livre de esquema foi avaliada levando-se em considera¸c˜ao
poss´ıveis erros propagados da adapta¸c˜ao de dados e descoberta de ˆancora para a acuidade
final da qualidade de atualiza¸c˜ao. As ´arvores de entrada foram agrupadas de acordo com
6.3 Qualidade das Opera¸c˜oes Livre de Esquema 65
os objetos descr itos por elas (novos ou existentes) para melhor entender o comportamento
de cada opera¸c˜ao de atualiza¸c˜ao em face de cada um desses casos.
A Tabela 3 mostra os valores de precis˜ao (P), revoca¸c˜ao (R) e acuidade de atualiza¸c˜ao
(A) para este experimento. Observe que as opera¸c˜oes de inser¸c˜ao e remo¸c˜ao foram quase
perfeitas, atingindo mais de 0, 98 de precis˜ao e revoca¸c˜ao. A opera¸c˜ao de fus˜ao tamb´em
alcan¸cou resultados muito bons, especialmente para novos objetos. Entretanto, a opera¸c˜ao
de atualiza¸c˜ao apresentou uma acuidade muito baixa, afetando os resultado da opera¸c˜ao de
fus˜ao sobre objetos existentes. Estes resultados inexpressivos da opera¸c˜ao de atualiza¸c˜ao
foram causados predominantemente pelo ancoramento incorreto de folhas. Isto aconteceu,
por exemplo, pois os anos “2004” e “2005” foram considerados similares devido a sua
baixa distˆancia de edi¸c˜ao. Entretanto, n´os acreditamos que uma opera¸c˜ao de atualiza¸c˜ao
dificilmente danifica o banco d e dados por duas raz˜oes: (1) se um elemento a ser atualizado
´e ancorado equivo cadamente, nada ´e realizado; e (2) se nosso m´etodo falha em ancorar
um elemento, valores muito similares s˜ao substitu´ıdos um pelo outro. Por exemplo, em
nossos experimentos a opera¸c˜ao de atualiza¸c˜ao substituiu incorretamente “United States
of America” por “United States” diversas vezes. Outro fato que poderia explicar estes
resultados ´e o baixo n´umero de elementos a serem atualizados: menos de 20.
Existentes Novos
Opera¸c˜oes
P R A P R A
Inser¸c˜ao 0,99 1 0,99 1 1 1
Atualiza¸c˜ao
0,55 0,72 0,11 – – –
Fus˜ao
0,88 0,9 0,76 1 1 1
Remo¸c˜ao
0,98 0,98 0,95 – – –
Tabela 3: Acuidade das op era¸c˜oes de atualiza¸c˜ao.
Bancos de dados Inser¸c˜ao Atualiza¸c˜ao Fus˜ao Remo¸c˜ao
Cinema – 0,99 – 1
M´usica
0,95 1 – 1
Livros
0,89 1 0,8 1
Artigos
0,83 1 1 1
Tabela 4: Corre¸c˜ao da opera¸c˜ao de atualiza¸c˜ao quando o banco de dados deveria perma-
necer inalterado.
Observe que opera¸c˜oes de atualiza¸c˜ao e de remo¸c˜ao devem manter o banco de da-
dos inalterados quando lidando com novos objetos. Portanto, n˜ao ´e poss´ıvel medir a sua
corre¸c˜ao atrav´es das m´etricas usadas neste experimento (como indicado por tra¸cos na
Tabela 3). Al´em destes, houveram outros 64 casos (totalizado 144 de 320) em nossos
experimentos onde o banco de dados deveria tamb´em ser mantido inalterado. A maioria
6.3 Qualidade das Opera¸c˜oes Livre de Esquema 66
desses casos foi devido a opera¸c˜ao de inser¸c˜ao, atualiza¸c˜ao ou fus˜ao sobre somente elemen-
tos ancorados na ´arvore de entrada. N´os medimos a corre¸c˜ao nessas situa¸c˜oes atrav´es da
por¸c˜ao d e elementos na ´arvore de entrada que n˜ao foram usados para atualizar o banco
de dados. Mais precisamente, seja p o n´umero de edi¸c˜oes propostas e n o n´umero de ele-
mentos na ´arvore de entrada; n´os definimos a corre¸c˜ao da opera¸c˜ao de atualiza¸c˜ao como
(n−p)/n. A Tabela 4 mostra os resultados deste experimento para todas as opera¸c˜oes em
cada dom´ınio. N˜ao houve nenhum caso em estudo com rela¸c˜ao as opera¸c˜oes de inser¸c˜ao
e fus˜ao em Cinema, e fus˜ao em M´usica (como indicado por tra¸cos na Tabela 4). Observe
que o comportamento das opera¸c˜oes de atualiza¸c˜ao e remo¸c˜ao foi muito pr´oximo a per-
fei¸c˜ao para todos os dom´ınios. Apesar das opera¸c˜oes de inser¸c˜ao e fus˜ao apresentarem
corre¸c˜ao variando de 0.8 a 0.95, um erro dessas opera¸c˜oes, no pior caso, significa apenas
a inser¸c˜ao de dados redundantes.
67
7 Conclus˜ao e Trabalhos Futuros
Este trabalho propˆos um novo arcabou¸co livre de esquema para atualizar documen-
tos XML. Este arcabou¸co ´e baseado em primitivas simples por´em poderosas nas quais o
usu´ario simplesmente indica a opera¸c˜ao desejada e indica os n´os envolvidos nela. Como
tal, nosso arcabou¸co ´e muito mais adequado para usu´ario casuais e n˜ao especialistas que os
paradigmas atuais baseados em XQuery. Para ilustrar como essas primitivas poderiam ser
usadas na pr´atica, propomos uma linguagem de atualiza¸c˜ao simples e intuitiva para espe-
cificar as opera¸c˜oes de atualiza¸c˜ao envolvendo objetos de dados de entrada e um banco de
dados alvo com estruturas possivelmente diferentes. O objetivo principal da linguagem ´e
realizar opera¸c˜oes sofisticadas sem requerer que o usu´ario saiba detalhes dos esquemas dos
dados de entrada ou do banco de dados envolvidos, e especialmente sem necessariamente
saber o local espec´ıfico no banco de dados onde a opera¸c˜ao de atualiza¸c˜ao deveria ocorrer.
Uma semˆantica conservadora foi discutida para esta linguagem, na qual atualiza¸c˜oes que
introduzem redundˆancia s˜ao evitadas. O processo de tradu¸c˜ao de instˆancias XML de um
DTD para outro foi discutido em detalhes, de uma forma que sempre ´e gerado conte´udo
v´alido m esmo quando lidamos com valores ausentes. Discutiu-se tamb´em o algoritmo
de descoberta de ˆancora para identificar n´os equivalentes nos document os XML fonte e
alvo, de onde o local preciso das atualiza¸c˜oes pode ser derivado. Nosso arcabou¸co ´e ´util
por trˆes raz˜oes: (1) ele ´e aplic´avel `a dados reais da Web, (2) pode ser implementado de
forma simples (3) retorna comandos de atualiza¸c˜ao que podem ser facilmente traduzidos
para programas de atualiza¸c˜ao em outras linguagens, ou implementados diretamente num
sistema de armazenamento nativo de XML. Finalmente, resultados experimentais da im-
plementa¸c˜ao de um prot´otipo indicaram o grande potencial dos nossos m´etodos em dados
reais da Web de diferentes dom´ınios.
Dada a importˆancia e onipresen¸ca de XML, prover ferramentas de gerˆen cia de da-
dos eficientes e acess´ıveis que podem ser usadas por usu´arios n˜ao especialistas ´e uma
promissora ´area de pesquisa. Enquanto os problemas relacionados `a consultas “livres de
esquema” em XML tem sido investigados por muitos, apenas arranhamos a superf´ıcie dos
7 Conclus˜ao e Trabalhos Futuros 68
problemas de troca de dados e atualiza¸c˜oes autom´aticas em XML. Esses problemas n˜ao
tem sido satisfatoriamente estudados na literatura; isto ´e verdade tamb´em no caso de
dados relacionais. Nosso trabalhos futuros incluem implementar completamente nossos
m´etodos num sistema real em produ¸c˜ao, juntamente com consultas livres de esquemas
tamb´em. Tamb´em identificamos a necessidade de desenvolver t´ecnicas mais robustas e
escal´aveis para lidar com dados XML que oferecem a flexibilidade do paradigma “livre de
esquema”. Al´em d isso, outras semˆanticas para as opera¸c˜oes de atualiza¸c˜ao precisam ser
estudadas a fim de melhorar os resultados da atualiza¸c˜ao. Em particular, isto pode ser
feito definindo-se em quais cen´arios cada uma deve ser aplicada.
Outro trabalho futuro ´e adaptar nosso arcabou¸co para receber como entrada documen-
tos com pouca ou nenhuma estrutura, como p´aginas da Web e texto plano (e-mail, classi-
ficados) ou semi-estruturado (curr´ıculos, endere¸cos)’. Isto pode ser feito desenvolvendo-se
novas t´ecnicas de adapta¸c˜ao de dados baseadas em ferramentas de extra¸c˜ao de dados.
´
E
poss´ıvel ainda desenvolver sistemas de reconhecimento de linguagem natural para atua-
liza¸c˜ao de bancos de dados XML baseados em nosso arcabou¸co. Neste caso, o desafio ´e
reconhecer no texto qual a opera¸c˜ao (inser¸c˜ao, remo¸c˜ao) e os dados envolvidos na atua-
liza¸c˜ao.
69
Ref erˆencias
ABITEBOUL, S. et al. The lowell database research self-assessment. Comm. ACM,
v. 48, n. 5, p. 111–118, 2005.
AGRAWAL, S.; CHAUDHURI, S.; DAS, G. DBXplorer: A system for keyword-based
search over relational databases. In: Proceedings of the International Conference on Data
Engineering. [S.l.: s.n.], 2002. p. 5–16.
ARENAS, M.; LIBKIN, L. XML data exchange: Consistency and query answering. In:
Proceedings of the Symposium on Principles of Database Systems. New York, NY, USA:
ACM Press, 2005. p. 13–24. ISBN 1-59593-062-0.
BAEZA-YATES, R.; RIBEIRO-NETO, B. Modern Information Retrieval. [S.l.]: Addison
Wesley, 1999.
BALMIN, A.; PAPAKONSTANTINOU, Y.; VIANU, V. Incremental validation of XML
documents. Transactions on Database S ystems, v. 29, n. 4, p. 710–751, 2004.
BARBOSA, D.; L EIGHTON, G.; SMITH, A. Efficient incremental validation of XML
documents after composite updates. In: Proceedings of the International XML Database
Symposium. [S.l.: s.n.], 2006. p. 107–121.
BARBOSA, D. et al. Efficient incremental validation of XML documents. In: Proceedings
of the International Conference on Data Engineering. [S.l.: s.n.], 2004. p. 671–682.
BRAUER, M. et al. Open Document Format for Office Applications v1.0. [S.l.], 2005.
BRAY, T. et al. Extensible Markup Language (XML) 1.0. 4th. ed. [S.l.], 2006.
BR
¨
UGGEMANN-KLEIN, A.; WOOD, D. One-unambiguous regular languages. Inf.
Comput., v. 140, n. 2, p. 229–253, 1998.
CLARK, J.; DEROSE, S. XML Path Language (XPath) — Version 1.0. [S.l.], 1999.
COHEN, S. et al. XSEarch: A semantic search engine for xml. In: Proceedings of the
International Conference on Very Large Databases. [S.l.: s.n.], 2003. p. 45–56.
COHEN, W. W.; HIRSH, H. Joins that generalize: Text classification using whirl. In:
Proceedings of the International Conference on Knowledge Discovery and Data M ini ng.
[S.l.: s.n.], 1998. p. 169–173.
COHEN, W. W.; RAVIKUMAR, P.; FIENBERG, S. E. A comparison of string distance
metrics for name-matching tasks. In: Proceedings of IJCAI Workshop on Inform ation
Integration on the Web. [S.l.: s.n.], 2003. p. 73–78.
Referˆencias 70
DITTRICH, J. J.-P.; SALLES, M. A. V. iDM: A unified and versatile data model for
personal dataspace management. In: Proceedings of the International Conference on
Very Large Databases. [S.l.: s.n.], 2006. p. 367–378.
FAGIN, R. et al. Data exchange: Semantics and query answering. In: CALVANESE, D.;
LENZERINI, M.; MOTWANI, R. (Ed.). Proceedings on the International Conference on
Database Theory. Berlin, Germany: [s.n.], 2003. (Lecture Notes in Computer Science,
2572), p. 207–204.
FUXMAN, A. et al. Peer data exchange. ACM Trans. Database Syst., ACM Press, New
York, NY, USA, v. 31, n. 4, p. 1454–1498, 2006. ISSN 0362-5915.
GALHARDAS, H. et al. Declarative data cleaning: Lan guage, model, and algorithms.
In: Proceedings of the International Conference on Very Large Databases. [S.l.: s.n.],
2001. p. 371–380.
GAREY, M. R.; JOHNSON, D. S. Computers and Intractability: A Guide to the Theory
of NP-Completeness. [S.l.]: W. H. Freeman, 1979.
GLUSHKOV, V. M. The abstract theory of aautomata. Russian Mathematic Surveys,
v. 16, n. 5, p. 1–53, 1961.
GRAVANO, L. et al. Approximate string joins in a database (almost) for free. In:
Proceedings of the International Conference on Very Large Databases. [S.l.: s.n.], 2001.
p. 491–500.
GUHA, S. et al. Approximate XML joins. In: Proceedings of the SIGMOD Conference
on Management of Data. [S.l.: s.n.], 2002. p. 287–298.
GUO, L. et al. XRANK: ranked keyword search over xml documents. In: Proceedings of
the SIGMOD Conference on Management of Data. [S.l.: s.n.], 2003. p. 16–27.
KLEINBERG, J.; TARDOS
´
Eva. Algorithm Desing. [S.l.]: Addison Wesley, 2005.
LAUX, A.; MARTIN, L. XUpdate. [S.l.], 2000.
LI, Y.; YU, C.; JAGADISH, H. V. Schema-free xquery. In: Proceedings of the
International Conference on Very Large Databases. [S.l.: s.n.], 2004. p. 72–83.
MELNIK, S.; GARCIA-MOLINA, H.; RAHM, E. Similarity floo ding: A versatile graph
matching algorithm and its application to schema matching. In: Proceedings of the
International Conference on Data Engineering. [S.l.: s.n.], 2002. p. 117 – 128.
MESQUITA, F. et al. LABRADOR: Efficiently publishing relational databases on the
web by using keyword-based query interfaces. Inf. Process. Manage., Pergamon Press,
Inc., v. 43, n. 4, p. 983–1004, 2007. ISSN 0306-4573.
MICROSOFT CORPORATION. Office 2003 XML Reference Schema. [S.l.], 2006.
Dispon´ıvel em: <http://www.microsoft.com/office/xml>.
PEARL, J. Probabilistic Reasoning in Intelligent Systems. [S.l.]: Morgan Kauffmann,
1988.
Referˆencias 71
POPA, L. et al. Translating web data. In: Proceedings of the International Conference
on Very Large Data Bases. [S.l.: s.n.], 2002. p. 598–609.
RAHM, E.; BERNSTEIN, P. A. A survey of approaches to automatic schema matching.
The VLDB Journal, v. 10, n. 4, p. 334–350, 2001.
ROBIE, J.; FLORESCU, D.; CHAMBERLIN, D. XQuery Update Facility. [S.l.], 2006.
SCHMIDT, A.; KERSTEN, M. L.; WINDHOUWER, M. Querying XML documents
made easy: Nearest concept queries. In: Proceedings of the International Conference on
Data Engineering. [S.l.: s.n.], 2001. p. 321–329.
SHANMUGASUNDARAM, J. et al. Efficiently publishing relational data as XML
documents. The VLDB Journal, v. 10, n. 2-3, p. 133–154, 2001.
WEIS, M.; NAUMANN, F. DogmatiX tracks down duplicates in XML. In: Proceedings
of the SIGMOD Conference on Management of Data. [S.l.: s.n.], 2005. p. 431–442.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
