Universidade Federal de Campina Grande
Mestrado em Informática
Indexando XML
Banco de Dados e Internet - 2004
Professor: Cláudio Baptista
Mestrando: Rômulo Nunes
Conteúdo da Apresentação
– Necessidade de Indexação
 Indexação XML com Listas
 Indexação XML com Árvores
 As Pesquisas no mundo
 Conclusão
 Introdução
2
14:16
Necessidade de Indexação
 SGBDs
precisam buscar informações;
 XML são arquivos;
 Precisamos de um acesso rápido e
eficiente às informações;
 Quais as soluções existentes para esse
acesso eficiente e rápido?
3
14:16
Indexação XML usando Listas
 Indicada
para casos mais simples;
 Essa solução indexa apenas um nível
na árvore do documento;
 Tem um custo inicial com a ordenação
prévia da lista;
 É eficiente e mais barata dependendo
do contexto do sistema.
4
14:16
Indexação XML usando Listas
<?xml version="1.0" ?>
<agenda>
<contato Nome=”Ana Paula da Silva”>
Visualização do nível da
árvore que vamos indexar
<Endereço>
Rua Zacarias de Azevedo, 323 Prado
</Endereço>
<Telefone>
323-3310
</Telefone>
<Telefone>
...
9991-3817
</Telefone>
</contato>
...
<contato Nome=”Zelda Cavalcante”>
<Endereço>
Av. Monte Castelo,2522
</Endereço>
<Telefone>
231-2233
5
14:16
</Telefone>
<contato Nome=”Zelda Cavalcante”>
<Endereço>
Av. Fernandes Lima,2522
</Endereço>
<Telefone>
231-2233
</Telefone>
</contato>
</contato>
</agenda>
...
Indexação XML usando Listas
Contato 1
Contato 2
Contato 3
Contato n
...
Ana Paula
6
14:16
Cláudia
Débora
Zelda
Indexação XML usando Listas
Para ordenar uma lista basta aplicarmos qualquer método da
estrutura de dados.
O Método de Hoare, também conhecido como Quick Sort é um dos
mais rápidos.
Depois de Ordenado é fácil aplicar, por exemplo, o método de
busca binário para encontrar um determinado elemento da lista.
Problemas: Gasto com o tempo para organizar; Só atende a
estrutura XML para um nível; Não se pode aplicar esse método
para buscas complexas.
7
14:16
Indexação XML com Árvores
 Passos
a serem seguidos
 Codificar a árvore em uma sequênçia
estruturada (Structure-Encoded
Sequence)
 Codificar também a consulta
8
14:16
Exemplo de uma árvore XML
9
14:16
Consultas XML
10
14:16
Procurar todos
os fabricantes
que fornecem
itens
Procurar
compras com
Vendedor
Boston e
comprador NY
Procurar
compras com
Boston como
comprador ou
vendedor
Procurar
compras que
contêm
produtos intel
Uma representação sequencial dos
dados XML de uma árvore

11
14:16

Considere de v1 a v8 o conjunto de variáveis que
representam respectivamente cada valor folha da
árvore percorrida em pre-ordem.
Percorrendo a árvore em pre-ordem temos a
representação: PSINv1Mv2IMv3INv4Lv5Nv6BLv7Nv8
Sequência Estruturada Codificada

Uma sequência estruturada codificada é uma sequência de
tuplas do tipo (simbolo_atual, prefixo).
D = (a1,p1), (a2,p2), …, (an,pn)

Para a árvore do slide anterior temos:
D = (P,),(S,P),(I,PS),(N,PSI),(v1,PSIN),(M,PSI),(v2,PSIM),(I,PSI),
(M,PSII),(v3,PSIIM),(I,PS),(N,PSI),(v4,PSIN),(L,PS),(v5,PSL),
(N,PS),(v6,PSN),(B,P),(L,PB),(v7,PBL),(N,PB),(v8,PBN)

12
14:16
Percorrer a árvore em pre-ordem garante uma codificação onde
nós vizinhos sempre estarão próximos.
Sequência Estruturada Codificada

Consultas (incluindo consultas ramificadas, e
consultas com caracteres coringas ‘*’ ou ‘//’)
podem ser convertidos para uma sequência
estruturada codificada.
Exemplos

D = (P,),(S,P),(I,PS),(N,PSI),(v1,PSIN),(M,PSI),(v2,PSIM),(I,PSI),
(M,PSII),(v3,PSIIM),(I,PS),(N,PSI),(v4,PSIN),(L,PS),(v5,PSL),
(N,PS),(v6,PSN),(B,P),(L,PB),(v7,PBL),(N,PB),(v8,PBN)

Q2= /* Boston como vendedor e New York como comprador */
(P,),(S,P),(L,PS),(v5,PSL),(B,P),(L,PB),(v7,PBL)

Q3= /* Boston como vendedor ou comprador */
(P,),(L,*),(v5,P*L)
14
14:16
Problema
Um nó pode ter filhos parecidos:
 /A[B/C]/B/D
Faz consultas multiplas e o
resultado é a o conjunto união.
“(A,),(B,A),(C,AB),(B,A),(D,AB)”
A
B
15
14:16
A
B
A
B
B
U
C
D
C
D
Solução
 Uma
definição formal de uma
linguagem que dê suporte a
consultas com restrições.
 Ponto Principal: A indexação do
caminho
16
14:16
Árvore de Sufixos

17
14:16
A sequência estruturada
codificada é colocada em
uma árvore de sufixos.
Algoritmo de Busca Simples


Query:
(P, )(L,P *)(v2,P*L)


18
14:16

Ancestor-Descendant Relationships

D-Ancestorship: Relacionamento entre nós
no documento XML de origem. (pai – filho)


S-Ancestorship: Relacionamento para os nós
no sufixo da árvore (filho – pai e sobrinho – tios)


19
14:16
Essencial pra uma Consulta modelada
Existe entre qualquer dois nós num mesmo
documento.
Essencial para evitar operações de união (intrarecord)
RIST: Relationship Indexed Suffix Tree
 Indexamos
os nós da árvore de sufixos
por tuplas (Symbol, Prefix)
(Indexação por D-Ancestorship)
 Agora vamos marcar cada nó da árvore
de sufixos com (n ,size), onde n é a
número em pre-ordem do nó e size é o
numero de nós abaixo dele.
(Indexação por S-Ancestorship)
20
14:16
Marcando a árvore de sufixos

21
14:16
Cada nó tem uma
tupla (Symbol, Prefix)
 Cada nó é marcado
com (nx,sizex)
um nó x é
descendente de um nó
y se nx está no
intervalo [ny, ny+ sizey)
 Criar uma árvore trie
para os indices criados
Algoritmo RIST
22
14:16
Algoritmo RIST - Resumo

Diferente do Algoritmo de busca simples,
RIST pula para o nó que representa o
próximo simbolo ao invés de uma busca
inteira na sub-árvore.
 A estrutura indexada e também o algoritmo
de busca, são baseados em arvores trie.
 Uma árvore de sufixos é construida para
fazer apresentar as marcas dos nós. Mas ela
não é usada no algoritmo de busca.
23
14:16
VIST: Virtual Suffix Tree
 Motivação:
 RIST
usa um esquema de marcação
estática (preordem, tamanho ), que
evita o adicionamento de novos nós
dinamicamente.
 A árvore de sufixos é uma estrutura que
precisa está completamente carregada
em memória, o que torna RIST não
suportado pelos SGBDs.
24
14:16
Sinal de probabilidade
Probabilidade que x ocorra
dado que u ocorra é
denotado como p(u|x)
 Se x é parente de u, é fácil dizer
quem é p(u|x)
 Por exemplo,




25
14:16
p(Name|Buyer)=1
p(Subitem|Item)=.1
Então temos que:
 p(u|x) é conhecido já que u é parente
de x
Follow Set



26
14:16
Dado um nó x, follow(x) está
para todo nó que pode
suceder x na sequência
estruturada codificada.
follow(x) = u, v, w, y, z, 
Se y é qualquer elemento de follow(x),
então p(y|x) = p(y|d), onde d é parente
de y.
Testes
 Definição
 DBLP.
para os testes:
Cada registro corresponde a uma
publicação, e o tamanho médio de
sequencias estruturadas codificadas é 31.
 Xmark. Um único registro com uma grande
estrutura. Sub estruturas complexas e
cheias de nós.
27
14:16
Testes
DocId B+Tree
Ancestor B+Trees
Suffix Tree
100
90
80
70
60
50
40
30
20
10
0
DBLP
VIST
28
14:16
DBLP
RIST
XMARK
VIST
Tamanho do indice
(em MB)
XMARK
RIST
Tempo de construção do indice
(em MB)
As pesquisas no Mundo
Nas universidades do mundo:
University of St. Petersburg na Russia;
University of Singapore,
University Stanford
Nas universidades do Brasil:
Pesquisas de indexação XML para fins específicos
(bibliotecas digitais, sistemas de busca, ...)
E os grandes desenvolvedores dos SGDBs?
A IBM é quem mais se destaca com suas pesquisas.
O VISIT é um exemplo
29
14:16
Conclusão
 SGBDs
e sistemas que utilizam XML
tendem a se fortalecer com as técnicas
avancadas de busca;
 Muitas pesquisas na área estão se
consolidando em uma forma única e
ideal de busca;
30
14:16