CS276B
Text Retrieval and Mining
Winter 2005
Lecture 12
O que é XML?






eXtensible Markup Language
Um framework para definir linguagens de
marcação
Sem coleção fixa de marcadores
Cada linguagem XML orientada para a
aplicação
Todas as linguagens XML compartilham
característica
Permite a construção de ferramentas
genéricas
Estrutura básica



Um documento XML é uma árvore ordenada
e rotulada
Nós folha de dado textual contém os dados
reais (strings de texto)
Nós elemento, são rotulados com



Um nome (frequentemente chamados de
elemento type), e
Um conjunto de atributos, cada um
composto por um nome e um valor,
Pode ter nós filhos
Exemplo XML
Exemplo XML
<chapter id="cmds">
<chaptitle>FileCab</chaptitle>
<para>This chapter describes the commands
that manage the <tm>FileCab</tm>
inet application.</para>
</chapter>
Elementos






Elementos são denotados por tags de
marcação
<foo attr1=“value” … > o_texto </foo>
Tag inicial do elemento: foo
Atributo: attr1
O dado textual: o_texto
Tag final do elemento correspondente:
</foo>
XML vs HTML





HTML é uma linguagem de marcação para
um propósito específico (exibição em
browsers)
XML é um framework para definir linguagens
de marcação
HTML pode ser formalizado como uma
linguagem XML (XHTML)
XML define estrutura lógica apenas
HTML: mesma intenção, mas evoluiu para
um linguagem de apresentação
XML: Objetivos de projeto




Separar sintaxe da semântica para prover
um framework comum para estruturação da
informação
Permite marcação feita sob medida para
qualquer domínio de aplicação imaginável
Suporta internacionalização (Unicode) e
independência de plataforma
Ser o futuro da informação
(semi)estruturada (fazer algum do trabalho
feito atualmente por bancos de dado)
Por que usar XML?




Representa dados semi-estruturados (dados
são estruturados, mas não encaixam no
modelo relacional)
XML é mais flexível que BDs
XML é mais estruturado do que RI simples
Você recebe uma gigantesca infra-estrutura
de graça
XML Schemas



Schema = definição de sintaxe da linguagem
XML
Linguagem Schema = linguagem formal para
expressar schemas XML
Exemplos



Document Type Definition - DTD
XML Schema (W3C)
Relevância para RI com XML

Nosso trabalho é mais fácil se nós temos (um)
schema
Tutorial XML



http://www.brics.dk/~amoeller/XML/index.html
(Anders Møller and Michael Schwartzbach)
Os slides anteriores (e alguns dos seguintes)
são baseados neste tutorial
Indexação e Busca XML
Banco de Dados XML Nativo


Usa documentos XML como uma unidade
lógica
Deve suportar





Elementos
Atributos
PCDATA (parsed character data)
Ordem do documento
Contraste com


BD modificado para XML
Sistemas RI genéricos modificados para XML
Indexação e Busca XML

A maioria das bases de dados XML nativas
tem uma abordagem BD




Correspondência exata
Avaliar expressões de caminho
Nenhum tipo de rankeamento de relevância
da RI
Apenas alguns que focam rakeamento de
relevância
Data vs. Text-centric XML

Data-centric XML: usado para o envio de
mensagens entre aplicativos empresariais


Principalmente a reformulação de dados
relacionais
Content-centric XML: usado para anotar o
conteúdo



Rico em texto
Demanda boa integração da funcionalidade
de recuperação de texto
Ex., encontre os números ISBN de Livros com
pelo menos Capítulos discutindo a produção
de cacau, rankeado por Preço
Desafios de RI XML 1: Estatísticas
do Termo




Não há unicidade no documento em XML
Como computamos tf e idf?
tf/idf global sobre todo o texto do contexto
é inútil
Granularidade de indexação
Desafios de RI XML 2: Fragmentos


Sistemas RI não pontua conteúdo (apenas
índice)
Precisa ir ao documento para
recuperar/apresentar fragmentos



Ex., me dê os Resumos dos Papers em
existencialismo
De onde você recupera o Resumo?
Mais fácil no framework BD
Desafios de RI XML 3: Schemas

O ideal seria:



Na prática: raro





Existe um único schema
Usuário entende o schema
Muitos schemas
Schemas não são conhecidos com
antecedência
Schemas mudam
Usuários não entendem os schemas
Necessário identificar elementos similares
em diferentes schemas

Exemplo: autor e criador
Desafios de RI XML 4: UI

Ajudar usuários a encontrar nós no schema


Autor, editor, contribuídor, “de:”/remetente
Qual é a linguagem de consulta que você
expõe ao usuário?



Linguagem de consulta específica do XML?
Não.
Formulários? Busca parametrizada?
Um textbox?
Desafios de RI XML 5: usando um
BD

Por que você não quer usar um BD


BD não possui nenhuma noção de ordenação
Rankeamento de relevância
Consultando XML

Hoje apresentamos:



XQuery
XIRQL
Próximo

Abordagens do espaço vetorial
XQuery


SQL para XML
Senários de uso




Depende de




Documentos legíveis
Documentos orientados a dados
Documentos mistos (ex., registro de
pacientes)
XPath
XML Schema datatypes
Turing completa
XQuery ainda é um projeto
XQuery

As formas principais das expressões
Xquery são:







Expressões de caminho
Construtores de elementos
Expressões de lista
Expressões condicionais
Expressões quantificadas
Expressões de tipos de dado (datatype)
Avaliados com relação a um contexto
Consultas suportadas por
XQuery


Localização/posição (“capítulo 3”)
Atributo/valor simples


/book/author contém “Gates”
Consultas Path


author que contém “Gates”
/book//author que contém “hamlet”
XIRQL

University of Dortmund


Objetivo: mecanismo de busca XML open source
Motivação

Fragmentos “retornáveis” são especiais



Ex., não retorna um fragmento <bold> algum texto
</bold>
Princípio da Recuperação de Documentos Estruturados
Capacitar os usuários que não conhecem o schema


Ativar pesquisa para qualquer pessoa, não importando
como esquema codifica os dados
Não se preocupa com atributo / elemento
Indexação XIRQL
Unidades de indexação
Não são unidades coerentes
Princípio da Recuperação de
Documentos Estruturados



Um sistema deve sempre retornar a parte
mais específica de um documento,
respondendo a uma consulta.
Consulta de exemplo: xql
Documento:
<capítulo> 0.3 XQL
<seçãp> 0.5 example </seção>
<seção> 0.8 XQL 0.7 syntax </seção>
</capítulo>

Retorna seção, não capítulo
Aumento de ponto




Certifique-se que o Princípio de Recuperação
de Documentos Estruturados é respeitado.
Suponha que as condições de consultas
diferentes são eventos disjuntos ->
independência.
P(chapter,XQL) = P(XQL|chapter) + P(section|chapter) *
P(XQL|section) – P(XQL|chapter) * P(section|chapter) *
P(XQL|section) = 0.3 + 0.6 * 0.8 - 0.3 * 0.6 * 0.8 = 0.636
Seção é classificada à frente de capítulo
Datatypes



Exemplo: nome_pessoa
Atribuir todos os elementos e atributos com
semântica de pessoa para este tipo de dado
Permite que o usuário procure por “pessoa”
sem especificar o caminho
XIRQL: Resumo




Rankeamento de relevância
Seleção de fragmento/contexto
Datatypes (nome_pessoa)
Relativismo semântico

Atributo/elemento
Estruturas de dados para
recuperação XML
Uma introdução básica.
Estruturas de dados para
recuperação XML



Quais são as primitivas necessárias?
Índice invertido: me dê todos os
elementos que corresponde a consulta
de texto Q
Nós sabemos fazer isto – tratar cada
elemento como um documento


Me dê todos os elementos
(imediatamente) abaixo de qualquer
instância do elemento Book
Combinação das opções acima
Links Pais/filhos


Numera cada elemento
Mantém uma lista de relacionamentos paisfilhos



Ex., Capítulo:21  Livro:8
Permite pai imediato
Mas e sobre “a palavra Hamlet embaixo de
um elemento Scene embaixo de um
elemento Play”?
Índices posicionais gerais


Visualiza o documento XML como um documento
texto
Constrói um índice posicional para cada elemento

Marca o início e o fim de cada elemento, ex.,
Play
Doc:1(27)
Doc:1(2033)
/Play
Doc:1(1122)
Doc:1(5790)
Verse
Doc:1(431)
Doc:4(33)
/Verse
Doc:1(867)
Doc:4(92)
Term:droppeth
Doc:1(720)
Contenção posicional
Doc:1
Play
27
1122
431
Verse
Termo:droppeth
720
2033
5790
867
Contenção pode ser
visto como fusão de
postings.
droppeth embaixo de Verse embaixo de Play.
Resumo de estruturas de dados




Contenção de caminho etc. pode
essencialmente ser resolvido por índices
invertidos posicionais
Recuperação consiste de “fusão” de postings
Todos os truques de compressão etc. de
276A continuam a ser aplicáveis
Complicações surgem a partir da
inserção/exclusão de elementos, texto
dentro de elementos

Álem do escopo deste curso
Resources






Jan-Marco Bremer’s publications on xml and ir:
http://www.db.cs.ucdavis.edu/~bremer
www.w3.org/XML - XML resources at W3C
Ronald Bourret on native XML databases:
http://www.rpbourret.com/xml/ProdsNative.htm
Norbert Fuhr and Kai Grossjohann. XIRQL: A query
language for information retrieval in XML
documents. In Proceedings of the 24th International
ACM SIGIR Conference, New Orleans, Louisiana,
September 2001.
http://www.sciam.com/2001/0501issue/0501berner
s-lee.html
ORDPATHs: Insert-Friendly XML Node Labels.

www.cs.umb.edu/~poneil/ordpath.pdf