\section{Modeling Trajectory Data}\label{secao:contribuicoes}

We now investigate solutions to support the application requirements we identified before. We propose two solutions that are driven by different modeling objectives. In one scenario, we imagine designers using trajectories as encapsulated objects without worrying about their internal details. For this scenario, we propose a solution which aims at encapsulating trajectories into a dedicated \textit{TrajectoryType} object type, equipped with methods providing access to trajectory components (events). In a second scenario, we suppose that designers want to associate thematic information with parts of the trajectory object, for instance, to associate a list of the closest points of interest with a trajectory event. We describe a solution for this scenario that focuses on the explicit representation of a trajectory and its components, which makes it possible to link application objects to any of these components. 

\subsection{Transactional Environment}\label{sub:datatype}

Extending data models with new data types is the key to provide adequate representation and manipulation of real world complex objects. In the database domain, this technique has been frequently applied in order to reduce the complexity of design and application development. For example, with the creation of new spatial data types, various DBMS were equipped with such types, which greatly facilitated the development of applications dealing with spatial data. The creation of a new data type not only provides comfort to the designer but also enables data management optimizations. Thus, a plausible solution is to define a trajectory data type containing attributes and methods that are useful for instantiating object types and creating attributes of this new type.

Figure~\ref{fig:datatype} shows the proposed trajectory data type. Note that this data type encapsulates two lists: \textit{samplePoints} and \textit{eventList}. The \textit{samplePoints} list represents the sample points collected from the positioning devices and the \textit{eventList} list refers to the semantic segmentation of the trajectory. In fact, according to the semantic trajectory definition (refer to Section~\ref{sec:preliminares}) the idea of capturing the geometric and semantic facet into a single data type is represented respectively by these two lists. An event has application-dependent information. In this case, the designer should provide a function that maps geometric data to event information. Each event is defined by two spatio-temporal points corresponding to the event begin and end, and a textual information about the event.

The proposed trajectory data type encapsulates a set of useful methods for retrieving geometric data (e.g. sample points), computing measures on trajectory data (e.g., length, duration, speed, etc), and accessing events. Due to space limitations, we do not show all the defined data type methods. Indeed, this data type can be extended with other attributes and methods to meet the requirements considered crucial to the application. 

The trajectory data type approach is adequate for applications that only require geometric data and a semantic event view of the trajectories. Whatever semantics the application needs should be explicitly defined by the database designer in the form of attributes of an object type (e.g. moving object), which must contain one attribute of type \textit{TrajectoryType}. Another way to attach semantics is by linking \textit{TrajectoryType} objects to other application objects.

\begin{figure}[tb]
	\centering
		\includegraphics[width=0.45\textwidth]{imagens/datatype2.eps}
	\caption{trajectory data type}
	\label{fig:datatype}
\end{figure}

Since much of the information on trajectories is application dependent, it is not adequate to completely solve this problem by adopting only the data type approach. An adequate solution is to expose \textit{TrajectoryType} components in such a way that additional application semantics may be linked to these components. This exposure is achieved by decomposing \textit{TrajectoryType} attributes into distinct object types. In addition, we add a new moving object type since a trajectory is always the result of a moving object. 

Design patterns are well known artifacts in the software engineering literature. They aim at facilitating and organizing the development process, providing pre-defined solutions to known problems in software design. Unlike the area of software engineering, where design patterns focus on models for software, this paper proposes the use of design standards for the construction of database schemas related to moving objects trajectories. Basically, the idea is to provide an off-the-shelf data schema using semantic trajectory concept and points of extension (called hooks in the literature). Extension points can be used by the designer to attach semantic information related to trajectory data. 

%***************************VCT
%no paragrafo acima, acrescentei: database schemas "RELATED TO MOVING OBJECTS TRAJECTORIES" e acrescentei: to attach "SEMANTIC"
%
%
%********

To meet application requirements related to real time or historical analysis, we propose two design patterns. We assume that transactional schemes are suitable for building applications that perform analysis in real time, and multidimensional schemes are ideal to carry out historical analysis. Therefore, we specify two design patterns, one for instantiating data schemas for transactional environment and another one for creating database schemas in a multidimensional environment.

Figure~\ref{fig:dptransactional} depicted the proposed design pattern for a transactional schema. This trajectory design pattern holds object types for representing trajectories, their events (a subcomponent of a trajectory) and moving objects. In fact, we assume that moving objects, trajectories and events are the common information needed by database designers of trajectory management applications. In addition to structure trajectory data, this design pattern includes hooks used to connect to application objects. In Figure~\ref{fig:dptransactional}, the hooks are represented as a box with dashed border. Trajectories are linked to a \textit{MovingObjectType} object type that represents the traveling objects covering the trajectories. Hence, a designer can instantiate a data schema from this design pattern by defining new attributes for the object types and substituting hook objects by application object types. 

\begin{figure}[tb]
	\centering
		\includegraphics[width=0.9\textwidth]{imagens/TrajectoryPattern2.eps}
	\caption{Trajectory Design Pattern for Transactional Environment}
	\label{fig:dptransactional}
\end{figure}

%\subsection{Steps for creating semantic trajectory type}\label{constructalg}

Algorithm 1 populates a transactional schema that instantiates the design pattern presented in Figure~\ref{fig:datatype}. It takes the raw spatio-temporal points generated by a positioning device (line 1), and, for each moving object, it creates an instance of MovingObjectType (line 2). Next, it calls a function, provided by the designer, to construct trajectories (line 3). For each trajectory this function constructs, an instance of TrajectoryType is created (line 5). Finally, it uses another function provided by the designer to segment a trajectory into a list of events (line 6). 

 \begin{algorithm}
 \caption{Populate Transactional Schema} 
 \label{populateTrans} 
 \begin{algorithmic} [1] 
\FOR{each distinct $moid$ in the Raw Spatio-Temporal Dataset} 
	\STATE  creates an instance $mo$ of \textit{MovingObjectType} 
	\STATE  $mo.trajList$ =  trajectorySegmentation(lp)
	\FOR{each trajectory $ti$  $\in$  \textit{trajList} } 
		\STATE  creates an instance $tr$ of  \textit{TrajectoryType} 
		\STATE  $tr$.eventList =  eventSegmentation(ti)
	\ENDFOR

\ENDFOR
 \end{algorithmic} 
 \end{algorithm}

\subsection{Multidimensional Environment}\label{sub:multidimensional}

Multidimensional modeling refers to a set of techniques and concepts used in data warehouse design. The multidimensional model is composed by two main conceptual constructors, called $fact$ and $dimension$. Facts are values (in general, numeric) that can be aggregated, and dimensions are groups of hierarchies and descriptors that contextualize the facts.

Figure \ref{fig:designpatternDW} shows the design pattern for a multidimensional modeling. We use UML notation for this design pattern, and sterotypes are used to denote fact and dimension classes. Dimensions are represented with traced lines, indicating that they are extension points (hooks). Dimensions can be extended with new hierarchies and properties. Facts accept extensions on measures but existing measures must be preserved in order to follow trajectory data type proposal.

In this design pattern, we use \textit{TrajectoryType} and \textit{EventType} as measures of multidimensional models, which define that aggregations will be made over trajectory and event facts. Indeed, these facts represent the geometric and semantic view on trajectories that is coherent with the idea of exposing the trajectory components. One example of geometric aggregation is the union of trajectories that exceed a certain speed threshold and that intersect a given \textit{ad hoc} query window. An example of an aggregation function for events is the average duration of an event of type "Lunch". 

Since a trajectory is inherently a spatio-temporal object resulting from traveling moving object, we propose three generic dimensions that are shared by trajectory and event facts: Time, Region (Space), and Moving Object. In addition, the \textit{TrajectoryCategory} and \textit{EventCategory} dimensions are defined to characterize aggregations over trajectory and event facts, respectively. It is worth noting that \textit{EventType} facts contain an attribute referring to the trajectory identification, (\textit{trid}), which is used to specify the degenerated Trajectory dimension. We assume that, for some trajectory applications, it is important to apply aggregations to trajectory ids, for instance, to compute the number of events of type "delivery gas" in trajectory id "13052".

\begin{figure}[tb]
	\centering
		\includegraphics[width=0.8\textwidth]{imagens/designpatternDW2.eps} 
	\caption{Trajectory Design Pattern for Multidimensional Environment}
	\label{fig:designpatternDW}
\end{figure}

Multidimensional modeling should include a process to extract and transform data from the source OLTP systems to feed a data warehouse, called \textit{ETL process}. In our scenario, the first step of the ETL process is to populate all levels from the hierarchy dimensions with values from the \textit{TrajectoryType} and \textit{EventType} attributes stored in the transactional schema. For example, the time dimension must be populated with values ranging over trajectories lifespan, and the \textit{EventCategory} dimension must cover all event categories of interest. For the region dimension, a topological spatial function (e.g. inside, crosses and near by) must be provided by the application designer to establish the spatial relationships between \textit{TrajectoryType} facts and the \textit{Region} dimension. We observe that a region dimension may not have a well-defined hierarchy (e.g. a predefined spatial hierarchy with a 1:N relationship among higher and lower attribute levels), as a trajectory geometry may not be associated with all levels of the region hierarchy. For example, a trajectory may be inside the State of Sao Paulo, but not inside any of its cities. A solution to this problem is to set $null$ to all region levels that do not match.

After populating the dimensions, we are able to extract the facts. Algoritm~\ref{alg:populateMulti} populates the TrajectoryType facts (line 1) and create links to the dimensions (lines 3-12). Lines 5 to 12 create links to the asymmetrical hierarchy~\cite{Malinowski2004} of the Region dimension.

 \begin{algorithm}
 \caption{Populate Multidimensional Schema} 
 \label{alg:populateMulti} 
 \begin{algorithmic} [1]
 \FOR{each trajectory $ti$ of \textit{TrajectoryType} table in transactional schema} 
 	\STATE  copy $ti$  to the trajectory fact in the multidimensional schema
	\STATE  create two links to the lowest level of Time dimension using $ti.trbegin$ and $ti.trtEnd$ properties
	\STATE  create one link to the lowest level of Moving Object dimension using $ti.oid$;
	\FOR{each hierarchical level $rl$ of Region dimension ordered in ascending order}
		\IF {$SpatialTopologicalFunction$($ti.geometry$,$rl.geometry$)=true}
			\STATE  create a link to the level $rl$ of Region dimension
			\STATE  break
		\ELSE
			\STATE  set $null$ to link to the level $rl$ of Region dimension
		\ENDIF
		\STATE  create one link to the lowest level of Trajectory Category dimension using $ti.category()$ function;
	\ENDFOR
%	get the geometry line for entire life span of the trajectory and check the relation inside with each element of superior level of dimension; if there is a match momentarily the relation are point to this element and then do the same with the next lower level for the elements that correspond with the setted in high level; repeat until you reach the lowest level of the dimension or you don't find a match. In cases that you don't find a match for the level the relation will point to the element of the dimension that has the superior levels found and the lowers setted as null.
\ENDFOR
 \end{algorithmic} 
 \end{algorithm}

%\begin{enumerate}
%	\item each instance of \textit{TrajectoryType} in the transactional schema must be add it in the trajectory fact in the multidimensional schema;
%	\item for each element of trajectory fact
%	\begin{itemize}
%		\item retrieve the instant from your begin STPoint and compare with the elements of the begin time dimension to set the appropriate link; do the same for trajectory fact end STPoint do define the link between the fact and end time dimension;
%		\item identify the moving object that originated each trajectory fact and assign the relation with the element of moving object dimension that represent it;
%		\item get the geometry line for entire life span of the trajectory and check the relation inside with each element of superior level of dimension; if there is a match momentarily the relation are point to this element and then do the same with the next lower level for the elements that correspond with the setted in high level; repeat until you reach the lowest level of the dimension or you don't find a match. In cases that you don't find a match for the level the relation will point to the element of the dimension that has the superior levels found and the lowers setted as null.
%	\end{itemize}	
%\end{enumerate}

The process for populating the \textit{EventType} facts is very similar. We must apply the same steps, except that we must replace \textit{TrajectoryType} by \textit{EventType} and add one more instruction to link events to values of the \textit{EventCategory} dimension, which must be supplied by a function provided by the designer (similar to the category function for trajectories, shown in line 12 of Algorithm~\ref{alg:populateMulti}).

\subsection{Aggregation Functions for Trajectories}\label{secao:contribuicoes2}

From an analytical point of view, it is fundamental to provide summarized information from a large collection of trajectory data. Aggregation functions have been widely used in database and decision-support applications with this purpose. However, the available aggregation functions for transactional and multidimensional environments are not appropriate to aggregate complex objects such as trajectories. Therefore, we propose to enhance the analytical processing capabilities of trajectory applications by introducing a new family of analytic functions for trajectory data. 

The proposed family of aggregation functions for trajectories reduces a set of trajectories to a single trajectory, to a line, to a time interval, or to a scalar value. However, we do not propose specific aggregation functions, since we believe that it is the responsibility of the designer to identify which functions are of interest to her/his application and to define their semantics. Instead, we introduce a generic signature that helps specifying a large number of trajectory aggregation functions, defined as follows:

\begin{center}
 $OP : T$ x $F \to D$ where 
\end{center}

\begin{itemize}
	\item $OP$ represents the following aggregation operations: SUM, COUNT, AVERAGE, MIN, and MAX;
	\item $T$ is a trajectory data set;
	\item $F$ defines which trajectory feature type is used by the aggregation operation $OP$. A trajectory feature is any information that can be computed or obtained from a trajectory (for instance, geometry, length, lifespan, set of sample points/events, etc). The possible trajectory feature types are: TRAJECTORY, SPATIAL, TEMPORAL, SET, and NUMERIC. 
	\item $D$ is the output data type
\end{itemize}


For example, Table~\ref{tab:aggfunc} illustrates some functions that have this generic signature. In the examples, the variable $t$ is of type \textit{TrajectoryType} and represents the set of trajectories being aggregated. Trajectory feature values are computed by trajectory functions that must be implemented in the \textit{TrajectoryType} data type. For example, in the second line of Table~\ref{tab:aggfunc}, the function  $t.events("LUNCH")$ returns a set of events with description "LUNCH". 

\begin{table}[t]
	\caption{Examples of Trajectory Aggregation Functions}
	\label{tab:aggfunc}
		\sffamily % CHANGES THE FONT WITHIN THE TABLE TO sans serif
		\begin{center}		
\scalebox{0.84}{
		\begin{tabular}{|p{6cm}|p{6cm}|p{5cm}|}
			\hline
			SIGNATURE & Example & Meaning \\
			\hline
			COUNT (T, T.ATTR) : NUMERIC & tr\_aggr\_count (t, t.events("LUNCH")) & returns the number of events of type "LUNCH" in a set of trajectories \\
			\hline
			AVERAGE (T, T.ATTR) : TEMPORAL & tr\_aggr\_avg\_temporal (t, t.lifespan()) & returns the average interval of a set of trajectories \\
			\hline
			MIN (T, T.ATTR) : TRAJECTORY & tr\_aggr\_min\_spatial (t, t.geometry()) & returns the shortest trajectory in space from a set of trajectories \\
			\hline
			MAX (T, T.ATTR) : SPATIAL & tr\_aggr\_max\_spatial (t, t.geometry()) & returns the geometry line from the longest trajectory in space of a set of trajectories \\
			\hline
		\end{tabular}
}
		\end{center}
		\rmfamily % RESTORES TO TIMES, SO THAT CAPTION IS WRITTEN PROPERLY
\end{table}