Gerenciamento de Data
Streams – uma introdução
AULA 21
PGC 107 - Sistemas de Banco de Dados
Profa. Sandra de Amo
Pós-graduação em Ciência da Computação – UFU
2012-2
1
Dados em Fluxo
 Sensores no oceano: dados de temperatura,
salinidade, ventos, humidade
 Satélites em órbita terrestre: dados
climáticos, vegetação, incêndios,
inundações, telefonia, internet
 Captores de dados biológicos: temperatura,
pressão arterial, batimentos cardíacos, nível de
insulina
2
Principais características dos dados
em fluxo
1. Dados novos chegam em grande quantidade e em
grande velocidade
Exemplo: Sensor no oceano: dados de temperatura, salinidade, ventos,
humidade (10 medidas por segundo)
 Milhares de sensores flutuantes enviando dados: localização,
temperatura local, salinidade, pressão, humidade
 10 medidas por segundo = 3,5 terabytes de dados por dia
3
Principais características dos dados
em fluxo
2. Impossibilidade de armazenamento dos dados em
sua integralidade

Requer memória ilimitada !
Solução :

Respostas a consultas não são exatas

Respostas a consultas são obtidas a partir de:



processamento em “batch”
amostragem dos dados ou
um sumário dos dados
4
SGDS versus SGBD
SGBD
SGDS
5
Como obter respostas aproximadas

Processamento em “batch” :


Utilizado quando a operação de update é rápida
mas a operação de computar a resposta é lenta:
Dados são processados em “batches”:



Dados são inseridos no buffer a medida que chegam
Dados antigos são descartados quando não cabem no
mais buffer
A resposta à consulta é calculada periodicamente
sobre os dados armazenados no buffer no momento
em que a consulta é submetida.
Como obter respostas aproximadas

Amostragem



Executar consulta sobre uma amostra dos dados
Utilizado quando a operação de update é lenta
mas a operação de computar a resposta é rápida
Sumarização


Manter uma estrutura de dados que guarda uma
sinopse dos dados
Reduz o tempo para calcular a resposta e o
espaço para armazenar os dados.
Consultas em Data Streams


Consultas Contínuas

Consulta submetida continuamente a cada determinado intervalo de
tempo
Q1, Q2, ..., Qn, ....
Consultas Ad-hoc

Referenciando dados passados

Solução 1


Resposta é dada considerando o tempo inicial como o tempo t em
que a consulta foi submetida.
Solução 2


Sumário dos dados é mantido pelo gerenciador.
Consulta é executada sobre o sumário dos dados
Referência

Projeto STREAM de Stanford

B.Babcock et al. 2002 : Models and Issues in Data Stream Systems. ACM
PODS 2002. Projeto

Stanford STREAM Project http://infolab.stanford.edu/stream/

Técnicas de Amostragem, Filtragem e Sumarização dos dados:

A. Rajaraman, J. Leskovec, J.D.Ullman: Mining of Massive Datasets, 2010.

http://infolab.stanford.edu/~ullman/mmds/book.pdf

Sintaxe e Semântica rigorosas de linguagem de consultas + Implementação
J.Krammer, B. Seeger: Semantics and Implementation of Continuous Sliding
Window Queries over Data Stream. ACM Transaction on Database
Systems, Vol. 34, No 1, Art. 4, 2009.
Linguagens de Consultas para Data
Streams - Requisitos




Uma semântica clara e não-ambigua em
qualquer instante t
Uma álgebra própria que estenda a álgebra
relacional padrão de SQL
Boa expressividade
Implementação eficiente dos operadores
Pesquisa nos anos 2000

Diversas propostas de linguagens de consultas




“soltas”, inexistência de proposta unificada
Semânticas diversificadas
Semânticas não especificadas de forma
rigorosa, somente a partir de exemplos
Exemplos simples de consultas não se
generalizam para casos mais complexos
Modelo de dados em fluxo




Domínio temporal

T = (T, ≤ )

Simplificando: T = {0, 1 , 2 ,...}
Instante t

t = elemento de T
Tupla sobre um esquema relacional R(A1,...,An) : atributos Ai não incluem o
atributo temporal T
Stream puro: sequência (pode ser infinita) de elementos do tipo (e,t) , onde e é
uma tupla sobre R e t é um instante.





Stream puro = dado que chega ao sistema no instante t, proveniente do mundo externo
Exemplo: Temperatura(x,t), onde x é um número real, medida de temperatura enviada
por um sensor no instante t (t = instante em que o dado foi produzido pelo sensor)
(e,t) : pode ser visto como um evento e que ocorreu no instante t
Stream puro = sequência ordenada pelo elemento temporal t
Requisito: número de tuplas com o mesmo t é FINITO.
Tempo de validade versus Tempo do
Sistema

Tempo de validade = instante em que o dado foi produzido
no mundo exterior.


Tempo do sistema = instante em que o dado chega ao
sistema


Este é o tempo que é considerado para o atributo T de um elemento de
dado em fluxo.
Caso um dado u chegue ao sistema sem um tempo de validade, o
sistema associa a u o tempo t do sistema, transformando u em um
elemento (u,t) de dado em fluxo.
Importante: tempo do sistema e tempo da aplicação
(validade) não são sincronizados (em geral são distintos !)
Exemplo de um esquema de banco de
dados em fluxo
Representação de dados em fluxo:
diagrama geral
Stream Lógico


Stream Lógico: Representação utilizada no modelo lógico
conceitual.
Um stream lógico é um multi-conjunto (bag), potencialmente
infinito, de elementos (e,n,t), onde e = tupla, n ϵ N, t um
instante.
 n denota a multiplicidade da tupla e no instante t (quantas
cópias de e foram produzidas no instante t) .
 (e,n,t) : e é válida no instante t e ocorre n vezes em t
Stream Físico


Stream Físico: Representação compacta do stream lógico,
utilizada na implementação dos operadores da álgebra.
Um Stream Físico é um multi-conjunto (bag), potencialmente
infinito, de elementos (e, [ts, tf) ), onde e = tupla, ts e tf são
instantes.
 (e, [ts, tf) ): e é válida no intervalo [ts, tf) , isto é, em
todos os instantes t tais que ts ≤ t < tf
 Dados são ordenados considerando o instante inicial ts
 Não existe ordem entre dois elementos (e, [ts,tf1)) e (e’,
[ts, tf2) )
Stream Chronon

Stream Chronon
 Tipo especial de stream físico, onde os intervalos
de tempo são chronons, isto é, unidades de
períodos de tempo não decomponíveis = duração
minima de tempo do dominio temporal T
 Instante = ponto na linha do tempo
 Chronon = periodo de tempo entre dois
instantes consecutivos na linha do tempo.
 Exemplo: se o tempo é contado em segundos,
então Chronon = periodo de 1 segundo
Transformando uma representação na
outra

Puro  Fisico


Puro  Lógico


(e,t)  (e, [t, t+1) )
S = { (e1,t1), ... }  {(e, n, t) | n = número de elementos iguais a (e,t) em S}
Fisico  Lógico
S = { (e1, [ts1,tf1)), (e2, [ts2,tf2)), ... } 
{(e, n, t) | n = número de elementos (e, [ts,tf)) em S, onde t ϵ [ts,tf ) }
Exemplo: S = { (e, [1,4)), (e, [2,5)), (e’, [1,3)) }
Stream Lógico correspondente ={(e,1,1), (e,2,2), (e,2,3), (e,1,4), (e’,1,1), (e’,1,2) }

Exemplo
Puro x Lógico x Físico
Conversor
Fonte externa do fluxo
Dado (b, t) produzido
no instante t, onde b é uma
sequência de bytes
Dado puro convertido
(e, t)
Dado fisico transformado (e, [ts,tf))
Sistema Gerenciador de Data Streams
Processamento de Consultas: esquema
geral
DSMS PIPES [Kramer 2004]



DSMS = Data Stream Management System
Fornece uma linguagem de consultas onde os
operadores são do tipo Stream  Stream
Formulação das consultas:

Via comandos da linguagem


Linguagem declarativa, semântica rigorosa, não-ambígua,
extensão de SQL.
Via interface gráfica

Permite aos usuários construir planos de expressões algébricas
diretamente, conectando os diferentes operadores da álgebra de
forma apropriada.
Criando um stream puro
Análogo ao Create Table do SQL
CREATE STREAM OpenAuction
(itemID INT, sellerID INT, start_price REAL,
Timestamp TIMESTAMP)
SOURCE establishConnection(‘port341001’, ‘converter’)
ORDERED BY Timestamp
establishConnection: função implementada pelo usuário
Transforma a sequência de bytes chegando na porta 341001 em um stream puro.
Consultas Contínuas
SELECT <lista de atributos> (não inclui timestamp !)
FROM <Stream1> [<WINDOW 1>], <Stream2> [<WINDOW 2>], ...
WHERE
GROUP BY
HAVING
<WINDOW > ::= ( <UNIDADE DE FRAME> <INICIO DO FRAME> )
<UNIDADE DE FRAME>::= ROWS | RANGE
<INICIO DO FRAME> ::= <VALOR> | UNBOUNDED
<VALOR> ::= <INTEIRO POSITIVO> [<UNIDADE>]
<UNIDADE> ::= SECONDS| MINUTES | HOURS | DAYS | MONTHS | YEARS
Exemplo
1) FROM R WINDOW (ROWS 6)
Considera todos os 6 últimos elementos do stream lógico R
2) FROM R WINDOW (RANGE 6 HOURS)
Considera todos os elementos (e,n) do stream lógico R cujo tempo de
validade t dista 6 horas do tempo corrente tc
Intervalo de 6 horas
t
t = instante em que
foi produzido o elemento no
mundo externo
tc
instante da consulta = instante corrente tc
Now Window


A cláusula WINDOW é opcional.
Quando não aparece no FROM

Sistema utiliza uma janela default = now window
1 unidade de tempo
tc
instante da consulta = instante corrente tc
Now window = todos os elementos do stream
produzidos há 1 unidade de tempo e que são
válidos no instante atual tc
Exemplo de consulta
Dê todos os dados sobre as compras que finalizaram após 5 horas
desde o primeiro lance.
SELECT OpenAuction.*
FROM OpenAuction O WINDOW (RANGE 5 HOURS), ClosedAuction C
WHERE O.ItemID = C.ItemID
Intervalo de 5 horas
t
tc
t = instante em que
foi dado o primeiro lance
instante da consulta = instante corrente tc
Semântica da consulta

Consulta submetida no tempo tc

Considera o conjunto O de todos os produtos cujo primeiro lance foi dado
no máximo há 5 horas, a partir do instante corrente tc

Considera o conjunto C de todos os produtos que estão encerrados na
última unidade de tempo (1 segundo ?) a partir do instante corrente tc

Faz a junção de O X C pelo ItemID

Projeta nos atributos de O (ItemID, sellerID, startPrice)