Filipe de Sá Mesquita
Atualizações Livres de Esquema em
Bancos de Dados XML
Manaus, Amazonas
05 de Maio de 2008
Filipe de Sá Mesquita
Atualizações Livres de Esquema em
Bancos de Dados XML
Dissertação de mestrado apresentada ao
Curso de Mestrado em Informática da Universidade Federal do Amazonas, como requisito para obtenção do tı́tulo de Mestre em
Informática
Orientador:
Professor Dr. Altigran Soares da Silva
Universidade Federal do Amazonas
Manaus, Amazonas
05 de Maio de 2008
Dissertação de Mestrado sob o tı́tulo “Atualizações Livres de Esquema em Bancos de
Dados XML”, defendida por Filipe de Sá Mesquita e aprovada em 05 de Maio de 2008,
em Manaus, Estado do Amazonas, pela banca examinadora constituı́da pelos doutores:
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. João Marcos Bastos Cavalcanti
Universidade Federal do Amazonas
Dedicatória
Aos meus pais, a quem tenho profunda gratidão e admiração.
Agradecimentos
Agradeço a Deus por me dar vida e propósito. Aos meus pais, José João e Lucı́lia,
e às minhas irmãs, Priscila e Débora, por me suportarem todos esses anos. À minha
namorada e futura esposa, Camila Picanço, por me amar do jeito que sou.
Resumo
Este trabalho considera o problema de atualizar dados em XML no contexto de
usuários casuais e não especialistas trocando dados (por exemplo, usando serviços de compartilhamentos de dados na Web) com limitado ou nenhum conhecimento sobre esquemas.
Um novo paradigma é introduzido para atualizar dados XML baseado em operações de
atualização simples porém poderosas. Em particular, propomos métodos efetivos para
traduzir dados de uma representação para outra e também determinar os locais apropriados para efetuar as atualizações sem violar o esquema do banco de dados. Para aplicar
nossos métodos de forma concreta, discute-se uma linguagem de atualização intuitiva que
libera o usuário de conhecimentos especı́ficos sobre esquemas e que pode ser implementada com o nosso arcabouço. Ainda mais, nossa proposta é mais simples que as linguagens
atuais para atualização de XML, e, como tal, é apropriada para usuários inexperientes.
Uma semântica para as operações de atualização é discutida, assim como algoritmos eficientes para implementá-la. Para avaliar nossa abordagem, apresentamos uma análise
experimental com dados XML reais de vários domı́nios, mostrando que nosso método é
eficiente, altamente efetivo e acurado.
Palavras-Chave: Atualização Livre de Esquema; XML; Gerência 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 locations for performing the updates without violating the schemas of the data sources.
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 evaluate our approach, we present an experimental 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.
Sumário
Lista de Figuras
Lista de Tabelas
p. 13
1 Introdução
Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 13
Um Exemplo Motivador . . . . . . . . . . . . . . . . . .
p. 14
Aplicações . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 16
1.1
Desafios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 17
1.2
Contribuições e Organização . . . . . . . . . . . . . . . . . . . . . . . .
p. 18
2 Fundamentos, Terminologia e Trabalhos Relacionados
2.1
p. 20
Conceitos Básicos de XML . . . . . . . . . . . . . . . . . . . . . . . . .
p. 20
Expressões regulares 1-unambiguous . . . . . . . . . . . .
p. 21
Autômato de Glushkov . . . . . . . . . . . . . . . . . . .
p. 21
Validando documentos . . . . . . . . . . . . . . . . . . .
p. 22
2.2
Consultas livre de esquema . . . . . . . . . . . . . . . . . . . . . . . . .
p. 22
2.3
Métricas de Similaridade . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 23
Distância de edição . . . . . . . . . . . . . . . . . . . . .
p. 23
Distância de edição em árvores . . . . . . . . . . . . . . .
p. 24
Similaridade de Cosseno . . . . . . . . . . . . . . . . . .
p. 24
softTF-IDF . . . . . . . . . . . . . . . . . . . . . . . . .
p. 24
Troca de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 24
2.4
2.5
Linguagens de Atualização de XML . . . . . . . . . . . . . . . . . . . .
p. 27
3 Atualização Livre de Esquema
3.1
p. 25
Considerações Iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 27
Atualizações Livres de Esquema . . . . . . . . . . . . . .
p. 29
3.2
Visão Geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 29
3.3
Ancoramento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 31
Determinando a Equivalência de Nós . . . . . . . . . . .
p. 32
Linguagem de Atualização Livre de Esquema . . . . . . . . . . . . . . .
p. 33
3.4.1
A Sintaxe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 33
Notação . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 34
Uma Semântica Conservadora . . . . . . . . . . . . . . . . . . .
p. 34
3.4
3.4.2
INSERT P1 INTO P2
3.5
. . . . . . . . . . . . . . . . . . . .
p. 34
UPDATE P2 WITH P1 . . . . . . . . . . . . . . . . . . . .
p. 35
Uma Nota sobre semântica . . . . . . . . . . . . . . . . .
p. 36
MERGE P1 INTO P2 . . . . . . . . . . . . . . . . . . . . .
p. 37
DELETE P1 FROM P2 . . . . . . . . . . . . . . . . . . . .
p. 37
Atualizações Resultando em Documentos Válidos . . . . . . . . . . . .
p. 37
Determinando o Local da Atualização . . . . . . . . . . .
p. 39
DTDs livres de conflito . . . . . . . . . . . . . . . . . . .
p. 39
4 Adaptação de Dados
p. 41
4.1
Mapeamentos na Adaptação de Dados . . . . . . . . . . . . . . . . . .
p. 41
4.2
Casamento de Tipos . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 42
Similaridade de conteúdo . . . . . . . . . . . . . . . . . .
p. 43
Similaridade baseada em palavras-chave . . . . . . . . . .
p. 44
Similaridade baseada em valor . . . . . . . . . . . . . . .
p. 45
Similaridade de rótulo
4.3
4.4
. . . . . . . . . . . . . . . . . . .
p. 45
Encontrando mapeamentos . . . . . . . . . . . . . . . . . . . . . . . . .
p. 47
Pares conflitantes . . . . . . . . . . . . . . . . . . . . . .
p. 47
Traduzindo Instâncias . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 49
Valores ausentes . . . . . . . . . . . . . . . . . . . . . . .
p. 50
Árvore geradora mı́nima . . . . . . . . . . . . . . . . . .
p. 50
5 Descoberta de Âncora
p. 52
5.1
Algoritmo de Descoberta de Âncora . . . . . . . . . . . . . . . . . . . .
p. 52
5.2
Similaridade de Nós Internos . . . . . . . . . . . . . . . . . . . . . . . .
p. 54
6 Avaliação Experimental
6.1
p. 56
Adaptação de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 57
Efetividade do escore combinado da adaptação de dados .
p. 58
Impacto do tamanho do documento de entrada . . . . . .
p. 59
Impacto no tamanho do banco de dados . . . . . . . . . .
p. 59
Tolerância a ruı́do . . . . . . . . . . . . . . . . . . . . . .
p. 60
Avaliação do arcabouço de atualização . . . . . . . . . .
p. 61
6.2
Descoberta de Âncora . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 62
6.3
Qualidade das Operações Livre de Esquema . . . . . . . . . . . . . . .
p. 63
Acuidade da Atualização . . . . . . . . . . . . . . . . . .
p. 64
Qualidade das operações livres de esquema . . . . . . . .
p. 64
7 Conclusão e Trabalhos Futuros
p. 67
Referências
p. 69
Lista de Figuras
1
Instâncias do banco de dados alvo antes (a) e depois (b) das operações
de atualização. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
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
Autômato de Glushkov correspondente a regra de DTD li ← a, (b∗ |
(c, a+)). qI é o estado inicial; qb , qc correspondem aos sı́mbolos b e c,
respectivamente; qa1 , qa2 correspondem a primeira e segunda ocorrência
do sı́mbolo a. Estados finais são denotados por nós com linhas duplas. .
p. 22
7
Resultado da adaptação de dados sobre o documento rss.xml. . . . . .
p. 28
8
Ancoramentos não ambı́guos e completos s → t. As linhas pontilhadas
indicam o ancoramento. . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 29
9
Visão geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 30
10
Ancoramento ambı́guo s → t∗ . (Para maior clareza, omitimos o tı́tulo
e o estúdio dos filmes). Observe que um único filme em s é mapeado a
dois filmes em t por causa dos atores ancorados. . . . . . . . . . . . . .
11
p. 31
Autômato de Glushkov correspondente a regra de DTD li ← a, (b∗ |
(c, a+)). qI é o estado inicial; qb , qc correspondem aos sı́mbolos b e c,
respectivamente; qa1 , qa2 correspondem a primeira e segunda ocorrência
do sı́mbolo a. Estados finais são denotados por nós com linhas duplas. .
p. 38
12
Mapeamento entre os grafos DTD de Ds e Dt . . . . . . . . . . . . . . .
p. 42
13
Rede bayesiana para combinação dos componentes de similaridade . . .
p. 42
14
Mapeamento entre os grafos DTD de Ds e Dt , com pares conflitantes a
e b. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 47
15
Procedimento para descoberta de âncora. . . . . . . . . . . . . . . . . .
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
Tolerância a ruı́do. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 60
21
Medida-f média da descoberta de âncora para vários valores como limiar
de ancoramento λ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 63
Lista de Tabelas
1
Qualidade da adaptação de dados. . . . . . . . . . . . . . . . . . . . . .
p. 62
2
Qualidade do ancoramento para elementos simples e complexos. . . . .
p. 63
3
Acuidade das operações de atualização. . . . . . . . . . . . . . . . . . .
p. 65
4
Correção da operação de atualização quando o banco de dados deveria
permanecer inalterado. . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 65
13
1
Introdução
Tecnologias presentes na World Wide Web, particularmente XML com seu crescente
repertório de ferramentas e aplicações, têm facilitado tremendamente a recuperação e o
compartilhamento de dados por usuários leigos ou casuais. Atualmente, há uma ampla
variedade de ferramentas e serviços fáceis de usar para publicar dados online, tal como
Freebase e Google Base. Outros serviços bastante difundidos para publicação de dados
na Web são os RSS feeds, que oferecem informações em formato XML. Estas facilidades
têm incentivado o desenvolvimento de soluções para facilitar a obtenção de respostas
para consultas de usuários não especialistas. Uma linha de pesquisa proeminente é o
uso de abordagens livres de esquema, tais como consultas baseadas em palavras-chave ou
estratégias de relaxamento de consultas. Entretanto, ainda não foram propostas soluções
equivalentes para o problema de atualização de bancos de dados XML por usuários leigos.
Este trabalho considera atualizações tı́picas realizadas por usuários casuais trocando
dados XML. Em uma aplicação onde colecionadores de filmes trocam dados, tais operações
seriam: inserir filmes de um documento fonte 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 atualização de XML requer conhecimento preciso
dos esquemas dos documentos envolvidos na atualização, assim como do conteúdo dos
documentos. Por exemplo, no caso de uma inserção de filmes no banco de dados, é
necessário evitar inserir filmes duplicados. Além disso, cuidados devem ser tomados para
que o banco de dados resultante seja ainda válido com respeito ao seu esquema. Se
adicionarmos a isso o fato de que é necessário conhecer XQuery, que é a base de todas
as linguagens práticas para consultas e atualizações em XML, chegamos a um nı́vel de
complexidade elevadı́ssimo para a maioria dos usuários, não somente os leigos.
Objetivo
Este trabalho visa permitir que usuários atualizem bancos de dados XML de uma forma
14
1 Introdução
movies
movies
genre
genre
@name
Thriller
@name
Thriller
movie
movie
title
Deja Vu
movie
year
1996
studio
unknown
(a) Original
title
Deja Vu
genre
@name
Horror
title
studio
The Departed Warner
movie
year
2006
studio
Touchstone Pictures
title
Sublime
studio
Warner
(b) Atualizado.
Figura 1: Instâncias do banco de dados alvo antes (a) e depois (b) das operações de
atualização.
mais intuitiva e descomplicada que as soluções baseadas em XQuery. Em particular,
propomos um novo paradigma para atualizar documentos XML baseado em primitivas
simples que não requerem conhecimento explı́cito de esquemas. Nossas primitivas “livres
de esquema” exigem apenas que o usuário indique os dados envolvidos nas operações. Por
exemplo, em uma inserção, o usuário pode simplesmente indicar um documento inteiro
para ser inserido em outro. A única hipótese adotada é que ambos documentos apresentam dados do mesmo domı́nio (por exemplo, filmes). Como mostramos ao logo do
trabalho, mesmo com documentos bastante pequenos, nossa abordagem é apta a encontrar as correspondências entre os tipos de elementos (ex., tı́tulo, ator) nos esquemas fonte
e alvo, permitindo portanto a reformatação dos dados fonte. Nossa abordagem também
é capaz de identificar itens de dados duplicados nos documentos fonte e alvo, permitindo
assim determinar os locais apropriados para atualizações.
Um Exemplo Motivador
Para ilustrar o problema de atualização livre de esquema, usaremos um banco de dados XML (db.xml) como mostrado na Figura 1(a), que armazena uma coleção de dados
pessoais sobre cinema. Observe que os atributos são iniciados com ‘@’ e os valores textuais
são descritos abaixo dos rótulos dos elementos ou atributos correspondentes. A Figura 2
mostra o DTD para este banco de dados. Suponha que o usuário queira inserir nesse
banco de dados novos lançamentos de filmes vindos de um RSS feed, no qual o usuário
se inscreveu (rss.xml, como mostrado na Figura 3(a)). Duas observações devem ser fei-
15
1 Introdução
<!ELEMENT
<!ELEMENT
<!ATTLIST
<!ELEMENT
<!ELEMENT
<!ELEMENT
<!ELEMENT
<!ELEMENT
<!ELEMENT
<!ATTLIST
<!ELEMENT
<!ELEMENT
movies (genre*)>
genre (movie*)>
genre name ID #REQUIRED>
movie (title, studio, year?, description?,
actor*,rating*, review*)>
title (#PCDATA)>
studio (#PCDATA)>
year (#PCDATA)>
description (#PCDATA)>
rating (#PCDATA)>
rating country CDATA #REQUIRED>
review (title, paragraph*)>
paragraph (#PCDATA)>
Figura 2: DTD para o banco de dados db.xml.
channel
name
Warner
item
film
item
title
genre
title
genre
The Departed Thriller Sublime Horror
(a)
title
Deja Vu
rated
PG−13
company
released
Touchstone Pictures 2006
(b)
Figura 3: Documentos fontes rss.xml (a) e ifilm.xml (b).
tas aqui. Primeiro, ambos os documentos XML contêm informação sobre cinema, mas
utilizam esquemas distintos; portanto, os dados de rss.xml devem ser re-estruturados de
acordo com o DTD de db.xml. Segundo, o DTD do banco de dados requer elementos
genre únicos (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
gênero ainda não presente no banco de dados.
A única maneira de executar esta tarefa com a infra-estrutura atual de atualização
de XML seria escrever comandos de atualização sobre db.xml que incluı́ssem também
comandos de consulta sobre o documento fonte rss.xml. Usando a linguagem XQuery
estendida com recursos de atualização (ROBIE; FLORESCU; CHAMBERLIN, 2006), os comandos apresentadas na Figura 4 podem ser usados para esta operação de atualização.
A instância resultante da execução desses comandos é apresentada na Figura 1(b), na
qual as arestas dos elementos inseridos estão destacadas por setas pontilhadas para maior
clareza.
Neste trabalho, propomos um novo paradigma no qual tais inserções podem ser indicadas por construções mais simples e de mais alto nı́vel. Para aplicar nossos métodos de
16
1 Introdução
forma concreta (em uma aplicação da Web, por exemplo), propomos uma linguagem de
atualização minimalista (Seção 3.4); entretanto, a essência da nossa abordagem é que o
usuário deve apenas ser obrigado a indicar os nós envolvidos na atualização. Por exemplo,
a atualização 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 responsável por inserir os dados de rss.xml apropriadamente
em db.xml.
Considere agora a atualização do banco de dados com informações mais precisas vindo
de uma fonte online. Por exemplo, o documento ifilm.xml (Figure 3(b)) contém o ano
correto de lançamento e nome do estúdio de um filme no banco de dados. Uma vez mais,
com a infra-estrutura atual de atualização de XML é necessário localizar manualmente
os elementos a serem atualizados, e consultar as porções apropriadas do documento de
entrada para efetuar esta alteração. Propomos então uma abordagem mais intuitiva na
qual o usuário submeteria um comando tal como:
UPDATE doc(’db.xml’) WITH doc(’ifilm.xml’)
Neste caso, nosso arcabouço seria responsável por fazer as correções que resultariam no
banco de dados final, como mostrado na Figura 1(b).
Aplicações
Nossa principal motivação para este trabalho é a troca de dados XML por usuários casuais ou leigos, proveniente do uso crescente de XML em ferramentas de computação
pessoal (BRAUER et al., 2005; MICROSOFT CORPORATION, 2006) e a proliferação de sites
e comunidades de compartilhamento de dados baseados na Web. Exemplos desse tipo
de site são Freebase1 e GoogleBase2 , os quais oferecem um ambiente colaborativo, onde
os usuários podem inserir novos dados ou editar os dados existentes, além de realizar
consultas sobre a base de dados. Usuários tı́picos desses sistemas não são especialistas
em tecnologias de bancos de dados, e, como tal, não são aptos a usar ferramentas e linguagens sofisticadas como XQuery e seus recursos de atualização. Nosso trabalho tem
aplicação também em gerência de dados pessoais, um desafio permanente em gerência
1
2
http://www.freebase.com/ .
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 dados 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 aplicação (DITTRICH; SALLES, 2006), fazendo os métodos que desenvolvemos aqui diretamente aplicáveis. Finalmente, nosso trabalho é aplicável no contexto tradicional de
troca e integração de dados. Isto deve-se ao uso de técnicas de casamento de esquema, juntamente com restrições semânticas, para produzir automaticamente mapeamentos entre
esquemas, os quais podem ser usados diretamente, ou como ponto de partida para os
usuários definirem os mapeamentos. Por outro lado, é possı́vel acoplar o nosso mecanismo de atualização dentro de uma ferramenta de troca de dados que use outros tipos
de processos para descoberta de mapeamentos. Em todos os casos, nossos métodos demandam baixo investimento de configuração e esforço mı́nimo dos usuários, tornando-se
uma opção bastante atrativa.
1.1
Desafios
Mesmo considerando que um paradigma de atualização livre de esquema, no qual o
usuário indica qual operação efetuar e indica os nós envolvidos na operação, é claramente
preferı́vel àquele baseado em atualização através de comandos em XQuery (Figura 4), há
1.2 Contribuições e Organização
18
muitos desafios para prover tal capacidade. Primeiro, como discutido acima, é necessário
identificar os elementos do documento fonte que serão realmente usados na atualização.
No exemplo acima, tivemos que tratar os dois filmes vindos de rss.xml diferentemente,
para evitar que a operação resultasse num banco de dados inválido. Ainda mais, mesmo
que o DTD permitisse gêneros (elementos genre) duplicados, é necessário tomar cuidado
para não introduzir redundância de dados desnecessária, que pode gerar confusão.
Além disso, precisamos formatar os dados de entrada de acordo com o DTD do banco
de dados. É necessário ainda tomar cuidado para não produzir atualizações que resultam em bancos de dados XML inválidos. Além de reformatar corretamente os dados
de entrada, isto requer determinar um local para atualização que não viole o DTD do
banco de dados. Em geral, isto requer revalidar o banco de dados depois da atualização,
e o problema pode se tornar ainda mais complicado quando vários locais de inserção são
permitidos.
Tradicionalmente, todos esses aspectos são tratados manualmente por um programador de XQuery, o qual precisa também conhecer os detalhes de ambos esquemas envolvidos. O desafio que enfrentamos neste trabalho é lidar com essas dificuldades de forma
automática, e no final das contas permitir que usuários inexperientes realizem atualizações
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 paradigma de alto nı́vel poderia também ser materializado via interfaces gráficas nas quais
uma interface mais intuitiva poderia ser usada (por exemplo, “arrastando” o documento
rss.xml e o “soltando” em db.xml para indicar a operação de inserção).
1.2
Contribuições e Organização
Até onde sabemos, nenhum outro trabalho anterior tratou o problema de produzir
automaticamente atualizações em documentos XML. Nossas contribuições são:
• Um novo paradigma para atualização de XML o qual é baseado em operações intuitivas e na habilidade do usuário de indicar os nós envolvidos na atualização.
• Propomos uma linguagem simples de atualização e uma semântica para esta linguagem que evita a introdução de redundância no banco de dados.
• Nosso arcabouço é composto pelo processo de adaptação de dados e pelo algoritmo
de descoberta de âncora. O processo de adaptação de dados traduz dados XML de
1.2 Contribuições e Organização
19
uma representação para outra, reestruturando e renomeando os elementos, de forma
que sempre é gerado conteúdo válido mesmo quando lidamos com valores ausentes.
• Nosso algoritmo de descoberta de âncora determina o local preciso das atualizações,
identificando nós equivalentes nos documentos XML fonte e alvo.
Os fundamentos teóricos, a terminologia utilizada neste trabalho e alguns trabalhos
relacionados são discutidos no próximo capı́tulo. Nosso arcabouço para atualização livre
de esquema é apresentado no Capı́tulo 3. Uma linguagem simples de atualização é apresentada para aplicar nossos métodos de forma concreta na Seção 3.4. O processo de
adaptação de dados é apresentado no capı́tulo Capı́tulo 4, e o algoritmo de descoberta
de âncora no Capı́tulo 5. A validação experimental dos nossos métodos é discutida no
Capı́tulo 6, e a conclusão do trabalho é apresentada no Capı́tulo 7.
20
2
Fundamentos, Terminologia e
Trabalhos Relacionados
Este capı́tulo introduz alguns conceitos básicos sobre XML e métricas de similaridade, necessários para entendimento do nosso trabalho. São apresentados também vários
trabalhos relacionados com a pesquisa realizada.
2.1
Conceitos Básicos de XML
A linguagem de marcação 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 são auto-descritivos e usam marcações textuais para descrever
dados, sendo elementos e atributos as principais marcações. Por exemplo, em <rating
country=‘‘US’’> PG-13 </rating> temos um elemento com rótulo rating e contéudo
“PG-13”, assim como um atributo com rótulo country e valor “US”. Um atributo pode
ser um identificador (ID) do elemento, e outros elementos podem ser apontadores ou
referências a outros elementos (IDREF, IDREFS). Documentos XML são modelados como
árvores (ou grafos, se considerarmos atributos IDREF), onde os nós são elementos e
atributos, e as arestas indicam como os elementos/atributos são aninhados. As relações
pai-filho e ancestral-descente entre os nós se aplicam aos documentos XML, assim como
em árvores. Um exemplo de árvore XML é apresentado na Figura 1(a).
A correção de um documento XML é medida de duas formas diferentes. Um documento é bem-formado se ele está 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 não é considerado um documento XML. Por outro lado, um
documento XML bem-formado é também válido se ele está em conformidade com sua
definição de esquema, expressa por um DTD (Document Type Definition), por exemplo.
DTD é uma gramática que define cada tipo de elemento permitido (e seu conteúdo) num
2.1 Conceitos Básicos de XML
21
Figura 5: Exemplo de um grafo de DTD.
documento através de expressões regulares. Elementos são declarados num DTD por
regras da forma <!ELEMENT l c>, conhecidas como modelos de conteúdo, as quais especificam que: elementos válidos do tipo l têm conteúdo de acordo com c, onde c é uma
expressão regular que gera conteúdo válido. O DTD do banco de dados da Figura 1(a)
é mostrado na Figura 2. Um DTD pode ser representado também como um grafo, onde
os nós são elementos, atributos e operadores (ex., ?, +, *). Na Figura 5 é mostrado um
exemplo de grafo de DTD.
Expressões regulares 1-unambiguous
A especificação de DTDs se restringem a expressões regulares 1-ambiguous para definir
modelos de conteúdo. Informalmente, uma expressão regular é 1-ambiguous se é possı́vel
casar unicamente a ocorrência de um sı́mbolo na expressão regular a um elemento XML
na seqüência de entrada sem verificar qualquer outro elemento. Em outras palavras,
expressões regulares 1-unambiguous requerem a verificação de apenas um sı́mbolo por
elemento XML de entrada.
Autômato de Glushkov
Uma forma de representar as expressões regulares de um DTD é através do autômato
finito proposto por Glushkov (GLUSHKOV, 1961). O conteúdo de um elemento é válido
se ele é aceito por um autômato de Glushkov correspondente ao modelo de conteúdo do
elemento. Em um autômato de Glushkov de uma expressão regular E, os estados correspondem às posições (sı́mbolos) de E e transições conectam aquelas posições que podem ser
consecutivas numa seqüência de elementos válida. Um exemplo de autômato de Glushkov
é ilustrado na Figura 6.
22
2.2 Consultas livre de esquema
b
a
qI
b
qa1
qb
a
c
a
qc
qa2
Figura 6: Autômato de Glushkov correspondente a regra de DTD li ← a, (b∗ | (c, a+)).
qI é o estado inicial; qb , qc correspondem aos sı́mbolos b e c, respectivamente; qa1 , qa2
correspondem a primeira e segunda ocorrência do sı́mbolo a. Estados finais são denotados
por nós com linhas duplas.
Validando documentos
Um problema relacionado ao nosso trabalho é verificar se um documento é válido com
relação a um DTD. Em termos gerais, é preciso validar o conteúdo de cada elemento
no documento através do autômato de Glushkov correspondente. Entretanto, como exigimos que um documento XML continue válido mesmo após uma atualização, podemos usar
técnicas de atualização incrementais (BARBOSA et al., 2004), que verificam se as alterações
num documento válido comprometem sua validade ou não.
2.2
Consultas livre de esquema
Numerosos métodos têm 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 também bancos de dados relacionais, por exemplo, (AGRAWAL; CHAUDHURI; DAS,
2002; MESQUITA et al., 2007). Entretanto, até onde sabemos, nosso método é o primeiro
a tratar o problema mais desafiador de atualizações livres de esquema.
A motivação 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 métodos de pesquisa semântica baseados em Recuperação de Informação, no qual fragmentos de XML são 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 nós na árvore 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-árvores que contenham
essas palavras-chaves em seu conteúdo textual. Muitos trabalhos vêm propondo dife-
2.3 Métricas de Similaridade
23
rentes maneiras de retornar sub-árvores significantes (meaningful) como resposta. Uma
das propostas mais difundidas é retornar o ancestral comum mais baixo (Lower Common
Ancestor or LCA) dos nós que contenham as palavras-chave da consulta (por exemplo,
Meet (SCHMIDT; KERSTEN; WINDHOUWER, 2001)). No segundo caso, as técnicas para encontrar sub-árvores significantes são incorporados para flexibilizar a definição da estrutura
a ser consultada.
Mais próximas ao nosso trabalho são as técnicas de estruturação 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 estruturadas em SQL (de acordo com uma semântica) que equivalem às consultas originais como
intencionadas pelo usuário. Este processo envolve identificar para cada palavra-chave o
atributo alvo pretendido pelo usuário. Da mesma forma, nossos métodos precisam identificar qual tipo de elemento onde cada valor de entrada melhor “se adapta” no banco
de dados. Além disso, também definimos uma semântica para possı́veis operações livres
de esquema, gerando ao final primitivas de atualização estruturadas, que podem ser facilmente traduzidas para linguagens de atualização, como XQuery.
2.3
Métricas de Similaridade
Muitas abordagens livres de esquema para consultas são, na verdade, buscas por
similaridade, onde dado uma consulta fornecida pelo usuário, queremos retornar os objetos
mais parecidos com a consulta num banco de dados. O cerne desse processo são as métricas
de similaridade utilizadas. Nesta seção discutiremos algumas delas, em particular as que
usamos neste trabalho. Há também outras aplicações para as métricas de similaridade,
como em limpeza de dados (GALHARDAS et al., 2001; GRAVANO et al., 2001) e detecção de
duplicatas (WEIS; NAUMANN, 2005).
Distância de edição
A distância de edição ou distância Levenshtein de duas seqüências de caracteres é dada
pelo número de edições necessárias para converter uma seqüência em outra. As operações
de edição utilizadas são, geralmente: inserção, remoção ou substituição de um caracter.
Em algumas aplicações o número de edições é normalizado pelo tamanho da seqüência
maior, resultando num valor em [0, 1]. A distância de edição normalizada serve comumente
como suporte de outras métricas para o casamento aproximado de valores.
2.4 Troca de dados
24
Distância de edição em árvores
A idéia de distância de edição também pode ser adaptada para árvores, onde queremos o número de edições para converter uma árvore em outra. As operações de edição
geralmente são inserir, remover ou substituir nós de uma árvore. Um problema relacionado é o de determinar quando duas árvores XML são equivalentes, embora elas possam
ter estruturas diferentes e usar diferentes rótulos 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 espaçovetorial (BAEZA-YATES; RIBEIRO-NETO, 1999) utilizado freqüentemente em Recuperação
de Informação, onde os documentos são modelados como vetores. Cada dimensão corresponde a um termo em separado. Se um termo ocorre num documento, o valor da dimensão
correspondente no vetor será maior que zero. Estes valores podem ser calculados por diversos esquemas de ponderação, sendo TF-IDF um dos mais difundidos (BAEZA-YATES;
RIBEIRO-NETO, 1999).
softTF-IDF
Uma limitação da similaridade de cosseno é que ela considera apenas o casamento exato de
palavras. Para contornar este problema, a variação denominada softTF-IDF (COHEN; RAVIKUMAR; FIENBERG, 2003) permite que palavras similares sejam também consideradas.
Para isto, uma segunda métrica é usada entre as palavras dos documentos analisados. Se
duas palavras são suficientemente similares, considera-se que suas respectivas dimensões
são as mesmas, ou seja, formam uma única dimensão.
2.4
Troca de dados
Outro problema que deve ser abordado em nosso contexto é traduzir dados formatados 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 definição mais
geral, consiste em, receber dados estruturados conforme um esquema fonte, restruturálos e traduzi-los para um esquema alvo. Fagin et al. (FAGIN et al., 2003) estabeleceram
2.5 Linguagens de Atualização de XML
25
as fundações deste problema; em particular, eles estudaram diferentes semânticas 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 estão 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 são 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 nós podemos definir um mapeamento completo (ou seja, uma maneira de traduzir
as instâncias de dados reais). Casamento de esquema tem sido extensivamente estudado
recentemente; Rahm e Bernstein apresentam um levantamento de várias técnicas para
este problema (RAHM; BERNSTEIN, 2001). Vários métodos (por exemplo, Similarity Flooding (MELNIK; GARCIA-MOLINA; RAHM, 2002)) exploram informação de esquema, tal como
rótulos elementos de esquema, para derivar mapeamentos. Outros métodos exploram os
valores de dados para derivar associações entre os elementos de esquema (COHEN; HIRSH,
1998). Nosso método de casamento automático combina tanto similaridade de esquemas
como de valores para derivar tais mapeamentos. Como discutido ao longo do texto, nosso
método atinge alta acuidade em dados reais de diferentes Web sites.
Há também trabalhos que tratam o problema de traduzir dados uma vez que os
esquemas estão casados (veja, por exemplo, (POPA et al., 2002) e as referências nele). O
estado-da-arte é definir mapeamentos com a ajuda de sistemas que necessitam tipicamente
de considerável investimento de configuração e intervenção do usuário. Nossa solução, por
outro lado, é completamente não supervisionada, e portanto adequada para usuários não
experientes e casuais trocadas dados na Web. Nosso algoritmo de tradução de dados é
baseado nas técnicas path outer union e hash-based tagging de (SHANMUGASUNDARAM et
al., 2001).
2.5
Linguagens de Atualização de XML
O estado-da-arte em linguagens de atualização de XML são linguagens estruturadas,
como XQuery (ROBIE; FLORESCU; CHAMBERLIN, 2006) e XUpdate(LAUX; MARTIN, 2000),
cuja semântica é precisa e bem-definida. Tais linguagens são eficientes e extremamente
adequadas para o desenvolvimento de aplicações crı́ticas, que exigem 100% de correção nas
operações de atualização. Entretanto, como discutido anteriormente, os usuários precisam
2.5 Linguagens de Atualização de XML
26
conhecer os esquemas envolvidos na operação e a sintaxe dessas linguagens para poderem
utilizá-las.
A linguagem proposta neste trabalho não visa substituir o paradigma atual de linguagens estruturadas, mas permitir que usuários consigam produzir, de uma forma simples e
intuitiva, operações complexas em um cenário onde poucos erros são aceitáveis. Até onde
sabemos, este é o primeiro trabalho a tratar o o problema de produzir automaticamente
atualizações em documentos XML.
27
3
Atualização Livre de Esquema
Como ilustrado no Capı́tulo 1, escrever programas de atualização 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
usuários devem poder especificar atualizações de uma forma mais intuitiva. Para este fim,
propomos uma linguagem de atualização muito mais simples na qual os usuários especificam a operação e o conteúdo que está envolvido na operação de atualização. O problema
da atualização livre de esquema consiste em traduzir tais expressões em programas de
atualização que capturam tanto quanto possı́vel a “intenção” da atualização dada pelo
usuário.
3.1
Considerações Iniciais
Documentos XML são modelados como árvores ordenadas e rotuladas, onde elementos
e atributos são nós e tags são rótulos. Por simplicidade, não há distinção entre atributos
e elementos textuais em nossa discussão. O tipo de um elemento é dado pelo seu rótulo
na notação de DTD. Dessa forma, dois elementos são do mesmo tipo se apresentam o
mesmo rótulo. Observe que, diferente do conceito apresentado aqui, o tipo de elemento
no contexto de XML Schema é mais próximo ao tipo de dado: inteiro, real, textual.
Antes de definir o problema de atualização livre de esquema, discutimos atualizações de
documentos XML em geral. Quatro primitivas de atualização são consideradas: anexar
um nó (ou seja, um elemento XML ou atributo) como último filho de um outro elemento
no banco de dados (APP), inserir um novo nó antes de outro no banco de dados (INSB),
substituir um nó no banco de dados por um novo (REP), e remover um nó do banco de
dados (DEL). A partir destas primitivas, define-se:
Definição 1 Uma operação individual de atualização estruturada, denotada por uma tripla u = (op, l, c), onde op é a primitiva de atualização, l é a expressão de caminho
28
3.1 Considerações Iniciais
genre
@name
Thriller
movie
title
studio
The Departed Warner
(a)
genre
@name
Horror
movie
title
Sublime
studio
Warner
(b)
Figura 7: Resultado da adaptação de dados sobre o documento rss.xml.
indicando o local da atualização, e c é o conteúdo a ser inserido ou modificado (c é vazio
para remoções).
Observe que o local da atualização pode ser expresso de muitas formas diferentes.
Em nossos exemplos são usadas expressões de caminho que retornam um nó apenas;
entretanto, poderiam ser diretamente usados identificadores internos em implementações
práticas.
Tipicamente, programas de atualização são definidos pelo que chamamos de atualizações estruturadas compostas: seqüências de atualizações individuais u1 , . . . , uk , agrupadas em uma única transação atômica. Assumimos que um programa de atualização
u1 , . . . , uk é completado integralmente (ou seja, cada operação é realizada) ou é abortado (ou seja, o documento é deixado inalterado). Além disso, assumimos que cada ui é
aplicado ao documento original (ou seja, os resultados de operações individuais não são
visı́veis a outras operações na mesma transação).
Exemplo 1 A seguinte operação de atualização composta produz o mesmo efeito que as
expressões de atualização na Figura 4:
u1 = (APP,
doc(‘db.xml’)//genre[@name=“Thriller”],
<movie><title>The Departed</title>
<studio>Warner</studio></movie>)
u2 = (APP,
doc(‘db.xml’)//movies,
<genre @name=“Horror”>
<movie><title>The Departed</title>
<studio>Warner</studio></movie>
</genre>)
29
3.2 Visão Geral
m
g
e
n
r
o
e
g
@
n
T
a
m
h
r
e
i
l
l
@
e
r
T
n
h
a
r
i
m
l
v
e
i
n
e
s
r
m
e
g
e
l
m
o
v
i
@
e
T
t
o
v
i
e
m
o
v
i
i
t
l
j
a
V
e
a
u
d
i
i
t
l
r
i
l
l
e
e
r
e
a
o
v
i
e
0
0
a
t
i
n
g
6
r
e
y
e
t
P
r
D
e
i
t
l
a
r
e
o
1
h
e
r
e
D
T
s
r
r
t
n
e
u
2
l
m
i
e
e
y
t
a
e
m
y
t
s
i
h
e
D
t
n
v
r
e
m
o
e
p
a
e
j
a
V
9
9
d
r
W
a
]
1
3
1
D
s
e
G
6
u
t
t
u
d
i
e
j
a
V
9
6
9
u
o
r
n
e
T
o
u
c
h
s
t
o
n
e
P
i
c
t
u
r
e
s
@
s
t
u
d
i
c
n
k
n
o
u
n
t
r
y
o
s
u
u
o
w
n
k
n
o
w
(a) Ancoramento do filme na Figura 7(a).
t
u
d
i
o
n
n
u
n
k
n
o
w
n
(b) Ancoramento do filme da Figura 3(b).
Figura 8: Ancoramentos não ambı́guos e completos s → t. As linhas pontilhadas indicam
o ancoramento.
Atualizações Livres de Esquema
Uma atualização livre de esquema é denotada pela tripla sf = (op, s, t), onde op é uma
operação, 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 são válidos com respeito aos DTDs Ds e Dt ,
que podem ou não ser os mesmos, esperamos que o banco de dados resultante da operação
também seja válido com respeito a Dt .
Este trabalho considera o problema de rescrever uma atualização livre de esquema
sf = (op, s, t) em uma atualização estruturada composta equivalente (de acordo com uma
dada semântica).
3.2
Visão Geral
Nossa abordagem funciona como ilustrado na Figura 9. Primeiro, os dados no documento fonte são reorganizados para ficar de acordo o DTD do banco de dados alvo
(caso já não estejam). Este processo, chamado de adaptação de dados(Data Fitting),
é descrito no Capı́tulo 4. Em resumo, a adaptação 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 operação de atualização separada.
Por exemplo, aplicando a operação de adaptação de dados no documento da Figura 3(a),
os dois fragmentos mostrados na Figura 7 seriam obtidos como resultado.
30
3.2 Visão Geral
Figura 9: Visão geral
O segundo passo é determinar os locais das atualizações. Isto é realizado tentando-se
ancorar cada sub-árvore resultante do primeiro passo ao banco de dados. Para ilustrar
essa idéia, a Figura 8(a) mostra o ancoramento do filme da Figura 7(a) no banco de dados
do nosso exemplo. Observe que o nó do elemento genre e seu atributo @name tem nós
correspondentes únicos no banco de dados. Portanto, dizemos que a árvore formada por
eles ancora de forma não ambı́gua no banco de dados.
A descoberta de âncora é crucial em nosso método e uma das principais contribuições
deste trabalho. De fato, a semântica das atualizações em nosso arcabouço é definida
baseando-se nas sub-árvores ancoradas (mais detalhes seguem). Para inserções, cada nó
não ancorado i que é filho de um nó ancorado j é inserido como filho do nó 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 nó genre. No caso das atualizações, cada nó não
ancorado no banco de dados é substituı́do por um nó equivalente no documento. Por
exemplo, no caso da Figura 8(b), isto corresponderia a substituir os nós studio e year no
banco de dados. Finalmente, para remoções, os nós ancorados (e seus descendentes) são
simplesmente removidos.
É possı́vel que mais de uma sub-árvore no documento de entrada ancore no banco de
dados. Por exemplo, se o banco de dados tivesse algum outro filme do estúdio “Warner”,
seria possı́vel que o nó 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
estúdio dos filmes). Observe que um único filme em s é mapeado a dois filmes em t por
causa dos atores ancorados.
dados. Isto poderia resultar em diferentes interpretações para o que deveria ser atualizado. A semântica que propomos mais à frente considera apenas o ancoramento que
envolve a raiz dos elementos XML produzidos pela adaptação de dados. Ou seja, nós
“desancoramos” qualquer par de nós cujos pais não estão ancorados um ao outro.
O próximo passo é verificar se a operação de atualização resulta numa instância válida
do banco de dados, como discutido na Seção 3.5. O último passo é produzir as atualizações
reais que serão efetuadas no banco de dados. Tais atualizações são representadas usando
a notação simples de atualizações estruturadas descrita acima, de tal forma que é possı́vel
executá-las num sistema de armazenamento de XML ou traduzi-las para a notação de
uma linguagem de atualização, como XQuery.
3.3
Ancoramento
Conforme descrito acima, o local da atualização é determinado encontrando-se um
conjunto de correspondências entre os elementos no documento fonte e os elementos no
banco de dados, o qual nós chamamos de ancoramento. Mais precisamente, um ancoramento entre duas árvores XML s e t é uma relação s → t∗ que associa para cada nó si ∈ s
todos os nós tj ∈ t tal que si e tj são equivalentes. O conceito de equivalência depende do
tipo de nó (folha ou interno), como discutido abaixo. Duas definições importantes são,
como segue:
3.3 Ancoramento
32
Definição 2 Um ancoramento A : s → t∗ é não ambı́guo se ele é na verdade uma função
s → t e se, para cada si , sj em s, se si e sj são irmãos então A(si ) e A(sj ) são também
irmãos.
Definição 3 Um ancoramento A : s → t∗ é completo se para cada si ∈ s, quando A(si )
é definido então A(sj ) também é definido, para cada sj que é um ancestral de si .
A Figura 8 mostra dois exemplos de ancoramentos não 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 são mapeados a filmes diferentes em t (alternativamente, pode-se interpretar o ancoramento como
um mapeamento de um único filme no documento a dois no banco de dados, portanto
ambı́guo). O ancoramento seria incompleto se houvesse dois nós ancorados i e j tal que
um é ancestral de outro e há um nó não ancorado no caminho entre eles.
A semântica conservadora que propomos requer que cada ancoramento seja não ambı́guo
e completo por duas razões. Primeiro, ancoramentos ambı́guos resultam em operações
de atualização com possı́veis efeitos colaterais indesejados, como redundância de dados.
Segundo, as lacunas apresentadas em ancoramentos incompletos permitem que o documento seja ancorada em diversas árvores do banco de dados (uma para cada lacuna), o que
pode ser visto como um tipo de ambigüidade. É importante notar que um ancoramento
completo não requer que s e t (ou seja, o documento e o banco de dados) tenham todos
os seus nós ancorados; na verdade, tudo o que é necessário é que exista uma sub-árvore
s′ de s, enraizada em s, e que s′ ancore a uma sub-árvore única em t. Ainda mais, um
ancoramento incompleto pode ser sempre completado “desancorando-se” os pares de nós
cujos pais não estão ancorados um ao outro.
Determinando a Equivalência de Nós
Consideramos que dois nós XML si e ti são equivalentes se: (1) eles apresentam o mesmo
tipo de elemento conforme a notação de DTD, e (2) se há um considerável grau de similaridade entre as sub-árvores enraizadas neles. Este grau de similaridade pode ser avaliado
por alguma forma de similaridade de árvores tal como distância de edição em árvores.
Neste trabalho, como detalhado no Capı́tulo 5, usamos um processo de casamento de
baixo pra cima. Iniciamos casando os nós folhas que apresentam os mesmos rótulos e cujo
conteúdo é suficientemente similar. Usamos casamento aproximado, em vez de igualdade,
3.4 Linguagem de Atualização Livre de Esquema
33
para permitir erros de escrita e variações de soletração no documento e no banco de dados.
Uma vez que os nós folhas que casam estão ancorados, nós prosseguimos de baixo pra
cima ancorando os ancestrais correspondentes. Em todos os casos, nós ancoramos apenas
os nós que tem tipos idênticos (rótulos de elementos na notação de DTD).
3.4
Linguagem de Atualização Livre de Esquema
Esta seção descreve a sintaxe da nossa linguagem de atualização livre de esquema, e
uma semântica conservadora para ela. Por conservadora entende-se que o resultado das
operações usam todos os dados do documento fonte que podem ser “encaixados” no banco
de dados, contanto que: (i) o banco de dados resultante seja válido com respeito ao seu
DTD e (ii) nenhuma redundância que poderia ser evitada seja introduzida no banco de
dados resultante.
3.4.1
A Sintaxe
Propomos a seguinte linguagem mı́nima para atualização de XML, parcialmente descrita 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 operações, onde cada uma utiliza duas expressões de
caminho que definem o escopo da operação. Por simplicidade, nossa linguagem é restringida a um fragmento de XPath muito pequeno, que é capaz de apontar os nós apenas. No
fragmento acima da especificação segundo forma normal de Backus-Naur(EBNF), name,
fname and number são terminais que representam nomes de nós, nomes de documentos, e números naturais, respectivamente. Estes terminais são completamente definidos
3.4 Linguagem de Atualização Livre de Esquema
34
em (CLARK; DEROSE, 1999), assim como o não terminal OrExpr, que especifica os predicados de comparação em XPath 1.0.
Exemplo 2 A seguinte atualização livre de esquema expressa a mesma atualização em
XQuery da Figura 4:
INSERT doc(’input.xml’) INTO doc(’db.xml’)
A seguinte atualização livre de esquema expressa a inserção de um filme especı́fico no
banco de dados:
INSERT doc(’input.xml’)//item[title=‘The Departed’]
INTO doc(’db.xml’)
Notação
Por simplicidade, [P ] denota a lista de nós que são retornados avaliando-se P como se faz
comumente em XPath. (Observe que cada expressão de caminho pode começar apenas
com um nome de documento, portanto [P ] é sempre bem definida.)
3.4.2
Uma Semântica Conservadora
Uma semântica conservadora para a linguagem que propomos é definida a seguir.
Como mencionado acima, esta semântica permite apenas ancoramentos não ambı́guos e
completos; isto significa que a operação é indefinida caso contrário.
Considere novamente A(e) como o conjunto (possivelmente vazio) dos nós no banco
de dados em quais o nó e no documento foi ancorado. Pelo fato de insistirmos em um
ancoramento não ambı́guo, abusaremos um pouco da notação e escreveremos A(e) = t
se t é o nó no banco de dados em qual e foi ancorado. Além disso, por questão de
simplicidade, não faremos distinção explı́cita entre um nó ou a subárvore enraizada em
tal nó. Entretanto, em todos os casos pode-se discernir se e denota apenas um nó ou uma
sub-árvore a partir do contexto.
3.4 Linguagem de Atualização Livre de Esquema
35
INSERT P1 INTO P2
Esta operação insere o conteúdo de cada nó retornado por P1 em cada elemento retornado
por P2 (um erro deve ser reportado se P2 retorna atributos).
Seja s um nó de [P1 ] e t um elemento de [P2 ]. A inserção de s em t é realizada como
segue. Primeiro, o processo de adaptação de dados é aplicado em s; como mencionado
anteriormente, isto resulta numa lista de elementos XML s1 , . . . , sn em conformidade
com o DTD alvo. Cada nó si é inserido em t separadamente. A inserção funciona
diferentemente dependendo se o nó si ancora ou não.
Se A(si ) = ti (ou seja, si ancora), então sejam e1 , . . . , ek os descendentes de si que
não ancoram (caso eles existam). Cada ej é inserido na posição mais à direita (relativa a
ordem do documento) em t que não resulta em uma violação de DT . Mais precisamente,
seja pj o pai de ej em s, ej é inserido como filho de A(pj ), no local mais à direita tal que
o conteúdo resultante é válido com respeito a DT , se possı́vel (veja Seção 3.5 abaixo).
Se si não ancora (ou seja, A(si ) = ∅), tenta-se inserir si como uma nova sub-árvore
no banco de dados. Seja ti um descendente de t que contém todos os elementos do mesmo
tipo, isto é, mesmo rótulo na notação do DTD, de si . Se t existe e é único, si é inserido em
t da mesma maneira como acima, ou seja, no local mais à direita que não causa violação
do DTD.
O resultado de um operação de inserção é uma seqüência de atualizações estruturadas
ui = (opi , li , ei ), um para cada filho não ancorado ei . A operação real opi será um APP
(anexar um nó como filho) ou um INSB (inserir antes de um nó), dependendo do DTD
(veja Seção 3.5); similarmente para o local preciso da atualização li .
Exemplo 3 Considere novamente a inserção de filmes na Figura 3(a) no banco de dados
da Figura 1(a). O resultado da adaptação de dados é apresentado na Figura 7. A inserção
do filme da Figura 7(a) é detalhada na Seção 3.2; neste caso, o elemento genre ancorou,
levando à inserção do elemento movie apenas. A inserção do filme da Figura 7(b) é
realizada diferentemente pois o elemento genre não ancora no banco de dados. Uma vez
que o DTD para o banco de dados permite apenas um lugar para elementos genre, a subárvore inteira da Figura 7(b) é inserida no banco de dados. O resultado dessa operação
livre de esquema são as primitvas estruturadas descritas no Exemplo 1.
3.4 Linguagem de Atualização Livre de Esquema
36
UPDATE P2 WITH P1
Enquanto o objetivo da operação de inserção é adicionar conteúdo novo no banco de
dados, que são os nós não ancorados, o objetivo da operação de atualização é substituir
o conteúdo existente. Intuitivamente, esta operação substitui todos os elementos não ancorados no banco de dados por aqueles no documento que têm o mesmo rótulo e podem
ser casados inequivocamente a outro. Como nas inserções, a operação de atualização é
aplicada a cada nó de [P1 ] e cada nó elemento de [P2 ] separadamente, como segue.
Sejam s, t nós de [P1 ] e [P2 ], respectivamente. Como antes, primeiro s é adaptado a
DT , resultando numa lista de elementos XML s1 , . . . , sn . Cada si é tratado separadamente,
como segue. Se si não ancora em t, nada é feito e prossegue-se para o próximo elemento
da lista. Caso contrário, seja A(si ) = ti . Cada descendente de si é substituı́do por um
nó equivalente ti com o mesmo rótulo mas conteúdo diferente (caso contrário tais nós
deveriam estar ancorados).
Sejam e1 , . . . , ek os descendentes de si que não ancoram, e seja p1 , . . . , pj seus pais
respectivos. Para cada ej , se a regra do DTD para o tipo de pj permite no máximo uma
ocorrência de um elemento do tipo de ej e A(pj ) tem um filho e′j com o mesmo rótulo de
ej , nós os substituı́mos com a primitiva: u = (REP, e′j , ej ).
Exemplo 4 Usando os documentos de nosso exemplo (Figura 1(a) e Figure 3(b)), considere a seguinte atualização:
UPDATE doc(’db.xml’) WITH doc(’ifilm.xml’)
Figura 8(b) mostra o ancoramento (depois da adaptação de dados) do documento da Figura 3(b). studio e year são substituı́dos no banco de dados pelos nós correspondentes no
documento.
Uma Nota sobre semântica
Deve-se observar que, de acordo com a maneira que os filmes são organizados no banco de
dados do nosso exemplo, filmes que pertencem a mais de um gênero irão aparecer diversas
vezes no banco de dados, uma para cada gênero. Portanto, na semântica conservativa,
a atualização do Exemplo 4 falharia se o filme “Deja Vu” aparecesse mais de uma vez
no banco de dados. Isto significaria que s na Figura 8(b) não poderia ancorar de forma
3.5 Atualizações Resultando em Documentos Válidos
37
não ambı́gua. Para realizar essa operação de atualização, teria-se que utilizar o seguinte
comando: UPDATE doc(’db.xml’) WITH doc(’film.xml’)//genre
MERGE P1 INTO P2
A operação de fusão ou merge é uma combinação de uma inserção e uma atualização.
Isto é equivalente a realizar em seqüência as operações INSERT P1 INTO P2 e UPDATE
P2 WITH P1 . Intuitivamente, elementos não ancorados de um documento de entrada são
inseridos no banco de dados, e elementos ancorados no banco de dados são substituı́dos
por seus elementos correspondentes no documento.
Exemplo 5 Considere a fusão do banco de dados da Figura 1(a) com o documento da
Figura 3(b). Além das atualizações discutidas no Exemplo 4, a operação de fusão teria
também inserido a classificação (rating) do filme, contanto que a operação de adaptação
de dados possa encontrar um tipo equivalente no banco de dados e o DTD do banco de
dados permita a inserção.
DELETE P1 FROM P2
Intuitivamente esta operação remove do banco de dados aqueles nós que ancoram aos
nós especificados por P1 . Para minimizar os potenciais efeitos colaterais indesejados, esta
operação deve ser realizada apenas quando P2 retorna um único elemento.
Como antes, a operação é realizada separadamente para cada nó s que casa com P1 ;
para cada nó desses, seja s1 , . . . , sn o resultado de adaptar s ao DTD DT . Para cada si ,
se A(si ) é simplesmente removido, se estiver definido, usando a primitiva: u = (DELETE,
A(si ), null).
Enfatizamos que remoções livre de esquema são potencialmente perigosas, uma vez
que podem surgir efeitos colaterais inesperados pelos usuários. Talvez a maneira mais
natural para usuários inexperientes especificarem remoções é através da abordagem de
apontar-e-clicar, com ajuda de um interface de usuário apropriada, por exemplo.
3.5
Atualizações Resultando em Documentos Válidos
Em todas as operações de atualização, é necessário detectar e prevenir mudanças que
resultem em violação do DTD do banco de dados. Durante a inserção de novos dados,
38
3.5 Atualizações Resultando em Documentos Válidos
b
a
qI
b
qa1
qb
a
c
a
qc
qa2
Figura 11: Autômato de Glushkov correspondente a regra de DTD li ← a, (b∗ | (c, a+)).
qI é o estado inicial; qb , qc correspondem aos sı́mbolos b e c, respectivamente; qa1 , qa2
correspondem a primeira e segunda ocorrência do sı́mbolo a. Estados finais são denotados
por nós 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 adaptação de dados, e certificar-se que o
conteúdo do banco de dados resultante de cada operação é válido. Isto inclui validar os
novos elementos a serem inseridos assim como os elementos onde a inserção será realizada.
Para remoções, é preciso garantir que o conteúdo do elemento afetado pela atualização
continue válido. Finalmente, para atualizações, ou seja, substituição de nós, deve-se tomar
cuidado com as restrições globais nos DTDs, tais como regras ID e IDREF, que aplicam-se
ao documento como um todo. Deixamos a discussão sobre formatação para o Capı́tulo 4,
onde processo de adaptação de dados é discutido em detalhes.
Determinar que uma atualização a um documento válido resulta também num documento válido é um problema por si só. Entretanto, algumas das soluções propostas na
literatura (BALMIN; PAPAKONSTANTINOU; VIANU, 2004; BARBOSA; LEIGHTON; SMITH,
2006; BARBOSA et al., 2004) e seu impacto no nosso arcabouço são discutidas brevemente
aqui. Em particular, a discussão considera questões de implementação e o tamanho dos
dados auxiliares requeridos por tais soluções.
Há uma solução geral para este problema que garante tempos de revalidação na ordem
de O(k log2 n), onde n é o tamanho do banco de dados e k é o tamanho da atualização,
ou seja, o número de nós sendo inseridos ou removidos. Esta solução necessita que sejam
criadas estruturas de dados auxiliares não triviais (e proporcionalmente muito grandes).
Uma solução mais prática é usar os métodos propostos em (BARBOSA et al., 2004), que
necessita apenas de tempo O(k log n), e que usam uma estrutura de dados auxiliar mais
simples e muito menor, e são aplicáveis à grande maioria (acima de 98%) dos DTDs
usados na prática (BARBOSA; LEIGHTON; SMITH, 2006). A solução mais simples, que
é revalidar o banco de dados inteiro ou apenas os elementos que foram afetados pela
atualização, não requerem nenhum armazenamento auxiliar mas são pontecialmente muito
caros (BARBOSA et al., 2004).
3.5 Atualizações Resultando em Documentos Válidos
39
Determinando o Local da Atualização
Um passo extra é necessário para inserções: antes de aplicar os algoritmos de revalidação
acima, é necessário determinar o lugar no qual a atualização deve ser aplicada. É óbvio que
dependendo do DTD, podem haver vários lugares onde a inserção poderia ser permitida.
Sabe-se que um DTD é uma associação de expressões regulares 1-unambiguous, ou modelos de conteúdo, para rótulos de elementos (BRÜGGEMANN-KLEIN; WOOD, 1998). Sejam
li ← ri uma regra do DTD e Gri o autômato de Glushkov (BRÜGGEMANN-KLEIN; WOOD,
1998) correspondente a ri , onde há um estado separado em Gri para cada ocorrência de
um sı́mbolo em ri . É possı́vel construir um ı́ndice que indica, para cada rótulo de elemento l, quais ocorrências de um sı́mbolo podem preceder um elemento com rótulo l de
um elemento válido.
Por exemplo, considere o autômato de Glushkov da Figura 11, que corresponde a
expressão regular da regra de DTD li ← a, (b∗ | (c, a+)). A partir deste autômato, e
pelo fato de exigirmos que as inserções sejam apenas na posição mais à direita possı́vel,
podemos inferir as seguintes regras:
- elementos c podem ser inseridos apenas depois de uma ocorrência de a1 ;
- elementos b podem ser inseridos apenas depois de outros elementos b;
- um elemento a pode ser inserido apenas depois de uma ocorrência de a2 .
Infelizmente, se li é o rótulo de um elemento e cujo pai é p, e o modelo de conteúdo
associado com p contém múltiplas ocorrências de li , determinar qual ocorrência de l corresponde a e requer validar p. Isto pode ser evitado se forem usados os métodos de
revalidação incremental discutidos em (BARBOSA et al., 2004), que mantêm precisamente
o mapeamento entre os nós no documento XML e os estados nos autômatos finitos determinı́sticos usados para validá-los.
DTDs livres de conflito
Para uma classe bastante comum de DTDs a situação é bem mais simples. Expressões regulares livres de conflito, chamados de modelos de conteúdo de elementos, são aqueles em
que nenhum sı́mbolo aparece mais que uma vez (BARBOSA et al., 2004), e correspondem a
mais de 98% daqueles usando na prática de acordo com um levantamento recente (BARBOSA; LEIGHTON; SMITH, 2006). Em tais casos, há uma correspondete de 1-para-1 entre
3.5 Atualizações Resultando em Documentos Válidos
40
rótulos de elementos e estados no autômato correspondente ao modelo de conteúdo. Portanto, com o método descrito acima seria possı́vel encontrar a localização precisa de uma
atualização sem validar o documento e sem armazenar nenhuma informação auxiliar.
41
4
Adaptação de Dados
O processo de adaptação de dados é responsável por formatar os dados do documento
fonte de acordo com o DTD do banco de dados alvo. Isto é feito por duas razões principais:
(1) assegurar que o banco de dados resultante da atualização seja válido (deve-se notar
que em geral é necessário também revalidar o banco de dados depois da atualização), e
(2) facilitar o processo de descoberta de âncora, que é bastante dependente dos tipos de
nós nas árvores sendo casadas, conforme a notação de DTD.
Essencialmente, nosso processo de adaptação de dados encontra um mapeamento entre
os tipos, ou rótulos 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 correspondências
entre tais tipos, o qual é usado para traduzir os dados de entrada de acordo com o DTD
alvo. Para isto, nosso método explora a similaridade de conteúdo entre instâncias de
diferentes tipos, assim como restrições semânticas e estruturais, como discutido a seguir.
4.1
Mapeamentos na Adaptação de Dados
O mapeamento utilizado na adaptação de dados é uma função que mapeia os tipos
do documento fonte s com DTD Ds no banco de dados t com DTD Dt . Na Figura 12 um
exemplo de mapeamento é mostrado. Observe, entretanto, que um nó folha pode ocorrer
como filho de vários elementos distintos. Por exemplo, no DTD Dt da Figura 12, o elemento title pode conter valores de tı́tulos de filmes (movie) ou tı́tulo de crı́ticas (review)
sobre o filme. Isto gera confusão no mapeamento, e conseqüentemente, na tradução dos
elementos. Para diferenciar os valores de cada tipo de elemento em casos como esse, os tipos são definidos não apenas pelo rótulo no DTD (ex., title), mas também 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́ definido pela
4.2 Casamento de Tipos
42
Figura 12: Mapeamento entre os grafos DTD de Ds e Dt .
Figura 13: Rede bayesiana para combinação dos componentes de similaridade
seqüência de rótulos de elementos no caminho de r até e. Por exemplo, o contexto de title
no DTD Dt da Figura 12 pode ser movie ou movie/review. De agora em diante, os tipos
considerados no mapeamento são definidos pelo rótulo 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
são considerados apenas os tipos de nós folhas (elementos simples e atributos), os quais
apresentam conteúdo textual. Sejam A e B tipos do documento fonte s com DTD Ds
e do banco de dados t com DTD Dt , respectivamente. A similaridade entre A e B é
medida usando dois componentes principais: a similaridade de conteúdo (C (A, B )) e a
similaridade de rótulos (L(A, B )) entre eles. A similaridade de conteúdo estima a extensão
da sobreposição 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 rótulo estima quão próximos são os rótulos de A e B (e de seus ancestrais).
Os escores de similaridade são modelados como probabilidades e combinados no modelo formal de redes bayesianas (PEARL, 1988) como segue (veja a Figura 13). A similaridade final entre A e B, denotada por F (A, B ), depende da similaridade de conteúdo e de
43
4.2 Casamento de Tipos
rótulo entre eles. Além disso, a similaridade de conteúdo 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 através de um operador disjuntivo or (·, ·), também
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 nó pai (C e
L) pode ativar F , ou seja, aumentar significantemente seu escore final. Este operador é
particularmente útil 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 disjuntivo é definido como segue:
or (x, y) = 1 − ((1 − x) · (1 − y))
onde x e y são probabilidades.
Similaridade de conteúdo
Nós textuais e numéricos são tratados diferentemente para calcular o escore C. Para
elementos e atributos numéricos, uma abordagem simples porém efetiva é utilizada: assumindo que os valores numéricos do tipo B seguem uma distribuição gaussiana, a similaridade entre A e B é definida como o valor médio da função densidade de probabilidade para
cada valor em nós do tipo A. A função densidade foi adaptada para retornar 1 quando
um valor é igual a média ou uma fração, caso contrário. Isto foi feito normalizando-se
a função pela densidade máxima, que é justamente atingida quando um valor é igual a
média. Portanto, o escore de conteúdo para elementos e atributos numéricos é definido
como segue:
C (A, B) =
1 X − (v−µ)2 2
e 2σ
|A| v∈A
onde σ e µ são o desvio padrão e a média, 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 conteúdo dos nós textuais é calculada combinando-
44
4.2 Casamento de Tipos
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 baseadas 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 através da porção de palavras em
comum compartilhadas por eles. Assume-se que o conteúdo de B é representativo com
relação ao domı́nio de seu tipo; ou seja, a maioria dos termos em valores de A podem
ser encontrada em B também, se eles são correspondentes. Note que o inverso não é
necessariamente verdade; ou seja, a similaridade de conteúdo pode ser assimétrica. Intuitivamente, a similaridade de termos entre A e B deve ser alta se a sobreposição de termos
entre o conteúdo de A e B é alta, e os termos em A que ocorrem em B são tı́picos nos
valores dos nós do tipo B (veja abaixo). Mais precisamente, define-se:
!
X wk (A)
Y
1
K(A, B) =
+1−
1 − wk (B)
2 k∈A∩B wtotal (A)
k∈A∩B
(4.1)
onde wk (A) e wk (B) são os pesos do termo k relativa aos tipos A e B, respectivamente;
P
e wtotal (A) = wk (A)∀k ∈ A.
O primeiro componente da Equação 4.1 é uma soma normalizada de pesos das palavras
em A ∩ B. A similaridade máxima é dada quando A ∩ B = A, e a mı́nima quando
A ∩ B = ∅. O termo de ponderação wk (A) é calculado pelo esquema de ponderação
bastante conhecido, TF-IDF (BAEZA-YATES; RIBEIRO-NETO, 1999), privilegiando a alta
sobreposição com palavras que são raras no documento de entrada mas comuns nos valores
dos nós do tipo A:
Ns
wk (A) = tf k (A) · log 1 +
att(s, k)
onde tf k (A) é a freqüência do termo k entre os valores de A, Ns é o número total de tipos
no DTD de entrada Ds e att(s, k) é o número de nós no documento fonte contendo k. Em
outras palavras, wk (A) será mais alto se k é freqüente em valores de A e não aparece em
muitos elementos do documento s.
O segundo componente da Equação 4.1 combina a chance de cada termo em nós do
tipo A ser um termo tı́pico no conteúdo de B, usando o operador disjuntivo. Este operador
45
4.2 Casamento de Tipos
permite que um único 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 nós do
tipo B e em nenhum outro tipo do banco de dados. Este conceito é similar ao esquema
TF-IDF. Entretanto, ao contrário do TF-IDF tradicional, o termo de ponderação wk (B)
retorna um valor no intervalo [0, 1], o qual é modelado como uma probabilidade:
log(val(B, k))
log(att(t, k))
wk (B) =
· 1−
log(VB )
log(Nt )
onde val(B, k) retorna o número de nós do tipo B onde k ocorre em seu conteúdo textual,
VB é o número total de nós do tipo B, att(t, k) é o número de nós em t contendo k em
seu valor textual e Nt é o número total de tipos diferentes de nós em t.
Similaridade baseada em valor
Enquanto a similaridade baseada em palavras-chave funciona bem quando há pouca ou
nenhuma sobreposição de valores exatos entre o conteúdo de A e B, a similaridade baseada
em valor tira vantagem desta sobreposição. Intuitivamente, a similaridade baseada em
valor entre A e B é alta se muitos valores do conteúdo de A são encontrados no conteúdo
de B. A contribuição de cada valor em A ∩ B para similaridade final é proporcional ao
número de nós de A, ou seja, 1/log(|A|), que é combinada por um operador de disjunção.
Assim define-se:
V (A, B) = 1 −
Y
v∈A
1−
ov (B)
log(|A|)
onde ov (B) é 1 se o valor v ocorre em pelo menos um nó do tipo B, ou 0 caso contrário;
e |A| é o número de elementos do tipo A.
Dois valores são considerados iguais se eles contém exatamente as mesmas palavraschave. Para acelerar a computação, representamos cada valor por uma assinatura MD5
do conjunto de suas palavras-chave. É necessário notar que palavras muito comuns (stopwrods) não são consideradas palavras-chave, portanto não são incluı́das nas assinaturas
dos valores.
Similaridade de rótulo
A similaridade de rótulo L(A, B) entre A e B é computada levando em consideração
seus ancestrais. Os rótulos não são comparados diretamente; em vez disso são usados
os radicais das palavras e algumas heurı́sticas simples para extrair palavras-chave rele-
46
4.2 Casamento de Tipos
vantes dos rótulos. Por exemplo, “running time” é representado por {“run”, “time”}. O
conjunto de palavras-chave de um tipo é chamado de descritor de rótulo.
A similaridade entre um par de descritores de rótulo é estimada usando a versão
“soft” da medida do cosseno no modelo espaço-vetorial, denominado soft TF-IDF (COHEN; RAVIKUMAR; FIENBERG, 2003). Diferentemente da medida do cosseno tradicional,
o softTF-IDF relaxa necessidade de casamento exato entre as palavras-chave e alcança
melhores resultados em nosso contexto. O modelo softTF-IDF considera também palavras
similares usando uma segunda medida de similaridade para palavras-chave. Desta forma,
dadas duas palavras-chave de rótulo 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 contrário.
Para calcular a similaridade de rótulo, 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 maxb′ ∈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) =
P
w(a, A) · w(b, B) · s(a, b)
(a,b)∈close(θ,A,B)
rP
a∈A
w(a, A)2 ·
rP
w(b, B)2
b∈B
onde w(a, A) e w(b, B) é o peso de palavras-chave de rótulo a e b com relação ao tipos A
e B, respectivamente.
Dois fatores são levados em consideração para calcular o peso de uma palavra: (1) o
nı́vel do elemento cujo rótulo contém a palavra-chave, ou seja, o número de elementos no
caminho do nó raiz até ele, e (2) quão raro é a palavra-chave entre os tipos de elementos
no esquema correspondente. Intuitivamente, uma palavra-chave de mais baixo nı́vel, que
ocorre no rótulo de um nó folha, melhor descreve um tipo que uma palavra-chave de nı́vel
mais alto, que ocorre no rótulo do nó raiz, por exemplo. Além disso, um rótulo que ocorre
em apenas um único 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 fração dos descritores de rótulo que contém a no esquema
correspondente.
4.3 Encontrando mapeamentos
47
Figura 14: Mapeamento entre os grafos DTD de Ds e Dt , 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 próximo
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 série de experimentos preliminares, onde testamos a qualidade dos mapeamentos com alguns valores de
limiar, definimos em nosso trabalho o valor 0,5. A partir de uma computação par a par, é
construı́do um multi-mapeamento de tipos (MELNIK; GARCIA-MOLINA; RAHM, 2002) M,
que é a relação 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 são considerados.
Além disso, para atributos textuais, exige-se que seu tamanho seja compatı́vel. Intuitivamente, isto evita casar, por exemplo, um tipo contendo crı́ticas de filmes com outro que
contém 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 comentários. Portanto, considerando um tipo de elemento textual X, seja X̂ a distribuição
dos tamanhos dos valores em nós do tipo X, seja E(X̂) a média de X̂ e std(X̂) o desvio
padrão de X̂. B é somente considerado como um candidato plausı́vel para A somente
se a diferença entre a média dos valores de Â e B̂ esteja dentro do desvio padrão de B̂.
Mais precisamente, exige-se que |E(Â) − E(B̂)| ≤ max(std(B̂), ε), onde ε é um limiar de
tolerância. Em nossos testes percebemos que ε = 1.5 funciona bem na prática.
Pares conflitantes
Outra restrição imposta é que M não contenha pares conflitantes, como segue. Sejam
X e Y tipos de Ds , X ′ e Y ′ tipos de Dt e lca(X, Y ) o ancestral comum mais baixo no
contexto (ver Seção 4.1) de X e Y . Dois pares de mapeamento (X, X ′ ) e (Y, Y ′ ) são
conflitantes se Ds permite mais de uma ocorrência de elementos dos tipos X e Y como
4.3 Encontrando mapeamentos
48
descendentes de lca(X, Y ), porém Dt não 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 são 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 geração de elementos redundantes, em particular os
elementos do tipo movies (lca(X ′ , Y ′ )). Isto acontece pois o tipo film(lca(X, Y )) pode
ter como descendentes vários elementos dos tipos keyword e comments provenientes do
documento de entrada; entretanto, como Dt não permite mais de um elemento do tipo
description por filme, para “acomodar” os múltiplos elementos traduzidos como description
precisamos duplicar os elementos movie e todos os seus descendentes, inclusive os vários
elementos paragraph. Isto resulta numa grande redundância de dados, que poderia ser
ainda maior se houvessem mais pares conflitantes.
Portanto, é necessário remover do multi-mapeamento os pares conflitantes que contribuem com escore mı́nimo de similaridade agregada entre Ds e Dt . Na realidade, este
é um problema de otimização NP-completo. Considere do problema de encontrar a cobertura de vértices de peso mı́nimo (GAREY; JOHNSON, 1979) em um grafo G = (V, E),
onde vértices são associados com pesos positivos. O problema consiste em encontrar a
cobertura de V , ou seja, VC ⊆ V tal que todas as arestas em E incidem num vértice de
VC , 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
configuração onde pares em M correspondem a vértices 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 são ordenados comparando-se seus escores
individuais contra a soma dos escores dos pares que estão em conflito com eles, removendo o par com menor valor. Este processo é repetido até que não existam mais pares
conflitantes.
A partir do multi-mapeamento, nosso objetivo é extrair um mapeamento final µ que
associa tipos de Ds em tipos de Dt . Note que, diferente de M, µ é uma função. Além
disso, como de costume (RAHM; BERNSTEIN, 2001), exige-se que µ seja injetiva; ou
seja, cada tipo de s é mapeado no máximo 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 até que
todos os tipos possı́veis sejam mapeados.
4.4 Traduzindo Instâncias
4.4
49
Traduzindo Instâncias
Uma vez que o mapeamento é definido, traduzir a instância de Ds em uma instância
de Dt se faz necessário. Os dados de entrada são achatados, ignorando tipos de elementos
que não estão no mapeamento, e publicados de acordo com o DTD alvo. Nosso algoritmo
de publicação é baseado nas técnicas path outer union e hash-based tagging de Shanmugasundaram et al. (2001).
Mais precisamente, a árvore de entrada s é achatada numa relação R(A1 , . . . , An ),
onde cada Ai corresponde a um tipo de Ds mapeado a um tipo de Dt . Caminha-se em
s numa busca em profundidade; cada vez que é encontrado um nó folha l cujo tipo é
mapeado (ou seja, pertence a R), todos os nós internos e1 , . . . , em situados no caminho
da raiz de s até l são identificados. Neste ponto uma tupla é adicionada a R contendo os
valores de todos os nós folhas mapeados que são descendentes de algum ei , contanto que
cada nó destes seja a única ocorrência descendente de ei permitida por Ds . Elementos e/ou
nós folhas ausentes são representados como valores null para as colunas correspondentes
de R. Observe que fazendo isto todos os dados da instância fonte que pode ser mapeada
são armazenados em R.
A produção da árvore XML traduzida é feita da seguinte forma. Primeiro, um elemento XML não ordenado ti é gerado para cada ri ∈ R, certificando-se de evitar a geração
de sub-árvores duplicadas, o que é feito mantendo-se uma tabela hash com os valores que
já foram mapeados. As árvores XML ordenadas finais devem ser válidas de acordo com o
modelo de conteúdo associado com o tipo de ti em Dt . Em outras palavras, a árvore deve
produzir uma palavra que é gerada pela expressão regular em Dt . Portanto, dado um nó
interno ei em ti , e o autômato de Glushkov G para o modelo de conteúdo associado com
ei em Dt , é necessário produzir uma palavra wi que é: (1) aceita por G, e (2) contem
tantos filhos de ei quanto possı́vel.
Isto é feito como segue. Vendo G como um grafo direcionado, obtém-se uma árvore
geradora mı́nima MCAG , a partir do qual o menor caminho p em G é encontrado, tal
que: (1) p começa no estado inicial de G e leva a um estado final; (2) p contém tantos nós
correspondentes ao tipos mapeados (ou seja, tipos em R) quanto possı́vel. Isto pode ser
feito caminhando em MCAG de trás pra frente a partir dos estados finais. Cada caminho
é verificado(há um número linear deles), mantendo-se o caminho com o maior número de
tipos mapeados nele. Se dois caminhos tem o mesmo número de tipos mapeados, o mais
longo é descartado. Isto resulta em uma palavra válida wi de acordo com G. O passo
4.4 Traduzindo Instâncias
50
final é substituir os elementos em wi com aqueles que foram mapeados pela adaptação de
dados, de acordo com seus tipos. Se mais de um elemento mapeado existe para o mesmo
elemento em wi , um deles é escolhido arbitrariamente.
Exemplo 6 Considere o autômato de Glushkov da Figura 11; a árvore geradora teria os
laços dos nós qb e qa2 removidos. Observe que há três possı́veis caminhos que poderiam
ser usados para produzir conteúdo válido: I → qa1 , I → qa1 → qb , e I → qa1 → qc → qa2 .
Esses correspondem a seguinte seqüência de elementos XML: a, a b, e a c a, respectivamente.
Valores ausentes
O processo acima resulta numa seqüência de elementos XML formando conteúdo XML
válido para os nós internos correspondentes (ei ). Entretanto, é possı́vel que ele contenha
elementos que não correspondem a nenhum tipo mapeado pela adaptação de dados. Semelhantemente, é possı́vel que alguns elementos apresentem atributos obrigatórios que
não são mapeados pelo nosso algoritmo de adaptação de dados. Em tais casos, precisa-se
adicionar valores padrões apropriados como conteúdo de tais elementos e atributos. Para
elementos textuais e atributos ausentes seus valores são definidos como “unknown”. Para
atributos ID, um número único é inserido (por exemplo, mantido por um contador) para
evitar a produção de conteúdo inválido. Para nós complexos, o processo discutido acima é
repetido; ou seja, encontra-se uma seqüência mı́nima de elementos que leva a um elemento
válido, e itera-se sobre os elementos dessa seqüência.
Exemplo 7 A Figura 8(b) mostra o ancoramento do filme da Figura 3(b). Observe que
o atributo @country foi adicionado ao elemento rating; porque nenhum paı́s está definido
no documento, o valor padrão foi usado no conteúdo mapeado.
Árvore geradora mı́nima
Historicamente, o problema de encontrar a árvore geradora mı́nima em grafos direcionados é chamado de problema de minimum-cost arborescence (KLEINBERG; TARDOS, 2005).
No nosso contexto, o grafo é o AFD do modelo de conteúdo de um dado tipo de elemento
no DTD do banco de dados. Este problema é resolvido usando-se o algoritmo clássico de
Chu and Liu (também proposto independentemente por Edmonds), descrito em (KLEINBERG; TARDOS, 2005). Uma questão é associar os pesos às arestas do grafo; isto pode ser
4.4 Traduzindo Instâncias
51
feito como segue: (1) arestas que não foram rotuladas com um tipo pelo mapeamento da
adaptação de dados recebem um custo arbitrariamente alto; (2) arestas que foram rotuladas com tipos pelo mapeamento da adaptação de dados recebem um custo proporcional
ao número de tuplas em R para os quais foram associados o valor null. Fazendo isso,
garante-se que todos os nós correspondentes aos tipos mapeados foram mantidos na árvore
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 implementação direta do algoritmo acima é possı́vel em tempo de processamento
O(|E||V |), onde E e V são o conjunto de arestas e vértices no grafo. Pelo fato do tamanho
dos autômatos de Glushkov serem limitados polinomialmente ao tamanho das expressões
regulares, este algoritmo é eficiente na prática.
52
5
Descoberta de Âncora
Neste capı́tulo o procedimento para computar o ancoramento da árvore XML s à
árvore XML t é apresentado (como brevemente descrito em Seção 3.3). Observe que, por
s ser uma árvore XML resultante do processo de adaptação de dados, ambos s e t são
formatados de acordo com o DTD alvo DT .
Nossa semântica conservadora (Seção 3.4.2) impõe que os ancoramentos produzidos
sejam completos e não ambı́guos. Ou seja, é necessário encontrar um ancoramento que é
na verdade uma função A : s → t tal que se A(e) = e′ , então todas as seguintes condições
são mantidas. Primeiro, e e e′ devem ter tipos (rótulos) idênticos. Segundo, e e e′ devem
ser suficientemente similares. Diferentes noções de similaridade são definidas para nós
folhas e para nós 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, não há e′′ 6= e′
em t que satisfaça todos estes requisitos acima.
5.1
Algoritmo de Descoberta de Âncora
Nosso algoritmo funciona em dois passos. Primeiro, o algoritmo opera ancorando
de cima pra baixo todos os pares de nós (e, e′ ) com o mesmo tipo. Quando os nós
folhas são alcançados, o sentido é invertido, onde os nós ancorados inicialmente que não
exibem suficiente similaridade com nenhum nó, ou são similares a mais de um nó, são
desancorados. A similaridade de dois nós folhas depende somente de seus conteúdos,
enquanto a similaridade de dois nós internos leva em consideração todos seus descendentes.
Além disso, se um nó é similar a dois ou mais nós, ele não é ancorado, para evitar
ambigüidade. 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 número de elementos
que precisam ser comparados, portanto melhorando grandemente o desempenho do nosso
método. De fato, um algoritmo puramente de cima para baixo começaria comparando
todos os nós folhas em s com todos os nós folhas em t, o que é desnecessário e caro.
5.1 Algoritmo de Descoberta de Âncora
53
Procedure: ancorar (e, C )
Input: nó XML e, e o conjunto de nós 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 distância(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 âncora.
De agora em diante, o tipo de um nó e é denotado por τ (e). Para uma discussão mais
concreta, o algoritmo será 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 árvore alvo t os quais são candidatos
para serem ancorados a e. Na prática, C é usado para “focar” o processo de ancoramento,
tal que nós evitamos tentar casar cada nó em s com cada nó em t. Na primeira chamada
ao algoritmo, e é a árvore de entrada s, e C o conjunto de todos os nós na árvore alvo t,
permitindo portanto que s ancore a qualquer nó em t.
O primeiro passo ao ancorar e é identificar aqueles elementos em C cujos tipos
(rótulos) são iguais ao de e (⋆). Em nosso exemplo, inicialmente e seria o elemento
genre da Figura 8(a); portanto, nós iteramos através de todos os elementos genre em t.
Dada a árvore de entrada e e uma árvore 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 consideração apenas os tipos
(rótulos) dos nós a serem ancorados. Entretanto, quando um nó folha é encontrado, o
5.2 Similaridade de Nós Internos
54
algoritmo é revertido para determinar a similaridade entre os nós de baixo para cima.
Inicialmente, o algoritmo compara a similaridade de dois nós folhas; se o seus conteúdos
são considerados suficientemente similares, eles são ancorados (≀). Dois nós folhas e e a
são ditos similares se a distância de edição 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 nós internos é utilizada para decidir
se eles devem ser ancorados ou não. Neste estágio, o algoritmo determina se o nó corrente
e em s não é similar ao outro nó em t ou se é similar a mais de um nó em t, o que resultaria
num ancoramento ambı́guo. Em ambos os casos, o nó não 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 está na fase de baixo pra cima, não haverá outra
tentativa para ancorar e. Isto pode ser ilustrado pelo nosso exemplo na Figura 8(a): pelo
fato do elemento movie em s não ser similar ao movie em t, ele é mantido não ancorado,
tentando-se em seguida ancorar o elemento genre através de seus outros nós descendentes,
em particular o atributo @name.
5.2
Similaridade de Nós Internos
O cerne do processo de descoberta de âncora é a função sim (e, a), que mede a similaridade entre dois nós internos e e a, considerando também a similaridade de seus
descendentes. Nossa medida de similaridade é baseada no DogmatiX (WEIS; NAUMANN,
2005), um arcabouço independente de domı́nio para detecção de duplicatas. Intuitivamente, a similaridade de duas sub-árvores e e a depende do numero de folhas em e e a
que concordam uma com a outra, e o número de de folhas em e e a que descordam uma
da outra.
Seja E≈ o conjunto de todos os pares (l, l′ ) de nós que concordam um com outro; ou
seja, l é um nó folha em e, l′ é um nó folha em a e A(l) = l′ . (Note que quando dois nós
internos estão sendo ancorados, todos os nós folhas descendentes deles que eram realmente
similares já foram ancorados.) Além disso, seja E6= o conjunto de pares (l, l′ ) de nós folhas
que descordam um do outro. E6= é construı́do pareando cada nó folha não ancorado em
e com um nó escolhido não ancorado arbitrariamente escolhido de a, contanto que eles
sejam do mesmo tipo e nenhum nó de e ou a pertence a mais de um par em E6= .
55
5.2 Similaridade de Nós Internos
A similaridade entre e e a é definido como segue:
sim (e, a) =
w(E≈ )
,
w(E≈ ) + w(E6= )
onde w(E) mede quão seletivos são os valores dos pares em E. Intuitivamente, uma
concordância (resp., discordância) com nós folhas contendo valores muito seletivos (ex., os
tı́tulos de filmes) são melhores indicadores de similaridade que uma concordância (resp.,
discordância) de folhas que envolvem valores mais comuns (ex., nomes de estúdio). A
freqüência inversa do documento é usada como medida de seletividade:
X
|T (e)|
w(E) =
log
,
cnt(e) + cnt(e′ )
′
(e,e )∈E
onde T (e) é o conjunto de elementos do tipo τ (e) no banco de dados alvo, e cnt(e) é o
número de elementos de T (e), cujo valor textual é o mesmo de e.
56
6
Avaliação Experimental
Para avaliar nosso arcabouço de atualização livre de esquema, as operações de atualização foram implementadas em um protótipo usando Java. Experimentos foram conduzidos sobre bancos de dados XML construı́dos usando dados publicamente disponı́veis na
Web de quatro domı́nios: cinema, música, livros e artigos cientı́ficos. A Figura 16(a) mostra o tamanho e a URL de cada um dos nossos bancos de dados de teste. Os tamanhos são
medidos em termos de “objetos de dados” representados nos bancos de dados, como filmes
e álbuns, e os diferentes tipos (rótulos) de elementos de acordo com o DTD. Os banco de
dados de livros e artigos são amostras aleatórias do arquivo XML da DBLP, preservandose a estrutura original. O banco de dados de música 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
número de tipos de elementos similares que eles apresentam. Intuitivamente, dois tipos
são considerados similares se os seus conteúdos se intercalam. Por exemplo, no banco
de dados de cinema, valores de elementos ator, diretor e escritor são dificilmente
discriminados até mesmo por humanos. Por isso, este banco de dados foi considerado
complexo. Outros exemplos de elementos similares são descriç~
ao e sinopse. Outro
banco de dados complexo é o de música, por causa dos elementos similares artista,
álbum e trilha. Os bancos de dados restantes foram considerados simples porque não
apresentam elementos similares.
Em termos gerais, os experimentos simulam a atualização dos banco de dados de
teste usando dados provenientes de um RSS Feed ou de dados extraı́dos de páginas Web
usando um extrator automático. Três conjuntos de objetos foram gerados para cada
domı́nio. O conjunto Existente contém 10 objetos que já existiam no banco de dados
correspondente. O conjunto Novo é formado por 10 objetos que não existem no banco de
dados correspondente. Finalmente, o conjunto União, como o nome sugere, é a união dos
57
6.1 Adaptação de Dados
Banco de dados
Cinema
Música
Livros
Artigos
Objetos
8,914
14,966
1,211
8,000
Tipos
19
4
19
13
Site
Complexidade
Complexo
Complexo
Simples
Simples
http://imdb.com
http://musicbrainz.org/doc/Database
http://dblp.uni-trier.de/xml/
http://dblp.uni-trier.de/xml/
(a) Bancos de dados alvos.
Documentos
Cinema
Música
Livros
Artigos
Tipos Usados/Total
10/77
4/40
4/5
4/6
Site
http://movies.yahoo.com
http://www.pandora.com
http://books.google.com
http://www.sigmod.org/record/xml/
Formato Original
HTML
RSS
HTML
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 fração dos tipos usados nas atualizações pelo total de tipos presentes nos documentos
fontes.
6.1
Adaptação de Dados
Antes de apresentarmos os resultados experimentais sobre os conjuntos de dados usados para avaliação do nosso arcabouço de atualização (Novo, Existente e União), avaliaremos nosso processo de adaptação de dados de forma independente. O objetivo dos
experimentos a seguir é avaliar a qualidade do mapeamento produzido pelo método. Neste
contexto, precisão e revocação são calculados como segue. Seja MR e MF o conjunto de
pares de mapeamento obtidos respectivamente por um especialista e pelo nosso método
de adaptação de dados. Os valores de precisão (P ), revocação (R) e medida-f (F ) são
calculados respectivamente como: P =
||MR ∩MF ||
,
||MF ||
R=
||MR ∩MF ||
||MR ||
eF =
2×P ×R
.
P +R
Nos experimentos a seguir a acuidade dos mapeamentos é medida usando a medida-f,
que combina precisão e revocação e é comumente usada nos experimentos de Recuperação
de Informação (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 precisão e 0,92 de revocação).
Isto significa que, na média, nosso método escolheu menos de um par 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 adaptação de dados foi estudada com as di-
6.1 Adaptação 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 são chamados de combinado, conteúdo, palavraschave, valores e rótulos nesta seção. Observe que o escore K (palavras-chave) também é
considerado para similaridade numérica, ao contrário de V (valores).
Efetividade do escore combinado da adaptação de dados
A Figura 6.1 mostra a acuidade média do mapeamento de esquemas para diferentes medidas de similaridade. Para cada domı́nio, foram usados 50 documentos fontes com 10
objetos de dados diferentes em cada um, e nosso método de adaptação de dados foi usado
com diferentes medidas de similaridade. Como o gráfico mostra, o método combinado
que propomos (Seção 4.2) supera todos as medidas de similaridade individuais (palavraschave, valores e rótulos); isto é particularmente evidente para os domı́nios mais complexos
em nossos testes: cinema e música. É importante notar que a similaridade de conteúdo,
que é uma combinação os escores de palavras-chave e valores, obteve resultados muito
próximos ao escore combinado. Isto mostra que nosso método é efetivo mesmo quando
os esquemas a serem mapeados são completamente dissimilares (em termos de rótulos de
elementos).
59
6.1 Adaptação de Dados
1
Medida−f
0.8
0.6
0.4
combinano
conteúdo
palavras−chave
valores
rótulos
0.2
0
1
5
10
15
20
25
Tamanho do documento de entrada
30
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 número elevado
de objetos necessário para realizar os testes. Entretanto, espera-se que os resultados relativos sejam mantidos para os outros bancos de dados. A Figura 18 compara a efetividade
no método de adaptação de dados com tamanhos variados do documento de entrada; cada
plotagem mostra a acuidade média de 20 rodadas, cada uma com uma amostra diferente
de objetos nos documentos fontes. Observe que novamente o método combinado supera os
outros, particularmente para os documentos menores, ou seja, quando atualizando poucos
dados. A queda na qualidade da abordagem baseada em rótulos é devido ao fato que mais
elementos opcionais estão presentes em amostras maiores.
Impacto no tamanho do banco de dados
A Figura 19 mostra como os escores do método de similaridade combinado variam em
função do número de objetos de dados no banco de dados. Cada plotagem mostra a acuidade média 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 método de adaptação de dados se comporta muito bem independente
do tamanho do banco de dados para os domı́nios mais simples (artigos e livros) dos nossos
testes, que são predominantes na Web. Para os bancos de dados mais complexos, como
esperado, a acuidade do método melhora quando mais objetos de dados são mantidos no
60
6.1 Adaptação de Dados
1
0.95
Medida−f
0.9
0.85
0.8
0.75
0.7
Artigos
Livros
Cinema
Música
0.65
0.6
50
250
500
750
Tamanho do banco de dados
1000
Figura 19: Impacto do tamanho do banco de dados.
banco de dados.
1
Medida−f
0.8
0.6
0.4
combinado
conteúdo
palavras−chave
valores
rótulos
0.2
0
0
5
10
15
Número de atributos indesejados
20
Figura 20: Tolerância a ruı́do.
Tolerância a ruı́do
A Figura 20 mostra o impacto que elementos indesejados (ou seja, que não tem correspondentes no banco de dados) nos documentos têm sobre a acuidade do nosso método,
usando o banco de dados de cinema. Cada plotagem é a média de 20 rodadas, cada uma
com 10 filmes. Inicialmente apenas elementos cujos tipos (rótulos na notação do DTD)
tem um tipo correspondente no banco de dados, depois outros tipos de elementos que
não tem um tipo correspondente no banco de dados são progressivamente adicionados ao
6.1 Adaptação 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 entrada tem um tipo correspondente no banco de dados, como mostra a Tabela 16(b),
onde apenas 10 tipos são realmente usados para atualizar o banco de dados de filmes. É
bastante provável que este comportamento se repita para o banco de dados de música,
onde alcançamos bons resultados mesmo com apenas quatro tipos usados na atualização
contra 40 no total. Não é possı́vel repetir este experimentos para os domı́nios de livros e
artigos, uma vez que os documentos fonte não apresentam quantidade suficiente de tipos
indesejados.
Avaliação do arcabouço de atualização
A seguir são apresentados os resultados do processo de adaptação de dados sobre os
12 conjuntos de dados usados para avaliação do nosso arcabouço de atualização, a saber,
Novo, Existente e União, de quatro domı́nios. A Tabela 1 apresenta os resultados do
processo sobre os conjuntos em análise. Nosso método funcionou quase perfeitamente no
conjunto Existente, o que era esperando uma vez que há uma grande sobreposição entre os
dados dos objetos deste conjunto com o banco de dados. O método também atingiu bons
resultados para o conjunto Novo, a despeito da pequena sobreposição de dados esperada
neste caso, que teve um impacto nos valores de revocação para os domı́nios de música e
artigos. Os resultados do conjunto União são tão bons quanto os resultados obtidos para
o conjunto Existente. Na verdade, o único resultado não perfeito foi o valor de precisão
para o banco de dados de filmes (0, 91), no qual apenas um, entre 11 mapeamentos, foram
incorretamente gerados. Isto significa que ocorrência de novos objetos não compromete a
qualidade geral do nosso método de adaptação de dados, como esperamos que aconteça
em situações práticas.
Para o conjunto União, a adaptação de dados resulta em 80 árvores 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
único par mapeado incorretamente como citado acima. Nós usamos estas 80 árvores nos
experimentos que seguem, os quais lidam com a acuidade da descobertade âncora.
62
6.2 Descoberta de Âncora
Existente
Bancos de dados
Cinema
Música
Livros
Artigos
P
0,9
1
1
1
R
1
1
1
1
Novo
P
1
1
1
1
R
1
0,75
1
0,80
União
P
0,91
1
1
1
R
1
1
1
1
Tabela 1: Qualidade da adaptação de dados.
6.2
Descoberta de Âncora
Avaliamos a qualidade do nosso algoritmo de descoberta de âncora através da comparação de seus resultados com ancoramentos manualmente gerados, os quais são considerados como corretos. Os resultados dos experimentos são dados em termos de precisão,
revocação e medida-f, definidos como segue. Seja AR um ancoramento perfeito e AF
o ancoramento obtido pelo nosso método. Os valores de precisão (P ), revocação (R),
e medida-f (F ) são respectivamente calculados como: P =
F =
||AR ∩AF ||
,
||AF ||
R =
||AR ∩AF ||
||AR ||
e
2×P ×F
.
P +F
Observe que para estas métricas serem úteis, AR e AF devem conter todos os elementos
da árvore de entrada, mesmo que alguns deles não sejam ancorados. Para lidar com essa
situação, os elementos não ancorados em um ancoramento são representados como pares
(e, null ), onde e é um elemento não ancorado.
A Figura 21 mostra a qualidade da descoberta de âncora expressada usando a média
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
método de descoberta de âncora é geral e estável 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 avaliação de qualidade da descoberta de âncora,
também usando medida-f. A coluna “Todos” considera todos os elementos, enquanto
as colunas “Simples” e “Complexos” consideram apenas elementos simples e complexos,
respectivamente. O método de descoberta de âncora apresentou um desempenho excelente
em todos os quatro domı́nios. Observe que eventuais erros em ancorar elementos simples
não comprometem o ancoramento de nós complexos, que são usualmente mais difı́ceis de
se lidar.
63
6.3 Qualidade das Operações Livre de Esquema
1
0.95
Medida−f
0.9
0.85
0.8
0.75
Cinema
Música
Livros
Artigos
0.7
0.65
0.6
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Limiar de ancoramento
Figura 21: Medida-f média da descoberta de âncora para vários valores como limiar de
ancoramento λ.
Cinema
Música
Livros
Artigos
Todos
0,96
0,98
0,95
0,95
Simples
0,97
0,98
0,94
0,92
Complexos
0,96
0,98
0,95
0,95
Tabela 2: Qualidade do ancoramento para elementos simples e complexos.
6.3
Qualidade das Operações Livre de Esquema
Apresentamos agora os resultados da avaliação de qualidade do nosso arcabouço em
produzir atualizações corretas em um banco de dados alvo D, conforme a intenção do
usuário que formulou a operação de atualização livre de esquema.
Para isto, considere uma instância I de D que reflete corretamente todas as edições
intencionadas envolvidas em alguma operação de atualização. Agora, considere outra
instância P que é resultado de aplicar as atualização sugeridas pelo nosso arcabouço. A
qualidade do nosso arcabouço é medida comparando-se quão distinto P é de I. Nossa
métrica é o esforço de reparar o banco de dados, definido como o número de edições
(inserções e remoções) necessários para converter P em I. Para este propósito, adaptamos
uma métrica às vezes utilizada para avaliar métodos de casamento de esquema (MELNIK;
GARCIA-MOLINA; RAHM, 2002). Esta métrica, chamada aqui de acuidade da atualização,
é detalhada abaixo.
6.3 Qualidade das Operações Livre de Esquema
64
Acuidade da Atualização
Sejam UP e UI conjuntos de edições necessárias para converter D em P e D em I, respectivamente. Portanto, o número de edições corretas é c = ||UP ∩ UI ||. A diferença (n − c),
onde n = ||UP ||, denota o número de edições aplicados a P que precisam ser desfeitos. De
forma similar, (m − c), onde m = ||UI ||, é o número de falso negativos, ou seja, edições
corretas que não foram aplicadas pelo nosso métodos. Por simplicidade, assume-se que
fazer ou desfazer uma edição requer o mesmo esforço, e que a verificação de um elemento
correto não tem custo. Se um usuário realiza cada edição em UI manualmente, então m
edições são necessárias. Portanto, o esforço do usuário é medido como a porção da “limpeza” manual necessária depois de aplicar a operação de atualização livre de esquema em
comparação a atualização completamente manual, como segue:
l=
(n − c) + (m − c)
m
A economia de esforço obtida usando-se uma operação de atualização livre de esquema
é estimada através da acuidade da atualização, definida como 1 − l. Numa atualização
perfeita, n = m = c, resultando em acuidade igual 1. Note que c/n e c/m correspondem
a precisão e revocação. Portanto, a acuidade da atualização pode ser expressa em função
da precisão e revocação como segue:
(n − c) + (m − c)
c n
=
2−
m
c
m
1
= Revocação 2 −
Precisão
Acuidade = 1 −
Na definição acima, a noção de acuidade faz sentido apenas se a precisão não é menor
que 0, 5, isto é, pelo menos metade das edições sugeridas pelo nosso método são corretas. Caso contrário, a acuidade é negativa. De fato, se mais da metade das edições são
incorretas, levaria mais esforço para o usuário desfazê-las e inserir os elementos ausentes
que fazer as edições manualmente desde o começo. Como esperado, a melhor acuidade 1
é obtida quando tanto a precisão e a revocação são iguais a 1.
Qualidade das operações livres de esquema
A qualidade das operações livre de esquema foi avaliada levando-se em consideração
possı́veis erros propagados da adaptação de dados e descoberta de âncora para a acuidade
final da qualidade de atualização. As árvores de entrada foram agrupadas de acordo com
65
6.3 Qualidade das Operações Livre de Esquema
os objetos descritos por elas (novos ou existentes) para melhor entender o comportamento
de cada operação de atualização em face de cada um desses casos.
A Tabela 3 mostra os valores de precisão (P), revocação (R) e acuidade de atualização
(A) para este experimento. Observe que as operações de inserção e remoção foram quase
perfeitas, atingindo mais de 0, 98 de precisão e revocação. A operação de fusão também
alcançou resultados muito bons, especialmente para novos objetos. Entretanto, a operação
de atualização apresentou uma acuidade muito baixa, afetando os resultado da operação de
fusão sobre objetos existentes. Estes resultados inexpressivos da operação de atualização
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 distância de edição. Entretanto, nós acreditamos que uma operação de atualização
dificilmente danifica o banco de dados por duas razões: (1) se um elemento a ser atualizado
é ancorado equivocadamente, nada é realizado; e (2) se nosso método falha em ancorar
um elemento, valores muito similares são substituı́dos um pelo outro. Por exemplo, em
nossos experimentos a operação de atualização substituiu incorretamente “United States
of America” por “United States” diversas vezes. Outro fato que poderia explicar estes
resultados é o baixo número de elementos a serem atualizados: menos de 20.
Existentes
Operações
Inserção
Atualização
Fusão
Remoção
P
0,99
0,55
0,88
0,98
R
1
0,72
0,9
0,98
A
0,99
0,11
0,76
0,95
Novos
P
1
–
1
–
R
1
–
1
–
A
1
–
1
–
Tabela 3: Acuidade das operações de atualização.
Bancos de dados
Cinema
Música
Livros
Artigos
Inserção
–
0,95
0,89
0,83
Atualização
0,99
1
1
1
Fusão
–
–
0,8
1
Remoção
1
1
1
1
Tabela 4: Correção da operação de atualização quando o banco de dados deveria permanecer inalterado.
Observe que operações de atualização e de remoção devem manter o banco de dados inalterados quando lidando com novos objetos. Portanto, não é possı́vel medir a sua
correção através das métricas usadas neste experimento (como indicado por traços na
Tabela 3). Além destes, houveram outros 64 casos (totalizado 144 de 320) em nossos
experimentos onde o banco de dados deveria também ser mantido inalterado. A maioria
6.3 Qualidade das Operações Livre de Esquema
66
desses casos foi devido a operação de inserção, atualização ou fusão sobre somente elementos ancorados na árvore de entrada. Nós medimos a correção nessas situações através da
porção de elementos na árvore de entrada que não foram usados para atualizar o banco
de dados. Mais precisamente, seja p o número de edições propostas e n o número de elementos na árvore de entrada; nós definimos a correção da operação de atualização como
(n − p)/n. A Tabela 4 mostra os resultados deste experimento para todas as operações em
cada domı́nio. Não houve nenhum caso em estudo com relação as operações de inserção
e fusão em Cinema, e fusão em Música (como indicado por traços na Tabela 4). Observe
que o comportamento das operações de atualização e remoção foi muito próximo a perfeição para todos os domı́nios. Apesar das operações de inserção e fusão apresentarem
correção variando de 0.8 a 0.95, um erro dessas operações, no pior caso, significa apenas
a inserção de dados redundantes.
67
7
Conclusão e Trabalhos Futuros
Este trabalho propôs um novo arcabouço livre de esquema para atualizar documentos XML. Este arcabouço é baseado em primitivas simples porém poderosas nas quais o
usuário simplesmente indica a operação desejada e indica os nós envolvidos nela. Como
tal, nosso arcabouço é muito mais adequado para usuário casuais e não especialistas que os
paradigmas atuais baseados em XQuery. Para ilustrar como essas primitivas poderiam ser
usadas na prática, propomos uma linguagem de atualização simples e intuitiva para especificar as operações de atualização envolvendo objetos de dados de entrada e um banco de
dados alvo com estruturas possivelmente diferentes. O objetivo principal da linguagem é
realizar operações sofisticadas sem requerer que o usuário 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 operação de atualização deveria ocorrer.
Uma semântica conservadora foi discutida para esta linguagem, na qual atualizações que
introduzem redundância são evitadas. O processo de tradução de instâncias XML de um
DTD para outro foi discutido em detalhes, de uma forma que sempre é gerado conteúdo
válido mesmo quando lidamos com valores ausentes. Discutiu-se também o algoritmo
de descoberta de âncora para identificar nós equivalentes nos documentos XML fonte e
alvo, de onde o local preciso das atualizações pode ser derivado. Nosso arcabouço é útil
por três razões: (1) ele é aplicável à dados reais da Web, (2) pode ser implementado de
forma simples (3) retorna comandos de atualização que podem ser facilmente traduzidos
para programas de atualização em outras linguagens, ou implementados diretamente num
sistema de armazenamento nativo de XML. Finalmente, resultados experimentais da implementação de um protótipo indicaram o grande potencial dos nossos métodos em dados
reais da Web de diferentes domı́nios.
Dada a importância e onipresença de XML, prover ferramentas de gerência de dados eficientes e acessı́veis que podem ser usadas por usuários não especialistas é uma
promissora área 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 Conclusão e Trabalhos Futuros
68
problemas de troca de dados e atualizações automáticas em XML. Esses problemas não
tem sido satisfatoriamente estudados na literatura; isto é verdade também no caso de
dados relacionais. Nosso trabalhos futuros incluem implementar completamente nossos
métodos num sistema real em produção, juntamente com consultas livres de esquemas
também. Também identificamos a necessidade de desenvolver técnicas mais robustas e
escaláveis para lidar com dados XML que oferecem a flexibilidade do paradigma “livre de
esquema”. Além disso, outras semânticas para as operações de atualização precisam ser
estudadas a fim de melhorar os resultados da atualização. Em particular, isto pode ser
feito definindo-se em quais cenários cada uma deve ser aplicada.
Outro trabalho futuro é adaptar nosso arcabouço para receber como entrada documentos com pouca ou nenhuma estrutura, como páginas da Web e texto plano (e-mail, classificados) ou semi-estruturado (currı́culos, endereços)’. Isto pode ser feito desenvolvendo-se
novas técnicas de adaptação de dados baseadas em ferramentas de extração de dados. É
possı́vel ainda desenvolver sistemas de reconhecimento de linguagem natural para atualização de bancos de dados XML baseados em nosso arcabouço. Neste caso, o desafio é
reconhecer no texto qual a operação (inserção, remoção) e os dados envolvidos na atualização.
69
Referências
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 Systems, v. 29, n. 4, p. 710–751, 2004.
BARBOSA, D.; LEIGHTON, 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.
BRÜGGEMANN-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 Mining.
[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 Information
Integration on the Web. [S.l.: s.n.], 2003. p. 73–78.
Referências
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: Language, 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 Éva. 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 flooding: 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.
Referências
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.
Download
Atualizaç˜oes Livres de Esquema em Bancos de Dados XML

Equipe - DCC/UFMG

PPT

- nddconnect

Atualizaç˜oes Livres de Esquema em Bancos de Dados XML

Equipe - DCC/UFMG

PPT

- nddconnect

Seminario

NF-e Validate

Apresentação em Power Point XML-SPC

- ArqNFe | w3F

T´ıtulo: Conteúdos para tablets do SENAI ser˜ao expostos

XML

ADRIANA NUNES TEIXEIRA
