Uma Estratégia baseada em Técnicas de KDD

8/2/2019 Uma Estratgia baseada em Tcnicas de KDD

1/15

Uma Estratgia baseada em Tcnicas de KDD para apoiar oProjeto Fsico em SGBDs XML Nativos

Miriam Oliveira dos Santos1, Ronaldo Goldschmidt2, Maria Cludia Cavalcanti1

1Instituto Militar de Engenharia (IME)Pa Gen Tiburcio, 80 Praia Vermelha Urca

CEP 22.290 270 Rio de Janeiro RJ Brasil

2Instituto Superior de Tecnologia do Rio de Janeiro (ISTCC-RJ FAETEC)Rua Clarimundo de Melo, 847 Quintino Bocaiuva

CEP 21.311 280 Rio de Janeiro RJ Brasil

{mosantos,rribeiro,yoko}@ime.eb.br

Abstract. Technological advances have contributed for an expressive increase

of Web information, in terms of volume and diversity. Much of this information

is organized as XML documents and come from many different sources.

Content management for heterogeneous XML documents does not provide

efficient mechanisms for guiding the storage of these documents, in such a way

that facilitates their retrieval. Therefore, this paper presents a strategy based

on Knowledge Discovery and Data Mining to guide the storage of

heterogeneous XML documents. A case study and a performance comparative

analysis illustrate the potential of the proposed strategy.

Keywords: semi-structured data, database physical design, knowledgediscovery, data mining

Resumo. Os avanos tecnolgicos tm contribudo para um expressivo

aumento do volume e da diversidade de informaes que circulam atualmente

pela Web. Muitas dessas informaes encontram-se organizadas em

documentos XML e provm de vrias fontes. O gerenciamento de contedo

envolvendo documentos XML heterogneos carece de mecanismos que

orientem o processo de armazenamento desses documentos, de forma a

facilitar sua posterior recuperao. Assim sendo, este artigo apresenta uma

estratgia baseada em princpios de Descoberta de Conhecimento e

Minerao de Dados para orientar o processo de armazenamento de

documentos XML heterogneos. Um estudo de caso e uma anlise

comparativa de desempenho ilustram o potencial da estratgia proposta.

Palavras-chave: dados semi-estruturados, projeto fsico de banco de dados,

descoberta de conhecimento, minerao de dados

1. Introduo

Os avanos tecnolgicos ocorridos sobretudo na ltima dcada tm contribudo para umexpressivo aumento do volume e da diversidade de informaes que circulamatualmente pela web. So inmeras e heterogneas as fontes de dados, assim como osdispositivos de sada a que tais informaes se destinam. Diante desse cenrio,mecanismos de gerenciamento de contedo [Pereira e Bax 2002] que apiem acaptao, organizao e distribuio de informao corporativa vm assumindo papel de

XII Simpsio Brasileiro de Banco de DadosSBBD 2007

300


2/15

extrema importncia nas organizaes modernas. Os Sistemas de GerenciamentoEletrnico de Documentos (GEDs) e os Sistemas Gerenciadores de Bancos de Dados(SGBDs) so exemplos de recursos voltados ao gerenciamento de contedo. Os GEDs

tm sido utilizados no armazenamento, localizao e recuperao de informaes noestruturadas, e atendem a categorias especficas de documentos. Os SGBDstradicionais, por outro lado, tm sido aplicados na gesto de informaes estruturadas erequerem portanto, a definio de estruturas de dados prvias. No entanto, h umademanda crescente no sentido de que os GEDs e SGBDs se voltem para ogerenciamento de documentos semi-estruturados e heterogneos, que vm sendorepresentados atravs da linguagem XML.

O interesse em monitorar diferentes fontes de informaes est presente emvrias reas, entre as quais podem ser citadas: prospeco tecnolgica, governo,comrcio eletrnico, aplicaes de marketing, integrao de redes de notcias, servios

de alfndega. O governo, por exemplo, atravs da Receita Federal, tem interesse emconfrontar as informaes declaradas no imposto de renda com outros documentos, embusca de dados conflitantes. Para isto, a Receita Federal deve ter acesso a diferentesinformaes dos contribuintes disponibilizadas em diferentes fontes, formatos e emdiferentes contextos. Muitas destas informaes podem ser encontradas em formatoXML, que devido sua flexibilidade quanto forma de representao, tem sidoamplamente adotado em diversas reas.

O gerenciamento de contedo envolvendo documentos XML heterogneoscarece de mecanismos que orientem o processo de armazenamento desses documentos,de forma a facilitar sua posterior recuperao. Vrias das abordagens encontradas naliteratura [Abiteboul et al. 2005], [Flesca et al. 2005], [Yang et al. 2005], [Nierman e

Jagadish 2002] e [Lee et al. 2001] propem solues voltadas para acervos com baixograu de heterogeneidade, onde a inteno extrair um esquema nico. J [Li et al.2004], embora facilite a formulao de consultas sobre documentos heterogneos, noprov soluo para o armazenamento destes documentos. Assim sendo, este artigo temcomo objetivo propor uma estratgia baseada em princpios de Descoberta deConhecimento e Minerao de Dados para orientar o processo de armazenamento dedocumentos XML heterogneos, separando-os em grupos mais homogneos.

O presente trabalho est organizado da seguinte forma. Na Seo 2,descrevemos brevemente algumas das abordagens atuais para o armazenamento eclassificao de documentos XML, discutindo alguns trabalhos relacionados. Na Seo

seguinte, apresentamos uma proposta de estratgia para apoiar o projeto fsico emSGBDs XML Nativos, a partir da aplicao de tcnicas de KDD. A Seo 4 apresentao prottipo implementado. As Sees 5 e 6 apresentam um estudo de caso e umadiscusso sobre os resultados obtidos. Por fim, a Seo 7 conclui o artigo.

2. Tcnicas e Abordagens Relacionadas

As duas principais abordagens para o armazenamento de documentos XML envolvemSGBDs relacionais e SGBDs XML Nativos. Em geral, nos SGBDs relacionais oarmazenamento consiste na fragmentao do documento em diversas tabelas atravs detcnicas de mapeamento. No mapeamento direto, tabelas especficas so criadas a partir

dos elementos (tags) e atributos do documento XML [Vieira 2002]. J no mapeamentoindireto existem estruturas genricas que armazenam o contedo dos elementos e


301


3/15

atributos presentes em qualquer documento XML [Florescu e Kossmann 1999], [Tian etal. 2002] e [Vieira 2002]. Uma das desvantagens do mapeamento direto a necessidadede se criar uma estrutura especfica, enquanto que no mapeamento indireto, mesmo que

no seja preciso a criao de estruturas especficas, ainda h a necessidade de umconhecimento prvio do esquema genrico adotado (no necessariamente padro).

J nos SGBDs XML Nativos [Schning 2001],[Jagadish et al. 2002] e [Brian2006], os documentos so armazenados sem que haja necessidade de se realizarmapeamentos. Os SGBDs XML Nativos, prprios para o armazenamento destacategoria de documentos, oferecem maior flexibilidade em relao aos SGBDsrelacionais tradicionais, porque no h obrigatoriedade da definio de umesquema. Osdocumentos so armazenados dentro de colees que so repositrios de documentosXML. No h restrio para os tipos de documentos armazenados em uma mesmacoleo, que pode conter documentos com diferentes estruturas.

Embora estas alternativas ofeream solues para o armazenamento dedocumentos XML, elas no consideram o tratamento de um acervo de grandespropores de documentos XML heterogneos. Neste sentido, procura-se por soluesde armazenamento que sejam mais eficientes, como por exemplo realizar um tratamentoprvio deste acervo, classificando e/ou agrupando seus documentos.

KDD (Knowledge Discovery in Databases) definido por [Fayad et al. 1996]como um processo de vrias etapas, no trivial, interativo e iterativo, para identificaode padres compreensveis, vlidos, novos e potencialmente teis a partir de grandesconjuntos de dados. A descoberta de conhecimento em bases de dados composta portrs etapas operacionais: pr-processamento, processamento ou minerao de dados e

ps-processamento. A etapa de pr-processamento responsvel pela captao,organizao e tratamento dos dados. A etapa de processamento ou minerao de dados responsvel pela busca efetiva de conhecimento atravs da aplicao de algoritmos deminerao. A etapa ps-processamento responsvel pela avaliao e pela aplicao doconhecimento obtido [Goldschmidt e Passos 2005].

Diversas abordagens baseadas em KDD tm sido propostas para tratamento deconjuntos de documentos XML heterogneos. Em [Abiteboul et al. 2005], [Flesca et al.2005], [Yang et al. 2005], [Nierman e Jagadish 2002] e [Lee et al. 2001] proposta acriao de um esquema nico a partir da percepo da similaridade entre osdocumentos. Em alguns destes trabalhos so descritas tcnicas para preparar osdocumentos XML para minerao de dados atravs da equiparao terminolgica dostermos presentes nos documentos. Entretanto, a idia de derivar um esquema nico apartir de um acervo heterogneo de documentos pode se tornar uma tarefa difcil, se noinvivel, dependendo do grau de heterogeneidade do mesmo. Em [Li et al. 2004] proposta uma estratgia para se trabalhar com colees heterogneas, baseada naformulao de consultas a diferentes esquemas que mantenham contedos similares.Diferente da nossa estratgia neste caso, os documentos no so agrupados porsimilaridade, permanecendo nas unidades de armazenamento originais, e portanto, semos benefcios do armazenamento em separado e da indexao, que agilizariam asconsultas.

Neste trabalho, propomos uma estratgia que envolve o uso de tarefas de KDD,

como clusterizao, sumarizao e associao, no sentido de minimizar aheterogeneidade dos documentos, atravs da separao do acervo em grupos mais


302


4/15

homogneos. Em [Lian et al. 2004], a clusterizao dos documentos tambm utilizada,porm com objetivo diferente. Neste caso, a clusterizao realizada atravs da anliseda hierarquia dos termos para minimizar o problema de fragmentao em bancos de

dados relacionais.3. Estratgia Proposta

Como j citado anteriormente, este trabalho tem como objetivo encontrar mecanismosque auxiliem o armazenamento e recuperao mais eficiente de documentos XMLheterogneos em SGBDs XML Nativos, propondo uma estratgia para armazenamentoe indexao destes documentos. A estratgia proposta se utiliza das informaes obtidascomo resultado do processo de KDD sobre a estrutura dos documentos XML e sobre osrecursos existentes nos SGBDs XML Nativos de modo a guiar o usurio nodesenvolvimento do projeto fsico.

Conforme exposto na seo 2, o processo de KDD apresenta trs etapas.Inspirada nesta organizao, a estratgia proposta tambm se divide nestas trs etapasconforme ilustra a Figura. 1. Estas etapas envolvem desde a captao e tratamento dedocumentos XML at o armazenamento dos mesmos.

Figura 1. Etapas da Estratgia Proposta

Apesar dos documentos XML poderem estar associados a estruturas quegarantam uma certa uniformidade, vale ressaltar que nossa estratgia parte dopressuposto que os documentos provm de origens distintas, o que nos leva a terdocumentos com estruturas heterogneas.

Para alcanar o objetivo geral proposto neste trabalho, existem dois objetivos

especficos que esperamos atingir por meio destas etapas que so: o armazenamento emseparado de documentos similares e a criao de ndices adequados para agilizar o


303


5/15

futuro acesso a tais documentos. Nas subsees seguintes apresentaremos odetalhamento das etapas que compem a estratgia proposta.

3.1 Pr-processamentoNa etapa de Pr-processamento foram identificadas trs sub-etapas que visam extrairinformaes sobre os documentos para a etapa central, denominada Processamento. Aetapa de Pr-processamento inicia-se a partir da anlise da estrutura dos documentosXML. A estrutura destes documentos composta por etiquetas, denominadas tags. Cadaetiquetapode ser vista como um termo que indica ou descreve a natureza da informaopor ela encapsulada. Um dos objetivos deste trabalho verificar a similaridade entreos documentos que na estratgia proposta, baseia-se na utilizao destes termos pelosdocumentos. Por isso, deste ponto em diante, a palavra termo ser utilizada no lugar dapalavra etiqueta, isto , os termos tratados pelas sub-etapas que compem a etapa depr-processamento so provenientes das etiquetas dos documentos XML.

Na sub-etapa de Equiparao de termos, inicialmente preciso identificar todosos termos distintos presentes em todos os documentos. A seguir, no sentido deminimizar a no uniformidade no conjunto de termos utilizados, substitui-se os termosequivalentes por um termo representante, reduzindo a quantidade de termos a tratar.Desta forma, evitamos diferenciar documentos similares s por que utilizam termosdiferentes, ignorando que os mesmos tm igual significado. Isto pode ser resolvidousando-se um vocabulrio controlado de termos denominado tesauro [UNESCO 1973].Os algoritmos de matching constituem uma alternativa para a integrao de termos dediferentes bases de dados de forma automatizada [Shvaiko e Euzenat 2005 ] .

A sub-etapa de Limitao de termos, consiste em restringir a quantidade determos a serem analisados. Em KDD a limitao de termos realizada pela funo deSeleo de dados, atravs da reduo de dados vertical, que tem como objetivo eliminaratributos pouco relevantes [Goldschmidt e Passos 2005]. A limitao de termos tambmpode ser realizada pelas tcnicas conhecidas como startword e stopword [Kelledy eSmeaton 1997] e [Brasil 2004]. Enquanto a tcnica de startword indica que termosdevem ser considerados, a tcnica stopwordindica que termos devem ser ignorados. Deforma a facilitar a escolha dos termos para execuo de uma destas tcnicas, calcula-sea quantidade de vezes que os termos ocorrem nos documentos atravs de uma atividadedenominada ranqueamento de termos.

A sub-etapa de Preparao da matriz de dados consiste na criao de uma matriz

de dados apropriada para clusterizao, seguida da normalizao dos dados que acompem. A matriz composta por valores numricos associados ao cruzamento decada termo referenciado por cada documento. Estes valores resultam da anlise dapresena dos termos na estrutura dos documentos podendo representar a sua ocorrnciae/ou frequncia. A matriz de ocorrncia de termos composta por 0s e 1s, para oscasos de ausncia ou presena de um termo em um documento. J a matriz defreqncia de termos informa o nmero de vezes em que um termo aparece em umdocumento. H ainda uma terceira abordagem que pode ser considerada na anlise daestrutura do documento XML. Nesta abordagem, leva-se em considerao a hierarquiado termo no documento e pode-se calcular a sua freqncia ou ocorrncia. Estaabordagem permite uma maior preciso se tivermos como objetivo identificardocumentos estruturalmente e hierarquicamente similares, pois os documentos, alm deserem compostos pelas mesmas tags, tm que ter estas tags aninhadas em uma mesma


304


6/15

estrutura hierrquica para serem considerados similares. Neste caso, a matriz construda para cada par de termos (pai-filho). No entanto, no caso de documentosheterogneos e consequentemente com estruturas diferentes, a aplicao direta de uma

matriz hierrquica dificultaria identificar documentos similares.Os valores constantes na matriz que ser submetida sub-etapa de Clusterizao

devero ser normalizados. Existem alguns mtodos de normalizao disponveis, comodocumentado em [Goldschmidt e Passos 2005]. Neste trabalho adotamos o mtodo denormalizao pelo valor mximo dos elementos. Este mtodo consiste em dividir cadavalor do termo que esteja sendo normalizado pelo maior valor dentre os valores de taltermo. Ao final da normalizao utilizada, todos os valores estaro entre 0 e 1.

3.2 Processamento

Na etapa de Processamento, a idia encontrar grupos de documentos XML similares

para facilitar sua distribuio por diferentes unidades de armazenamento e aindaidentificar possveis candidatos indexao.

A sub-etapa de Clusterizao voltada para identificar grupos de documentossimilares. A matriz construda na etapa anterior submetida ao algoritmo declusterizao. A abordagem adotada para clusterizao de documentos heterogneosprope o uso do algoritmo fuzzy k-means [Goldschmidt e Passos 2005]. O algoritmo

fuzzy k-means um algoritmo de clusterizao que permite que um objeto pertena amais de um grupo com diferentes graus de pertinncia [Rosa 2001]. Utilizando-se destaabordagem, possvel identificar documentos que compartilhem caractersticas comunscom documentos de mais de um grupo. Cada grupo identificado sugere uma unidade de

armazenamento contendo documentos similares.Aps a clusterizao concluda, os documentos apresentam graus de pertinncia

a todos os clusters. Por isto, na sub-etapa de Verificao de Pertinncia que os gruposso definidos de fato. Os graus de pertinncia apresentados variam, o documento podeser mais ou menos pertinente a um clusterdo que a outro. Neste caso, preciso definir,previamente, um limiar mnimo de pertinncia a ser considerado.

A sub-etapa Verificao de Homogeneidade analisa se os documentos quecompem cada cluster formam um grupo homogneo. Este tipo de anlise deve serrealizada, pois nem sempre conhecida a quantidade de contextos distintos, de ondeprovm os documentos. Por isso, no possvel em um primeiro momento determinar a

quantidade de clusters adequada. A partir de uma quantidade de clusters inadequada,pode-se resultar em grupos mal formados, como por exemplo um grupo que contenhasubgrupos. Assim, mesmo que o usurio tenha uma idia de quantos clusters devem serformados, necessrio validar se o cluster homogneo. Isso pode ser feito pela anlisedos graus de pertinncia dos documentos que compem o cluster. Dado um cluster C, seo maior grau de pertinncia subtrado do menor grau de pertinncia dos documentos quecompem o cluster, for menor ou igual a um limiar de homogeneidade , previamentedefinido pelo usurio, ento o cluster C homogneo, seno o cluster C heterogneo.

No caso de ter sido verificada a heterogeneidade de pelo menos um cluster,volta-se sub-etapa de Clusterizao. A Clusterizao deve ser refeita, incrementando-se a quantidade de clusters. Cabe ressaltar que o processo deve ser refeito para todos osdocumentos e no apenas para os documentos pertencentes ao cluster em que foi


305


7/15

constatada a heterogeneidade. A sub-etapa de Sumarizao permitir descrever ocontedo de cada cluster.

Por fim, a sub-etapa de Associao ir identificar termos freqentes que poderoser utilizados para escolha de candidatos a ndices. Tal identificao se d atravs deduas abordagens: termos independentes (1 a 1 e/ou 2 a 2), e termos hierarquicamentedependentes (pai-filho). No caso da abordagem de anlise dos termos independentes montada uma matriz no formato basket[Goldschmidt e Passos 2005]. No contexto destetrabalho, cada documento ser identificado como uma transao e cada termo seridentificado como um item. Aps a matriz no formato basket ter sido criada sorealizadas duas atividades inspiradas no funcionamento do algoritmo clssico deminerao de regras de associao chamado Apriori [Goldschmidt e Passos 2005]: Aformao de conjuntos de 1 elemento, responsvel por identificar termos que ocorramfrequentemente e a formao de conjuntos de 2 elementos gerados pela combinao dos

termos resultantes da atividade anterior (conjuntos de 1 elemento), dois a dois, queatendam a um suporte mnimo, previamente estabelecido pelo usurio. Com isso soobtidas combinaes de termos que aparecem de forma conjunta e freqente nosclusters do acervo de documentos. Tais combinaes podem ser consideradas pelousurio da aplicao como alternativas de ndices a serem criados.

3.3 Ps-processamento

Na etapa Ps-processamento, o usurio guiado na elaborao de um projeto fsico debanco de dados com base nas informaes geradas nas etapas anteriores somado aosrecursos normalmente oferecidos por SGBDs XML Nativos. Nesta etapa so definidasquantas Unidades de Armazenamento (UAs) sero necessrias para o armazenamento

dos documentos, de que tipos devem ser e os ndices que devem atuar sobre as mesmas.Na sub-etapa de Definio de Armazenamento, inicialmente define-se o tipo e a

quantidade de UAs que sero necessrias para armazenar os clusters criados. Aprincpio, a quantidade mnima de UAs corresponde a quantidade de clustersestabelecida. A quantidade mxima de UAs depende de outros fatores que vo desde acapacidade de armazenamento de cada UA a estratgias diferenciadas que podem seraplicadas de acordo com as caractersticas dos documentos. A anlise da UA quanto estratgia de armazenamento avalia os recursos que o SGBD XML Nativo oferece. Porexemplo, h SGBDs que orientam que documentos muito grandes sejam armazenadosde forma fragmentada, enquanto documentos pequenos sejam armazenados de forma

contgua, sem que haja a fragmentao.Em seguida, define-se quais metadados sero associados aos documentos. Alm

da referncia ao documento original (que nesta estratgia transformado para permitir aidentificao de similaridades), h outras informaes que podem ser armazenadascomo metadados, tais como: nome do documento que na maioria dos SGBDs XMLNativos j utilizado, pertinncia do documento ao cluster, nome de quem criou aunidade de armazenamento, data de criao, tamanho do documento dentre outrasinformaes que podem ser consideradas. Uma vez identificados os metadados, osdocumentos so ento armazenados nas unidades correspondentes.

Uma vez criadas e povoadas as UAs, a partir da sugesto de ndices fornecida

pela etapa de processamento e das alternativas oferecidas pelo SGBD, procede-se adefinio e criao dos ndices. ndices unitrios (simples) e compostos (sobre dois ou


306


8/15

mais elementos que ocorram de forma associada); ndices sobre textos para elementoscom textos longos; e ndices sobre elementos pouco estveis, que podem ou no estarpresentes nos documentos.

3.4 Consideraes sobre a Estratgia Proposta

Os documentos submetidos a esta estratgia so documentos que normalmente nosofrem alteraes (e.g. livros, artigos, revistas), nos quais uma alterao gera novasverses destes documentos, e portanto, outros documentos. Com isto, a tendncia queos documentos uma vez armazenados e identificados dentro de unidades, que mantmdocumentos similares, no sofram alteraes, e assim, as UAs mantenham suahomogeneidade.

Neste estudo, no foi considerada a entrada de novos documentos em UAs jpovoadas. A entrada de novos documentos isoladamente ou mesmo em um nmeroconsidervel, requer uma nova avaliao sobre que UA receberia o(s) novo(s)documentos. De qualquer forma, cada novo documento teria que passar pelas etapas depr-processamento, processamento e ps-processamento, podendo haver alteraes naestratgia. Quanto a isto, outras questes podem ser levantadas, j que o novodocumento poderia no ser similar a nenhum dos grupos existentes e com isto surgiria anecessidade de se criar um novo grupo e portanto uma nova UA a fim de manter ahomogeneidade e o conjunto de regras aplicadas a esta UA.

A criao de UAs homogneas somada criao de ndices, j nos d uma idiado ganho na recuperao destes documentos. Para avaliar a estratgia proposta sermostrado um estudo de caso que apresenta uma comparao com outras abordagens.

4. Prottipo

Com o objetivo de orientar a construo do projeto fsico de banco de dados emSGBDs XML Nativos, com base na estratgia proposta, foi desenvolvido um prottipo,denominado GAIDoX (Guia para Armazenamento e Indexao de Documentos XML)que cobre parcialmente as etapas de pr-processamento, processamento e ps-processamento. A Figura 2 mostra a arquitetura do prottipo.

Figura 2. Arquitetura do Prottipo.

A implementao do prottipo foi feita em Java JDK verso 1.5, utilizando aversao 2.2.13 da API fornecida pelo SGBD XML Nativo Berkeley DB XML

(BDBXML - http://www.oracle.com/database/berkeley-db.html). Este SGBD utilizadopara armazenar os grupos de documentos XML, aps a etapa de processamento.


307


9/15

O mdulo de configurao, onde so cadastradas informaes bsicas como aindicao de diretrios onde esto armazenados os documentos, a parametrizao devalores (e.g. nmero de clusters, limiar de homogeneidade, etc.), e informaes

relacionadas ao SGBD utilizado (e.g. capacidade mxima de cada UA). Estasinformaes so armazenadas no BD de configurao e so consultadas pelos demaismdulos.

O mdulo de pr-processamento cobre as tarefas de identificao de termos ecomposio da matriz de dados. Neste mdulo ainda possvel limitar a quantidades detags que iro compor a matriz de dados.

No mdulo de processamento, a tarefa de clusterizao, que utiliza o algoritmoFuzzy K-Means realizada pelo MatLab (http://www.mathworks.com/), constituindo omdulo FCM MATLAB. Os resultados obtidos so importados para o mdulo deprocessamento e repassados para as tarefas de verificao de pertinncia e verificao

de homogeneidade. Aps constatada a homogeneidade dos clusters solicitada umadescrio para os mesmos. Este mdulo cobre ainda as tarefas de associao cujosresultados so utilizados para a sugesto dos ndices.

No mdulo de ps-processamento, os documentos so armazenados de acordocom os resultados da clusterizao obtidos na etapa de processamento e com asestratgias de armazenamento. As estratgias oferecidas pelo BDBXML so: whole enode. A primeira fora o armazenamento do documento ntegro, sem fragment-lo. J asegunda, a critrio do SGBD, fragmenta o documento em ns. A Figura 3 mostra oassistente de armazenamento deste mdulo.

Alm do armazenamento propriamente dito, o mdulo de ps-processamento

cobre ainda as atividades de definio das UAs, onde indicada a quantidade de UAsnecessrias de acordo com a sua capacidade e o tamanho dos clusters formados; e aatividade de definio de metadados.

Figura 3. Assistente de Armazenamento.

Os mdulos de processamento e ps-processamento mantm um log paraarmazenar informaes sobre as caractersticas do armazenamento e decises do


308


10/15

usurio. Basicamente, as informaes do log contm para cada cluster: o tamanhoocupado, a quantidade de UAs necessrias, os metadados selecionados, a data decriao e informaes sobre a estratgia de armazenamento.

No prottipo h ainda um mdulo para realizao de consultas sobre osdocumentos j agrupados e armazenados.

5. Estudo de Caso

Para realizar este estudo de caso, de forma a avaliar a estratgia proposta, foi precisoreunir um grande volume de documentos. Alm disso, preocupou-se tambm com aconstruo de um acervo heterogneo, com documentos de diferentes fontes, quevariassem significativamente em termos estruturais, porm que guardassem algumasimilaridade. Deste modo, foi possvel avaliar a etapa de clusterizao, permitindoantever a formao dos grupos de documentos similares, e ainda, avaliar as etapas de

armazenamento/indexao atravs de consultas que visam recuperar documentos dosdiversos grupos de documentos.

Assim, optou-se por trabalhar com trs conjuntos de documentos heterogneos,sendo que um destes conjuntos, artigos completos, formado por documentos geradosautomaticamente por um utilitrio (http://www.cs.toronto.edu/tox/toxgene/). O segundoconjunto, resumos de artigos, contm documentos reais, provenientes da revistaeletrnica Sigmod record (http://www.sigmod.org/record/xml/). O terceiro grupo,currculos, contm documentos criados manualmente. A Tabela 1 totaliza a quantidadede documentos do acervo utilizado neste estudo de caso, discriminando os grupos.

Tabela 1. Acervo de Documentos XML

Com relao etapa de pr-processamento, para os grupos artigos completos eresumo de artigos, nenhum tratamento foi empregado, j que as tags que formam estesdocumentos j apresentavam homogeneidade em sua descrio. Para o grupo decurrculos, para os documentos que no seguiam o formato Lattes, foi preciso

uniformizar manualmente as tags usadas.Aps computada a freqncia com que as tagsapareciam em cada documento, montou-se uma matriz de freqncia de dados para sersubmetida ao algoritmo de clusterizao.

Uma caracterstica do algoritmo de clusterizao atribuir diferentes graus depertinncia dos documentos a todos os clusters formados, estabelecendo graus depertinncia mais ou menos significativos para cada documento em cada cluster.Conhecendo previamente o acervo, optou-se por utilizar trs clusters. O algoritmo declusterizao se comportou corretamente, mantendo os documentos de cada grupo, comaltos graus de pertinncia, em um mesmo cluster. Assim, foram gerados 3 clusters, umpara cada grupo de documentos do acervo. A partir dos grupos definidos, estesdocumentos foram armazenados em 3 Unidades de Armazenamento (UA), segundo aestratgia proposta, e de duas outras formas (sem considerar a similaridade dosdocumentos):

Tipo Origem Qtd Tamanho

resumos de artigos sigmod record 911 1,96Mb

artigos completos Xbench 405 250Mb

curriculos CV Lattes, Web e outros 15 58,9Kb

Total 1331 252Mb


309


11/15

UAs Mltiplas Homogneas: A estratgia proposta que realiza o armazenamentopor UA somente de documentos similares. Nesta estratgia temos uma UA paracada clusterformado.

UA nica Heterognea: A estratgia que realiza o armazenamento de diferentesdocumentos em uma nica UA.

UAs Mltiplas Heterogneas: A estratgia que se utiliza de mltiplas UAs paradistribuir os documentos, sendo que esta distribuio realizada de formaaleatria, sem considerar qualquer tipo de relao entre os documentos.

Para cada uma destas situaes foi avaliada a utilizao ou no de ndices. Osresultados foram obtidos para as trs estratgias de armazenamento, e so apresentadose analisados na seo seguinte. Para cada uma destas estratgias, considerou-se somenteo modo de armazenamento node. O BDBXML no foi capaz de armazenar a quantidade

de documentos do acervo preparado, no modo whole.Quatro funcionalidades esto sendo avaliadas pelas consultas selecionadas, so

elas: consultas por valores exatos, ordenao, verificao de dados irregulares ereferncias e joins. Na Tabela 2 so listadas as consultas selecionadas, direcionadas acada grupo de documentos, e os ndices empregados em cada uma delas.

Tabela 2. Consultas realizadas nos testes e os respectivos ndices usados

Consultas para o grupo Artigos Completos Indices utilizados

1. for $a in collection(container)/article[@id=1] return $art/prolog/title id (node-attribute-equality-string)

2.for $prolog in collection("container ")/article/prologwhere $prolog/authors/author/name="Ben Yang" return $prolog/title

Name(node-element-equality-string)

3.for $a in collection("container.dbxml")/article/prologwhere $a/dateline/country="Canada" order by $a/dateline/datereturn {$a/title} {$a/dateline/date}

country(node-element-equality-string)

4.collection("container")/article/prolog[not(genre)]/title Genre(node-element-presence-none)5.collection("container.dbxml")/article/prolog/genre/title Genre(node-element-presence-none)6.for $a in collection("container")/article[@id="7"]/epilog/references/a_id,

$b in collection("container")/articlewhere $a = $b/@id return {$b/prolog/title}

id (node-attribute-equality-string)

Consultas para o grupo Resumos de Artigos Indices utilizados

1. for $art in collection("container ")/IndexTermsPage/title[@id="00585"] return $art/title id (node-attribute-equality-string)

2. for $art in collection("container")/IndexTermsPagewhere $art/authors/author="Dick Tsur" return $art/author

author(node-element-equality-string)

3.for $a in collection("container")/IndexTermsPagewhere $a/confyear="1993" order by $a/title return {$a/title}

confyear(node-element-equality-string)

4.collection("container")/IndexTermsPage/categoryAndSubjectDescriptors[not(categoryAndSubjectDescriptorsTuple)]

categoryAndSubjectDescriptorsTuple (node-element-presence-none)

5.collection("container")/IndexTermsPage/categoryAndSubjectDescriptors/categoryAndSubjectDescriptorsTuple/category

categoryAndSubjectDescriptorsTuple (node-element-presence-none)

6. for $a in collection("container")/IndexTermsPage/title[@id="00585"]/authors/author,$b in collection("container")/IndexTermsPage/authors/author

where $a = $b return {$b/IndexTermsPage/title}

id (node-attribute-equality-string)

Consultas para o grupo Currculos Indices utilizados

1.for $cur in collection("container")where contains($cur//instituicao,"IME") return $cur//dados_pessoais

instituicao(node-element-substring-string)

2.collection("container ")[//doutorado]//nome doutorado(node-element-presence-none)3.collection("container ")[//cidade="Rio de Janeiro"]//experiencia_profissional cidade(node-element-equality-string)


310


12/15

4.for $tese in collection("container")//tesewhere contains ($tese/title,"XML") return $tese

title(node-element-substring-string)

5.collection("container")[//instituicao/nome="IME"] Nome(node-element-equality-string)

6. for $cur in collection("container") where contains ($cur//dados_pessoais/nome,ana)order by $cur/dados_pessoais/nome return $cur

Dados_pessoais.nome(edge-element-equality-string)

Os tempos das execues das consultas foram coletados considerando-se comotempo de execuo final, a mdia entre os tempos de execuo a quente. Paracomputao dos tempos foram realizadas 6 (seis) execues, sendo descartado o tempoda primeira execuo. O ambiente utilizado para os testes foi o SGBD BDBXML. Ostestes foram realizados utilizando-se um microcomputador com processador Pentium4.3, memria RAM de 2 Gbytes, disco rgido de 160 Gbytes e sistema operacionalWindows XP Professional.

6. Resultados e Discusso

Foram avaliados os tempos de execuo das consultas com e sem ndice em cada umadas 3 estratgias de armazenamento propostas no estudo de caso: homogneo mltiplo,heterogneo nico e heterogneo mltiplo. Algumas consultas foram reescritas, demodo a garantir a utilizao correta dos ndices, e com isto a melhora do desempenho.Os resultados das execues sem ndice mostraram que a estratgia proposta por estetrabalho apresenta os menores tempos de processamento (Santos, 2007). As subseesseguintes discutem os resultados obtidos a partir das execues com a utilizao dendices, apresentando grficos comparativos entre a estratgia proposta (homogneomltiplo) e as demais estratgias (heterogneo mtiplo e nico).

6.1 Resultados das Consultas sobre o Grupo Artigos Completos (Xbench)Pode-se perceber atravs da anlise dos grficos da Figura 4, que a estratgia propostaapresenta os menores tempos de processamento na maior parte das consultas. Os ganhosde desempenho so significativamente maiores para as consultas C2, C3. Os ndicesusados nestas consultas so baseados em igualdade de valores sobre elementos (tags),diferentemente dos ndices usados nas demais consultas que so ndices para dadosirregulares (presena) e para atributos. Em relao a estratgia Heterogneo Mltiplo,exceto nas consultas C1 e C6, os ganhos so sempre significativamente maiores. Aconsulta C6, que envolve o uso de ndices para realizar juno, apresentou, para aestratgia homogneo mltiplo, piores resultados em relao a estratgia heterogneomltiplo.

Figura 4. Tempos (em ms) por consultas c/ ndices Grupo Artigos Completos


311


13/15

6.2 Resultados das Consultas sobre o Grupo Resumos de Artigos (Sigmod)

Pode-se perceber atravs da anlise dos grficos da Figura 5, que a estratgia propostaapresenta os menores tempos de processamento em todas as consultas, exceto naconsulta C5 que perde para a estratgia heterogneo nico e no apresenta grandesdiferenas em relao estratgia heterogneo mltiplo. O ndice usado nesta consultaoferece suporte a dados irregulares (presena).

Figura 5. Tempos (em ms) por consulta c/ ndice - Grupo Resumos de Artigos

6.3 Resultados das Consultas sobre o Grupo de Curriculos

A Figura 6 no apresenta os tempos para a estratgia heterogneo mltiplo, poisocorreram diversos erros no processamento destas consultas sobre este grupo dedocumentos. Todas as consultas aplicadas a este grupo utilizam-se do recurso de barrasduplas, que indica que a tag subsequente pode aparecer como um descendente da tagprecedente. Este recurso foi utilizado, j que h grandes diferenas estruturais nestegrupo de documentos.

A consulta C2 apresentou o maior ganho na estratgia proposta, homogneomltiplo, em relao s demais estratgias. Esta consulta envolve o uso de ndices paradados irregulares (presena). J a consulta C3 foi a que apresentou tempos de execuomais prximos entre as estratgias homogneo mltiplo e heterogneo nico. O ndiceutilizado nesta consulta baseado em igualdade de valores sobre elementos.

Figura 6. Tempos (em ms) por consulta c/ ndice Grupo de Currculos

6.4 Consideraes sobre os Resultados

Durante a realizao dos testes, foram encontrados alguns problemas no uso do SGBDBDBXML, o que nos leva a considerar refazer os testes com outros SGBDs XMLNativos O principal problema diz respeito ao uso de ndices, pois o comportamento do

otimizador de consultas do BDBXML no apresentou um comportamento muitoregular. Por este motivo, algumas consultas tiveram que ser reescritas para que o


312


14/15

otimizador reconhecesse os ndices. Em outras consultas, percebeu-se que os ndicesforam utilizados de forma diferenciada pelo otimizador de consulta, ora beneficiando,ora prejudicando o desempenho das consultas, o que tornou a comparao, nestes casos,

inconclusiva, levando ao descarte destas consultas.Apesar de terem sido avaliadas poucas consultas, pode-se perceber que o fato de

ter UAs homogneas, mantendo documentos com caractersticas comuns, proporcionaalgumas vantagens sobre as outras estratgias. Uma delas saber para onde as consultassero direcionadas, o que no acontece na forma de armazenamento heterogneomltiplo, onde para cada pesquisa, vrias UAs precisam ser consultadas. Isto noacontece na forma de armazenamento heterogneo nico, que mantm todos osdocumentos em uma nica UA, mas por outro lado, no se pode aplicar estratgias dearmazenamento diferenciadas. A estratgia de armazenamento proposta procurapossibilitar um emprego adequado dos recursos de armazenamento e acesso ao tipo de

documento sendo armazenado.Nos trs conjuntos de documentos apresentados, foi possvel perceber

claramente os ganhos, em especial para o grupo de currculos. Embora este grupo sejapequeno em termos de nmero de documentos e espao exigido para armazenamento,estamos preparando uma base maior para confirmar os resultados obtidos.

Identificamos ainda, outros testes importantes que poderiam ser realizados paraavaliar melhor a estratgia proposta, como por exemplo, para avaliar acessoconcorrente, ou para avaliar consultas com resultados possveis em todos os grupos.

7. Concluso

Como contribuio deste trabalho, destaca-se a especificao de uma estratgia,composta por etapas bem definidas, para auxiliar o armazenamento e recuperao maiseficientes de documentos XML heterogneos em SGBDs XML Nativos. Alm disso,h tambm o prottipo implementado para auxiliar o usurio a desenvolver um projetofsico de banco de dados sobre SGBDs XML Nativos. Apesar de ter sido avaliadoapenas o SGBD BDBXML, vale ressaltar que a estratgia proposta aplicvel aqualquer SGBD XML Nativo, assim como poderiam ter sido aplicados outrosalgoritmos de minerao correspondentes s tarefas de associao e clusterizaoutilizados. Para tornar o prottipo independente do SGBD a ser utilizado, precisaramosrealizar pequenas adaptaes principalmente na fase de ps-processamento onde oSGBD acionado em atividades que envolvem a sub-etapa de armazenamento.

Como trabalho futuro podemos citar a gerao de esquema nico, sobre cadaUA gerada pela estratgia proposta. Um outro trabalho interessante seria no sentido dedeterminar automaticamente a quantidade inicial de clusters. Outra avaliaes daestratgia proposta tambm poderiam ser realizadas, como aplic-la sobre outrosSGBDs XML Nativos, e ou sobre acervos desconhecidos. Por fim, pretende-se tambmproceder a adequao da estratgia para tratar a incluso de novos documentos,considerando os grupos j formados.

Referncias

Abiteboul, S.; Manolescu, I.; Nguyen, B. e Preda, N. (2005) A Test Plataform for theINEX heterogeneous track, Springer Berlin, Advances in XML InformationRetrieval, v. 3493, p.358-371.


313


15/15

Brasil, Christiane Regina. (2004) Ferramenta Inteligente de Apoio a Pesquisa:Minerao de Artigos Cientficos na WEB, USP, Dissertao.

Brian, Danny. (2006) The Definitive Guide to Berkeley DB XML, APRESS.

Fayad, U.M.; Piatetsky-Shapiro, G. e Smyth, P. (1996) From Data Mining toKnowledge Discovery: An Overview. Knowledge Discovery and Data Mining,Menlo Park: AAAI Press.

Flesca, S.; Manco G., Masciari, E.; Pontieri, L. e Pugliese, A. (2005) Fast Detection ofXML Structural Similarity, IEEE.

Goldschmidt, R. e Passos, E. (2005) Data Mining Um Guia Prtico, Campus.

Jagadish,H.V.; Al-Khalifa, S.; Chapman, A. et al. (2002) TIMBER: A native XMLdatabase, Springer Berlin, VLDB Journal, V.11, p.274-291.

Kelledy, F.; Smeaton, A. F. (1997) Automatic Phrase Recognition and Extraction fromText, Proceedings of the 19th Annual BSC-IRSG Colloquium on IR Research.

Lee, J.; Lee, K. e Kim, W. (2001) Preparations for Semantics-Based XML Mining,IEEE.

Li, Y.; Yu, C. e Jagadish, H.V. (2004) Schema-Free Xquery, VLDB.

Lian, Wang; Cheung David; Mamoulis, Nikos e Yiu, Siu-Ming. (2004) An efficientand scalable algorithm for Clustering XML Documents by Structure, IEEE.

Nierman, A. e Jagadish, H. V. (2002) Evaluating Structural Similarity in XMLDocuments, Proc. Int. Workshop on the Web and Databases (WebDB), Madison,

WI.Pereira, J. C. L. e Bax, M. P. (2002) Introduo a Gesto de Contedos, Workshop

Brasileiro de Inteligncia Competitiva e Gesto do Conhecimento.

Rosa, J.M.C; Tanscheit, R.; Vellasco, M.; Zanini, A; Klein, C.H; Bloch, K.V; Nogueira,A.R; Salis, L.H e Souza e Silva, N.A. (2001) Aplicao Fuzzy Clustering a Bancode Dados de Amostra Domiciliar da Populao da Ilha do Governador, SBAI.

Santos, M. O. (2007) Armazenamento e Recuperao de Documentos XMLHeterogneos: Aplicando Tcnicas de KDD para apoiar o projeto fsico em SGBDsXML Nativos, IME, Dissertao.

Schning, H. (2001) "Tamino-A DBMS designed for XML", Int. Conf. on DataEngineering.

Shvaiko, P.;Euzenat, J. (2005) "A Survey of Schema-Based Matching Approaches",Journal on Data Semantics IV, volume 4, p.146-171.

UNESCO. (1973) Guidelines for the establishment and development of monolingualthesauri. Paris, 37p.

Yang, J.; Cheung, W. e Chen, X. (2005) Integrating Element and Term Semantics forSimilarity-Based XML Document Clustering, Int. Conf. on Web Intelligence.


314