\section{Related Work}
\label{sec:RelatedWork}

Spatio-temporal phenomena have been studied by several research communities in the context of several application areas. In the database community, the work of Guting was the first full implementation of a database for coping with moving objects. Based on Guting's and Wolfsonz's work \cite{Wolfson1998} \cite{Guting2000}, Pelekis \cite{Pelekis2007} devised a framework for representing and querying moving objects over Oracle DBMS platform. The database community has mainly focused on management techniques for moving objects and has largely neglected supporting the concept of trajectories as first class objects.

In addition, data collection of trajectories of moving objects currently consists of the acquisition of their positions in time and space that correspond to sample points (i.e. raw data), represented by triples of the form (x, y, t), where $x$ and $y$ denote the coordinate data and $t$ indicates the time in which such data were collected. Most DBMSs used today in transactional applications perform trajectory analysis by storing and processing queries on the raw data, making it difficult to process queries over trajectories, which should regarded as first class objects.

Several methods have been proposed to improve trajectory data analysis, including the use of spatiotemporal databases and data mining techniques. They can be classified according to the following groups: (i) generation of trajectory patterns (e.g.  convergence, encounter, flock and leadership) according to the geometrical properties of trajectories \cite{Laube2005}; (ii) extraction of clusters of sample points from trajectories, basically using time and space to determine trajectories located in dense regions, trajectories with similar shapes or distances, and trajectories that move between regions during the same time  interval \cite{Nanni2006} \cite{Kuijpers2006} \cite{Giannotti2007} \cite{Pelekis2007}; (iii) analysis of  trajectories from a semantic point of view, trying to add context information \cite{Alvares2007} \cite{Guc2008} \cite{Spaccapietra2008} \cite{Palma2008} \cite{Rocha2010} \cite{Moreno2010}; (iv) development of architectures, ETL (Extraction, Transformation and Loading) processes, data models and languages for helping in the construction of trajectory data warehouses (TDWs). This last group is the focus of the work described here and, therefore, the rest of this section surveys this group in more detail.

Data Warehouse (DW) technology has helped many organizations improve their decision-making processes and improve their performance. A DW is a multidimensional database that stores subject-oriented, integrated, time-variant and non-volatile data \cite{Kimball2002}, and is often queried through an OLAP (On-line Analytical Processing) tool that is aimed at multidimensional processing of data extracted from DWs, allowing these data to be analyzed in different perspectives and levels of aggregation \cite{Chaudhuri1997}. There has been a number of proposals in the literature aimed at integrating functionality and characteristics related to trajectory data and data warehouse systems \cite{Orlando2007a} \cite{Orlando2007b} \cite{Pelekis2008} \cite{Marketos2008} \cite{Leonardi2009} \cite{Baltzer2008}. The main goal is to enable the storage of trajectory data in a data warehouse and to provide multidimensional processing with the capability of querying these trajectories according to several perspectives of analysis in order to support strategic decision-making processes related to moving objects. This kind of environment has been referred to as Trajectory Data Warehouses (TDWs). 

In \cite{Marketos2008}, data originated from GPS sensors were loaded into a trajectory warehouse by using a set of ETL (Extract, Transform and Load) procedures. In addition, mechanisms for performing spatio-temporal aggregations analytical queries over trajectory data are detailed in \cite{Leonardi2009}. Moreover, based on the trajectory conceptual model proposed in \cite{Spaccapietra2008}, a conceptual model schema for TDW that is aimed at supporting the monitoring of athletes' biochemical data is discussed in \cite{Moura2010}. However, these biochemical data are not organized into dimensional data structures, through the use of fact and dimension tables and the representation of different levels of aggregation. In fact, traditional data warehouse techniques and current analytical tools do not satisfy the requirements of TDW applications because the representation and aggregation of trajectories imply the need for the modeling and aggregation of varied and interrelated data types, such as geometries, context information and spatiotemporal objects.  Consequently, there is still no consensus about how trajectories are modeled multidimensionally, organized in different levels of aggregation and used for answering aggregation queries of OLAP systems.

Even though the advantages of spatiotemporal data warehouses have been known for some time, as far as we know, no commercial business intelligence solutions employ TDWs today. In \cite{Orlando2007a}, the first proposal of a DW for trajectories defines an OLAP data cube with both spatial and temporal dimensions, and a set of spatiotemporal hierarchies determined through the use of regular grids. Both numerical and spatial measures are proposed for this TDW.  Some other studies have been conducted to help the development and widespread use of TDWs. However, none of them deals with the semantic aspect of trajectories that are rarely treated as first class objects and, thus, the resulting multidimensional analysis lacks knowledge about the discovered multidimensional patterns. 

In this paper, two modeling approaches, both based on design patterns, are proposed for designing trajectory data schemas of transactional and multidimensional environments, in which trajectories are considered as first class objects. This enables the creation of reports and other outputs that tend to be much richer than those whose spatiotemporal data are handled as a sample of points with no associated semantics.  Also, a case study based on real truck trajectories was developed to illustrate how both real time and historical trajectories are modeled and queried in a way that facilitates analysis and reporting.

%Um dos pioneiros na descoberta de conhecimento a partir de dados de objetos móveis foi o projeto GeoPKDD\footnote{www.geopkdd.eu} (\textit{Geographic Privacy-aware Knowledge Discovery and Delivery}), que tinha como objetivo o desenvolvimento de métodos para representar, armazenar e
%gerenciar objetos móveis, prevendo, ainda, a possibilidade que estes pudessem mudar sua geometria ao longo da trajetória. Para isso, o foco estava no desenvolvimento de metodologias para data warehousing e data mining que suportassem trajetórias de objetos móveis. Grande parte do esforço do projeto foi empregado na extração e transformação dos dados de trajetórias, a partir dos quais, eram realizados os processos de mineração de dados para descoberta e extração de conhecimento. No entanto, pouco esforço foi despendido na pesquisa sobre a aplicação de técnicas de data warehousing e OLAP com essa finalidade. Outro projeto que, atualmente, realiza pesquisas para descoberta de conhecimento a partir de dados de mobilidade é o MODAP\footnote{www.modap.org}
%(\textit{Mobility, Data Mining and Privacy}). Este atua na coordenação e incentivo a atividades de pesquisa em temas que envolvem mobilidade, mineração
%de dados e privacidade.

%Nos SGBDs atuais, a análise de trajetórias é limitada ao armazenamento e e realização de consultas sobre os dados brutos, tornando difícil a obtenção de qualquer informação de análise em alto nível sobre esses dados. A partir dessa dificuldade, o trabalho \cite{Spaccapietra2008} oferece uma solução conceitual para modelagem de trajetórias através de anotações semânticas permitindo, assim, que trajetórias possam ser vistas como entidades de primeira ordem, possibilitando o desenvolvimento de aplicações baseadas em trajetórias. São propostas duas alternativas: uma baseada em padrões de projetos através da definição de esquemas e estruturas para representação de trajetórias em banco de dados permitindo maior flexibilidade para alteração do esquema e inicial, enquanto a segunda alternativa se baseia na definição de tipos específicos para encapsulamento e definição de métodos próprios capazes de lidar com os aspectos geométricos e atributos, sendo mais próxima do nível de implementação para a escrita de programas que manipulam objetos ou para a escrita de consultas SQL que retornam uma coleção de elementos. A visão de trajetória como objeto de primeira ordem, bem como a abordagem através de tipificação são usadas como ponto de partida para as contribuições apresentadas em nosso trabalho.

%Spatio-temporal phenomena has been studied in several research communities. Particularly, trajectory data has been extensively studied in geoinformatics, data mining, visual analytics, and database [refs]. 

%In database community, the work of Guting was the first full implementation of a datase for coping with moving objects....

%Based on Guting's and Wolfson's work, Pelekis devised a framework for representing and querying moving object over Oracle DBMS platform....

%Database community has mainly focused in management techniques for moving objects but has neglected supporting the concept of trajectories in the application point of view.... 

%O trabalho \cite{Guting2000} oferece uma solução para representação e realização de consultas sobre dados espaço-temporais com suporte, também, para objetos móveis através da definição de tipos abstratos e extensão de linguagem de consulta para SGBD que influenciou bastante as idéias iniciais de contribuição deste trabalho, porém, o banco de dados para objetos móveis proposto não satisfaz inteiramente nossas necessidades pois não apresenta trajetória como objeto complexo de primeira ordem com medidas e valor semântico associado para uma visão mais próxima da realidade. No trabalho uma trajetória é vista como o retorno de um operador aplicado a um tipo abstrato, o que dificulta a manipulação de medidas de forma direta além de não viabilizar a criação de métodos de manipulação próprios para trajetórias. Para obter o comprimento de uma trajetória, por exemplo, deve-se instanciar um elemento construído a partir de uma consulta que retorna um tipo abstrato e sobre esse elemento deve ser aplicado o operador para construção de trajetória e, sobre o resultado desse operador deve ser chamada a operação que retorna o tamanho como mostrado:

%\noindent
%LET route = (SELECT r	FROM flight WHERE airline = "LH" and no = 257);\\
%length(trajectory(route));

%\noindent
%Com o objetivo de modelar e consultar sobre objetos móveis, o \textit{HERMES} \cite{Pelekis2006}, \cite{Pelekis2006a}, que é uma extensão do \textit{STAU} \cite{Pelekis2002}, \cite{Pelekis2005}, se utiliza de extensão objeto-relacional de SGBD para prover funcionalidades com respeito a trajetórias através da definição de tipos e um conjunto de operações como uma extensão do Oracle. A definição de tipos e operações para manipulação em SGBDOR fornece uma representação mais próxima da realidade. Contudo, ainda um pouco distante da manipulação do ponto de vista de objetos complexos com características e métodos próprios, até mesmo porque essas contribuições são feitas para serem o mais geral possível para objetos espaço-temporais e não somente específicas para trajetórias.

%Algumas características, problemas e requisitos envolvidos na construção de um DW de trajetórias são apresentados em \cite{Orlando2007} onde se destacam o os problemas do processamento e armazenamento de medidas obtidas por agregação holística demonstrado através do problema da contagem para uma medida de presença, a qual retorna o número de trajetórias distintas em uma célula nas operações de \textit{roll-up}. Propõem, ainda, um modelo para data warehouse de trajetórias implementado no Oracle e realizam uma avaliação sobre os desafios de projeto - como viabilidade e desempenho - e do processo de ETL com experimentos realizados com dados reais e fictícios. É importante ressaltar que o modelo de TrDW proposto somente armazena informações agregadas sobre as trajetórias, as trajetórias de fato são armazenadas e representadas em um BD de objetos móveis da qual são extraídas as informações que alimentam o DW. No mesmo contexto temos ainda o trabalho de \cite{Marketos2008} que trata de forma mais detalhada a reconstrução de trajetórias a partir de dados \textit{raw}, o processo de ETL para povoar o DW que, também, armazena informações agregadas e, para isso, destaca a importância das funções de agregação.

%Buscando-se na literatura a respeito de trabalhos que tratam de funções de agregação para suporte à análise sobre dados de trajetórias, percebe-se que, ainda, não há trabalhos que ofereçam uma solução definitiva para representação e manipulação com essa finalidade. Contudo, encontramos trabalhos relevantes nos 
%quais suas contribuições podem ser usadas, de maneira pontual, como partes para a solução do problema. O escopo de análises de trajetórias, tanto no modelo OR proposto, quanto no DW, invariavelmente envolve a utilização de funções de agregação. E, para nortear a definição de nossas funções nós adotamos a classificação do trabalho \cite{Silva2008} que, apesar de abordar somente OLAP Espacial (SOLAP), tem como proposta um conjunto de funções de agregação para medidas espaciais, bem como uma proposta de classificação para as mesmas que se enquadra, também, em nosso trabalho. Outros trabalhos como o de \cite{Baltzer2008}, \cite{Jeung2008}, \cite {Giannotti2007} e \cite{Lee2007} apresentam contribuições que podem ser tomadas como base para funções de agregação holísticas  cujas definições e implementações envolvem estudos mais complexos e com pouca literatura a respeito.

