Semantic Web – “formal”

Similaridade

Os operadores de consulta por similaridade podem ser combinados com operadores tradicionais para melhorar a semˆantica e o resultado das consultas em SQL (Silva e Aref, 2009). Internamente, cabe ao SGBDR definir a ordem de execu¸c˜ao de cada um dos operadores sobre os dados, podendo utilizar heur´ısticas que estimam qual o melhor plano de consulta para cada execu¸c˜ao.

Podemos visualizar um plano de consulta, como uma “´arvore de comandos” como a da Figura 3.3. Nesse sentido, para estimarmos qual o melhor tempo de execu¸c˜ao, precisamos considerar a precedˆencia dos operadores, tanto os tradicionais quanto os de similaridade. Propriedades particularmente interessantes s˜ao as propriedades de comutatividade e distributividade. Os predicados por limitados por ξ apresentam tamb´em a propriedade similares, ou seja: σ(atributoθvalor)(ˆσ(S:(d(),Q,ξ))T1) = ˆσ(S:(d(),Q,ξ))(σ(atributoθvalor)T1).

No entanto, para os predicados que utilizam busca aos k -vizinhos mais pr´oximos ou aos k -pares de vizinhos mais pr´oximos a propriedade de comutatividade n˜ao ´e v´alida. Essa limita¸c˜ao impede a comutatividade de conjuntos conectados pelos predicados AND

42 3. Recupera¸c˜ao de Dados por Conte´udo em SGBDR Le Le

σ

^

σ

π

Figura 3.3: ´Arvore de comandos (bottom-up) que representa a ordem de execu¸c˜ao de

uma consulta SQL envolvendo operadores por similaridade e tradicionais. e OR da linguagem SQL, algo que inviabiliza e dificulta a execu¸c˜ao de heur´ısticas para determinar o plano ´otimo de consulta. Por exemplo, suponha que a Figura 3.3 represente um plano canˆonico de execu¸c˜ao, as opera¸c˜oes de sele¸c˜ao e jun¸c˜ao por similaridade s´o poderiam ser trocadas, na busca pelo plano de execu¸c˜ao ´otimo, se todas elas fossem opera¸c˜oes de Range Query.

Uma das solu¸c˜oes para este impasse de ambiguidade, em se tratando de predicados limitados por k, ´e a defini¸c˜ao de regras como: Predicados por similaridade devem ser sempre executados antes dos predicados tradicionais; os predicados limitados por k devem ser executados antes dos predicados Range e; dois ou mais predicados limitados por k devem ser executados independementente e sobre seu conjunto-solu¸c˜ao deve ser aplicado uma intersec¸c˜ao/uni˜ao. Utilizar essas regras, no entanto, pode levar a uma execu¸c˜ao lenta e bastante distante dos plano de consultas ideais.

O estudo das propriedades entre os operadores relacionais tradicionais e os operadores por similaridade ´e alvo de diversas pesquisas (Lange e Naumann, 2013) cujo objetivo final ´e encontrar novas heur´ısticas que, respeitando as propriedades t´acitas dos operadores de similaridade, sejam capazes de encontrar o plano de consulta ´otimo, dentro dos requisitos estabelecidos.

3.11

Considera¸c˜oes Finais

Nesse cap´ıtulo e no anterior vimos que a literatura nos apresenta um s´olido arcabou¸co para que o conceito de consultas por similaridade seja incorporado aos SGBDR comerciais. Isso, por sua vez, popularizaria e facilitaria o desenvolvimento de aplica¸c˜oes de recupera¸c˜ao por conte´udo, t˜ao necessarias em um ambiente onde os dados multim´ıdia crescem a uma taxa exponencial.

3.11 Considera¸c˜oes Finais 43 Agregar todos estes conceitos em um prot´otipo/framework, no entanto, ainda

representa um grande desafio. Mais do que isso, planejar uma arquitetura onde os

dados complexos possam co-existir sem que o DBA ou o usu´ario final precisem realizar pessoalmente as opera¸c˜oes e dar suporte a novos dados complexos, a medida em que forem sendo definidos por pesquisas desenvolvidas representa um desafio ainda maior.

A representa¸c˜ao do dado complexo no espa¸co m´etrico atrav´es de um extrator de caracter´ısticas e sua compara¸c˜ao atrav´es de uma fun¸c˜ao de distˆancia ´e apontado como o maior desafio (M¨uller et al., 2004) para se diminuir o gap semˆantico entre os aplicativos de recupera¸c˜ao de dados complexos por conte´udo e dom´ınios espec´ıficos, como medicina e mercado de a¸c˜oes. Construir novos extratores de caracter´ısticas e novas fun¸c˜oes de distˆancia tamb´em ´e o objetivo de diversos trabalhos (Kao et al., 2013) (Nixon e Aguado, 2008).

Alguns sistemas, como o FMi-SiR (Kaster et al., 2010) e o SIREN (Barioni, 2006) merecem cita¸c˜ao especial, por implementarem prot´otipos de interpretadores de extens˜oes da linguagem da linguagem SQL, respeitando as defini¸c˜oes citadas ao longo dos dois ´

ultimos cap´ıtulos. Em particular, o SIREN, diferentemente do FMi-SiR que est´a acoplado

ao SGBDR Oracle , apresenta uma sintaxe bem definida de SQL estendido que suporta:R

• Expressar consultas por similaridade, representando um baixo impacto na linguagem SQL padr˜ao;

• Expressar uma associa¸c˜ao inicial entre <extrator, fun¸c˜ao de distˆancia> para que possam ser efetuadas as compara¸c˜oes entre imagens e dados PARTICULATE (definidos sobre dados simples).

• Expressar a defini¸c˜ao de clusters para a defini¸c˜ao de agrupamento de dados.

Nos pr´oximos cap´ıtulos veremos como, com os conceitos definidos nas ´ultimas se¸c˜oes e partindo-se do interpretador de SQL estendido da vers˜ao original do SIREN, pode-se desenvolver um framework onde torna-se poss´ıvel integrar novos dados complexos, extra- tores de caracter´ısticas, fun¸c˜oes de distˆancia, m´etodos de acesso m´etrico ao interpretador de consultas, bem como definir novas palavras reservadas (dicion´ario de dados) para o tratamento dos mesmos, ampliando o conceito do SIREN de mero aplicativo a um framework de recursos capaz de lidar com as diversas consultas por similaridade.

Para validar essa nova abordagem foi constru´ıdo um aplicativo shell (similar aos disponibilizados pelos SGBDR propriet´arios) onde ´e poss´ıvel inserir os comandos em SQL estendido, interpret´a-los e execut´a-los em trˆes SGBDR distintos.

Al´em disso, os novos recursos adicionados ao SIREN permitem que se utilize como base as consultas por similaridade via SQL estendido para a cria¸c˜ao de aplicativos

de recupera¸c˜ao de dados por conte´udo. Em particular ´e apresentado como exemplo

44 3. Recupera¸c˜ao de Dados por Conte´udo em SGBDR

desenvolvido sob a nova arquitetura do SIREN e testado em um dom´ınio real, o Hospital das Clin´ıcas de Ribeir˜ao Preto.

Cap´ıtulo

4

Metodologia

A nova arquitetura e os novos recursos para o SIREN, requereu que fosse feita uma nova implementa¸c˜ao de um shell, similar aos diponibilizados pelos SGBDR comerciais para a valida¸c˜ao da proposta deste trabalho. Al´em disso, para validar a flexibilidade da arquitetura desenvolvida, que deve contemplar suporte a novos dados complexos, foi implementada uma biblioteca de s´eries-temporais financeiras e criado um novo extrator de caracter´ıstica para este tipo de dados, ao final integrados ao shell. Ainda para validar a arquitetura, foi proposto e implementado um sistema de recupera¸c˜ao de imagens m´edicas por conte´udo, espec´ıfico para imagens de mamografia, que utiliza os recursos propostos e implementados neste trabalho, para auxiliar m´edicos radiologistas em um ambiente real de aplica¸c˜ao. Esses m´odulos de software s˜ao apresentados neste caop´ıtulo.

4.1

Equipamentos e Detalhes de Implementa¸c˜ao

Todos os recursos (do agora framework ) SIREN, incluindo bibliotecas, foram codificado em C++, seguindo a proposta da STL. Para resolver um dos problemas enfrentados pela vers˜ao inicial, foi utilizado a plataforma cruzada Qt que possibilita que as bibliotecasR desenvolvidas funcionem tanto para Windows, quanto Linux e MAC OS. Os drivers para conex˜ao aos bancos utilizados s˜ao os disponibilizados pela Nokia e TrolltechR paraR

Qt e permitem conex˜ao aos SGBDR Oracle , PostGresR e MySQLR .R

Nessa vers˜ao, foram incorporadas as seguintes bibliotecas: Artemis, Apolo, Midas, Hermes, Arboretum e Agathon. Artemis ´e (Bedo e Traina, 2010b) uma biblioteca para o tratamento de imagens que d´a suporte aos formatos jpg, bmp, png, krl e DICOM e possui os seguintes m´etodos extratores de caracter´ısticas: Histograma de tons de cinza, Histograma de Cores, Histograma M´etrico (Traina et al., 2003), MPEG Color Layout

46 4. Metodologia

(Ivanova et al., 2010), Haralick (Haralick et al., 1973), Wavelets de Haar (Graps, 1995), Wavelets de Daubechies (Kao et al., 2013) e caracter´ısticas de Zernike (Hasan e Shaker, 2012); Apollo (Bedo e Traina, 2010a) ´e uma biblioteca para tratamento de ´audio que trabalha com arquivos no formato wav e tem os extratores de caracter´ıstica PCA e STFT; a biblioteca Midas d´a suporte a s´eries-temporais financeiras no formato xls, csv e txt, e inclui o extrator de caracter´ısticas GapExtractor (Bedo et al., 2013b); a biblioteca de fun¸c˜oes de distˆancia Hermes (Bedo e Traina, 2011) implementa as fun¸c˜oes de distˆancia: Ledit (Levenshtein, 1966), fam´ılia Minkowsky (Zezula et al., 2010), Metric Histogram Distance (Traina et al., 2003) e DTW (Ratanamahatana, 2005); a biblioteca Arboretum d´a suporte aos M´etodos de Acesso M´etrico Slim Tree (Traina et al., 2002), M-Tree (Ciaccia et al., 1997) e Omni-Tree (Traina et al., 2007). Por fim a biblioteca Agathon, baseado na implementa¸c˜ao original do SIREN, ´e respons´avel pela interpreta¸c˜ao do comando e possui classes e m´etodos que definem um interpretador de comandos de SQL estendido.