EXTRAÇÃO DE CONSULTAS GERENCIAIS BASEADA NA TÉCNICA DE AMOSTRAGEM ESTRATIFICADA

EXTRAÇÃO DE CONSULTAS GERENCIAIS BASEADA NA TÉCNICA DE AMOSTRAGEM ESTRATIFICADA

Cláudio Ratke1 Dalton Francisco de Andrade²

RESUMO O volume de dados em um SGBD pode influenciar diretamente na performance de consultas e/ou relatórios. A extração de dados gerenciais não exige exatidão das informações, por isso informações gerenciais poderiam ser obtidas a partir de amostras. Este artigo propõe a utilização de método estatístico sobre a base de dados, denominado de amostragem estratificada, que permite a obtenção de uma amostra reduzida, porém mantendo um nível aceitável de acurácia, para uma consulta de dados gerencial. Através deste método, obter-se-á expressões em linguagem SQL para extração de tuplas expressivas, que retornarão a amostra onde será aplicada em consultas.

PALAVRAS-CHAVE: Banco de dados. Estratificação. Mineração de dados

Proceedings of the XII SIBGRAPI (October 1999) 101-104

2

ABSTRACT Data volume in a DBMS (database management system) can influence directly in the performance of queries and/or reports. The extraction of managerial data doesn't demand accuracy of the information, for that managerial information could be obtained from samples. This paper proposes the use of statistical method on the database, denominated stratified sampling, which allows the obtaining of a reduced sample, however maintaining an acceptable level of accuracy for a managerial query of data. Through this method, it will be obtained expressions in SQL (structured query language) to extraction of expressive tuples, which will return a sample where will be applied in queries. KEYWORDS: Database. Stratification. Data mining.

1 INTRODUÇÃO A tecnologia tem provido métodos eficientes e com custo reduzido para armazenamento de dados o que tem possibilitado a criação de inúmeros SPTs (sistema de processamento de transações) (STAIR, 1996) que dão apoio à monitoração e a realização das negociações de uma organização. A maioria de SPTs utilizam-se de um sistema de SGBD (Sistema Gerenciador de Banco de Dados) para armazenamento de seus dados, criando uma grande massa de dados gerenciados pelos SGBDs (DATE, 2003). A maioria dos SGBDs possui uma DML (Data Manipulation Lange) (CODD, 1970) baseada no padrão SQL (Structured Query Linguage) definido pela ANSI (Americam National Standards Institute) e a ISO

3

(International Standards Organization) que é amplamente usada para geração de consultas e/ou relatórios sobre os dados mantidos pelos SGBDs. Um SIG (Sistema de Informações Gerenciais) baseia-se dos dados coletados pelos SPTs e normalmente envolve uma grande massa de dados. Por isso, geralmente as consultas e relatórios gerenciais consomem grande tempo para seu processamento. Por outro lado, não é exibido que as informações gerenciais sejam exatas, pois a maioria das informações são apresentadas sob a forma de gráficos evidenciando alguma tendência (STAIR, 1996). Organizações com grande volume de dados utilizam um repositório (data warehouse) de informações coletadas de diversas fontes para elaboração de consultas gerenciais. Esta redundância visa evitar que seja afetado o desempenho dos SPTs durante o processamento das consultas gerenciais (SILBERSCHATZ, 1999). Em estatística utiliza-se a amostragem quando não se pode trabalhar com o universo de dados (denominado população), ora seja pelo tamanho da massa de dados, ora seja, pelo custo despendido para tal operação. As técnicas de amostragem (plano amostral) visam obter um conjunto de dados representativo (amostra) da população e que possam fornecer informações aproximadas do universo através de processos de estimação. A busca por uma informação de interesse é a principal função de consultas e relatórios gerenciais. Das técnicas de amostragem existentes, o plano amostral estratificado divide a universo em grupos mais homogêneos com base em uma informação de interesse.

4

A proposta deste artigo é utilizar os recursos de banco de dados para extração de consultas gerenciais baseando-se na técnica de amostragem estratificada, considerando os seguintes aspectos: • Custo de processamento: ao trabalhar com uma amostra dos dados tem-se um custo de processamento menor; • Precisão: com a utilização do método de amostragem estratificada, pode-se obter valores estimados próximos dos reais; • Versatilidade: o método pode ser aplicado a uma série de diferentes aplicações e portanto, torna-se independente de áreas de negócio; • Pesquisa simultânea: como utiliza o próprio SGBD para realizar a operações de consulta torna-se possível a utilização de consultas simultâneas. • Complexidade: algoritmo simples que pode ser convertido em uma função ou store procedure da grande maioria dos gerenciadores de banco de dados (SGBD). • Custo: custo reduzido pela pouca necessidade de poder de processamento dos equipamentos. Para testes utilizou-se a extensão de linguagem SQL fornecida pelo MS SQL Server, versão 2000. Este artigo está dividido em três partes. Na seção 2 é fundamentada a técnica de amostragem estratificada. A seção 3 descreve o algoritmo proposto. Por fim, na seção 4, apresenta-se um breve teste. Considerações finais e sugestões são apresentadas na última seção.

5

2 AMOSTRAGEM ESTRATIFICADA Amostragem estratificada é uma técnica de amostragem na qual é usada para estimar parâmetros da população mais eficientemente quando há substancial variabilidade entre as sub-populações (COCHRAN, 1977; NEYMAN, 1934). Neste método a população é separada em estratos. Cada estrato é formado por grupos de elementos com valores similares de uma ou mais variáveis (campos) de estratificação. O valor de cada variável de estratificação é conhecido na população e assumi-se que há uma correlação com a variável de interesse. Uma amostragem estratificada é construída pela seleção de probabilidade da pesquisa em cada estrato independentemente, aplicandose em seguida a amostragem aleatória simples sobre cada estrato (sem reposição) (JOHNSON, 1969). Considerando uma população contendo N elementos e H estratos. A variável de interesse é denotada por y e yi como sendo o valor do inésimo elemento da população. Onde i é um índice compreendido entre 1,...,N. Nh é o tamanho do estrato h, podendo estar entre 1,...,H. Supondo que uma amostragem estratificada simples seja selecionada a partir da população, com nh elementos obtidos para cada estrato h. Para estimar a média da população µ =

µˆest =

N i =1

yi / N , o estimador é dado por:

H 1 H N h yh = Wh yh N h =1 h =1

6

É comum utilizar yh =

nk yhi / nh , para calcular a média dentro de i =1

cada estrato h, sendo Wh = Nh / N relativo ao tamanho de cada estrato h. Quando estuda-se variáveis binárias com valor yi=1 ou yi=0 então a variável µ pode ser usada como estimador para proporção ou pˆ est . A variância do estimador estratificado será menor se a variável de estudo tiver uma variância dentro de cada estrato menor que a variância entre os diferentes estratos. Na prática, amostragem estratificada oferece um maior desempenho sobre uma amostra aleatória simples e raramente uma eficiência menor (COCHRAN, 1977). Um importante aspecto sobre a amostragem estratificada é como o tamanho será alocado sobre o montante de estratos. Há vários métodos de alocação (SARNDAL, 1992). Um método particularmente simples é a alocação proporcional, na qual o tamanho alocado para cada estrato é aproximadamente proporcional ao tamanho do estrato, isto é, nh = nWh . E a variância completa do estimador estratificado para uma alocação proporcional (TULL, 1973) é dado por:

Var ( µˆest ) =

H

3 DESCRIÇÃO DO ALGORITMO Esta proposta está dividida em duas etapas: a) Extração de expressões de execução b) Utilização das expressões

σ2

Wh h h =1 n

7

A Figura 1, a seguir, descreve o fluxograma de execução do método desenvolvido.

Figura 1- Fluxograma do método create procedure Calcula_Variancia_Coluna( @pColuna Varchar(30), -- Nome do atributo @pTabela varchar(30), -- Nome da tabela @pParam varchar(500), -- Filtro para concatenação @PMeta Varchar(30)) -– variável de interesse as begin (...) set @wMenorVar = 999999; set @wSql = N'set @wCursor = cursor local forward_only static read_only for select distinct(' +@pColuna+ ') from ' +@pTabela+ ' where (1=1) '+@pParam + ' ORDER BY ' + @pColuna+'; open @wCursor '; execute sp_executesql @wSql, N'@wCursor cursor output', @wCursor output if cursor_status('variable', '@wCursor') >= 0 begin FETCH NEXT FROM @wCursor INTO @wValor; while (@@fetch_status=0) begin set

@wVariancia = 0;

execute db_teste.teste.Calcula_Variancia_campo_valor @pColuna, @pTabela,

@pParam, @pMeta, @wValor, @wVariancia output;

8

(...) end

Figura 2 – Procedimento para identificar atributos e valores de menor variância A primeira etapa compreende a obtenção de uma amostra aleatória simples sobre a base de dados. A partir desta amostra, seriam identificadas as informações que mais influenciam na variável de interesse, através do cálculo de variância. Para identificar quais valores e atributos que determinam maior homogeneidade, o algoritmo verifica todos os atributos numéricos da entidade. Para cada atributo, são identificados todos os valores distintos. O trecho de procedimento apresentado no Figura 2 tem a função de obter o valor do atributo que possui a menor variância para a variável de interesse. Dessa forma, o procedimento é executado para cada atributo selecionado. O cálculo da variância sobre a variável de interesse baseado no valor do atributo pode ser visto na Figura 3. Este procedimento retorna o valor de menor variância deste atributo. create procedure Calcula_Variancia_campo_valor( @pColuna Varchar(30), -- nome do atributo @pTabela varchar(30), -- nome da entidade @pParam varchar(500), -- Filtro para concatenação @pMeta Varchar(30),

-- variável de interesse

@pValor varchar(30),

-- valor distinto do atributo

@@wResultado Float output) –- retorna valor da variância deste atributo/valor as begin declare @wSqlMenor

nvarchar(4000) --Armazenar o comando SQL

declare @wCursorMenor

cursor

declare @wSqlMaior

nvarchar(4000) --Armazenar o comando SQL

declare @wCursorMaior

cursor

--Armazena o Cursor

declare @wValorMenor

float;

--Armazena a valor da variância

declare @wContadorMenor Numeric(8,0);

--Armazena o Cursor

--Nr. registros com esta variância

9

declare @wValorMaior

float;

declare @wContadorMaior Numeric(8,0);

--Armazena a valor da variância --Nr. registros com esta variância

set @wSqlMenor = N'set @wCursorMenor = cursor local forward_only static read_only for select var('+@pMeta+'), count('+@pMeta+') from ' +@pTabela+ ' where (1=1) AND '+@pColuna+ ' '+Cast(@pvalor as Varchar)+' '+@pParam + ';

open @wCursorMaior;'; execute sp_executesql @wSqlMenor, N'@wCursorMenor cursor output', @wCursorMenor output if cursor_status('variable', '@wCursorMenor') >= 0 begin FETCH NEXT FROM @wCursorMenor INTO @wValorMenor, @wContadorMenor; end; execute sp_executesql @wSqlMaior, N'@wCursorMaior cursor output', @wCursorMaior output if cursor_status('variable', '@wCursorMaior') >= 0 begin FETCH NEXT FROM @wCursorMaior INTO @wValorMaior, @wContadorMaior; end; set @@wResultado = (power(@wContadorMenor/@wContadorMenor+@wContadorMaior,2)) * @wValorMenor + (power(@wContadorMaior/@wContadorMenor+@wContadorMaior,2)) * @wValorMaior; -- Calculo da Variância proporcional close @wCursorMenor; deallocate @wCursorMenor; close @wCursorMaior; deallocate @wCursorMaior; end

Figura 3 – Procedimento de cálculo da variância Como resultado seriam criados comandos em linguagem SQL, como por exemplo, uma view, que seriam utilizados para obter um coleção reduzida de tuplas, mas mantendo uma acurácia sobre a variável de interesse.

10

4 TESTES Como exemplo, foi utilizada uma consulta que apresentava o valor médio das vendas de um determinado período. Pode-se observar o comando tradicional utilizado para extração desta informação a partir da Figura 4.

select avg(vlrvenda) from tabvendas

Figura 4 – Comando tradicional para obtenção da média Neste caso, a variável de interesse trata-se do atributo vlrvenda (valor de venda). Então se aplica o algoritmo para minimizar o acesso ao banco de dados. Com isso identificou-se que existem dois grupos homogêneos, sendo um pertencente aos clientes com idade inferior a 35 anos e outro de clientes com idade igual ou superior a 35 anos. O algoritmo gera a seguinte instrução (Figura 5).

create view viewvendas as select top 900 vlrvenda from tabvendas where idadecliente 35 )

Figura 5 – Instruções produzidas pelo algoritmo A partir da execução do comando acima, a consulta seria realizada a partir do seguinte comando (Figura 6).

select avg(vlrvenda) from viewvendas

11

Figura 6 – Nova instrução para consulta gerencial

5 CONCLUSÃO Pode-se observar a partir do desenvolvimento deste artigo que o tempo para processamento de consultas foi minimizado. Entretanto, observou-se benefícios significativos somente ao aplicá-lo em bases de dados com volume considerável. Nos outros casos, o ganho foi pouco perceptível. Relatórios e consulta que possuem a mesma variável de interesse podem compartilhar a mesma expressão de consulta. Não é esperado que esta técnica seja comparada ao data warehouse. Espera-se que a técnica possa auxiliar na extração de dados ainda não replicados no data warehouse.

Esta técnica não pode ser utilizada quando se espera obter dados exatos, como por exemplo, informações utilizadas como base para efetuar pagamentos. Neste caso, deve-se utilizar técnicas tradicionais. Para trabalhos futuros, sugere-se: • Implementação em linguagem SQL ANSI para utilização em outros SGBDs; • Estender o funcionamento dos procedimentos para utilização de várias tabelas na instrução de seleção;

12

• Estudar estratégias para detecção e geração de índices para agilizar ainda mais o processo de consulta; • A geração de expressões SQL dos atributos poderia ser realizada em um processo em lote fora do horário de trabalho de pico; • Estudar a validade de se implementar um dicionário no banco de dados para armazenar as informações sobre as expressões de consulta; • Melhorar o procedimento para utilizar atributos binários ou dicotômicos na geração das expressões de consulta; • Melhorar o procedimento para executar um processo recursivo na obtenção dos filtros de consulta.

REFERÊNCIAS COCHRAN, William Gemmell. Sampling techniques. 3.ed. New York: J. Wiley, c1977. 428p

CODD, E.F. A relational model of data for a large shared data banks. Communications ACM, V. 13, n. 6, p. 377-387, 1970. DATE, C. J, Introdução a sistemas de bancos de dados. Rio de Janeiro Campos, 2003. JOHNSON, Norman L; SMITH, Harry. New developments in survey sampling. New York: John Wiley & Sons, 1969.

13

NEYMAN J. On two different aspects of the representative method: the method of stratified sampling and the method of purposive selection. J. [s. l]: Royal Stat. Soc. B. 97, 558–606. 1934 STAIR, Ralph M.; REYNOLDS, George W. Principles of information systems: managerial Approach. 3.ed Cambridge: Course Technology, c1998. REZENDE, Denis Alcides; ABREU, Aline França de. Tecnologia da informação: aplicada a sistema de informações empresariais. São Paulo: Atlas, 2000. SARNDAL, C. E.; SWENSSON, B.; WRETMAN, J. Model assisted survey sampling. New York: Springer-Verlag, 1992. SILBERCHATZ, Abraham; KORTH, Henry F.; SUDARSHAN, S. Database system concepts. [s. l.] McGraw-Hill, 1999. Tull, Donald S.; Albaum, Gerald S. Survey Research: a decisional approach. New York: Intext, 1973.

©

Breve Currículo

¹Mestrando no Departamento de Informática e Estatística da UFSC. Professor e Coordenador do Curso de Tecnologia em Redes de computadores do CESBLU. ²Professor Titular do Departamento de Informática e Estatística da UFSC.