# Introdução

O objetivo deste documento é apresentar o projeto da disciplina Processamento de Dados Massivos do curso de mestrado em Ciência da Computação. O projeto consiste no projeto, implementação e avaliação experimental de um arcabouço para agregação eficiente em dados temporais em bancos de dados não relacionais.

## Motivação e Justificativa

A tecnologia NoSQL é idealizada pelos desenvolvedores da Web 2.0 e comunidades que perceberam que os bancos de dados relacionais não são ideais para o gerenciamento de sites de redes social em tempo real onde os dados são volumosos e heterogêneos (Lee, Tang, and Choi 2012).
Especificamente, NoSQL se refere à classe de sistemas de armazenamento de dados que é significativamente diferente dos bancos de dados relacionais convencionais. Por exemplo, NoSQL não exige esquema pré-definido, relacionamento e chaves. Consultas de junções também não são suportadas.
Bancos de dados NoSQL são de baixo custo, sem esquema rígido e horizontalmente escaláveis para novos recursos computacionais sobre demanda, essa escalabilidade horizontal também é conhecida como sharding. Os bancos NoSQL podem ser dos tipos:
(i) Key/Value, que é simplesmente o armazenamento de várias chaves e um valor para cada uma delas;
(ii) Wide column store, que é um armazenamento inspirado no Big Table da Google e suporta várias linhas, colunas e sub colunas;
(iii) Document store, onde os dados são armazenados em formas de documentos JSON ou similares; e
(iv) Graph store, que armazenam grafos e fornecem meios de navegação no grafo.
Todos esses tipos são paradigmas diferentes dos bancos relacionais (Cattell 2011). Especificamente nos bancos de dados de chave-valor (key/value) orientado a documentos (Document store), os dados são armazenados em coleções e cada coleção contém um ou mais documentos. Comparando com bancos de dados relacionais, coleções são análogas às tabelas e documentos são análogos aos registros (linhas da tabela).
As tecnologias para bancos de dados NoSQL têm evoluído constantemente. Porém, ainda não existe suporte a consultas temporais. Bancos de dados temporais é um tema relevante da área de Bancos de Dados, estando bem consolidado e exaustivamente discutido nos mais diversos contextos (bancos de dados relacionais, orientado a objetos, XML, e afins). Por exemplo, frequentemente aparecem situações em que é necessário manter o histórico de como os registros mudam com o tempo. Bancos de dados temporais tradicionais resolvem esse problema e fornecem maneiras eficientes de consultar os dados temporais através da linguagem de consulta TSQL2 (R. T. Snodgrass 1995).
Um dado temporal pode ser unitemporal ou bitemporal. Um dado unitemporal armazena a informação do período em que o dado existe no banco de dados temporal. O dado bitemporal além de armazenar o período em que o dado existe, também armazena o período em que ele é válido. Dessa forma, os dados bitemporais permitem que haja um dado que exista no banco de dados em um determinado período mas não seja válido neste mesmo período. Tanto os dados unitemporais quanto os bitemporais podem ser implementados como uma linha em uma tabela de um banco de dados relacionais (Johnston and Weis 2010). A Figura abaixo ilustra a diferença entre esses tipos.
LINK PARA FIGURA
Uma tabela não temporal pode ser mapeada para o modelo unitemporal através da adição de dois meta campos, bd e ed, para cada linha. bd indica a data inicial da qual a linha existe e ed indica a data final. A chave primária, pk, da nova tabela é composta pela chave primária da tabela não temporal e pelos novos campos bd e ed. Assim, uma linha da tabela não temporal pode ter várias versões na tabela unitemporal, cada uma delas representa o dado em um período diferente de tempo. De maneira análoga, uma tabela não temporal pode ser mapeada para o modelo bitemporal através da adição de quatro meta campos bd1, ed1, bd2 e ed2. Neste caso, bd1 e ed1 indica o período em que o dado existe e bd2 e ed2 indica o período em que o dado é válido.
Até agora, as implementações mais famosas de bancos de dados temporais foram escritas para bancos de dados SQL ou XML (Wang and Zaniolo 2008) (Wang, Zaniolo, and Zhou 2008). Neste projeto, introduzimos funções temporais para um banco de dados NoSQL orientado a documentos (schemaless). Esse novo banco de dados traz grandes benefícios para a área de bancos de dados e significa um avanço nos bancos de dados NoSQL pois permite unir todas as vantagens e tendências dos bancos NoSQL com as vantagens de um banco de dados temporal. Dessa forma, torna possível, por exemplo, lidar com grandes volumes de dados temporais através de fácil particionamento horizontal usufruindo de toda a flexibilidade de utilizar em esquema não rígido, que pode sofrer mutações com o tempo se adequando ao contexto do tempo em que o dado existe.
Com relação à implementação das características temporais, existem algumas questões que os gerenciadores de bancos de dados precisam resolver. Regras de restrição de integridade referencial (chave estrangeira) são um pouco mais complexas, quando um registro é removido em cascata em bancos de dados temporais relacionais. Neste caso, registros em estados antigos da base podem referenciar o dado atual a ser removido; tais registros não podem ser removidos em cascata uma vez que serão necessários para consultar um estado antigo da base. Essas questões de restrição de integridade não são um problema para bancos de dados NoSQL orientados a documentos porque esse tipo de banco não suporta chaves estrangeiras.
Outra questão relevante na implementação de um banco de dados temporal é a eficiência das consultas de agregação, que normalmente são caras porque precisam de relacionar os dados recuperados na consulta. Por exemplo, suponha um banco de dados de funcionários, a tarefa de calcular a média do salário dos funcionários para cada departamento é custosa. É necessário recuperar todos os funcionários, agrupar por departamento, em seguida somar os valores dos salários por grupo e dividir pelo número de funcionários de cada grupo. Em um banco de dados temporal, o custo é ainda maior porque antes de realizar esses procedimentos é necessário descobrir quais registros do banco são pertinentes no período de tempo especificado. O banco de dados temporal tem de ser bem projetado para consultar o mínimo de registros possível nessas consultas para ter um bom desempenho.
Tendo em vista os benefícios dos bancos NoSQL e a tendência da Web em usá-los para sistemas de tempo real e alta disponibilidade, percebe-se que essa tecnologia tem grande potencial e é um tema relevante e atual. Apesar disso, ainda há uma carência de funcionalidades temporais nesses bancos. Funcionalidades temporais são necessárias em diversos cenários, por exemplo, em serviços de auditoria (quando frequentemente se faz necessário analisar dados passados através de consultas complexas, como as que envolvem agregação). Um banco de dados temporal viabiliza essa análise de maneira muito prática. Por isso, desenvolvimento de métodos eficazes para consultar e agregar dados temporais em ambientes NoSQL mostra-se necessário.

## Objetivos Gerais e Específicos

O objetivo geral deste projeto consiste em desenvolver um arcabouço em um ambiente NoSQL, com dados orientados a documentos, para permitir realizar consultas complexas, como de agregação, em dados temporais de forma eficiente.
O arcabouço foi montado a partir de um banco de dados NoSQL existente e, portanto, os objetivos específicos do projeto foram:
(i) Elaborar um modelo de armazenamento de dados e processamento de consultas que permita manter o histórico do banco de dados em qualquer momento passado do tempo.
(ii) Implementar um mecanismo que garanta a consistência dos dados temporais de forma que os intervalos de tempo armazenados em diversos registros sempre formem uma linha contínua.
(iii) Definir uma interface de consulta temporal e implementar um proxy para o driver do banco de dados para aceitar consultas temporais e convertê-las para consultas nativas utilizando os meta campos temporais definidos no modelo de armazenamento de dados definido no objetivo (i).
(iv) Realizar o sharding do banco de dados de forma a garantir a eficiência das consultas temporais mesmo em bases grandes e em cenários de agregação.

# Revisão Literária

Este capítulo revisa a literatura relevante relacionada a bancos de dados temporais e bancos de dados NoSQL. Ao final, é discutido como este trabalho se compara aos trabalhos citados.

## Banco de Dados Temporais

Um banco de dados convencional apaga o dado antigo quando é atualizado. Assim, apenas os dados atuais residem no banco. Em algumas aplicações não é apropriado descartar os dados antigos. Nesses casos, é necessário associar valores de tempo aos dados para indicar seus períodos de validade (Codd 1983). A incorporação de tempo impõe uma ordem cronológica dentro do banco de dados. Esses bancos são chamados de bancos de dados temporais. O tempo tem papel importante no processamento dos dados (Bolour et al. 1982).
Jones, et al. (S. Jones and Mason 1980) (Susan Jones, Mason, and Stamper 1979) e Snodgrass (R. Snodgrass 1987) desenvolveram modelos para bancos de dados temporais. Eles desenvolveram linguagens de consulta poderosas e as implementaram. As ideias básicas deles sobre os fundamentos do modelo são essencialmente iguais. Eles consideram o tempo de início e tempo de término como atributos especiais. Esses atributos especiais são usados para consultar o banco de dados em diferentes estados do tempo.
Snodgrass (R. Snodgrass 1987) fornece uma semântica para uma linguagem temporal chamada TQUEL que provê processamento de consultas temporais usuais através dos campos de início e término. Ben-Zvi (Ben-Zvi 1982) e Gadia (Gadia 1988) propõem modelos diferentes para bancos de dados temporais e definem a álgebra relacional para as consultas de seus modelos.

## Banco de dados NoSQL

Sistemas de gerenciamento de bancos de dados hoje são a tecnologia predominante para armazenar dados estruturados na web em aplicações de negócios. Desde 1970 (Codd 1983) esses armazenamentos de dados, baseando em cálculos relacionais e fornecendo facilidades ad hoc para consultas SQL (Chamberlin and Boyce 1974), vêm sendo adotados frequentemente e são entendidos como a única alternativa para armazenamento de dados acessível para múltiplos clientes de forma consistente.
Apesar de terem surgido abordagens diferentes nesses anos como bancos de dados XML, essas tecnologias nunca foram adotadas tão amplamente no mercado como foram os RDBMs. (Pokorny 2011). Nos últimos anos, entretanto, o pensamento "one size fits all" fez com que a forma de armazenamento de dados fosse repensada, tanto no meio acadêmico quanto no meio empresarial. Isso encadeou o surgimento de uma grande variedade de bancos de dados alternativos. Essas alternativas são frequentemente generalizadas como NoSQL, que tem como característica usarem esquemas não relacionais (Obasanjo 2009).
Apesar de ser uma tecnologia relativamente nova, NoSQL é significativo por ser uma abordagem frequente de bancos de dados para computação em nuvem e em sistemas de grande volumes de dados (Lee, Tang, and Choi 2012). A alta taxa de adoção dos bancos NoSQL em sistemas de computação em nuvem pode ser explicada principalmente pela alta facilidade de fazer sharding nesses bancos, o que possibilita dividir o armazenamento dos dados em várias máquinas de maneira mais simples do que nos bancos de dados relacionais, que normalmente exigem uma remodelagem agressiva do esquema para realizar o sharding.

## Enquadramento deste trabalho no Estado da Arte

Conforme apresentado neste capítulo, estudos sobre banco de dados temporais estão bem consolidados e estudos de banco de dados não relacionais têm sido realizados em diversos trabalhos. Entretanto, as duas áreas não são estudadas em conjunto. Especificamente, este trabalho teve por finalidade definir e implementar um arcabouço de banco de dados temporal em uma estrutura de dados NoSQL orientada a documentos. É importante ressaltar que esta é a primeira vez que esta combinação de estudos foi feita. Obteve-se um arcabouço com alta escalabilidade, fácil particionamento horizontal (sharding), modelo de dados flexível (schemaless) e alto desempenho em consultas temporais de agregação.

# Desenvolvimento

A proposta deste trabalho consiste em criar um banco de dados temporal NoSQL orientado a documentos. O ponto de partida para este trabalho foi o banco de dados open source MongoDB. A implementação foi feita através de um Proxy do driver de Python (pymongo) para o MongoDB.

## Proxy do banco de dados

As rotinas de UPDATE, DELETE e INSERT foram reescritas para não apagarem os dados antigos em um comando de atualização ou remoção. Além disso as novas rotinas são responsáveis por preencher meta campos nos documentos para indicar o período de validade de cada dado.
Os meta campos têm como objetivo principalmente de viabilizar o uso do conceito de temporalidade no banco de dados. Para isso, são definidos os campos:
* _id_pai: o id do documento com a última versão dos dados em questão.
* _inicio: data em que o documento foi inserido no banco.
* _fim: data em que o documento passou a ser inválido.
Junto à adição meta campos, a modificação de rotinas possibilita o funcionamento proxy do banco de dados junto às abstrações da temporalidade em questão.
A rotina do UPDATE, por exemplo, foi substituida por:
* Atualiza a data de _fim para a data atual.
* Clona o documento no banco e realiza as atualizações nesse novo documento.
* A data de início do documento clonado passa a ser a data atual e a data de fim passa a ser nula.
* O _id documento original é atribuído ao campo _id_pai do documento clonado.
No exemplo de um sistema de banco de dados de um empresa, teríamos então o seguinte cenário: um funcionário, João Silva, cujo salário inicial era de 1.000, teve o valor aumentado para 2000 no dia 13/12/2012. No banco de dados, o documento que armazena os dados do salário do funcionário João Silva passa por um operação de UPDATE, que segue toda lógica explicada anteriormente.
Desta forma, o estado do banco passa de:
Para:

## Linguagem de consulta

Foi definida uma linguagem de consulta temporal para o banco de dados e o Proxy do MongoDB foi especializou o método de consulta para fazer o parser desta nova linguagem e convertê-la para uma consulta nativa que utiliza os meta campos de validade dos dados.
Foi definido um novo operador $dbDate que aceita as seguintes sintaxes:
* {$dbDate: <date>}: faz uma query no estado do banco em uma data específica.
* {$dbDate: {$gte: <date>, $lte: <date1>}}: faz uma query em estados de um intervalo de tempo específico.
Considere os seguintes exemplos:
A consulta 1 seleciona todos os empregados com o salário maior do que 1.000,00 no dia 01/01/2012. Já a conulta 2 seleciona todos os empregados que tiveram o salário maior do que 1.000,00 em algum momento do ano de 2012.
O Proxy do método de consulta irá interpretar essas consultas e transformá-las respectivamente nas seguintes consultas:
O operador $dbDate foi transformado em operadores de nativos do MongoDB e as consultas passaram a usar os meta campos temporais de forma trasparente para o usuário. Na primeira consulta, a data de início deve ser menor ou igual a data do estado do banco desejada. A data de fim deve ser maior do que a data desejada ou igual a nulo. A segunda consulta foi elaborada de forma análoga.
Uma consulta sem o operador $dbDate também é transformada. Considere a consulta abaixo.
Por definição, uma cosulta sem o operador $dbDate considera apenas os registros do estado atual do banco, por isso, a consulta acima é transformada para a seguinte:
Sempre que uma consulta pesquisa pelo campo _id é necessário transformar a query para utilizar o campo _id_pai, já que a cada atualização de um registro implica na criação de um novo documento com um novo _id. O campo _id_pai recebe o valor do _id original para indicar qual é o documento referenciado.
Dessa forma, a seguinte consulta:
é transformada para:

# Experimentos

Por fim, o arcabouço desenvolvido foi testado com grandes dados particionados horizontalmente em várias máquinas e agrupados pelos meta campos de validade dos documentos. Nesta etapa final, a metodologia proposta foi avaliada experimentalmente.

## Base de dados

A base de dados utilizada é de um software de vendas de uma empresa de elevadores. Cada possível venda é representada por um documento da coleção de elevadores. Esses documentos sofrem atualizações diárias com dados do local de instalação do elevador, o registro de ligações feitas para o cliente, a possibilidade de fechamento da venda e vários outros campos que serão omitidos no exemplo de documento abaixo em prol da didaticidade.
O documento acima é uma representação parcial de uma possível venda de elevador. No contexto da empresa de vendas, é necessário fazer consultas no estado atual do banco para acompanhar as vendas e também é necessário fazer consultas temporais para analisar a evolução da venda com o tempo e fazer mineração de dados para obter padrões de evolução de venda que levam ao fechamento da venda ou não.
A base de dados tem outras coleções além da de elevador, mas nos exemplos mostrados neste trabalho vamos focar na coleção de elevador apenas.
Esta coleção possui 1.978.201 documentos representando 48.117 possibilidades de vendas únicas. Portanto, cada venda tem aproximadamente 41,1 alterações. O tamhno ocupado pela coleção é de 25,43 GB.

## Particionamento de dados e índices

Os dados foram particionados em três máquinas virtuais, cada uma com 8GB de RAM e 10GB de HD. O campo de particionamento foi o _fim. Isso possibilita que todos os dados atuais da base (que tem o campo _fim nulo) fiquem na mesma máquina, proporcionando um ganho de performance para consultas no estado atual da base.
Foram criados índices nos campos de _inicio, _fim e _id_pai. Esses índices são usados em praticamente todas as consultas temporais e otimizam as consultas em estados antigos da base de dados.

## Resultados

Para testar a performance do banco de dados, foram selecionadas duas consultas de agregação.
A primeira consulta calcula a média dos preços dos elevadores no estado atual da base. A segunda consulta calcula a média dos preços dos elevadores no estado da base do dia 20/06/2011.
A primeira consulta executou em 0,922 segundos e pesquisou 48.117 documentos quando executada em um ambiente de uma única máquina. Quando executada em um ambiente de 3 máquinas, foram gastos 0,987 segundos e 48.117 documentos foram consultados. O gráfico abaixo mostra este resultado.
LINK PARA O GRAFICO 1 (EPS)
LINK PARA O GRAFICO 1 (PNG)
O tempo de execução da primeira consulta em ambiente com várias máquinas e ambiente com uma máquina apenas é quase igual porque é uma consulta no estado atual da base e o particionamento horizontal garante que os dados atuais fiquem agrupados na mesma máquina.
A segunda consulta executou em 1.291 segundos e pesquisou 453.839 documentos quando executada em um ambiente de uma única máquina. Quando executada em um ambiente de 3 máquinas, foram gastos 1.677 segundos e 453.839 documentos foram consultados. O gráfico abaixo mostra este resultado.
LINK PARA O GRAFICO 2 (EPS)
LINK PARA O GRAFICO 2 (PNG)
O tempo de execução da consulta temporal é baixo porque os índices nos meta campos _inicio e _fim garantem que o mínimo de decoumentos possíveis sejam consultados para simular o estado passado do banco de dados.

# Conclusão

Este trabalho introduziu funcionalidades temporais em bancos de dados NoSQL de forma escalável. É possível trabalhar com grande qantidade de dados, manter o histórico de atualizações sobre eles e consultar estados passados dos dados de maneira eficiente.
Como trabalhos futuros pretende-se implementar as funcionalidades temporais diretamente no código fonte de um banco de dados NoSQL ao invés de fazer um Proxy. Essa implementação trará mais ganho de performance para as consultas.

# Referências

Ben-Zvi, Jacov. 1982. “The time relational model.”
Bolour, A., T. L. Anderson, L. J. Dekeyser, and Harry K. T. Wong. 1982. “The Role of Time in Information Processing: A Survey.” SIGMOD Record 12: 27–50. http://dblp.uni-trier.de/db/journals/sigmod/sigmod12.html#BolourADW82.
Cattell, Rick. 2011. “Scalable SQL and NoSQL data stores.” SIGMOD Rec. 39 (may): 12–27. doi:10.1145/1978915.1978919. http://doi.acm.org/10.1145/1978915.1978919.
Chamberlin, Donald D., and Raymond F. Boyce. 1974. “SEQUEL: A structured English query language.” In Proceedings of ACM SIGFIDET workshop on Data description, access and control, 249–264. New York, NY, USA: ACM. doi:10.1145/800296.811515. http://doi.acm.org/10.1145/800296.811515.
Codd, E. F. 1983. “A relational model of data for large shared data banks.” Commun. ACM 26: 64–69. doi:10.1145/357980.358007. http://doi.acm.org/10.1145/357980.358007.
Gadia, Shashi K. 1988. “A homogeneous relational model and query languages for temporal databases.” ACM Trans. Database Syst. 13: 418–448. doi:10.1145/49346.50065. http://doi.acm.org/10.1145/49346.50065.
Johnston, Tom, and Randall Weis. 2010. Managing Time in Relational Databases: How to Design, Update and Query Temporal Data. Morgan Kaufmann.
Jones, S., and P. J. Mason. 1980. “Handling the Time Dimension in a Data Base.” In International Conference on Databases, 65–83.
Jones, Susan, Peter Mason, and Ronald K. Stamper. 1979. “LEGOL 2.0: A relational specification language for complex rules.” Inf. Syst. 4: 293–305.
Lee, Ken Ka-Yin, Wai-Choi Tang, and Kup-Sze Choi. 2012. “Alternatives to relational database: Comparison of NoSQL and XML approaches for clinical data storage.” Computer Methods and Programs in Biomedicine. doi:10.1016/j.cmpb.2012.10.018. http://www.sciencedirect.com/science/article/pii/S0169260712002805.
Obasanjo, Dare. 2009. “Building scalable databases: Denormalization, the NoSQL movement and Digg.” http://www.25hoursaday.com/weblog/2009/09/10/BuildingScalableDatabasesDenormalizationTheNoSQLMovementAndDigg.aspx.
Pokorny, Jaroslav. 2011. “NoSQL databases: a step to database scalability in web environment.” In Proceedings of the 13th International Conference on Information Integration and Web-based Applications and Services, 278–283. New York, NY, USA: ACM. http://doi.acm.org/10.1145/2095536.2095583.
Snodgrass, Richard. 1987. “The temporal query language TQuel.” ACM Trans. Database Syst. 12: 247–298. doi:10.1145/22952.22956. http://doi.acm.org/10.1145/22952.22956.
Snodgrass, Richard T., ed. 1995. The TSQL2 Temporal Query Language. Kluwer.
Wang, Fusheng, Carlo Zaniolo, and Xin Zhou. 2008. “ArchIS: an XML-based approach to transaction-time temporal database systems.” VLDB J. 17: 1445–1463. doi:http://dx.doi.org/10.1007/s00778-007-0086-6.
Wang, Fusheng, and Carlo Zaniolo. 2008. “Temporal queries and version management in XML-based document archives.” Data and Knowledge Engineering 65: 304–324. doi:http://dx.doi.org/10.1016/j.datak.2007.08.002.