%\documentclass[dvips,12pt]{amsart}
\documentclass[pdftex,12pt]{amsart}
\usepackage{amsmath}
\usepackage[portuges]{babel}
\usepackage{enumerate}

\usepackage{hyperref}
\def\hbref#1#2#3{\href{#1#2}{#3}}


\def\cwurl{http://www.inf.ufes.br/~raulh/ufes/teaching/courses/s.and.s/page/cw/}

\input{defport}
\input{deflogic}
\input{defseqs}
\input{deftrees}
\def\stb#1#2{\ensuremath{st.#1.b.#2}}
\def\xstb#1#2#3{\ensuremath{\stb#1#2=\langle#3\rangle}}
\def\xoldstb#1#2#3{\ensuremath{#1\in\stb#2#3}}

\def\stdin{\emph{stdin}}
\def\stdout{\emph{stdout}}
\def\tarball{\emph{tarball}}
\def\mailto#1{\href{mailto:#1}{#1}}
\title{Trabalho 2: \\ Indexa\c{c}\~ao em Disco \\
       Escarecimentos}

\author{Raul H.C. Lopes}
\def\radixsort{\emph{radix sort}}
\def\splitter{\emph{splitter}}
\def\quicksort{\emph{quick sort}}
\def\mergesort{\emph{merge sort}}
\def\prefsum{prefix sum}
\def\real{Real}

%\setcounter{page}{0}
%\setcounter{section}{0}
%\setcounter{subsection}{0}

\def\clang{linguagem \emph{C/C++}}
\def\hbuffertree#1{\href{http://www.brics.dk/RS/96/28/BRICS-RS-96-28.pdf}{#1}}
\def\hcomer#1{\href{http://portal.acm.org/citation.cfm?id=356776}{#1}}
\def\hprefixbtree#1{\href{http://portal.acm.org/citation.cfm?id=320530}{#1}}
\def\hlometbtree#1{\href{http://www.cs.duke.edu/~junyang/cps216/papers/lomet-2001.pdf}{#1}}
\def\hbtreecaches#1{\href{http://doi.ieeecomputersociety.org/10.1109/ICDE.2001.914847}{#1}}

\def\btreeprog{\textbf{Btree}}
\def\btreeplusprog{\textbf{BtreeX}}

\def\hbase{http://www.inf.ufes.br/~raulh/}
\def\cwd{ufes/teaching/courses/s.and.s/cw/2/}
\def\hcwtwo{\href{\hbase\cwd2.pdf}{\emph{TP2}}}
\def\hcwTwo{\href{\hbase\cwd2.pdf}{\emph{Trabalho Pr\'atico 2}}}

\begin{document}

\maketitle

\section{Os algoritmos de indexa\c{c}\~ao}
O objetivo fundamental do \hcwTwo\ consiste em exercitar o processo de
constru\c{c}\~ao de \'{\i}ndices residentes em disco para bases de dados, cujas
chaves de indexa\c{c}\~ao s\~ao strings de tamanho vari\'avel. Antes de mais
nada \'e preciso atentar para os seguintes fatos:
\begin{itemize}
	\item Essa situa\c{c}\~ao ocorre freq\"uentemente no trabalho di\'ario
		de bancos de dados.
	\item Em situa\c{c}\~oes pr\'aticas os conjuntos de dados a indexar
		s\~ao normalmente muito maiores do que a mem\'oria RAM
		dispon\'{\i}vel e \textbf{n\~ao} \'e razo\'avel assumir
		que \'e possivel manter o \'{\i}ndice ou os arquivos de
		dados a indexar em mem\'oria. 
\end{itemize}

O trabalho consiste fundamentalmente em construir dois programas diferentes 
para indexa\c{c}\~ao de textos.
Os dois programas construir\~ao \'{\i}ndices obrigatoriamente baseados em 
\btree. O primeiro programa, \btreeprog, 
usar\'a em sua implementa\c{c}\~ao uma das varia\c{c}\~oes  de \btree,
descrita na se\c{c}\~ao \textbf{6.2.4} de \cite{dek:taocp:iii} ou em
\cite{cormen:lrs:algo}. 

Em seu segundo programa, \btreeplusprog, 
voc\^e tentar\'a obter uma \btree\ que seja eficiente em termos uso
de espa\c{c}o em disco, redu\c{c}\~ao de acessos a disco e tempo
de pesquisa dentro de um n\'o.

Os problemas fundamentais do \hcwtwo\ s\~ao:
\begin{itemize}
	\item As bases de dados a indexat s\~ao textos que n\~ao podem residir 
		em mem\'oria.
	\item As chaves de indexa\c{c}\~ao s\~ao palavras dos textos e como tal
		t\^em tamanho vari\'avel, embora se possa asumir um limite
		m\'aximo para cada um em torno de algumas centenas de
		car\'ateres.
\end{itemize}



\section{\'Indice baseado em \btree\ simples}\label{btree:basics}
A alternativa mais simples para a implementa\c{c}ao do
programa \btreeprog\ usar\'a consiste em usar uma variante obrigatoriamente um \'{\i}ndice baseado em 
alguma variante de \btree, descrita 
descrita na se\c{c}\~ao \textbf{6.2.4} de \cite{dek:taocp:iii} ou em
\cite{cormen:lrs:algo}. \'E importante levar em conta que:

\begin{itemize}
	\item Suas chaves s\~ao strings de tamanhos vari\'aveis: pode haver 
		palavras a indexar com um caracter e palavras com cem
		caracteres. Para superar esta dificuldade voc\^e pode, como
		descrito em \cite{dek:taocp:iii}:
		\begin{itemize}
			\item Armazenar nos n\'os refer\^encias para
				ocorr\^encias de palavras, em vez das pr\'oprias
				palavras;
			\item Fixar o espa\c{c}o dispon\'{\i}vel por n\'o para
				as chaves, mas permitir que cada uma delas ocupe
				espa\c{c}o vari\'avel. Neste caso, o split
				do n\'o ocorre quando n\~ao existe mais
				espa\c{c}o dispon\'{\i}vel para a nova chave.
		\end{itemize}
	\item Seu \'{\i}ndice e seus documentos residir\~ao necessariamente
		em disco.
\end{itemize}

\subsection{\'Indice baseado em \btree\ para strings}\label{btree:plus}
O programa \btreeplusprog\ usar\'a obrigatoriamente um \'{\i}ndice baseado em 
alguma variante de \btree, definida em
um dos artigos:
\begin{itemize}
	\item \hcomer{Refer\^encia b\'asica} sobre \btree\ e varia\c{c}\~oes;
	\item A b\'{\i}blia \cite{dek:taocp:iii};
	\item \hprefixbtree{Prefix B-tree};
	\item \hlometbtree{Evolu\c{c}\~ao de estudo de caches}.
\end{itemize}

A op\c{c}\~ao mais  interessante aqui \'e a \emph{simple prefix b-tree}, 
descrita nas se\c{c}\~oes um e dois de \hprefixbtree{Prefix B-tree}. A proposta
ali apresentada consiste em ter:
\begin{itemize}
	\item Uma \btree\ com chaves que podem ser prefixos das chaves reais dos
		textos indexados: essas chaves s\~ao \emph{separadores ou
		particionadores} do espa\c{c}o de pesquisa.
	\item Um arquivo de \'{\i}ndice com as chaves reais.
\end{itemize}

Note que no extremo esta alternativa pode ser implementada atrav\'es de dois
arquivos, que formam o \'{\i}ndice, e os textos a indexar. Os dois arqivos
de \'{\i}ndice constituiriam o que o artigo 
\hprefixbtree{Prefix \btree} chama de representa\c{c}\~ao de \emph{simple
prefix B-tree} em um \emph{$B^\ast$-tree}.

Note que a \btree\ tem como \'unico objetivo particionar  o espa\c{c}o de
pesquisa. O arquivo com as chaves reais indicaria que chaves est\~ao sendo 
indexadas e todas as suas ocorr\^ecias no texto.

Por exemplo, considere que existe um \'unico texto e que ele cont\'em as
palavras: \emph{on,part,problem,solution,prototype.} Assuma
inser\c{c}\~ao na ordem de apresent\c{c}\~ao. Ap\'os a inser\c{c}\~ao das
duas primeiras o \'{\i}ndice ficaria com a estrutura:
$$([on] o [part])$$

A inten\c{c}\~ao da representa\c{c}\~ao acima \'e indicar que na \btree\ existe 
apenas a raiz com a palavra (de um caracter) ``o''. \`A esquerda est\'a uma
folha, contendo ``on'' e \`a direita uma folha contendo ``part''. As duas folhas
poderiam estar armazenadas em um arquivo (ou sistema de arquivos) separado que 
al\'em de indicar a chave indicaria todas as suas ocorr\^encias em textos.
Finalmente, note a palavra ``o'' que fica na raiz: ela \'e o menor prefixo de
uma chave que separa que est\~ao \`a esquerda e \`a direita.

Ap\'os a inser\c{c}\~ao da pr\'oxima palavra o \'{\i}ndice fiacria:
$$([on] o [part:problem])$$

Note que o uso do caracter ``:'' como delimitador de chaves. 
Assuma agora que cada
folha comporta no m\'aximo 16 bytes. A inser\c{c}\~ao da pr\'oxima chave 
demanda um split produzindo:

$$([on] o [part] pa [problem:solution])$$

Decis\~oes importantes a tomar:
\begin{itemize}
	\item tamanho dos n\'os das folhas;
	\item tamanho dos n\'os internos da \btree: a raiz da \'arvore cima
		j\'a cont\'em tr\^es bytes ocupados com caracteres de
		separadores de chaves e 
		mais bytes para delimitadores e refer\^encias para os n\'os.
\end{itemize}

Uma representa\c{c}\~ao razo\'avel para o n\'o interno da \btree\ seria
\begin{itemize}
	\item um vetor de caracteres, que conteria as palavras que formam
		separadores delimitadas por
		caracters que n\~ao ocorrem no texto: nulo por exemplo.
	\item um vetor de inteiros com as refer\^encias para os n\'os filhos.
\end{itemize}

Assumindo que a raiz n\~ao comporta mais nenhum separador, a inser\c{c}\~ao 
pr\'oxima chave produz:
$$( ([on] o [part]) pa ([problem] prob [prototype:solution]) )$$

\bibliographystyle{amsplain}
\bibliography{abbrev,general,program,simulation,co,algorithms,compgeo,formal,maths}

\end{document}

